1 /* Abstract sequential list data type.
2 Copyright (C) 2006 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 2, or (at your option)
8 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, write to the Free Software Foundation,
17 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
18
19 #ifndef _GL_LIST_H
20 #define _GL_LIST_H
21
22 #include <stdbool.h>
23 #include <stddef.h>
24
25 #ifdef __cplusplus
26 extern "C" {
27 #endif
28
29
30 /* gl_list is an abstract list data type. It can contain any number of
31 objects ('void *' or 'const void *' pointers) in any given order.
32 Duplicates are allowed, but can optionally be forbidden.
33
34 There are several implementations of this list datatype, optimized for
35 different operations or for memory. You can start using the simplest list
36 implementation, GL_ARRAY_LIST, and switch to a different implementation
37 later, when you realize which operations are performed the most frequently.
38 The API of the different implementations is exactly the same; when
39 switching to a different implementation, you only have to change the
40 gl_list_create call.
41
42 The implementations are:
43 GL_ARRAY_LIST a growable array
44 GL_CARRAY_LIST a growable circular array
45 GL_LINKED_LIST a linked list
46 GL_AVLTREE_LIST a binary tree (AVL tree)
47 GL_RBTREE_LIST a binary tree (red-black tree)
48 GL_LINKEDHASH_LIST a hash table with a linked list
49 GL_AVLTREEHASH_LIST a hash table with a binary tree (AVL tree)
50 GL_RBTREEHASH_LIST a hash table with a binary tree (red-black tree)
51
52 The memory consumption is asymptotically the same: O(1) for every object
53 in the list. When looking more closely at the average memory consumed
54 for an object, GL_ARRAY_LIST is the most compact representation, and
55 GL_LINKEDHASH_LIST and GL_TREEHASH_LIST need more memory.
56
57 The guaranteed average performance of the operations is, for a list of
58 n elements:
59
60 Operation ARRAY LINKED TREE LINKEDHASH TREEHASH
61 CARRAY with|without with|without
62 duplicates duplicates
63
64 gl_list_size O(1) O(1) O(1) O(1) O(1)
65 gl_list_node_value O(1) O(1) O(1) O(1) O(1)
66 gl_list_next_node O(1) O(1) O(log n) O(1) O(log n)
67 gl_list_previous_node O(1) O(1) O(log n) O(1) O(log n)
68 gl_list_get_at O(1) O(n) O(log n) O(n) O(log n)
69 gl_list_set_at O(1) O(n) O(log n) O(n) O((log n)²)/O(log n)
70 gl_list_search O(n) O(n) O(n) O(n)/O(1) O(log n)/O(1)
71 gl_list_search_from O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n)
72 gl_list_search_from_to O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n)
73 gl_list_indexof O(n) O(n) O(n) O(n) O(log n)
74 gl_list_indexof_from O(n) O(n) O(n) O(n) O((log n)²)/O(log n)
75 gl_list_indexof_from_to O(n) O(n) O(n) O(n) O((log n)²)/O(log n)
76 gl_list_add_first O(n)/O(1) O(1) O(log n) O(1) O((log n)²)/O(log n)
77 gl_list_add_last O(1) O(1) O(log n) O(1) O((log n)²)/O(log n)
78 gl_list_add_before O(n) O(1) O(log n) O(1) O((log n)²)/O(log n)
79 gl_list_add_after O(n) O(1) O(log n) O(1) O((log n)²)/O(log n)
80 gl_list_add_at O(n) O(n) O(log n) O(n) O((log n)²)/O(log n)
81 gl_list_remove_node O(n) O(1) O(log n) O(n)/O(1) O((log n)²)/O(log n)
82 gl_list_remove_at O(n) O(n) O(log n) O(n) O((log n)²)/O(log n)
83 gl_list_remove O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n)
84 gl_list_iterator O(1) O(1) O(log n) O(1) O(log n)
85 gl_list_iterator_from_to O(1) O(n) O(log n) O(n) O(log n)
86 gl_list_iterator_next O(1) O(1) O(log n) O(1) O(log n)
87 gl_sortedlist_search O(log n) O(n) O(log n) O(n) O(log n)
88 gl_sortedlist_search_from O(log n) O(n) O(log n) O(n) O(log n)
89 gl_sortedlist_indexof O(log n) O(n) O(log n) O(n) O(log n)
90 gl_sortedlist_indexof_fro O(log n) O(n) O(log n) O(n) O(log n)
91 gl_sortedlist_add O(n) O(n) O(log n) O(n) O((log n)²)/O(log n)
92 gl_sortedlist_remove O(n) O(n) O(log n) O(n) O((log n)²)/O(log n)
93 */
94
95 /* -------------------------- gl_list_t Data Type -------------------------- */
96
97 /* Type of function used to compare two elements.
98 NULL denotes pointer comparison. */
99 typedef bool (*gl_listelement_equals_fn) (const void *elt1, const void *elt2);
100
101 /* Type of function used to compute a hash code.
102 NULL denotes a function that depends only on the pointer itself. */
103 typedef size_t (*gl_listelement_hashcode_fn) (const void *elt);
104
105 struct gl_list_impl;
106 /* Type representing an entire list. */
107 typedef struct gl_list_impl * gl_list_t;
108
109 struct gl_list_node_impl;
110 /* Type representing the position of an element in the list, in a way that
111 is more adapted to the list implementation than a plain index.
112 Note: It is invalidated by insertions and removals! */
113 typedef struct gl_list_node_impl * gl_list_node_t;
114
115 struct gl_list_implementation;
116 /* Type representing a list datatype implementation. */
117 typedef const struct gl_list_implementation * gl_list_implementation_t;
118
119 /* Create an empty list.
120 IMPLEMENTATION is one of GL_ARRAY_LIST, GL_CARRAY_LIST, GL_LINKED_LIST,
121 GL_AVLTREE_LIST, GL_RBTREE_LIST, GL_LINKEDHASH_LIST, GL_AVLTREEHASH_LIST,
122 GL_RBTREEHASH_LIST.
123 EQUALS_FN is an element comparison function or NULL.
124 HASHCODE_FN is an element hash code function or NULL.
125 ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in
126 the list. The implementation may verify this at runtime. */
127 extern gl_list_t gl_list_create_empty (gl_list_implementation_t implementation,
128 gl_listelement_equals_fn equals_fn,
129 gl_listelement_hashcode_fn hashcode_fn,
130 bool allow_duplicates);
131
132 /* Create a list with given contents.
133 IMPLEMENTATION is one of GL_ARRAY_LIST, GL_CARRAY_LIST, GL_LINKED_LIST,
134 GL_AVLTREE_LIST, GL_RBTREE_LIST, GL_LINKEDHASH_LIST, GL_AVLTREEHASH_LIST,
135 GL_RBTREEHASH_LIST.
136 EQUALS_FN is an element comparison function or NULL.
137 HASHCODE_FN is an element hash code function or NULL.
138 ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in
139 the list. The implementation may verify this at runtime.
140 COUNT is the number of initial elements.
141 CONTENTS[0..COUNT-1] is the initial contents. */
142 extern gl_list_t gl_list_create (gl_list_implementation_t implementation,
143 gl_listelement_equals_fn equals_fn,
144 gl_listelement_hashcode_fn hashcode_fn,
145 bool allow_duplicates,
146 size_t count, const void **contents);
147
148 /* Return the current number of elements in a list. */
149 extern size_t gl_list_size (gl_list_t list);
150
151 /* Return the element value represented by a list node. */
152 extern const void * gl_list_node_value (gl_list_t list, gl_list_node_t node);
153
154 /* Return the node immediately after the given node in the list, or NULL
155 if the given node is the last (rightmost) one in the list. */
156 extern gl_list_node_t gl_list_next_node (gl_list_t list, gl_list_node_t node);
157
158 /* Return the node immediately before the given node in the list, or NULL
159 if the given node is the first (leftmost) one in the list. */
160 extern gl_list_node_t gl_list_previous_node (gl_list_t list, gl_list_node_t node);
161
162 /* Return the element at a given position in the list.
163 POSITION must be >= 0 and < gl_list_size (list). */
164 extern const void * gl_list_get_at (gl_list_t list, size_t position);
165
166 /* Replace the element at a given position in the list.
167 POSITION must be >= 0 and < gl_list_size (list).
168 Return its node. */
169 extern gl_list_node_t gl_list_set_at (gl_list_t list, size_t position,
170 const void *elt);
171
172 /* Search whether an element is already in the list.
173 Return its node if found, or NULL if not present in the list. */
174 extern gl_list_node_t gl_list_search (gl_list_t list, const void *elt);
175
176 /* Search whether an element is already in the list,
177 at a position >= START_INDEX.
178 Return its node if found, or NULL if not present in the list. */
179 extern gl_list_node_t gl_list_search_from (gl_list_t list, size_t start_index,
180 const void *elt);
181
182 /* Search whether an element is already in the list,
183 at a position >= START_INDEX and < END_INDEX.
184 Return its node if found, or NULL if not present in the list. */
185 extern gl_list_node_t gl_list_search_from_to (gl_list_t list,
186 size_t start_index,
187 size_t end_index,
188 const void *elt);
189
190 /* Search whether an element is already in the list.
191 Return its position if found, or (size_t)(-1) if not present in the list. */
192 extern size_t gl_list_indexof (gl_list_t list, const void *elt);
193
194 /* Search whether an element is already in the list,
195 at a position >= START_INDEX.
196 Return its position if found, or (size_t)(-1) if not present in the list. */
197 extern size_t gl_list_indexof_from (gl_list_t list, size_t start_index,
198 const void *elt);
199
200 /* Search whether an element is already in the list,
201 at a position >= START_INDEX and < END_INDEX.
202 Return its position if found, or (size_t)(-1) if not present in the list. */
203 extern size_t gl_list_indexof_from_to (gl_list_t list,
204 size_t start_index, size_t end_index,
205 const void *elt);
206
207 /* Add an element as the first element of the list.
208 Return its node. */
209 extern gl_list_node_t gl_list_add_first (gl_list_t list, const void *elt);
210
211 /* Add an element as the last element of the list.
212 Return its node. */
213 extern gl_list_node_t gl_list_add_last (gl_list_t list, const void *elt);
214
215 /* Add an element before a given element node of the list.
216 Return its node. */
217 extern gl_list_node_t gl_list_add_before (gl_list_t list, gl_list_node_t node,
218 const void *elt);
219
220 /* Add an element after a given element node of the list.
221 Return its node. */
222 extern gl_list_node_t gl_list_add_after (gl_list_t list, gl_list_node_t node,
223 const void *elt);
224
225 /* Add an element add a given position in the list.
226 POSITION must be >= 0 and <= gl_list_size (list). */
227 extern gl_list_node_t gl_list_add_at (gl_list_t list, size_t position,
228 const void *elt);
229
230 /* Remove an element from the list.
231 Return true. */
232 extern bool gl_list_remove_node (gl_list_t list, gl_list_node_t node);
233
234 /* Remove an element at a given position from the list.
235 POSITION must be >= 0 and < gl_list_size (list).
236 Return true. */
237 extern bool gl_list_remove_at (gl_list_t list, size_t position);
238
239 /* Search and remove an element from the list.
240 Return true if it was found and removed. */
241 extern bool gl_list_remove (gl_list_t list, const void *elt);
242
243 /* Free an entire list.
244 (But this call does not free the elements of the list.) */
245 extern void gl_list_free (gl_list_t list);
246
247 /* --------------------- gl_list_iterator_t Data Type --------------------- */
248
249 /* Functions for iterating through a list. */
250
251 /* Type of an iterator that traverses a list.
252 This is a fixed-size struct, so that creation of an iterator doesn't need
253 memory allocation on the heap. */
254 typedef struct
255 {
256 /* For fast dispatch of gl_list_iterator_next. */
257 const struct gl_list_implementation *vtable;
258 /* For detecting whether the last returned element was removed. */
259 gl_list_t list;
260 size_t count;
261 /* Other, implementation-private fields. */
262 void *p; void *q;
263 size_t i; size_t j;
264 } gl_list_iterator_t;
265
266 /* Create an iterator traversing a list.
267 The list contents must not be modified while the iterator is in use,
268 except for replacing or removing the last returned element. */
269 extern gl_list_iterator_t gl_list_iterator (gl_list_t list);
270
271 /* Create an iterator traversing the element with indices i,
272 start_index <= i < end_index, of a list.
273 The list contents must not be modified while the iterator is in use,
274 except for replacing or removing the last returned element. */
275 extern gl_list_iterator_t gl_list_iterator_from_to (gl_list_t list,
276 size_t start_index,
277 size_t end_index);
278
279 /* If there is a next element, store the next element in *ELTP, store its
280 node in *NODEP if NODEP is non-NULL, advance the iterator and return true.
281 Otherwise, return false. */
282 extern bool gl_list_iterator_next (gl_list_iterator_t *iterator,
283 const void **eltp, gl_list_node_t *nodep);
284
285 /* Free an iterator. */
286 extern void gl_list_iterator_free (gl_list_iterator_t *iterator);
287
288 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
289
290 /* The following functions are for lists without duplicates where the
291 order is given by a sort criterion. */
292
293 /* Type of function used to compare two elements. Same as for qsort().
294 NULL denotes pointer comparison. */
295 typedef int (*gl_listelement_compar_fn) (const void *elt1, const void *elt2);
296
297 /* Search whether an element is already in the list.
298 The list is assumed to be sorted with COMPAR.
299 Return its node if found, or NULL if not present in the list.
300 If the list contains several copies of ELT, the node of the leftmost one is
301 returned. */
302 extern gl_list_node_t gl_sortedlist_search (gl_list_t list,
303 gl_listelement_compar_fn compar,
304 const void *elt);
305
306 /* Search whether an element is already in the list.
307 The list is assumed to be sorted with COMPAR.
308 Only list elements with indices >= START_INDEX and < END_INDEX are
309 considered; the implementation uses these bounds to minimize the number
310 of COMPAR invocations.
311 Return its node if found, or NULL if not present in the list.
312 If the list contains several copies of ELT, the node of the leftmost one is
313 returned. */
314 extern gl_list_node_t gl_sortedlist_search_from_to (gl_list_t list,
315 gl_listelement_compar_fn compar,
316 size_t start_index,
317 size_t end_index,
318 const void *elt);
319
320 /* Search whether an element is already in the list.
321 The list is assumed to be sorted with COMPAR.
322 Return its position if found, or (size_t)(-1) if not present in the list.
323 If the list contains several copies of ELT, the position of the leftmost one
324 is returned. */
325 extern size_t gl_sortedlist_indexof (gl_list_t list,
326 gl_listelement_compar_fn compar,
327 const void *elt);
328
329 /* Search whether an element is already in the list.
330 The list is assumed to be sorted with COMPAR.
331 Only list elements with indices >= START_INDEX and < END_INDEX are
332 considered; the implementation uses these bounds to minimize the number
333 of COMPAR invocations.
334 Return its position if found, or (size_t)(-1) if not present in the list.
335 If the list contains several copies of ELT, the position of the leftmost one
336 is returned. */
337 extern size_t gl_sortedlist_indexof_from_to (gl_list_t list,
338 gl_listelement_compar_fn compar,
339 size_t start_index,
340 size_t end_index,
341 const void *elt);
342
343 /* Add an element at the appropriate position in the list.
344 The list is assumed to be sorted with COMPAR.
345 Return its node. */
346 extern gl_list_node_t gl_sortedlist_add (gl_list_t list,
347 gl_listelement_compar_fn compar,
348 const void *elt);
349
350 /* Search and remove an element from the list.
351 The list is assumed to be sorted with COMPAR.
352 Return true if it was found and removed.
353 If the list contains several copies of ELT, only the leftmost one is
354 removed. */
355 extern bool gl_sortedlist_remove (gl_list_t list,
356 gl_listelement_compar_fn compar,
357 const void *elt);
358
359 /* ------------------------ Implementation Details ------------------------ */
360
361 struct gl_list_implementation
362 {
363 /* gl_list_t functions. */
364 gl_list_t (*create_empty) (gl_list_implementation_t implementation,
365 gl_listelement_equals_fn equals_fn,
366 gl_listelement_hashcode_fn hashcode_fn,
367 bool allow_duplicates);
368 gl_list_t (*create) (gl_list_implementation_t implementation,
369 gl_listelement_equals_fn equals_fn,
370 gl_listelement_hashcode_fn hashcode_fn,
371 bool allow_duplicates,
372 size_t count, const void **contents);
373 size_t (*size) (gl_list_t list);
374 const void * (*node_value) (gl_list_t list, gl_list_node_t node);
375 gl_list_node_t (*next_node) (gl_list_t list, gl_list_node_t node);
376 gl_list_node_t (*previous_node) (gl_list_t list, gl_list_node_t node);
377 const void * (*get_at) (gl_list_t list, size_t position);
378 gl_list_node_t (*set_at) (gl_list_t list, size_t position, const void *elt);
379 gl_list_node_t (*search_from_to) (gl_list_t list, size_t start_index,
380 size_t end_index, const void *elt);
381 size_t (*indexof_from_to) (gl_list_t list, size_t start_index,
382 size_t end_index, const void *elt);
383 gl_list_node_t (*add_first) (gl_list_t list, const void *elt);
384 gl_list_node_t (*add_last) (gl_list_t list, const void *elt);
385 gl_list_node_t (*add_before) (gl_list_t list, gl_list_node_t node,
386 const void *elt);
387 gl_list_node_t (*add_after) (gl_list_t list, gl_list_node_t node,
388 const void *elt);
389 gl_list_node_t (*add_at) (gl_list_t list, size_t position,
390 const void *elt);
391 bool (*remove_node) (gl_list_t list, gl_list_node_t node);
392 bool (*remove_at) (gl_list_t list, size_t position);
393 bool (*remove) (gl_list_t list, const void *elt);
394 void (*list_free) (gl_list_t list);
395 /* gl_list_iterator_t functions. */
396 gl_list_iterator_t (*iterator) (gl_list_t list);
397 gl_list_iterator_t (*iterator_from_to) (gl_list_t list,
398 size_t start_index,
399 size_t end_index);
400 bool (*iterator_next) (gl_list_iterator_t *iterator,
401 const void **eltp, gl_list_node_t *nodep);
402 void (*iterator_free) (gl_list_iterator_t *iterator);
403 /* Sorted gl_list_t functions. */
404 gl_list_node_t (*sortedlist_search) (gl_list_t list,
405 gl_listelement_compar_fn compar,
406 const void *elt);
407 gl_list_node_t (*sortedlist_search_from_to) (gl_list_t list,
408 gl_listelement_compar_fn compar,
409 size_t start_index,
410 size_t end_index,
411 const void *elt);
412 size_t (*sortedlist_indexof) (gl_list_t list,
413 gl_listelement_compar_fn compar,
414 const void *elt);
415 size_t (*sortedlist_indexof_from_to) (gl_list_t list,
416 gl_listelement_compar_fn compar,
417 size_t start_index, size_t end_index,
418 const void *elt);
419 gl_list_node_t (*sortedlist_add) (gl_list_t list,
420 gl_listelement_compar_fn compar,
421 const void *elt);
422 bool (*sortedlist_remove) (gl_list_t list,
423 gl_listelement_compar_fn compar,
424 const void *elt);
425 };
426
427 struct gl_list_impl_base
428 {
429 const struct gl_list_implementation *vtable;
430 gl_listelement_equals_fn equals_fn;
431 gl_listelement_hashcode_fn hashcode_fn;
432 bool allow_duplicates;
433 };
434
435 #if HAVE_INLINE
436
437 /* Define all functions of this file as inline accesses to the
438 struct gl_list_implementation.
439 Use #define to avoid a warning because of extern vs. static. */
440
441 # define gl_list_create_empty gl_list_create_empty_inline
442 static inline gl_list_t
gl_list_create_empty(gl_list_implementation_t implementation,gl_listelement_equals_fn equals_fn,gl_listelement_hashcode_fn hashcode_fn,bool allow_duplicates)443 gl_list_create_empty (gl_list_implementation_t implementation,
444 gl_listelement_equals_fn equals_fn,
445 gl_listelement_hashcode_fn hashcode_fn,
446 bool allow_duplicates)
447 {
448 return implementation->create_empty (implementation, equals_fn, hashcode_fn,
449 allow_duplicates);
450 }
451
452 # define gl_list_create gl_list_create_inline
453 static inline gl_list_t
gl_list_create(gl_list_implementation_t implementation,gl_listelement_equals_fn equals_fn,gl_listelement_hashcode_fn hashcode_fn,bool allow_duplicates,size_t count,const void ** contents)454 gl_list_create (gl_list_implementation_t implementation,
455 gl_listelement_equals_fn equals_fn,
456 gl_listelement_hashcode_fn hashcode_fn,
457 bool allow_duplicates,
458 size_t count, const void **contents)
459 {
460 return implementation->create (implementation, equals_fn, hashcode_fn,
461 allow_duplicates, count, contents);
462 }
463
464 # define gl_list_size gl_list_size_inline
465 static inline size_t
gl_list_size(gl_list_t list)466 gl_list_size (gl_list_t list)
467 {
468 return ((const struct gl_list_impl_base *) list)->vtable
469 ->size (list);
470 }
471
472 # define gl_list_node_value gl_list_node_value_inline
473 static inline const void *
gl_list_node_value(gl_list_t list,gl_list_node_t node)474 gl_list_node_value (gl_list_t list, gl_list_node_t node)
475 {
476 return ((const struct gl_list_impl_base *) list)->vtable
477 ->node_value (list, node);
478 }
479
480 # define gl_list_next_node gl_list_next_node_inline
481 static inline gl_list_node_t
gl_list_next_node(gl_list_t list,gl_list_node_t node)482 gl_list_next_node (gl_list_t list, gl_list_node_t node)
483 {
484 return ((const struct gl_list_impl_base *) list)->vtable
485 ->next_node (list, node);
486 }
487
488 # define gl_list_previous_node gl_list_previous_node_inline
489 static inline gl_list_node_t
gl_list_previous_node(gl_list_t list,gl_list_node_t node)490 gl_list_previous_node (gl_list_t list, gl_list_node_t node)
491 {
492 return ((const struct gl_list_impl_base *) list)->vtable
493 ->previous_node (list, node);
494 }
495
496 # define gl_list_get_at gl_list_get_at_inline
497 static inline const void *
gl_list_get_at(gl_list_t list,size_t position)498 gl_list_get_at (gl_list_t list, size_t position)
499 {
500 return ((const struct gl_list_impl_base *) list)->vtable
501 ->get_at (list, position);
502 }
503
504 # define gl_list_set_at gl_list_set_at_inline
505 static inline gl_list_node_t
gl_list_set_at(gl_list_t list,size_t position,const void * elt)506 gl_list_set_at (gl_list_t list, size_t position, const void *elt)
507 {
508 return ((const struct gl_list_impl_base *) list)->vtable
509 ->set_at (list, position, elt);
510 }
511
512 # define gl_list_search gl_list_search_inline
513 static inline gl_list_node_t
gl_list_search(gl_list_t list,const void * elt)514 gl_list_search (gl_list_t list, const void *elt)
515 {
516 size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
517 return ((const struct gl_list_impl_base *) list)->vtable
518 ->search_from_to (list, 0, size, elt);
519 }
520
521 # define gl_list_search_from gl_list_search_from_inline
522 static inline gl_list_node_t
gl_list_search_from(gl_list_t list,size_t start_index,const void * elt)523 gl_list_search_from (gl_list_t list, size_t start_index, const void *elt)
524 {
525 size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
526 return ((const struct gl_list_impl_base *) list)->vtable
527 ->search_from_to (list, start_index, size, elt);
528 }
529
530 # define gl_list_search_from_to gl_list_search_from_to_inline
531 static 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)532 gl_list_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
533 const void *elt)
534 {
535 return ((const struct gl_list_impl_base *) list)->vtable
536 ->search_from_to (list, start_index, end_index, elt);
537 }
538
539 # define gl_list_indexof gl_list_indexof_inline
540 static inline size_t
gl_list_indexof(gl_list_t list,const void * elt)541 gl_list_indexof (gl_list_t list, const void *elt)
542 {
543 size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
544 return ((const struct gl_list_impl_base *) list)->vtable
545 ->indexof_from_to (list, 0, size, elt);
546 }
547
548 # define gl_list_indexof_from gl_list_indexof_from_inline
549 static inline size_t
gl_list_indexof_from(gl_list_t list,size_t start_index,const void * elt)550 gl_list_indexof_from (gl_list_t list, size_t start_index, const void *elt)
551 {
552 size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
553 return ((const struct gl_list_impl_base *) list)->vtable
554 ->indexof_from_to (list, start_index, size, elt);
555 }
556
557 # define gl_list_indexof_from_to gl_list_indexof_from_to_inline
558 static inline size_t
gl_list_indexof_from_to(gl_list_t list,size_t start_index,size_t end_index,const void * elt)559 gl_list_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
560 const void *elt)
561 {
562 return ((const struct gl_list_impl_base *) list)->vtable
563 ->indexof_from_to (list, start_index, end_index, elt);
564 }
565
566 # define gl_list_add_first gl_list_add_first_inline
567 static inline gl_list_node_t
gl_list_add_first(gl_list_t list,const void * elt)568 gl_list_add_first (gl_list_t list, const void *elt)
569 {
570 return ((const struct gl_list_impl_base *) list)->vtable
571 ->add_first (list, elt);
572 }
573
574 # define gl_list_add_last gl_list_add_last_inline
575 static inline gl_list_node_t
gl_list_add_last(gl_list_t list,const void * elt)576 gl_list_add_last (gl_list_t list, const void *elt)
577 {
578 return ((const struct gl_list_impl_base *) list)->vtable
579 ->add_last (list, elt);
580 }
581
582 # define gl_list_add_before gl_list_add_before_inline
583 static inline gl_list_node_t
gl_list_add_before(gl_list_t list,gl_list_node_t node,const void * elt)584 gl_list_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
585 {
586 return ((const struct gl_list_impl_base *) list)->vtable
587 ->add_before (list, node, elt);
588 }
589
590 # define gl_list_add_after gl_list_add_after_inline
591 static inline gl_list_node_t
gl_list_add_after(gl_list_t list,gl_list_node_t node,const void * elt)592 gl_list_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
593 {
594 return ((const struct gl_list_impl_base *) list)->vtable
595 ->add_after (list, node, elt);
596 }
597
598 # define gl_list_add_at gl_list_add_at_inline
599 static inline gl_list_node_t
gl_list_add_at(gl_list_t list,size_t position,const void * elt)600 gl_list_add_at (gl_list_t list, size_t position, const void *elt)
601 {
602 return ((const struct gl_list_impl_base *) list)->vtable
603 ->add_at (list, position, elt);
604 }
605
606 # define gl_list_remove_node gl_list_remove_node_inline
607 static inline bool
gl_list_remove_node(gl_list_t list,gl_list_node_t node)608 gl_list_remove_node (gl_list_t list, gl_list_node_t node)
609 {
610 return ((const struct gl_list_impl_base *) list)->vtable
611 ->remove_node (list, node);
612 }
613
614 # define gl_list_remove_at gl_list_remove_at_inline
615 static inline bool
gl_list_remove_at(gl_list_t list,size_t position)616 gl_list_remove_at (gl_list_t list, size_t position)
617 {
618 return ((const struct gl_list_impl_base *) list)->vtable
619 ->remove_at (list, position);
620 }
621
622 # define gl_list_remove gl_list_remove_inline
623 static inline bool
gl_list_remove(gl_list_t list,const void * elt)624 gl_list_remove (gl_list_t list, const void *elt)
625 {
626 return ((const struct gl_list_impl_base *) list)->vtable
627 ->remove (list, elt);
628 }
629
630 # define gl_list_free gl_list_free_inline
631 static inline void
gl_list_free(gl_list_t list)632 gl_list_free (gl_list_t list)
633 {
634 ((const struct gl_list_impl_base *) list)->vtable->list_free (list);
635 }
636
637 # define gl_list_iterator gl_list_iterator_inline
638 static inline gl_list_iterator_t
gl_list_iterator(gl_list_t list)639 gl_list_iterator (gl_list_t list)
640 {
641 return ((const struct gl_list_impl_base *) list)->vtable
642 ->iterator (list);
643 }
644
645 # define gl_list_iterator_from_to gl_list_iterator_from_to_inline
646 static inline gl_list_iterator_t
gl_list_iterator_from_to(gl_list_t list,size_t start_index,size_t end_index)647 gl_list_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
648 {
649 return ((const struct gl_list_impl_base *) list)->vtable
650 ->iterator_from_to (list, start_index, end_index);
651 }
652
653 # define gl_list_iterator_next gl_list_iterator_next_inline
654 static inline bool
gl_list_iterator_next(gl_list_iterator_t * iterator,const void ** eltp,gl_list_node_t * nodep)655 gl_list_iterator_next (gl_list_iterator_t *iterator,
656 const void **eltp, gl_list_node_t *nodep)
657 {
658 return iterator->vtable->iterator_next (iterator, eltp, nodep);
659 }
660
661 # define gl_list_iterator_free gl_list_iterator_free_inline
662 static inline void
gl_list_iterator_free(gl_list_iterator_t * iterator)663 gl_list_iterator_free (gl_list_iterator_t *iterator)
664 {
665 iterator->vtable->iterator_free (iterator);
666 }
667
668 # define gl_sortedlist_search gl_sortedlist_search_inline
669 static inline gl_list_node_t
gl_sortedlist_search(gl_list_t list,gl_listelement_compar_fn compar,const void * elt)670 gl_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
671 {
672 return ((const struct gl_list_impl_base *) list)->vtable
673 ->sortedlist_search (list, compar, elt);
674 }
675
676 # define gl_sortedlist_search_from_to gl_sortedlist_search_from_to_inline
677 static 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)678 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)
679 {
680 return ((const struct gl_list_impl_base *) list)->vtable
681 ->sortedlist_search_from_to (list, compar, start_index, end_index,
682 elt);
683 }
684
685 # define gl_sortedlist_indexof gl_sortedlist_indexof_inline
686 static inline size_t
gl_sortedlist_indexof(gl_list_t list,gl_listelement_compar_fn compar,const void * elt)687 gl_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
688 {
689 return ((const struct gl_list_impl_base *) list)->vtable
690 ->sortedlist_indexof (list, compar, elt);
691 }
692
693 # define gl_sortedlist_indexof_from_to gl_sortedlist_indexof_from_to_inline
694 static 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)695 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)
696 {
697 return ((const struct gl_list_impl_base *) list)->vtable
698 ->sortedlist_indexof_from_to (list, compar, start_index, end_index,
699 elt);
700 }
701
702 # define gl_sortedlist_add gl_sortedlist_add_inline
703 static inline gl_list_node_t
gl_sortedlist_add(gl_list_t list,gl_listelement_compar_fn compar,const void * elt)704 gl_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
705 {
706 return ((const struct gl_list_impl_base *) list)->vtable
707 ->sortedlist_add (list, compar, elt);
708 }
709
710 # define gl_sortedlist_remove gl_sortedlist_remove_inline
711 static inline bool
gl_sortedlist_remove(gl_list_t list,gl_listelement_compar_fn compar,const void * elt)712 gl_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
713 {
714 return ((const struct gl_list_impl_base *) list)->vtable
715 ->sortedlist_remove (list, compar, elt);
716 }
717
718 #endif
719
720 #ifdef __cplusplus
721 }
722 #endif
723
724 #endif /* _GL_LIST_H */
725