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