lib/gl_list.h

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