lib/gl_array_list.c

   1 /* Sequential list data type implemented by an array.
   2    Copyright (C) 2006-2020 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 <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
 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 const void * _GL_ATTRIBUTE_PURE
 170 gl_array_get_at (gl_list_t list, size_t position)
 171 {
 172   size_t count = list->count;
 173
 174   if (!(position < count))
 175     /* Invalid argument.  */
 176     abort ();
 177   return list->elements[position];
 178 }
 179
 180 static gl_list_node_t
 181 gl_array_nx_set_at (gl_list_t list, size_t position, const void *elt)
 182 {
 183   size_t count = list->count;
 184
 185   if (!(position < count))
 186     /* Invalid argument.  */
 187     abort ();
 188   list->elements[position] = elt;
 189   return INDEX_TO_NODE (position);
 190 }
 191
 192 static size_t
 193 gl_array_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
 194                           const void *elt)
 195 {
 196   size_t count = list->count;
 197
 198   if (!(start_index <= end_index && end_index <= count))
 199     /* Invalid arguments.  */
 200     abort ();
 201
 202   if (start_index < end_index)
 203     {
 204       gl_listelement_equals_fn equals = list->base.equals_fn;
 205       if (equals != NULL)
 206         {
 207           size_t i;
 208
 209           for (i = start_index;;)
 210             {
 211               if (equals (elt, list->elements[i]))
 212                 return i;
 213               i++;
 214               if (i == end_index)
 215                 break;
 216             }
 217         }
 218       else
 219         {
 220           size_t i;
 221
 222           for (i = start_index;;)
 223             {
 224               if (elt == list->elements[i])
 225                 return i;
 226               i++;
 227               if (i == end_index)
 228                 break;
 229             }
 230         }
 231     }
 232   return (size_t)(-1);
 233 }
 234
 235 static gl_list_node_t
 236 gl_array_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
 237                          const void *elt)
 238 {
 239   size_t index = gl_array_indexof_from_to (list, start_index, end_index, elt);
 240   return INDEX_TO_NODE (index);
 241 }
 242
 243 /* Ensure that list->allocated > list->count.
 244    Return 0 upon success, -1 upon out-of-memory.  */
 245 static int
 246 grow (gl_list_t list)
 247 {
 248   size_t new_allocated;
 249   size_t memory_size;
 250   const void **memory;
 251
 252   new_allocated = xtimes (list->allocated, 2);
 253   new_allocated = xsum (new_allocated, 1);
 254   memory_size = xtimes (new_allocated, sizeof (const void *));
 255   if (size_overflow_p (memory_size))
 256     /* Overflow, would lead to out of memory.  */
 257     return -1;
 258   memory = (const void **) realloc (list->elements, memory_size);
 259   if (memory == NULL)
 260     /* Out of memory.  */
 261     return -1;
 262   list->elements = memory;
 263   list->allocated = new_allocated;
 264   return 0;
 265 }
 266
 267 static gl_list_node_t
 268 gl_array_nx_add_first (gl_list_t list, const void *elt)
 269 {
 270   size_t count = list->count;
 271   const void **elements;
 272   size_t i;
 273
 274   if (count == list->allocated)
 275     if (grow (list) < 0)
 276       return NULL;
 277   elements = list->elements;
 278   for (i = count; i > 0; i--)
 279     elements[i] = elements[i - 1];
 280   elements[0] = elt;
 281   list->count = count + 1;
 282   return INDEX_TO_NODE (0);
 283 }
 284
 285 static gl_list_node_t
 286 gl_array_nx_add_last (gl_list_t list, const void *elt)
 287 {
 288   size_t count = list->count;
 289
 290   if (count == list->allocated)
 291     if (grow (list) < 0)
 292       return NULL;
 293   list->elements[count] = elt;
 294   list->count = count + 1;
 295   return INDEX_TO_NODE (count);
 296 }
 297
 298 static gl_list_node_t
 299 gl_array_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
 300 {
 301   size_t count = list->count;
 302   uintptr_t index = NODE_TO_INDEX (node);
 303   size_t position;
 304   const void **elements;
 305   size_t i;
 306
 307   if (!(index < count))
 308     /* Invalid argument.  */
 309     abort ();
 310   position = index;
 311   if (count == list->allocated)
 312     if (grow (list) < 0)
 313       return NULL;
 314   elements = list->elements;
 315   for (i = count; i > position; i--)
 316     elements[i] = elements[i - 1];
 317   elements[position] = elt;
 318   list->count = count + 1;
 319   return INDEX_TO_NODE (position);
 320 }
 321
 322 static gl_list_node_t
 323 gl_array_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
 324 {
 325   size_t count = list->count;
 326   uintptr_t index = NODE_TO_INDEX (node);
 327   size_t position;
 328   const void **elements;
 329   size_t i;
 330
 331   if (!(index < count))
 332     /* Invalid argument.  */
 333     abort ();
 334   position = index + 1;
 335   if (count == list->allocated)
 336     if (grow (list) < 0)
 337       return NULL;
 338   elements = list->elements;
 339   for (i = count; i > position; i--)
 340     elements[i] = elements[i - 1];
 341   elements[position] = elt;
 342   list->count = count + 1;
 343   return INDEX_TO_NODE (position);
 344 }
 345
 346 static gl_list_node_t
 347 gl_array_nx_add_at (gl_list_t list, size_t position, const void *elt)
 348 {
 349   size_t count = list->count;
 350   const void **elements;
 351   size_t i;
 352
 353   if (!(position <= count))
 354     /* Invalid argument.  */
 355     abort ();
 356   if (count == list->allocated)
 357     if (grow (list) < 0)
 358       return NULL;
 359   elements = list->elements;
 360   for (i = count; i > position; i--)
 361     elements[i] = elements[i - 1];
 362   elements[position] = elt;
 363   list->count = count + 1;
 364   return INDEX_TO_NODE (position);
 365 }
 366
 367 static bool
 368 gl_array_remove_node (gl_list_t list, gl_list_node_t node)
 369 {
 370   size_t count = list->count;
 371   uintptr_t index = NODE_TO_INDEX (node);
 372   size_t position;
 373   const void **elements;
 374   size_t i;
 375
 376   if (!(index < count))
 377     /* Invalid argument.  */
 378     abort ();
 379   position = index;
 380   elements = list->elements;
 381   if (list->base.dispose_fn != NULL)
 382     list->base.dispose_fn (elements[position]);
 383   for (i = position + 1; i < count; i++)
 384     elements[i - 1] = elements[i];
 385   list->count = count - 1;
 386   return true;
 387 }
 388
 389 static bool
 390 gl_array_remove_at (gl_list_t list, size_t position)
 391 {
 392   size_t count = list->count;
 393   const void **elements;
 394   size_t i;
 395
 396   if (!(position < count))
 397     /* Invalid argument.  */
 398     abort ();
 399   elements = list->elements;
 400   if (list->base.dispose_fn != NULL)
 401     list->base.dispose_fn (elements[position]);
 402   for (i = position + 1; i < count; i++)
 403     elements[i - 1] = elements[i];
 404   list->count = count - 1;
 405   return true;
 406 }
 407
 408 static bool
 409 gl_array_remove (gl_list_t list, const void *elt)
 410 {
 411   size_t position = gl_array_indexof_from_to (list, 0, list->count, elt);
 412   if (position == (size_t)(-1))
 413     return false;
 414   else
 415     return gl_array_remove_at (list, position);
 416 }
 417
 418 static void
 419 gl_array_list_free (gl_list_t list)
 420 {
 421   if (list->elements != NULL)
 422     {
 423       if (list->base.dispose_fn != NULL)
 424         {
 425           size_t count = list->count;
 426
 427           if (count > 0)
 428             {
 429               gl_listelement_dispose_fn dispose = list->base.dispose_fn;
 430               const void **elements = list->elements;
 431
 432               do
 433                 dispose (*elements++);
 434               while (--count > 0);
 435             }
 436         }
 437       free (list->elements);
 438     }
 439   free (list);
 440 }
 441
 442 /* --------------------- gl_list_iterator_t Data Type --------------------- */
 443
 444 static gl_list_iterator_t
 445 gl_array_iterator (gl_list_t list)
 446 {
 447   gl_list_iterator_t result;
 448
 449   result.vtable = list->base.vtable;
 450   result.list = list;
 451   result.count = list->count;
 452   result.p = list->elements + 0;
 453   result.q = list->elements + list->count;
 454 #if defined GCC_LINT || defined lint
 455   result.i = 0;
 456   result.j = 0;
 457 #endif
 458
 459   return result;
 460 }
 461
 462 static gl_list_iterator_t
 463 gl_array_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
 464 {
 465   gl_list_iterator_t result;
 466
 467   if (!(start_index <= end_index && end_index <= list->count))
 468     /* Invalid arguments.  */
 469     abort ();
 470   result.vtable = list->base.vtable;
 471   result.list = list;
 472   result.count = list->count;
 473   result.p = list->elements + start_index;
 474   result.q = list->elements + end_index;
 475 #if defined GCC_LINT || defined lint
 476   result.i = 0;
 477   result.j = 0;
 478 #endif
 479
 480   return result;
 481 }
 482
 483 static bool
 484 gl_array_iterator_next (gl_list_iterator_t *iterator,
 485                         const void **eltp, gl_list_node_t *nodep)
 486 {
 487   gl_list_t list = iterator->list;
 488   if (iterator->count != list->count)
 489     {
 490       if (iterator->count != list->count + 1)
 491         /* Concurrent modifications were done on the list.  */
 492         abort ();
 493       /* The last returned element was removed.  */
 494       iterator->count--;
 495       iterator->p = (const void **) iterator->p - 1;
 496       iterator->q = (const void **) iterator->q - 1;
 497     }
 498   if (iterator->p < iterator->q)
 499     {
 500       const void **p = (const void **) iterator->p;
 501       *eltp = *p;
 502       if (nodep != NULL)
 503         *nodep = INDEX_TO_NODE (p - list->elements);
 504       iterator->p = p + 1;
 505       return true;
 506     }
 507   else
 508     return false;
 509 }
 510
 511 static void
 512 gl_array_iterator_free (gl_list_iterator_t *iterator _GL_UNUSED)
 513 {
 514 }
 515
 516 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
 517
 518 static size_t
 519 gl_array_sortedlist_indexof_from_to (gl_list_t list,
 520                                      gl_listelement_compar_fn compar,
 521                                      size_t low, size_t high,
 522                                      const void *elt)
 523 {
 524   if (!(low <= high && high <= list->count))
 525     /* Invalid arguments.  */
 526     abort ();
 527   if (low < high)
 528     {
 529       /* At each loop iteration, low < high; for indices < low the values
 530          are smaller than ELT; for indices >= high the values are greater
 531          than ELT.  So, if the element occurs in the list, it is at
 532          low <= position < high.  */
 533       do
 534         {
 535           size_t mid = low + (high - low) / 2; /* low <= mid < high */
 536           int cmp = compar (list->elements[mid], elt);
 537
 538           if (cmp < 0)
 539             low = mid + 1;
 540           else if (cmp > 0)
 541             high = mid;
 542           else /* cmp == 0 */
 543             {
 544               /* We have an element equal to ELT at index MID.  But we need
 545                  the minimal such index.  */
 546               high = mid;
 547               /* At each loop iteration, low <= high and
 548                    compar (list->elements[high], elt) == 0,
 549                  and we know that the first occurrence of the element is at
 550                  low <= position <= high.  */
 551               while (low < high)
 552                 {
 553                   size_t mid2 = low + (high - low) / 2; /* low <= mid2 < high */
 554                   int cmp2 = compar (list->elements[mid2], elt);
 555
 556                   if (cmp2 < 0)
 557                     low = mid2 + 1;
 558                   else if (cmp2 > 0)
 559                     /* The list was not sorted.  */
 560                     abort ();
 561                   else /* cmp2 == 0 */
 562                     {
 563                       if (mid2 == low)
 564                         break;
 565                       high = mid2 - 1;
 566                     }
 567                 }
 568               return low;
 569             }
 570         }
 571       while (low < high);
 572       /* Here low == high.  */
 573     }
 574   return (size_t)(-1);
 575 }
 576
 577 static size_t
 578 gl_array_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
 579                              const void *elt)
 580 {
 581   return gl_array_sortedlist_indexof_from_to (list, compar, 0, list->count,
 582                                               elt);
 583 }
 584
 585 static gl_list_node_t
 586 gl_array_sortedlist_search_from_to (gl_list_t list,
 587                                     gl_listelement_compar_fn compar,
 588                                     size_t low, size_t high,
 589                                     const void *elt)
 590 {
 591   size_t index =
 592     gl_array_sortedlist_indexof_from_to (list, compar, low, high, elt);
 593   return INDEX_TO_NODE (index);
 594 }
 595
 596 static gl_list_node_t
 597 gl_array_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
 598                             const void *elt)
 599 {
 600   size_t index =
 601     gl_array_sortedlist_indexof_from_to (list, compar, 0, list->count, elt);
 602   return INDEX_TO_NODE (index);
 603 }
 604
 605 static gl_list_node_t
 606 gl_array_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar,
 607                             const void *elt)
 608 {
 609   size_t count = list->count;
 610   size_t low = 0;
 611   size_t high = count;
 612
 613   /* At each loop iteration, low <= high; for indices < low the values are
 614      smaller than ELT; for indices >= high the values are greater than ELT.  */
 615   while (low < high)
 616     {
 617       size_t mid = low + (high - low) / 2; /* low <= mid < high */
 618       int cmp = compar (list->elements[mid], elt);
 619
 620       if (cmp < 0)
 621         low = mid + 1;
 622       else if (cmp > 0)
 623         high = mid;
 624       else /* cmp == 0 */
 625         {
 626           low = mid;
 627           break;
 628         }
 629     }
 630   return gl_array_nx_add_at (list, low, elt);
 631 }
 632
 633 static bool
 634 gl_array_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
 635                             const void *elt)
 636 {
 637   size_t index = gl_array_sortedlist_indexof (list, compar, elt);
 638   if (index == (size_t)(-1))
 639     return false;
 640   else
 641     return gl_array_remove_at (list, index);
 642 }
 643
 644
 645 const struct gl_list_implementation gl_array_list_implementation =
 646   {
 647     gl_array_nx_create_empty,
 648     gl_array_nx_create,
 649     gl_array_size,
 650     gl_array_node_value,
 651     gl_array_node_nx_set_value,
 652     gl_array_next_node,
 653     gl_array_previous_node,
 654     gl_array_get_at,
 655     gl_array_nx_set_at,
 656     gl_array_search_from_to,
 657     gl_array_indexof_from_to,
 658     gl_array_nx_add_first,
 659     gl_array_nx_add_last,
 660     gl_array_nx_add_before,
 661     gl_array_nx_add_after,
 662     gl_array_nx_add_at,
 663     gl_array_remove_node,
 664     gl_array_remove_at,
 665     gl_array_remove,
 666     gl_array_list_free,
 667     gl_array_iterator,
 668     gl_array_iterator_from_to,
 669     gl_array_iterator_next,
 670     gl_array_iterator_free,
 671     gl_array_sortedlist_search,
 672     gl_array_sortedlist_search_from_to,
 673     gl_array_sortedlist_indexof,
 674     gl_array_sortedlist_indexof_from_to,
 675     gl_array_sortedlist_nx_add,
 676     gl_array_sortedlist_remove
 677   };