lib/gl_array_list.c

   1 /* Sequential list data type implemented by an 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_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                        bool allow_duplicates)
  60 {
  61   struct gl_list_impl *list =
  62     (struct gl_list_impl *) xmalloc (sizeof (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.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                  bool allow_duplicates,
  80                  size_t count, const void **contents)
  81 {
  82   struct gl_list_impl *list =
  83     (struct gl_list_impl *) xmalloc (sizeof (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.allow_duplicates = allow_duplicates;
  89   if (count > 0)
  90     {
  91       list->elements =
  92         (const void **) xmalloc (count * sizeof (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   for (i = position + 1; i < count; i++)
 352     elements[i - 1] = elements[i];
 353   list->count = count - 1;
 354   return true;
 355 }
 356
 357 static bool
 358 gl_array_remove_at (gl_list_t list, size_t position)
 359 {
 360   size_t count = list->count;
 361   const void **elements;
 362   size_t i;
 363
 364   if (!(position < count))
 365     /* Invalid argument.  */
 366     abort ();
 367   elements = list->elements;
 368   for (i = position + 1; i < count; i++)
 369     elements[i - 1] = elements[i];
 370   list->count = count - 1;
 371   return true;
 372 }
 373
 374 static bool
 375 gl_array_remove (gl_list_t list, const void *elt)
 376 {
 377   size_t position = gl_array_indexof_from_to (list, 0, list->count, elt);
 378   if (position == (size_t)(-1))
 379     return false;
 380   else
 381     return gl_array_remove_at (list, position);
 382 }
 383
 384 static void
 385 gl_array_list_free (gl_list_t list)
 386 {
 387   if (list->elements != NULL)
 388     free (list->elements);
 389   free (list);
 390 }
 391
 392 /* --------------------- gl_list_iterator_t Data Type --------------------- */
 393
 394 static gl_list_iterator_t
 395 gl_array_iterator (gl_list_t list)
 396 {
 397   gl_list_iterator_t result;
 398
 399   result.vtable = list->base.vtable;
 400   result.list = list;
 401   result.count = list->count;
 402   result.p = list->elements + 0;
 403   result.q = list->elements + list->count;
 404 #ifdef lint
 405   result.i = 0;
 406   result.j = 0;
 407 #endif
 408
 409   return result;
 410 }
 411
 412 static gl_list_iterator_t
 413 gl_array_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
 414 {
 415   gl_list_iterator_t result;
 416
 417   if (!(start_index <= end_index && end_index <= list->count))
 418     /* Invalid arguments.  */
 419     abort ();
 420   result.vtable = list->base.vtable;
 421   result.list = list;
 422   result.count = list->count;
 423   result.p = list->elements + start_index;
 424   result.q = list->elements + end_index;
 425 #ifdef lint
 426   result.i = 0;
 427   result.j = 0;
 428 #endif
 429
 430   return result;
 431 }
 432
 433 static bool
 434 gl_array_iterator_next (gl_list_iterator_t *iterator,
 435                         const void **eltp, gl_list_node_t *nodep)
 436 {
 437   gl_list_t list = iterator->list;
 438   if (iterator->count != list->count)
 439     {
 440       if (iterator->count != list->count + 1)
 441         /* Concurrent modifications were done on the list.  */
 442         abort ();
 443       /* The last returned element was removed.  */
 444       iterator->count--;
 445       iterator->p--;
 446       iterator->q--;
 447     }
 448   if (iterator->p < iterator->q)
 449     {
 450       const void **p = (const void **) iterator->p;
 451       *eltp = *p;
 452       if (nodep != NULL)
 453         *nodep = INDEX_TO_NODE (p - list->elements);
 454       iterator->p = p + 1;
 455       return true;
 456     }
 457   else
 458     return false;
 459 }
 460
 461 static void
 462 gl_array_iterator_free (gl_list_iterator_t *iterator)
 463 {
 464 }
 465
 466 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
 467
 468 static size_t
 469 gl_array_sortedlist_indexof_from_to (gl_list_t list,
 470                                      gl_listelement_compar_fn compar,
 471                                      size_t low, size_t high,
 472                                      const void *elt)
 473 {
 474   if (!(low <= high && high <= list->count))
 475     /* Invalid arguments.  */
 476     abort ();
 477   if (low < high)
 478     {
 479       /* At each loop iteration, low < high; for indices < low the values
 480          are smaller than ELT; for indices >= high the values are greater
 481          than ELT.  So, if the element occurs in the list, it is at
 482          low <= position < high.  */
 483       do
 484         {
 485           size_t mid = low + (high - low) / 2; /* low <= mid < high */
 486           int cmp = compar (list->elements[mid], elt);
 487
 488           if (cmp < 0)
 489             low = mid + 1;
 490           else if (cmp > 0)
 491             high = mid;
 492           else /* cmp == 0 */
 493             {
 494               /* We have an element equal to ELT at index MID.  But we need
 495                  the minimal such index.  */
 496               high = mid;
 497               /* At each loop iteration, low <= high and
 498                    compar (list->elements[high], elt) == 0,
 499                  and we know that the first occurrence of the element is at
 500                  low <= position <= high.  */
 501               while (low < high)
 502                 {
 503                   size_t mid2 = low + (high - low) / 2; /* low <= mid2 < high */
 504                   int cmp2 = compar (list->elements[mid2], elt);
 505
 506                   if (cmp2 < 0)
 507                     low = mid2 + 1;
 508                   else if (cmp2 > 0)
 509                     /* The list was not sorted.  */
 510                     abort ();
 511                   else /* cmp2 == 0 */
 512                     {
 513                       if (mid2 == low)
 514                         break;
 515                       high = mid2 - 1;
 516                     }
 517                 }
 518               return low;
 519             }
 520         }
 521       while (low < high);
 522       /* Here low == high.  */
 523     }
 524   return (size_t)(-1);
 525 }
 526
 527 static size_t
 528 gl_array_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
 529                              const void *elt)
 530 {
 531   return gl_array_sortedlist_indexof_from_to (list, compar, 0, list->count,
 532                                               elt);
 533 }
 534
 535 static gl_list_node_t
 536 gl_array_sortedlist_search_from_to (gl_list_t list,
 537                                     gl_listelement_compar_fn compar,
 538                                     size_t low, size_t high,
 539                                     const void *elt)
 540 {
 541   size_t index =
 542     gl_array_sortedlist_indexof_from_to (list, compar, low, high, elt);
 543   return INDEX_TO_NODE (index);
 544 }
 545
 546 static gl_list_node_t
 547 gl_array_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
 548                             const void *elt)
 549 {
 550   size_t index =
 551     gl_array_sortedlist_indexof_from_to (list, compar, 0, list->count, elt);
 552   return INDEX_TO_NODE (index);
 553 }
 554
 555 static gl_list_node_t
 556 gl_array_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
 557                          const void *elt)
 558 {
 559   size_t count = list->count;
 560   size_t low = 0;
 561   size_t high = count;
 562
 563   /* At each loop iteration, low <= high; for indices < low the values are
 564      smaller than ELT; for indices >= high the values are greater than ELT.  */
 565   while (low < high)
 566     {
 567       size_t mid = low + (high - low) / 2; /* low <= mid < high */
 568       int cmp = compar (list->elements[mid], elt);
 569
 570       if (cmp < 0)
 571         low = mid + 1;
 572       else if (cmp > 0)
 573         high = mid;
 574       else /* cmp == 0 */
 575         {
 576           low = mid;
 577           break;
 578         }
 579     }
 580   return gl_array_add_at (list, low, elt);
 581 }
 582
 583 static bool
 584 gl_array_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
 585                             const void *elt)
 586 {
 587   size_t index = gl_array_sortedlist_indexof (list, compar, elt);
 588   if (index == (size_t)(-1))
 589     return false;
 590   else
 591     return gl_array_remove_at (list, index);
 592 }
 593
 594
 595 const struct gl_list_implementation gl_array_list_implementation =
 596   {
 597     gl_array_create_empty,
 598     gl_array_create,
 599     gl_array_size,
 600     gl_array_node_value,
 601     gl_array_next_node,
 602     gl_array_previous_node,
 603     gl_array_get_at,
 604     gl_array_set_at,
 605     gl_array_search_from_to,
 606     gl_array_indexof_from_to,
 607     gl_array_add_first,
 608     gl_array_add_last,
 609     gl_array_add_before,
 610     gl_array_add_after,
 611     gl_array_add_at,
 612     gl_array_remove_node,
 613     gl_array_remove_at,
 614     gl_array_remove,
 615     gl_array_list_free,
 616     gl_array_iterator,
 617     gl_array_iterator_from_to,
 618     gl_array_iterator_next,
 619     gl_array_iterator_free,
 620     gl_array_sortedlist_search,
 621     gl_array_sortedlist_search_from_to,
 622     gl_array_sortedlist_indexof,
 623     gl_array_sortedlist_indexof_from_to,
 624     gl_array_sortedlist_add,
 625     gl_array_sortedlist_remove
 626   };