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