lib/gl_list.h

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