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_indexof     O(log n)   O(n)   O(log n)    O(n)       O(log n)
  89    gl_sortedlist_add           O(n)     O(n)   O(log n)    O(n)    O((log n)²)/O(log n)
  90    gl_sortedlist_remove        O(n)     O(n)   O(log n)    O(n)    O((log n)²)/O(log n)
  91  */
  92
  93 /* -------------------------- gl_list_t Data Type -------------------------- */
  94
  95 /* Type of function used to compare two elements.
  96    NULL denotes pointer comparison.  */
  97 typedef bool (*gl_listelement_equals_fn) (const void *elt1, const void *elt2);
  98
  99 /* Type of function used to compute a hash code.
 100    NULL denotes a function that depends only on the pointer itself.  */
 101 typedef size_t (*gl_listelement_hashcode_fn) (const void *elt);
 102
 103 struct gl_list_impl;
 104 /* Type representing an entire list.  */
 105 typedef struct gl_list_impl * gl_list_t;
 106
 107 struct gl_list_node_impl;
 108 /* Type representing the position of an element in the list, in a way that
 109    is more adapted to the list implementation than a plain index.
 110    Note: It is invalidated by insertions and removals!  */
 111 typedef struct gl_list_node_impl * gl_list_node_t;
 112
 113 struct gl_list_implementation;
 114 /* Type representing a list datatype implementation.  */
 115 typedef const struct gl_list_implementation * gl_list_implementation_t;
 116
 117 /* Create an empty list.
 118    IMPLEMENTATION is one of GL_ARRAY_LIST, GL_CARRAY_LIST, GL_LINKED_LIST,
 119    GL_AVLTREE_LIST, GL_RBTREE_LIST, GL_LINKEDHASH_LIST, GL_AVLTREEHASH_LIST,
 120    GL_RBTREEHASH_LIST.
 121    EQUALS_FN is an element comparison function or NULL.
 122    HASHCODE_FN is an element hash code function or NULL.
 123    ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in
 124    the list. The implementation may verify this at runtime.  */
 125 extern gl_list_t gl_list_create_empty (gl_list_implementation_t implementation,
 126                                        gl_listelement_equals_fn equals_fn,
 127                                        gl_listelement_hashcode_fn hashcode_fn,
 128                                        bool allow_duplicates);
 129
 130 /* Create a list with given contents.
 131    IMPLEMENTATION is one of GL_ARRAY_LIST, GL_CARRAY_LIST, GL_LINKED_LIST,
 132    GL_AVLTREE_LIST, GL_RBTREE_LIST, GL_LINKEDHASH_LIST, GL_AVLTREEHASH_LIST,
 133    GL_RBTREEHASH_LIST.
 134    EQUALS_FN is an element comparison function or NULL.
 135    HASHCODE_FN is an element hash code function or NULL.
 136    ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in
 137    the list. The implementation may verify this at runtime.
 138    COUNT is the number of initial elements.
 139    CONTENTS[0..COUNT-1] is the initial contents.  */
 140 extern gl_list_t gl_list_create (gl_list_implementation_t implementation,
 141                                  gl_listelement_equals_fn equals_fn,
 142                                  gl_listelement_hashcode_fn hashcode_fn,
 143                                  bool allow_duplicates,
 144                                  size_t count, const void **contents);
 145
 146 /* Return the current number of elements in a list.  */
 147 extern size_t gl_list_size (gl_list_t list);
 148
 149 /* Return the element value represented by a list node.  */
 150 extern const void * gl_list_node_value (gl_list_t list, gl_list_node_t node);
 151
 152 /* Return the node immediately after the given node in the list, or NULL
 153    if the given node is the last (rightmost) one in the list.  */
 154 extern gl_list_node_t gl_list_next_node (gl_list_t list, gl_list_node_t node);
 155
 156 /* Return the node immediately before the given node in the list, or NULL
 157    if the given node is the first (leftmost) one in the list.  */
 158 extern gl_list_node_t gl_list_previous_node (gl_list_t list, gl_list_node_t node);
 159
 160 /* Return the element at a given position in the list.
 161    POSITION must be >= 0 and < gl_list_size (list).  */
 162 extern const void * gl_list_get_at (gl_list_t list, size_t position);
 163
 164 /* Replace the element at a given position in the list.
 165    POSITION must be >= 0 and < gl_list_size (list).
 166    Return its node.  */
 167 extern gl_list_node_t gl_list_set_at (gl_list_t list, size_t position,
 168                                       const void *elt);
 169
 170 /* Search whether an element is already in the list.
 171    Return its node if found, or NULL if not present in the list.  */
 172 extern gl_list_node_t gl_list_search (gl_list_t list, const void *elt);
 173
 174 /* Search whether an element is already in the list,
 175    at a position >= START_INDEX.
 176    Return its node if found, or NULL if not present in the list.  */
 177 extern gl_list_node_t gl_list_search_from (gl_list_t list, size_t start_index,
 178                                            const void *elt);
 179
 180 /* Search whether an element is already in the list,
 181    at a position >= START_INDEX and < END_INDEX.
 182    Return its node if found, or NULL if not present in the list.  */
 183 extern gl_list_node_t gl_list_search_from_to (gl_list_t list,
 184                                               size_t start_index,
 185                                               size_t end_index,
 186                                               const void *elt);
 187
 188 /* Search whether an element is already in the list.
 189    Return its position if found, or (size_t)(-1) if not present in the list.  */
 190 extern size_t gl_list_indexof (gl_list_t list, const void *elt);
 191
 192 /* Search whether an element is already in the list,
 193    at a position >= START_INDEX.
 194    Return its position if found, or (size_t)(-1) if not present in the list.  */
 195 extern size_t gl_list_indexof_from (gl_list_t list, size_t start_index,
 196                                     const void *elt);
 197
 198 /* Search whether an element is already in the list,
 199    at a position >= START_INDEX and < END_INDEX.
 200    Return its position if found, or (size_t)(-1) if not present in the list.  */
 201 extern size_t gl_list_indexof_from_to (gl_list_t list,
 202                                        size_t start_index, size_t end_index,
 203                                        const void *elt);
 204
 205 /* Add an element as the first element of the list.
 206    Return its node.  */
 207 extern gl_list_node_t gl_list_add_first (gl_list_t list, const void *elt);
 208
 209 /* Add an element as the last element of the list.
 210    Return its node.  */
 211 extern gl_list_node_t gl_list_add_last (gl_list_t list, const void *elt);
 212
 213 /* Add an element before a given element node of the list.
 214    Return its node.  */
 215 extern gl_list_node_t gl_list_add_before (gl_list_t list, gl_list_node_t node,
 216                                           const void *elt);
 217
 218 /* Add an element after a given element node of the list.
 219    Return its node.  */
 220 extern gl_list_node_t gl_list_add_after (gl_list_t list, gl_list_node_t node,
 221                                          const void *elt);
 222
 223 /* Add an element add a given position in the list.
 224    POSITION must be >= 0 and <= gl_list_size (list).  */
 225 extern gl_list_node_t gl_list_add_at (gl_list_t list, size_t position,
 226                                       const void *elt);
 227
 228 /* Remove an element from the list.
 229    Return true.  */
 230 extern bool gl_list_remove_node (gl_list_t list, gl_list_node_t node);
 231
 232 /* Remove an element at a given position from the list.
 233    POSITION must be >= 0 and < gl_list_size (list).
 234    Return true.  */
 235 extern bool gl_list_remove_at (gl_list_t list, size_t position);
 236
 237 /* Search and remove an element from the list.
 238    Return true if it was found and removed.  */
 239 extern bool gl_list_remove (gl_list_t list, const void *elt);
 240
 241 /* Free an entire list.
 242    (But this call does not free the elements of the list.)  */
 243 extern void gl_list_free (gl_list_t list);
 244
 245 /* --------------------- gl_list_iterator_t Data Type --------------------- */
 246
 247 /* Functions for iterating through a list.  */
 248
 249 /* Type of an iterator that traverses a list.
 250    This is a fixed-size struct, so that creation of an iterator doesn't need
 251    memory allocation on the heap.  */
 252 typedef struct
 253 {
 254   /* For fast dispatch of gl_list_iterator_next.  */
 255   const struct gl_list_implementation *vtable;
 256   /* For detecting whether the last returned element was removed.  */
 257   gl_list_t list;
 258   size_t count;
 259   /* Other, implementation-private fields.  */
 260   void *p; void *q;
 261   size_t i; size_t j;
 262 } gl_list_iterator_t;
 263
 264 /* Create an iterator traversing a list.
 265    The list contents must not be modified while the iterator is in use,
 266    except for replacing or removing the last returned element.  */
 267 extern gl_list_iterator_t gl_list_iterator (gl_list_t list);
 268
 269 /* Create an iterator traversing the element with indices i,
 270    start_index <= i < end_index, of a list.
 271    The list contents must not be modified while the iterator is in use,
 272    except for replacing or removing the last returned element.  */
 273 extern gl_list_iterator_t gl_list_iterator_from_to (gl_list_t list,
 274                                                     size_t start_index,
 275                                                     size_t end_index);
 276
 277 /* If there is a next element, store the next element in *ELTP, store its
 278    node in *NODEP if NODEP is non-NULL, advance the iterator and return true.
 279    Otherwise, return false.  */
 280 extern bool gl_list_iterator_next (gl_list_iterator_t *iterator,
 281                                    const void **eltp, gl_list_node_t *nodep);
 282
 283 /* Free an iterator.  */
 284 extern void gl_list_iterator_free (gl_list_iterator_t *iterator);
 285
 286 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
 287
 288 /* The following functions are for lists without duplicates where the
 289    order is given by a sort criterion.  */
 290
 291 /* Type of function used to compare two elements.  Same as for qsort().
 292    NULL denotes pointer comparison.  */
 293 typedef int (*gl_listelement_compar_fn) (const void *elt1, const void *elt2);
 294
 295 /* Search whether an element is already in the list.
 296    The list is assumed to be sorted with COMPAR.
 297    Return its node if found, or NULL if not present in the list.
 298    If the list contains several copies of ELT, the node of the leftmost one is
 299    returned.  */
 300 extern gl_list_node_t gl_sortedlist_search (gl_list_t list,
 301                                             gl_listelement_compar_fn compar,
 302                                             const void *elt);
 303
 304 /* Search whether an element is already in the list.
 305    The list is assumed to be sorted with COMPAR.
 306    Return its position if found, or (size_t)(-1) if not present in the list.
 307    If the list contains several copies of ELT, the position of the leftmost one
 308    is returned.  */
 309 extern size_t gl_sortedlist_indexof (gl_list_t list,
 310                                      gl_listelement_compar_fn compar,
 311                                      const void *elt);
 312
 313 /* Add an element at the appropriate position in the list.
 314    The list is assumed to be sorted with COMPAR.
 315    Return its node.  */
 316 extern gl_list_node_t gl_sortedlist_add (gl_list_t list,
 317                                          gl_listelement_compar_fn compar,
 318                                          const void *elt);
 319
 320 /* Search and remove an element from the list.
 321    The list is assumed to be sorted with COMPAR.
 322    Return true if it was found and removed.
 323    If the list contains several copies of ELT, only the leftmost one is
 324    removed.  */
 325 extern bool gl_sortedlist_remove (gl_list_t list,
 326                                   gl_listelement_compar_fn compar,
 327                                   const void *elt);
 328
 329 /* ------------------------ Implementation Details ------------------------ */
 330
 331 struct gl_list_implementation
 332 {
 333   // gl_list_t functions.
 334   gl_list_t (*create_empty) (gl_list_implementation_t implementation,
 335                              gl_listelement_equals_fn equals_fn,
 336                              gl_listelement_hashcode_fn hashcode_fn,
 337                              bool allow_duplicates);
 338   gl_list_t (*create) (gl_list_implementation_t implementation,
 339                        gl_listelement_equals_fn equals_fn,
 340                        gl_listelement_hashcode_fn hashcode_fn,
 341                        bool allow_duplicates,
 342                        size_t count, const void **contents);
 343   size_t (*size) (gl_list_t list);
 344   const void * (*node_value) (gl_list_t list, gl_list_node_t node);
 345   gl_list_node_t (*next_node) (gl_list_t list, gl_list_node_t node);
 346   gl_list_node_t (*previous_node) (gl_list_t list, gl_list_node_t node);
 347   const void * (*get_at) (gl_list_t list, size_t position);
 348   gl_list_node_t (*set_at) (gl_list_t list, size_t position, const void *elt);
 349   gl_list_node_t (*search_from_to) (gl_list_t list, size_t start_index,
 350                                     size_t end_index, const void *elt);
 351   size_t (*indexof_from_to) (gl_list_t list, size_t start_index,
 352                              size_t end_index, const void *elt);
 353   gl_list_node_t (*add_first) (gl_list_t list, const void *elt);
 354   gl_list_node_t (*add_last) (gl_list_t list, const void *elt);
 355   gl_list_node_t (*add_before) (gl_list_t list, gl_list_node_t node,
 356                                 const void *elt);
 357   gl_list_node_t (*add_after) (gl_list_t list, gl_list_node_t node,
 358                                const void *elt);
 359   gl_list_node_t (*add_at) (gl_list_t list, size_t position,
 360                             const void *elt);
 361   bool (*remove_node) (gl_list_t list, gl_list_node_t node);
 362   bool (*remove_at) (gl_list_t list, size_t position);
 363   bool (*remove) (gl_list_t list, const void *elt);
 364   void (*list_free) (gl_list_t list);
 365   // gl_list_iterator_t functions.
 366   gl_list_iterator_t (*iterator) (gl_list_t list);
 367   gl_list_iterator_t (*iterator_from_to) (gl_list_t list,
 368                                           size_t start_index,
 369                                           size_t end_index);
 370   bool (*iterator_next) (gl_list_iterator_t *iterator,
 371                          const void **eltp, gl_list_node_t *nodep);
 372   void (*iterator_free) (gl_list_iterator_t *iterator);
 373   // Sorted gl_list_t functions.
 374   gl_list_node_t (*sortedlist_search) (gl_list_t list,
 375                                        gl_listelement_compar_fn compar,
 376                                        const void *elt);
 377   size_t (*sortedlist_indexof) (gl_list_t list,
 378                                 gl_listelement_compar_fn compar,
 379                                 const void *elt);
 380   gl_list_node_t (*sortedlist_add) (gl_list_t list,
 381                                     gl_listelement_compar_fn compar,
 382                                     const void *elt);
 383   bool (*sortedlist_remove) (gl_list_t list,
 384                              gl_listelement_compar_fn compar,
 385                              const void *elt);
 386 };
 387
 388 struct gl_list_impl_base
 389 {
 390   const struct gl_list_implementation *vtable;
 391   gl_listelement_equals_fn equals_fn;
 392   gl_listelement_hashcode_fn hashcode_fn;
 393   bool allow_duplicates;
 394 };
 395
 396 #if HAVE_INLINE
 397
 398 /* Define all functions of this file as inline accesses to the
 399    struct gl_list_implementation.
 400    Use #define to avoid a warning because of extern vs. static.  */
 401
 402 # define gl_list_create_empty gl_list_create_empty_inline
 403 static inline gl_list_t
 404 gl_list_create_empty (gl_list_implementation_t implementation,
 405                       gl_listelement_equals_fn equals_fn,
 406                       gl_listelement_hashcode_fn hashcode_fn,
 407                       bool allow_duplicates)
 408 {
 409   return implementation->create_empty (implementation, equals_fn, hashcode_fn,
 410                                        allow_duplicates);
 411 }
 412
 413 # define gl_list_create gl_list_create_inline
 414 static inline gl_list_t
 415 gl_list_create (gl_list_implementation_t implementation,
 416                 gl_listelement_equals_fn equals_fn,
 417                 gl_listelement_hashcode_fn hashcode_fn,
 418                 bool allow_duplicates,
 419                 size_t count, const void **contents)
 420 {
 421   return implementation->create (implementation, equals_fn, hashcode_fn,
 422                                  allow_duplicates, count, contents);
 423 }
 424
 425 # define gl_list_size gl_list_size_inline
 426 static inline size_t
 427 gl_list_size (gl_list_t list)
 428 {
 429   return ((const struct gl_list_impl_base *) list)->vtable
 430          ->size (list);
 431 }
 432
 433 # define gl_list_node_value gl_list_node_value_inline
 434 static inline const void *
 435 gl_list_node_value (gl_list_t list, gl_list_node_t node)
 436 {
 437   return ((const struct gl_list_impl_base *) list)->vtable
 438          ->node_value (list, node);
 439 }
 440
 441 # define gl_list_next_node gl_list_next_node_inline
 442 static inline gl_list_node_t
 443 gl_list_next_node (gl_list_t list, gl_list_node_t node)
 444 {
 445   return ((const struct gl_list_impl_base *) list)->vtable
 446          ->next_node (list, node);
 447 }
 448
 449 # define gl_list_previous_node gl_list_previous_node_inline
 450 static inline gl_list_node_t
 451 gl_list_previous_node (gl_list_t list, gl_list_node_t node)
 452 {
 453   return ((const struct gl_list_impl_base *) list)->vtable
 454          ->previous_node (list, node);
 455 }
 456
 457 # define gl_list_get_at gl_list_get_at_inline
 458 static inline const void *
 459 gl_list_get_at (gl_list_t list, size_t position)
 460 {
 461   return ((const struct gl_list_impl_base *) list)->vtable
 462          ->get_at (list, position);
 463 }
 464
 465 # define gl_list_set_at gl_list_set_at_inline
 466 static inline gl_list_node_t
 467 gl_list_set_at (gl_list_t list, size_t position, const void *elt)
 468 {
 469   return ((const struct gl_list_impl_base *) list)->vtable
 470          ->set_at (list, position, elt);
 471 }
 472
 473 # define gl_list_search gl_list_search_inline
 474 static inline gl_list_node_t
 475 gl_list_search (gl_list_t list, const void *elt)
 476 {
 477   size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
 478   return ((const struct gl_list_impl_base *) list)->vtable
 479          ->search_from_to (list, 0, size, elt);
 480 }
 481
 482 # define gl_list_search_from gl_list_search_from_inline
 483 static inline gl_list_node_t
 484 gl_list_search_from (gl_list_t list, size_t start_index, const void *elt)
 485 {
 486   size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
 487   return ((const struct gl_list_impl_base *) list)->vtable
 488          ->search_from_to (list, start_index, size, elt);
 489 }
 490
 491 # define gl_list_search_from_to gl_list_search_from_to_inline
 492 static inline gl_list_node_t
 493 gl_list_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
 494                         const void *elt)
 495 {
 496   return ((const struct gl_list_impl_base *) list)->vtable
 497          ->search_from_to (list, start_index, end_index, elt);
 498 }
 499
 500 # define gl_list_indexof gl_list_indexof_inline
 501 static inline size_t
 502 gl_list_indexof (gl_list_t list, const void *elt)
 503 {
 504   size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
 505   return ((const struct gl_list_impl_base *) list)->vtable
 506          ->indexof_from_to (list, 0, size, elt);
 507 }
 508
 509 # define gl_list_indexof_from gl_list_indexof_from_inline
 510 static inline size_t
 511 gl_list_indexof_from (gl_list_t list, size_t start_index, const void *elt)
 512 {
 513   size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
 514   return ((const struct gl_list_impl_base *) list)->vtable
 515          ->indexof_from_to (list, start_index, size, elt);
 516 }
 517
 518 # define gl_list_indexof_from_to gl_list_indexof_from_to_inline
 519 static inline size_t
 520 gl_list_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
 521                          const void *elt)
 522 {
 523   return ((const struct gl_list_impl_base *) list)->vtable
 524          ->indexof_from_to (list, start_index, end_index, elt);
 525 }
 526
 527 # define gl_list_add_first gl_list_add_first_inline
 528 static inline gl_list_node_t
 529 gl_list_add_first (gl_list_t list, const void *elt)
 530 {
 531   return ((const struct gl_list_impl_base *) list)->vtable
 532          ->add_first (list, elt);
 533 }
 534
 535 # define gl_list_add_last gl_list_add_last_inline
 536 static inline gl_list_node_t
 537 gl_list_add_last (gl_list_t list, const void *elt)
 538 {
 539   return ((const struct gl_list_impl_base *) list)->vtable
 540          ->add_last (list, elt);
 541 }
 542
 543 # define gl_list_add_before gl_list_add_before_inline
 544 static inline gl_list_node_t
 545 gl_list_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
 546 {
 547   return ((const struct gl_list_impl_base *) list)->vtable
 548          ->add_before (list, node, elt);
 549 }
 550
 551 # define gl_list_add_after gl_list_add_after_inline
 552 static inline gl_list_node_t
 553 gl_list_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
 554 {
 555   return ((const struct gl_list_impl_base *) list)->vtable
 556          ->add_after (list, node, elt);
 557 }
 558
 559 # define gl_list_add_at gl_list_add_at_inline
 560 static inline gl_list_node_t
 561 gl_list_add_at (gl_list_t list, size_t position, const void *elt)
 562 {
 563   return ((const struct gl_list_impl_base *) list)->vtable
 564          ->add_at (list, position, elt);
 565 }
 566
 567 # define gl_list_remove_node gl_list_remove_node_inline
 568 static inline bool
 569 gl_list_remove_node (gl_list_t list, gl_list_node_t node)
 570 {
 571   return ((const struct gl_list_impl_base *) list)->vtable
 572          ->remove_node (list, node);
 573 }
 574
 575 # define gl_list_remove_at gl_list_remove_at_inline
 576 static inline bool
 577 gl_list_remove_at (gl_list_t list, size_t position)
 578 {
 579   return ((const struct gl_list_impl_base *) list)->vtable
 580          ->remove_at (list, position);
 581 }
 582
 583 # define gl_list_remove gl_list_remove_inline
 584 static inline bool
 585 gl_list_remove (gl_list_t list, const void *elt)
 586 {
 587   return ((const struct gl_list_impl_base *) list)->vtable
 588          ->remove (list, elt);
 589 }
 590
 591 # define gl_list_free gl_list_free_inline
 592 static inline void
 593 gl_list_free (gl_list_t list)
 594 {
 595   ((const struct gl_list_impl_base *) list)->vtable->list_free (list);
 596 }
 597
 598 # define gl_list_iterator gl_list_iterator_inline
 599 static inline gl_list_iterator_t
 600 gl_list_iterator (gl_list_t list)
 601 {
 602   return ((const struct gl_list_impl_base *) list)->vtable
 603          ->iterator (list);
 604 }
 605
 606 # define gl_list_iterator_from_to gl_list_iterator_from_to_inline
 607 static inline gl_list_iterator_t
 608 gl_list_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
 609 {
 610   return ((const struct gl_list_impl_base *) list)->vtable
 611          ->iterator_from_to (list, start_index, end_index);
 612 }
 613
 614 # define gl_list_iterator_next gl_list_iterator_next_inline
 615 static inline bool
 616 gl_list_iterator_next (gl_list_iterator_t *iterator,
 617                        const void **eltp, gl_list_node_t *nodep)
 618 {
 619   return iterator->vtable->iterator_next (iterator, eltp, nodep);
 620 }
 621
 622 # define gl_list_iterator_free gl_list_iterator_free_inline
 623 static inline void
 624 gl_list_iterator_free (gl_list_iterator_t *iterator)
 625 {
 626   iterator->vtable->iterator_free (iterator);
 627 }
 628
 629 # define gl_sortedlist_search gl_sortedlist_search_inline
 630 static inline gl_list_node_t
 631 gl_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
 632 {
 633   return ((const struct gl_list_impl_base *) list)->vtable
 634          ->sortedlist_search (list, compar, elt);
 635 }
 636
 637 # define gl_sortedlist_indexof gl_sortedlist_indexof_inline
 638 static inline size_t
 639 gl_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
 640 {
 641   return ((const struct gl_list_impl_base *) list)->vtable
 642          ->sortedlist_indexof (list, compar, elt);
 643 }
 644
 645 # define gl_sortedlist_add gl_sortedlist_add_inline
 646 static inline gl_list_node_t
 647 gl_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
 648 {
 649   return ((const struct gl_list_impl_base *) list)->vtable
 650          ->sortedlist_add (list, compar, elt);
 651 }
 652
 653 # define gl_sortedlist_remove gl_sortedlist_remove_inline
 654 static inline bool
 655 gl_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
 656 {
 657   return ((const struct gl_list_impl_base *) list)->vtable
 658          ->sortedlist_remove (list, compar, elt);
 659 }
 660
 661 #endif
 662
 663 #ifdef __cplusplus
 664 }
 665 #endif
 666
 667 #endif /* _GL_LIST_H */