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