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