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