lib/gl_list.h

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