lib/gl_array_list.c

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