lib/gl_array_list.c

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