lib/gl_carray_list.c

   1 /* Sequential list data type implemented by a circular array.
   2    Copyright (C) 2006 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_carray_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 elements
  44      OFFSET, (OFFSET + 1) % ALLOCATED, ..., (OFFSET + COUNT - 1) % ALLOCATED
  45      are used.  0 <= COUNT <= ALLOCATED.  Either OFFSET = ALLOCATED = 0 or
  46      0 <= OFFSET < ALLOCATED.  */
  47   const void **elements;
  48   size_t offset;
  49   size_t count;
  50   size_t allocated;
  51 };
  52
  53 /* struct gl_list_node_impl doesn't exist here.  The pointers are actually
  54    indices + 1.  */
  55 #define INDEX_TO_NODE(index) (gl_list_node_t)(uintptr_t)(size_t)((index) + 1)
  56 #define NODE_TO_INDEX(node) ((uintptr_t)(node) - 1)
  57
  58 static gl_list_t
  59 gl_carray_create_empty (gl_list_implementation_t implementation,
  60                        gl_listelement_equals_fn equals_fn,
  61                        gl_listelement_hashcode_fn hashcode_fn,
  62                        bool allow_duplicates)
  63 {
  64   struct gl_list_impl *list =
  65     (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl));
  66
  67   list->base.vtable = implementation;
  68   list->base.equals_fn = equals_fn;
  69   list->base.hashcode_fn = hashcode_fn;
  70   list->base.allow_duplicates = allow_duplicates;
  71   list->elements = NULL;
  72   list->offset = 0;
  73   list->count = 0;
  74   list->allocated = 0;
  75
  76   return list;
  77 }
  78
  79 static gl_list_t
  80 gl_carray_create (gl_list_implementation_t implementation,
  81                  gl_listelement_equals_fn equals_fn,
  82                  gl_listelement_hashcode_fn hashcode_fn,
  83                  bool allow_duplicates,
  84                  size_t count, const void **contents)
  85 {
  86   struct gl_list_impl *list =
  87     (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl));
  88
  89   list->base.vtable = implementation;
  90   list->base.equals_fn = equals_fn;
  91   list->base.hashcode_fn = hashcode_fn;
  92   list->base.allow_duplicates = allow_duplicates;
  93   if (count > 0)
  94     {
  95       list->elements =
  96         (const void **) xmalloc (count * sizeof (const void *));
  97       memcpy (list->elements, contents, count * sizeof (const void *));
  98     }
  99   else
 100     list->elements = NULL;
 101   list->offset = 0;
 102   list->count = count;
 103   list->allocated = count;
 104
 105   return list;
 106 }
 107
 108 static size_t
 109 gl_carray_size (gl_list_t list)
 110 {
 111   return list->count;
 112 }
 113
 114 static const void *
 115 gl_carray_node_value (gl_list_t list, gl_list_node_t node)
 116 {
 117   uintptr_t index = NODE_TO_INDEX (node);
 118   size_t i;
 119
 120   if (!(index < list->count))
 121     /* Invalid argument.  */
 122     abort ();
 123   i = list->offset + index;
 124   if (i >= list->allocated)
 125     i -= list->allocated;
 126   return list->elements[i];
 127 }
 128
 129 static gl_list_node_t
 130 gl_carray_next_node (gl_list_t list, gl_list_node_t node)
 131 {
 132   uintptr_t index = NODE_TO_INDEX (node);
 133   if (!(index < list->count))
 134     /* Invalid argument.  */
 135     abort ();
 136   index++;
 137   if (index < list->count)
 138     return INDEX_TO_NODE (index);
 139   else
 140     return NULL;
 141 }
 142
 143 static gl_list_node_t
 144 gl_carray_previous_node (gl_list_t list, gl_list_node_t node)
 145 {
 146   uintptr_t index = NODE_TO_INDEX (node);
 147   if (!(index < list->count))
 148     /* Invalid argument.  */
 149     abort ();
 150   if (index > 0)
 151     return INDEX_TO_NODE (index - 1);
 152   else
 153     return NULL;
 154 }
 155
 156 static const void *
 157 gl_carray_get_at (gl_list_t list, size_t position)
 158 {
 159   size_t count = list->count;
 160   size_t i;
 161
 162   if (!(position < count))
 163     /* Invalid argument.  */
 164     abort ();
 165   i = list->offset + position;
 166   if (i >= list->allocated)
 167     i -= list->allocated;
 168   return list->elements[i];
 169 }
 170
 171 static gl_list_node_t
 172 gl_carray_set_at (gl_list_t list, size_t position, const void *elt)
 173 {
 174   size_t count = list->count;
 175   size_t i;
 176
 177   if (!(position < count))
 178     /* Invalid argument.  */
 179     abort ();
 180   i = list->offset + position;
 181   if (i >= list->allocated)
 182     i -= list->allocated;
 183   list->elements[i] = elt;
 184   return INDEX_TO_NODE (position);
 185 }
 186
 187 static size_t
 188 gl_carray_indexof (gl_list_t list, const void *elt)
 189 {
 190   size_t count = list->count;
 191   if (count > 0)
 192     {
 193       gl_listelement_equals_fn equals = list->base.equals_fn;
 194       size_t allocated = list->allocated;
 195       size_t i_end;
 196
 197       i_end = list->offset + list->count;
 198       if (i_end >= allocated)
 199         i_end -= allocated;
 200
 201       if (equals != NULL)
 202         {
 203           size_t i;
 204
 205           for (i = list->offset;;)
 206             {
 207               if (equals (elt, list->elements[i]))
 208                 return (i >= list->offset ? i : i + allocated) - list->offset;
 209               i++;
 210               if (i == allocated)
 211                 i = 0;
 212               if (i == i_end)
 213                 break;
 214             }
 215         }
 216       else
 217         {
 218           size_t i;
 219
 220           for (i = list->offset;;)
 221             {
 222               if (elt == list->elements[i])
 223                 return (i >= list->offset ? i : i + allocated) - list->offset;
 224               i++;
 225               if (i == allocated)
 226                 i = 0;
 227               if (i == i_end)
 228                 break;
 229             }
 230         }
 231     }
 232   return (size_t)(-1);
 233 }
 234
 235 static gl_list_node_t
 236 gl_carray_search (gl_list_t list, const void *elt)
 237 {
 238   size_t index = gl_carray_indexof (list, elt);
 239   return INDEX_TO_NODE (index);
 240 }
 241
 242 /* Ensure that list->allocated > list->count.  */
 243 static void
 244 grow (gl_list_t list)
 245 {
 246   size_t new_allocated;
 247   size_t memory_size;
 248   const void **memory;
 249
 250   new_allocated = xtimes (list->allocated, 2);
 251   new_allocated = xsum (new_allocated, 1);
 252   memory_size = xtimes (new_allocated, sizeof (const void *));
 253   if (size_overflow_p (memory_size))
 254     /* Overflow, would lead to out of memory.  */
 255     xalloc_die ();
 256   if (list->offset > 0 && list->count > 0)
 257     {
 258       memory = (const void **) xmalloc (memory_size);
 259       if (memory == NULL)
 260         /* Out of memory.  */
 261         xalloc_die ();
 262       if (list->offset + list->count > list->allocated)
 263         {
 264           memcpy (memory, &list->elements[list->offset],
 265                   (list->allocated - list->offset) * sizeof (const void *));
 266           memcpy (memory + (list->allocated - list->offset), list->elements,
 267                   (list->offset + list->count - list->allocated)
 268                   * sizeof (const void *));
 269
 270         }
 271       else
 272         memcpy (memory, &list->elements[list->offset],
 273                 list->count * sizeof (const void *));
 274       if (list->elements != NULL)
 275         free (list->elements);
 276     }
 277   else
 278     {
 279       memory = (const void **) xrealloc (list->elements, memory_size);
 280       if (memory == NULL)
 281         /* Out of memory.  */
 282         xalloc_die ();
 283     }
 284   list->elements = memory;
 285   list->offset = 0;
 286   list->allocated = new_allocated;
 287 }
 288
 289 static gl_list_node_t
 290 gl_carray_add_first (gl_list_t list, const void *elt)
 291 {
 292   size_t count = list->count;
 293
 294   if (count == list->allocated)
 295     grow (list);
 296   list->offset = (list->offset == 0 ? list->allocated : list->offset) - 1;
 297   list->elements[list->offset] = elt;
 298   list->count = count + 1;
 299   return INDEX_TO_NODE (0);
 300 }
 301
 302 static gl_list_node_t
 303 gl_carray_add_last (gl_list_t list, const void *elt)
 304 {
 305   size_t count = list->count;
 306   size_t i;
 307
 308   if (count == list->allocated)
 309     grow (list);
 310   i = list->offset + count;
 311   if (i >= list->allocated)
 312     i -= list->allocated;
 313   list->elements[i] = elt;
 314   list->count = count + 1;
 315   return INDEX_TO_NODE (count);
 316 }
 317
 318 static gl_list_node_t
 319 gl_carray_add_at (gl_list_t list, size_t position, const void *elt)
 320 {
 321   size_t count = list->count;
 322   const void **elements;
 323
 324   if (!(position <= count))
 325     /* Invalid argument.  */
 326     abort ();
 327   if (count == list->allocated)
 328     grow (list);
 329   elements = list->elements;
 330   if (position <= (count / 2))
 331     {
 332       /* Shift at most count/2 elements to the left.  */
 333       size_t i2, i;
 334
 335       list->offset = (list->offset == 0 ? list->allocated : list->offset) - 1;
 336
 337       i2 = list->offset + position;
 338       if (i2 >= list->allocated)
 339         {
 340           /* Here we must have list->offset > 0, hence list->allocated > 0.  */
 341           size_t i1 = list->allocated - 1;
 342           i2 -= list->allocated;
 343           for (i = list->offset; i < i1; i++)
 344             elements[i] = elements[i + 1];
 345           elements[i1] = elements[0];
 346           for (i = 0; i < i2; i++)
 347             elements[i] = elements[i + 1];
 348         }
 349       else
 350         {
 351           for (i = list->offset; i < i2; i++)
 352             elements[i] = elements[i + 1];
 353         }
 354       elements[i2] = elt;
 355     }
 356   else
 357     {
 358       /* Shift at most (count+1)/2 elements to the right.  */
 359       size_t i1, i3, i;
 360
 361       i1 = list->offset + position;
 362       i3 = list->offset + count;
 363       if (i1 >= list->allocated)
 364         {
 365           i1 -= list->allocated;
 366           i3 -= list->allocated;
 367           for (i = i3; i > i1; i--)
 368             elements[i] = elements[i - 1];
 369         }
 370       else if (i3 >= list->allocated)
 371         {
 372           /* Here we must have list->offset > 0, hence list->allocated > 0.  */
 373           size_t i2 = list->allocated - 1;
 374           i3 -= list->allocated;
 375           for (i = i3; i > 0; i--)
 376             elements[i] = elements[i - 1];
 377           elements[0] = elements[i2];
 378           for (i = i2; i > i1; i--)
 379             elements[i] = elements[i - 1];
 380         }
 381       else
 382         {
 383           for (i = i3; i > i1; i--)
 384             elements[i] = elements[i - 1];
 385         }
 386       elements[i1] = elt;
 387     }
 388   list->count = count + 1;
 389   return INDEX_TO_NODE (position);
 390 }
 391
 392 static gl_list_node_t
 393 gl_carray_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
 394 {
 395   size_t count = list->count;
 396   uintptr_t index = NODE_TO_INDEX (node);
 397
 398   if (!(index < count))
 399     /* Invalid argument.  */
 400     abort ();
 401   return gl_carray_add_at (list, index, elt);
 402 }
 403
 404 static gl_list_node_t
 405 gl_carray_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
 406 {
 407   size_t count = list->count;
 408   uintptr_t index = NODE_TO_INDEX (node);
 409
 410   if (!(index < count))
 411     /* Invalid argument.  */
 412     abort ();
 413   return gl_carray_add_at (list, index + 1, elt);
 414 }
 415
 416 static bool
 417 gl_carray_remove_at (gl_list_t list, size_t position)
 418 {
 419   size_t count = list->count;
 420   const void **elements;
 421
 422   if (!(position < count))
 423     /* Invalid argument.  */
 424     abort ();
 425   /* Here we know count > 0.  */
 426   elements = list->elements;
 427   if (position <= ((count - 1) / 2))
 428     {
 429       /* Shift at most (count-1)/2 elements to the right.  */
 430       size_t i0, i2, i;
 431
 432       i0 = list->offset;
 433       i2 = list->offset + position;
 434       if (i2 >= list->allocated)
 435         {
 436           /* Here we must have list->offset > 0, hence list->allocated > 0.  */
 437           size_t i1 = list->allocated - 1;
 438           i2 -= list->allocated;
 439           for (i = i2; i > 0; i--)
 440             elements[i] = elements[i - 1];
 441           elements[0] = elements[i1];
 442           for (i = i1; i > i0; i--)
 443             elements[i] = elements[i - 1];
 444         }
 445       else
 446         {
 447           for (i = i2; i > i0; i--)
 448             elements[i] = elements[i - 1];
 449         }
 450
 451       i0++;
 452       list->offset = (i0 == list->allocated ? 0 : i0);
 453     }
 454   else
 455     {
 456       /* Shift at most count/2 elements to the left.  */
 457       size_t i1, i3, i;
 458
 459       i1 = list->offset + position;
 460       i3 = list->offset + count - 1;
 461       if (i1 >= list->allocated)
 462         {
 463           i1 -= list->allocated;
 464           i3 -= list->allocated;
 465           for (i = i1; i < i3; i++)
 466             elements[i] = elements[i + 1];
 467         }
 468       else if (i3 >= list->allocated)
 469         {
 470           /* Here we must have list->offset > 0, hence list->allocated > 0.  */
 471           size_t i2 = list->allocated - 1;
 472           i3 -= list->allocated;
 473           for (i = i1; i < i2; i++)
 474             elements[i] = elements[i + 1];
 475           elements[i2] = elements[0];
 476           for (i = 0; i < i3; i++)
 477             elements[i] = elements[i + 1];
 478         }
 479       else
 480         {
 481           for (i = i1; i < i3; i++)
 482             elements[i] = elements[i + 1];
 483         }
 484     }
 485   list->count = count - 1;
 486   return true;
 487 }
 488
 489 static bool
 490 gl_carray_remove_node (gl_list_t list, gl_list_node_t node)
 491 {
 492   size_t count = list->count;
 493   uintptr_t index = NODE_TO_INDEX (node);
 494
 495   if (!(index < count))
 496     /* Invalid argument.  */
 497     abort ();
 498   return gl_carray_remove_at (list, index);
 499 }
 500
 501 static bool
 502 gl_carray_remove (gl_list_t list, const void *elt)
 503 {
 504   size_t position = gl_carray_indexof (list, elt);
 505   if (position == (size_t)(-1))
 506     return false;
 507   else
 508     return gl_carray_remove_at (list, position);
 509 }
 510
 511 static void
 512 gl_carray_list_free (gl_list_t list)
 513 {
 514   if (list->elements != NULL)
 515     free (list->elements);
 516   free (list);
 517 }
 518
 519 /* --------------------- gl_list_iterator_t Data Type --------------------- */
 520
 521 static gl_list_iterator_t
 522 gl_carray_iterator (gl_list_t list)
 523 {
 524   gl_list_iterator_t result;
 525
 526   result.vtable = list->base.vtable;
 527   result.list = list;
 528   result.count = list->count;
 529   result.i = 0;
 530   result.j = list->count;
 531
 532   return result;
 533 }
 534
 535 static gl_list_iterator_t
 536 gl_carray_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
 537 {
 538   gl_list_iterator_t result;
 539
 540   if (!(start_index <= end_index && end_index <= list->count))
 541     /* Invalid arguments.  */
 542     abort ();
 543   result.vtable = list->base.vtable;
 544   result.list = list;
 545   result.count = list->count;
 546   result.i = start_index;
 547   result.j = end_index;
 548
 549   return result;
 550 }
 551
 552 static bool
 553 gl_carray_iterator_next (gl_list_iterator_t *iterator,
 554                          const void **eltp, gl_list_node_t *nodep)
 555 {
 556   gl_list_t list = iterator->list;
 557   if (iterator->count != list->count)
 558     {
 559       if (iterator->count != list->count + 1)
 560         /* Concurrent modifications were done on the list.  */
 561         abort ();
 562       /* The last returned element was removed.  */
 563       iterator->count--;
 564       iterator->i--;
 565       iterator->j--;
 566     }
 567   if (iterator->i < iterator->j)
 568     {
 569       size_t i = list->offset + iterator->i;
 570       if (i >= list->allocated)
 571         i -= list->allocated;
 572       *eltp = list->elements[i];
 573       if (nodep != NULL)
 574         *nodep = INDEX_TO_NODE (iterator->i);
 575       iterator->i++;
 576       return true;
 577     }
 578   else
 579     return false;
 580 }
 581
 582 static void
 583 gl_carray_iterator_free (gl_list_iterator_t *iterator)
 584 {
 585 }
 586
 587 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
 588
 589 static size_t
 590 gl_carray_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
 591                               const void *elt)
 592 {
 593   size_t count = list->count;
 594
 595   if (count > 0)
 596     {
 597       size_t low = 0;
 598       size_t high = count;
 599
 600       /* At each loop iteration, low < high; for indices < low the values
 601          are smaller than ELT; for indices >= high the values are greater
 602          than ELT.  So, if the element occurs in the list, is at
 603          low <= position < high.  */
 604       do
 605         {
 606           size_t mid = low + (high - low) / 2; /* low <= mid < high */
 607           size_t i_mid;
 608           int cmp;
 609
 610           i_mid = list->offset + mid;
 611           if (i_mid >= list->allocated)
 612             i_mid -= list->allocated;
 613
 614           cmp = compar (list->elements[i_mid], elt);
 615
 616           if (cmp < 0)
 617             low = mid + 1;
 618           else if (cmp > 0)
 619             high = mid;
 620           else /* cmp == 0 */
 621             {
 622               /* We have an element equal to ELT at index MID.  But we need
 623                  the minimal such index.  */
 624               high = mid;
 625               /* At each loop iteration, low <= high and
 626                    compar (list->elements[i_high], elt) == 0,
 627                  and we know that the first occurrence of the element is at
 628                  low <= position <= high.  */
 629               while (low < high)
 630                 {
 631                   size_t mid2 = low + (high - low) / 2; /* low <= mid < high */
 632                   size_t i_mid2;
 633                   int cmp2;
 634
 635                   i_mid2 = list->offset + mid2;
 636                   if (i_mid2 >= list->allocated)
 637                     i_mid2 -= list->allocated;
 638
 639                   cmp2 = compar (list->elements[i_mid2], elt);
 640
 641                   if (cmp2 < 0)
 642                     low = mid2 + 1;
 643                   else if (cmp2 > 0)
 644                     /* The list was not sorted.  */
 645                     abort ();
 646                   else /* cmp2 == 0 */
 647                     {
 648                       if (mid2 == low)
 649                         break;
 650                       high = mid2 - 1;
 651                     }
 652                 }
 653               return low;
 654             }
 655         }
 656       while (low < high);
 657       /* Here low == high.  */
 658     }
 659   return (size_t)(-1);
 660 }
 661
 662 static gl_list_node_t
 663 gl_carray_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
 664                              const void *elt)
 665 {
 666   size_t index = gl_carray_sortedlist_indexof (list, compar, elt);
 667   return INDEX_TO_NODE (index);
 668 }
 669
 670 static gl_list_node_t
 671 gl_carray_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
 672                           const void *elt)
 673 {
 674   size_t count = list->count;
 675   size_t low = 0;
 676   size_t high = count;
 677
 678   /* At each loop iteration, low <= high; for indices < low the values are
 679      smaller than ELT; for indices >= high the values are greater than ELT.  */
 680   while (low < high)
 681     {
 682       size_t mid = low + (high - low) / 2; /* low <= mid < high */
 683       size_t i_mid;
 684       int cmp;
 685
 686       i_mid = list->offset + mid;
 687       if (i_mid >= list->allocated)
 688         i_mid -= list->allocated;
 689
 690       cmp = compar (list->elements[i_mid], elt);
 691
 692       if (cmp < 0)
 693         low = mid + 1;
 694       else if (cmp > 0)
 695         high = mid;
 696       else /* cmp == 0 */
 697         {
 698           low = mid;
 699           break;
 700         }
 701     }
 702   return gl_carray_add_at (list, low, elt);
 703 }
 704
 705 static bool
 706 gl_carray_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
 707                              const void *elt)
 708 {
 709   size_t index = gl_carray_sortedlist_indexof (list, compar, elt);
 710   if (index == (size_t)(-1))
 711     return false;
 712   else
 713     return gl_carray_remove_at (list, index);
 714 }
 715
 716
 717 const struct gl_list_implementation gl_carray_list_implementation =
 718   {
 719     gl_carray_create_empty,
 720     gl_carray_create,
 721     gl_carray_size,
 722     gl_carray_node_value,
 723     gl_carray_next_node,
 724     gl_carray_previous_node,
 725     gl_carray_get_at,
 726     gl_carray_set_at,
 727     gl_carray_search,
 728     gl_carray_indexof,
 729     gl_carray_add_first,
 730     gl_carray_add_last,
 731     gl_carray_add_before,
 732     gl_carray_add_after,
 733     gl_carray_add_at,
 734     gl_carray_remove_node,
 735     gl_carray_remove_at,
 736     gl_carray_remove,
 737     gl_carray_list_free,
 738     gl_carray_iterator,
 739     gl_carray_iterator_from_to,
 740     gl_carray_iterator_next,
 741     gl_carray_iterator_free,
 742     gl_carray_sortedlist_search,
 743     gl_carray_sortedlist_indexof,
 744     gl_carray_sortedlist_add,
 745     gl_carray_sortedlist_remove
 746   };