lib/gl_list.h

   1 /* Abstract sequential list data type.  -*- coding: utf-8 -*-
   2    Copyright (C) 2006-2017 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 #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.)  */
 337 extern void gl_list_free (gl_list_t list);
 338
 339 #endif /* End of inline and gl_xlist.h-defined functions.  */
 340
 341 /* --------------------- gl_list_iterator_t Data Type --------------------- */
 342
 343 /* Functions for iterating through a list.  */
 344
 345 /* Type of an iterator that traverses a list.
 346    This is a fixed-size struct, so that creation of an iterator doesn't need
 347    memory allocation on the heap.  */
 348 typedef struct
 349 {
 350   /* For fast dispatch of gl_list_iterator_next.  */
 351   const struct gl_list_implementation *vtable;
 352   /* For detecting whether the last returned element was removed.  */
 353   gl_list_t list;
 354   size_t count;
 355   /* Other, implementation-private fields.  */
 356   void *p; void *q;
 357   size_t i; size_t j;
 358 } gl_list_iterator_t;
 359
 360 #if 0 /* These are defined inline below.  */
 361
 362 /* Create an iterator traversing a list.
 363    The list contents must not be modified while the iterator is in use,
 364    except for replacing or removing the last returned element.  */
 365 extern gl_list_iterator_t gl_list_iterator (gl_list_t list);
 366
 367 /* Create an iterator traversing the element with indices i,
 368    start_index <= i < end_index, of a list.
 369    The list contents must not be modified while the iterator is in use,
 370    except for replacing or removing the last returned element.  */
 371 extern gl_list_iterator_t gl_list_iterator_from_to (gl_list_t list,
 372                                                     size_t start_index,
 373                                                     size_t end_index);
 374
 375 /* If there is a next element, store the next element in *ELTP, store its
 376    node in *NODEP if NODEP is non-NULL, advance the iterator and return true.
 377    Otherwise, return false.  */
 378 extern bool gl_list_iterator_next (gl_list_iterator_t *iterator,
 379                                    const void **eltp, gl_list_node_t *nodep);
 380
 381 /* Free an iterator.  */
 382 extern void gl_list_iterator_free (gl_list_iterator_t *iterator);
 383
 384 #endif /* End of inline functions.  */
 385
 386 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
 387
 388 /* The following functions are for lists without duplicates where the
 389    order is given by a sort criterion.  */
 390
 391 /* Type of function used to compare two elements.  Same as for qsort().
 392    NULL denotes pointer comparison.  */
 393 typedef int (*gl_listelement_compar_fn) (const void *elt1, const void *elt2);
 394
 395 #if 0 /* Unless otherwise specified, these are defined inline below.  */
 396
 397 /* Search whether an element is already in the list.
 398    The list is assumed to be sorted with COMPAR.
 399    Return its node if found, or NULL if not present in the list.
 400    If the list contains several copies of ELT, the node of the leftmost one is
 401    returned.  */
 402 extern gl_list_node_t gl_sortedlist_search (gl_list_t list,
 403                                             gl_listelement_compar_fn compar,
 404                                             const void *elt);
 405
 406 /* Search whether an element is already in the list.
 407    The list is assumed to be sorted with COMPAR.
 408    Only list elements with indices >= START_INDEX and < END_INDEX are
 409    considered; the implementation uses these bounds to minimize the number
 410    of COMPAR invocations.
 411    Return its node if found, or NULL if not present in the list.
 412    If the list contains several copies of ELT, the node of the leftmost one is
 413    returned.  */
 414 extern gl_list_node_t gl_sortedlist_search_from_to (gl_list_t list,
 415                                                     gl_listelement_compar_fn compar,
 416                                                     size_t start_index,
 417                                                     size_t end_index,
 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    Return its position if found, or (size_t)(-1) if not present in the list.
 423    If the list contains several copies of ELT, the position of the leftmost one
 424    is returned.  */
 425 extern size_t gl_sortedlist_indexof (gl_list_t list,
 426                                      gl_listelement_compar_fn compar,
 427                                      const void *elt);
 428
 429 /* Search whether an element is already in the list.
 430    The list is assumed to be sorted with COMPAR.
 431    Only list elements with indices >= START_INDEX and < END_INDEX are
 432    considered; the implementation uses these bounds to minimize the number
 433    of COMPAR invocations.
 434    Return its position if found, or (size_t)(-1) if not present in the list.
 435    If the list contains several copies of ELT, the position of the leftmost one
 436    is returned.  */
 437 extern size_t gl_sortedlist_indexof_from_to (gl_list_t list,
 438                                              gl_listelement_compar_fn compar,
 439                                              size_t start_index,
 440                                              size_t end_index,
 441                                              const void *elt);
 442
 443 /* Add an element at the appropriate position in the list.
 444    The list is assumed to be sorted with COMPAR.
 445    Return its node.  */
 446 /* declared in gl_xlist.h */
 447 extern gl_list_node_t gl_sortedlist_add (gl_list_t list,
 448                                          gl_listelement_compar_fn compar,
 449                                          const void *elt);
 450 /* Likewise.  Return NULL upon out-of-memory.  */
 451 extern gl_list_node_t gl_sortedlist_nx_add (gl_list_t list,
 452                                             gl_listelement_compar_fn compar,
 453                                             const void *elt)
 454 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
 455   __attribute__ ((__warn_unused_result__))
 456 #endif
 457   ;
 458
 459 /* Search and remove an element from the list.
 460    The list is assumed to be sorted with COMPAR.
 461    Return true if it was found and removed.
 462    If the list contains several copies of ELT, only the leftmost one is
 463    removed.  */
 464 extern bool gl_sortedlist_remove (gl_list_t list,
 465                                   gl_listelement_compar_fn compar,
 466                                   const void *elt);
 467
 468 #endif /* End of inline and gl_xlist.h-defined functions.  */
 469
 470 /* ------------------------ Implementation Details ------------------------ */
 471
 472 struct gl_list_implementation
 473 {
 474   /* gl_list_t functions.  */
 475   gl_list_t (*nx_create_empty) (gl_list_implementation_t implementation,
 476                                 gl_listelement_equals_fn equals_fn,
 477                                 gl_listelement_hashcode_fn hashcode_fn,
 478                                 gl_listelement_dispose_fn dispose_fn,
 479                                 bool allow_duplicates);
 480   gl_list_t (*nx_create) (gl_list_implementation_t implementation,
 481                           gl_listelement_equals_fn equals_fn,
 482                           gl_listelement_hashcode_fn hashcode_fn,
 483                           gl_listelement_dispose_fn dispose_fn,
 484                           bool allow_duplicates,
 485                           size_t count, const void **contents);
 486   size_t (*size) (gl_list_t list);
 487   const void * (*node_value) (gl_list_t list, gl_list_node_t node);
 488   int (*node_nx_set_value) (gl_list_t list, gl_list_node_t node,
 489                             const void *elt);
 490   gl_list_node_t (*next_node) (gl_list_t list, gl_list_node_t node);
 491   gl_list_node_t (*previous_node) (gl_list_t list, gl_list_node_t node);
 492   const void * (*get_at) (gl_list_t list, size_t position);
 493   gl_list_node_t (*nx_set_at) (gl_list_t list, size_t position,
 494                                const void *elt);
 495   gl_list_node_t (*search_from_to) (gl_list_t list, size_t start_index,
 496                                     size_t end_index, const void *elt);
 497   size_t (*indexof_from_to) (gl_list_t list, size_t start_index,
 498                              size_t end_index, const void *elt);
 499   gl_list_node_t (*nx_add_first) (gl_list_t list, const void *elt);
 500   gl_list_node_t (*nx_add_last) (gl_list_t list, const void *elt);
 501   gl_list_node_t (*nx_add_before) (gl_list_t list, gl_list_node_t node,
 502                                    const void *elt);
 503   gl_list_node_t (*nx_add_after) (gl_list_t list, gl_list_node_t node,
 504                                   const void *elt);
 505   gl_list_node_t (*nx_add_at) (gl_list_t list, size_t position,
 506                                const void *elt);
 507   bool (*remove_node) (gl_list_t list, gl_list_node_t node);
 508   bool (*remove_at) (gl_list_t list, size_t position);
 509   bool (*remove_elt) (gl_list_t list, const void *elt);
 510   void (*list_free) (gl_list_t list);
 511   /* gl_list_iterator_t functions.  */
 512   gl_list_iterator_t (*iterator) (gl_list_t list);
 513   gl_list_iterator_t (*iterator_from_to) (gl_list_t list,
 514                                           size_t start_index,
 515                                           size_t end_index);
 516   bool (*iterator_next) (gl_list_iterator_t *iterator,
 517                          const void **eltp, gl_list_node_t *nodep);
 518   void (*iterator_free) (gl_list_iterator_t *iterator);
 519   /* Sorted gl_list_t functions.  */
 520   gl_list_node_t (*sortedlist_search) (gl_list_t list,
 521                                        gl_listelement_compar_fn compar,
 522                                        const void *elt);
 523   gl_list_node_t (*sortedlist_search_from_to) (gl_list_t list,
 524                                                gl_listelement_compar_fn compar,
 525                                                size_t start_index,
 526                                                size_t end_index,
 527                                                const void *elt);
 528   size_t (*sortedlist_indexof) (gl_list_t list,
 529                                 gl_listelement_compar_fn compar,
 530                                 const void *elt);
 531   size_t (*sortedlist_indexof_from_to) (gl_list_t list,
 532                                         gl_listelement_compar_fn compar,
 533                                         size_t start_index, size_t end_index,
 534                                         const void *elt);
 535   gl_list_node_t (*sortedlist_nx_add) (gl_list_t list,
 536                                        gl_listelement_compar_fn compar,
 537                                     const void *elt);
 538   bool (*sortedlist_remove) (gl_list_t list,
 539                              gl_listelement_compar_fn compar,
 540                              const void *elt);
 541 };
 542
 543 struct gl_list_impl_base
 544 {
 545   const struct gl_list_implementation *vtable;
 546   gl_listelement_equals_fn equals_fn;
 547   gl_listelement_hashcode_fn hashcode_fn;
 548   gl_listelement_dispose_fn dispose_fn;
 549   bool allow_duplicates;
 550 };
 551
 552 /* Define all functions of this file as accesses to the
 553    struct gl_list_implementation.  */
 554
 555 GL_LIST_INLINE gl_list_t
 556 gl_list_nx_create_empty (gl_list_implementation_t implementation,
 557                          gl_listelement_equals_fn equals_fn,
 558                          gl_listelement_hashcode_fn hashcode_fn,
 559                          gl_listelement_dispose_fn dispose_fn,
 560                          bool allow_duplicates)
 561 {
 562   return implementation->nx_create_empty (implementation, equals_fn,
 563                                           hashcode_fn, dispose_fn,
 564                                           allow_duplicates);
 565 }
 566
 567 GL_LIST_INLINE gl_list_t
 568 gl_list_nx_create (gl_list_implementation_t implementation,
 569                    gl_listelement_equals_fn equals_fn,
 570                    gl_listelement_hashcode_fn hashcode_fn,
 571                    gl_listelement_dispose_fn dispose_fn,
 572                    bool allow_duplicates,
 573                    size_t count, const void **contents)
 574 {
 575   return implementation->nx_create (implementation, equals_fn, hashcode_fn,
 576                                     dispose_fn, allow_duplicates, count,
 577                                     contents);
 578 }
 579
 580 GL_LIST_INLINE size_t
 581 gl_list_size (gl_list_t list)
 582 {
 583   return ((const struct gl_list_impl_base *) list)->vtable
 584          ->size (list);
 585 }
 586
 587 GL_LIST_INLINE const void *
 588 gl_list_node_value (gl_list_t list, gl_list_node_t node)
 589 {
 590   return ((const struct gl_list_impl_base *) list)->vtable
 591          ->node_value (list, node);
 592 }
 593
 594 GL_LIST_INLINE int
 595 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
 596   __attribute__ ((__warn_unused_result__))
 597 #endif
 598 gl_list_node_nx_set_value (gl_list_t list, gl_list_node_t node,
 599                            const void *elt)
 600 {
 601   return ((const struct gl_list_impl_base *) list)->vtable
 602          ->node_nx_set_value (list, node, elt);
 603 }
 604
 605 GL_LIST_INLINE gl_list_node_t
 606 gl_list_next_node (gl_list_t list, gl_list_node_t node)
 607 {
 608   return ((const struct gl_list_impl_base *) list)->vtable
 609          ->next_node (list, node);
 610 }
 611
 612 GL_LIST_INLINE gl_list_node_t
 613 gl_list_previous_node (gl_list_t list, gl_list_node_t node)
 614 {
 615   return ((const struct gl_list_impl_base *) list)->vtable
 616          ->previous_node (list, node);
 617 }
 618
 619 GL_LIST_INLINE const void *
 620 gl_list_get_at (gl_list_t list, size_t position)
 621 {
 622   return ((const struct gl_list_impl_base *) list)->vtable
 623          ->get_at (list, position);
 624 }
 625
 626 GL_LIST_INLINE gl_list_node_t
 627 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
 628   __attribute__ ((__warn_unused_result__))
 629 #endif
 630 gl_list_nx_set_at (gl_list_t list, size_t position, const void *elt)
 631 {
 632   return ((const struct gl_list_impl_base *) list)->vtable
 633          ->nx_set_at (list, position, elt);
 634 }
 635
 636 GL_LIST_INLINE gl_list_node_t
 637 gl_list_search (gl_list_t list, const void *elt)
 638 {
 639   size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
 640   return ((const struct gl_list_impl_base *) list)->vtable
 641          ->search_from_to (list, 0, size, elt);
 642 }
 643
 644 GL_LIST_INLINE gl_list_node_t
 645 gl_list_search_from (gl_list_t list, size_t start_index, const void *elt)
 646 {
 647   size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
 648   return ((const struct gl_list_impl_base *) list)->vtable
 649          ->search_from_to (list, start_index, size, elt);
 650 }
 651
 652 GL_LIST_INLINE gl_list_node_t
 653 gl_list_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
 654                         const void *elt)
 655 {
 656   return ((const struct gl_list_impl_base *) list)->vtable
 657          ->search_from_to (list, start_index, end_index, elt);
 658 }
 659
 660 GL_LIST_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 GL_LIST_INLINE size_t
 669 gl_list_indexof_from (gl_list_t list, size_t start_index, const void *elt)
 670 {
 671   size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
 672   return ((const struct gl_list_impl_base *) list)->vtable
 673          ->indexof_from_to (list, start_index, size, elt);
 674 }
 675
 676 GL_LIST_INLINE size_t
 677 gl_list_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
 678                          const void *elt)
 679 {
 680   return ((const struct gl_list_impl_base *) list)->vtable
 681          ->indexof_from_to (list, start_index, end_index, elt);
 682 }
 683
 684 GL_LIST_INLINE gl_list_node_t
 685 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
 686   __attribute__ ((__warn_unused_result__))
 687 #endif
 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 GL_LIST_INLINE gl_list_node_t
 695 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
 696   __attribute__ ((__warn_unused_result__))
 697 #endif
 698 gl_list_nx_add_last (gl_list_t list, const void *elt)
 699 {
 700   return ((const struct gl_list_impl_base *) list)->vtable
 701          ->nx_add_last (list, elt);
 702 }
 703
 704 GL_LIST_INLINE gl_list_node_t
 705 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
 706   __attribute__ ((__warn_unused_result__))
 707 #endif
 708 gl_list_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
 709 {
 710   return ((const struct gl_list_impl_base *) list)->vtable
 711          ->nx_add_before (list, node, elt);
 712 }
 713
 714 GL_LIST_INLINE gl_list_node_t
 715 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
 716   __attribute__ ((__warn_unused_result__))
 717 #endif
 718 gl_list_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
 719 {
 720   return ((const struct gl_list_impl_base *) list)->vtable
 721          ->nx_add_after (list, node, elt);
 722 }
 723
 724 GL_LIST_INLINE gl_list_node_t
 725 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
 726   __attribute__ ((__warn_unused_result__))
 727 #endif
 728 gl_list_nx_add_at (gl_list_t list, size_t position, const void *elt)
 729 {
 730   return ((const struct gl_list_impl_base *) list)->vtable
 731          ->nx_add_at (list, position, elt);
 732 }
 733
 734 GL_LIST_INLINE bool
 735 gl_list_remove_node (gl_list_t list, gl_list_node_t node)
 736 {
 737   return ((const struct gl_list_impl_base *) list)->vtable
 738          ->remove_node (list, node);
 739 }
 740
 741 GL_LIST_INLINE bool
 742 gl_list_remove_at (gl_list_t list, size_t position)
 743 {
 744   return ((const struct gl_list_impl_base *) list)->vtable
 745          ->remove_at (list, position);
 746 }
 747
 748 GL_LIST_INLINE bool
 749 gl_list_remove (gl_list_t list, const void *elt)
 750 {
 751   return ((const struct gl_list_impl_base *) list)->vtable
 752          ->remove_elt (list, elt);
 753 }
 754
 755 GL_LIST_INLINE void
 756 gl_list_free (gl_list_t list)
 757 {
 758   ((const struct gl_list_impl_base *) list)->vtable->list_free (list);
 759 }
 760
 761 GL_LIST_INLINE gl_list_iterator_t
 762 gl_list_iterator (gl_list_t list)
 763 {
 764   return ((const struct gl_list_impl_base *) list)->vtable
 765          ->iterator (list);
 766 }
 767
 768 GL_LIST_INLINE gl_list_iterator_t
 769 gl_list_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
 770 {
 771   return ((const struct gl_list_impl_base *) list)->vtable
 772          ->iterator_from_to (list, start_index, end_index);
 773 }
 774
 775 GL_LIST_INLINE bool
 776 gl_list_iterator_next (gl_list_iterator_t *iterator,
 777                        const void **eltp, gl_list_node_t *nodep)
 778 {
 779   return iterator->vtable->iterator_next (iterator, eltp, nodep);
 780 }
 781
 782 GL_LIST_INLINE void
 783 gl_list_iterator_free (gl_list_iterator_t *iterator)
 784 {
 785   iterator->vtable->iterator_free (iterator);
 786 }
 787
 788 GL_LIST_INLINE gl_list_node_t
 789 gl_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
 790 {
 791   return ((const struct gl_list_impl_base *) list)->vtable
 792          ->sortedlist_search (list, compar, elt);
 793 }
 794
 795 GL_LIST_INLINE gl_list_node_t
 796 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)
 797 {
 798   return ((const struct gl_list_impl_base *) list)->vtable
 799          ->sortedlist_search_from_to (list, compar, start_index, end_index,
 800                                       elt);
 801 }
 802
 803 GL_LIST_INLINE size_t
 804 gl_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
 805 {
 806   return ((const struct gl_list_impl_base *) list)->vtable
 807          ->sortedlist_indexof (list, compar, elt);
 808 }
 809
 810 GL_LIST_INLINE size_t
 811 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)
 812 {
 813   return ((const struct gl_list_impl_base *) list)->vtable
 814          ->sortedlist_indexof_from_to (list, compar, start_index, end_index,
 815                                        elt);
 816 }
 817
 818 GL_LIST_INLINE gl_list_node_t
 819 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
 820   __attribute__ ((__warn_unused_result__))
 821 #endif
 822 gl_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
 823 {
 824   return ((const struct gl_list_impl_base *) list)->vtable
 825          ->sortedlist_nx_add (list, compar, elt);
 826 }
 827
 828 GL_LIST_INLINE bool
 829 gl_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
 830 {
 831   return ((const struct gl_list_impl_base *) list)->vtable
 832          ->sortedlist_remove (list, compar, elt);
 833 }
 834
 835 #ifdef __cplusplus
 836 }
 837 #endif
 838
 839 _GL_INLINE_HEADER_END
 840
 841 #endif /* _GL_LIST_H */