root/maint/gnulib/lib/gl_oset.h

/* [previous][next][first][last][top][bottom][index][help] */

INCLUDED FROM


DEFINITIONS

This source file includes following definitions.
  1. gl_oset_create_empty
  2. gl_oset_nx_create_empty
  3. gl_oset_size
  4. gl_oset_search
  5. gl_oset_search_atleast
  6. gl_oset_nx_add
  7. gl_oset_remove
  8. gl_oset_update
  9. gl_oset_free
  10. gl_oset_iterator
  11. gl_oset_iterator_atleast
  12. gl_oset_iterator_next
  13. gl_oset_iterator_free

   1 /* Abstract ordered set data type.
   2    Copyright (C) 2006-2007, 2009-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_OSET_H
  19 #define _GL_OSET_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_OSET_INLINE
  29 # define GL_OSET_INLINE _GL_INLINE
  30 #endif
  31 
  32 #ifdef __cplusplus
  33 extern "C" {
  34 #endif
  35 
  36 
  37 /* gl_oset is an abstract ordered set data type.  It can contain any number
  38    of objects ('void *' or 'const void *' pointers) in the order of a given
  39    comparator function.  Duplicates (in the sense of the comparator) are
  40    forbidden.
  41 
  42    There are several implementations of this ordered set datatype, optimized
  43    for different operations or for memory.  You can start using the simplest
  44    ordered set implementation, GL_ARRAY_OSET, and switch to a different
  45    implementation later, when you realize which operations are performed
  46    the most frequently.  The API of the different implementations is exactly
  47    the same; when switching to a different implementation, you only have to
  48    change the gl_oset_create call.
  49 
  50    The implementations are:
  51      GL_ARRAY_OSET        a growable array
  52      GL_AVLTREE_OSET      a binary tree (AVL tree)
  53      GL_RBTREE_OSET       a binary tree (red-black tree)
  54 
  55    The memory consumption is asymptotically the same: O(1) for every object
  56    in the set.  When looking more closely at the average memory consumed
  57    for an object, GL_ARRAY_OSET is the most compact representation, and
  58    GL_AVLTREE_OSET, GL_RBTREE_OSET need more memory.
  59 
  60    The guaranteed average performance of the operations is, for a set of
  61    n elements:
  62 
  63    Operation                  ARRAY     TREE
  64 
  65    gl_oset_size                O(1)     O(1)
  66    gl_oset_add                 O(n)   O(log n)
  67    gl_oset_remove              O(n)   O(log n)
  68    gl_oset_update              O(n)   O(log n)
  69    gl_oset_search            O(log n) O(log n)
  70    gl_oset_search_atleast    O(log n) O(log n)
  71    gl_oset_iterator            O(1)   O(log n)
  72    gl_oset_iterator_atleast  O(log n) O(log n)
  73    gl_oset_iterator_next       O(1)   O(log n)
  74  */
  75 
  76 /* -------------------------- gl_oset_t Data Type -------------------------- */
  77 
  78 /* Type of function used to compare two elements.  Same as for qsort().
  79    NULL denotes pointer comparison.  */
  80 typedef int (*gl_setelement_compar_fn) (const void *elt1, const void *elt2);
  81 
  82 #ifndef _GL_SETELEMENT_DISPOSE_FN_DEFINED
  83 /* Type of function used to dispose an element once it's removed from a set.
  84    NULL denotes a no-op.  */
  85 typedef void (*gl_setelement_dispose_fn) (const void *elt);
  86 # define _GL_SETELEMENT_DISPOSE_FN_DEFINED 1
  87 #endif
  88 
  89 /* Type of function used to compare an element with a threshold.
  90    Returns true if the element is greater or equal than the threshold.  */
  91 typedef bool (*gl_setelement_threshold_fn) (const void *elt, const void *threshold);
  92 
  93 struct gl_oset_impl;
  94 /* Type representing an entire ordered set.  */
  95 typedef struct gl_oset_impl * gl_oset_t;
  96 
  97 struct gl_oset_implementation;
  98 /* Type representing a ordered set datatype implementation.  */
  99 typedef const struct gl_oset_implementation * gl_oset_implementation_t;
 100 
 101 #if 0 /* Unless otherwise specified, these are defined inline below.  */
 102 
 103 /* Creates an empty set.
 104    IMPLEMENTATION is one of GL_ARRAY_OSET, GL_AVLTREE_OSET, GL_RBTREE_OSET.
 105    COMPAR_FN is an element comparison function or NULL.
 106    DISPOSE_FN is an element disposal function or NULL.  */
 107 /* declared in gl_xoset.h */
 108 extern gl_oset_t gl_oset_create_empty (gl_oset_implementation_t implementation,
     /* [previous][next][first][last][top][bottom][index][help] */
 109                                        gl_setelement_compar_fn compar_fn,
 110                                        gl_setelement_dispose_fn dispose_fn)
 111   /*_GL_ATTRIBUTE_DEALLOC (gl_oset_free, 1)*/
 112   _GL_ATTRIBUTE_RETURNS_NONNULL;
 113 /* Likewise.  Returns NULL upon out-of-memory.  */
 114 extern gl_oset_t gl_oset_nx_create_empty (gl_oset_implementation_t implementation,
 115                                           gl_setelement_compar_fn compar_fn,
 116                                           gl_setelement_dispose_fn dispose_fn)
 117   /*_GL_ATTRIBUTE_DEALLOC (gl_oset_free, 1)*/;
 118 
 119 /* Returns the current number of elements in an ordered set.  */
 120 extern size_t gl_oset_size (gl_oset_t set);
 121 
 122 /* Searches whether an element is already in the ordered set.
 123    Returns true if found, or false if not present in the set.  */
 124 extern bool gl_oset_search (gl_oset_t set, const void *elt);
 125 
 126 /* Searches the least element in the ordered set that compares greater or equal
 127    to the given THRESHOLD.  The representation of the THRESHOLD is defined
 128    by the THRESHOLD_FN.
 129    Returns true and stores the found element in *ELTP if found, otherwise returns
 130    false.  */
 131 extern bool gl_oset_search_atleast (gl_oset_t set,
 132                                     gl_setelement_threshold_fn threshold_fn,
 133                                     const void *threshold,
 134                                     const void **eltp);
 135 
 136 /* Adds an element to an ordered set.
 137    Returns true if it was not already in the set and added, false otherwise.  */
 138 /* declared in gl_xoset.h */
 139 extern bool gl_oset_add (gl_oset_t set, const void *elt);
 140 
 141 /* Likewise.  Returns -1 upon out-of-memory.  */
 142 _GL_ATTRIBUTE_NODISCARD
 143 extern int gl_oset_nx_add (gl_oset_t set, const void *elt);
 144 
 145 /* Removes an element from an ordered set.
 146    Returns true if it was found and removed.  */
 147 extern bool gl_oset_remove (gl_oset_t set, const void *elt);
 148 
 149 /* Invokes ACTION (ELT, ACTION_DATA) and updates the given ordered set if,
 150    during this invocation, the attributes/properties of the element ELT change
 151    in a way that influences the comparison function.
 152    Warning: During the invocation of ACTION, the ordered set is inconsistent
 153    and must not be accessed!
 154    Returns 1 if the position of the element in the ordered set has changed as
 155    a consequence, 0 if the element stayed at the same position, or -1 if it
 156    collided with another element and was therefore removed.  */
 157 extern int gl_oset_update (gl_oset_t set, const void *elt,
 158                            void (*action) (const void *elt, void *action_data),
 159                            void *action_data);
 160 
 161 /* Frees an entire ordered set.
 162    (But this call does not free the elements of the set.  It only invokes
 163    the DISPOSE_FN on each of the elements of the set.)  */
 164 extern void gl_oset_free (gl_oset_t set);
 165 
 166 #endif /* End of inline and gl_xoset.h-defined functions.  */
 167 
 168 /* --------------------- gl_oset_iterator_t Data Type --------------------- */
 169 
 170 /* Functions for iterating through an ordered set.  */
 171 
 172 /* Type of an iterator that traverses an ordered set.
 173    This is a fixed-size struct, so that creation of an iterator doesn't need
 174    memory allocation on the heap.  */
 175 typedef struct
 176 {
 177   /* For fast dispatch of gl_oset_iterator_next.  */
 178   const struct gl_oset_implementation *vtable;
 179   /* For detecting whether the last returned element was removed.  */
 180   gl_oset_t set;
 181   size_t count;
 182   /* Other, implementation-private fields.  */
 183   void *p; void *q;
 184   size_t i; size_t j;
 185 } gl_oset_iterator_t;
 186 
 187 #if 0 /* These are defined inline below.  */
 188 
 189 /* Creates an iterator traversing an ordered set.
 190    The set's contents must not be modified while the iterator is in use,
 191    except for removing the last returned element.  */
 192 extern gl_oset_iterator_t gl_oset_iterator (gl_oset_t set);
 193 
 194 /* Creates an iterator traversing the tail of an ordered set, that comprises
 195    the elements that compare greater or equal to the given THRESHOLD.  The
 196    representation of the THRESHOLD is defined by the THRESHOLD_FN.  */
 197 extern gl_oset_iterator_t gl_oset_iterator_atleast (gl_oset_t set,
 198                                                     gl_setelement_threshold_fn threshold_fn,
 199                                                     const void *threshold);
 200 
 201 /* If there is a next element, stores the next element in *ELTP, advances the
 202    iterator and returns true.  Otherwise, returns false.  */
 203 extern bool gl_oset_iterator_next (gl_oset_iterator_t *iterator,
 204                                    const void **eltp);
 205 
 206 /* Frees an iterator.  */
 207 extern void gl_oset_iterator_free (gl_oset_iterator_t *iterator);
 208 
 209 #endif /* End of inline functions.  */
 210 
 211 /* ------------------------ Implementation Details ------------------------ */
 212 
 213 struct gl_oset_implementation
 214 {
 215   /* gl_oset_t functions.  */
 216   gl_oset_t (*nx_create_empty) (gl_oset_implementation_t implementation,
 217                                 gl_setelement_compar_fn compar_fn,
 218                                 gl_setelement_dispose_fn dispose_fn);
 219   size_t (*size) (gl_oset_t set);
 220   bool (*search) (gl_oset_t set, const void *elt);
 221   bool (*search_atleast) (gl_oset_t set,
 222                           gl_setelement_threshold_fn threshold_fn,
 223                           const void *threshold, const void **eltp);
 224   int (*nx_add) (gl_oset_t set, const void *elt);
 225   bool (*remove_elt) (gl_oset_t set, const void *elt);
 226   int (*update) (gl_oset_t set, const void *elt,
 227                  void (*action) (const void * /*elt*/, void * /*action_data*/),
 228                  void *action_data);
 229   void (*oset_free) (gl_oset_t set);
 230   /* gl_oset_iterator_t functions.  */
 231   gl_oset_iterator_t (*iterator) (gl_oset_t set);
 232   gl_oset_iterator_t (*iterator_atleast) (gl_oset_t set,
 233                                           gl_setelement_threshold_fn threshold_fn,
 234                                           const void *threshold);
 235   bool (*iterator_next) (gl_oset_iterator_t *iterator, const void **eltp);
 236   void (*iterator_free) (gl_oset_iterator_t *iterator);
 237 };
 238 
 239 struct gl_oset_impl_base
 240 {
 241   const struct gl_oset_implementation *vtable;
 242   gl_setelement_compar_fn compar_fn;
 243   gl_setelement_dispose_fn dispose_fn;
 244 };
 245 
 246 /* Define all functions of this file as accesses to the
 247    struct gl_oset_implementation.  */
 248 
 249 GL_OSET_INLINE
 250 /*_GL_ATTRIBUTE_DEALLOC (gl_oset_free, 1)*/
 251 gl_oset_t
 252 gl_oset_nx_create_empty (gl_oset_implementation_t implementation,
     /* [previous][next][first][last][top][bottom][index][help] */
 253                          gl_setelement_compar_fn compar_fn,
 254                          gl_setelement_dispose_fn dispose_fn)
 255 {
 256   return implementation->nx_create_empty (implementation, compar_fn,
 257                                           dispose_fn);
 258 }
 259 
 260 GL_OSET_INLINE size_t
 261 gl_oset_size (gl_oset_t set)
     /* [previous][next][first][last][top][bottom][index][help] */
 262 {
 263   return ((const struct gl_oset_impl_base *) set)->vtable->size (set);
 264 }
 265 
 266 GL_OSET_INLINE bool
 267 gl_oset_search (gl_oset_t set, const void *elt)
     /* [previous][next][first][last][top][bottom][index][help] */
 268 {
 269   return ((const struct gl_oset_impl_base *) set)->vtable->search (set, elt);
 270 }
 271 
 272 GL_OSET_INLINE bool
 273 gl_oset_search_atleast (gl_oset_t set,
     /* [previous][next][first][last][top][bottom][index][help] */
 274                         gl_setelement_threshold_fn threshold_fn,
 275                         const void *threshold, const void **eltp)
 276 {
 277   return ((const struct gl_oset_impl_base *) set)->vtable
 278          ->search_atleast (set, threshold_fn, threshold, eltp);
 279 }
 280 
 281 _GL_ATTRIBUTE_NODISCARD GL_OSET_INLINE int
 282 gl_oset_nx_add (gl_oset_t set, const void *elt)
     /* [previous][next][first][last][top][bottom][index][help] */
 283 {
 284   return ((const struct gl_oset_impl_base *) set)->vtable->nx_add (set, elt);
 285 }
 286 
 287 GL_OSET_INLINE bool
 288 gl_oset_remove (gl_oset_t set, const void *elt)
     /* [previous][next][first][last][top][bottom][index][help] */
 289 {
 290   return ((const struct gl_oset_impl_base *) set)->vtable
 291          ->remove_elt (set, elt);
 292 }
 293 
 294 GL_OSET_INLINE int
 295 gl_oset_update (gl_oset_t set, const void *elt,
     /* [previous][next][first][last][top][bottom][index][help] */
 296                 void (*action) (const void * /*elt*/, void * /*action_data*/),
 297                 void *action_data)
 298 {
 299   return ((const struct gl_oset_impl_base *) set)->vtable
 300          ->update (set, elt, action, action_data);
 301 }
 302 
 303 GL_OSET_INLINE void
 304 gl_oset_free (gl_oset_t set)
     /* [previous][next][first][last][top][bottom][index][help] */
 305 {
 306   ((const struct gl_oset_impl_base *) set)->vtable->oset_free (set);
 307 }
 308 
 309 GL_OSET_INLINE gl_oset_iterator_t
 310 gl_oset_iterator (gl_oset_t set)
     /* [previous][next][first][last][top][bottom][index][help] */
 311 {
 312   return ((const struct gl_oset_impl_base *) set)->vtable->iterator (set);
 313 }
 314 
 315 GL_OSET_INLINE gl_oset_iterator_t
 316 gl_oset_iterator_atleast (gl_oset_t set,
     /* [previous][next][first][last][top][bottom][index][help] */
 317                           gl_setelement_threshold_fn threshold_fn,
 318                           const void *threshold)
 319 {
 320   return ((const struct gl_oset_impl_base *) set)->vtable
 321          ->iterator_atleast (set, threshold_fn, threshold);
 322 }
 323 
 324 GL_OSET_INLINE bool
 325 gl_oset_iterator_next (gl_oset_iterator_t *iterator, const void **eltp)
     /* [previous][next][first][last][top][bottom][index][help] */
 326 {
 327   return iterator->vtable->iterator_next (iterator, eltp);
 328 }
 329 
 330 GL_OSET_INLINE void
 331 gl_oset_iterator_free (gl_oset_iterator_t *iterator)
     /* [previous][next][first][last][top][bottom][index][help] */
 332 {
 333   iterator->vtable->iterator_free (iterator);
 334 }
 335 
 336 #ifdef __cplusplus
 337 }
 338 #endif
 339 
 340 _GL_INLINE_HEADER_END
 341 
 342 #endif /* _GL_OSET_H */

/* [previous][next][first][last][top][bottom][index][help] */