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