lib/gl_list.h

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