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 (gl_list_t list, const void *elt)
 171 {
 172   size_t count = list->count;
 173   if (count > 0)
 174     {
 175       gl_listelement_equals_fn equals = list->base.equals_fn;
 176       if (equals != NULL)
 177         {
 178           size_t i;
 179
 180           for (i = 0;;)
 181             {
 182               if (equals (elt, list->elements[i]))
 183                 return i;
 184               i++;
 185               if (i == count)
 186                 break;
 187             }
 188         }
 189       else
 190         {
 191           size_t i;
 192
 193           for (i = 0;;)
 194             {
 195               if (elt == list->elements[i])
 196                 return i;
 197               i++;
 198               if (i == count)
 199                 break;
 200             }
 201         }
 202     }
 203   return (size_t)(-1);
 204 }
 205
 206 static gl_list_node_t
 207 gl_array_search (gl_list_t list, const void *elt)
 208 {
 209   size_t index = gl_array_indexof (list, elt);
 210   return INDEX_TO_NODE (index);
 211 }
 212
 213 /* Ensure that list->allocated > list->count.  */
 214 static void
 215 grow (gl_list_t list)
 216 {
 217   size_t new_allocated;
 218   size_t memory_size;
 219   const void **memory;
 220
 221   new_allocated = xtimes (list->allocated, 2);
 222   new_allocated = xsum (new_allocated, 1);
 223   memory_size = xtimes (new_allocated, sizeof (const void *));
 224   if (size_overflow_p (memory_size))
 225     /* Overflow, would lead to out of memory.  */
 226     xalloc_die ();
 227   memory = (const void **) xrealloc (list->elements, memory_size);
 228   if (memory == NULL)
 229     /* Out of memory.  */
 230     xalloc_die ();
 231   list->elements = memory;
 232   list->allocated = new_allocated;
 233 }
 234
 235 static gl_list_node_t
 236 gl_array_add_first (gl_list_t list, const void *elt)
 237 {
 238   size_t count = list->count;
 239   const void **elements;
 240   size_t i;
 241
 242   if (count == list->allocated)
 243     grow (list);
 244   elements = list->elements;
 245   for (i = count; i > 0; i--)
 246     elements[i] = elements[i - 1];
 247   elements[0] = elt;
 248   list->count = count + 1;
 249   return INDEX_TO_NODE (0);
 250 }
 251
 252 static gl_list_node_t
 253 gl_array_add_last (gl_list_t list, const void *elt)
 254 {
 255   size_t count = list->count;
 256
 257   if (count == list->allocated)
 258     grow (list);
 259   list->elements[count] = elt;
 260   list->count = count + 1;
 261   return INDEX_TO_NODE (count);
 262 }
 263
 264 static gl_list_node_t
 265 gl_array_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
 266 {
 267   size_t count = list->count;
 268   uintptr_t index = NODE_TO_INDEX (node);
 269   size_t position;
 270   const void **elements;
 271   size_t i;
 272
 273   if (!(index < count))
 274     /* Invalid argument.  */
 275     abort ();
 276   position = index;
 277   if (count == list->allocated)
 278     grow (list);
 279   elements = list->elements;
 280   for (i = count; i > position; i--)
 281     elements[i] = elements[i - 1];
 282   elements[position] = elt;
 283   list->count = count + 1;
 284   return INDEX_TO_NODE (position);
 285 }
 286
 287 static gl_list_node_t
 288 gl_array_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
 289 {
 290   size_t count = list->count;
 291   uintptr_t index = NODE_TO_INDEX (node);
 292   size_t position;
 293   const void **elements;
 294   size_t i;
 295
 296   if (!(index < count))
 297     /* Invalid argument.  */
 298     abort ();
 299   position = index + 1;
 300   if (count == list->allocated)
 301     grow (list);
 302   elements = list->elements;
 303   for (i = count; i > position; i--)
 304     elements[i] = elements[i - 1];
 305   elements[position] = elt;
 306   list->count = count + 1;
 307   return INDEX_TO_NODE (position);
 308 }
 309
 310 static gl_list_node_t
 311 gl_array_add_at (gl_list_t list, size_t position, const void *elt)
 312 {
 313   size_t count = list->count;
 314   const void **elements;
 315   size_t i;
 316
 317   if (!(position <= count))
 318     /* Invalid argument.  */
 319     abort ();
 320   if (count == list->allocated)
 321     grow (list);
 322   elements = list->elements;
 323   for (i = count; i > position; i--)
 324     elements[i] = elements[i - 1];
 325   elements[position] = elt;
 326   list->count = count + 1;
 327   return INDEX_TO_NODE (position);
 328 }
 329
 330 static bool
 331 gl_array_remove_node (gl_list_t list, gl_list_node_t node)
 332 {
 333   size_t count = list->count;
 334   uintptr_t index = NODE_TO_INDEX (node);
 335   size_t position;
 336   const void **elements;
 337   size_t i;
 338
 339   if (!(index < count))
 340     /* Invalid argument.  */
 341     abort ();
 342   position = index;
 343   elements = list->elements;
 344   for (i = position + 1; i < count; i++)
 345     elements[i - 1] = elements[i];
 346   list->count = count - 1;
 347   return true;
 348 }
 349
 350 static bool
 351 gl_array_remove_at (gl_list_t list, size_t position)
 352 {
 353   size_t count = list->count;
 354   const void **elements;
 355   size_t i;
 356
 357   if (!(position < count))
 358     /* Invalid argument.  */
 359     abort ();
 360   elements = list->elements;
 361   for (i = position + 1; i < count; i++)
 362     elements[i - 1] = elements[i];
 363   list->count = count - 1;
 364   return true;
 365 }
 366
 367 static bool
 368 gl_array_remove (gl_list_t list, const void *elt)
 369 {
 370   size_t position = gl_array_indexof (list, elt);
 371   if (position == (size_t)(-1))
 372     return false;
 373   else
 374     return gl_array_remove_at (list, position);
 375 }
 376
 377 static void
 378 gl_array_list_free (gl_list_t list)
 379 {
 380   if (list->elements != NULL)
 381     free (list->elements);
 382   free (list);
 383 }
 384
 385 /* --------------------- gl_list_iterator_t Data Type --------------------- */
 386
 387 static gl_list_iterator_t
 388 gl_array_iterator (gl_list_t list)
 389 {
 390   gl_list_iterator_t result;
 391
 392   result.vtable = list->base.vtable;
 393   result.list = list;
 394   result.count = list->count;
 395   result.p = list->elements + 0;
 396   result.q = list->elements + list->count;
 397 #ifdef lint
 398   result.i = 0;
 399   result.j = 0;
 400 #endif
 401
 402   return result;
 403 }
 404
 405 static gl_list_iterator_t
 406 gl_array_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
 407 {
 408   gl_list_iterator_t result;
 409
 410   if (!(start_index <= end_index && end_index <= list->count))
 411     /* Invalid arguments.  */
 412     abort ();
 413   result.vtable = list->base.vtable;
 414   result.list = list;
 415   result.count = list->count;
 416   result.p = list->elements + start_index;
 417   result.q = list->elements + end_index;
 418 #ifdef lint
 419   result.i = 0;
 420   result.j = 0;
 421 #endif
 422
 423   return result;
 424 }
 425
 426 static bool
 427 gl_array_iterator_next (gl_list_iterator_t *iterator,
 428                         const void **eltp, gl_list_node_t *nodep)
 429 {
 430   gl_list_t list = iterator->list;
 431   if (iterator->count != list->count)
 432     {
 433       if (iterator->count != list->count + 1)
 434         /* Concurrent modifications were done on the list.  */
 435         abort ();
 436       /* The last returned element was removed.  */
 437       iterator->count--;
 438       iterator->p--;
 439       iterator->q--;
 440     }
 441   if (iterator->p < iterator->q)
 442     {
 443       const void **p = (const void **) iterator->p;
 444       *eltp = *p;
 445       if (nodep != NULL)
 446         *nodep = INDEX_TO_NODE (p - list->elements);
 447       iterator->p = p + 1;
 448       return true;
 449     }
 450   else
 451     return false;
 452 }
 453
 454 static void
 455 gl_array_iterator_free (gl_list_iterator_t *iterator)
 456 {
 457 }
 458
 459 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
 460
 461 static size_t
 462 gl_array_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
 463                              const void *elt)
 464 {
 465   size_t count = list->count;
 466
 467   if (count > 0)
 468     {
 469       size_t low = 0;
 470       size_t high = count;
 471
 472       /* At each loop iteration, low < high; for indices < low the values
 473          are smaller than ELT; for indices >= high the values are greater
 474          than ELT.  So, if the element occurs in the list, is at
 475          low <= position < high.  */
 476       do
 477         {
 478           size_t mid = low + (high - low) / 2; /* low <= mid < high */
 479           int cmp = compar (list->elements[mid], elt);
 480
 481           if (cmp < 0)
 482             low = mid + 1;
 483           else if (cmp > 0)
 484             high = mid;
 485           else /* cmp == 0 */
 486             {
 487               /* We have an element equal to ELT at index MID.  But we need
 488                  the minimal such index.  */
 489               high = mid;
 490               /* At each loop iteration, low <= high and
 491                    compar (list->elements[high], elt) == 0,
 492                  and we know that the first occurrence of the element is at
 493                  low <= position <= high.  */
 494               while (low < high)
 495                 {
 496                   size_t mid2 = low + (high - low) / 2; /* low <= mid < high */
 497                   int cmp2 = compar (list->elements[mid2], elt);
 498
 499                   if (cmp2 < 0)
 500                     low = mid2 + 1;
 501                   else if (cmp2 > 0)
 502                     /* The list was not sorted.  */
 503                     abort ();
 504                   else /* cmp2 == 0 */
 505                     {
 506                       if (mid2 == low)
 507                         break;
 508                       high = mid2 - 1;
 509                     }
 510                 }
 511               return low;
 512             }
 513         }
 514       while (low < high);
 515       /* Here low == high.  */
 516     }
 517   return (size_t)(-1);
 518 }
 519
 520 static gl_list_node_t
 521 gl_array_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
 522                             const void *elt)
 523 {
 524   size_t index = gl_array_sortedlist_indexof (list, compar, elt);
 525   return INDEX_TO_NODE (index);
 526 }
 527
 528 static gl_list_node_t
 529 gl_array_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
 530                          const void *elt)
 531 {
 532   size_t count = list->count;
 533   size_t low = 0;
 534   size_t high = count;
 535
 536   /* At each loop iteration, low <= high; for indices < low the values are
 537      smaller than ELT; for indices >= high the values are greater than ELT.  */
 538   while (low < high)
 539     {
 540       size_t mid = low + (high - low) / 2; /* low <= mid < high */
 541       int cmp = compar (list->elements[mid], elt);
 542
 543       if (cmp < 0)
 544         low = mid + 1;
 545       else if (cmp > 0)
 546         high = mid;
 547       else /* cmp == 0 */
 548         {
 549           low = mid;
 550           break;
 551         }
 552     }
 553   return gl_array_add_at (list, low, elt);
 554 }
 555
 556 static bool
 557 gl_array_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
 558                             const void *elt)
 559 {
 560   size_t index = gl_array_sortedlist_indexof (list, compar, elt);
 561   if (index == (size_t)(-1))
 562     return false;
 563   else
 564     return gl_array_remove_at (list, index);
 565 }
 566
 567
 568 const struct gl_list_implementation gl_array_list_implementation =
 569   {
 570     gl_array_create_empty,
 571     gl_array_create,
 572     gl_array_size,
 573     gl_array_node_value,
 574     gl_array_next_node,
 575     gl_array_previous_node,
 576     gl_array_get_at,
 577     gl_array_set_at,
 578     gl_array_search,
 579     gl_array_indexof,
 580     gl_array_add_first,
 581     gl_array_add_last,
 582     gl_array_add_before,
 583     gl_array_add_after,
 584     gl_array_add_at,
 585     gl_array_remove_node,
 586     gl_array_remove_at,
 587     gl_array_remove,
 588     gl_array_list_free,
 589     gl_array_iterator,
 590     gl_array_iterator_from_to,
 591     gl_array_iterator_next,
 592     gl_array_iterator_free,
 593     gl_array_sortedlist_search,
 594     gl_array_sortedlist_indexof,
 595     gl_array_sortedlist_add,
 596     gl_array_sortedlist_remove
 597   };