lib/gl_array_list.c

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