lib/gl_oset.h

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