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