1 /* Abstract sequential list data type.
2 Copyright (C) 2006-2011 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 #if 0 /* declared in gl_xlist.h */
133 extern gl_list_t gl_list_create_empty (gl_list_implementation_t implementation,
134 gl_listelement_equals_fn equals_fn,
135 gl_listelement_hashcode_fn hashcode_fn,
136 gl_listelement_dispose_fn dispose_fn,
137 bool allow_duplicates);
139 /* Likewise. Return NULL upon out-of-memory. */
140 extern gl_list_t gl_list_nx_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);
146 /* Create a list with given contents.
147 IMPLEMENTATION is one of GL_ARRAY_LIST, GL_CARRAY_LIST, GL_LINKED_LIST,
148 GL_AVLTREE_LIST, GL_RBTREE_LIST, GL_LINKEDHASH_LIST, GL_AVLTREEHASH_LIST,
150 EQUALS_FN is an element comparison function or NULL.
151 HASHCODE_FN is an element hash code function or NULL.
152 DISPOSE_FN is an element disposal function or NULL.
153 ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in
154 the list. The implementation may verify this at runtime.
155 COUNT is the number of initial elements.
156 CONTENTS[0..COUNT-1] is the initial contents. */
157 #if 0 /* declared in gl_xlist.h */
158 extern gl_list_t gl_list_create (gl_list_implementation_t implementation,
159 gl_listelement_equals_fn equals_fn,
160 gl_listelement_hashcode_fn hashcode_fn,
161 gl_listelement_dispose_fn dispose_fn,
162 bool allow_duplicates,
163 size_t count, const void **contents);
165 /* Likewise. Return NULL upon out-of-memory. */
166 extern gl_list_t gl_list_nx_create (gl_list_implementation_t implementation,
167 gl_listelement_equals_fn equals_fn,
168 gl_listelement_hashcode_fn hashcode_fn,
169 gl_listelement_dispose_fn dispose_fn,
170 bool allow_duplicates,
171 size_t count, const void **contents);
173 /* Return the current number of elements in a list. */
174 extern size_t gl_list_size (gl_list_t list);
176 /* Return the element value represented by a list node. */
177 extern const void * gl_list_node_value (gl_list_t list, gl_list_node_t node);
179 /* Replace the element value represented by a list node. */
180 #if 0 /* declared in gl_xlist.h */
181 extern void gl_list_node_set_value (gl_list_t list, gl_list_node_t node,
184 /* Likewise. Return 0 upon success, -1 upon out-of-memory. */
185 extern int gl_list_node_nx_set_value (gl_list_t list, gl_list_node_t node,
187 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
188 __attribute__ ((__warn_unused_result__))
192 /* Return the node immediately after the given node in the list, or NULL
193 if the given node is the last (rightmost) one in the list. */
194 extern gl_list_node_t gl_list_next_node (gl_list_t list, gl_list_node_t node);
196 /* Return the node immediately before the given node in the list, or NULL
197 if the given node is the first (leftmost) one in the list. */
198 extern gl_list_node_t gl_list_previous_node (gl_list_t list, gl_list_node_t node);
200 /* Return the element at a given position in the list.
201 POSITION must be >= 0 and < gl_list_size (list). */
202 extern const void * gl_list_get_at (gl_list_t list, size_t position);
204 /* Replace the element at a given position in the list.
205 POSITION must be >= 0 and < gl_list_size (list).
207 #if 0 /* declared in gl_xlist.h */
208 extern gl_list_node_t gl_list_set_at (gl_list_t list, size_t position,
211 /* Likewise. Return NULL upon out-of-memory. */
212 extern gl_list_node_t gl_list_nx_set_at (gl_list_t list, size_t position,
214 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
215 __attribute__ ((__warn_unused_result__))
219 /* Search whether an element is already in the list.
220 Return its node if found, or NULL if not present in the list. */
221 extern gl_list_node_t gl_list_search (gl_list_t list, const void *elt);
223 /* Search whether an element is already in the list,
224 at a position >= START_INDEX.
225 Return its node if found, or NULL if not present in the list. */
226 extern gl_list_node_t gl_list_search_from (gl_list_t list, size_t start_index,
229 /* Search whether an element is already in the list,
230 at a position >= START_INDEX and < END_INDEX.
231 Return its node if found, or NULL if not present in the list. */
232 extern gl_list_node_t gl_list_search_from_to (gl_list_t list,
237 /* Search whether an element is already in the list.
238 Return its position if found, or (size_t)(-1) if not present in the list. */
239 extern size_t gl_list_indexof (gl_list_t list, const void *elt);
241 /* Search whether an element is already in the list,
242 at a position >= START_INDEX.
243 Return its position if found, or (size_t)(-1) if not present in the list. */
244 extern size_t gl_list_indexof_from (gl_list_t list, size_t start_index,
247 /* Search whether an element is already in the list,
248 at a position >= START_INDEX and < END_INDEX.
249 Return its position if found, or (size_t)(-1) if not present in the list. */
250 extern size_t gl_list_indexof_from_to (gl_list_t list,
251 size_t start_index, size_t end_index,
254 /* Add an element as the first element of the list.
256 #if 0 /* declared in gl_xlist.h */
257 extern gl_list_node_t gl_list_add_first (gl_list_t list, const void *elt);
259 /* Likewise. Return NULL upon out-of-memory. */
260 extern gl_list_node_t gl_list_nx_add_first (gl_list_t list, const void *elt)
261 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
262 __attribute__ ((__warn_unused_result__))
266 /* Add an element as the last element of the list.
268 #if 0 /* declared in gl_xlist.h */
269 extern gl_list_node_t gl_list_add_last (gl_list_t list, const void *elt);
271 /* Likewise. Return NULL upon out-of-memory. */
272 extern gl_list_node_t gl_list_nx_add_last (gl_list_t list, const void *elt)
273 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
274 __attribute__ ((__warn_unused_result__))
278 /* Add an element before a given element node of the list.
280 #if 0 /* declared in gl_xlist.h */
281 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 #if 0 /* declared in gl_xlist.h */
296 extern gl_list_node_t gl_list_add_after (gl_list_t list, gl_list_node_t node,
299 /* Likewise. Return NULL upon out-of-memory. */
300 extern gl_list_node_t gl_list_nx_add_after (gl_list_t list, gl_list_node_t node,
302 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
303 __attribute__ ((__warn_unused_result__))
307 /* Add an element at a given position in the list.
308 POSITION must be >= 0 and <= gl_list_size (list). */
309 #if 0 /* declared in gl_xlist.h */
310 extern gl_list_node_t gl_list_add_at (gl_list_t list, size_t position,
313 /* Likewise. Return NULL upon out-of-memory. */
314 extern gl_list_node_t gl_list_nx_add_at (gl_list_t list, size_t position,
316 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
317 __attribute__ ((__warn_unused_result__))
321 /* Remove an element from the list.
323 extern bool gl_list_remove_node (gl_list_t list, gl_list_node_t node);
325 /* Remove an element at a given position from the list.
326 POSITION must be >= 0 and < gl_list_size (list).
328 extern bool gl_list_remove_at (gl_list_t list, size_t position);
330 /* Search and remove an element from the list.
331 Return true if it was found and removed. */
332 extern bool gl_list_remove (gl_list_t list, const void *elt);
334 /* Free an entire list.
335 (But this call does not free the elements of the list.) */
336 extern void gl_list_free (gl_list_t list);
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 /* Create an iterator traversing a list.
358 The list contents must not be modified while the iterator is in use,
359 except for replacing or removing the last returned element. */
360 extern gl_list_iterator_t gl_list_iterator (gl_list_t list);
362 /* Create an iterator traversing the element with indices i,
363 start_index <= i < end_index, of a list.
364 The list contents must not be modified while the iterator is in use,
365 except for replacing or removing the last returned element. */
366 extern gl_list_iterator_t gl_list_iterator_from_to (gl_list_t list,
370 /* If there is a next element, store the next element in *ELTP, store its
371 node in *NODEP if NODEP is non-NULL, advance the iterator and return true.
372 Otherwise, return false. */
373 extern bool gl_list_iterator_next (gl_list_iterator_t *iterator,
374 const void **eltp, gl_list_node_t *nodep);
376 /* Free an iterator. */
377 extern void gl_list_iterator_free (gl_list_iterator_t *iterator);
379 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
381 /* The following functions are for lists without duplicates where the
382 order is given by a sort criterion. */
384 /* Type of function used to compare two elements. Same as for qsort().
385 NULL denotes pointer comparison. */
386 typedef int (*gl_listelement_compar_fn) (const void *elt1, const void *elt2);
388 /* Search whether an element is already in the list.
389 The list is assumed to be sorted with COMPAR.
390 Return its node if found, or NULL if not present in the list.
391 If the list contains several copies of ELT, the node of the leftmost one is
393 extern gl_list_node_t gl_sortedlist_search (gl_list_t list,
394 gl_listelement_compar_fn compar,
397 /* Search whether an element is already in the list.
398 The list is assumed to be sorted with COMPAR.
399 Only list elements with indices >= START_INDEX and < END_INDEX are
400 considered; the implementation uses these bounds to minimize the number
401 of COMPAR invocations.
402 Return its node if found, or NULL if not present in the list.
403 If the list contains several copies of ELT, the node of the leftmost one is
405 extern gl_list_node_t gl_sortedlist_search_from_to (gl_list_t list,
406 gl_listelement_compar_fn compar,
411 /* Search whether an element is already in the list.
412 The list is assumed to be sorted with COMPAR.
413 Return its position if found, or (size_t)(-1) if not present in the list.
414 If the list contains several copies of ELT, the position of the leftmost one
416 extern size_t gl_sortedlist_indexof (gl_list_t list,
417 gl_listelement_compar_fn compar,
420 /* Search whether an element is already in the list.
421 The list is assumed to be sorted with COMPAR.
422 Only list elements with indices >= START_INDEX and < END_INDEX are
423 considered; the implementation uses these bounds to minimize the number
424 of COMPAR invocations.
425 Return its position if found, or (size_t)(-1) if not present in the list.
426 If the list contains several copies of ELT, the position of the leftmost one
428 extern size_t gl_sortedlist_indexof_from_to (gl_list_t list,
429 gl_listelement_compar_fn compar,
434 /* Add an element at the appropriate position in the list.
435 The list is assumed to be sorted with COMPAR.
437 #if 0 /* declared in gl_xlist.h */
438 extern gl_list_node_t gl_sortedlist_add (gl_list_t list,
439 gl_listelement_compar_fn compar,
442 /* Likewise. Return NULL upon out-of-memory. */
443 extern gl_list_node_t gl_sortedlist_nx_add (gl_list_t list,
444 gl_listelement_compar_fn compar,
446 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
447 __attribute__ ((__warn_unused_result__))
451 /* Search and remove an element from the list.
452 The list is assumed to be sorted with COMPAR.
453 Return true if it was found and removed.
454 If the list contains several copies of ELT, only the leftmost one is
456 extern bool gl_sortedlist_remove (gl_list_t list,
457 gl_listelement_compar_fn compar,
460 /* ------------------------ Implementation Details ------------------------ */
462 struct gl_list_implementation
464 /* gl_list_t functions. */
465 gl_list_t (*nx_create_empty) (gl_list_implementation_t implementation,
466 gl_listelement_equals_fn equals_fn,
467 gl_listelement_hashcode_fn hashcode_fn,
468 gl_listelement_dispose_fn dispose_fn,
469 bool allow_duplicates);
470 gl_list_t (*nx_create) (gl_list_implementation_t implementation,
471 gl_listelement_equals_fn equals_fn,
472 gl_listelement_hashcode_fn hashcode_fn,
473 gl_listelement_dispose_fn dispose_fn,
474 bool allow_duplicates,
475 size_t count, const void **contents);
476 size_t (*size) (gl_list_t list);
477 const void * (*node_value) (gl_list_t list, gl_list_node_t node);
478 int (*node_nx_set_value) (gl_list_t list, gl_list_node_t node,
480 gl_list_node_t (*next_node) (gl_list_t list, gl_list_node_t node);
481 gl_list_node_t (*previous_node) (gl_list_t list, gl_list_node_t node);
482 const void * (*get_at) (gl_list_t list, size_t position);
483 gl_list_node_t (*nx_set_at) (gl_list_t list, size_t position,
485 gl_list_node_t (*search_from_to) (gl_list_t list, size_t start_index,
486 size_t end_index, const void *elt);
487 size_t (*indexof_from_to) (gl_list_t list, size_t start_index,
488 size_t end_index, const void *elt);
489 gl_list_node_t (*nx_add_first) (gl_list_t list, const void *elt);
490 gl_list_node_t (*nx_add_last) (gl_list_t list, const void *elt);
491 gl_list_node_t (*nx_add_before) (gl_list_t list, gl_list_node_t node,
493 gl_list_node_t (*nx_add_after) (gl_list_t list, gl_list_node_t node,
495 gl_list_node_t (*nx_add_at) (gl_list_t list, size_t position,
497 bool (*remove_node) (gl_list_t list, gl_list_node_t node);
498 bool (*remove_at) (gl_list_t list, size_t position);
499 bool (*remove_elt) (gl_list_t list, const void *elt);
500 void (*list_free) (gl_list_t list);
501 /* gl_list_iterator_t functions. */
502 gl_list_iterator_t (*iterator) (gl_list_t list);
503 gl_list_iterator_t (*iterator_from_to) (gl_list_t list,
506 bool (*iterator_next) (gl_list_iterator_t *iterator,
507 const void **eltp, gl_list_node_t *nodep);
508 void (*iterator_free) (gl_list_iterator_t *iterator);
509 /* Sorted gl_list_t functions. */
510 gl_list_node_t (*sortedlist_search) (gl_list_t list,
511 gl_listelement_compar_fn compar,
513 gl_list_node_t (*sortedlist_search_from_to) (gl_list_t list,
514 gl_listelement_compar_fn compar,
518 size_t (*sortedlist_indexof) (gl_list_t list,
519 gl_listelement_compar_fn compar,
521 size_t (*sortedlist_indexof_from_to) (gl_list_t list,
522 gl_listelement_compar_fn compar,
523 size_t start_index, size_t end_index,
525 gl_list_node_t (*sortedlist_nx_add) (gl_list_t list,
526 gl_listelement_compar_fn compar,
528 bool (*sortedlist_remove) (gl_list_t list,
529 gl_listelement_compar_fn compar,
533 struct gl_list_impl_base
535 const struct gl_list_implementation *vtable;
536 gl_listelement_equals_fn equals_fn;
537 gl_listelement_hashcode_fn hashcode_fn;
538 gl_listelement_dispose_fn dispose_fn;
539 bool allow_duplicates;
544 /* Define all functions of this file as inline accesses to the
545 struct gl_list_implementation.
546 Use #define to avoid a warning because of extern vs. static. */
548 # define gl_list_nx_create_empty gl_list_nx_create_empty_inline
549 static inline gl_list_t
550 gl_list_nx_create_empty (gl_list_implementation_t implementation,
551 gl_listelement_equals_fn equals_fn,
552 gl_listelement_hashcode_fn hashcode_fn,
553 gl_listelement_dispose_fn dispose_fn,
554 bool allow_duplicates)
556 return implementation->nx_create_empty (implementation, equals_fn,
557 hashcode_fn, dispose_fn,
561 # define gl_list_nx_create gl_list_nx_create_inline
562 static inline gl_list_t
563 gl_list_nx_create (gl_list_implementation_t implementation,
564 gl_listelement_equals_fn equals_fn,
565 gl_listelement_hashcode_fn hashcode_fn,
566 gl_listelement_dispose_fn dispose_fn,
567 bool allow_duplicates,
568 size_t count, const void **contents)
570 return implementation->nx_create (implementation, equals_fn, hashcode_fn,
571 dispose_fn, allow_duplicates, count,
575 # define gl_list_size gl_list_size_inline
577 gl_list_size (gl_list_t list)
579 return ((const struct gl_list_impl_base *) list)->vtable
583 # define gl_list_node_value gl_list_node_value_inline
584 static 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);
591 # define gl_list_node_nx_set_value gl_list_node_nx_set_value_inline
593 gl_list_node_nx_set_value (gl_list_t list, gl_list_node_t node,
596 return ((const struct gl_list_impl_base *) list)->vtable
597 ->node_nx_set_value (list, node, elt);
600 # define gl_list_next_node gl_list_next_node_inline
601 static inline gl_list_node_t
602 gl_list_next_node (gl_list_t list, gl_list_node_t node)
604 return ((const struct gl_list_impl_base *) list)->vtable
605 ->next_node (list, node);
608 # define gl_list_previous_node gl_list_previous_node_inline
609 static 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 # define gl_list_get_at gl_list_get_at_inline
617 static inline const void *
618 gl_list_get_at (gl_list_t list, size_t position)
620 return ((const struct gl_list_impl_base *) list)->vtable
621 ->get_at (list, position);
624 # define gl_list_nx_set_at gl_list_nx_set_at_inline
625 static inline gl_list_node_t
626 gl_list_nx_set_at (gl_list_t list, size_t position, const void *elt)
628 return ((const struct gl_list_impl_base *) list)->vtable
629 ->nx_set_at (list, position, elt);
632 # define gl_list_search gl_list_search_inline
633 static 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 # define gl_list_search_from gl_list_search_from_inline
642 static inline gl_list_node_t
643 gl_list_search_from (gl_list_t list, size_t start_index, const void *elt)
645 size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
646 return ((const struct gl_list_impl_base *) list)->vtable
647 ->search_from_to (list, start_index, size, elt);
650 # define gl_list_search_from_to gl_list_search_from_to_inline
651 static inline gl_list_node_t
652 gl_list_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
655 return ((const struct gl_list_impl_base *) list)->vtable
656 ->search_from_to (list, start_index, end_index, elt);
659 # define gl_list_indexof gl_list_indexof_inline
661 gl_list_indexof (gl_list_t list, const void *elt)
663 size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
664 return ((const struct gl_list_impl_base *) list)->vtable
665 ->indexof_from_to (list, 0, size, elt);
668 # define gl_list_indexof_from gl_list_indexof_from_inline
670 gl_list_indexof_from (gl_list_t list, size_t start_index, const void *elt)
672 size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
673 return ((const struct gl_list_impl_base *) list)->vtable
674 ->indexof_from_to (list, start_index, size, elt);
677 # define gl_list_indexof_from_to gl_list_indexof_from_to_inline
679 gl_list_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
682 return ((const struct gl_list_impl_base *) list)->vtable
683 ->indexof_from_to (list, start_index, end_index, elt);
686 # define gl_list_nx_add_first gl_list_nx_add_first_inline
687 static inline gl_list_node_t
688 gl_list_nx_add_first (gl_list_t list, const void *elt)
690 return ((const struct gl_list_impl_base *) list)->vtable
691 ->nx_add_first (list, elt);
694 # define gl_list_nx_add_last gl_list_nx_add_last_inline
695 static inline gl_list_node_t
696 gl_list_nx_add_last (gl_list_t list, const void *elt)
698 return ((const struct gl_list_impl_base *) list)->vtable
699 ->nx_add_last (list, elt);
702 # define gl_list_nx_add_before gl_list_nx_add_before_inline
703 static inline gl_list_node_t
704 gl_list_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
706 return ((const struct gl_list_impl_base *) list)->vtable
707 ->nx_add_before (list, node, elt);
710 # define gl_list_nx_add_after gl_list_nx_add_after_inline
711 static inline gl_list_node_t
712 gl_list_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
714 return ((const struct gl_list_impl_base *) list)->vtable
715 ->nx_add_after (list, node, elt);
718 # define gl_list_nx_add_at gl_list_nx_add_at_inline
719 static inline gl_list_node_t
720 gl_list_nx_add_at (gl_list_t list, size_t position, const void *elt)
722 return ((const struct gl_list_impl_base *) list)->vtable
723 ->nx_add_at (list, position, elt);
726 # define gl_list_remove_node gl_list_remove_node_inline
728 gl_list_remove_node (gl_list_t list, gl_list_node_t node)
730 return ((const struct gl_list_impl_base *) list)->vtable
731 ->remove_node (list, node);
734 # define gl_list_remove_at gl_list_remove_at_inline
736 gl_list_remove_at (gl_list_t list, size_t position)
738 return ((const struct gl_list_impl_base *) list)->vtable
739 ->remove_at (list, position);
742 # define gl_list_remove gl_list_remove_inline
744 gl_list_remove (gl_list_t list, const void *elt)
746 return ((const struct gl_list_impl_base *) list)->vtable
747 ->remove_elt (list, elt);
750 # define gl_list_free gl_list_free_inline
752 gl_list_free (gl_list_t list)
754 ((const struct gl_list_impl_base *) list)->vtable->list_free (list);
757 # define gl_list_iterator gl_list_iterator_inline
758 static inline gl_list_iterator_t
759 gl_list_iterator (gl_list_t list)
761 return ((const struct gl_list_impl_base *) list)->vtable
765 # define gl_list_iterator_from_to gl_list_iterator_from_to_inline
766 static inline gl_list_iterator_t
767 gl_list_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
769 return ((const struct gl_list_impl_base *) list)->vtable
770 ->iterator_from_to (list, start_index, end_index);
773 # define gl_list_iterator_next gl_list_iterator_next_inline
775 gl_list_iterator_next (gl_list_iterator_t *iterator,
776 const void **eltp, gl_list_node_t *nodep)
778 return iterator->vtable->iterator_next (iterator, eltp, nodep);
781 # define gl_list_iterator_free gl_list_iterator_free_inline
783 gl_list_iterator_free (gl_list_iterator_t *iterator)
785 iterator->vtable->iterator_free (iterator);
788 # define gl_sortedlist_search gl_sortedlist_search_inline
789 static inline gl_list_node_t
790 gl_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
792 return ((const struct gl_list_impl_base *) list)->vtable
793 ->sortedlist_search (list, compar, elt);
796 # define gl_sortedlist_search_from_to gl_sortedlist_search_from_to_inline
797 static inline gl_list_node_t
798 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)
800 return ((const struct gl_list_impl_base *) list)->vtable
801 ->sortedlist_search_from_to (list, compar, start_index, end_index,
805 # define gl_sortedlist_indexof gl_sortedlist_indexof_inline
807 gl_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
809 return ((const struct gl_list_impl_base *) list)->vtable
810 ->sortedlist_indexof (list, compar, elt);
813 # define gl_sortedlist_indexof_from_to gl_sortedlist_indexof_from_to_inline
815 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)
817 return ((const struct gl_list_impl_base *) list)->vtable
818 ->sortedlist_indexof_from_to (list, compar, start_index, end_index,
822 # define gl_sortedlist_nx_add gl_sortedlist_nx_add_inline
823 static inline gl_list_node_t
824 gl_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
826 return ((const struct gl_list_impl_base *) list)->vtable
827 ->sortedlist_nx_add (list, compar, elt);
830 # define gl_sortedlist_remove gl_sortedlist_remove_inline
832 gl_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
834 return ((const struct gl_list_impl_base *) list)->vtable
835 ->sortedlist_remove (list, compar, elt);
844 #endif /* _GL_LIST_H */