lib/gl_list.h

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