lib/gl_list.h

   1 /* Abstract sequential list data type.
   2    Copyright (C) 2006-2012 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 /* Create an empty list.
 129    IMPLEMENTATION is one of GL_ARRAY_LIST, GL_CARRAY_LIST, GL_LINKED_LIST,
 130    GL_AVLTREE_LIST, GL_RBTREE_LIST, GL_LINKEDHASH_LIST, GL_AVLTREEHASH_LIST,
 131    GL_RBTREEHASH_LIST.
 132    EQUALS_FN is an element comparison function or NULL.
 133    HASHCODE_FN is an element hash code function or NULL.
 134    DISPOSE_FN is an element disposal function or NULL.
 135    ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in
 136    the list. The implementation may verify this at runtime.  */
 137 #if 0 /* declared in gl_xlist.h */
 138 extern gl_list_t gl_list_create_empty (gl_list_implementation_t implementation,
 139                                        gl_listelement_equals_fn equals_fn,
 140                                        gl_listelement_hashcode_fn hashcode_fn,
 141                                        gl_listelement_dispose_fn dispose_fn,
 142                                        bool allow_duplicates);
 143 #endif
 144 /* Likewise.  Return NULL upon out-of-memory.  */
 145 extern gl_list_t gl_list_nx_create_empty (gl_list_implementation_t implementation,
 146                                           gl_listelement_equals_fn equals_fn,
 147                                           gl_listelement_hashcode_fn hashcode_fn,
 148                                           gl_listelement_dispose_fn dispose_fn,
 149                                           bool allow_duplicates);
 150
 151 /* Create a list with given contents.
 152    IMPLEMENTATION is one of GL_ARRAY_LIST, GL_CARRAY_LIST, GL_LINKED_LIST,
 153    GL_AVLTREE_LIST, GL_RBTREE_LIST, GL_LINKEDHASH_LIST, GL_AVLTREEHASH_LIST,
 154    GL_RBTREEHASH_LIST.
 155    EQUALS_FN is an element comparison function or NULL.
 156    HASHCODE_FN is an element hash code function or NULL.
 157    DISPOSE_FN is an element disposal function or NULL.
 158    ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in
 159    the list. The implementation may verify this at runtime.
 160    COUNT is the number of initial elements.
 161    CONTENTS[0..COUNT-1] is the initial contents.  */
 162 #if 0 /* declared in gl_xlist.h */
 163 extern gl_list_t gl_list_create (gl_list_implementation_t implementation,
 164                                  gl_listelement_equals_fn equals_fn,
 165                                  gl_listelement_hashcode_fn hashcode_fn,
 166                                  gl_listelement_dispose_fn dispose_fn,
 167                                  bool allow_duplicates,
 168                                  size_t count, const void **contents);
 169 #endif
 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 #if 0 /* 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 #endif
 189 /* Likewise.  Return 0 upon success, -1 upon out-of-memory.  */
 190 extern int gl_list_node_nx_set_value (gl_list_t list, gl_list_node_t node,
 191                                       const void *elt)
 192 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
 193   __attribute__ ((__warn_unused_result__))
 194 #endif
 195   ;
 196
 197 /* Return the node immediately after the given node in the list, or NULL
 198    if the given node is the last (rightmost) one in the list.  */
 199 extern gl_list_node_t gl_list_next_node (gl_list_t list, gl_list_node_t node);
 200
 201 /* Return the node immediately before the given node in the list, or NULL
 202    if the given node is the first (leftmost) one in the list.  */
 203 extern gl_list_node_t gl_list_previous_node (gl_list_t list, gl_list_node_t node);
 204
 205 /* Return the element at a given position in the list.
 206    POSITION must be >= 0 and < gl_list_size (list).  */
 207 extern const void * gl_list_get_at (gl_list_t list, size_t position);
 208
 209 /* Replace the element at a given position in the list.
 210    POSITION must be >= 0 and < gl_list_size (list).
 211    Return its node.  */
 212 #if 0 /* declared in gl_xlist.h */
 213 extern gl_list_node_t gl_list_set_at (gl_list_t list, size_t position,
 214                                       const void *elt);
 215 #endif
 216 /* Likewise.  Return NULL upon out-of-memory.  */
 217 extern gl_list_node_t gl_list_nx_set_at (gl_list_t list, size_t position,
 218                                          const void *elt)
 219 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
 220   __attribute__ ((__warn_unused_result__))
 221 #endif
 222   ;
 223
 224 /* Search whether an element is already in the list.
 225    Return its node if found, or NULL if not present in the list.  */
 226 extern gl_list_node_t gl_list_search (gl_list_t list, const void *elt);
 227
 228 /* Search whether an element is already in the list,
 229    at a position >= START_INDEX.
 230    Return its node if found, or NULL if not present in the list.  */
 231 extern gl_list_node_t gl_list_search_from (gl_list_t list, size_t start_index,
 232                                            const void *elt);
 233
 234 /* Search whether an element is already in the list,
 235    at a position >= START_INDEX and < END_INDEX.
 236    Return its node if found, or NULL if not present in the list.  */
 237 extern gl_list_node_t gl_list_search_from_to (gl_list_t list,
 238                                               size_t start_index,
 239                                               size_t end_index,
 240                                               const void *elt);
 241
 242 /* Search whether an element is already in the list.
 243    Return its position if found, or (size_t)(-1) if not present in the list.  */
 244 extern size_t gl_list_indexof (gl_list_t list, const void *elt);
 245
 246 /* Search whether an element is already in the list,
 247    at a position >= START_INDEX.
 248    Return its position if found, or (size_t)(-1) if not present in the list.  */
 249 extern size_t gl_list_indexof_from (gl_list_t list, size_t start_index,
 250                                     const void *elt);
 251
 252 /* Search whether an element is already in the list,
 253    at a position >= START_INDEX and < END_INDEX.
 254    Return its position if found, or (size_t)(-1) if not present in the list.  */
 255 extern size_t gl_list_indexof_from_to (gl_list_t list,
 256                                        size_t start_index, size_t end_index,
 257                                        const void *elt);
 258
 259 /* Add an element as the first element of the list.
 260    Return its node.  */
 261 #if 0 /* declared in gl_xlist.h */
 262 extern gl_list_node_t gl_list_add_first (gl_list_t list, const void *elt);
 263 #endif
 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 #if 0 /* declared in gl_xlist.h */
 274 extern gl_list_node_t gl_list_add_last (gl_list_t list, const void *elt);
 275 #endif
 276 /* Likewise.  Return NULL upon out-of-memory.  */
 277 extern gl_list_node_t gl_list_nx_add_last (gl_list_t list, const void *elt)
 278 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
 279   __attribute__ ((__warn_unused_result__))
 280 #endif
 281   ;
 282
 283 /* Add an element before a given element node of the list.
 284    Return its node.  */
 285 #if 0 /* declared in gl_xlist.h */
 286 extern gl_list_node_t gl_list_add_before (gl_list_t list, gl_list_node_t node,
 287                                           const void *elt);
 288 #endif
 289 /* Likewise.  Return NULL upon out-of-memory.  */
 290 extern gl_list_node_t gl_list_nx_add_before (gl_list_t list,
 291                                              gl_list_node_t node,
 292                                              const void *elt)
 293 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
 294   __attribute__ ((__warn_unused_result__))
 295 #endif
 296   ;
 297
 298 /* Add an element after a given element node of the list.
 299    Return its node.  */
 300 #if 0 /* declared in gl_xlist.h */
 301 extern gl_list_node_t gl_list_add_after (gl_list_t list, gl_list_node_t node,
 302                                          const void *elt);
 303 #endif
 304 /* Likewise.  Return NULL upon out-of-memory.  */
 305 extern gl_list_node_t gl_list_nx_add_after (gl_list_t list, gl_list_node_t node,
 306                                             const void *elt)
 307 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
 308   __attribute__ ((__warn_unused_result__))
 309 #endif
 310   ;
 311
 312 /* Add an element at a given position in the list.
 313    POSITION must be >= 0 and <= gl_list_size (list).  */
 314 #if 0 /* declared in gl_xlist.h */
 315 extern gl_list_node_t gl_list_add_at (gl_list_t list, size_t position,
 316                                       const void *elt);
 317 #endif
 318 /* Likewise.  Return NULL upon out-of-memory.  */
 319 extern gl_list_node_t gl_list_nx_add_at (gl_list_t list, size_t position,
 320                                          const void *elt)
 321 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
 322   __attribute__ ((__warn_unused_result__))
 323 #endif
 324   ;
 325
 326 /* Remove an element from the list.
 327    Return true.  */
 328 extern bool gl_list_remove_node (gl_list_t list, gl_list_node_t node);
 329
 330 /* Remove an element at a given position from the list.
 331    POSITION must be >= 0 and < gl_list_size (list).
 332    Return true.  */
 333 extern bool gl_list_remove_at (gl_list_t list, size_t position);
 334
 335 /* Search and remove an element from the list.
 336    Return true if it was found and removed.  */
 337 extern bool gl_list_remove (gl_list_t list, const void *elt);
 338
 339 /* Free an entire list.
 340    (But this call does not free the elements of the list.)  */
 341 extern void gl_list_free (gl_list_t list);
 342
 343 /* --------------------- gl_list_iterator_t Data Type --------------------- */
 344
 345 /* Functions for iterating through a list.  */
 346
 347 /* Type of an iterator that traverses a list.
 348    This is a fixed-size struct, so that creation of an iterator doesn't need
 349    memory allocation on the heap.  */
 350 typedef struct
 351 {
 352   /* For fast dispatch of gl_list_iterator_next.  */
 353   const struct gl_list_implementation *vtable;
 354   /* For detecting whether the last returned element was removed.  */
 355   gl_list_t list;
 356   size_t count;
 357   /* Other, implementation-private fields.  */
 358   void *p; void *q;
 359   size_t i; size_t j;
 360 } gl_list_iterator_t;
 361
 362 /* 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 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
 385
 386 /* The following functions are for lists without duplicates where the
 387    order is given by a sort criterion.  */
 388
 389 /* Type of function used to compare two elements.  Same as for qsort().
 390    NULL denotes pointer comparison.  */
 391 typedef int (*gl_listelement_compar_fn) (const void *elt1, const void *elt2);
 392
 393 /* Search whether an element is already in the list.
 394    The list is assumed to be sorted with COMPAR.
 395    Return its node if found, or NULL if not present in the list.
 396    If the list contains several copies of ELT, the node of the leftmost one is
 397    returned.  */
 398 extern gl_list_node_t gl_sortedlist_search (gl_list_t list,
 399                                             gl_listelement_compar_fn compar,
 400                                             const void *elt);
 401
 402 /* Search whether an element is already in the list.
 403    The list is assumed to be sorted with COMPAR.
 404    Only list elements with indices >= START_INDEX and < END_INDEX are
 405    considered; the implementation uses these bounds to minimize the number
 406    of COMPAR invocations.
 407    Return its node if found, or NULL if not present in the list.
 408    If the list contains several copies of ELT, the node of the leftmost one is
 409    returned.  */
 410 extern gl_list_node_t gl_sortedlist_search_from_to (gl_list_t list,
 411                                                     gl_listelement_compar_fn compar,
 412                                                     size_t start_index,
 413                                                     size_t end_index,
 414                                                     const void *elt);
 415
 416 /* Search whether an element is already in the list.
 417    The list is assumed to be sorted with COMPAR.
 418    Return its position if found, or (size_t)(-1) if not present in the list.
 419    If the list contains several copies of ELT, the position of the leftmost one
 420    is returned.  */
 421 extern size_t gl_sortedlist_indexof (gl_list_t list,
 422                                      gl_listelement_compar_fn compar,
 423                                      const void *elt);
 424
 425 /* Search whether an element is already in the list.
 426    The list is assumed to be sorted with COMPAR.
 427    Only list elements with indices >= START_INDEX and < END_INDEX are
 428    considered; the implementation uses these bounds to minimize the number
 429    of COMPAR invocations.
 430    Return its position if found, or (size_t)(-1) if not present in the list.
 431    If the list contains several copies of ELT, the position of the leftmost one
 432    is returned.  */
 433 extern size_t gl_sortedlist_indexof_from_to (gl_list_t list,
 434                                              gl_listelement_compar_fn compar,
 435                                              size_t start_index,
 436                                              size_t end_index,
 437                                              const void *elt);
 438
 439 /* Add an element at the appropriate position in the list.
 440    The list is assumed to be sorted with COMPAR.
 441    Return its node.  */
 442 #if 0 /* declared in gl_xlist.h */
 443 extern gl_list_node_t gl_sortedlist_add (gl_list_t list,
 444                                          gl_listelement_compar_fn compar,
 445                                          const void *elt);
 446 #endif
 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 /* ------------------------ Implementation Details ------------------------ */
 466
 467 struct gl_list_implementation
 468 {
 469   /* gl_list_t functions.  */
 470   gl_list_t (*nx_create_empty) (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   gl_list_t (*nx_create) (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                           size_t count, const void **contents);
 481   size_t (*size) (gl_list_t list);
 482   const void * (*node_value) (gl_list_t list, gl_list_node_t node);
 483   int (*node_nx_set_value) (gl_list_t list, gl_list_node_t node,
 484                             const void *elt);
 485   gl_list_node_t (*next_node) (gl_list_t list, gl_list_node_t node);
 486   gl_list_node_t (*previous_node) (gl_list_t list, gl_list_node_t node);
 487   const void * (*get_at) (gl_list_t list, size_t position);
 488   gl_list_node_t (*nx_set_at) (gl_list_t list, size_t position,
 489                                const void *elt);
 490   gl_list_node_t (*search_from_to) (gl_list_t list, size_t start_index,
 491                                     size_t end_index, const void *elt);
 492   size_t (*indexof_from_to) (gl_list_t list, size_t start_index,
 493                              size_t end_index, const void *elt);
 494   gl_list_node_t (*nx_add_first) (gl_list_t list, const void *elt);
 495   gl_list_node_t (*nx_add_last) (gl_list_t list, const void *elt);
 496   gl_list_node_t (*nx_add_before) (gl_list_t list, gl_list_node_t node,
 497                                    const void *elt);
 498   gl_list_node_t (*nx_add_after) (gl_list_t list, gl_list_node_t node,
 499                                   const void *elt);
 500   gl_list_node_t (*nx_add_at) (gl_list_t list, size_t position,
 501                                const void *elt);
 502   bool (*remove_node) (gl_list_t list, gl_list_node_t node);
 503   bool (*remove_at) (gl_list_t list, size_t position);
 504   bool (*remove_elt) (gl_list_t list, const void *elt);
 505   void (*list_free) (gl_list_t list);
 506   /* gl_list_iterator_t functions.  */
 507   gl_list_iterator_t (*iterator) (gl_list_t list);
 508   gl_list_iterator_t (*iterator_from_to) (gl_list_t list,
 509                                           size_t start_index,
 510                                           size_t end_index);
 511   bool (*iterator_next) (gl_list_iterator_t *iterator,
 512                          const void **eltp, gl_list_node_t *nodep);
 513   void (*iterator_free) (gl_list_iterator_t *iterator);
 514   /* Sorted gl_list_t functions.  */
 515   gl_list_node_t (*sortedlist_search) (gl_list_t list,
 516                                        gl_listelement_compar_fn compar,
 517                                        const void *elt);
 518   gl_list_node_t (*sortedlist_search_from_to) (gl_list_t list,
 519                                                gl_listelement_compar_fn compar,
 520                                                size_t start_index,
 521                                                size_t end_index,
 522                                                const void *elt);
 523   size_t (*sortedlist_indexof) (gl_list_t list,
 524                                 gl_listelement_compar_fn compar,
 525                                 const void *elt);
 526   size_t (*sortedlist_indexof_from_to) (gl_list_t list,
 527                                         gl_listelement_compar_fn compar,
 528                                         size_t start_index, size_t end_index,
 529                                         const void *elt);
 530   gl_list_node_t (*sortedlist_nx_add) (gl_list_t list,
 531                                        gl_listelement_compar_fn compar,
 532                                     const void *elt);
 533   bool (*sortedlist_remove) (gl_list_t list,
 534                              gl_listelement_compar_fn compar,
 535                              const void *elt);
 536 };
 537
 538 struct gl_list_impl_base
 539 {
 540   const struct gl_list_implementation *vtable;
 541   gl_listelement_equals_fn equals_fn;
 542   gl_listelement_hashcode_fn hashcode_fn;
 543   gl_listelement_dispose_fn dispose_fn;
 544   bool allow_duplicates;
 545 };
 546
 547 /* Define all functions of this file as accesses to the
 548    struct gl_list_implementation.  */
 549
 550 GL_LIST_INLINE gl_list_t
 551 gl_list_nx_create_empty (gl_list_implementation_t implementation,
 552                          gl_listelement_equals_fn equals_fn,
 553                          gl_listelement_hashcode_fn hashcode_fn,
 554                          gl_listelement_dispose_fn dispose_fn,
 555                          bool allow_duplicates)
 556 {
 557   return implementation->nx_create_empty (implementation, equals_fn,
 558                                           hashcode_fn, dispose_fn,
 559                                           allow_duplicates);
 560 }
 561
 562 GL_LIST_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 GL_LIST_INLINE size_t
 576 gl_list_size (gl_list_t list)
 577 {
 578   return ((const struct gl_list_impl_base *) list)->vtable
 579          ->size (list);
 580 }
 581
 582 GL_LIST_INLINE const void *
 583 gl_list_node_value (gl_list_t list, gl_list_node_t node)
 584 {
 585   return ((const struct gl_list_impl_base *) list)->vtable
 586          ->node_value (list, node);
 587 }
 588
 589 GL_LIST_INLINE int
 590 gl_list_node_nx_set_value (gl_list_t list, gl_list_node_t node,
 591                            const void *elt)
 592 {
 593   return ((const struct gl_list_impl_base *) list)->vtable
 594          ->node_nx_set_value (list, node, elt);
 595 }
 596
 597 GL_LIST_INLINE gl_list_node_t
 598 gl_list_next_node (gl_list_t list, gl_list_node_t node)
 599 {
 600   return ((const struct gl_list_impl_base *) list)->vtable
 601          ->next_node (list, node);
 602 }
 603
 604 GL_LIST_INLINE gl_list_node_t
 605 gl_list_previous_node (gl_list_t list, gl_list_node_t node)
 606 {
 607   return ((const struct gl_list_impl_base *) list)->vtable
 608          ->previous_node (list, node);
 609 }
 610
 611 GL_LIST_INLINE const void *
 612 gl_list_get_at (gl_list_t list, size_t position)
 613 {
 614   return ((const struct gl_list_impl_base *) list)->vtable
 615          ->get_at (list, position);
 616 }
 617
 618 GL_LIST_INLINE gl_list_node_t
 619 gl_list_nx_set_at (gl_list_t list, size_t position, const void *elt)
 620 {
 621   return ((const struct gl_list_impl_base *) list)->vtable
 622          ->nx_set_at (list, position, elt);
 623 }
 624
 625 GL_LIST_INLINE gl_list_node_t
 626 gl_list_search (gl_list_t list, const void *elt)
 627 {
 628   size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
 629   return ((const struct gl_list_impl_base *) list)->vtable
 630          ->search_from_to (list, 0, size, elt);
 631 }
 632
 633 GL_LIST_INLINE gl_list_node_t
 634 gl_list_search_from (gl_list_t list, size_t start_index, 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, start_index, size, elt);
 639 }
 640
 641 GL_LIST_INLINE gl_list_node_t
 642 gl_list_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
 643                         const void *elt)
 644 {
 645   return ((const struct gl_list_impl_base *) list)->vtable
 646          ->search_from_to (list, start_index, end_index, elt);
 647 }
 648
 649 GL_LIST_INLINE size_t
 650 gl_list_indexof (gl_list_t list, const void *elt)
 651 {
 652   size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
 653   return ((const struct gl_list_impl_base *) list)->vtable
 654          ->indexof_from_to (list, 0, size, elt);
 655 }
 656
 657 GL_LIST_INLINE size_t
 658 gl_list_indexof_from (gl_list_t list, size_t start_index, 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, start_index, size, elt);
 663 }
 664
 665 GL_LIST_INLINE size_t
 666 gl_list_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
 667                          const void *elt)
 668 {
 669   return ((const struct gl_list_impl_base *) list)->vtable
 670          ->indexof_from_to (list, start_index, end_index, elt);
 671 }
 672
 673 GL_LIST_INLINE gl_list_node_t
 674 gl_list_nx_add_first (gl_list_t list, const void *elt)
 675 {
 676   return ((const struct gl_list_impl_base *) list)->vtable
 677          ->nx_add_first (list, elt);
 678 }
 679
 680 GL_LIST_INLINE gl_list_node_t
 681 gl_list_nx_add_last (gl_list_t list, const void *elt)
 682 {
 683   return ((const struct gl_list_impl_base *) list)->vtable
 684          ->nx_add_last (list, elt);
 685 }
 686
 687 GL_LIST_INLINE gl_list_node_t
 688 gl_list_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
 689 {
 690   return ((const struct gl_list_impl_base *) list)->vtable
 691          ->nx_add_before (list, node, elt);
 692 }
 693
 694 GL_LIST_INLINE gl_list_node_t
 695 gl_list_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
 696 {
 697   return ((const struct gl_list_impl_base *) list)->vtable
 698          ->nx_add_after (list, node, elt);
 699 }
 700
 701 GL_LIST_INLINE gl_list_node_t
 702 gl_list_nx_add_at (gl_list_t list, size_t position, const void *elt)
 703 {
 704   return ((const struct gl_list_impl_base *) list)->vtable
 705          ->nx_add_at (list, position, elt);
 706 }
 707
 708 GL_LIST_INLINE bool
 709 gl_list_remove_node (gl_list_t list, gl_list_node_t node)
 710 {
 711   return ((const struct gl_list_impl_base *) list)->vtable
 712          ->remove_node (list, node);
 713 }
 714
 715 GL_LIST_INLINE bool
 716 gl_list_remove_at (gl_list_t list, size_t position)
 717 {
 718   return ((const struct gl_list_impl_base *) list)->vtable
 719          ->remove_at (list, position);
 720 }
 721
 722 GL_LIST_INLINE bool
 723 gl_list_remove (gl_list_t list, const void *elt)
 724 {
 725   return ((const struct gl_list_impl_base *) list)->vtable
 726          ->remove_elt (list, elt);
 727 }
 728
 729 GL_LIST_INLINE void
 730 gl_list_free (gl_list_t list)
 731 {
 732   ((const struct gl_list_impl_base *) list)->vtable->list_free (list);
 733 }
 734
 735 GL_LIST_INLINE gl_list_iterator_t
 736 gl_list_iterator (gl_list_t list)
 737 {
 738   return ((const struct gl_list_impl_base *) list)->vtable
 739          ->iterator (list);
 740 }
 741
 742 GL_LIST_INLINE gl_list_iterator_t
 743 gl_list_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
 744 {
 745   return ((const struct gl_list_impl_base *) list)->vtable
 746          ->iterator_from_to (list, start_index, end_index);
 747 }
 748
 749 GL_LIST_INLINE bool
 750 gl_list_iterator_next (gl_list_iterator_t *iterator,
 751                        const void **eltp, gl_list_node_t *nodep)
 752 {
 753   return iterator->vtable->iterator_next (iterator, eltp, nodep);
 754 }
 755
 756 GL_LIST_INLINE void
 757 gl_list_iterator_free (gl_list_iterator_t *iterator)
 758 {
 759   iterator->vtable->iterator_free (iterator);
 760 }
 761
 762 GL_LIST_INLINE gl_list_node_t
 763 gl_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
 764 {
 765   return ((const struct gl_list_impl_base *) list)->vtable
 766          ->sortedlist_search (list, compar, elt);
 767 }
 768
 769 GL_LIST_INLINE gl_list_node_t
 770 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)
 771 {
 772   return ((const struct gl_list_impl_base *) list)->vtable
 773          ->sortedlist_search_from_to (list, compar, start_index, end_index,
 774                                       elt);
 775 }
 776
 777 GL_LIST_INLINE size_t
 778 gl_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
 779 {
 780   return ((const struct gl_list_impl_base *) list)->vtable
 781          ->sortedlist_indexof (list, compar, elt);
 782 }
 783
 784 GL_LIST_INLINE size_t
 785 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)
 786 {
 787   return ((const struct gl_list_impl_base *) list)->vtable
 788          ->sortedlist_indexof_from_to (list, compar, start_index, end_index,
 789                                        elt);
 790 }
 791
 792 GL_LIST_INLINE gl_list_node_t
 793 gl_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
 794 {
 795   return ((const struct gl_list_impl_base *) list)->vtable
 796          ->sortedlist_nx_add (list, compar, elt);
 797 }
 798
 799 GL_LIST_INLINE bool
 800 gl_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
 801 {
 802   return ((const struct gl_list_impl_base *) list)->vtable
 803          ->sortedlist_remove (list, compar, elt);
 804 }
 805
 806 #ifdef __cplusplus
 807 }
 808 #endif
 809
 810 _GL_INLINE_HEADER_END
 811
 812 #endif /* _GL_LIST_H */