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