1 /* Abstract sequential list data type.
2 Copyright (C) 2006-2013 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/>. */
24 _GL_INLINE_HEADER_BEGIN
25 #ifndef GL_LIST_INLINE
26 # define GL_LIST_INLINE _GL_INLINE
34 /* gl_list is an abstract list data type. It can contain any number of
35 objects ('void *' or 'const void *' pointers) in any given order.
36 Duplicates are allowed, but can optionally be forbidden.
38 There are several implementations of this list datatype, optimized for
39 different operations or for memory. You can start using the simplest list
40 implementation, GL_ARRAY_LIST, and switch to a different implementation
41 later, when you realize which operations are performed the most frequently.
42 The API of the different implementations is exactly the same; when
43 switching to a different implementation, you only have to change the
46 The implementations are:
47 GL_ARRAY_LIST a growable array
48 GL_CARRAY_LIST a growable circular array
49 GL_LINKED_LIST a linked list
50 GL_AVLTREE_LIST a binary tree (AVL tree)
51 GL_RBTREE_LIST a binary tree (red-black tree)
52 GL_LINKEDHASH_LIST a hash table with a linked list
53 GL_AVLTREEHASH_LIST a hash table with a binary tree (AVL tree)
54 GL_RBTREEHASH_LIST a hash table with a binary tree (red-black tree)
56 The memory consumption is asymptotically the same: O(1) for every object
57 in the list. When looking more closely at the average memory consumed
58 for an object, GL_ARRAY_LIST is the most compact representation, and
59 GL_LINKEDHASH_LIST and GL_TREEHASH_LIST need more memory.
61 The guaranteed average performance of the operations is, for a list of
64 Operation ARRAY LINKED TREE LINKEDHASH TREEHASH
65 CARRAY with|without with|without
68 gl_list_size O(1) O(1) O(1) O(1) O(1)
69 gl_list_node_value O(1) O(1) O(1) O(1) O(1)
70 gl_list_node_set_value O(1) O(1) O(1) O(1) O((log n)²)/O(1)
71 gl_list_next_node O(1) O(1) O(log n) O(1) O(log n)
72 gl_list_previous_node O(1) O(1) O(log n) O(1) O(log n)
73 gl_list_get_at O(1) O(n) O(log n) O(n) O(log n)
74 gl_list_set_at O(1) O(n) O(log n) O(n) O((log n)²)/O(log n)
75 gl_list_search O(n) O(n) O(n) O(n)/O(1) O(log n)/O(1)
76 gl_list_search_from O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n)
77 gl_list_search_from_to O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n)
78 gl_list_indexof O(n) O(n) O(n) O(n) O(log n)
79 gl_list_indexof_from O(n) O(n) O(n) O(n) O((log n)²)/O(log n)
80 gl_list_indexof_from_to O(n) O(n) O(n) O(n) O((log n)²)/O(log n)
81 gl_list_add_first O(n)/O(1) O(1) O(log n) O(1) O((log n)²)/O(log n)
82 gl_list_add_last O(1) O(1) O(log n) O(1) O((log n)²)/O(log n)
83 gl_list_add_before O(n) O(1) O(log n) O(1) O((log n)²)/O(log n)
84 gl_list_add_after O(n) O(1) O(log n) O(1) O((log n)²)/O(log n)
85 gl_list_add_at O(n) O(n) O(log n) O(n) O((log n)²)/O(log n)
86 gl_list_remove_node O(n) O(1) O(log n) O(n)/O(1) O((log n)²)/O(log n)
87 gl_list_remove_at O(n) O(n) O(log n) O(n) O((log n)²)/O(log n)
88 gl_list_remove O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n)
89 gl_list_iterator O(1) O(1) O(log n) O(1) O(log n)
90 gl_list_iterator_from_to O(1) O(n) O(log n) O(n) O(log n)
91 gl_list_iterator_next O(1) O(1) O(log n) O(1) O(log n)
92 gl_sortedlist_search O(log n) O(n) O(log n) O(n) O(log n)
93 gl_sortedlist_search_from O(log n) O(n) O(log n) O(n) O(log n)
94 gl_sortedlist_indexof O(log n) O(n) O(log n) O(n) O(log n)
95 gl_sortedlist_indexof_fro O(log n) O(n) O(log n) O(n) O(log n)
96 gl_sortedlist_add O(n) O(n) O(log n) O(n) O((log n)²)/O(log n)
97 gl_sortedlist_remove O(n) O(n) O(log n) O(n) O((log n)²)/O(log n)
100 /* -------------------------- gl_list_t Data Type -------------------------- */
102 /* Type of function used to compare two elements.
103 NULL denotes pointer comparison. */
104 typedef bool (*gl_listelement_equals_fn) (const void *elt1, const void *elt2);
106 /* Type of function used to compute a hash code.
107 NULL denotes a function that depends only on the pointer itself. */
108 typedef size_t (*gl_listelement_hashcode_fn) (const void *elt);
110 /* Type of function used to dispose an element once it's removed from a list.
111 NULL denotes a no-op. */
112 typedef void (*gl_listelement_dispose_fn) (const void *elt);
115 /* Type representing an entire list. */
116 typedef struct gl_list_impl * gl_list_t;
118 struct gl_list_node_impl;
119 /* Type representing the position of an element in the list, in a way that
120 is more adapted to the list implementation than a plain index.
121 Note: It is invalidated by insertions and removals! */
122 typedef struct gl_list_node_impl * gl_list_node_t;
124 struct gl_list_implementation;
125 /* Type representing a list datatype implementation. */
126 typedef const struct gl_list_implementation * gl_list_implementation_t;
128 #if 0 /* Unless otherwise specified, these are defined inline below. */
130 /* Create an empty list.
131 IMPLEMENTATION is one of GL_ARRAY_LIST, GL_CARRAY_LIST, GL_LINKED_LIST,
132 GL_AVLTREE_LIST, GL_RBTREE_LIST, GL_LINKEDHASH_LIST, GL_AVLTREEHASH_LIST,
134 EQUALS_FN is an element comparison function or NULL.
135 HASHCODE_FN is an element hash code function or NULL.
136 DISPOSE_FN is an element disposal function or NULL.
137 ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in
138 the list. The implementation may verify this at runtime. */
139 /* declared in gl_xlist.h */
140 extern gl_list_t gl_list_create_empty (gl_list_implementation_t implementation,
141 gl_listelement_equals_fn equals_fn,
142 gl_listelement_hashcode_fn hashcode_fn,
143 gl_listelement_dispose_fn dispose_fn,
144 bool allow_duplicates);
145 /* Likewise. Return NULL upon out-of-memory. */
146 extern gl_list_t gl_list_nx_create_empty (gl_list_implementation_t implementation,
147 gl_listelement_equals_fn equals_fn,
148 gl_listelement_hashcode_fn hashcode_fn,
149 gl_listelement_dispose_fn dispose_fn,
150 bool allow_duplicates);
152 /* Create a list with given contents.
153 IMPLEMENTATION is one of GL_ARRAY_LIST, GL_CARRAY_LIST, GL_LINKED_LIST,
154 GL_AVLTREE_LIST, GL_RBTREE_LIST, GL_LINKEDHASH_LIST, GL_AVLTREEHASH_LIST,
156 EQUALS_FN is an element comparison function or NULL.
157 HASHCODE_FN is an element hash code function or NULL.
158 DISPOSE_FN is an element disposal function or NULL.
159 ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in
160 the list. The implementation may verify this at runtime.
161 COUNT is the number of initial elements.
162 CONTENTS[0..COUNT-1] is the initial contents. */
163 /* declared in gl_xlist.h */
164 extern gl_list_t gl_list_create (gl_list_implementation_t implementation,
165 gl_listelement_equals_fn equals_fn,
166 gl_listelement_hashcode_fn hashcode_fn,
167 gl_listelement_dispose_fn dispose_fn,
168 bool allow_duplicates,
169 size_t count, const void **contents);
170 /* Likewise. Return NULL upon out-of-memory. */
171 extern gl_list_t gl_list_nx_create (gl_list_implementation_t implementation,
172 gl_listelement_equals_fn equals_fn,
173 gl_listelement_hashcode_fn hashcode_fn,
174 gl_listelement_dispose_fn dispose_fn,
175 bool allow_duplicates,
176 size_t count, const void **contents);
178 /* Return the current number of elements in a list. */
179 extern size_t gl_list_size (gl_list_t list);
181 /* Return the element value represented by a list node. */
182 extern const void * gl_list_node_value (gl_list_t list, gl_list_node_t node);
184 /* Replace the element value represented by a list node. */
185 /* declared in gl_xlist.h */
186 extern void gl_list_node_set_value (gl_list_t list, gl_list_node_t node,
188 /* Likewise. Return 0 upon success, -1 upon out-of-memory. */
189 extern int gl_list_node_nx_set_value (gl_list_t list, gl_list_node_t node,
191 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
192 __attribute__ ((__warn_unused_result__))
196 /* Return the node immediately after the given node in the list, or NULL
197 if the given node is the last (rightmost) one in the list. */
198 extern gl_list_node_t gl_list_next_node (gl_list_t list, gl_list_node_t node);
200 /* Return the node immediately before the given node in the list, or NULL
201 if the given node is the first (leftmost) one in the list. */
202 extern gl_list_node_t gl_list_previous_node (gl_list_t list, gl_list_node_t node);
204 /* Return the element at a given position in the list.
205 POSITION must be >= 0 and < gl_list_size (list). */
206 extern const void * gl_list_get_at (gl_list_t list, size_t position);
208 /* Replace the element at a given position in the list.
209 POSITION must be >= 0 and < gl_list_size (list).
211 /* declared in gl_xlist.h */
212 extern gl_list_node_t gl_list_set_at (gl_list_t list, size_t position,
214 /* Likewise. Return NULL upon out-of-memory. */
215 extern gl_list_node_t gl_list_nx_set_at (gl_list_t list, size_t position,
217 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
218 __attribute__ ((__warn_unused_result__))
222 /* Search whether an element is already in the list.
223 Return its node if found, or NULL if not present in the list. */
224 extern gl_list_node_t gl_list_search (gl_list_t list, const void *elt);
226 /* Search whether an element is already in the list,
227 at a position >= START_INDEX.
228 Return its node if found, or NULL if not present in the list. */
229 extern gl_list_node_t gl_list_search_from (gl_list_t list, size_t start_index,
232 /* Search whether an element is already in the list,
233 at a position >= START_INDEX and < END_INDEX.
234 Return its node if found, or NULL if not present in the list. */
235 extern gl_list_node_t gl_list_search_from_to (gl_list_t list,
240 /* Search whether an element is already in the list.
241 Return its position if found, or (size_t)(-1) if not present in the list. */
242 extern size_t gl_list_indexof (gl_list_t list, const void *elt);
244 /* Search whether an element is already in the list,
245 at a position >= START_INDEX.
246 Return its position if found, or (size_t)(-1) if not present in the list. */
247 extern size_t gl_list_indexof_from (gl_list_t list, size_t start_index,
250 /* Search whether an element is already in the list,
251 at a position >= START_INDEX and < END_INDEX.
252 Return its position if found, or (size_t)(-1) if not present in the list. */
253 extern size_t gl_list_indexof_from_to (gl_list_t list,
254 size_t start_index, size_t end_index,
257 /* Add an element as the first element of the list.
259 /* declared in gl_xlist.h */
260 extern gl_list_node_t gl_list_add_first (gl_list_t list, const void *elt);
261 /* Likewise. Return NULL upon out-of-memory. */
262 extern gl_list_node_t gl_list_nx_add_first (gl_list_t list, const void *elt)
263 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
264 __attribute__ ((__warn_unused_result__))
268 /* Add an element as the last element of the list.
270 /* declared in gl_xlist.h */
271 extern gl_list_node_t gl_list_add_last (gl_list_t list, const void *elt);
272 /* Likewise. Return NULL upon out-of-memory. */
273 extern gl_list_node_t gl_list_nx_add_last (gl_list_t list, const void *elt)
274 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
275 __attribute__ ((__warn_unused_result__))
279 /* Add an element before a given element node of the list.
281 /* declared in gl_xlist.h */
282 extern gl_list_node_t gl_list_add_before (gl_list_t list, gl_list_node_t node,
284 /* Likewise. Return NULL upon out-of-memory. */
285 extern gl_list_node_t gl_list_nx_add_before (gl_list_t list,
288 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
289 __attribute__ ((__warn_unused_result__))
293 /* Add an element after a given element node of the list.
295 /* declared in gl_xlist.h */
296 extern gl_list_node_t gl_list_add_after (gl_list_t list, gl_list_node_t node,
298 /* Likewise. Return NULL upon out-of-memory. */
299 extern gl_list_node_t gl_list_nx_add_after (gl_list_t list, gl_list_node_t node,
301 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
302 __attribute__ ((__warn_unused_result__))
306 /* Add an element at a given position in the list.
307 POSITION must be >= 0 and <= gl_list_size (list). */
308 /* declared in gl_xlist.h */
309 extern gl_list_node_t gl_list_add_at (gl_list_t list, size_t position,
311 /* Likewise. Return NULL upon out-of-memory. */
312 extern gl_list_node_t gl_list_nx_add_at (gl_list_t list, size_t position,
314 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
315 __attribute__ ((__warn_unused_result__))
319 /* Remove an element from the list.
321 extern bool gl_list_remove_node (gl_list_t list, gl_list_node_t node);
323 /* Remove an element at a given position from the list.
324 POSITION must be >= 0 and < gl_list_size (list).
326 extern bool gl_list_remove_at (gl_list_t list, size_t position);
328 /* Search and remove an element from the list.
329 Return true if it was found and removed. */
330 extern bool gl_list_remove (gl_list_t list, const void *elt);
332 /* Free an entire list.
333 (But this call does not free the elements of the list.) */
334 extern void gl_list_free (gl_list_t list);
336 #endif /* End of inline and gl_xlist.h-defined functions. */
338 /* --------------------- gl_list_iterator_t Data Type --------------------- */
340 /* Functions for iterating through a list. */
342 /* Type of an iterator that traverses a list.
343 This is a fixed-size struct, so that creation of an iterator doesn't need
344 memory allocation on the heap. */
347 /* For fast dispatch of gl_list_iterator_next. */
348 const struct gl_list_implementation *vtable;
349 /* For detecting whether the last returned element was removed. */
352 /* Other, implementation-private fields. */
355 } gl_list_iterator_t;
357 #if 0 /* These are defined inline below. */
359 /* Create an iterator traversing a list.
360 The list contents must not be modified while the iterator is in use,
361 except for replacing or removing the last returned element. */
362 extern gl_list_iterator_t gl_list_iterator (gl_list_t list);
364 /* Create an iterator traversing the element with indices i,
365 start_index <= i < end_index, of a list.
366 The list contents must not be modified while the iterator is in use,
367 except for replacing or removing the last returned element. */
368 extern gl_list_iterator_t gl_list_iterator_from_to (gl_list_t list,
372 /* If there is a next element, store the next element in *ELTP, store its
373 node in *NODEP if NODEP is non-NULL, advance the iterator and return true.
374 Otherwise, return false. */
375 extern bool gl_list_iterator_next (gl_list_iterator_t *iterator,
376 const void **eltp, gl_list_node_t *nodep);
378 /* Free an iterator. */
379 extern void gl_list_iterator_free (gl_list_iterator_t *iterator);
381 #endif /* End of inline functions. */
383 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
385 /* The following functions are for lists without duplicates where the
386 order is given by a sort criterion. */
388 /* Type of function used to compare two elements. Same as for qsort().
389 NULL denotes pointer comparison. */
390 typedef int (*gl_listelement_compar_fn) (const void *elt1, const void *elt2);
392 #if 0 /* Unless otherwise specified, these are defined inline below. */
394 /* Search whether an element is already in the list.
395 The list is assumed to be sorted with COMPAR.
396 Return its node if found, or NULL if not present in the list.
397 If the list contains several copies of ELT, the node of the leftmost one is
399 extern gl_list_node_t gl_sortedlist_search (gl_list_t list,
400 gl_listelement_compar_fn compar,
403 /* Search whether an element is already in the list.
404 The list is assumed to be sorted with COMPAR.
405 Only list elements with indices >= START_INDEX and < END_INDEX are
406 considered; the implementation uses these bounds to minimize the number
407 of COMPAR invocations.
408 Return its node if found, or NULL if not present in the list.
409 If the list contains several copies of ELT, the node of the leftmost one is
411 extern gl_list_node_t gl_sortedlist_search_from_to (gl_list_t list,
412 gl_listelement_compar_fn compar,
417 /* Search whether an element is already in the list.
418 The list is assumed to be sorted with COMPAR.
419 Return its position if found, or (size_t)(-1) if not present in the list.
420 If the list contains several copies of ELT, the position of the leftmost one
422 extern size_t gl_sortedlist_indexof (gl_list_t list,
423 gl_listelement_compar_fn compar,
426 /* Search whether an element is already in the list.
427 The list is assumed to be sorted with COMPAR.
428 Only list elements with indices >= START_INDEX and < END_INDEX are
429 considered; the implementation uses these bounds to minimize the number
430 of COMPAR invocations.
431 Return its position if found, or (size_t)(-1) if not present in the list.
432 If the list contains several copies of ELT, the position of the leftmost one
434 extern size_t gl_sortedlist_indexof_from_to (gl_list_t list,
435 gl_listelement_compar_fn compar,
440 /* Add an element at the appropriate position in the list.
441 The list is assumed to be sorted with COMPAR.
443 /* declared in gl_xlist.h */
444 extern gl_list_node_t gl_sortedlist_add (gl_list_t list,
445 gl_listelement_compar_fn compar,
447 /* Likewise. Return NULL upon out-of-memory. */
448 extern gl_list_node_t gl_sortedlist_nx_add (gl_list_t list,
449 gl_listelement_compar_fn compar,
451 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
452 __attribute__ ((__warn_unused_result__))
456 /* Search and remove an element from the list.
457 The list is assumed to be sorted with COMPAR.
458 Return true if it was found and removed.
459 If the list contains several copies of ELT, only the leftmost one is
461 extern bool gl_sortedlist_remove (gl_list_t list,
462 gl_listelement_compar_fn compar,
465 #endif /* End of inline and gl_xlist.h-defined functions. */
467 /* ------------------------ Implementation Details ------------------------ */
469 struct gl_list_implementation
471 /* gl_list_t functions. */
472 gl_list_t (*nx_create_empty) (gl_list_implementation_t implementation,
473 gl_listelement_equals_fn equals_fn,
474 gl_listelement_hashcode_fn hashcode_fn,
475 gl_listelement_dispose_fn dispose_fn,
476 bool allow_duplicates);
477 gl_list_t (*nx_create) (gl_list_implementation_t implementation,
478 gl_listelement_equals_fn equals_fn,
479 gl_listelement_hashcode_fn hashcode_fn,
480 gl_listelement_dispose_fn dispose_fn,
481 bool allow_duplicates,
482 size_t count, const void **contents);
483 size_t (*size) (gl_list_t list);
484 const void * (*node_value) (gl_list_t list, gl_list_node_t node);
485 int (*node_nx_set_value) (gl_list_t list, gl_list_node_t node,
487 gl_list_node_t (*next_node) (gl_list_t list, gl_list_node_t node);
488 gl_list_node_t (*previous_node) (gl_list_t list, gl_list_node_t node);
489 const void * (*get_at) (gl_list_t list, size_t position);
490 gl_list_node_t (*nx_set_at) (gl_list_t list, size_t position,
492 gl_list_node_t (*search_from_to) (gl_list_t list, size_t start_index,
493 size_t end_index, const void *elt);
494 size_t (*indexof_from_to) (gl_list_t list, size_t start_index,
495 size_t end_index, const void *elt);
496 gl_list_node_t (*nx_add_first) (gl_list_t list, const void *elt);
497 gl_list_node_t (*nx_add_last) (gl_list_t list, const void *elt);
498 gl_list_node_t (*nx_add_before) (gl_list_t list, gl_list_node_t node,
500 gl_list_node_t (*nx_add_after) (gl_list_t list, gl_list_node_t node,
502 gl_list_node_t (*nx_add_at) (gl_list_t list, size_t position,
504 bool (*remove_node) (gl_list_t list, gl_list_node_t node);
505 bool (*remove_at) (gl_list_t list, size_t position);
506 bool (*remove_elt) (gl_list_t list, const void *elt);
507 void (*list_free) (gl_list_t list);
508 /* gl_list_iterator_t functions. */
509 gl_list_iterator_t (*iterator) (gl_list_t list);
510 gl_list_iterator_t (*iterator_from_to) (gl_list_t list,
513 bool (*iterator_next) (gl_list_iterator_t *iterator,
514 const void **eltp, gl_list_node_t *nodep);
515 void (*iterator_free) (gl_list_iterator_t *iterator);
516 /* Sorted gl_list_t functions. */
517 gl_list_node_t (*sortedlist_search) (gl_list_t list,
518 gl_listelement_compar_fn compar,
520 gl_list_node_t (*sortedlist_search_from_to) (gl_list_t list,
521 gl_listelement_compar_fn compar,
525 size_t (*sortedlist_indexof) (gl_list_t list,
526 gl_listelement_compar_fn compar,
528 size_t (*sortedlist_indexof_from_to) (gl_list_t list,
529 gl_listelement_compar_fn compar,
530 size_t start_index, size_t end_index,
532 gl_list_node_t (*sortedlist_nx_add) (gl_list_t list,
533 gl_listelement_compar_fn compar,
535 bool (*sortedlist_remove) (gl_list_t list,
536 gl_listelement_compar_fn compar,
540 struct gl_list_impl_base
542 const struct gl_list_implementation *vtable;
543 gl_listelement_equals_fn equals_fn;
544 gl_listelement_hashcode_fn hashcode_fn;
545 gl_listelement_dispose_fn dispose_fn;
546 bool allow_duplicates;
549 /* Define all functions of this file as accesses to the
550 struct gl_list_implementation. */
552 GL_LIST_INLINE gl_list_t
553 gl_list_nx_create_empty (gl_list_implementation_t implementation,
554 gl_listelement_equals_fn equals_fn,
555 gl_listelement_hashcode_fn hashcode_fn,
556 gl_listelement_dispose_fn dispose_fn,
557 bool allow_duplicates)
559 return implementation->nx_create_empty (implementation, equals_fn,
560 hashcode_fn, dispose_fn,
564 GL_LIST_INLINE gl_list_t
565 gl_list_nx_create (gl_list_implementation_t implementation,
566 gl_listelement_equals_fn equals_fn,
567 gl_listelement_hashcode_fn hashcode_fn,
568 gl_listelement_dispose_fn dispose_fn,
569 bool allow_duplicates,
570 size_t count, const void **contents)
572 return implementation->nx_create (implementation, equals_fn, hashcode_fn,
573 dispose_fn, allow_duplicates, count,
577 GL_LIST_INLINE size_t
578 gl_list_size (gl_list_t list)
580 return ((const struct gl_list_impl_base *) list)->vtable
584 GL_LIST_INLINE const void *
585 gl_list_node_value (gl_list_t list, gl_list_node_t node)
587 return ((const struct gl_list_impl_base *) list)->vtable
588 ->node_value (list, node);
592 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
593 __attribute__ ((__warn_unused_result__))
595 gl_list_node_nx_set_value (gl_list_t list, gl_list_node_t node,
598 return ((const struct gl_list_impl_base *) list)->vtable
599 ->node_nx_set_value (list, node, elt);
602 GL_LIST_INLINE gl_list_node_t
603 gl_list_next_node (gl_list_t list, gl_list_node_t node)
605 return ((const struct gl_list_impl_base *) list)->vtable
606 ->next_node (list, node);
609 GL_LIST_INLINE gl_list_node_t
610 gl_list_previous_node (gl_list_t list, gl_list_node_t node)
612 return ((const struct gl_list_impl_base *) list)->vtable
613 ->previous_node (list, node);
616 GL_LIST_INLINE const void *
617 gl_list_get_at (gl_list_t list, size_t position)
619 return ((const struct gl_list_impl_base *) list)->vtable
620 ->get_at (list, position);
623 GL_LIST_INLINE gl_list_node_t
624 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
625 __attribute__ ((__warn_unused_result__))
627 gl_list_nx_set_at (gl_list_t list, size_t position, const void *elt)
629 return ((const struct gl_list_impl_base *) list)->vtable
630 ->nx_set_at (list, position, elt);
633 GL_LIST_INLINE gl_list_node_t
634 gl_list_search (gl_list_t list, const void *elt)
636 size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
637 return ((const struct gl_list_impl_base *) list)->vtable
638 ->search_from_to (list, 0, size, elt);
641 GL_LIST_INLINE gl_list_node_t
642 gl_list_search_from (gl_list_t list, size_t start_index, const void *elt)
644 size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
645 return ((const struct gl_list_impl_base *) list)->vtable
646 ->search_from_to (list, start_index, size, elt);
649 GL_LIST_INLINE gl_list_node_t
650 gl_list_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
653 return ((const struct gl_list_impl_base *) list)->vtable
654 ->search_from_to (list, start_index, end_index, elt);
657 GL_LIST_INLINE size_t
658 gl_list_indexof (gl_list_t list, const void *elt)
660 size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
661 return ((const struct gl_list_impl_base *) list)->vtable
662 ->indexof_from_to (list, 0, size, elt);
665 GL_LIST_INLINE size_t
666 gl_list_indexof_from (gl_list_t list, size_t start_index, const void *elt)
668 size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
669 return ((const struct gl_list_impl_base *) list)->vtable
670 ->indexof_from_to (list, start_index, size, elt);
673 GL_LIST_INLINE size_t
674 gl_list_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
677 return ((const struct gl_list_impl_base *) list)->vtable
678 ->indexof_from_to (list, start_index, end_index, elt);
681 GL_LIST_INLINE gl_list_node_t
682 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
683 __attribute__ ((__warn_unused_result__))
685 gl_list_nx_add_first (gl_list_t list, const void *elt)
687 return ((const struct gl_list_impl_base *) list)->vtable
688 ->nx_add_first (list, elt);
691 GL_LIST_INLINE gl_list_node_t
692 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
693 __attribute__ ((__warn_unused_result__))
695 gl_list_nx_add_last (gl_list_t list, const void *elt)
697 return ((const struct gl_list_impl_base *) list)->vtable
698 ->nx_add_last (list, elt);
701 GL_LIST_INLINE gl_list_node_t
702 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
703 __attribute__ ((__warn_unused_result__))
705 gl_list_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
707 return ((const struct gl_list_impl_base *) list)->vtable
708 ->nx_add_before (list, node, elt);
711 GL_LIST_INLINE gl_list_node_t
712 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
713 __attribute__ ((__warn_unused_result__))
715 gl_list_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
717 return ((const struct gl_list_impl_base *) list)->vtable
718 ->nx_add_after (list, node, elt);
721 GL_LIST_INLINE gl_list_node_t
722 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
723 __attribute__ ((__warn_unused_result__))
725 gl_list_nx_add_at (gl_list_t list, size_t position, const void *elt)
727 return ((const struct gl_list_impl_base *) list)->vtable
728 ->nx_add_at (list, position, elt);
732 gl_list_remove_node (gl_list_t list, gl_list_node_t node)
734 return ((const struct gl_list_impl_base *) list)->vtable
735 ->remove_node (list, node);
739 gl_list_remove_at (gl_list_t list, size_t position)
741 return ((const struct gl_list_impl_base *) list)->vtable
742 ->remove_at (list, position);
746 gl_list_remove (gl_list_t list, const void *elt)
748 return ((const struct gl_list_impl_base *) list)->vtable
749 ->remove_elt (list, elt);
753 gl_list_free (gl_list_t list)
755 ((const struct gl_list_impl_base *) list)->vtable->list_free (list);
758 GL_LIST_INLINE gl_list_iterator_t
759 gl_list_iterator (gl_list_t list)
761 return ((const struct gl_list_impl_base *) list)->vtable
765 GL_LIST_INLINE gl_list_iterator_t
766 gl_list_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
768 return ((const struct gl_list_impl_base *) list)->vtable
769 ->iterator_from_to (list, start_index, end_index);
773 gl_list_iterator_next (gl_list_iterator_t *iterator,
774 const void **eltp, gl_list_node_t *nodep)
776 return iterator->vtable->iterator_next (iterator, eltp, nodep);
780 gl_list_iterator_free (gl_list_iterator_t *iterator)
782 iterator->vtable->iterator_free (iterator);
785 GL_LIST_INLINE gl_list_node_t
786 gl_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
788 return ((const struct gl_list_impl_base *) list)->vtable
789 ->sortedlist_search (list, compar, elt);
792 GL_LIST_INLINE gl_list_node_t
793 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)
795 return ((const struct gl_list_impl_base *) list)->vtable
796 ->sortedlist_search_from_to (list, compar, start_index, end_index,
800 GL_LIST_INLINE size_t
801 gl_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
803 return ((const struct gl_list_impl_base *) list)->vtable
804 ->sortedlist_indexof (list, compar, elt);
807 GL_LIST_INLINE size_t
808 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)
810 return ((const struct gl_list_impl_base *) list)->vtable
811 ->sortedlist_indexof_from_to (list, compar, start_index, end_index,
815 GL_LIST_INLINE gl_list_node_t
816 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
817 __attribute__ ((__warn_unused_result__))
819 gl_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
821 return ((const struct gl_list_impl_base *) list)->vtable
822 ->sortedlist_nx_add (list, compar, elt);
826 gl_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
828 return ((const struct gl_list_impl_base *) list)->vtable
829 ->sortedlist_remove (list, compar, elt);
836 _GL_INLINE_HEADER_END
838 #endif /* _GL_LIST_H */