lib/gl_list.h

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