Coverage Report

Created: 2025-03-06 07:58

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