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