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.
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
33 extern "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_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)
109 */
110
111 /* -------------------------- gl_list_t Data Type -------------------------- */
112
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);
116
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);
120
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);
124
125 struct gl_list_impl;
126 /* Type representing an entire list. */
127 typedef struct gl_list_impl * gl_list_t;
128
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;
134
135 struct gl_list_implementation;
136 /* Type representing a list datatype implementation. */
137 typedef const struct gl_list_implementation * gl_list_implementation_t;
138
139 #if 0 /* Unless otherwise specified, these are defined inline below. */
140
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,
144 GL_RBTREEHASH_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);
162
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,
166 GL_RBTREEHASH_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);
188
189 /* Returns the current number of elements in a list. */
190 extern size_t gl_list_size (gl_list_t list);
191
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);
194
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,
198 const void *elt);
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,
201 const void *elt)
202 _GL_ATTRIBUTE_NODISCARD;
203
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);
207
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);
211
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:
214 gl_list_node_t node;
215 for (node = gl_list_first_node (list); node != NULL; node = gl_list_next_node (node))
216 ...
217 */
218 extern gl_list_node_t gl_list_first_node (gl_list_t list);
219
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,
222 like this:
223 gl_list_node_t node;
224 for (node = gl_list_last_node (list); node != NULL; node = gl_list_previous_node (node))
225 ...
226 */
227 extern gl_list_node_t gl_list_last_node (gl_list_t list);
228
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);
232
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);
236
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);
240
241 /* Replaces the element at a given position in the list.
242 POSITION must be >= 0 and < gl_list_size (list).
243 Returns its node. */
244 /* declared in gl_xlist.h */
245 extern gl_list_node_t gl_list_set_at (gl_list_t list, size_t position,
246 const void *elt);
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,
249 const void *elt)
250 _GL_ATTRIBUTE_NODISCARD;
251
252 /* Replaces the element at the first position in the list.
253 Returns its node.
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;
260
261 /* Replaces the element at the last position in the list.
262 Returns its node.
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;
269
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);
273
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,
278 const void *elt);
279
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,
284 size_t start_index,
285 size_t end_index,
286 const void *elt);
287
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);
291
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,
296 const void *elt);
297
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,
303 const void *elt);
304
305 /* Adds an element as the first element of the list.
306 Returns its node. */
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;
312
313 /* Adds an element as the last element of the list.
314 Returns its node. */
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;
320
321 /* Adds an element before a given element node of the list.
322 Returns its node. */
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,
325 const void *elt);
326 /* Likewise. Returns NULL upon out-of-memory. */
327 extern gl_list_node_t gl_list_nx_add_before (gl_list_t list,
328 gl_list_node_t node,
329 const void *elt)
330 _GL_ATTRIBUTE_NODISCARD;
331
332 /* Adds an element after a given element node of the list.
333 Returns its node. */
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,
336 const void *elt);
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,
339 const void *elt)
340 _GL_ATTRIBUTE_NODISCARD;
341
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,
346 const void *elt);
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,
349 const void *elt)
350 _GL_ATTRIBUTE_NODISCARD;
351
352 /* Removes an element from the list.
353 Returns true. */
354 extern bool gl_list_remove_node (gl_list_t list, gl_list_node_t node);
355
356 /* Removes an element at a given position from the list.
357 POSITION must be >= 0 and < gl_list_size (list).
358 Returns true. */
359 extern bool gl_list_remove_at (gl_list_t list, size_t position);
360
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);
364
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);
368
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);
372
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);
378
379 #endif /* End of inline and gl_xlist.h-defined functions. */
380
381 /* --------------------- gl_list_iterator_t Data Type --------------------- */
382
383 /* Functions for iterating through a list. */
384
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. */
388 typedef struct
389 {
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. */
393 gl_list_t list;
394 size_t count;
395 /* Other, implementation-private fields. */
396 void *p; void *q;
397 size_t i; size_t j;
398 } gl_list_iterator_t;
399
400 #if 0 /* These are defined inline below. */
401
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);
406
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,
412 size_t start_index,
413 size_t end_index);
414
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);
420
421 /* Frees an iterator. */
422 extern void gl_list_iterator_free (gl_list_iterator_t *iterator);
423
424 #endif /* End of inline functions. */
425
426 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
427
428 /* The following functions are for lists without duplicates where the
429 order is given by a sort criterion. */
430
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);
434
435 #if 0 /* Unless otherwise specified, these are defined inline below. */
436
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
441 returned. */
442 extern gl_list_node_t gl_sortedlist_search (gl_list_t list,
443 gl_listelement_compar_fn compar,
444 const void *elt);
445
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
453 returned. */
454 extern gl_list_node_t gl_sortedlist_search_from_to (gl_list_t list,
455 gl_listelement_compar_fn compar,
456 size_t start_index,
457 size_t end_index,
458 const void *elt);
459
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
464 is returned. */
465 extern size_t gl_sortedlist_indexof (gl_list_t list,
466 gl_listelement_compar_fn compar,
467 const void *elt);
468
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
476 is returned. */
477 extern size_t gl_sortedlist_indexof_from_to (gl_list_t list,
478 gl_listelement_compar_fn compar,
479 size_t start_index,
480 size_t end_index,
481 const void *elt);
482
483 /* Adds an element at the appropriate position in the list.
484 The list is assumed to be sorted with COMPAR.
485 Returns its node. */
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,
489 const void *elt);
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,
493 const void *elt)
494 _GL_ATTRIBUTE_NODISCARD;
495
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
500 removed. */
501 extern bool gl_sortedlist_remove (gl_list_t list,
502 gl_listelement_compar_fn compar,
503 const void *elt);
504
505 #endif /* End of inline and gl_xlist.h-defined functions. */
506
507 /* ------------------------ Implementation Details ------------------------ */
508
509 struct gl_list_implementation
510 {
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,
526 const void *elt);
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,
533 const void *elt);
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,
541 const void *elt);
542 gl_list_node_t (*nx_add_after) (gl_list_t list, gl_list_node_t node,
543 const void *elt);
544 gl_list_node_t (*nx_add_at) (gl_list_t list, size_t position,
545 const void *elt);
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,
553 size_t start_index,
554 size_t end_index);
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,
561 const void *elt);
562 gl_list_node_t (*sortedlist_search_from_to) (gl_list_t list,
563 gl_listelement_compar_fn compar,
564 size_t start_index,
565 size_t end_index,
566 const void *elt);
567 size_t (*sortedlist_indexof) (gl_list_t list,
568 gl_listelement_compar_fn compar,
569 const void *elt);
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,
573 const void *elt);
574 gl_list_node_t (*sortedlist_nx_add) (gl_list_t list,
575 gl_listelement_compar_fn compar,
576 const void *elt);
577 bool (*sortedlist_remove) (gl_list_t list,
578 gl_listelement_compar_fn compar,
579 const void *elt);
580 };
581
582 struct gl_list_impl_base
583 {
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;
589 };
590
591 /* Define all functions of this file as accesses to the
592 struct gl_list_implementation. */
593
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)
600 {
601 return implementation->nx_create_empty (implementation, equals_fn,
602 hashcode_fn, dispose_fn,
603 allow_duplicates);
604 }
605
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)
613 {
614 return implementation->nx_create (implementation, equals_fn, hashcode_fn,
615 dispose_fn, allow_duplicates, count,
616 contents);
617 }
618
619 GL_LIST_INLINE size_t
620 gl_list_size (gl_list_t list)
621 {
622 return ((const struct gl_list_impl_base *) list)->vtable
623 ->size (list);
624 }
625
626 GL_LIST_INLINE const void *
627 gl_list_node_value (gl_list_t list, gl_list_node_t node)
628 {
629 return ((const struct gl_list_impl_base *) list)->vtable
630 ->node_value (list, node);
631 }
632
633 GL_LIST_INLINE _GL_ATTRIBUTE_NODISCARD int
634 gl_list_node_nx_set_value (gl_list_t list, gl_list_node_t node,
635 const void *elt)
636 {
637 return ((const struct gl_list_impl_base *) list)->vtable
638 ->node_nx_set_value (list, node, elt);
639 }
640
641 GL_LIST_INLINE gl_list_node_t
642 gl_list_next_node (gl_list_t list, gl_list_node_t node)
643 {
644 return ((const struct gl_list_impl_base *) list)->vtable
645 ->next_node (list, node);
646 }
647
648 GL_LIST_INLINE gl_list_node_t
649 gl_list_previous_node (gl_list_t list, gl_list_node_t node)
650 {
651 return ((const struct gl_list_impl_base *) list)->vtable
652 ->previous_node (list, node);
653 }
654
655 GL_LIST_INLINE gl_list_node_t
656 gl_list_first_node (gl_list_t list)
657 {
658 return ((const struct gl_list_impl_base *) list)->vtable
659 ->first_node (list);
660 }
661
662 GL_LIST_INLINE gl_list_node_t
663 gl_list_last_node (gl_list_t list)
664 {
665 return ((const struct gl_list_impl_base *) list)->vtable
666 ->last_node (list);
667 }
668
669 GL_LIST_INLINE const void *
670 gl_list_get_at (gl_list_t list, size_t position)
671 {
672 return ((const struct gl_list_impl_base *) list)->vtable
673 ->get_at (list, position);
674 }
675
676 GL_LIST_INLINE const void *
677 gl_list_get_first (gl_list_t list)
678 {
679 return gl_list_get_at (list, 0);
680 }
681
682 GL_LIST_INLINE const void *
683 gl_list_get_last (gl_list_t list)
684 {
685 return gl_list_get_at (list, gl_list_size (list) - 1);
686 }
687
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)
690 {
691 return ((const struct gl_list_impl_base *) list)->vtable
692 ->nx_set_at (list, position, elt);
693 }
694
695 GL_LIST_INLINE _GL_ATTRIBUTE_NODISCARD gl_list_node_t
696 gl_list_nx_set_first (gl_list_t list, const void *elt)
697 {
698 return gl_list_nx_set_at (list, 0, elt);
699 }
700
701 GL_LIST_INLINE _GL_ATTRIBUTE_NODISCARD gl_list_node_t
702 gl_list_nx_set_last (gl_list_t list, const void *elt)
703 {
704 return gl_list_nx_set_at (list, gl_list_size (list) - 1, elt);
705 }
706
707 GL_LIST_INLINE gl_list_node_t
708 gl_list_search (gl_list_t list, const void *elt)
709 {
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);
713 }
714
715 GL_LIST_INLINE gl_list_node_t
716 gl_list_search_from (gl_list_t list, size_t start_index, const void *elt)
717 {
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);
721 }
722
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,
725 const void *elt)
726 {
727 return ((const struct gl_list_impl_base *) list)->vtable
728 ->search_from_to (list, start_index, end_index, elt);
729 }
730
731 GL_LIST_INLINE size_t
732 gl_list_indexof (gl_list_t list, const void *elt)
733 {
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);
737 }
738
739 GL_LIST_INLINE size_t
740 gl_list_indexof_from (gl_list_t list, size_t start_index, const void *elt)
741 {
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);
745 }
746
747 GL_LIST_INLINE size_t
748 gl_list_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
749 const void *elt)
750 {
751 return ((const struct gl_list_impl_base *) list)->vtable
752 ->indexof_from_to (list, start_index, end_index, elt);
753 }
754
755 GL_LIST_INLINE _GL_ATTRIBUTE_NODISCARD gl_list_node_t
756 gl_list_nx_add_first (gl_list_t list, const void *elt)
757 {
758 return ((const struct gl_list_impl_base *) list)->vtable
759 ->nx_add_first (list, elt);
760 }
761
762 GL_LIST_INLINE _GL_ATTRIBUTE_NODISCARD gl_list_node_t
763 gl_list_nx_add_last (gl_list_t list, const void *elt)
764 {
765 return ((const struct gl_list_impl_base *) list)->vtable
766 ->nx_add_last (list, elt);
767 }
768
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)
771 {
772 return ((const struct gl_list_impl_base *) list)->vtable
773 ->nx_add_before (list, node, elt);
774 }
775
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)
778 {
779 return ((const struct gl_list_impl_base *) list)->vtable
780 ->nx_add_after (list, node, elt);
781 }
782
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)
785 {
786 return ((const struct gl_list_impl_base *) list)->vtable
787 ->nx_add_at (list, position, elt);
788 }
789
790 GL_LIST_INLINE bool
791 gl_list_remove_node (gl_list_t list, gl_list_node_t node)
792 {
793 return ((const struct gl_list_impl_base *) list)->vtable
794 ->remove_node (list, node);
795 }
796
797 GL_LIST_INLINE bool
798 gl_list_remove_at (gl_list_t list, size_t position)
799 {
800 return ((const struct gl_list_impl_base *) list)->vtable
801 ->remove_at (list, position);
802 }
803
804 GL_LIST_INLINE bool
805 gl_list_remove_first (gl_list_t list)
806 {
807 size_t size = gl_list_size (list);
808 if (size > 0)
809 return gl_list_remove_at (list, 0);
810 else
811 return false;
812 }
813
814 GL_LIST_INLINE bool
815 gl_list_remove_last (gl_list_t list)
816 {
817 size_t size = gl_list_size (list);
818 if (size > 0)
819 return gl_list_remove_at (list, size - 1);
820 else
821 return false;
822 }
823
824 GL_LIST_INLINE bool
825 gl_list_remove (gl_list_t list, const void *elt)
826 {
827 return ((const struct gl_list_impl_base *) list)->vtable
828 ->remove_elt (list, elt);
829 }
830
831 GL_LIST_INLINE void
832 gl_list_free (gl_list_t list)
833 {
834 ((const struct gl_list_impl_base *) list)->vtable->list_free (list);
835 }
836
837 GL_LIST_INLINE gl_list_iterator_t
838 gl_list_iterator (gl_list_t list)
839 {
840 return ((const struct gl_list_impl_base *) list)->vtable
841 ->iterator (list);
842 }
843
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)
846 {
847 return ((const struct gl_list_impl_base *) list)->vtable
848 ->iterator_from_to (list, start_index, end_index);
849 }
850
851 GL_LIST_INLINE bool
852 gl_list_iterator_next (gl_list_iterator_t *iterator,
853 const void **eltp, gl_list_node_t *nodep)
854 {
855 return iterator->vtable->iterator_next (iterator, eltp, nodep);
856 }
857
858 GL_LIST_INLINE void
859 gl_list_iterator_free (gl_list_iterator_t *iterator)
860 {
861 iterator->vtable->iterator_free (iterator);
862 }
863
864 GL_LIST_INLINE gl_list_node_t
865 gl_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
866 {
867 return ((const struct gl_list_impl_base *) list)->vtable
868 ->sortedlist_search (list, compar, elt);
869 }
870
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)
873 {
874 return ((const struct gl_list_impl_base *) list)->vtable
875 ->sortedlist_search_from_to (list, compar, start_index, end_index,
876 elt);
877 }
878
879 GL_LIST_INLINE size_t
880 gl_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
881 {
882 return ((const struct gl_list_impl_base *) list)->vtable
883 ->sortedlist_indexof (list, compar, elt);
884 }
885
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)
888 {
889 return ((const struct gl_list_impl_base *) list)->vtable
890 ->sortedlist_indexof_from_to (list, compar, start_index, end_index,
891 elt);
892 }
893
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)
896 {
897 return ((const struct gl_list_impl_base *) list)->vtable
898 ->sortedlist_nx_add (list, compar, elt);
899 }
900
901 GL_LIST_INLINE bool
902 gl_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
903 {
904 return ((const struct gl_list_impl_base *) list)->vtable
905 ->sortedlist_remove (list, compar, elt);
906 }
907
908 #ifdef __cplusplus
909 }
910 #endif
911
912 _GL_INLINE_HEADER_END
913
914 #endif /* _GL_LIST_H */