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