1 /* Abstract sequential list data type. -*- coding: utf-8 -*-
2 Copyright (C) 2006-2021 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 <https://www.gnu.org/licenses/>. */
24 #ifndef _GL_INLINE_HEADER_BEGIN
25 #error "Please include config.h first."
27 _GL_INLINE_HEADER_BEGIN
28 #ifndef GL_LIST_INLINE
29 # define GL_LIST_INLINE _GL_INLINE
37 /* gl_list is an abstract list data type. It can contain any number of
38 objects ('void *' or 'const void *' pointers) in any given order.
39 Duplicates are allowed, but can optionally be forbidden.
41 There are several implementations of this list datatype, optimized for
42 different operations or for memory. You can start using the simplest list
43 implementation, GL_ARRAY_LIST, and switch to a different implementation
44 later, when you realize which operations are performed the most frequently.
45 The API of the different implementations is exactly the same; when
46 switching to a different implementation, you only have to change the
49 The implementations are:
50 GL_ARRAY_LIST a growable array
51 GL_CARRAY_LIST a growable circular array
52 GL_LINKED_LIST a linked list
53 GL_AVLTREE_LIST a binary tree (AVL tree)
54 GL_RBTREE_LIST a binary tree (red-black tree)
55 GL_LINKEDHASH_LIST a hash table with a linked list
56 GL_AVLTREEHASH_LIST a hash table with a binary tree (AVL tree)
57 GL_RBTREEHASH_LIST a hash table with a binary tree (red-black tree)
59 The memory consumption is asymptotically the same: O(1) for every object
60 in the list. When looking more closely at the average memory consumed
61 for an object, GL_ARRAY_LIST is the most compact representation, and
62 GL_LINKEDHASH_LIST and GL_TREEHASH_LIST need more memory.
64 The guaranteed average performance of the operations is, for a list of
67 Operation ARRAY LINKED TREE LINKEDHASH TREEHASH
68 CARRAY with|without with|without
71 gl_list_size O(1) O(1) O(1) O(1) O(1)
72 gl_list_node_value O(1) O(1) O(1) O(1) O(1)
73 gl_list_node_set_value O(1) O(1) O(1) O(1) O((log n)²)/O(1)
74 gl_list_next_node O(1) O(1) O(log n) O(1) O(log n)
75 gl_list_previous_node O(1) O(1) O(log n) O(1) O(log n)
76 gl_list_first_node O(1) O(1) O(log n) O(1) O(log n)
77 gl_list_last_node O(1) O(1) O(log n) O(1) O(log n)
78 gl_list_get_at O(1) O(n) O(log n) O(n) O(log n)
79 gl_list_get_first O(1) O(1) O(log n) O(1) O(log n)
80 gl_list_get_last O(1) O(1) O(log n) O(1) O(log n)
81 gl_list_set_at O(1) O(n) O(log n) O(n) O((log n)²)/O(log n)
82 gl_list_set_first O(1) O(1) O(log n) O(n)/O(1) O((log n)²)/O(log n)
83 gl_list_set_last O(1) O(1) O(log n) O(n)/O(1) O((log n)²)/O(log n)
84 gl_list_search O(n) O(n) O(n) O(n)/O(1) O(log n)/O(1)
85 gl_list_search_from O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n)
86 gl_list_search_from_to O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n)
87 gl_list_indexof O(n) O(n) O(n) O(n) O(log n)
88 gl_list_indexof_from O(n) O(n) O(n) O(n) O((log n)²)/O(log n)
89 gl_list_indexof_from_to O(n) O(n) O(n) O(n) O((log n)²)/O(log n)
90 gl_list_add_first O(n)/O(1) O(1) O(log n) O(1) O((log n)²)/O(log n)
91 gl_list_add_last O(1) O(1) O(log n) O(1) O((log n)²)/O(log n)
92 gl_list_add_before O(n) O(1) O(log n) O(1) O((log n)²)/O(log n)
93 gl_list_add_after O(n) O(1) O(log n) O(1) O((log n)²)/O(log n)
94 gl_list_add_at O(n) O(n) O(log n) O(n) O((log n)²)/O(log n)
95 gl_list_remove_node O(n) O(1) O(log n) O(n)/O(1) O((log n)²)/O(log n)
96 gl_list_remove_at O(n) O(n) O(log n) O(n) O((log n)²)/O(log n)
97 gl_list_remove_first O(n)/O(1) O(1) O(log n) O(n)/O(1) O((log n)²)/O(log n)
98 gl_list_remove_last O(1) O(1) O(log n) O(n)/O(1) O((log n)²)/O(log n)
99 gl_list_remove O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n)
100 gl_list_iterator O(1) O(1) O(log n) O(1) O(log n)
101 gl_list_iterator_from_to O(1) O(n) O(log n) O(n) O(log n)
102 gl_list_iterator_next O(1) O(1) O(log n) O(1) O(log n)
103 gl_sortedlist_search O(log n) O(n) O(log n) O(n) O(log n)
104 gl_sortedlist_search_from O(log n) O(n) O(log n) O(n) O(log n)
105 gl_sortedlist_indexof O(log n) O(n) O(log n) O(n) O(log n)
106 gl_sortedlist_indexof_fro O(log n) O(n) O(log n) O(n) O(log n)
107 gl_sortedlist_add O(n) O(n) O(log n) O(n) O((log n)²)/O(log n)
108 gl_sortedlist_remove O(n) O(n) O(log n) O(n) O((log n)²)/O(log n)
111 /* -------------------------- gl_list_t Data Type -------------------------- */
113 /* Type of function used to compare two elements.
114 NULL denotes pointer comparison. */
115 typedef bool (*gl_listelement_equals_fn) (const void *elt1, const void *elt2);
117 /* Type of function used to compute a hash code.
118 NULL denotes a function that depends only on the pointer itself. */
119 typedef size_t (*gl_listelement_hashcode_fn) (const void *elt);
121 /* Type of function used to dispose an element once it's removed from a list.
122 NULL denotes a no-op. */
123 typedef void (*gl_listelement_dispose_fn) (const void *elt);
126 /* Type representing an entire list. */
127 typedef struct gl_list_impl * gl_list_t;
129 struct gl_list_node_impl;
130 /* Type representing the position of an element in the list, in a way that
131 is more adapted to the list implementation than a plain index.
132 Note: It is invalidated by insertions and removals! */
133 typedef struct gl_list_node_impl * gl_list_node_t;
135 struct gl_list_implementation;
136 /* Type representing a list datatype implementation. */
137 typedef const struct gl_list_implementation * gl_list_implementation_t;
139 #if 0 /* Unless otherwise specified, these are defined inline below. */
141 /* Creates an empty list.
142 IMPLEMENTATION is one of GL_ARRAY_LIST, GL_CARRAY_LIST, GL_LINKED_LIST,
143 GL_AVLTREE_LIST, GL_RBTREE_LIST, GL_LINKEDHASH_LIST, GL_AVLTREEHASH_LIST,
145 EQUALS_FN is an element comparison function or NULL.
146 HASHCODE_FN is an element hash code function or NULL.
147 DISPOSE_FN is an element disposal function or NULL.
148 ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in
149 the list. The implementation may verify this at runtime. */
150 /* declared in gl_xlist.h */
151 extern gl_list_t gl_list_create_empty (gl_list_implementation_t implementation,
152 gl_listelement_equals_fn equals_fn,
153 gl_listelement_hashcode_fn hashcode_fn,
154 gl_listelement_dispose_fn dispose_fn,
155 bool allow_duplicates);
156 /* Likewise. Returns NULL upon out-of-memory. */
157 extern gl_list_t gl_list_nx_create_empty (gl_list_implementation_t implementation,
158 gl_listelement_equals_fn equals_fn,
159 gl_listelement_hashcode_fn hashcode_fn,
160 gl_listelement_dispose_fn dispose_fn,
161 bool allow_duplicates);
163 /* Creates a list with given contents.
164 IMPLEMENTATION is one of GL_ARRAY_LIST, GL_CARRAY_LIST, GL_LINKED_LIST,
165 GL_AVLTREE_LIST, GL_RBTREE_LIST, GL_LINKEDHASH_LIST, GL_AVLTREEHASH_LIST,
167 EQUALS_FN is an element comparison function or NULL.
168 HASHCODE_FN is an element hash code function or NULL.
169 DISPOSE_FN is an element disposal function or NULL.
170 ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in
171 the list. The implementation may verify this at runtime.
172 COUNT is the number of initial elements.
173 CONTENTS[0..COUNT-1] is the initial contents. */
174 /* declared in gl_xlist.h */
175 extern gl_list_t gl_list_create (gl_list_implementation_t implementation,
176 gl_listelement_equals_fn equals_fn,
177 gl_listelement_hashcode_fn hashcode_fn,
178 gl_listelement_dispose_fn dispose_fn,
179 bool allow_duplicates,
180 size_t count, const void **contents);
181 /* Likewise. Returns NULL upon out-of-memory. */
182 extern gl_list_t gl_list_nx_create (gl_list_implementation_t implementation,
183 gl_listelement_equals_fn equals_fn,
184 gl_listelement_hashcode_fn hashcode_fn,
185 gl_listelement_dispose_fn dispose_fn,
186 bool allow_duplicates,
187 size_t count, const void **contents);
189 /* Returns the current number of elements in a list. */
190 extern size_t gl_list_size (gl_list_t list);
192 /* Returns the element value represented by a list node. */
193 extern const void * gl_list_node_value (gl_list_t list, gl_list_node_t node);
195 /* Replaces the element value represented by a list node. */
196 /* declared in gl_xlist.h */
197 extern void gl_list_node_set_value (gl_list_t list, gl_list_node_t node,
199 /* Likewise. Returns 0 upon success, -1 upon out-of-memory. */
200 extern int gl_list_node_nx_set_value (gl_list_t list, gl_list_node_t node,
202 _GL_ATTRIBUTE_NODISCARD;
204 /* Returns the node immediately after the given node in the list, or NULL
205 if the given node is the last (rightmost) one in the list. */
206 extern gl_list_node_t gl_list_next_node (gl_list_t list, gl_list_node_t node);
208 /* Returns the node immediately before the given node in the list, or NULL
209 if the given node is the first (leftmost) one in the list. */
210 extern gl_list_node_t gl_list_previous_node (gl_list_t list, gl_list_node_t node);
212 /* Returns the first node in the list, or NULL if the list is empty.
213 This function is useful for iterating through the list like this:
215 for (node = gl_list_first_node (list); node != NULL; node = gl_list_next_node (node))
218 extern gl_list_node_t gl_list_first_node (gl_list_t list);
220 /* Returns the last node in the list, or NULL if the list is empty.
221 This function is useful for iterating through the list in backward order,
224 for (node = gl_list_last_node (list); node != NULL; node = gl_list_previous_node (node))
227 extern gl_list_node_t gl_list_last_node (gl_list_t list);
229 /* Returns the element at a given position in the list.
230 POSITION must be >= 0 and < gl_list_size (list). */
231 extern const void * gl_list_get_at (gl_list_t list, size_t position);
233 /* Returns the element at the first position in the list.
234 The list must be non-empty. */
235 extern const void * gl_list_get_first (gl_list_t list);
237 /* Returns the element at the last position in the list.
238 The list must be non-empty. */
239 extern const void * gl_list_get_last (gl_list_t list);
241 /* Replaces the element at a given position in the list.
242 POSITION must be >= 0 and < gl_list_size (list).
244 /* declared in gl_xlist.h */
245 extern gl_list_node_t gl_list_set_at (gl_list_t list, size_t position,
247 /* Likewise. Returns NULL upon out-of-memory. */
248 extern gl_list_node_t gl_list_nx_set_at (gl_list_t list, size_t position,
250 _GL_ATTRIBUTE_NODISCARD;
252 /* Replaces the element at the first position in the list.
254 The list must be non-empty. */
255 /* declared in gl_xlist.h */
256 extern gl_list_node_t gl_list_set_first (gl_list_t list, const void *elt);
257 /* Likewise. Returns NULL upon out-of-memory. */
258 extern gl_list_node_t gl_list_nx_set_first (gl_list_t list, const void *elt)
259 _GL_ATTRIBUTE_NODISCARD;
261 /* Replaces the element at the last position in the list.
263 The list must be non-empty. */
264 /* declared in gl_xlist.h */
265 extern gl_list_node_t gl_list_set_last (gl_list_t list, const void *elt);
266 /* Likewise. Returns NULL upon out-of-memory. */
267 extern gl_list_node_t gl_list_nx_set_last (gl_list_t list, const void *elt)
268 _GL_ATTRIBUTE_NODISCARD;
270 /* Searches whether an element is already in the list.
271 Returns its node if found, or NULL if not present in the list. */
272 extern gl_list_node_t gl_list_search (gl_list_t list, const void *elt);
274 /* Searches whether an element is already in the list,
275 at a position >= START_INDEX.
276 Returns its node if found, or NULL if not present in the list. */
277 extern gl_list_node_t gl_list_search_from (gl_list_t list, size_t start_index,
280 /* Searches whether an element is already in the list,
281 at a position >= START_INDEX and < END_INDEX.
282 Returns its node if found, or NULL if not present in the list. */
283 extern gl_list_node_t gl_list_search_from_to (gl_list_t list,
288 /* Searches whether an element is already in the list.
289 Returns its position if found, or (size_t)(-1) if not present in the list. */
290 extern size_t gl_list_indexof (gl_list_t list, const void *elt);
292 /* Searches whether an element is already in the list,
293 at a position >= START_INDEX.
294 Returns its position if found, or (size_t)(-1) if not present in the list. */
295 extern size_t gl_list_indexof_from (gl_list_t list, size_t start_index,
298 /* Searches whether an element is already in the list,
299 at a position >= START_INDEX and < END_INDEX.
300 Returns its position if found, or (size_t)(-1) if not present in the list. */
301 extern size_t gl_list_indexof_from_to (gl_list_t list,
302 size_t start_index, size_t end_index,
305 /* Adds an element as the first element of the list.
307 /* declared in gl_xlist.h */
308 extern gl_list_node_t gl_list_add_first (gl_list_t list, const void *elt);
309 /* Likewise. Returns NULL upon out-of-memory. */
310 extern gl_list_node_t gl_list_nx_add_first (gl_list_t list, const void *elt)
311 _GL_ATTRIBUTE_NODISCARD;
313 /* Adds an element as the last element of the list.
315 /* declared in gl_xlist.h */
316 extern gl_list_node_t gl_list_add_last (gl_list_t list, const void *elt);
317 /* Likewise. Returns NULL upon out-of-memory. */
318 extern gl_list_node_t gl_list_nx_add_last (gl_list_t list, const void *elt)
319 _GL_ATTRIBUTE_NODISCARD;
321 /* Adds an element before a given element node of the list.
323 /* declared in gl_xlist.h */
324 extern gl_list_node_t gl_list_add_before (gl_list_t list, gl_list_node_t node,
326 /* Likewise. Returns NULL upon out-of-memory. */
327 extern gl_list_node_t gl_list_nx_add_before (gl_list_t list,
330 _GL_ATTRIBUTE_NODISCARD;
332 /* Adds an element after a given element node of the list.
334 /* declared in gl_xlist.h */
335 extern gl_list_node_t gl_list_add_after (gl_list_t list, gl_list_node_t node,
337 /* Likewise. Returns NULL upon out-of-memory. */
338 extern gl_list_node_t gl_list_nx_add_after (gl_list_t list, gl_list_node_t node,
340 _GL_ATTRIBUTE_NODISCARD;
342 /* Adds an element at a given position in the list.
343 POSITION must be >= 0 and <= gl_list_size (list). */
344 /* declared in gl_xlist.h */
345 extern gl_list_node_t gl_list_add_at (gl_list_t list, size_t position,
347 /* Likewise. Returns NULL upon out-of-memory. */
348 extern gl_list_node_t gl_list_nx_add_at (gl_list_t list, size_t position,
350 _GL_ATTRIBUTE_NODISCARD;
352 /* Removes an element from the list.
354 extern bool gl_list_remove_node (gl_list_t list, gl_list_node_t node);
356 /* Removes an element at a given position from the list.
357 POSITION must be >= 0 and < gl_list_size (list).
359 extern bool gl_list_remove_at (gl_list_t list, size_t position);
361 /* Removes the element at the first position from the list.
362 Returns true if it was found and removed, or false if the list was empty. */
363 extern bool gl_list_remove_first (gl_list_t list);
365 /* Removes the element at the last position from the list.
366 Returns true if it was found and removed, or false if the list was empty. */
367 extern bool gl_list_remove_last (gl_list_t list);
369 /* Searches and removes an element from the list.
370 Returns true if it was found and removed. */
371 extern bool gl_list_remove (gl_list_t list, const void *elt);
373 /* Frees an entire list.
374 (But this call does not free the elements of the list. It only invokes
375 the DISPOSE_FN on each of the elements of the list, and only if the list
376 is not a sublist.) */
377 extern void gl_list_free (gl_list_t list);
379 #endif /* End of inline and gl_xlist.h-defined functions. */
381 /* --------------------- gl_list_iterator_t Data Type --------------------- */
383 /* Functions for iterating through a list. */
385 /* Type of an iterator that traverses a list.
386 This is a fixed-size struct, so that creation of an iterator doesn't need
387 memory allocation on the heap. */
390 /* For fast dispatch of gl_list_iterator_next. */
391 const struct gl_list_implementation *vtable;
392 /* For detecting whether the last returned element was removed. */
395 /* Other, implementation-private fields. */
398 } gl_list_iterator_t;
400 #if 0 /* These are defined inline below. */
402 /* Creates an iterator traversing a list.
403 The list contents must not be modified while the iterator is in use,
404 except for replacing or removing the last returned element. */
405 extern gl_list_iterator_t gl_list_iterator (gl_list_t list);
407 /* Creates an iterator traversing the element with indices i,
408 start_index <= i < end_index, of a list.
409 The list contents must not be modified while the iterator is in use,
410 except for replacing or removing the last returned element. */
411 extern gl_list_iterator_t gl_list_iterator_from_to (gl_list_t list,
415 /* If there is a next element, stores the next element in *ELTP, stores its
416 node in *NODEP if NODEP is non-NULL, advances the iterator and returns true.
417 Otherwise, returns false. */
418 extern bool gl_list_iterator_next (gl_list_iterator_t *iterator,
419 const void **eltp, gl_list_node_t *nodep);
421 /* Frees an iterator. */
422 extern void gl_list_iterator_free (gl_list_iterator_t *iterator);
424 #endif /* End of inline functions. */
426 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
428 /* The following functions are for lists without duplicates where the
429 order is given by a sort criterion. */
431 /* Type of function used to compare two elements. Same as for qsort().
432 NULL denotes pointer comparison. */
433 typedef int (*gl_listelement_compar_fn) (const void *elt1, const void *elt2);
435 #if 0 /* Unless otherwise specified, these are defined inline below. */
437 /* Searches whether an element is already in the list.
438 The list is assumed to be sorted with COMPAR.
439 Returns its node if found, or NULL if not present in the list.
440 If the list contains several copies of ELT, the node of the leftmost one is
442 extern gl_list_node_t gl_sortedlist_search (gl_list_t list,
443 gl_listelement_compar_fn compar,
446 /* Searches whether an element is already in the list.
447 The list is assumed to be sorted with COMPAR.
448 Only list elements with indices >= START_INDEX and < END_INDEX are
449 considered; the implementation uses these bounds to minimize the number
450 of COMPAR invocations.
451 Returns its node if found, or NULL if not present in the list.
452 If the list contains several copies of ELT, the node of the leftmost one is
454 extern gl_list_node_t gl_sortedlist_search_from_to (gl_list_t list,
455 gl_listelement_compar_fn compar,
460 /* Searches whether an element is already in the list.
461 The list is assumed to be sorted with COMPAR.
462 Returns its position if found, or (size_t)(-1) if not present in the list.
463 If the list contains several copies of ELT, the position of the leftmost one
465 extern size_t gl_sortedlist_indexof (gl_list_t list,
466 gl_listelement_compar_fn compar,
469 /* Searches whether an element is already in the list.
470 The list is assumed to be sorted with COMPAR.
471 Only list elements with indices >= START_INDEX and < END_INDEX are
472 considered; the implementation uses these bounds to minimize the number
473 of COMPAR invocations.
474 Returns its position if found, or (size_t)(-1) if not present in the list.
475 If the list contains several copies of ELT, the position of the leftmost one
477 extern size_t gl_sortedlist_indexof_from_to (gl_list_t list,
478 gl_listelement_compar_fn compar,
483 /* Adds an element at the appropriate position in the list.
484 The list is assumed to be sorted with COMPAR.
486 /* declared in gl_xlist.h */
487 extern gl_list_node_t gl_sortedlist_add (gl_list_t list,
488 gl_listelement_compar_fn compar,
490 /* Likewise. Returns NULL upon out-of-memory. */
491 extern gl_list_node_t gl_sortedlist_nx_add (gl_list_t list,
492 gl_listelement_compar_fn compar,
494 _GL_ATTRIBUTE_NODISCARD;
496 /* Searches and removes an element from the list.
497 The list is assumed to be sorted with COMPAR.
498 Returns true if it was found and removed.
499 If the list contains several copies of ELT, only the leftmost one is
501 extern bool gl_sortedlist_remove (gl_list_t list,
502 gl_listelement_compar_fn compar,
505 #endif /* End of inline and gl_xlist.h-defined functions. */
507 /* ------------------------ Implementation Details ------------------------ */
509 struct gl_list_implementation
511 /* gl_list_t functions. */
512 gl_list_t (*nx_create_empty) (gl_list_implementation_t implementation,
513 gl_listelement_equals_fn equals_fn,
514 gl_listelement_hashcode_fn hashcode_fn,
515 gl_listelement_dispose_fn dispose_fn,
516 bool allow_duplicates);
517 gl_list_t (*nx_create) (gl_list_implementation_t implementation,
518 gl_listelement_equals_fn equals_fn,
519 gl_listelement_hashcode_fn hashcode_fn,
520 gl_listelement_dispose_fn dispose_fn,
521 bool allow_duplicates,
522 size_t count, const void **contents);
523 size_t (*size) (gl_list_t list);
524 const void * (*node_value) (gl_list_t list, gl_list_node_t node);
525 int (*node_nx_set_value) (gl_list_t list, gl_list_node_t node,
527 gl_list_node_t (*next_node) (gl_list_t list, gl_list_node_t node);
528 gl_list_node_t (*previous_node) (gl_list_t list, gl_list_node_t node);
529 gl_list_node_t (*first_node) (gl_list_t list);
530 gl_list_node_t (*last_node) (gl_list_t list);
531 const void * (*get_at) (gl_list_t list, size_t position);
532 gl_list_node_t (*nx_set_at) (gl_list_t list, size_t position,
534 gl_list_node_t (*search_from_to) (gl_list_t list, size_t start_index,
535 size_t end_index, const void *elt);
536 size_t (*indexof_from_to) (gl_list_t list, size_t start_index,
537 size_t end_index, const void *elt);
538 gl_list_node_t (*nx_add_first) (gl_list_t list, const void *elt);
539 gl_list_node_t (*nx_add_last) (gl_list_t list, const void *elt);
540 gl_list_node_t (*nx_add_before) (gl_list_t list, gl_list_node_t node,
542 gl_list_node_t (*nx_add_after) (gl_list_t list, gl_list_node_t node,
544 gl_list_node_t (*nx_add_at) (gl_list_t list, size_t position,
546 bool (*remove_node) (gl_list_t list, gl_list_node_t node);
547 bool (*remove_at) (gl_list_t list, size_t position);
548 bool (*remove_elt) (gl_list_t list, const void *elt);
549 void (*list_free) (gl_list_t list);
550 /* gl_list_iterator_t functions. */
551 gl_list_iterator_t (*iterator) (gl_list_t list);
552 gl_list_iterator_t (*iterator_from_to) (gl_list_t list,
555 bool (*iterator_next) (gl_list_iterator_t *iterator,
556 const void **eltp, gl_list_node_t *nodep);
557 void (*iterator_free) (gl_list_iterator_t *iterator);
558 /* Sorted gl_list_t functions. */
559 gl_list_node_t (*sortedlist_search) (gl_list_t list,
560 gl_listelement_compar_fn compar,
562 gl_list_node_t (*sortedlist_search_from_to) (gl_list_t list,
563 gl_listelement_compar_fn compar,
567 size_t (*sortedlist_indexof) (gl_list_t list,
568 gl_listelement_compar_fn compar,
570 size_t (*sortedlist_indexof_from_to) (gl_list_t list,
571 gl_listelement_compar_fn compar,
572 size_t start_index, size_t end_index,
574 gl_list_node_t (*sortedlist_nx_add) (gl_list_t list,
575 gl_listelement_compar_fn compar,
577 bool (*sortedlist_remove) (gl_list_t list,
578 gl_listelement_compar_fn compar,
582 struct gl_list_impl_base
584 const struct gl_list_implementation *vtable;
585 gl_listelement_equals_fn equals_fn;
586 gl_listelement_hashcode_fn hashcode_fn;
587 gl_listelement_dispose_fn dispose_fn;
588 bool allow_duplicates;
591 /* Define all functions of this file as accesses to the
592 struct gl_list_implementation. */
594 GL_LIST_INLINE gl_list_t
595 gl_list_nx_create_empty (gl_list_implementation_t implementation,
596 gl_listelement_equals_fn equals_fn,
597 gl_listelement_hashcode_fn hashcode_fn,
598 gl_listelement_dispose_fn dispose_fn,
599 bool allow_duplicates)
601 return implementation->nx_create_empty (implementation, equals_fn,
602 hashcode_fn, dispose_fn,
606 GL_LIST_INLINE gl_list_t
607 gl_list_nx_create (gl_list_implementation_t implementation,
608 gl_listelement_equals_fn equals_fn,
609 gl_listelement_hashcode_fn hashcode_fn,
610 gl_listelement_dispose_fn dispose_fn,
611 bool allow_duplicates,
612 size_t count, const void **contents)
614 return implementation->nx_create (implementation, equals_fn, hashcode_fn,
615 dispose_fn, allow_duplicates, count,
619 GL_LIST_INLINE size_t
620 gl_list_size (gl_list_t list)
622 return ((const struct gl_list_impl_base *) list)->vtable
626 GL_LIST_INLINE const void *
627 gl_list_node_value (gl_list_t list, gl_list_node_t node)
629 return ((const struct gl_list_impl_base *) list)->vtable
630 ->node_value (list, node);
633 GL_LIST_INLINE _GL_ATTRIBUTE_NODISCARD int
634 gl_list_node_nx_set_value (gl_list_t list, gl_list_node_t node,
637 return ((const struct gl_list_impl_base *) list)->vtable
638 ->node_nx_set_value (list, node, elt);
641 GL_LIST_INLINE gl_list_node_t
642 gl_list_next_node (gl_list_t list, gl_list_node_t node)
644 return ((const struct gl_list_impl_base *) list)->vtable
645 ->next_node (list, node);
648 GL_LIST_INLINE gl_list_node_t
649 gl_list_previous_node (gl_list_t list, gl_list_node_t node)
651 return ((const struct gl_list_impl_base *) list)->vtable
652 ->previous_node (list, node);
655 GL_LIST_INLINE gl_list_node_t
656 gl_list_first_node (gl_list_t list)
658 return ((const struct gl_list_impl_base *) list)->vtable
662 GL_LIST_INLINE gl_list_node_t
663 gl_list_last_node (gl_list_t list)
665 return ((const struct gl_list_impl_base *) list)->vtable
669 GL_LIST_INLINE const void *
670 gl_list_get_at (gl_list_t list, size_t position)
672 return ((const struct gl_list_impl_base *) list)->vtable
673 ->get_at (list, position);
676 GL_LIST_INLINE const void *
677 gl_list_get_first (gl_list_t list)
679 return gl_list_get_at (list, 0);
682 GL_LIST_INLINE const void *
683 gl_list_get_last (gl_list_t list)
685 return gl_list_get_at (list, gl_list_size (list) - 1);
688 GL_LIST_INLINE _GL_ATTRIBUTE_NODISCARD gl_list_node_t
689 gl_list_nx_set_at (gl_list_t list, size_t position, const void *elt)
691 return ((const struct gl_list_impl_base *) list)->vtable
692 ->nx_set_at (list, position, elt);
695 GL_LIST_INLINE _GL_ATTRIBUTE_NODISCARD gl_list_node_t
696 gl_list_nx_set_first (gl_list_t list, const void *elt)
698 return gl_list_nx_set_at (list, 0, elt);
701 GL_LIST_INLINE _GL_ATTRIBUTE_NODISCARD gl_list_node_t
702 gl_list_nx_set_last (gl_list_t list, const void *elt)
704 return gl_list_nx_set_at (list, gl_list_size (list) - 1, elt);
707 GL_LIST_INLINE gl_list_node_t
708 gl_list_search (gl_list_t list, const void *elt)
710 size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
711 return ((const struct gl_list_impl_base *) list)->vtable
712 ->search_from_to (list, 0, size, elt);
715 GL_LIST_INLINE gl_list_node_t
716 gl_list_search_from (gl_list_t list, size_t start_index, const void *elt)
718 size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
719 return ((const struct gl_list_impl_base *) list)->vtable
720 ->search_from_to (list, start_index, size, elt);
723 GL_LIST_INLINE gl_list_node_t
724 gl_list_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
727 return ((const struct gl_list_impl_base *) list)->vtable
728 ->search_from_to (list, start_index, end_index, elt);
731 GL_LIST_INLINE size_t
732 gl_list_indexof (gl_list_t list, const void *elt)
734 size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
735 return ((const struct gl_list_impl_base *) list)->vtable
736 ->indexof_from_to (list, 0, size, elt);
739 GL_LIST_INLINE size_t
740 gl_list_indexof_from (gl_list_t list, size_t start_index, const void *elt)
742 size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
743 return ((const struct gl_list_impl_base *) list)->vtable
744 ->indexof_from_to (list, start_index, size, elt);
747 GL_LIST_INLINE size_t
748 gl_list_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
751 return ((const struct gl_list_impl_base *) list)->vtable
752 ->indexof_from_to (list, start_index, end_index, elt);
755 GL_LIST_INLINE _GL_ATTRIBUTE_NODISCARD gl_list_node_t
756 gl_list_nx_add_first (gl_list_t list, const void *elt)
758 return ((const struct gl_list_impl_base *) list)->vtable
759 ->nx_add_first (list, elt);
762 GL_LIST_INLINE _GL_ATTRIBUTE_NODISCARD gl_list_node_t
763 gl_list_nx_add_last (gl_list_t list, const void *elt)
765 return ((const struct gl_list_impl_base *) list)->vtable
766 ->nx_add_last (list, elt);
769 GL_LIST_INLINE _GL_ATTRIBUTE_NODISCARD gl_list_node_t
770 gl_list_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
772 return ((const struct gl_list_impl_base *) list)->vtable
773 ->nx_add_before (list, node, elt);
776 GL_LIST_INLINE _GL_ATTRIBUTE_NODISCARD gl_list_node_t
777 gl_list_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
779 return ((const struct gl_list_impl_base *) list)->vtable
780 ->nx_add_after (list, node, elt);
783 GL_LIST_INLINE _GL_ATTRIBUTE_NODISCARD gl_list_node_t
784 gl_list_nx_add_at (gl_list_t list, size_t position, const void *elt)
786 return ((const struct gl_list_impl_base *) list)->vtable
787 ->nx_add_at (list, position, elt);
791 gl_list_remove_node (gl_list_t list, gl_list_node_t node)
793 return ((const struct gl_list_impl_base *) list)->vtable
794 ->remove_node (list, node);
798 gl_list_remove_at (gl_list_t list, size_t position)
800 return ((const struct gl_list_impl_base *) list)->vtable
801 ->remove_at (list, position);
805 gl_list_remove_first (gl_list_t list)
807 size_t size = gl_list_size (list);
809 return gl_list_remove_at (list, 0);
815 gl_list_remove_last (gl_list_t list)
817 size_t size = gl_list_size (list);
819 return gl_list_remove_at (list, size - 1);
825 gl_list_remove (gl_list_t list, const void *elt)
827 return ((const struct gl_list_impl_base *) list)->vtable
828 ->remove_elt (list, elt);
832 gl_list_free (gl_list_t list)
834 ((const struct gl_list_impl_base *) list)->vtable->list_free (list);
837 GL_LIST_INLINE gl_list_iterator_t
838 gl_list_iterator (gl_list_t list)
840 return ((const struct gl_list_impl_base *) list)->vtable
844 GL_LIST_INLINE gl_list_iterator_t
845 gl_list_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
847 return ((const struct gl_list_impl_base *) list)->vtable
848 ->iterator_from_to (list, start_index, end_index);
852 gl_list_iterator_next (gl_list_iterator_t *iterator,
853 const void **eltp, gl_list_node_t *nodep)
855 return iterator->vtable->iterator_next (iterator, eltp, nodep);
859 gl_list_iterator_free (gl_list_iterator_t *iterator)
861 iterator->vtable->iterator_free (iterator);
864 GL_LIST_INLINE gl_list_node_t
865 gl_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
867 return ((const struct gl_list_impl_base *) list)->vtable
868 ->sortedlist_search (list, compar, elt);
871 GL_LIST_INLINE gl_list_node_t
872 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)
874 return ((const struct gl_list_impl_base *) list)->vtable
875 ->sortedlist_search_from_to (list, compar, start_index, end_index,
879 GL_LIST_INLINE size_t
880 gl_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
882 return ((const struct gl_list_impl_base *) list)->vtable
883 ->sortedlist_indexof (list, compar, elt);
886 GL_LIST_INLINE size_t
887 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)
889 return ((const struct gl_list_impl_base *) list)->vtable
890 ->sortedlist_indexof_from_to (list, compar, start_index, end_index,
894 GL_LIST_INLINE _GL_ATTRIBUTE_NODISCARD gl_list_node_t
895 gl_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
897 return ((const struct gl_list_impl_base *) list)->vtable
898 ->sortedlist_nx_add (list, compar, elt);
902 gl_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
904 return ((const struct gl_list_impl_base *) list)->vtable
905 ->sortedlist_remove (list, compar, elt);
912 _GL_INLINE_HEADER_END
914 #endif /* _GL_LIST_H */