lib/gl_list.h

   1 /* Abstract sequential list data type.  -*- coding: utf-8 -*-
   2    Copyright (C) 2006-2024 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 {
 611   return implementation->nx_create_empty (implementation, equals_fn,
 612                                           hashcode_fn, dispose_fn,
 613                                           allow_duplicates);
 614 }
 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 {
 626   return implementation->nx_create (implementation, equals_fn, hashcode_fn,
 627                                     dispose_fn, allow_duplicates, count,
 628                                     contents);
 629 }
 630
 631 GL_LIST_INLINE size_t
 632 gl_list_size (gl_list_t list)
 633 {
 634   return ((const struct gl_list_impl_base *) list)->vtable
 635          ->size (list);
 636 }
 637
 638 GL_LIST_INLINE const void *
 639 gl_list_node_value (gl_list_t list, gl_list_node_t node)
 640 {
 641   return ((const struct gl_list_impl_base *) list)->vtable
 642          ->node_value (list, node);
 643 }
 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 {
 649   return ((const struct gl_list_impl_base *) list)->vtable
 650          ->node_nx_set_value (list, node, elt);
 651 }
 652
 653 GL_LIST_INLINE gl_list_node_t
 654 gl_list_next_node (gl_list_t list, gl_list_node_t node)
 655 {
 656   return ((const struct gl_list_impl_base *) list)->vtable
 657          ->next_node (list, node);
 658 }
 659
 660 GL_LIST_INLINE gl_list_node_t
 661 gl_list_previous_node (gl_list_t list, gl_list_node_t node)
 662 {
 663   return ((const struct gl_list_impl_base *) list)->vtable
 664          ->previous_node (list, node);
 665 }
 666
 667 GL_LIST_INLINE gl_list_node_t
 668 gl_list_first_node (gl_list_t list)
 669 {
 670   return ((const struct gl_list_impl_base *) list)->vtable
 671          ->first_node (list);
 672 }
 673
 674 GL_LIST_INLINE gl_list_node_t
 675 gl_list_last_node (gl_list_t list)
 676 {
 677   return ((const struct gl_list_impl_base *) list)->vtable
 678          ->last_node (list);
 679 }
 680
 681 GL_LIST_INLINE const void *
 682 gl_list_get_at (gl_list_t list, size_t position)
 683 {
 684   return ((const struct gl_list_impl_base *) list)->vtable
 685          ->get_at (list, position);
 686 }
 687
 688 GL_LIST_INLINE const void *
 689 gl_list_get_first (gl_list_t list)
 690 {
 691   return gl_list_get_at (list, 0);
 692 }
 693
 694 GL_LIST_INLINE const void *
 695 gl_list_get_last (gl_list_t list)
 696 {
 697   return gl_list_get_at (list, gl_list_size (list) - 1);
 698 }
 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 {
 703   return ((const struct gl_list_impl_base *) list)->vtable
 704          ->nx_set_at (list, position, elt);
 705 }
 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 {
 710   return gl_list_nx_set_at (list, 0, elt);
 711 }
 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 {
 716   return gl_list_nx_set_at (list, gl_list_size (list) - 1, elt);
 717 }
 718
 719 GL_LIST_INLINE gl_list_node_t
 720 gl_list_search (gl_list_t list, const void *elt)
 721 {
 722   size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
 723   return ((const struct gl_list_impl_base *) list)->vtable
 724          ->search_from_to (list, 0, size, elt);
 725 }
 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 {
 730   size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
 731   return ((const struct gl_list_impl_base *) list)->vtable
 732          ->search_from_to (list, start_index, size, elt);
 733 }
 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 {
 739   return ((const struct gl_list_impl_base *) list)->vtable
 740          ->search_from_to (list, start_index, end_index, elt);
 741 }
 742
 743 GL_LIST_INLINE size_t
 744 gl_list_indexof (gl_list_t list, const void *elt)
 745 {
 746   size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
 747   return ((const struct gl_list_impl_base *) list)->vtable
 748          ->indexof_from_to (list, 0, size, elt);
 749 }
 750
 751 GL_LIST_INLINE size_t
 752 gl_list_indexof_from (gl_list_t list, size_t start_index, const void *elt)
 753 {
 754   size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
 755   return ((const struct gl_list_impl_base *) list)->vtable
 756          ->indexof_from_to (list, start_index, size, elt);
 757 }
 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 {
 763   return ((const struct gl_list_impl_base *) list)->vtable
 764          ->indexof_from_to (list, start_index, end_index, elt);
 765 }
 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 {
 770   return ((const struct gl_list_impl_base *) list)->vtable
 771          ->nx_add_first (list, elt);
 772 }
 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 {
 777   return ((const struct gl_list_impl_base *) list)->vtable
 778          ->nx_add_last (list, elt);
 779 }
 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 {
 784   return ((const struct gl_list_impl_base *) list)->vtable
 785          ->nx_add_before (list, node, elt);
 786 }
 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 {
 791   return ((const struct gl_list_impl_base *) list)->vtable
 792          ->nx_add_after (list, node, elt);
 793 }
 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 {
 798   return ((const struct gl_list_impl_base *) list)->vtable
 799          ->nx_add_at (list, position, elt);
 800 }
 801
 802 GL_LIST_INLINE bool
 803 gl_list_remove_node (gl_list_t list, gl_list_node_t node)
 804 {
 805   return ((const struct gl_list_impl_base *) list)->vtable
 806          ->remove_node (list, node);
 807 }
 808
 809 GL_LIST_INLINE bool
 810 gl_list_remove_at (gl_list_t list, size_t position)
 811 {
 812   return ((const struct gl_list_impl_base *) list)->vtable
 813          ->remove_at (list, position);
 814 }
 815
 816 GL_LIST_INLINE bool
 817 gl_list_remove_first (gl_list_t list)
 818 {
 819   size_t size = gl_list_size (list);
 820   if (size > 0)
 821     return gl_list_remove_at (list, 0);
 822   else
 823     return false;
 824 }
 825
 826 GL_LIST_INLINE bool
 827 gl_list_remove_last (gl_list_t list)
 828 {
 829   size_t size = gl_list_size (list);
 830   if (size > 0)
 831     return gl_list_remove_at (list, size - 1);
 832   else
 833     return false;
 834 }
 835
 836 GL_LIST_INLINE bool
 837 gl_list_remove (gl_list_t list, const void *elt)
 838 {
 839   return ((const struct gl_list_impl_base *) list)->vtable
 840          ->remove_elt (list, elt);
 841 }
 842
 843 GL_LIST_INLINE void
 844 gl_list_free (gl_list_t list)
 845 {
 846   ((const struct gl_list_impl_base *) list)->vtable->list_free (list);
 847 }
 848
 849 GL_LIST_INLINE gl_list_iterator_t
 850 gl_list_iterator (gl_list_t list)
 851 {
 852   return ((const struct gl_list_impl_base *) list)->vtable
 853          ->iterator (list);
 854 }
 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 {
 859   return ((const struct gl_list_impl_base *) list)->vtable
 860          ->iterator_from_to (list, start_index, end_index);
 861 }
 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 {
 867   return iterator->vtable->iterator_next (iterator, eltp, nodep);
 868 }
 869
 870 GL_LIST_INLINE void
 871 gl_list_iterator_free (gl_list_iterator_t *iterator)
 872 {
 873   iterator->vtable->iterator_free (iterator);
 874 }
 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 {
 879   return ((const struct gl_list_impl_base *) list)->vtable
 880          ->sortedlist_search (list, compar, elt);
 881 }
 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 {
 886   return ((const struct gl_list_impl_base *) list)->vtable
 887          ->sortedlist_search_from_to (list, compar, start_index, end_index,
 888                                       elt);
 889 }
 890
 891 GL_LIST_INLINE size_t
 892 gl_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
 893 {
 894   return ((const struct gl_list_impl_base *) list)->vtable
 895          ->sortedlist_indexof (list, compar, elt);
 896 }
 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 {
 901   return ((const struct gl_list_impl_base *) list)->vtable
 902          ->sortedlist_indexof_from_to (list, compar, start_index, end_index,
 903                                        elt);
 904 }
 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 {
 909   return ((const struct gl_list_impl_base *) list)->vtable
 910          ->sortedlist_nx_add (list, compar, elt);
 911 }
 912
 913 GL_LIST_INLINE bool
 914 gl_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
 915 {
 916   return ((const struct gl_list_impl_base *) list)->vtable
 917          ->sortedlist_remove (list, compar, elt);
 918 }
 919
 920 #ifdef __cplusplus
 921 }
 922 #endif
 923
 924 _GL_INLINE_HEADER_END
 925
 926 #endif /* _GL_LIST_H */