lib/gl_list.h

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