1/* Abstract sequential list data type. -*- coding: utf-8 -*-
2 Copyright (C) 2006-2019 Free Software Foundation, Inc.
3 Written by Bruno Haible <bruno@clisp.org>, 2006.
4
5 This program is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 3 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <https://www.gnu.org/licenses/>. */
17
18#ifndef _GL_LIST_H
19#define _GL_LIST_H
20
21#include <stdbool.h>
22#include <stddef.h>
23
24#ifndef _GL_INLINE_HEADER_BEGIN
25 #error "Please include config.h first."
26#endif
27_GL_INLINE_HEADER_BEGIN
28#ifndef GL_LIST_INLINE
29# define GL_LIST_INLINE _GL_INLINE
30#endif
31
32#ifdef __cplusplus
33extern "C" {
34#endif
35
36
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.
40
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
47 gl_list_create call.
48
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)
58
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.
63
64 The guaranteed average performance of the operations is, for a list of
65 n elements:
66
67 Operation ARRAY LINKED TREE LINKEDHASH TREEHASH
68 CARRAY with|without with|without
69 duplicates duplicates
70
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_get_at O(1) O(n) O(log n) O(n) O(log n)
77 gl_list_set_at O(1) O(n) O(log n) O(n) O((log n)²)/O(log n)
78 gl_list_search O(n) O(n) O(n) O(n)/O(1) O(log n)/O(1)
79 gl_list_search_from O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n)
80 gl_list_search_from_to O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n)
81 gl_list_indexof O(n) O(n) O(n) O(n) O(log n)
82 gl_list_indexof_from O(n) O(n) O(n) O(n) O((log n)²)/O(log n)
83 gl_list_indexof_from_to O(n) O(n) O(n) O(n) O((log n)²)/O(log n)
84 gl_list_add_first O(n)/O(1) O(1) O(log n) O(1) O((log n)²)/O(log n)
85 gl_list_add_last O(1) O(1) O(log n) O(1) O((log n)²)/O(log n)
86 gl_list_add_before O(n) O(1) O(log n) O(1) O((log n)²)/O(log n)
87 gl_list_add_after O(n) O(1) O(log n) O(1) O((log n)²)/O(log n)
88 gl_list_add_at O(n) O(n) O(log n) O(n) O((log n)²)/O(log n)
89 gl_list_remove_node O(n) O(1) O(log n) O(n)/O(1) O((log n)²)/O(log n)
90 gl_list_remove_at O(n) O(n) O(log n) O(n) O((log n)²)/O(log n)
91 gl_list_remove O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n)
92 gl_list_iterator O(1) O(1) O(log n) O(1) O(log n)
93 gl_list_iterator_from_to O(1) O(n) O(log n) O(n) O(log n)
94 gl_list_iterator_next O(1) O(1) O(log n) O(1) O(log n)
95 gl_sortedlist_search O(log n) O(n) O(log n) O(n) O(log n)
96 gl_sortedlist_search_from O(log n) O(n) O(log n) O(n) O(log n)
97 gl_sortedlist_indexof O(log n) O(n) O(log n) O(n) O(log n)
98 gl_sortedlist_indexof_fro O(log n) O(n) O(log n) O(n) O(log n)
99 gl_sortedlist_add O(n) O(n) O(log n) O(n) O((log n)²)/O(log n)
100 gl_sortedlist_remove O(n) O(n) O(log n) O(n) O((log n)²)/O(log n)
101 */
102
103/* -------------------------- gl_list_t Data Type -------------------------- */
104
105/* Type of function used to compare two elements.
106 NULL denotes pointer comparison. */
107typedef bool (*gl_listelement_equals_fn) (const void *elt1, const void *elt2);
108
109/* Type of function used to compute a hash code.
110 NULL denotes a function that depends only on the pointer itself. */
111typedef size_t (*gl_listelement_hashcode_fn) (const void *elt);
112
113/* Type of function used to dispose an element once it's removed from a list.
114 NULL denotes a no-op. */
115typedef void (*gl_listelement_dispose_fn) (const void *elt);
116
117struct gl_list_impl;
118/* Type representing an entire list. */
119typedef struct gl_list_impl * gl_list_t;
120
121struct gl_list_node_impl;
122/* Type representing the position of an element in the list, in a way that
123 is more adapted to the list implementation than a plain index.
124 Note: It is invalidated by insertions and removals! */
125typedef struct gl_list_node_impl * gl_list_node_t;
126
127struct gl_list_implementation;
128/* Type representing a list datatype implementation. */
129typedef const struct gl_list_implementation * gl_list_implementation_t;
130
131#if 0 /* Unless otherwise specified, these are defined inline below. */
132
133/* Create an empty list.
134 IMPLEMENTATION is one of GL_ARRAY_LIST, GL_CARRAY_LIST, GL_LINKED_LIST,
135 GL_AVLTREE_LIST, GL_RBTREE_LIST, GL_LINKEDHASH_LIST, GL_AVLTREEHASH_LIST,
136 GL_RBTREEHASH_LIST.
137 EQUALS_FN is an element comparison function or NULL.
138 HASHCODE_FN is an element hash code function or NULL.
139 DISPOSE_FN is an element disposal function or NULL.
140 ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in
141 the list. The implementation may verify this at runtime. */
142/* declared in gl_xlist.h */
143extern gl_list_t gl_list_create_empty (gl_list_implementation_t implementation,
144 gl_listelement_equals_fn equals_fn,
145 gl_listelement_hashcode_fn hashcode_fn,
146 gl_listelement_dispose_fn dispose_fn,
147 bool allow_duplicates);
148/* Likewise. Return NULL upon out-of-memory. */
149extern gl_list_t gl_list_nx_create_empty (gl_list_implementation_t implementation,
150 gl_listelement_equals_fn equals_fn,
151 gl_listelement_hashcode_fn hashcode_fn,
152 gl_listelement_dispose_fn dispose_fn,
153 bool allow_duplicates);
154
155/* Create a list with given contents.
156 IMPLEMENTATION is one of GL_ARRAY_LIST, GL_CARRAY_LIST, GL_LINKED_LIST,
157 GL_AVLTREE_LIST, GL_RBTREE_LIST, GL_LINKEDHASH_LIST, GL_AVLTREEHASH_LIST,
158 GL_RBTREEHASH_LIST.
159 EQUALS_FN is an element comparison function or NULL.
160 HASHCODE_FN is an element hash code function or NULL.
161 DISPOSE_FN is an element disposal function or NULL.
162 ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in
163 the list. The implementation may verify this at runtime.
164 COUNT is the number of initial elements.
165 CONTENTS[0..COUNT-1] is the initial contents. */
166/* declared in gl_xlist.h */
167extern gl_list_t gl_list_create (gl_list_implementation_t implementation,
168 gl_listelement_equals_fn equals_fn,
169 gl_listelement_hashcode_fn hashcode_fn,
170 gl_listelement_dispose_fn dispose_fn,
171 bool allow_duplicates,
172 size_t count, const void **contents);
173/* Likewise. Return NULL upon out-of-memory. */
174extern gl_list_t gl_list_nx_create (gl_list_implementation_t implementation,
175 gl_listelement_equals_fn equals_fn,
176 gl_listelement_hashcode_fn hashcode_fn,
177 gl_listelement_dispose_fn dispose_fn,
178 bool allow_duplicates,
179 size_t count, const void **contents);
180
181/* Return the current number of elements in a list. */
182extern size_t gl_list_size (gl_list_t list);
183
184/* Return the element value represented by a list node. */
185extern const void * gl_list_node_value (gl_list_t list, gl_list_node_t node);
186
187/* Replace the element value represented by a list node. */
188/* declared in gl_xlist.h */
189extern void gl_list_node_set_value (gl_list_t list, gl_list_node_t node,
190 const void *elt);
191/* Likewise. Return 0 upon success, -1 upon out-of-memory. */
192extern int gl_list_node_nx_set_value (gl_list_t list, gl_list_node_t node,
193 const void *elt)
194#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
195 __attribute__ ((__warn_unused_result__))
196#endif
197 ;
198
199/* Return the node immediately after the given node in the list, or NULL
200 if the given node is the last (rightmost) one in the list. */
201extern gl_list_node_t gl_list_next_node (gl_list_t list, gl_list_node_t node);
202
203/* Return the node immediately before the given node in the list, or NULL
204 if the given node is the first (leftmost) one in the list. */
205extern gl_list_node_t gl_list_previous_node (gl_list_t list, gl_list_node_t node);
206
207/* Return the element at a given position in the list.
208 POSITION must be >= 0 and < gl_list_size (list). */
209extern const void * gl_list_get_at (gl_list_t list, size_t position);
210
211/* Replace the element at a given position in the list.
212 POSITION must be >= 0 and < gl_list_size (list).
213 Return its node. */
214/* declared in gl_xlist.h */
215extern gl_list_node_t gl_list_set_at (gl_list_t list, size_t position,
216 const void *elt);
217/* Likewise. Return NULL upon out-of-memory. */
218extern gl_list_node_t gl_list_nx_set_at (gl_list_t list, size_t position,
219 const void *elt)
220#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
221 __attribute__ ((__warn_unused_result__))
222#endif
223 ;
224
225/* Search whether an element is already in the list.
226 Return its node if found, or NULL if not present in the list. */
227extern gl_list_node_t gl_list_search (gl_list_t list, const void *elt);
228
229/* Search whether an element is already in the list,
230 at a position >= START_INDEX.
231 Return its node if found, or NULL if not present in the list. */
232extern gl_list_node_t gl_list_search_from (gl_list_t list, size_t start_index,
233 const void *elt);
234
235/* Search whether an element is already in the list,
236 at a position >= START_INDEX and < END_INDEX.
237 Return its node if found, or NULL if not present in the list. */
238extern gl_list_node_t gl_list_search_from_to (gl_list_t list,
239 size_t start_index,
240 size_t end_index,
241 const void *elt);
242
243/* Search whether an element is already in the list.
244 Return its position if found, or (size_t)(-1) if not present in the list. */
245extern size_t gl_list_indexof (gl_list_t list, const void *elt);
246
247/* Search whether an element is already in the list,
248 at a position >= START_INDEX.
249 Return its position if found, or (size_t)(-1) if not present in the list. */
250extern size_t gl_list_indexof_from (gl_list_t list, size_t start_index,
251 const void *elt);
252
253/* Search whether an element is already in the list,
254 at a position >= START_INDEX and < END_INDEX.
255 Return its position if found, or (size_t)(-1) if not present in the list. */
256extern size_t gl_list_indexof_from_to (gl_list_t list,
257 size_t start_index, size_t end_index,
258 const void *elt);
259
260/* Add an element as the first element of the list.
261 Return its node. */
262/* declared in gl_xlist.h */
263extern gl_list_node_t gl_list_add_first (gl_list_t list, const void *elt);
264/* Likewise. Return NULL upon out-of-memory. */
265extern gl_list_node_t gl_list_nx_add_first (gl_list_t list, const void *elt)
266#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
267 __attribute__ ((__warn_unused_result__))
268#endif
269 ;
270
271/* Add an element as the last element of the list.
272 Return its node. */
273/* declared in gl_xlist.h */
274extern gl_list_node_t gl_list_add_last (gl_list_t list, const void *elt);
275/* Likewise. Return NULL upon out-of-memory. */
276extern gl_list_node_t gl_list_nx_add_last (gl_list_t list, const void *elt)
277#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
278 __attribute__ ((__warn_unused_result__))
279#endif
280 ;
281
282/* Add an element before a given element node of the list.
283 Return its node. */
284/* declared in gl_xlist.h */
285extern gl_list_node_t gl_list_add_before (gl_list_t list, gl_list_node_t node,
286 const void *elt);
287/* Likewise. Return NULL upon out-of-memory. */
288extern gl_list_node_t gl_list_nx_add_before (gl_list_t list,
289 gl_list_node_t node,
290 const void *elt)
291#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
292 __attribute__ ((__warn_unused_result__))
293#endif
294 ;
295
296/* Add an element after a given element node of the list.
297 Return its node. */
298/* declared in gl_xlist.h */
299extern gl_list_node_t gl_list_add_after (gl_list_t list, gl_list_node_t node,
300 const void *elt);
301/* Likewise. Return NULL upon out-of-memory. */
302extern gl_list_node_t gl_list_nx_add_after (gl_list_t list, gl_list_node_t node,
303 const void *elt)
304#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
305 __attribute__ ((__warn_unused_result__))
306#endif
307 ;
308
309/* Add an element at a given position in the list.
310 POSITION must be >= 0 and <= gl_list_size (list). */
311/* declared in gl_xlist.h */
312extern gl_list_node_t gl_list_add_at (gl_list_t list, size_t position,
313 const void *elt);
314/* Likewise. Return NULL upon out-of-memory. */
315extern gl_list_node_t gl_list_nx_add_at (gl_list_t list, size_t position,
316 const void *elt)
317#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
318 __attribute__ ((__warn_unused_result__))
319#endif
320 ;
321
322/* Remove an element from the list.
323 Return true. */
324extern bool gl_list_remove_node (gl_list_t list, gl_list_node_t node);
325
326/* Remove an element at a given position from the list.
327 POSITION must be >= 0 and < gl_list_size (list).
328 Return true. */
329extern bool gl_list_remove_at (gl_list_t list, size_t position);
330
331/* Search and remove an element from the list.
332 Return true if it was found and removed. */
333extern bool gl_list_remove (gl_list_t list, const void *elt);
334
335/* Free an entire list.
336 (But this call does not free the elements of the list. It only invokes
337 the DISPOSE_FN on each of the elements of the list, and only if the list
338 is not a sublist.) */
339extern void gl_list_free (gl_list_t list);
340
341#endif /* End of inline and gl_xlist.h-defined functions. */
342
343/* --------------------- gl_list_iterator_t Data Type --------------------- */
344
345/* Functions for iterating through a list. */
346
347/* Type of an iterator that traverses a list.
348 This is a fixed-size struct, so that creation of an iterator doesn't need
349 memory allocation on the heap. */
350typedef struct
351{
352 /* For fast dispatch of gl_list_iterator_next. */
353 const struct gl_list_implementation *vtable;
354 /* For detecting whether the last returned element was removed. */
355 gl_list_t list;
356 size_t count;
357 /* Other, implementation-private fields. */
358 void *p; void *q;
359 size_t i; size_t j;
360} gl_list_iterator_t;
361
362#if 0 /* These are defined inline below. */
363
364/* Create an iterator traversing a list.
365 The list contents must not be modified while the iterator is in use,
366 except for replacing or removing the last returned element. */
367extern gl_list_iterator_t gl_list_iterator (gl_list_t list);
368
369/* Create an iterator traversing the element with indices i,
370 start_index <= i < end_index, of a list.
371 The list contents must not be modified while the iterator is in use,
372 except for replacing or removing the last returned element. */
373extern gl_list_iterator_t gl_list_iterator_from_to (gl_list_t list,
374 size_t start_index,
375 size_t end_index);
376
377/* If there is a next element, store the next element in *ELTP, store its
378 node in *NODEP if NODEP is non-NULL, advance the iterator and return true.
379 Otherwise, return false. */
380extern bool gl_list_iterator_next (gl_list_iterator_t *iterator,
381 const void **eltp, gl_list_node_t *nodep);
382
383/* Free an iterator. */
384extern void gl_list_iterator_free (gl_list_iterator_t *iterator);
385
386#endif /* End of inline functions. */
387
388/* ---------------------- Sorted gl_list_t Data Type ---------------------- */
389
390/* The following functions are for lists without duplicates where the
391 order is given by a sort criterion. */
392
393/* Type of function used to compare two elements. Same as for qsort().
394 NULL denotes pointer comparison. */
395typedef int (*gl_listelement_compar_fn) (const void *elt1, const void *elt2);
396
397#if 0 /* Unless otherwise specified, these are defined inline below. */
398
399/* Search whether an element is already in the list.
400 The list is assumed to be sorted with COMPAR.
401 Return its node if found, or NULL if not present in the list.
402 If the list contains several copies of ELT, the node of the leftmost one is
403 returned. */
404extern gl_list_node_t gl_sortedlist_search (gl_list_t list,
405 gl_listelement_compar_fn compar,
406 const void *elt);
407
408/* Search whether an element is already in the list.
409 The list is assumed to be sorted with COMPAR.
410 Only list elements with indices >= START_INDEX and < END_INDEX are
411 considered; the implementation uses these bounds to minimize the number
412 of COMPAR invocations.
413 Return its node if found, or NULL if not present in the list.
414 If the list contains several copies of ELT, the node of the leftmost one is
415 returned. */
416extern gl_list_node_t gl_sortedlist_search_from_to (gl_list_t list,
417 gl_listelement_compar_fn compar,
418 size_t start_index,
419 size_t end_index,
420 const void *elt);
421
422/* Search whether an element is already in the list.
423 The list is assumed to be sorted with COMPAR.
424 Return its position if found, or (size_t)(-1) if not present in the list.
425 If the list contains several copies of ELT, the position of the leftmost one
426 is returned. */
427extern size_t gl_sortedlist_indexof (gl_list_t list,
428 gl_listelement_compar_fn compar,
429 const void *elt);
430
431/* Search whether an element is already in the list.
432 The list is assumed to be sorted with COMPAR.
433 Only list elements with indices >= START_INDEX and < END_INDEX are
434 considered; the implementation uses these bounds to minimize the number
435 of COMPAR invocations.
436 Return its position if found, or (size_t)(-1) if not present in the list.
437 If the list contains several copies of ELT, the position of the leftmost one
438 is returned. */
439extern size_t gl_sortedlist_indexof_from_to (gl_list_t list,
440 gl_listelement_compar_fn compar,
441 size_t start_index,
442 size_t end_index,
443 const void *elt);
444
445/* Add an element at the appropriate position in the list.
446 The list is assumed to be sorted with COMPAR.
447 Return its node. */
448/* declared in gl_xlist.h */
449extern gl_list_node_t gl_sortedlist_add (gl_list_t list,
450 gl_listelement_compar_fn compar,
451 const void *elt);
452/* Likewise. Return NULL upon out-of-memory. */
453extern gl_list_node_t gl_sortedlist_nx_add (gl_list_t list,
454 gl_listelement_compar_fn compar,
455 const void *elt)
456#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
457 __attribute__ ((__warn_unused_result__))
458#endif
459 ;
460
461/* Search and remove an element from the list.
462 The list is assumed to be sorted with COMPAR.
463 Return true if it was found and removed.
464 If the list contains several copies of ELT, only the leftmost one is
465 removed. */
466extern bool gl_sortedlist_remove (gl_list_t list,
467 gl_listelement_compar_fn compar,
468 const void *elt);
469
470#endif /* End of inline and gl_xlist.h-defined functions. */
471
472/* ------------------------ Implementation Details ------------------------ */
473
474struct gl_list_implementation
475{
476 /* gl_list_t functions. */
477 gl_list_t (*nx_create_empty) (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 gl_list_t (*nx_create) (gl_list_implementation_t implementation,
483 gl_listelement_equals_fn equals_fn,
484 gl_listelement_hashcode_fn hashcode_fn,
485 gl_listelement_dispose_fn dispose_fn,
486 bool allow_duplicates,
487 size_t count, const void **contents);
488 size_t (*size) (gl_list_t list);
489 const void * (*node_value) (gl_list_t list, gl_list_node_t node);
490 int (*node_nx_set_value) (gl_list_t list, gl_list_node_t node,
491 const void *elt);
492 gl_list_node_t (*next_node) (gl_list_t list, gl_list_node_t node);
493 gl_list_node_t (*previous_node) (gl_list_t list, gl_list_node_t node);
494 const void * (*get_at) (gl_list_t list, size_t position);
495 gl_list_node_t (*nx_set_at) (gl_list_t list, size_t position,
496 const void *elt);
497 gl_list_node_t (*search_from_to) (gl_list_t list, size_t start_index,
498 size_t end_index, const void *elt);
499 size_t (*indexof_from_to) (gl_list_t list, size_t start_index,
500 size_t end_index, const void *elt);
501 gl_list_node_t (*nx_add_first) (gl_list_t list, const void *elt);
502 gl_list_node_t (*nx_add_last) (gl_list_t list, const void *elt);
503 gl_list_node_t (*nx_add_before) (gl_list_t list, gl_list_node_t node,
504 const void *elt);
505 gl_list_node_t (*nx_add_after) (gl_list_t list, gl_list_node_t node,
506 const void *elt);
507 gl_list_node_t (*nx_add_at) (gl_list_t list, size_t position,
508 const void *elt);
509 bool (*remove_node) (gl_list_t list, gl_list_node_t node);
510 bool (*remove_at) (gl_list_t list, size_t position);
511 bool (*remove_elt) (gl_list_t list, const void *elt);
512 void (*list_free) (gl_list_t list);
513 /* gl_list_iterator_t functions. */
514 gl_list_iterator_t (*iterator) (gl_list_t list);
515 gl_list_iterator_t (*iterator_from_to) (gl_list_t list,
516 size_t start_index,
517 size_t end_index);
518 bool (*iterator_next) (gl_list_iterator_t *iterator,
519 const void **eltp, gl_list_node_t *nodep);
520 void (*iterator_free) (gl_list_iterator_t *iterator);
521 /* Sorted gl_list_t functions. */
522 gl_list_node_t (*sortedlist_search) (gl_list_t list,
523 gl_listelement_compar_fn compar,
524 const void *elt);
525 gl_list_node_t (*sortedlist_search_from_to) (gl_list_t list,
526 gl_listelement_compar_fn compar,
527 size_t start_index,
528 size_t end_index,
529 const void *elt);
530 size_t (*sortedlist_indexof) (gl_list_t list,
531 gl_listelement_compar_fn compar,
532 const void *elt);
533 size_t (*sortedlist_indexof_from_to) (gl_list_t list,
534 gl_listelement_compar_fn compar,
535 size_t start_index, size_t end_index,
536 const void *elt);
537 gl_list_node_t (*sortedlist_nx_add) (gl_list_t list,
538 gl_listelement_compar_fn compar,
539 const void *elt);
540 bool (*sortedlist_remove) (gl_list_t list,
541 gl_listelement_compar_fn compar,
542 const void *elt);
543};
544
545struct gl_list_impl_base
546{
547 const struct gl_list_implementation *vtable;
548 gl_listelement_equals_fn equals_fn;
549 gl_listelement_hashcode_fn hashcode_fn;
550 gl_listelement_dispose_fn dispose_fn;
551 bool allow_duplicates;
552};
553
554/* Define all functions of this file as accesses to the
555 struct gl_list_implementation. */
556
557GL_LIST_INLINE gl_list_t
558gl_list_nx_create_empty (gl_list_implementation_t implementation,
559 gl_listelement_equals_fn equals_fn,
560 gl_listelement_hashcode_fn hashcode_fn,
561 gl_listelement_dispose_fn dispose_fn,
562 bool allow_duplicates)
563{
564 return implementation->nx_create_empty (implementation, equals_fn,
565 hashcode_fn, dispose_fn,
566 allow_duplicates);
567}
568
569GL_LIST_INLINE gl_list_t
570gl_list_nx_create (gl_list_implementation_t implementation,
571 gl_listelement_equals_fn equals_fn,
572 gl_listelement_hashcode_fn hashcode_fn,
573 gl_listelement_dispose_fn dispose_fn,
574 bool allow_duplicates,
575 size_t count, const void **contents)
576{
577 return implementation->nx_create (implementation, equals_fn, hashcode_fn,
578 dispose_fn, allow_duplicates, count,
579 contents);
580}
581
582GL_LIST_INLINE size_t
583gl_list_size (gl_list_t list)
584{
585 return ((const struct gl_list_impl_base *) list)->vtable
586 ->size (list);
587}
588
589GL_LIST_INLINE const void *
590gl_list_node_value (gl_list_t list, gl_list_node_t node)
591{
592 return ((const struct gl_list_impl_base *) list)->vtable
593 ->node_value (list, node);
594}
595
596GL_LIST_INLINE int
597#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
598 __attribute__ ((__warn_unused_result__))
599#endif
600gl_list_node_nx_set_value (gl_list_t list, gl_list_node_t node,
601 const void *elt)
602{
603 return ((const struct gl_list_impl_base *) list)->vtable
604 ->node_nx_set_value (list, node, elt);
605}
606
607GL_LIST_INLINE gl_list_node_t
608gl_list_next_node (gl_list_t list, gl_list_node_t node)
609{
610 return ((const struct gl_list_impl_base *) list)->vtable
611 ->next_node (list, node);
612}
613
614GL_LIST_INLINE gl_list_node_t
615gl_list_previous_node (gl_list_t list, gl_list_node_t node)
616{
617 return ((const struct gl_list_impl_base *) list)->vtable
618 ->previous_node (list, node);
619}
620
621GL_LIST_INLINE const void *
622gl_list_get_at (gl_list_t list, size_t position)
623{
624 return ((const struct gl_list_impl_base *) list)->vtable
625 ->get_at (list, position);
626}
627
628GL_LIST_INLINE gl_list_node_t
629#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
630 __attribute__ ((__warn_unused_result__))
631#endif
632gl_list_nx_set_at (gl_list_t list, size_t position, const void *elt)
633{
634 return ((const struct gl_list_impl_base *) list)->vtable
635 ->nx_set_at (list, position, elt);
636}
637
638GL_LIST_INLINE gl_list_node_t
639gl_list_search (gl_list_t list, const void *elt)
640{
641 size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
642 return ((const struct gl_list_impl_base *) list)->vtable
643 ->search_from_to (list, 0, size, elt);
644}
645
646GL_LIST_INLINE gl_list_node_t
647gl_list_search_from (gl_list_t list, size_t start_index, const void *elt)
648{
649 size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
650 return ((const struct gl_list_impl_base *) list)->vtable
651 ->search_from_to (list, start_index, size, elt);
652}
653
654GL_LIST_INLINE gl_list_node_t
655gl_list_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
656 const void *elt)
657{
658 return ((const struct gl_list_impl_base *) list)->vtable
659 ->search_from_to (list, start_index, end_index, elt);
660}
661
662GL_LIST_INLINE size_t
663gl_list_indexof (gl_list_t list, const void *elt)
664{
665 size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
666 return ((const struct gl_list_impl_base *) list)->vtable
667 ->indexof_from_to (list, 0, size, elt);
668}
669
670GL_LIST_INLINE size_t
671gl_list_indexof_from (gl_list_t list, size_t start_index, const void *elt)
672{
673 size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
674 return ((const struct gl_list_impl_base *) list)->vtable
675 ->indexof_from_to (list, start_index, size, elt);
676}
677
678GL_LIST_INLINE size_t
679gl_list_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
680 const void *elt)
681{
682 return ((const struct gl_list_impl_base *) list)->vtable
683 ->indexof_from_to (list, start_index, end_index, elt);
684}
685
686GL_LIST_INLINE gl_list_node_t
687#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
688 __attribute__ ((__warn_unused_result__))
689#endif
690gl_list_nx_add_first (gl_list_t list, const void *elt)
691{
692 return ((const struct gl_list_impl_base *) list)->vtable
693 ->nx_add_first (list, elt);
694}
695
696GL_LIST_INLINE gl_list_node_t
697#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
698 __attribute__ ((__warn_unused_result__))
699#endif
700gl_list_nx_add_last (gl_list_t list, const void *elt)
701{
702 return ((const struct gl_list_impl_base *) list)->vtable
703 ->nx_add_last (list, elt);
704}
705
706GL_LIST_INLINE gl_list_node_t
707#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
708 __attribute__ ((__warn_unused_result__))
709#endif
710gl_list_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
711{
712 return ((const struct gl_list_impl_base *) list)->vtable
713 ->nx_add_before (list, node, elt);
714}
715
716GL_LIST_INLINE gl_list_node_t
717#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
718 __attribute__ ((__warn_unused_result__))
719#endif
720gl_list_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
721{
722 return ((const struct gl_list_impl_base *) list)->vtable
723 ->nx_add_after (list, node, elt);
724}
725
726GL_LIST_INLINE gl_list_node_t
727#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
728 __attribute__ ((__warn_unused_result__))
729#endif
730gl_list_nx_add_at (gl_list_t list, size_t position, const void *elt)
731{
732 return ((const struct gl_list_impl_base *) list)->vtable
733 ->nx_add_at (list, position, elt);
734}
735
736GL_LIST_INLINE bool
737gl_list_remove_node (gl_list_t list, gl_list_node_t node)
738{
739 return ((const struct gl_list_impl_base *) list)->vtable
740 ->remove_node (list, node);
741}
742
743GL_LIST_INLINE bool
744gl_list_remove_at (gl_list_t list, size_t position)
745{
746 return ((const struct gl_list_impl_base *) list)->vtable
747 ->remove_at (list, position);
748}
749
750GL_LIST_INLINE bool
751gl_list_remove (gl_list_t list, const void *elt)
752{
753 return ((const struct gl_list_impl_base *) list)->vtable
754 ->remove_elt (list, elt);
755}
756
757GL_LIST_INLINE void
758gl_list_free (gl_list_t list)
759{
760 ((const struct gl_list_impl_base *) list)->vtable->list_free (list);
761}
762
763GL_LIST_INLINE gl_list_iterator_t
764gl_list_iterator (gl_list_t list)
765{
766 return ((const struct gl_list_impl_base *) list)->vtable
767 ->iterator (list);
768}
769
770GL_LIST_INLINE gl_list_iterator_t
771gl_list_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
772{
773 return ((const struct gl_list_impl_base *) list)->vtable
774 ->iterator_from_to (list, start_index, end_index);
775}
776
777GL_LIST_INLINE bool
778gl_list_iterator_next (gl_list_iterator_t *iterator,
779 const void **eltp, gl_list_node_t *nodep)
780{
781 return iterator->vtable->iterator_next (iterator, eltp, nodep);
782}
783
784GL_LIST_INLINE void
785gl_list_iterator_free (gl_list_iterator_t *iterator)
786{
787 iterator->vtable->iterator_free (iterator);
788}
789
790GL_LIST_INLINE gl_list_node_t
791gl_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
792{
793 return ((const struct gl_list_impl_base *) list)->vtable
794 ->sortedlist_search (list, compar, elt);
795}
796
797GL_LIST_INLINE gl_list_node_t
798gl_sortedlist_search_from_to (gl_list_t list, gl_listelement_compar_fn compar, size_t start_index, size_t end_index, const void *elt)
799{
800 return ((const struct gl_list_impl_base *) list)->vtable
801 ->sortedlist_search_from_to (list, compar, start_index, end_index,
802 elt);
803}
804
805GL_LIST_INLINE size_t
806gl_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
807{
808 return ((const struct gl_list_impl_base *) list)->vtable
809 ->sortedlist_indexof (list, compar, elt);
810}
811
812GL_LIST_INLINE size_t
813gl_sortedlist_indexof_from_to (gl_list_t list, gl_listelement_compar_fn compar, size_t start_index, size_t end_index, const void *elt)
814{
815 return ((const struct gl_list_impl_base *) list)->vtable
816 ->sortedlist_indexof_from_to (list, compar, start_index, end_index,
817 elt);
818}
819
820GL_LIST_INLINE gl_list_node_t
821#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
822 __attribute__ ((__warn_unused_result__))
823#endif
824gl_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
825{
826 return ((const struct gl_list_impl_base *) list)->vtable
827 ->sortedlist_nx_add (list, compar, elt);
828}
829
830GL_LIST_INLINE bool
831gl_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
832{
833 return ((const struct gl_list_impl_base *) list)->vtable
834 ->sortedlist_remove (list, compar, elt);
835}
836
837#ifdef __cplusplus
838}
839#endif
840
841_GL_INLINE_HEADER_END
842
843#endif /* _GL_LIST_H */
844