lib/gl_list.h

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