summaryrefslogtreecommitdiff
path: root/draft/mcastseed/lib/gl_list.h
blob: c9d05b0d4dafc708db16a8a818a21ff4a1613626 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
/* Abstract sequential list data type.  -*- coding: utf-8 -*-
   Copyright (C) 2006-2016 Free Software Foundation, Inc.
   Written by Bruno Haible <bruno@clisp.org>, 2006.

   This program is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 3 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */

#ifndef _GL_LIST_H
#define _GL_LIST_H

#include <stdbool.h>
#include <stddef.h>

#ifndef _GL_INLINE_HEADER_BEGIN
 #error "Please include config.h first."
#endif
_GL_INLINE_HEADER_BEGIN
#ifndef GL_LIST_INLINE
# define GL_LIST_INLINE _GL_INLINE
#endif

#ifdef __cplusplus
extern "C" {
#endif


/* gl_list is an abstract list data type.  It can contain any number of
   objects ('void *' or 'const void *' pointers) in any given order.
   Duplicates are allowed, but can optionally be forbidden.

   There are several implementations of this list datatype, optimized for
   different operations or for memory.  You can start using the simplest list
   implementation, GL_ARRAY_LIST, and switch to a different implementation
   later, when you realize which operations are performed the most frequently.
   The API of the different implementations is exactly the same; when
   switching to a different implementation, you only have to change the
   gl_list_create call.

   The implementations are:
     GL_ARRAY_LIST        a growable array
     GL_CARRAY_LIST       a growable circular array
     GL_LINKED_LIST       a linked list
     GL_AVLTREE_LIST      a binary tree (AVL tree)
     GL_RBTREE_LIST       a binary tree (red-black tree)
     GL_LINKEDHASH_LIST   a hash table with a linked list
     GL_AVLTREEHASH_LIST  a hash table with a binary tree (AVL tree)
     GL_RBTREEHASH_LIST   a hash table with a binary tree (red-black tree)

   The memory consumption is asymptotically the same: O(1) for every object
   in the list.  When looking more closely at the average memory consumed
   for an object, GL_ARRAY_LIST is the most compact representation, and
   GL_LINKEDHASH_LIST and GL_TREEHASH_LIST need more memory.

   The guaranteed average performance of the operations is, for a list of
   n elements:

   Operation                  ARRAY    LINKED    TREE    LINKEDHASH   TREEHASH
                              CARRAY                   with|without with|without
                                                         duplicates  duplicates

   gl_list_size                O(1)     O(1)     O(1)      O(1)         O(1)
   gl_list_node_value          O(1)     O(1)     O(1)      O(1)         O(1)
   gl_list_node_set_value      O(1)     O(1)     O(1)      O(1)    O((log n)²)/O(1)
   gl_list_next_node           O(1)     O(1)   O(log n)    O(1)       O(log n)
   gl_list_previous_node       O(1)     O(1)   O(log n)    O(1)       O(log n)
   gl_list_get_at              O(1)     O(n)   O(log n)    O(n)       O(log n)
   gl_list_set_at              O(1)     O(n)   O(log n)    O(n)    O((log n)²)/O(log n)
   gl_list_search              O(n)     O(n)     O(n)    O(n)/O(1)    O(log n)/O(1)
   gl_list_search_from         O(n)     O(n)     O(n)    O(n)/O(1) O((log n)²)/O(log n)
   gl_list_search_from_to      O(n)     O(n)     O(n)    O(n)/O(1) O((log n)²)/O(log n)
   gl_list_indexof             O(n)     O(n)     O(n)      O(n)       O(log n)
   gl_list_indexof_from        O(n)     O(n)     O(n)      O(n)    O((log n)²)/O(log n)
   gl_list_indexof_from_to     O(n)     O(n)     O(n)      O(n)    O((log n)²)/O(log n)
   gl_list_add_first         O(n)/O(1)  O(1)   O(log n)    O(1)    O((log n)²)/O(log n)
   gl_list_add_last            O(1)     O(1)   O(log n)    O(1)    O((log n)²)/O(log n)
   gl_list_add_before          O(n)     O(1)   O(log n)    O(1)    O((log n)²)/O(log n)
   gl_list_add_after           O(n)     O(1)   O(log n)    O(1)    O((log n)²)/O(log n)
   gl_list_add_at              O(n)     O(n)   O(log n)    O(n)    O((log n)²)/O(log n)
   gl_list_remove_node         O(n)     O(1)   O(log n)  O(n)/O(1) O((log n)²)/O(log n)
   gl_list_remove_at           O(n)     O(n)   O(log n)    O(n)    O((log n)²)/O(log n)
   gl_list_remove              O(n)     O(n)     O(n)    O(n)/O(1) O((log n)²)/O(log n)
   gl_list_iterator            O(1)     O(1)   O(log n)    O(1)       O(log n)
   gl_list_iterator_from_to    O(1)     O(n)   O(log n)    O(n)       O(log n)
   gl_list_iterator_next       O(1)     O(1)   O(log n)    O(1)       O(log n)
   gl_sortedlist_search      O(log n)   O(n)   O(log n)    O(n)       O(log n)
   gl_sortedlist_search_from O(log n)   O(n)   O(log n)    O(n)       O(log n)
   gl_sortedlist_indexof     O(log n)   O(n)   O(log n)    O(n)       O(log n)
   gl_sortedlist_indexof_fro O(log n)   O(n)   O(log n)    O(n)       O(log n)
   gl_sortedlist_add           O(n)     O(n)   O(log n)    O(n)    O((log n)²)/O(log n)
   gl_sortedlist_remove        O(n)     O(n)   O(log n)    O(n)    O((log n)²)/O(log n)
 */

/* -------------------------- gl_list_t Data Type -------------------------- */

/* Type of function used to compare two elements.
   NULL denotes pointer comparison.  */
typedef bool (*gl_listelement_equals_fn) (const void *elt1, const void *elt2);

/* Type of function used to compute a hash code.
   NULL denotes a function that depends only on the pointer itself.  */
typedef size_t (*gl_listelement_hashcode_fn) (const void *elt);

/* Type of function used to dispose an element once it's removed from a list.
   NULL denotes a no-op.  */
typedef void (*gl_listelement_dispose_fn) (const void *elt);

struct gl_list_impl;
/* Type representing an entire list.  */
typedef struct gl_list_impl * gl_list_t;

struct gl_list_node_impl;
/* Type representing the position of an element in the list, in a way that
   is more adapted to the list implementation than a plain index.
   Note: It is invalidated by insertions and removals!  */
typedef struct gl_list_node_impl * gl_list_node_t;

struct gl_list_implementation;
/* Type representing a list datatype implementation.  */
typedef const struct gl_list_implementation * gl_list_implementation_t;

#if 0 /* Unless otherwise specified, these are defined inline below.  */

/* Create an empty list.
   IMPLEMENTATION is one of GL_ARRAY_LIST, GL_CARRAY_LIST, GL_LINKED_LIST,
   GL_AVLTREE_LIST, GL_RBTREE_LIST, GL_LINKEDHASH_LIST, GL_AVLTREEHASH_LIST,
   GL_RBTREEHASH_LIST.
   EQUALS_FN is an element comparison function or NULL.
   HASHCODE_FN is an element hash code function or NULL.
   DISPOSE_FN is an element disposal function or NULL.
   ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in
   the list. The implementation may verify this at runtime.  */
/* declared in gl_xlist.h */
extern gl_list_t gl_list_create_empty (gl_list_implementation_t implementation,
                                       gl_listelement_equals_fn equals_fn,
                                       gl_listelement_hashcode_fn hashcode_fn,
                                       gl_listelement_dispose_fn dispose_fn,
                                       bool allow_duplicates);
/* Likewise.  Return NULL upon out-of-memory.  */
extern gl_list_t gl_list_nx_create_empty (gl_list_implementation_t implementation,
                                          gl_listelement_equals_fn equals_fn,
                                          gl_listelement_hashcode_fn hashcode_fn,
                                          gl_listelement_dispose_fn dispose_fn,
                                          bool allow_duplicates);

/* Create a list with given contents.
   IMPLEMENTATION is one of GL_ARRAY_LIST, GL_CARRAY_LIST, GL_LINKED_LIST,
   GL_AVLTREE_LIST, GL_RBTREE_LIST, GL_LINKEDHASH_LIST, GL_AVLTREEHASH_LIST,
   GL_RBTREEHASH_LIST.
   EQUALS_FN is an element comparison function or NULL.
   HASHCODE_FN is an element hash code function or NULL.
   DISPOSE_FN is an element disposal function or NULL.
   ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in
   the list. The implementation may verify this at runtime.
   COUNT is the number of initial elements.
   CONTENTS[0..COUNT-1] is the initial contents.  */
/* declared in gl_xlist.h */
extern gl_list_t gl_list_create (gl_list_implementation_t implementation,
                                 gl_listelement_equals_fn equals_fn,
                                 gl_listelement_hashcode_fn hashcode_fn,
                                 gl_listelement_dispose_fn dispose_fn,
                                 bool allow_duplicates,
                                 size_t count, const void **contents);
/* Likewise.  Return NULL upon out-of-memory.  */
extern gl_list_t gl_list_nx_create (gl_list_implementation_t implementation,
                                    gl_listelement_equals_fn equals_fn,
                                    gl_listelement_hashcode_fn hashcode_fn,
                                    gl_listelement_dispose_fn dispose_fn,
                                    bool allow_duplicates,
                                    size_t count, const void **contents);

/* Return the current number of elements in a list.  */
extern size_t gl_list_size (gl_list_t list);

/* Return the element value represented by a list node.  */
extern const void * gl_list_node_value (gl_list_t list, gl_list_node_t node);

/* Replace the element value represented by a list node.  */
/* declared in gl_xlist.h */
extern void gl_list_node_set_value (gl_list_t list, gl_list_node_t node,
                                    const void *elt);
/* Likewise.  Return 0 upon success, -1 upon out-of-memory.  */
extern int gl_list_node_nx_set_value (gl_list_t list, gl_list_node_t node,
                                      const void *elt)
#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
  __attribute__ ((__warn_unused_result__))
#endif
  ;

/* Return the node immediately after the given node in the list, or NULL
   if the given node is the last (rightmost) one in the list.  */
extern gl_list_node_t gl_list_next_node (gl_list_t list, gl_list_node_t node);

/* Return the node immediately before the given node in the list, or NULL
   if the given node is the first (leftmost) one in the list.  */
extern gl_list_node_t gl_list_previous_node (gl_list_t list, gl_list_node_t node);

/* Return the element at a given position in the list.
   POSITION must be >= 0 and < gl_list_size (list).  */
extern const void * gl_list_get_at (gl_list_t list, size_t position);

/* Replace the element at a given position in the list.
   POSITION must be >= 0 and < gl_list_size (list).
   Return its node.  */
/* declared in gl_xlist.h */
extern gl_list_node_t gl_list_set_at (gl_list_t list, size_t position,
                                      const void *elt);
/* Likewise.  Return NULL upon out-of-memory.  */
extern gl_list_node_t gl_list_nx_set_at (gl_list_t list, size_t position,
                                         const void *elt)
#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
  __attribute__ ((__warn_unused_result__))
#endif
  ;

/* Search whether an element is already in the list.
   Return its node if found, or NULL if not present in the list.  */
extern gl_list_node_t gl_list_search (gl_list_t list, const void *elt);

/* Search whether an element is already in the list,
   at a position >= START_INDEX.
   Return its node if found, or NULL if not present in the list.  */
extern gl_list_node_t gl_list_search_from (gl_list_t list, size_t start_index,
                                           const void *elt);

/* Search whether an element is already in the list,
   at a position >= START_INDEX and < END_INDEX.
   Return its node if found, or NULL if not present in the list.  */
extern gl_list_node_t gl_list_search_from_to (gl_list_t list,
                                              size_t start_index,
                                              size_t end_index,
                                              const void *elt);

/* Search whether an element is already in the list.
   Return its position if found, or (size_t)(-1) if not present in the list.  */
extern size_t gl_list_indexof (gl_list_t list, const void *elt);

/* Search whether an element is already in the list,
   at a position >= START_INDEX.
   Return its position if found, or (size_t)(-1) if not present in the list.  */
extern size_t gl_list_indexof_from (gl_list_t list, size_t start_index,
                                    const void *elt);

/* Search whether an element is already in the list,
   at a position >= START_INDEX and < END_INDEX.
   Return its position if found, or (size_t)(-1) if not present in the list.  */
extern size_t gl_list_indexof_from_to (gl_list_t list,
                                       size_t start_index, size_t end_index,
                                       const void *elt);

/* Add an element as the first element of the list.
   Return its node.  */
/* declared in gl_xlist.h */
extern gl_list_node_t gl_list_add_first (gl_list_t list, const void *elt);
/* Likewise.  Return NULL upon out-of-memory.  */
extern gl_list_node_t gl_list_nx_add_first (gl_list_t list, const void *elt)
#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
  __attribute__ ((__warn_unused_result__))
#endif
  ;

/* Add an element as the last element of the list.
   Return its node.  */
/* declared in gl_xlist.h */
extern gl_list_node_t gl_list_add_last (gl_list_t list, const void *elt);
/* Likewise.  Return NULL upon out-of-memory.  */
extern gl_list_node_t gl_list_nx_add_last (gl_list_t list, const void *elt)
#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
  __attribute__ ((__warn_unused_result__))
#endif
  ;

/* Add an element before a given element node of the list.
   Return its node.  */
/* declared in gl_xlist.h */
extern gl_list_node_t gl_list_add_before (gl_list_t list, gl_list_node_t node,
                                          const void *elt);
/* Likewise.  Return NULL upon out-of-memory.  */
extern gl_list_node_t gl_list_nx_add_before (gl_list_t list,
                                             gl_list_node_t node,
                                             const void *elt)
#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
  __attribute__ ((__warn_unused_result__))
#endif
  ;

/* Add an element after a given element node of the list.
   Return its node.  */
/* declared in gl_xlist.h */
extern gl_list_node_t gl_list_add_after (gl_list_t list, gl_list_node_t node,
                                         const void *elt);
/* Likewise.  Return NULL upon out-of-memory.  */
extern gl_list_node_t gl_list_nx_add_after (gl_list_t list, gl_list_node_t node,
                                            const void *elt)
#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
  __attribute__ ((__warn_unused_result__))
#endif
  ;

/* Add an element at a given position in the list.
   POSITION must be >= 0 and <= gl_list_size (list).  */
/* declared in gl_xlist.h */
extern gl_list_node_t gl_list_add_at (gl_list_t list, size_t position,
                                      const void *elt);
/* Likewise.  Return NULL upon out-of-memory.  */
extern gl_list_node_t gl_list_nx_add_at (gl_list_t list, size_t position,
                                         const void *elt)
#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
  __attribute__ ((__warn_unused_result__))
#endif
  ;

/* Remove an element from the list.
   Return true.  */
extern bool gl_list_remove_node (gl_list_t list, gl_list_node_t node);

/* Remove an element at a given position from the list.
   POSITION must be >= 0 and < gl_list_size (list).
   Return true.  */
extern bool gl_list_remove_at (gl_list_t list, size_t position);

/* Search and remove an element from the list.
   Return true if it was found and removed.  */
extern bool gl_list_remove (gl_list_t list, const void *elt);

/* Free an entire list.
   (But this call does not free the elements of the list.)  */
extern void gl_list_free (gl_list_t list);

#endif /* End of inline and gl_xlist.h-defined functions.  */

/* --------------------- gl_list_iterator_t Data Type --------------------- */

/* Functions for iterating through a list.  */

/* Type of an iterator that traverses a list.
   This is a fixed-size struct, so that creation of an iterator doesn't need
   memory allocation on the heap.  */
typedef struct
{
  /* For fast dispatch of gl_list_iterator_next.  */
  const struct gl_list_implementation *vtable;
  /* For detecting whether the last returned element was removed.  */
  gl_list_t list;
  size_t count;
  /* Other, implementation-private fields.  */
  void *p; void *q;
  size_t i; size_t j;
} gl_list_iterator_t;

#if 0 /* These are defined inline below.  */

/* Create an iterator traversing a list.
   The list contents must not be modified while the iterator is in use,
   except for replacing or removing the last returned element.  */
extern gl_list_iterator_t gl_list_iterator (gl_list_t list);

/* Create an iterator traversing the element with indices i,
   start_index <= i < end_index, of a list.
   The list contents must not be modified while the iterator is in use,
   except for replacing or removing the last returned element.  */
extern gl_list_iterator_t gl_list_iterator_from_to (gl_list_t list,
                                                    size_t start_index,
                                                    size_t end_index);

/* If there is a next element, store the next element in *ELTP, store its
   node in *NODEP if NODEP is non-NULL, advance the iterator and return true.
   Otherwise, return false.  */
extern bool gl_list_iterator_next (gl_list_iterator_t *iterator,
                                   const void **eltp, gl_list_node_t *nodep);

/* Free an iterator.  */
extern void gl_list_iterator_free (gl_list_iterator_t *iterator);

#endif /* End of inline functions.  */

/* ---------------------- Sorted gl_list_t Data Type ---------------------- */

/* The following functions are for lists without duplicates where the
   order is given by a sort criterion.  */

/* Type of function used to compare two elements.  Same as for qsort().
   NULL denotes pointer comparison.  */
typedef int (*gl_listelement_compar_fn) (const void *elt1, const void *elt2);

#if 0 /* Unless otherwise specified, these are defined inline below.  */

/* Search whether an element is already in the list.
   The list is assumed to be sorted with COMPAR.
   Return its node if found, or NULL if not present in the list.
   If the list contains several copies of ELT, the node of the leftmost one is
   returned.  */
extern gl_list_node_t gl_sortedlist_search (gl_list_t list,
                                            gl_listelement_compar_fn compar,
                                            const void *elt);

/* Search whether an element is already in the list.
   The list is assumed to be sorted with COMPAR.
   Only list elements with indices >= START_INDEX and < END_INDEX are
   considered; the implementation uses these bounds to minimize the number
   of COMPAR invocations.
   Return its node if found, or NULL if not present in the list.
   If the list contains several copies of ELT, the node of the leftmost one is
   returned.  */
extern 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);

/* Search whether an element is already in the list.
   The list is assumed to be sorted with COMPAR.
   Return its position if found, or (size_t)(-1) if not present in the list.
   If the list contains several copies of ELT, the position of the leftmost one
   is returned.  */
extern size_t gl_sortedlist_indexof (gl_list_t list,
                                     gl_listelement_compar_fn compar,
                                     const void *elt);

/* Search whether an element is already in the list.
   The list is assumed to be sorted with COMPAR.
   Only list elements with indices >= START_INDEX and < END_INDEX are
   considered; the implementation uses these bounds to minimize the number
   of COMPAR invocations.
   Return its position if found, or (size_t)(-1) if not present in the list.
   If the list contains several copies of ELT, the position of the leftmost one
   is returned.  */
extern 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);

/* Add an element at the appropriate position in the list.
   The list is assumed to be sorted with COMPAR.
   Return its node.  */
/* declared in gl_xlist.h */
extern gl_list_node_t gl_sortedlist_add (gl_list_t list,
                                         gl_listelement_compar_fn compar,
                                         const void *elt);
/* Likewise.  Return NULL upon out-of-memory.  */
extern gl_list_node_t gl_sortedlist_nx_add (gl_list_t list,
                                            gl_listelement_compar_fn compar,
                                            const void *elt)
#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
  __attribute__ ((__warn_unused_result__))
#endif
  ;

/* Search and remove an element from the list.
   The list is assumed to be sorted with COMPAR.
   Return true if it was found and removed.
   If the list contains several copies of ELT, only the leftmost one is
   removed.  */
extern bool gl_sortedlist_remove (gl_list_t list,
                                  gl_listelement_compar_fn compar,
                                  const void *elt);

#endif /* End of inline and gl_xlist.h-defined functions.  */

/* ------------------------ Implementation Details ------------------------ */

struct gl_list_implementation
{
  /* gl_list_t functions.  */
  gl_list_t (*nx_create_empty) (gl_list_implementation_t implementation,
                                gl_listelement_equals_fn equals_fn,
                                gl_listelement_hashcode_fn hashcode_fn,
                                gl_listelement_dispose_fn dispose_fn,
                                bool allow_duplicates);
  gl_list_t (*nx_create) (gl_list_implementation_t implementation,
                          gl_listelement_equals_fn equals_fn,
                          gl_listelement_hashcode_fn hashcode_fn,
                          gl_listelement_dispose_fn dispose_fn,
                          bool allow_duplicates,
                          size_t count, const void **contents);
  size_t (*size) (gl_list_t list);
  const void * (*node_value) (gl_list_t list, gl_list_node_t node);
  int (*node_nx_set_value) (gl_list_t list, gl_list_node_t node,
                            const void *elt);
  gl_list_node_t (*next_node) (gl_list_t list, gl_list_node_t node);
  gl_list_node_t (*previous_node) (gl_list_t list, gl_list_node_t node);
  const void * (*get_at) (gl_list_t list, size_t position);
  gl_list_node_t (*nx_set_at) (gl_list_t list, size_t position,
                               const void *elt);
  gl_list_node_t (*search_from_to) (gl_list_t list, size_t start_index,
                                    size_t end_index, const void *elt);
  size_t (*indexof_from_to) (gl_list_t list, size_t start_index,
                             size_t end_index, const void *elt);
  gl_list_node_t (*nx_add_first) (gl_list_t list, const void *elt);
  gl_list_node_t (*nx_add_last) (gl_list_t list, const void *elt);
  gl_list_node_t (*nx_add_before) (gl_list_t list, gl_list_node_t node,
                                   const void *elt);
  gl_list_node_t (*nx_add_after) (gl_list_t list, gl_list_node_t node,
                                  const void *elt);
  gl_list_node_t (*nx_add_at) (gl_list_t list, size_t position,
                               const void *elt);
  bool (*remove_node) (gl_list_t list, gl_list_node_t node);
  bool (*remove_at) (gl_list_t list, size_t position);
  bool (*remove_elt) (gl_list_t list, const void *elt);
  void (*list_free) (gl_list_t list);
  /* gl_list_iterator_t functions.  */
  gl_list_iterator_t (*iterator) (gl_list_t list);
  gl_list_iterator_t (*iterator_from_to) (gl_list_t list,
                                          size_t start_index,
                                          size_t end_index);
  bool (*iterator_next) (gl_list_iterator_t *iterator,
                         const void **eltp, gl_list_node_t *nodep);
  void (*iterator_free) (gl_list_iterator_t *iterator);
  /* Sorted gl_list_t functions.  */
  gl_list_node_t (*sortedlist_search) (gl_list_t list,
                                       gl_listelement_compar_fn compar,
                                       const void *elt);
  gl_list_node_t (*sortedlist_search_from_to) (gl_list_t list,
                                               gl_listelement_compar_fn compar,
                                               size_t start_index,
                                               size_t end_index,
                                               const void *elt);
  size_t (*sortedlist_indexof) (gl_list_t list,
                                gl_listelement_compar_fn compar,
                                const void *elt);
  size_t (*sortedlist_indexof_from_to) (gl_list_t list,
                                        gl_listelement_compar_fn compar,
                                        size_t start_index, size_t end_index,
                                        const void *elt);
  gl_list_node_t (*sortedlist_nx_add) (gl_list_t list,
                                       gl_listelement_compar_fn compar,
                                    const void *elt);
  bool (*sortedlist_remove) (gl_list_t list,
                             gl_listelement_compar_fn compar,
                             const void *elt);
};

struct gl_list_impl_base
{
  const struct gl_list_implementation *vtable;
  gl_listelement_equals_fn equals_fn;
  gl_listelement_hashcode_fn hashcode_fn;
  gl_listelement_dispose_fn dispose_fn;
  bool allow_duplicates;
};

/* Define all functions of this file as accesses to the
   struct gl_list_implementation.  */

GL_LIST_INLINE gl_list_t
gl_list_nx_create_empty (gl_list_implementation_t implementation,
                         gl_listelement_equals_fn equals_fn,
                         gl_listelement_hashcode_fn hashcode_fn,
                         gl_listelement_dispose_fn dispose_fn,
                         bool allow_duplicates)
{
  return implementation->nx_create_empty (implementation, equals_fn,
                                          hashcode_fn, dispose_fn,
                                          allow_duplicates);
}

GL_LIST_INLINE gl_list_t
gl_list_nx_create (gl_list_implementation_t implementation,
                   gl_listelement_equals_fn equals_fn,
                   gl_listelement_hashcode_fn hashcode_fn,
                   gl_listelement_dispose_fn dispose_fn,
                   bool allow_duplicates,
                   size_t count, const void **contents)
{
  return implementation->nx_create (implementation, equals_fn, hashcode_fn,
                                    dispose_fn, allow_duplicates, count,
                                    contents);
}

GL_LIST_INLINE size_t
gl_list_size (gl_list_t list)
{
  return ((const struct gl_list_impl_base *) list)->vtable
         ->size (list);
}

GL_LIST_INLINE const void *
gl_list_node_value (gl_list_t list, gl_list_node_t node)
{
  return ((const struct gl_list_impl_base *) list)->vtable
         ->node_value (list, node);
}

GL_LIST_INLINE int
#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
  __attribute__ ((__warn_unused_result__))
#endif
gl_list_node_nx_set_value (gl_list_t list, gl_list_node_t node,
                           const void *elt)
{
  return ((const struct gl_list_impl_base *) list)->vtable
         ->node_nx_set_value (list, node, elt);
}

GL_LIST_INLINE gl_list_node_t
gl_list_next_node (gl_list_t list, gl_list_node_t node)
{
  return ((const struct gl_list_impl_base *) list)->vtable
         ->next_node (list, node);
}

GL_LIST_INLINE gl_list_node_t
gl_list_previous_node (gl_list_t list, gl_list_node_t node)
{
  return ((const struct gl_list_impl_base *) list)->vtable
         ->previous_node (list, node);
}

GL_LIST_INLINE const void *
gl_list_get_at (gl_list_t list, size_t position)
{
  return ((const struct gl_list_impl_base *) list)->vtable
         ->get_at (list, position);
}

GL_LIST_INLINE gl_list_node_t
#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
  __attribute__ ((__warn_unused_result__))
#endif
gl_list_nx_set_at (gl_list_t list, size_t position, const void *elt)
{
  return ((const struct gl_list_impl_base *) list)->vtable
         ->nx_set_at (list, position, elt);
}

GL_LIST_INLINE gl_list_node_t
gl_list_search (gl_list_t list, const void *elt)
{
  size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
  return ((const struct gl_list_impl_base *) list)->vtable
         ->search_from_to (list, 0, size, elt);
}

GL_LIST_INLINE gl_list_node_t
gl_list_search_from (gl_list_t list, size_t start_index, const void *elt)
{
  size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
  return ((const struct gl_list_impl_base *) list)->vtable
         ->search_from_to (list, start_index, size, elt);
}

GL_LIST_INLINE gl_list_node_t
gl_list_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
                        const void *elt)
{
  return ((const struct gl_list_impl_base *) list)->vtable
         ->search_from_to (list, start_index, end_index, elt);
}

GL_LIST_INLINE size_t
gl_list_indexof (gl_list_t list, const void *elt)
{
  size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
  return ((const struct gl_list_impl_base *) list)->vtable
         ->indexof_from_to (list, 0, size, elt);
}

GL_LIST_INLINE size_t
gl_list_indexof_from (gl_list_t list, size_t start_index, const void *elt)
{
  size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
  return ((const struct gl_list_impl_base *) list)->vtable
         ->indexof_from_to (list, start_index, size, elt);
}

GL_LIST_INLINE size_t
gl_list_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
                         const void *elt)
{
  return ((const struct gl_list_impl_base *) list)->vtable
         ->indexof_from_to (list, start_index, end_index, elt);
}

GL_LIST_INLINE gl_list_node_t
#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
  __attribute__ ((__warn_unused_result__))
#endif
gl_list_nx_add_first (gl_list_t list, const void *elt)
{
  return ((const struct gl_list_impl_base *) list)->vtable
         ->nx_add_first (list, elt);
}

GL_LIST_INLINE gl_list_node_t
#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
  __attribute__ ((__warn_unused_result__))
#endif
gl_list_nx_add_last (gl_list_t list, const void *elt)
{
  return ((const struct gl_list_impl_base *) list)->vtable
         ->nx_add_last (list, elt);
}

GL_LIST_INLINE gl_list_node_t
#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
  __attribute__ ((__warn_unused_result__))
#endif
gl_list_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
{
  return ((const struct gl_list_impl_base *) list)->vtable
         ->nx_add_before (list, node, elt);
}

GL_LIST_INLINE gl_list_node_t
#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
  __attribute__ ((__warn_unused_result__))
#endif
gl_list_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
{
  return ((const struct gl_list_impl_base *) list)->vtable
         ->nx_add_after (list, node, elt);
}

GL_LIST_INLINE gl_list_node_t
#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
  __attribute__ ((__warn_unused_result__))
#endif
gl_list_nx_add_at (gl_list_t list, size_t position, const void *elt)
{
  return ((const struct gl_list_impl_base *) list)->vtable
         ->nx_add_at (list, position, elt);
}

GL_LIST_INLINE bool
gl_list_remove_node (gl_list_t list, gl_list_node_t node)
{
  return ((const struct gl_list_impl_base *) list)->vtable
         ->remove_node (list, node);
}

GL_LIST_INLINE bool
gl_list_remove_at (gl_list_t list, size_t position)
{
  return ((const struct gl_list_impl_base *) list)->vtable
         ->remove_at (list, position);
}

GL_LIST_INLINE bool
gl_list_remove (gl_list_t list, const void *elt)
{
  return ((const struct gl_list_impl_base *) list)->vtable
         ->remove_elt (list, elt);
}

GL_LIST_INLINE void
gl_list_free (gl_list_t list)
{
  ((const struct gl_list_impl_base *) list)->vtable->list_free (list);
}

GL_LIST_INLINE gl_list_iterator_t
gl_list_iterator (gl_list_t list)
{
  return ((const struct gl_list_impl_base *) list)->vtable
         ->iterator (list);
}

GL_LIST_INLINE gl_list_iterator_t
gl_list_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
{
  return ((const struct gl_list_impl_base *) list)->vtable
         ->iterator_from_to (list, start_index, end_index);
}

GL_LIST_INLINE bool
gl_list_iterator_next (gl_list_iterator_t *iterator,
                       const void **eltp, gl_list_node_t *nodep)
{
  return iterator->vtable->iterator_next (iterator, eltp, nodep);
}

GL_LIST_INLINE void
gl_list_iterator_free (gl_list_iterator_t *iterator)
{
  iterator->vtable->iterator_free (iterator);
}

GL_LIST_INLINE gl_list_node_t
gl_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
{
  return ((const struct gl_list_impl_base *) list)->vtable
         ->sortedlist_search (list, compar, elt);
}

GL_LIST_INLINE gl_list_node_t
gl_sortedlist_search_from_to (gl_list_t list, gl_listelement_compar_fn compar, size_t start_index, size_t end_index, const void *elt)
{
  return ((const struct gl_list_impl_base *) list)->vtable
         ->sortedlist_search_from_to (list, compar, start_index, end_index,
                                      elt);
}

GL_LIST_INLINE size_t
gl_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
{
  return ((const struct gl_list_impl_base *) list)->vtable
         ->sortedlist_indexof (list, compar, elt);
}

GL_LIST_INLINE size_t
gl_sortedlist_indexof_from_to (gl_list_t list, gl_listelement_compar_fn compar, size_t start_index, size_t end_index, const void *elt)
{
  return ((const struct gl_list_impl_base *) list)->vtable
         ->sortedlist_indexof_from_to (list, compar, start_index, end_index,
                                       elt);
}

GL_LIST_INLINE gl_list_node_t
#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
  __attribute__ ((__warn_unused_result__))
#endif
gl_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
{
  return ((const struct gl_list_impl_base *) list)->vtable
         ->sortedlist_nx_add (list, compar, elt);
}

GL_LIST_INLINE bool
gl_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
{
  return ((const struct gl_list_impl_base *) list)->vtable
         ->sortedlist_remove (list, compar, elt);
}

#ifdef __cplusplus
}
#endif

_GL_INLINE_HEADER_END

#endif /* _GL_LIST_H */