maint/gnulib/lib/gl

/* */
This source file includes following definitions.
gl_list_create_empty
gl_list_nx_create_empty
gl_list_nx_create
gl_list_size
gl_list_node_value
gl_list_node_nx_set_value
gl_list_next_node
gl_list_previous_node
gl_list_first_node
gl_list_last_node
gl_list_get_at
gl_list_get_first
gl_list_get_last
gl_list_nx_set_at
gl_list_nx_set_first
gl_list_nx_set_last
gl_list_search
gl_list_search_from
gl_list_search_from_to
gl_list_indexof
gl_list_indexof_from
gl_list_indexof_from_to
gl_list_nx_add_first
gl_list_nx_add_last
gl_list_nx_add_before
gl_list_nx_add_after
gl_list_nx_add_at
gl_list_remove_node
gl_list_remove_at
gl_list_remove_first
gl_list_remove_last
gl_list_remove
gl_list_free
gl_list_iterator
gl_list_iterator_from_to
gl_list_iterator_next
gl_list_iterator_free
gl_sortedlist_search
gl_sortedlist_search_from_to
gl_sortedlist_indexof
gl_sortedlist_indexof_from_to
gl_sortedlist_nx_add
gl_sortedlist_remove
   1 /* Abstract sequential list data type.  -*- coding: utf-8 -*-
   2    Copyright (C) 2006-2021 Free Software Foundation, Inc.
   3    Written by Bruno Haible <bruno@clisp.org>, 2006.
   4 
   5    This file is free software: you can redistribute it and/or modify
   6    it under the terms of the GNU Lesser General Public License as
   7    published by the Free Software Foundation; either version 2.1 of the
   8    License, or (at your option) any later version.
   9 
  10    This file 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 Lesser General Public License for more details.
  14 
  15    You should have received a copy of the GNU Lesser General Public License
  16    along with this program.  If not, see <https://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 #ifndef _GL_INLINE_HEADER_BEGIN
  25  #error "Please include config.h first."
  26 #endif
  27 _GL_INLINE_HEADER_BEGIN
  28 #ifndef GL_LIST_INLINE
  29 # define GL_LIST_INLINE _GL_INLINE
  30 #endif
  31 
  32 #ifdef __cplusplus
  33 extern "C" {
  34 #endif
  35 
  36 
  37 /* gl_list is an abstract list data type.  It can contain any number of
  38    objects ('void *' or 'const void *' pointers) in any given order.
  39    Duplicates are allowed, but can optionally be forbidden.
  40 
  41    There are several implementations of this list datatype, optimized for
  42    different operations or for memory.  You can start using the simplest list
  43    implementation, GL_ARRAY_LIST, and switch to a different implementation
  44    later, when you realize which operations are performed the most frequently.
  45    The API of the different implementations is exactly the same; when
  46    switching to a different implementation, you only have to change the
  47    gl_list_create call.
  48 
  49    The implementations are:
  50      GL_ARRAY_LIST        a growable array
  51      GL_CARRAY_LIST       a growable circular array
  52      GL_LINKED_LIST       a linked list
  53      GL_AVLTREE_LIST      a binary tree (AVL tree)
  54      GL_RBTREE_LIST       a binary tree (red-black tree)
  55      GL_LINKEDHASH_LIST   a hash table with a linked list
  56      GL_AVLTREEHASH_LIST  a hash table with a binary tree (AVL tree)
  57      GL_RBTREEHASH_LIST   a hash table with a binary tree (red-black tree)
  58 
  59    The memory consumption is asymptotically the same: O(1) for every object
  60    in the list.  When looking more closely at the average memory consumed
  61    for an object, GL_ARRAY_LIST is the most compact representation, and
  62    GL_LINKEDHASH_LIST and GL_TREEHASH_LIST need more memory.
  63 
  64    The guaranteed average performance of the operations is, for a list of
  65    n elements:
  66 
  67    Operation                  ARRAY    LINKED    TREE    LINKEDHASH   TREEHASH
  68                               CARRAY                   with|without with|without
  69                                                          duplicates  duplicates
  70 
  71    gl_list_size                O(1)     O(1)     O(1)      O(1)         O(1)
  72    gl_list_node_value          O(1)     O(1)     O(1)      O(1)         O(1)
  73    gl_list_node_set_value      O(1)     O(1)     O(1)      O(1)    O((log n)²)/O(1)
  74    gl_list_next_node           O(1)     O(1)   O(log n)    O(1)       O(log n)
  75    gl_list_previous_node       O(1)     O(1)   O(log n)    O(1)       O(log n)
  76    gl_list_first_node          O(1)     O(1)   O(log n)    O(1)       O(log n)
  77    gl_list_last_node           O(1)     O(1)   O(log n)    O(1)       O(log n)
  78    gl_list_get_at              O(1)     O(n)   O(log n)    O(n)       O(log n)
  79    gl_list_get_first           O(1)     O(1)   O(log n)    O(1)       O(log n)
  80    gl_list_get_last            O(1)     O(1)   O(log n)    O(1)       O(log n)
  81    gl_list_set_at              O(1)     O(n)   O(log n)    O(n)    O((log n)²)/O(log n)
  82    gl_list_set_first           O(1)     O(1)   O(log n)  O(n)/O(1) O((log n)²)/O(log n)
  83    gl_list_set_last            O(1)     O(1)   O(log n)  O(n)/O(1) O((log n)²)/O(log n)
  84    gl_list_search              O(n)     O(n)     O(n)    O(n)/O(1)    O(log n)/O(1)
  85    gl_list_search_from         O(n)     O(n)     O(n)    O(n)/O(1) O((log n)²)/O(log n)
  86    gl_list_search_from_to      O(n)     O(n)     O(n)    O(n)/O(1) O((log n)²)/O(log n)
  87    gl_list_indexof             O(n)     O(n)     O(n)      O(n)       O(log n)
  88    gl_list_indexof_from        O(n)     O(n)     O(n)      O(n)    O((log n)²)/O(log n)
  89    gl_list_indexof_from_to     O(n)     O(n)     O(n)      O(n)    O((log n)²)/O(log n)
  90    gl_list_add_first         O(n)/O(1)  O(1)   O(log n)    O(1)    O((log n)²)/O(log n)
  91    gl_list_add_last            O(1)     O(1)   O(log n)    O(1)    O((log n)²)/O(log n)
  92    gl_list_add_before          O(n)     O(1)   O(log n)    O(1)    O((log n)²)/O(log n)
  93    gl_list_add_after           O(n)     O(1)   O(log n)    O(1)    O((log n)²)/O(log n)
  94    gl_list_add_at              O(n)     O(n)   O(log n)    O(n)    O((log n)²)/O(log n)
  95    gl_list_remove_node         O(n)     O(1)   O(log n)  O(n)/O(1) O((log n)²)/O(log n)
  96    gl_list_remove_at           O(n)     O(n)   O(log n)    O(n)    O((log n)²)/O(log n)
  97    gl_list_remove_first      O(n)/O(1)  O(1)   O(log n)  O(n)/O(1) O((log n)²)/O(log n)
  98    gl_list_remove_last         O(1)     O(1)   O(log n)  O(n)/O(1) O((log n)²)/O(log n)
  99    gl_list_remove              O(n)     O(n)     O(n)    O(n)/O(1) O((log n)²)/O(log n)
 100    gl_list_iterator            O(1)     O(1)   O(log n)    O(1)       O(log n)
 101    gl_list_iterator_from_to    O(1)     O(n)   O(log n)    O(n)       O(log n)
 102    gl_list_iterator_next       O(1)     O(1)   O(log n)    O(1)       O(log n)
 103    gl_sortedlist_search      O(log n)   O(n)   O(log n)    O(n)       O(log n)
 104    gl_sortedlist_search_from O(log n)   O(n)   O(log n)    O(n)       O(log n)
 105    gl_sortedlist_indexof     O(log n)   O(n)   O(log n)    O(n)       O(log n)
 106    gl_sortedlist_indexof_fro O(log n)   O(n)   O(log n)    O(n)       O(log n)
 107    gl_sortedlist_add           O(n)     O(n)   O(log n)    O(n)    O((log n)²)/O(log n)
 108    gl_sortedlist_remove        O(n)     O(n)   O(log n)    O(n)    O((log n)²)/O(log n)
 109  */
 110 
 111 /* -------------------------- gl_list_t Data Type -------------------------- */
 112 
 113 /* Type of function used to compare two elements.
 114    NULL denotes pointer comparison.  */
 115 typedef bool (*gl_listelement_equals_fn) (const void *elt1, const void *elt2);
 116 
 117 /* Type of function used to compute a hash code.
 118    NULL denotes a function that depends only on the pointer itself.  */
 119 typedef size_t (*gl_listelement_hashcode_fn) (const void *elt);
 120 
 121 /* Type of function used to dispose an element once it's removed from a list.
 122    NULL denotes a no-op.  */
 123 typedef void (*gl_listelement_dispose_fn) (const void *elt);
 124 
 125 struct gl_list_impl;
 126 /* Type representing an entire list.  */
 127 typedef struct gl_list_impl * gl_list_t;
 128 
 129 struct gl_list_node_impl;
 130 /* Type representing the position of an element in the list, in a way that
 131    is more adapted to the list implementation than a plain index.
 132    Note: It is invalidated by insertions and removals!  */
 133 typedef struct gl_list_node_impl * gl_list_node_t;
 134 
 135 struct gl_list_implementation;
 136 /* Type representing a list datatype implementation.  */
 137 typedef const struct gl_list_implementation * gl_list_implementation_t;
 138 
 139 #if 0 /* Unless otherwise specified, these are defined inline below.  */
 140 
 141 /* Creates an empty list.
 142    IMPLEMENTATION is one of GL_ARRAY_LIST, GL_CARRAY_LIST, GL_LINKED_LIST,
 143    GL_AVLTREE_LIST, GL_RBTREE_LIST, GL_LINKEDHASH_LIST, GL_AVLTREEHASH_LIST,
 144    GL_RBTREEHASH_LIST.
 145    EQUALS_FN is an element comparison function or NULL.
 146    HASHCODE_FN is an element hash code function or NULL.
 147    DISPOSE_FN is an element disposal function or NULL.
 148    ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in
 149    the list. The implementation may verify this at runtime.  */
 150 /* declared in gl_xlist.h */
 151 extern gl_list_t gl_list_create_empty (gl_list_implementation_t implementation,
     /*  */
 152                                        gl_listelement_equals_fn equals_fn,
 153                                        gl_listelement_hashcode_fn hashcode_fn,
 154                                        gl_listelement_dispose_fn dispose_fn,
 155                                        bool allow_duplicates)
 156   /*_GL_ATTRIBUTE_DEALLOC (gl_list_free, 1)*/
 157   _GL_ATTRIBUTE_RETURNS_NONNULL;
 158 /* Likewise.  Returns NULL upon out-of-memory.  */
 159 extern gl_list_t gl_list_nx_create_empty (gl_list_implementation_t implementation,
 160                                           gl_listelement_equals_fn equals_fn,
 161                                           gl_listelement_hashcode_fn hashcode_fn,
 162                                           gl_listelement_dispose_fn dispose_fn,
 163                                           bool allow_duplicates)
 164   /*_GL_ATTRIBUTE_DEALLOC (gl_list_free, 1)*/;
 165 
 166 /* Creates a list with given contents.
 167    IMPLEMENTATION is one of GL_ARRAY_LIST, GL_CARRAY_LIST, GL_LINKED_LIST,
 168    GL_AVLTREE_LIST, GL_RBTREE_LIST, GL_LINKEDHASH_LIST, GL_AVLTREEHASH_LIST,
 169    GL_RBTREEHASH_LIST.
 170    EQUALS_FN is an element comparison function or NULL.
 171    HASHCODE_FN is an element hash code function or NULL.
 172    DISPOSE_FN is an element disposal function or NULL.
 173    ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in
 174    the list. The implementation may verify this at runtime.
 175    COUNT is the number of initial elements.
 176    CONTENTS[0..COUNT-1] is the initial contents.  */
 177 /* declared in gl_xlist.h */
 178 extern gl_list_t gl_list_create (gl_list_implementation_t implementation,
 179                                  gl_listelement_equals_fn equals_fn,
 180                                  gl_listelement_hashcode_fn hashcode_fn,
 181                                  gl_listelement_dispose_fn dispose_fn,
 182                                  bool allow_duplicates,
 183                                  size_t count, const void **contents)
 184   /*_GL_ATTRIBUTE_DEALLOC (gl_list_free, 1)*/
 185   _GL_ATTRIBUTE_RETURNS_NONNULL;
 186 /* Likewise.  Returns NULL upon out-of-memory.  */
 187 extern gl_list_t gl_list_nx_create (gl_list_implementation_t implementation,
 188                                     gl_listelement_equals_fn equals_fn,
 189                                     gl_listelement_hashcode_fn hashcode_fn,
 190                                     gl_listelement_dispose_fn dispose_fn,
 191                                     bool allow_duplicates,
 192                                     size_t count, const void **contents)
 193   /*_GL_ATTRIBUTE_DEALLOC (gl_list_free, 1)*/;
 194 
 195 /* Returns the current number of elements in a list.  */
 196 extern size_t gl_list_size (gl_list_t list);
 197 
 198 /* Returns the element value represented by a list node.  */
 199 extern const void * gl_list_node_value (gl_list_t list, gl_list_node_t node);
 200 
 201 /* Replaces the element value represented by a list node.  */
 202 /* declared in gl_xlist.h */
 203 extern void gl_list_node_set_value (gl_list_t list, gl_list_node_t node,
 204                                     const void *elt);
 205 /* Likewise.  Returns 0 upon success, -1 upon out-of-memory.  */
 206 _GL_ATTRIBUTE_NODISCARD
 207 extern int gl_list_node_nx_set_value (gl_list_t list, gl_list_node_t node,
 208                                       const void *elt);
 209 
 210 /* Returns the node immediately after the given node in the list, or NULL
 211    if the given node is the last (rightmost) one in the list.  */
 212 extern gl_list_node_t gl_list_next_node (gl_list_t list, gl_list_node_t node);
 213 
 214 /* Returns the node immediately before the given node in the list, or NULL
 215    if the given node is the first (leftmost) one in the list.  */
 216 extern gl_list_node_t gl_list_previous_node (gl_list_t list, gl_list_node_t node);
 217 
 218 /* Returns the first node in the list, or NULL if the list is empty.
 219    This function is useful for iterating through the list like this:
 220      gl_list_node_t node;
 221      for (node = gl_list_first_node (list); node != NULL; node = gl_list_next_node (node))
 222        ...
 223  */
 224 extern gl_list_node_t gl_list_first_node (gl_list_t list);
 225 
 226 /* Returns the last node in the list, or NULL if the list is empty.
 227    This function is useful for iterating through the list in backward order,
 228    like this:
 229      gl_list_node_t node;
 230      for (node = gl_list_last_node (list); node != NULL; node = gl_list_previous_node (node))
 231        ...
 232  */
 233 extern gl_list_node_t gl_list_last_node (gl_list_t list);
 234 
 235 /* Returns the element at a given position in the list.
 236    POSITION must be >= 0 and < gl_list_size (list).  */
 237 extern const void * gl_list_get_at (gl_list_t list, size_t position);
 238 
 239 /* Returns the element at the first position in the list.
 240    The list must be non-empty.  */
 241 extern const void * gl_list_get_first (gl_list_t list);
 242 
 243 /* Returns the element at the last position in the list.
 244    The list must be non-empty.  */
 245 extern const void * gl_list_get_last (gl_list_t list);
 246 
 247 /* Replaces the element at a given position in the list.
 248    POSITION must be >= 0 and < gl_list_size (list).
 249    Returns its node.  */
 250 /* declared in gl_xlist.h */
 251 extern gl_list_node_t gl_list_set_at (gl_list_t list, size_t position,
 252                                       const void *elt);
 253 /* Likewise.  Returns NULL upon out-of-memory.  */
 254 _GL_ATTRIBUTE_NODISCARD
 255 extern gl_list_node_t gl_list_nx_set_at (gl_list_t list, size_t position,
 256                                          const void *elt);
 257 
 258 /* Replaces the element at the first position in the list.
 259    Returns its node.
 260    The list must be non-empty.  */
 261 /* declared in gl_xlist.h */
 262 extern gl_list_node_t gl_list_set_first (gl_list_t list, const void *elt);
 263 /* Likewise.  Returns NULL upon out-of-memory.  */
 264 _GL_ATTRIBUTE_NODISCARD
 265 extern gl_list_node_t gl_list_nx_set_first (gl_list_t list, const void *elt);
 266 
 267 /* Replaces the element at the last position in the list.
 268    Returns its node.
 269    The list must be non-empty.  */
 270 /* declared in gl_xlist.h */
 271 extern gl_list_node_t gl_list_set_last (gl_list_t list, const void *elt);
 272 /* Likewise.  Returns NULL upon out-of-memory.  */
 273 _GL_ATTRIBUTE_NODISCARD
 274 extern gl_list_node_t gl_list_nx_set_last (gl_list_t list, const void *elt);
 275 
 276 /* Searches whether an element is already in the list.
 277    Returns its node if found, or NULL if not present in the list.  */
 278 extern gl_list_node_t gl_list_search (gl_list_t list, const void *elt);
 279 
 280 /* Searches whether an element is already in the list,
 281    at a position >= START_INDEX.
 282    Returns its node if found, or NULL if not present in the list.  */
 283 extern gl_list_node_t gl_list_search_from (gl_list_t list, size_t start_index,
 284                                            const void *elt);
 285 
 286 /* Searches whether an element is already in the list,
 287    at a position >= START_INDEX and < END_INDEX.
 288    Returns its node if found, or NULL if not present in the list.  */
 289 extern gl_list_node_t gl_list_search_from_to (gl_list_t list,
 290                                               size_t start_index,
 291                                               size_t end_index,
 292                                               const void *elt);
 293 
 294 /* Searches whether an element is already in the list.
 295    Returns its position if found, or (size_t)(-1) if not present in the list.  */
 296 extern size_t gl_list_indexof (gl_list_t list, const void *elt);
 297 
 298 /* Searches whether an element is already in the list,
 299    at a position >= START_INDEX.
 300    Returns its position if found, or (size_t)(-1) if not present in the list.  */
 301 extern size_t gl_list_indexof_from (gl_list_t list, size_t start_index,
 302                                     const void *elt);
 303 
 304 /* Searches whether an element is already in the list,
 305    at a position >= START_INDEX and < END_INDEX.
 306    Returns its position if found, or (size_t)(-1) if not present in the list.  */
 307 extern size_t gl_list_indexof_from_to (gl_list_t list,
 308                                        size_t start_index, size_t end_index,
 309                                        const void *elt);
 310 
 311 /* Adds an element as the first element of the list.
 312    Returns its node.  */
 313 /* declared in gl_xlist.h */
 314 extern gl_list_node_t gl_list_add_first (gl_list_t list, const void *elt);
 315 /* Likewise.  Returns NULL upon out-of-memory.  */
 316 _GL_ATTRIBUTE_NODISCARD
 317 extern gl_list_node_t gl_list_nx_add_first (gl_list_t list, const void *elt);
 318 
 319 /* Adds an element as the last element of the list.
 320    Returns its node.  */
 321 /* declared in gl_xlist.h */
 322 extern gl_list_node_t gl_list_add_last (gl_list_t list, const void *elt);
 323 /* Likewise.  Returns NULL upon out-of-memory.  */
 324 _GL_ATTRIBUTE_NODISCARD
 325 extern gl_list_node_t gl_list_nx_add_last (gl_list_t list, const void *elt);
 326 
 327 /* Adds an element before a given element node of the list.
 328    Returns its node.  */
 329 /* declared in gl_xlist.h */
 330 extern gl_list_node_t gl_list_add_before (gl_list_t list, gl_list_node_t node,
 331                                           const void *elt);
 332 /* Likewise.  Returns NULL upon out-of-memory.  */
 333 _GL_ATTRIBUTE_NODISCARD
 334 extern gl_list_node_t gl_list_nx_add_before (gl_list_t list,
 335                                              gl_list_node_t node,
 336                                              const void *elt);
 337 
 338 /* Adds an element after a given element node of the list.
 339    Returns its node.  */
 340 /* declared in gl_xlist.h */
 341 extern gl_list_node_t gl_list_add_after (gl_list_t list, gl_list_node_t node,
 342                                          const void *elt);
 343 /* Likewise.  Returns NULL upon out-of-memory.  */
 344 _GL_ATTRIBUTE_NODISCARD
 345 extern gl_list_node_t gl_list_nx_add_after (gl_list_t list, gl_list_node_t node,
 346                                             const void *elt);
 347 
 348 /* Adds an element at a given position in the list.
 349    POSITION must be >= 0 and <= gl_list_size (list).  */
 350 /* declared in gl_xlist.h */
 351 extern gl_list_node_t gl_list_add_at (gl_list_t list, size_t position,
 352                                       const void *elt);
 353 /* Likewise.  Returns NULL upon out-of-memory.  */
 354 _GL_ATTRIBUTE_NODISCARD
 355 extern gl_list_node_t gl_list_nx_add_at (gl_list_t list, size_t position,
 356                                          const void *elt);
 357 
 358 /* Removes an element from the list.
 359    Returns true.  */
 360 extern bool gl_list_remove_node (gl_list_t list, gl_list_node_t node);
 361 
 362 /* Removes an element at a given position from the list.
 363    POSITION must be >= 0 and < gl_list_size (list).
 364    Returns true.  */
 365 extern bool gl_list_remove_at (gl_list_t list, size_t position);
 366 
 367 /* Removes the element at the first position from the list.
 368    Returns true if it was found and removed, or false if the list was empty.  */
 369 extern bool gl_list_remove_first (gl_list_t list);
 370 
 371 /* Removes the element at the last position from the list.
 372    Returns true if it was found and removed, or false if the list was empty.  */
 373 extern bool gl_list_remove_last (gl_list_t list);
 374 
 375 /* Searches and removes an element from the list.
 376    Returns true if it was found and removed.  */
 377 extern bool gl_list_remove (gl_list_t list, const void *elt);
 378 
 379 /* Frees an entire list.
 380    (But this call does not free the elements of the list.  It only invokes
 381    the DISPOSE_FN on each of the elements of the list, and only if the list
 382    is not a sublist.)  */
 383 extern void gl_list_free (gl_list_t list);
 384 
 385 #endif /* End of inline and gl_xlist.h-defined functions.  */
 386 
 387 /* --------------------- gl_list_iterator_t Data Type --------------------- */
 388 
 389 /* Functions for iterating through a list.  */
 390 
 391 /* Type of an iterator that traverses a list.
 392    This is a fixed-size struct, so that creation of an iterator doesn't need
 393    memory allocation on the heap.  */
 394 typedef struct
 395 {
 396   /* For fast dispatch of gl_list_iterator_next.  */
 397   const struct gl_list_implementation *vtable;
 398   /* For detecting whether the last returned element was removed.  */
 399   gl_list_t list;
 400   size_t count;
 401   /* Other, implementation-private fields.  */
 402   void *p; void *q;
 403   size_t i; size_t j;
 404 } gl_list_iterator_t;
 405 
 406 #if 0 /* These are defined inline below.  */
 407 
 408 /* Creates an iterator traversing a list.
 409    The list contents must not be modified while the iterator is in use,
 410    except for replacing or removing the last returned element.  */
 411 extern gl_list_iterator_t gl_list_iterator (gl_list_t list);
 412 
 413 /* Creates an iterator traversing the element with indices i,
 414    start_index <= i < end_index, of a list.
 415    The list contents must not be modified while the iterator is in use,
 416    except for replacing or removing the last returned element.  */
 417 extern gl_list_iterator_t gl_list_iterator_from_to (gl_list_t list,
 418                                                     size_t start_index,
 419                                                     size_t end_index);
 420 
 421 /* If there is a next element, stores the next element in *ELTP, stores its
 422    node in *NODEP if NODEP is non-NULL, advances the iterator and returns true.
 423    Otherwise, returns false.  */
 424 extern bool gl_list_iterator_next (gl_list_iterator_t *iterator,
 425                                    const void **eltp, gl_list_node_t *nodep);
 426 
 427 /* Frees an iterator.  */
 428 extern void gl_list_iterator_free (gl_list_iterator_t *iterator);
 429 
 430 #endif /* End of inline functions.  */
 431 
 432 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
 433 
 434 /* The following functions are for lists without duplicates where the
 435    order is given by a sort criterion.  */
 436 
 437 /* Type of function used to compare two elements.  Same as for qsort().
 438    NULL denotes pointer comparison.  */
 439 typedef int (*gl_listelement_compar_fn) (const void *elt1, const void *elt2);
 440 
 441 #if 0 /* Unless otherwise specified, these are defined inline below.  */
 442 
 443 /* Searches whether an element is already in the list.
 444    The list is assumed to be sorted with COMPAR.
 445    Returns its node if found, or NULL if not present in the list.
 446    If the list contains several copies of ELT, the node of the leftmost one is
 447    returned.  */
 448 extern gl_list_node_t gl_sortedlist_search (gl_list_t list,
 449                                             gl_listelement_compar_fn compar,
 450                                             const void *elt);
 451 
 452 /* Searches whether an element is already in the list.
 453    The list is assumed to be sorted with COMPAR.
 454    Only list elements with indices >= START_INDEX and < END_INDEX are
 455    considered; the implementation uses these bounds to minimize the number
 456    of COMPAR invocations.
 457    Returns its node if found, or NULL if not present in the list.
 458    If the list contains several copies of ELT, the node of the leftmost one is
 459    returned.  */
 460 extern gl_list_node_t gl_sortedlist_search_from_to (gl_list_t list,
 461                                                     gl_listelement_compar_fn compar,
 462                                                     size_t start_index,
 463                                                     size_t end_index,
 464                                                     const void *elt);
 465 
 466 /* Searches whether an element is already in the list.
 467    The list is assumed to be sorted with COMPAR.
 468    Returns its position if found, or (size_t)(-1) if not present in the list.
 469    If the list contains several copies of ELT, the position of the leftmost one
 470    is returned.  */
 471 extern size_t gl_sortedlist_indexof (gl_list_t list,
 472                                      gl_listelement_compar_fn compar,
 473                                      const void *elt);
 474 
 475 /* Searches whether an element is already in the list.
 476    The list is assumed to be sorted with COMPAR.
 477    Only list elements with indices >= START_INDEX and < END_INDEX are
 478    considered; the implementation uses these bounds to minimize the number
 479    of COMPAR invocations.
 480    Returns its position if found, or (size_t)(-1) if not present in the list.
 481    If the list contains several copies of ELT, the position of the leftmost one
 482    is returned.  */
 483 extern size_t gl_sortedlist_indexof_from_to (gl_list_t list,
 484                                              gl_listelement_compar_fn compar,
 485                                              size_t start_index,
 486                                              size_t end_index,
 487                                              const void *elt);
 488 
 489 /* Adds an element at the appropriate position in the list.
 490    The list is assumed to be sorted with COMPAR.
 491    Returns its node.  */
 492 /* declared in gl_xlist.h */
 493 extern gl_list_node_t gl_sortedlist_add (gl_list_t list,
 494                                          gl_listelement_compar_fn compar,
 495                                          const void *elt);
 496 /* Likewise.  Returns NULL upon out-of-memory.  */
 497 _GL_ATTRIBUTE_NODISCARD
 498 extern gl_list_node_t gl_sortedlist_nx_add (gl_list_t list,
 499                                             gl_listelement_compar_fn compar,
 500                                             const void *elt);
 501 
 502 /* Searches and removes an element from the list.
 503    The list is assumed to be sorted with COMPAR.
 504    Returns true if it was found and removed.
 505    If the list contains several copies of ELT, only the leftmost one is
 506    removed.  */
 507 extern bool gl_sortedlist_remove (gl_list_t list,
 508                                   gl_listelement_compar_fn compar,
 509                                   const void *elt);
 510 
 511 #endif /* End of inline and gl_xlist.h-defined functions.  */
 512 
 513 /* ------------------------ Implementation Details ------------------------ */
 514 
 515 struct gl_list_implementation
 516 {
 517   /* gl_list_t functions.  */
 518   gl_list_t (*nx_create_empty) (gl_list_implementation_t implementation,
 519                                 gl_listelement_equals_fn equals_fn,
 520                                 gl_listelement_hashcode_fn hashcode_fn,
 521                                 gl_listelement_dispose_fn dispose_fn,
 522                                 bool allow_duplicates);
 523   gl_list_t (*nx_create) (gl_list_implementation_t implementation,
 524                           gl_listelement_equals_fn equals_fn,
 525                           gl_listelement_hashcode_fn hashcode_fn,
 526                           gl_listelement_dispose_fn dispose_fn,
 527                           bool allow_duplicates,
 528                           size_t count, const void **contents);
 529   size_t (*size) (gl_list_t list);
 530   const void * (*node_value) (gl_list_t list, gl_list_node_t node);
 531   int (*node_nx_set_value) (gl_list_t list, gl_list_node_t node,
 532                             const void *elt);
 533   gl_list_node_t (*next_node) (gl_list_t list, gl_list_node_t node);
 534   gl_list_node_t (*previous_node) (gl_list_t list, gl_list_node_t node);
 535   gl_list_node_t (*first_node) (gl_list_t list);
 536   gl_list_node_t (*last_node) (gl_list_t list);
 537   const void * (*get_at) (gl_list_t list, size_t position);
 538   gl_list_node_t (*nx_set_at) (gl_list_t list, size_t position,
 539                                const void *elt);
 540   gl_list_node_t (*search_from_to) (gl_list_t list, size_t start_index,
 541                                     size_t end_index, const void *elt);
 542   size_t (*indexof_from_to) (gl_list_t list, size_t start_index,
 543                              size_t end_index, const void *elt);
 544   gl_list_node_t (*nx_add_first) (gl_list_t list, const void *elt);
 545   gl_list_node_t (*nx_add_last) (gl_list_t list, const void *elt);
 546   gl_list_node_t (*nx_add_before) (gl_list_t list, gl_list_node_t node,
 547                                    const void *elt);
 548   gl_list_node_t (*nx_add_after) (gl_list_t list, gl_list_node_t node,
 549                                   const void *elt);
 550   gl_list_node_t (*nx_add_at) (gl_list_t list, size_t position,
 551                                const void *elt);
 552   bool (*remove_node) (gl_list_t list, gl_list_node_t node);
 553   bool (*remove_at) (gl_list_t list, size_t position);
 554   bool (*remove_elt) (gl_list_t list, const void *elt);
 555   void (*list_free) (gl_list_t list);
 556   /* gl_list_iterator_t functions.  */
 557   gl_list_iterator_t (*iterator) (gl_list_t list);
 558   gl_list_iterator_t (*iterator_from_to) (gl_list_t list,
 559                                           size_t start_index,
 560                                           size_t end_index);
 561   bool (*iterator_next) (gl_list_iterator_t *iterator,
 562                          const void **eltp, gl_list_node_t *nodep);
 563   void (*iterator_free) (gl_list_iterator_t *iterator);
 564   /* Sorted gl_list_t functions.  */
 565   gl_list_node_t (*sortedlist_search) (gl_list_t list,
 566                                        gl_listelement_compar_fn compar,
 567                                        const void *elt);
 568   gl_list_node_t (*sortedlist_search_from_to) (gl_list_t list,
 569                                                gl_listelement_compar_fn compar,
 570                                                size_t start_index,
 571                                                size_t end_index,
 572                                                const void *elt);
 573   size_t (*sortedlist_indexof) (gl_list_t list,
 574                                 gl_listelement_compar_fn compar,
 575                                 const void *elt);
 576   size_t (*sortedlist_indexof_from_to) (gl_list_t list,
 577                                         gl_listelement_compar_fn compar,
 578                                         size_t start_index, size_t end_index,
 579                                         const void *elt);
 580   gl_list_node_t (*sortedlist_nx_add) (gl_list_t list,
 581                                        gl_listelement_compar_fn compar,
 582                                     const void *elt);
 583   bool (*sortedlist_remove) (gl_list_t list,
 584                              gl_listelement_compar_fn compar,
 585                              const void *elt);
 586 };
 587 
 588 struct gl_list_impl_base
 589 {
 590   const struct gl_list_implementation *vtable;
 591   gl_listelement_equals_fn equals_fn;
 592   gl_listelement_hashcode_fn hashcode_fn;
 593   gl_listelement_dispose_fn dispose_fn;
 594   bool allow_duplicates;
 595 };
 596 
 597 /* Define all functions of this file as accesses to the
 598    struct gl_list_implementation.  */
 599 
 600 GL_LIST_INLINE
 601 /*_GL_ATTRIBUTE_DEALLOC (gl_list_free, 1)*/
 602 gl_list_t
 603 gl_list_nx_create_empty (gl_list_implementation_t implementation,
     /*  */
 604                          gl_listelement_equals_fn equals_fn,
 605                          gl_listelement_hashcode_fn hashcode_fn,
 606                          gl_listelement_dispose_fn dispose_fn,
 607                          bool allow_duplicates)
 608 {
 609   return implementation->nx_create_empty (implementation, equals_fn,
 610                                           hashcode_fn, dispose_fn,
 611                                           allow_duplicates);
 612 }
 613 
 614 GL_LIST_INLINE
 615 /*_GL_ATTRIBUTE_DEALLOC (gl_list_free, 1)*/
 616 gl_list_t
 617 gl_list_nx_create (gl_list_implementation_t implementation,
     /*  */
 618                    gl_listelement_equals_fn equals_fn,
 619                    gl_listelement_hashcode_fn hashcode_fn,
 620                    gl_listelement_dispose_fn dispose_fn,
 621                    bool allow_duplicates,
 622                    size_t count, const void **contents)
 623 {
 624   return implementation->nx_create (implementation, equals_fn, hashcode_fn,
 625                                     dispose_fn, allow_duplicates, count,
 626                                     contents);
 627 }
 628 
 629 GL_LIST_INLINE size_t
 630 gl_list_size (gl_list_t list)
     /*  */
 631 {
 632   return ((const struct gl_list_impl_base *) list)->vtable
 633          ->size (list);
 634 }
 635 
 636 GL_LIST_INLINE const void *
 637 gl_list_node_value (gl_list_t list, gl_list_node_t node)
     /*  */
 638 {
 639   return ((const struct gl_list_impl_base *) list)->vtable
 640          ->node_value (list, node);
 641 }
 642 
 643 _GL_ATTRIBUTE_NODISCARD GL_LIST_INLINE int
 644 gl_list_node_nx_set_value (gl_list_t list, gl_list_node_t node,
     /*  */
 645                            const void *elt)
 646 {
 647   return ((const struct gl_list_impl_base *) list)->vtable
 648          ->node_nx_set_value (list, node, elt);
 649 }
 650 
 651 GL_LIST_INLINE gl_list_node_t
 652 gl_list_next_node (gl_list_t list, gl_list_node_t node)
     /*  */
 653 {
 654   return ((const struct gl_list_impl_base *) list)->vtable
 655          ->next_node (list, node);
 656 }
 657 
 658 GL_LIST_INLINE gl_list_node_t
 659 gl_list_previous_node (gl_list_t list, gl_list_node_t node)
     /*  */
 660 {
 661   return ((const struct gl_list_impl_base *) list)->vtable
 662          ->previous_node (list, node);
 663 }
 664 
 665 GL_LIST_INLINE gl_list_node_t
 666 gl_list_first_node (gl_list_t list)
     /*  */
 667 {
 668   return ((const struct gl_list_impl_base *) list)->vtable
 669          ->first_node (list);
 670 }
 671 
 672 GL_LIST_INLINE gl_list_node_t
 673 gl_list_last_node (gl_list_t list)
     /*  */
 674 {
 675   return ((const struct gl_list_impl_base *) list)->vtable
 676          ->last_node (list);
 677 }
 678 
 679 GL_LIST_INLINE const void *
 680 gl_list_get_at (gl_list_t list, size_t position)
     /*  */
 681 {
 682   return ((const struct gl_list_impl_base *) list)->vtable
 683          ->get_at (list, position);
 684 }
 685 
 686 GL_LIST_INLINE const void *
 687 gl_list_get_first (gl_list_t list)
     /*  */
 688 {
 689   return gl_list_get_at (list, 0);
 690 }
 691 
 692 GL_LIST_INLINE const void *
 693 gl_list_get_last (gl_list_t list)
     /*  */
 694 {
 695   return gl_list_get_at (list, gl_list_size (list) - 1);
 696 }
 697 
 698 _GL_ATTRIBUTE_NODISCARD GL_LIST_INLINE gl_list_node_t
 699 gl_list_nx_set_at (gl_list_t list, size_t position, const void *elt)
     /*  */
 700 {
 701   return ((const struct gl_list_impl_base *) list)->vtable
 702          ->nx_set_at (list, position, elt);
 703 }
 704 
 705 _GL_ATTRIBUTE_NODISCARD GL_LIST_INLINE gl_list_node_t
 706 gl_list_nx_set_first (gl_list_t list, const void *elt)
     /*  */
 707 {
 708   return gl_list_nx_set_at (list, 0, elt);
 709 }
 710 
 711 _GL_ATTRIBUTE_NODISCARD GL_LIST_INLINE gl_list_node_t
 712 gl_list_nx_set_last (gl_list_t list, const void *elt)
     /*  */
 713 {
 714   return gl_list_nx_set_at (list, gl_list_size (list) - 1, elt);
 715 }
 716 
 717 GL_LIST_INLINE gl_list_node_t
 718 gl_list_search (gl_list_t list, const void *elt)
     /*  */
 719 {
 720   size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
 721   return ((const struct gl_list_impl_base *) list)->vtable
 722          ->search_from_to (list, 0, size, elt);
 723 }
 724 
 725 GL_LIST_INLINE gl_list_node_t
 726 gl_list_search_from (gl_list_t list, size_t start_index, const void *elt)
     /*  */
 727 {
 728   size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
 729   return ((const struct gl_list_impl_base *) list)->vtable
 730          ->search_from_to (list, start_index, size, elt);
 731 }
 732 
 733 GL_LIST_INLINE gl_list_node_t
 734 gl_list_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
     /*  */
 735                         const void *elt)
 736 {
 737   return ((const struct gl_list_impl_base *) list)->vtable
 738          ->search_from_to (list, start_index, end_index, elt);
 739 }
 740 
 741 GL_LIST_INLINE size_t
 742 gl_list_indexof (gl_list_t list, const void *elt)
     /*  */
 743 {
 744   size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
 745   return ((const struct gl_list_impl_base *) list)->vtable
 746          ->indexof_from_to (list, 0, size, elt);
 747 }
 748 
 749 GL_LIST_INLINE size_t
 750 gl_list_indexof_from (gl_list_t list, size_t start_index, const void *elt)
     /*  */
 751 {
 752   size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
 753   return ((const struct gl_list_impl_base *) list)->vtable
 754          ->indexof_from_to (list, start_index, size, elt);
 755 }
 756 
 757 GL_LIST_INLINE size_t
 758 gl_list_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
     /*  */
 759                          const void *elt)
 760 {
 761   return ((const struct gl_list_impl_base *) list)->vtable
 762          ->indexof_from_to (list, start_index, end_index, elt);
 763 }
 764 
 765 _GL_ATTRIBUTE_NODISCARD GL_LIST_INLINE gl_list_node_t
 766 gl_list_nx_add_first (gl_list_t list, const void *elt)
     /*  */
 767 {
 768   return ((const struct gl_list_impl_base *) list)->vtable
 769          ->nx_add_first (list, elt);
 770 }
 771 
 772 _GL_ATTRIBUTE_NODISCARD GL_LIST_INLINE gl_list_node_t
 773 gl_list_nx_add_last (gl_list_t list, const void *elt)
     /*  */
 774 {
 775   return ((const struct gl_list_impl_base *) list)->vtable
 776          ->nx_add_last (list, elt);
 777 }
 778 
 779 _GL_ATTRIBUTE_NODISCARD GL_LIST_INLINE gl_list_node_t
 780 gl_list_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
     /*  */
 781 {
 782   return ((const struct gl_list_impl_base *) list)->vtable
 783          ->nx_add_before (list, node, elt);
 784 }
 785 
 786 _GL_ATTRIBUTE_NODISCARD GL_LIST_INLINE gl_list_node_t
 787 gl_list_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
     /*  */
 788 {
 789   return ((const struct gl_list_impl_base *) list)->vtable
 790          ->nx_add_after (list, node, elt);
 791 }
 792 
 793 _GL_ATTRIBUTE_NODISCARD GL_LIST_INLINE gl_list_node_t
 794 gl_list_nx_add_at (gl_list_t list, size_t position, const void *elt)
     /*  */
 795 {
 796   return ((const struct gl_list_impl_base *) list)->vtable
 797          ->nx_add_at (list, position, elt);
 798 }
 799 
 800 GL_LIST_INLINE bool
 801 gl_list_remove_node (gl_list_t list, gl_list_node_t node)
     /*  */
 802 {
 803   return ((const struct gl_list_impl_base *) list)->vtable
 804          ->remove_node (list, node);
 805 }
 806 
 807 GL_LIST_INLINE bool
 808 gl_list_remove_at (gl_list_t list, size_t position)
     /*  */
 809 {
 810   return ((const struct gl_list_impl_base *) list)->vtable
 811          ->remove_at (list, position);
 812 }
 813 
 814 GL_LIST_INLINE bool
 815 gl_list_remove_first (gl_list_t list)
     /*  */
 816 {
 817   size_t size = gl_list_size (list);
 818   if (size > 0)
 819     return gl_list_remove_at (list, 0);
 820   else
 821     return false;
 822 }
 823 
 824 GL_LIST_INLINE bool
 825 gl_list_remove_last (gl_list_t list)
     /*  */
 826 {
 827   size_t size = gl_list_size (list);
 828   if (size > 0)
 829     return gl_list_remove_at (list, size - 1);
 830   else
 831     return false;
 832 }
 833 
 834 GL_LIST_INLINE bool
 835 gl_list_remove (gl_list_t list, const void *elt)
     /*  */
 836 {
 837   return ((const struct gl_list_impl_base *) list)->vtable
 838          ->remove_elt (list, elt);
 839 }
 840 
 841 GL_LIST_INLINE void
 842 gl_list_free (gl_list_t list)
     /*  */
 843 {
 844   ((const struct gl_list_impl_base *) list)->vtable->list_free (list);
 845 }
 846 
 847 GL_LIST_INLINE gl_list_iterator_t
 848 gl_list_iterator (gl_list_t list)
     /*  */
 849 {
 850   return ((const struct gl_list_impl_base *) list)->vtable
 851          ->iterator (list);
 852 }
 853 
 854 GL_LIST_INLINE gl_list_iterator_t
 855 gl_list_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
     /*  */
 856 {
 857   return ((const struct gl_list_impl_base *) list)->vtable
 858          ->iterator_from_to (list, start_index, end_index);
 859 }
 860 
 861 GL_LIST_INLINE bool
 862 gl_list_iterator_next (gl_list_iterator_t *iterator,
     /*  */
 863                        const void **eltp, gl_list_node_t *nodep)
 864 {
 865   return iterator->vtable->iterator_next (iterator, eltp, nodep);
 866 }
 867 
 868 GL_LIST_INLINE void
 869 gl_list_iterator_free (gl_list_iterator_t *iterator)
     /*  */
 870 {
 871   iterator->vtable->iterator_free (iterator);
 872 }
 873 
 874 GL_LIST_INLINE gl_list_node_t
 875 gl_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
     /*  */
 876 {
 877   return ((const struct gl_list_impl_base *) list)->vtable
 878          ->sortedlist_search (list, compar, elt);
 879 }
 880 
 881 GL_LIST_INLINE gl_list_node_t
 882 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)
     /*  */
 883 {
 884   return ((const struct gl_list_impl_base *) list)->vtable
 885          ->sortedlist_search_from_to (list, compar, start_index, end_index,
 886                                       elt);
 887 }
 888 
 889 GL_LIST_INLINE size_t
 890 gl_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
     /*  */
 891 {
 892   return ((const struct gl_list_impl_base *) list)->vtable
 893          ->sortedlist_indexof (list, compar, elt);
 894 }
 895 
 896 GL_LIST_INLINE size_t
 897 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)
     /*  */
 898 {
 899   return ((const struct gl_list_impl_base *) list)->vtable
 900          ->sortedlist_indexof_from_to (list, compar, start_index, end_index,
 901                                        elt);
 902 }
 903 
 904 _GL_ATTRIBUTE_NODISCARD GL_LIST_INLINE gl_list_node_t
 905 gl_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
     /*  */
 906 {
 907   return ((const struct gl_list_impl_base *) list)->vtable
 908          ->sortedlist_nx_add (list, compar, elt);
 909 }
 910 
 911 GL_LIST_INLINE bool
 912 gl_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
     /*  */
 913 {
 914   return ((const struct gl_list_impl_base *) list)->vtable
 915          ->sortedlist_remove (list, compar, elt);
 916 }
 917 
 918 #ifdef __cplusplus
 919 }
 920 #endif
 921 
 922 _GL_INLINE_HEADER_END
 923 
 924 #endif /* _GL_LIST_H */
/* */
root/maint/gnulib/lib/gl_list.h

INCLUDED FROM

DEFINITIONS
