1 /* Abstract sequential list data type.
2 Copyright (C) 2006-2008 Free Software Foundation, Inc.
3 Written by Bruno Haible <bruno@clisp.org>, 2006.
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 3 of the License, or
8 (at your option) any later version.
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.
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>. */
29 /* gl_list is an abstract list data type. It can contain any number of
30 objects ('void *' or 'const void *' pointers) in any given order.
31 Duplicates are allowed, but can optionally be forbidden.
33 There are several implementations of this list datatype, optimized for
34 different operations or for memory. You can start using the simplest list
35 implementation, GL_ARRAY_LIST, and switch to a different implementation
36 later, when you realize which operations are performed the most frequently.
37 The API of the different implementations is exactly the same; when
38 switching to a different implementation, you only have to change the
41 The implementations are:
42 GL_ARRAY_LIST a growable array
43 GL_CARRAY_LIST a growable circular array
44 GL_LINKED_LIST a linked list
45 GL_AVLTREE_LIST a binary tree (AVL tree)
46 GL_RBTREE_LIST a binary tree (red-black tree)
47 GL_LINKEDHASH_LIST a hash table with a linked list
48 GL_AVLTREEHASH_LIST a hash table with a binary tree (AVL tree)
49 GL_RBTREEHASH_LIST a hash table with a binary tree (red-black tree)
51 The memory consumption is asymptotically the same: O(1) for every object
52 in the list. When looking more closely at the average memory consumed
53 for an object, GL_ARRAY_LIST is the most compact representation, and
54 GL_LINKEDHASH_LIST and GL_TREEHASH_LIST need more memory.
56 The guaranteed average performance of the operations is, for a list of
59 Operation ARRAY LINKED TREE LINKEDHASH TREEHASH
60 CARRAY with|without with|without
63 gl_list_size O(1) O(1) O(1) O(1) O(1)
64 gl_list_node_value O(1) O(1) O(1) O(1) O(1)
65 gl_list_node_set_value O(1) O(1) O(1) O(1) O((log n)²)/O(1)
66 gl_list_next_node O(1) O(1) O(log n) O(1) O(log n)
67 gl_list_previous_node O(1) O(1) O(log n) O(1) O(log n)
68 gl_list_get_at O(1) O(n) O(log n) O(n) O(log n)
69 gl_list_set_at O(1) O(n) O(log n) O(n) O((log n)²)/O(log n)
70 gl_list_search O(n) O(n) O(n) O(n)/O(1) O(log n)/O(1)
71 gl_list_search_from O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n)
72 gl_list_search_from_to O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n)
73 gl_list_indexof O(n) O(n) O(n) O(n) O(log n)
74 gl_list_indexof_from O(n) O(n) O(n) O(n) O((log n)²)/O(log n)
75 gl_list_indexof_from_to O(n) O(n) O(n) O(n) O((log n)²)/O(log n)
76 gl_list_add_first O(n)/O(1) O(1) O(log n) O(1) O((log n)²)/O(log n)
77 gl_list_add_last O(1) O(1) O(log n) O(1) O((log n)²)/O(log n)
78 gl_list_add_before O(n) O(1) O(log n) O(1) O((log n)²)/O(log n)
79 gl_list_add_after O(n) O(1) O(log n) O(1) O((log n)²)/O(log n)
80 gl_list_add_at O(n) O(n) O(log n) O(n) O((log n)²)/O(log n)
81 gl_list_remove_node O(n) O(1) O(log n) O(n)/O(1) O((log n)²)/O(log n)
82 gl_list_remove_at O(n) O(n) O(log n) O(n) O((log n)²)/O(log n)
83 gl_list_remove O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n)
84 gl_list_iterator O(1) O(1) O(log n) O(1) O(log n)
85 gl_list_iterator_from_to O(1) O(n) O(log n) O(n) O(log n)
86 gl_list_iterator_next O(1) O(1) O(log n) O(1) O(log n)
87 gl_sortedlist_search O(log n) O(n) O(log n) O(n) O(log n)
88 gl_sortedlist_search_from O(log n) O(n) O(log n) O(n) O(log n)
89 gl_sortedlist_indexof O(log n) O(n) O(log n) O(n) O(log n)
90 gl_sortedlist_indexof_fro O(log n) O(n) O(log n) O(n) O(log n)
91 gl_sortedlist_add O(n) O(n) O(log n) O(n) O((log n)²)/O(log n)
92 gl_sortedlist_remove O(n) O(n) O(log n) O(n) O((log n)²)/O(log n)
95 /* -------------------------- gl_list_t Data Type -------------------------- */
97 /* Type of function used to compare two elements.
98 NULL denotes pointer comparison. */
99 typedef bool (*gl_listelement_equals_fn) (const void *elt1, const void *elt2);
101 /* Type of function used to compute a hash code.
102 NULL denotes a function that depends only on the pointer itself. */
103 typedef size_t (*gl_listelement_hashcode_fn) (const void *elt);
105 /* Type of function used to dispose an element once it's removed from a list.
106 NULL denotes a no-op. */
107 typedef void (*gl_listelement_dispose_fn) (const void *elt);
110 /* Type representing an entire list. */
111 typedef struct gl_list_impl * gl_list_t;
113 struct gl_list_node_impl;
114 /* Type representing the position of an element in the list, in a way that
115 is more adapted to the list implementation than a plain index.
116 Note: It is invalidated by insertions and removals! */
117 typedef struct gl_list_node_impl * gl_list_node_t;
119 struct gl_list_implementation;
120 /* Type representing a list datatype implementation. */
121 typedef const struct gl_list_implementation * gl_list_implementation_t;
123 /* Create an empty list.
124 IMPLEMENTATION is one of GL_ARRAY_LIST, GL_CARRAY_LIST, GL_LINKED_LIST,
125 GL_AVLTREE_LIST, GL_RBTREE_LIST, GL_LINKEDHASH_LIST, GL_AVLTREEHASH_LIST,
127 EQUALS_FN is an element comparison function or NULL.
128 HASHCODE_FN is an element hash code function or NULL.
129 DISPOSE_FN is an element disposal function or NULL.
130 ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in
131 the list. The implementation may verify this at runtime. */
132 extern gl_list_t gl_list_create_empty (gl_list_implementation_t implementation,
133 gl_listelement_equals_fn equals_fn,
134 gl_listelement_hashcode_fn hashcode_fn,
135 gl_listelement_dispose_fn dispose_fn,
136 bool allow_duplicates);
138 /* Create a list with given contents.
139 IMPLEMENTATION is one of GL_ARRAY_LIST, GL_CARRAY_LIST, GL_LINKED_LIST,
140 GL_AVLTREE_LIST, GL_RBTREE_LIST, GL_LINKEDHASH_LIST, GL_AVLTREEHASH_LIST,
142 EQUALS_FN is an element comparison function or NULL.
143 HASHCODE_FN is an element hash code function or NULL.
144 DISPOSE_FN is an element disposal function or NULL.
145 ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in
146 the list. The implementation may verify this at runtime.
147 COUNT is the number of initial elements.
148 CONTENTS[0..COUNT-1] is the initial contents. */
149 extern gl_list_t gl_list_create (gl_list_implementation_t implementation,
150 gl_listelement_equals_fn equals_fn,
151 gl_listelement_hashcode_fn hashcode_fn,
152 gl_listelement_dispose_fn dispose_fn,
153 bool allow_duplicates,
154 size_t count, const void **contents);
156 /* Return the current number of elements in a list. */
157 extern size_t gl_list_size (gl_list_t list);
159 /* Return the element value represented by a list node. */
160 extern const void * gl_list_node_value (gl_list_t list, gl_list_node_t node);
162 /* Replace the element value represented by a list node. */
163 extern void gl_list_node_set_value (gl_list_t list, gl_list_node_t node,
166 /* Return the node immediately after the given node in the list, or NULL
167 if the given node is the last (rightmost) one in the list. */
168 extern gl_list_node_t gl_list_next_node (gl_list_t list, gl_list_node_t node);
170 /* Return the node immediately before the given node in the list, or NULL
171 if the given node is the first (leftmost) one in the list. */
172 extern gl_list_node_t gl_list_previous_node (gl_list_t list, gl_list_node_t node);
174 /* Return the element at a given position in the list.
175 POSITION must be >= 0 and < gl_list_size (list). */
176 extern const void * gl_list_get_at (gl_list_t list, size_t position);
178 /* Replace the element at a given position in the list.
179 POSITION must be >= 0 and < gl_list_size (list).
181 extern gl_list_node_t gl_list_set_at (gl_list_t list, size_t position,
184 /* Search whether an element is already in the list.
185 Return its node if found, or NULL if not present in the list. */
186 extern gl_list_node_t gl_list_search (gl_list_t list, const void *elt);
188 /* Search whether an element is already in the list,
189 at a position >= START_INDEX.
190 Return its node if found, or NULL if not present in the list. */
191 extern gl_list_node_t gl_list_search_from (gl_list_t list, size_t start_index,
194 /* Search whether an element is already in the list,
195 at a position >= START_INDEX and < END_INDEX.
196 Return its node if found, or NULL if not present in the list. */
197 extern gl_list_node_t gl_list_search_from_to (gl_list_t list,
202 /* Search whether an element is already in the list.
203 Return its position if found, or (size_t)(-1) if not present in the list. */
204 extern size_t gl_list_indexof (gl_list_t list, const void *elt);
206 /* Search whether an element is already in the list,
207 at a position >= START_INDEX.
208 Return its position if found, or (size_t)(-1) if not present in the list. */
209 extern size_t gl_list_indexof_from (gl_list_t list, size_t start_index,
212 /* Search whether an element is already in the list,
213 at a position >= START_INDEX and < END_INDEX.
214 Return its position if found, or (size_t)(-1) if not present in the list. */
215 extern size_t gl_list_indexof_from_to (gl_list_t list,
216 size_t start_index, size_t end_index,
219 /* Add an element as the first element of the list.
221 extern gl_list_node_t gl_list_add_first (gl_list_t list, const void *elt);
223 /* Add an element as the last element of the list.
225 extern gl_list_node_t gl_list_add_last (gl_list_t list, const void *elt);
227 /* Add an element before a given element node of the list.
229 extern gl_list_node_t gl_list_add_before (gl_list_t list, gl_list_node_t node,
232 /* Add an element after a given element node of the list.
234 extern gl_list_node_t gl_list_add_after (gl_list_t list, gl_list_node_t node,
237 /* Add an element add a given position in the list.
238 POSITION must be >= 0 and <= gl_list_size (list). */
239 extern gl_list_node_t gl_list_add_at (gl_list_t list, size_t position,
242 /* Remove an element from the list.
244 extern bool gl_list_remove_node (gl_list_t list, gl_list_node_t node);
246 /* Remove an element at a given position from the list.
247 POSITION must be >= 0 and < gl_list_size (list).
249 extern bool gl_list_remove_at (gl_list_t list, size_t position);
251 /* Search and remove an element from the list.
252 Return true if it was found and removed. */
253 extern bool gl_list_remove (gl_list_t list, const void *elt);
255 /* Free an entire list.
256 (But this call does not free the elements of the list.) */
257 extern void gl_list_free (gl_list_t list);
259 /* --------------------- gl_list_iterator_t Data Type --------------------- */
261 /* Functions for iterating through a list. */
263 /* Type of an iterator that traverses a list.
264 This is a fixed-size struct, so that creation of an iterator doesn't need
265 memory allocation on the heap. */
268 /* For fast dispatch of gl_list_iterator_next. */
269 const struct gl_list_implementation *vtable;
270 /* For detecting whether the last returned element was removed. */
273 /* Other, implementation-private fields. */
276 } gl_list_iterator_t;
278 /* Create an iterator traversing a list.
279 The list contents must not be modified while the iterator is in use,
280 except for replacing or removing the last returned element. */
281 extern gl_list_iterator_t gl_list_iterator (gl_list_t list);
283 /* Create an iterator traversing the element with indices i,
284 start_index <= i < end_index, of a list.
285 The list contents must not be modified while the iterator is in use,
286 except for replacing or removing the last returned element. */
287 extern gl_list_iterator_t gl_list_iterator_from_to (gl_list_t list,
291 /* If there is a next element, store the next element in *ELTP, store its
292 node in *NODEP if NODEP is non-NULL, advance the iterator and return true.
293 Otherwise, return false. */
294 extern bool gl_list_iterator_next (gl_list_iterator_t *iterator,
295 const void **eltp, gl_list_node_t *nodep);
297 /* Free an iterator. */
298 extern void gl_list_iterator_free (gl_list_iterator_t *iterator);
300 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
302 /* The following functions are for lists without duplicates where the
303 order is given by a sort criterion. */
305 /* Type of function used to compare two elements. Same as for qsort().
306 NULL denotes pointer comparison. */
307 typedef int (*gl_listelement_compar_fn) (const void *elt1, const void *elt2);
309 /* Search whether an element is already in the list.
310 The list is assumed to be sorted with COMPAR.
311 Return its node if found, or NULL if not present in the list.
312 If the list contains several copies of ELT, the node of the leftmost one is
314 extern gl_list_node_t gl_sortedlist_search (gl_list_t list,
315 gl_listelement_compar_fn compar,
318 /* Search whether an element is already in the list.
319 The list is assumed to be sorted with COMPAR.
320 Only list elements with indices >= START_INDEX and < END_INDEX are
321 considered; the implementation uses these bounds to minimize the number
322 of COMPAR invocations.
323 Return its node if found, or NULL if not present in the list.
324 If the list contains several copies of ELT, the node of the leftmost one is
326 extern gl_list_node_t gl_sortedlist_search_from_to (gl_list_t list,
327 gl_listelement_compar_fn compar,
332 /* Search whether an element is already in the list.
333 The list is assumed to be sorted with COMPAR.
334 Return its position if found, or (size_t)(-1) if not present in the list.
335 If the list contains several copies of ELT, the position of the leftmost one
337 extern size_t gl_sortedlist_indexof (gl_list_t list,
338 gl_listelement_compar_fn compar,
341 /* Search whether an element is already in the list.
342 The list is assumed to be sorted with COMPAR.
343 Only list elements with indices >= START_INDEX and < END_INDEX are
344 considered; the implementation uses these bounds to minimize the number
345 of COMPAR invocations.
346 Return its position if found, or (size_t)(-1) if not present in the list.
347 If the list contains several copies of ELT, the position of the leftmost one
349 extern size_t gl_sortedlist_indexof_from_to (gl_list_t list,
350 gl_listelement_compar_fn compar,
355 /* Add an element at the appropriate position in the list.
356 The list is assumed to be sorted with COMPAR.
358 extern gl_list_node_t gl_sortedlist_add (gl_list_t list,
359 gl_listelement_compar_fn compar,
362 /* Search and remove an element from the list.
363 The list is assumed to be sorted with COMPAR.
364 Return true if it was found and removed.
365 If the list contains several copies of ELT, only the leftmost one is
367 extern bool gl_sortedlist_remove (gl_list_t list,
368 gl_listelement_compar_fn compar,
371 /* ------------------------ Implementation Details ------------------------ */
373 struct gl_list_implementation
375 /* gl_list_t functions. */
376 gl_list_t (*create_empty) (gl_list_implementation_t implementation,
377 gl_listelement_equals_fn equals_fn,
378 gl_listelement_hashcode_fn hashcode_fn,
379 gl_listelement_dispose_fn dispose_fn,
380 bool allow_duplicates);
381 gl_list_t (*create) (gl_list_implementation_t implementation,
382 gl_listelement_equals_fn equals_fn,
383 gl_listelement_hashcode_fn hashcode_fn,
384 gl_listelement_dispose_fn dispose_fn,
385 bool allow_duplicates,
386 size_t count, const void **contents);
387 size_t (*size) (gl_list_t list);
388 const void * (*node_value) (gl_list_t list, gl_list_node_t node);
389 void (*node_set_value) (gl_list_t list, gl_list_node_t node, const void *elt);
390 gl_list_node_t (*next_node) (gl_list_t list, gl_list_node_t node);
391 gl_list_node_t (*previous_node) (gl_list_t list, gl_list_node_t node);
392 const void * (*get_at) (gl_list_t list, size_t position);
393 gl_list_node_t (*set_at) (gl_list_t list, size_t position, const void *elt);
394 gl_list_node_t (*search_from_to) (gl_list_t list, size_t start_index,
395 size_t end_index, const void *elt);
396 size_t (*indexof_from_to) (gl_list_t list, size_t start_index,
397 size_t end_index, const void *elt);
398 gl_list_node_t (*add_first) (gl_list_t list, const void *elt);
399 gl_list_node_t (*add_last) (gl_list_t list, const void *elt);
400 gl_list_node_t (*add_before) (gl_list_t list, gl_list_node_t node,
402 gl_list_node_t (*add_after) (gl_list_t list, gl_list_node_t node,
404 gl_list_node_t (*add_at) (gl_list_t list, size_t position,
406 bool (*remove_node) (gl_list_t list, gl_list_node_t node);
407 bool (*remove_at) (gl_list_t list, size_t position);
408 bool (*remove) (gl_list_t list, const void *elt);
409 void (*list_free) (gl_list_t list);
410 /* gl_list_iterator_t functions. */
411 gl_list_iterator_t (*iterator) (gl_list_t list);
412 gl_list_iterator_t (*iterator_from_to) (gl_list_t list,
415 bool (*iterator_next) (gl_list_iterator_t *iterator,
416 const void **eltp, gl_list_node_t *nodep);
417 void (*iterator_free) (gl_list_iterator_t *iterator);
418 /* Sorted gl_list_t functions. */
419 gl_list_node_t (*sortedlist_search) (gl_list_t list,
420 gl_listelement_compar_fn compar,
422 gl_list_node_t (*sortedlist_search_from_to) (gl_list_t list,
423 gl_listelement_compar_fn compar,
427 size_t (*sortedlist_indexof) (gl_list_t list,
428 gl_listelement_compar_fn compar,
430 size_t (*sortedlist_indexof_from_to) (gl_list_t list,
431 gl_listelement_compar_fn compar,
432 size_t start_index, size_t end_index,
434 gl_list_node_t (*sortedlist_add) (gl_list_t list,
435 gl_listelement_compar_fn compar,
437 bool (*sortedlist_remove) (gl_list_t list,
438 gl_listelement_compar_fn compar,
442 struct gl_list_impl_base
444 const struct gl_list_implementation *vtable;
445 gl_listelement_equals_fn equals_fn;
446 gl_listelement_hashcode_fn hashcode_fn;
447 gl_listelement_dispose_fn dispose_fn;
448 bool allow_duplicates;
453 /* Define all functions of this file as inline accesses to the
454 struct gl_list_implementation.
455 Use #define to avoid a warning because of extern vs. static. */
457 # define gl_list_create_empty gl_list_create_empty_inline
458 static inline gl_list_t
459 gl_list_create_empty (gl_list_implementation_t implementation,
460 gl_listelement_equals_fn equals_fn,
461 gl_listelement_hashcode_fn hashcode_fn,
462 gl_listelement_dispose_fn dispose_fn,
463 bool allow_duplicates)
465 return implementation->create_empty (implementation, equals_fn, hashcode_fn,
466 dispose_fn, allow_duplicates);
469 # define gl_list_create gl_list_create_inline
470 static inline gl_list_t
471 gl_list_create (gl_list_implementation_t implementation,
472 gl_listelement_equals_fn equals_fn,
473 gl_listelement_hashcode_fn hashcode_fn,
474 gl_listelement_dispose_fn dispose_fn,
475 bool allow_duplicates,
476 size_t count, const void **contents)
478 return implementation->create (implementation, equals_fn, hashcode_fn,
479 dispose_fn, allow_duplicates, count, contents);
482 # define gl_list_size gl_list_size_inline
484 gl_list_size (gl_list_t list)
486 return ((const struct gl_list_impl_base *) list)->vtable
490 # define gl_list_node_value gl_list_node_value_inline
491 static inline const void *
492 gl_list_node_value (gl_list_t list, gl_list_node_t node)
494 return ((const struct gl_list_impl_base *) list)->vtable
495 ->node_value (list, node);
498 # define gl_list_node_set_value gl_list_node_set_value_inline
500 gl_list_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt)
502 ((const struct gl_list_impl_base *) list)->vtable
503 ->node_set_value (list, node, elt);
506 # define gl_list_next_node gl_list_next_node_inline
507 static inline gl_list_node_t
508 gl_list_next_node (gl_list_t list, gl_list_node_t node)
510 return ((const struct gl_list_impl_base *) list)->vtable
511 ->next_node (list, node);
514 # define gl_list_previous_node gl_list_previous_node_inline
515 static inline gl_list_node_t
516 gl_list_previous_node (gl_list_t list, gl_list_node_t node)
518 return ((const struct gl_list_impl_base *) list)->vtable
519 ->previous_node (list, node);
522 # define gl_list_get_at gl_list_get_at_inline
523 static inline const void *
524 gl_list_get_at (gl_list_t list, size_t position)
526 return ((const struct gl_list_impl_base *) list)->vtable
527 ->get_at (list, position);
530 # define gl_list_set_at gl_list_set_at_inline
531 static inline gl_list_node_t
532 gl_list_set_at (gl_list_t list, size_t position, const void *elt)
534 return ((const struct gl_list_impl_base *) list)->vtable
535 ->set_at (list, position, elt);
538 # define gl_list_search gl_list_search_inline
539 static inline gl_list_node_t
540 gl_list_search (gl_list_t list, const void *elt)
542 size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
543 return ((const struct gl_list_impl_base *) list)->vtable
544 ->search_from_to (list, 0, size, elt);
547 # define gl_list_search_from gl_list_search_from_inline
548 static inline gl_list_node_t
549 gl_list_search_from (gl_list_t list, size_t start_index, const void *elt)
551 size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
552 return ((const struct gl_list_impl_base *) list)->vtable
553 ->search_from_to (list, start_index, size, elt);
556 # define gl_list_search_from_to gl_list_search_from_to_inline
557 static inline gl_list_node_t
558 gl_list_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
561 return ((const struct gl_list_impl_base *) list)->vtable
562 ->search_from_to (list, start_index, end_index, elt);
565 # define gl_list_indexof gl_list_indexof_inline
567 gl_list_indexof (gl_list_t list, const void *elt)
569 size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
570 return ((const struct gl_list_impl_base *) list)->vtable
571 ->indexof_from_to (list, 0, size, elt);
574 # define gl_list_indexof_from gl_list_indexof_from_inline
576 gl_list_indexof_from (gl_list_t list, size_t start_index, const void *elt)
578 size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
579 return ((const struct gl_list_impl_base *) list)->vtable
580 ->indexof_from_to (list, start_index, size, elt);
583 # define gl_list_indexof_from_to gl_list_indexof_from_to_inline
585 gl_list_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
588 return ((const struct gl_list_impl_base *) list)->vtable
589 ->indexof_from_to (list, start_index, end_index, elt);
592 # define gl_list_add_first gl_list_add_first_inline
593 static inline gl_list_node_t
594 gl_list_add_first (gl_list_t list, const void *elt)
596 return ((const struct gl_list_impl_base *) list)->vtable
597 ->add_first (list, elt);
600 # define gl_list_add_last gl_list_add_last_inline
601 static inline gl_list_node_t
602 gl_list_add_last (gl_list_t list, const void *elt)
604 return ((const struct gl_list_impl_base *) list)->vtable
605 ->add_last (list, elt);
608 # define gl_list_add_before gl_list_add_before_inline
609 static inline gl_list_node_t
610 gl_list_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
612 return ((const struct gl_list_impl_base *) list)->vtable
613 ->add_before (list, node, elt);
616 # define gl_list_add_after gl_list_add_after_inline
617 static inline gl_list_node_t
618 gl_list_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
620 return ((const struct gl_list_impl_base *) list)->vtable
621 ->add_after (list, node, elt);
624 # define gl_list_add_at gl_list_add_at_inline
625 static inline gl_list_node_t
626 gl_list_add_at (gl_list_t list, size_t position, const void *elt)
628 return ((const struct gl_list_impl_base *) list)->vtable
629 ->add_at (list, position, elt);
632 # define gl_list_remove_node gl_list_remove_node_inline
634 gl_list_remove_node (gl_list_t list, gl_list_node_t node)
636 return ((const struct gl_list_impl_base *) list)->vtable
637 ->remove_node (list, node);
640 # define gl_list_remove_at gl_list_remove_at_inline
642 gl_list_remove_at (gl_list_t list, size_t position)
644 return ((const struct gl_list_impl_base *) list)->vtable
645 ->remove_at (list, position);
648 # define gl_list_remove gl_list_remove_inline
650 gl_list_remove (gl_list_t list, const void *elt)
652 return ((const struct gl_list_impl_base *) list)->vtable
653 ->remove (list, elt);
656 # define gl_list_free gl_list_free_inline
658 gl_list_free (gl_list_t list)
660 ((const struct gl_list_impl_base *) list)->vtable->list_free (list);
663 # define gl_list_iterator gl_list_iterator_inline
664 static inline gl_list_iterator_t
665 gl_list_iterator (gl_list_t list)
667 return ((const struct gl_list_impl_base *) list)->vtable
671 # define gl_list_iterator_from_to gl_list_iterator_from_to_inline
672 static inline gl_list_iterator_t
673 gl_list_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
675 return ((const struct gl_list_impl_base *) list)->vtable
676 ->iterator_from_to (list, start_index, end_index);
679 # define gl_list_iterator_next gl_list_iterator_next_inline
681 gl_list_iterator_next (gl_list_iterator_t *iterator,
682 const void **eltp, gl_list_node_t *nodep)
684 return iterator->vtable->iterator_next (iterator, eltp, nodep);
687 # define gl_list_iterator_free gl_list_iterator_free_inline
689 gl_list_iterator_free (gl_list_iterator_t *iterator)
691 iterator->vtable->iterator_free (iterator);
694 # define gl_sortedlist_search gl_sortedlist_search_inline
695 static inline gl_list_node_t
696 gl_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
698 return ((const struct gl_list_impl_base *) list)->vtable
699 ->sortedlist_search (list, compar, elt);
702 # define gl_sortedlist_search_from_to gl_sortedlist_search_from_to_inline
703 static inline gl_list_node_t
704 gl_sortedlist_search_from_to (gl_list_t list, gl_listelement_compar_fn compar, size_t start_index, size_t end_index, const void *elt)
706 return ((const struct gl_list_impl_base *) list)->vtable
707 ->sortedlist_search_from_to (list, compar, start_index, end_index,
711 # define gl_sortedlist_indexof gl_sortedlist_indexof_inline
713 gl_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
715 return ((const struct gl_list_impl_base *) list)->vtable
716 ->sortedlist_indexof (list, compar, elt);
719 # define gl_sortedlist_indexof_from_to gl_sortedlist_indexof_from_to_inline
721 gl_sortedlist_indexof_from_to (gl_list_t list, gl_listelement_compar_fn compar, size_t start_index, size_t end_index, const void *elt)
723 return ((const struct gl_list_impl_base *) list)->vtable
724 ->sortedlist_indexof_from_to (list, compar, start_index, end_index,
728 # define gl_sortedlist_add gl_sortedlist_add_inline
729 static inline gl_list_node_t
730 gl_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
732 return ((const struct gl_list_impl_base *) list)->vtable
733 ->sortedlist_add (list, compar, elt);
736 # define gl_sortedlist_remove gl_sortedlist_remove_inline
738 gl_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
740 return ((const struct gl_list_impl_base *) list)->vtable
741 ->sortedlist_remove (list, compar, elt);
750 #endif /* _GL_LIST_H */