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