lib/gl_array_list.c

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