lib/gl_array_list.c

   1 /* Sequential list data type implemented by an array.
   2    Copyright (C) 2006 Free Software Foundation, Inc.
   3    Written by Bruno Haible <bruno@clisp.org>, 2006.
   4
   5    This program is free software; you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; either version 2, or (at your option)
   8    any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program; if not, write to the Free Software Foundation,
  17    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  18
  19 #include <config.h>
  20
  21 /* Specification.  */
  22 #include "gl_array_list.h"
  23
  24 #include <stdlib.h>
  25 /* Get memcpy.  */
  26 #include <string.h>
  27
  28 #include "xalloc.h"
  29
  30 /* Checked size_t computations.  */
  31 #include "xsize.h"
  32
  33 #ifndef uintptr_t
  34 # define uintptr_t unsigned long
  35 #endif
  36
  37 /* -------------------------- gl_list_t Data Type -------------------------- */
  38
  39 /* Concrete gl_list_impl type, valid for this file only.  */
  40 struct gl_list_impl
  41 {
  42   struct gl_list_impl_base base;
  43   /* An array of ALLOCATED elements, of which the first COUNT are used.
  44      0 <= COUNT <= ALLOCATED.  */
  45   const void **elements;
  46   size_t count;
  47   size_t allocated;
  48 };
  49
  50 /* struct gl_list_node_impl doesn't exist here.  The pointers are actually
  51    indices + 1.  */
  52 #define INDEX_TO_NODE(index) (gl_list_node_t)(uintptr_t)(size_t)((index) + 1)
  53 #define NODE_TO_INDEX(node) ((uintptr_t)(node) - 1)
  54
  55 static gl_list_t
  56 gl_array_create_empty (gl_list_implementation_t implementation,
  57                        gl_listelement_equals_fn equals_fn,
  58                        gl_listelement_hashcode_fn hashcode_fn,
  59                        bool allow_duplicates)
  60 {
  61   struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
  62
  63   list->base.vtable = implementation;
  64   list->base.equals_fn = equals_fn;
  65   list->base.hashcode_fn = hashcode_fn;
  66   list->base.allow_duplicates = allow_duplicates;
  67   list->elements = NULL;
  68   list->count = 0;
  69   list->allocated = 0;
  70
  71   return list;
  72 }
  73
  74 static gl_list_t
  75 gl_array_create (gl_list_implementation_t implementation,
  76                  gl_listelement_equals_fn equals_fn,
  77                  gl_listelement_hashcode_fn hashcode_fn,
  78                  bool allow_duplicates,
  79                  size_t count, const void **contents)
  80 {
  81   struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
  82
  83   list->base.vtable = implementation;
  84   list->base.equals_fn = equals_fn;
  85   list->base.hashcode_fn = hashcode_fn;
  86   list->base.allow_duplicates = allow_duplicates;
  87   if (count > 0)
  88     {
  89       list->elements = XNMALLOC (count, const void *);
  90       memcpy (list->elements, contents, count * sizeof (const void *));
  91     }
  92   else
  93     list->elements = NULL;
  94   list->count = count;
  95   list->allocated = count;
  96
  97   return list;
  98 }
  99
 100 static size_t
 101 gl_array_size (gl_list_t list)
 102 {
 103   return list->count;
 104 }
 105
 106 static const void *
 107 gl_array_node_value (gl_list_t list, gl_list_node_t node)
 108 {
 109   uintptr_t index = NODE_TO_INDEX (node);
 110   if (!(index < list->count))
 111     /* Invalid argument.  */
 112     abort ();
 113   return list->elements[index];
 114 }
 115
 116 static gl_list_node_t
 117 gl_array_next_node (gl_list_t list, gl_list_node_t node)
 118 {
 119   uintptr_t index = NODE_TO_INDEX (node);
 120   if (!(index < list->count))
 121     /* Invalid argument.  */
 122     abort ();
 123   index++;
 124   if (index < list->count)
 125     return INDEX_TO_NODE (index);
 126   else
 127     return NULL;
 128 }
 129
 130 static gl_list_node_t
 131 gl_array_previous_node (gl_list_t list, gl_list_node_t node)
 132 {
 133   uintptr_t index = NODE_TO_INDEX (node);
 134   if (!(index < list->count))
 135     /* Invalid argument.  */
 136     abort ();
 137   if (index > 0)
 138     return INDEX_TO_NODE (index - 1);
 139   else
 140     return NULL;
 141 }
 142
 143 static const void *
 144 gl_array_get_at (gl_list_t list, size_t position)
 145 {
 146   size_t count = list->count;
 147
 148   if (!(position < count))
 149     /* Invalid argument.  */
 150     abort ();
 151   return list->elements[position];
 152 }
 153
 154 static gl_list_node_t
 155 gl_array_set_at (gl_list_t list, size_t position, const void *elt)
 156 {
 157   size_t count = list->count;
 158
 159   if (!(position < count))
 160     /* Invalid argument.  */
 161     abort ();
 162   list->elements[position] = elt;
 163   return INDEX_TO_NODE (position);
 164 }
 165
 166 static size_t
 167 gl_array_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
 168                           const void *elt)
 169 {
 170   size_t count = list->count;
 171
 172   if (!(start_index <= end_index && end_index <= count))
 173     /* Invalid arguments.  */
 174     abort ();
 175
 176   if (start_index < end_index)
 177     {
 178       gl_listelement_equals_fn equals = list->base.equals_fn;
 179       if (equals != NULL)
 180         {
 181           size_t i;
 182
 183           for (i = start_index;;)
 184             {
 185               if (equals (elt, list->elements[i]))
 186                 return i;
 187               i++;
 188               if (i == end_index)
 189                 break;
 190             }
 191         }
 192       else
 193         {
 194           size_t i;
 195
 196           for (i = start_index;;)
 197             {
 198               if (elt == list->elements[i])
 199                 return i;
 200               i++;
 201               if (i == end_index)
 202                 break;
 203             }
 204         }
 205     }
 206   return (size_t)(-1);
 207 }
 208
 209 static gl_list_node_t
 210 gl_array_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
 211                          const void *elt)
 212 {
 213   size_t index = gl_array_indexof_from_to (list, start_index, end_index, elt);
 214   return INDEX_TO_NODE (index);
 215 }
 216
 217 /* Ensure that list->allocated > list->count.  */
 218 static void
 219 grow (gl_list_t list)
 220 {
 221   size_t new_allocated;
 222   size_t memory_size;
 223   const void **memory;
 224
 225   new_allocated = xtimes (list->allocated, 2);
 226   new_allocated = xsum (new_allocated, 1);
 227   memory_size = xtimes (new_allocated, sizeof (const void *));
 228   if (size_overflow_p (memory_size))
 229     /* Overflow, would lead to out of memory.  */
 230     xalloc_die ();
 231   memory = (const void **) xrealloc (list->elements, memory_size);
 232   if (memory == NULL)
 233     /* Out of memory.  */
 234     xalloc_die ();
 235   list->elements = memory;
 236   list->allocated = new_allocated;
 237 }
 238
 239 static gl_list_node_t
 240 gl_array_add_first (gl_list_t list, const void *elt)
 241 {
 242   size_t count = list->count;
 243   const void **elements;
 244   size_t i;
 245
 246   if (count == list->allocated)
 247     grow (list);
 248   elements = list->elements;
 249   for (i = count; i > 0; i--)
 250     elements[i] = elements[i - 1];
 251   elements[0] = elt;
 252   list->count = count + 1;
 253   return INDEX_TO_NODE (0);
 254 }
 255
 256 static gl_list_node_t
 257 gl_array_add_last (gl_list_t list, const void *elt)
 258 {
 259   size_t count = list->count;
 260
 261   if (count == list->allocated)
 262     grow (list);
 263   list->elements[count] = elt;
 264   list->count = count + 1;
 265   return INDEX_TO_NODE (count);
 266 }
 267
 268 static gl_list_node_t
 269 gl_array_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
 270 {
 271   size_t count = list->count;
 272   uintptr_t index = NODE_TO_INDEX (node);
 273   size_t position;
 274   const void **elements;
 275   size_t i;
 276
 277   if (!(index < count))
 278     /* Invalid argument.  */
 279     abort ();
 280   position = index;
 281   if (count == list->allocated)
 282     grow (list);
 283   elements = list->elements;
 284   for (i = count; i > position; i--)
 285     elements[i] = elements[i - 1];
 286   elements[position] = elt;
 287   list->count = count + 1;
 288   return INDEX_TO_NODE (position);
 289 }
 290
 291 static gl_list_node_t
 292 gl_array_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
 293 {
 294   size_t count = list->count;
 295   uintptr_t index = NODE_TO_INDEX (node);
 296   size_t position;
 297   const void **elements;
 298   size_t i;
 299
 300   if (!(index < count))
 301     /* Invalid argument.  */
 302     abort ();
 303   position = index + 1;
 304   if (count == list->allocated)
 305     grow (list);
 306   elements = list->elements;
 307   for (i = count; i > position; i--)
 308     elements[i] = elements[i - 1];
 309   elements[position] = elt;
 310   list->count = count + 1;
 311   return INDEX_TO_NODE (position);
 312 }
 313
 314 static gl_list_node_t
 315 gl_array_add_at (gl_list_t list, size_t position, const void *elt)
 316 {
 317   size_t count = list->count;
 318   const void **elements;
 319   size_t i;
 320
 321   if (!(position <= count))
 322     /* Invalid argument.  */
 323     abort ();
 324   if (count == list->allocated)
 325     grow (list);
 326   elements = list->elements;
 327   for (i = count; i > position; i--)
 328     elements[i] = elements[i - 1];
 329   elements[position] = elt;
 330   list->count = count + 1;
 331   return INDEX_TO_NODE (position);
 332 }
 333
 334 static bool
 335 gl_array_remove_node (gl_list_t list, gl_list_node_t node)
 336 {
 337   size_t count = list->count;
 338   uintptr_t index = NODE_TO_INDEX (node);
 339   size_t position;
 340   const void **elements;
 341   size_t i;
 342
 343   if (!(index < count))
 344     /* Invalid argument.  */
 345     abort ();
 346   position = index;
 347   elements = list->elements;
 348   for (i = position + 1; i < count; i++)
 349     elements[i - 1] = elements[i];
 350   list->count = count - 1;
 351   return true;
 352 }
 353
 354 static bool
 355 gl_array_remove_at (gl_list_t list, size_t position)
 356 {
 357   size_t count = list->count;
 358   const void **elements;
 359   size_t i;
 360
 361   if (!(position < count))
 362     /* Invalid argument.  */
 363     abort ();
 364   elements = list->elements;
 365   for (i = position + 1; i < count; i++)
 366     elements[i - 1] = elements[i];
 367   list->count = count - 1;
 368   return true;
 369 }
 370
 371 static bool
 372 gl_array_remove (gl_list_t list, const void *elt)
 373 {
 374   size_t position = gl_array_indexof_from_to (list, 0, list->count, elt);
 375   if (position == (size_t)(-1))
 376     return false;
 377   else
 378     return gl_array_remove_at (list, position);
 379 }
 380
 381 static void
 382 gl_array_list_free (gl_list_t list)
 383 {
 384   if (list->elements != NULL)
 385     free (list->elements);
 386   free (list);
 387 }
 388
 389 /* --------------------- gl_list_iterator_t Data Type --------------------- */
 390
 391 static gl_list_iterator_t
 392 gl_array_iterator (gl_list_t list)
 393 {
 394   gl_list_iterator_t result;
 395
 396   result.vtable = list->base.vtable;
 397   result.list = list;
 398   result.count = list->count;
 399   result.p = list->elements + 0;
 400   result.q = list->elements + list->count;
 401 #ifdef lint
 402   result.i = 0;
 403   result.j = 0;
 404 #endif
 405
 406   return result;
 407 }
 408
 409 static gl_list_iterator_t
 410 gl_array_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
 411 {
 412   gl_list_iterator_t result;
 413
 414   if (!(start_index <= end_index && end_index <= list->count))
 415     /* Invalid arguments.  */
 416     abort ();
 417   result.vtable = list->base.vtable;
 418   result.list = list;
 419   result.count = list->count;
 420   result.p = list->elements + start_index;
 421   result.q = list->elements + end_index;
 422 #ifdef lint
 423   result.i = 0;
 424   result.j = 0;
 425 #endif
 426
 427   return result;
 428 }
 429
 430 static bool
 431 gl_array_iterator_next (gl_list_iterator_t *iterator,
 432                         const void **eltp, gl_list_node_t *nodep)
 433 {
 434   gl_list_t list = iterator->list;
 435   if (iterator->count != list->count)
 436     {
 437       if (iterator->count != list->count + 1)
 438         /* Concurrent modifications were done on the list.  */
 439         abort ();
 440       /* The last returned element was removed.  */
 441       iterator->count--;
 442       iterator->p = (const void **) iterator->p - 1;
 443       iterator->q = (const void **) iterator->q - 1;
 444     }
 445   if (iterator->p < iterator->q)
 446     {
 447       const void **p = (const void **) iterator->p;
 448       *eltp = *p;
 449       if (nodep != NULL)
 450         *nodep = INDEX_TO_NODE (p - list->elements);
 451       iterator->p = p + 1;
 452       return true;
 453     }
 454   else
 455     return false;
 456 }
 457
 458 static void
 459 gl_array_iterator_free (gl_list_iterator_t *iterator)
 460 {
 461 }
 462
 463 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
 464
 465 static size_t
 466 gl_array_sortedlist_indexof_from_to (gl_list_t list,
 467                                      gl_listelement_compar_fn compar,
 468                                      size_t low, size_t high,
 469                                      const void *elt)
 470 {
 471   if (!(low <= high && high <= list->count))
 472     /* Invalid arguments.  */
 473     abort ();
 474   if (low < high)
 475     {
 476       /* At each loop iteration, low < high; for indices < low the values
 477          are smaller than ELT; for indices >= high the values are greater
 478          than ELT.  So, if the element occurs in the list, it is at
 479          low <= position < high.  */
 480       do
 481         {
 482           size_t mid = low + (high - low) / 2; /* low <= mid < high */
 483           int cmp = compar (list->elements[mid], elt);
 484
 485           if (cmp < 0)
 486             low = mid + 1;
 487           else if (cmp > 0)
 488             high = mid;
 489           else /* cmp == 0 */
 490             {
 491               /* We have an element equal to ELT at index MID.  But we need
 492                  the minimal such index.  */
 493               high = mid;
 494               /* At each loop iteration, low <= high and
 495                    compar (list->elements[high], elt) == 0,
 496                  and we know that the first occurrence of the element is at
 497                  low <= position <= high.  */
 498               while (low < high)
 499                 {
 500                   size_t mid2 = low + (high - low) / 2; /* low <= mid2 < high */
 501                   int cmp2 = compar (list->elements[mid2], elt);
 502
 503                   if (cmp2 < 0)
 504                     low = mid2 + 1;
 505                   else if (cmp2 > 0)
 506                     /* The list was not sorted.  */
 507                     abort ();
 508                   else /* cmp2 == 0 */
 509                     {
 510                       if (mid2 == low)
 511                         break;
 512                       high = mid2 - 1;
 513                     }
 514                 }
 515               return low;
 516             }
 517         }
 518       while (low < high);
 519       /* Here low == high.  */
 520     }
 521   return (size_t)(-1);
 522 }
 523
 524 static size_t
 525 gl_array_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
 526                              const void *elt)
 527 {
 528   return gl_array_sortedlist_indexof_from_to (list, compar, 0, list->count,
 529                                               elt);
 530 }
 531
 532 static gl_list_node_t
 533 gl_array_sortedlist_search_from_to (gl_list_t list,
 534                                     gl_listelement_compar_fn compar,
 535                                     size_t low, size_t high,
 536                                     const void *elt)
 537 {
 538   size_t index =
 539     gl_array_sortedlist_indexof_from_to (list, compar, low, high, elt);
 540   return INDEX_TO_NODE (index);
 541 }
 542
 543 static gl_list_node_t
 544 gl_array_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
 545                             const void *elt)
 546 {
 547   size_t index =
 548     gl_array_sortedlist_indexof_from_to (list, compar, 0, list->count, elt);
 549   return INDEX_TO_NODE (index);
 550 }
 551
 552 static gl_list_node_t
 553 gl_array_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
 554                          const void *elt)
 555 {
 556   size_t count = list->count;
 557   size_t low = 0;
 558   size_t high = count;
 559
 560   /* At each loop iteration, low <= high; for indices < low the values are
 561      smaller than ELT; for indices >= high the values are greater than ELT.  */
 562   while (low < high)
 563     {
 564       size_t mid = low + (high - low) / 2; /* low <= mid < high */
 565       int cmp = compar (list->elements[mid], elt);
 566
 567       if (cmp < 0)
 568         low = mid + 1;
 569       else if (cmp > 0)
 570         high = mid;
 571       else /* cmp == 0 */
 572         {
 573           low = mid;
 574           break;
 575         }
 576     }
 577   return gl_array_add_at (list, low, elt);
 578 }
 579
 580 static bool
 581 gl_array_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
 582                             const void *elt)
 583 {
 584   size_t index = gl_array_sortedlist_indexof (list, compar, elt);
 585   if (index == (size_t)(-1))
 586     return false;
 587   else
 588     return gl_array_remove_at (list, index);
 589 }
 590
 591
 592 const struct gl_list_implementation gl_array_list_implementation =
 593   {
 594     gl_array_create_empty,
 595     gl_array_create,
 596     gl_array_size,
 597     gl_array_node_value,
 598     gl_array_next_node,
 599     gl_array_previous_node,
 600     gl_array_get_at,
 601     gl_array_set_at,
 602     gl_array_search_from_to,
 603     gl_array_indexof_from_to,
 604     gl_array_add_first,
 605     gl_array_add_last,
 606     gl_array_add_before,
 607     gl_array_add_after,
 608     gl_array_add_at,
 609     gl_array_remove_node,
 610     gl_array_remove_at,
 611     gl_array_remove,
 612     gl_array_list_free,
 613     gl_array_iterator,
 614     gl_array_iterator_from_to,
 615     gl_array_iterator_next,
 616     gl_array_iterator_free,
 617     gl_array_sortedlist_search,
 618     gl_array_sortedlist_search_from_to,
 619     gl_array_sortedlist_indexof,
 620     gl_array_sortedlist_indexof_from_to,
 621     gl_array_sortedlist_add,
 622     gl_array_sortedlist_remove
 623   };