lib/gl_oset.h

   1 /* Abstract ordered set data type.
   2    Copyright (C) 2006-2007, 2009-2020 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 <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,
 109                                        gl_setelement_compar_fn compar_fn,
 110                                        gl_setelement_dispose_fn dispose_fn);
 111 /* Likewise.  Returns NULL upon out-of-memory.  */
 112 extern gl_oset_t gl_oset_nx_create_empty (gl_oset_implementation_t implementation,
 113                                           gl_setelement_compar_fn compar_fn,
 114                                           gl_setelement_dispose_fn dispose_fn);
 115
 116 /* Returns the current number of elements in an ordered set.  */
 117 extern size_t gl_oset_size (gl_oset_t set);
 118
 119 /* Searches whether an element is already in the ordered set.
 120    Returns true if found, or false if not present in the set.  */
 121 extern bool gl_oset_search (gl_oset_t set, const void *elt);
 122
 123 /* Searches the least element in the ordered set that compares greater or equal
 124    to the given THRESHOLD.  The representation of the THRESHOLD is defined
 125    by the THRESHOLD_FN.
 126    Returns true and stores the found element in *ELTP if found, otherwise returns
 127    false.  */
 128 extern bool gl_oset_search_atleast (gl_oset_t set,
 129                                     gl_setelement_threshold_fn threshold_fn,
 130                                     const void *threshold,
 131                                     const void **eltp);
 132
 133 /* Adds an element to an ordered set.
 134    Returns true if it was not already in the set and added, false otherwise.  */
 135 /* declared in gl_xoset.h */
 136 extern bool gl_oset_add (gl_oset_t set, const void *elt);
 137 /* Likewise.  Returns -1 upon out-of-memory.  */
 138 extern int gl_oset_nx_add (gl_oset_t set, const void *elt)
 139   _GL_ATTRIBUTE_NODISCARD;
 140
 141 /* Removes an element from an ordered set.
 142    Returns true if it was found and removed.  */
 143 extern bool gl_oset_remove (gl_oset_t set, const void *elt);
 144
 145 /* Invokes ACTION (ELT, ACTION_DATA) and updates the given ordered set if,
 146    during this invocation, the attributes/properties of the element ELT change
 147    in a way that influences the comparison function.
 148    Warning: During the invocation of ACTION, the ordered set is inconsistent
 149    and must not be accessed!
 150    Returns 1 if the position of the element in the ordered set has changed as
 151    a consequence, 0 if the element stayed at the same position, or -1 if it
 152    collided with another element and was therefore removed.  */
 153 extern int gl_oset_update (gl_oset_t set, const void *elt,
 154                            void (*action) (const void *elt, void *action_data),
 155                            void *action_data);
 156
 157 /* Frees an entire ordered set.
 158    (But this call does not free the elements of the set.  It only invokes
 159    the DISPOSE_FN on each of the elements of the set.)  */
 160 extern void gl_oset_free (gl_oset_t set);
 161
 162 #endif /* End of inline and gl_xoset.h-defined functions.  */
 163
 164 /* --------------------- gl_oset_iterator_t Data Type --------------------- */
 165
 166 /* Functions for iterating through an ordered set.  */
 167
 168 /* Type of an iterator that traverses an ordered set.
 169    This is a fixed-size struct, so that creation of an iterator doesn't need
 170    memory allocation on the heap.  */
 171 typedef struct
 172 {
 173   /* For fast dispatch of gl_oset_iterator_next.  */
 174   const struct gl_oset_implementation *vtable;
 175   /* For detecting whether the last returned element was removed.  */
 176   gl_oset_t set;
 177   size_t count;
 178   /* Other, implementation-private fields.  */
 179   void *p; void *q;
 180   size_t i; size_t j;
 181 } gl_oset_iterator_t;
 182
 183 #if 0 /* These are defined inline below.  */
 184
 185 /* Creates an iterator traversing an ordered set.
 186    The set's contents must not be modified while the iterator is in use,
 187    except for removing the last returned element.  */
 188 extern gl_oset_iterator_t gl_oset_iterator (gl_oset_t set);
 189
 190 /* Creates an iterator traversing the tail of an ordered set, that comprises
 191    the elements that compare greater or equal to the given THRESHOLD.  The
 192    representation of the THRESHOLD is defined by the THRESHOLD_FN.  */
 193 extern gl_oset_iterator_t gl_oset_iterator_atleast (gl_oset_t set,
 194                                                     gl_setelement_threshold_fn threshold_fn,
 195                                                     const void *threshold);
 196
 197 /* If there is a next element, stores the next element in *ELTP, advances the
 198    iterator and returns true.  Otherwise, returns false.  */
 199 extern bool gl_oset_iterator_next (gl_oset_iterator_t *iterator,
 200                                    const void **eltp);
 201
 202 /* Frees an iterator.  */
 203 extern void gl_oset_iterator_free (gl_oset_iterator_t *iterator);
 204
 205 #endif /* End of inline functions.  */
 206
 207 /* ------------------------ Implementation Details ------------------------ */
 208
 209 struct gl_oset_implementation
 210 {
 211   /* gl_oset_t functions.  */
 212   gl_oset_t (*nx_create_empty) (gl_oset_implementation_t implementation,
 213                                 gl_setelement_compar_fn compar_fn,
 214                                 gl_setelement_dispose_fn dispose_fn);
 215   size_t (*size) (gl_oset_t set);
 216   bool (*search) (gl_oset_t set, const void *elt);
 217   bool (*search_atleast) (gl_oset_t set,
 218                           gl_setelement_threshold_fn threshold_fn,
 219                           const void *threshold, const void **eltp);
 220   int (*nx_add) (gl_oset_t set, const void *elt);
 221   bool (*remove_elt) (gl_oset_t set, const void *elt);
 222   int (*update) (gl_oset_t set, const void *elt,
 223                  void (*action) (const void * /*elt*/, void * /*action_data*/),
 224                  void *action_data);
 225   void (*oset_free) (gl_oset_t set);
 226   /* gl_oset_iterator_t functions.  */
 227   gl_oset_iterator_t (*iterator) (gl_oset_t set);
 228   gl_oset_iterator_t (*iterator_atleast) (gl_oset_t set,
 229                                           gl_setelement_threshold_fn threshold_fn,
 230                                           const void *threshold);
 231   bool (*iterator_next) (gl_oset_iterator_t *iterator, const void **eltp);
 232   void (*iterator_free) (gl_oset_iterator_t *iterator);
 233 };
 234
 235 struct gl_oset_impl_base
 236 {
 237   const struct gl_oset_implementation *vtable;
 238   gl_setelement_compar_fn compar_fn;
 239   gl_setelement_dispose_fn dispose_fn;
 240 };
 241
 242 /* Define all functions of this file as accesses to the
 243    struct gl_oset_implementation.  */
 244
 245 GL_OSET_INLINE gl_oset_t
 246 gl_oset_nx_create_empty (gl_oset_implementation_t implementation,
 247                          gl_setelement_compar_fn compar_fn,
 248                          gl_setelement_dispose_fn dispose_fn)
 249 {
 250   return implementation->nx_create_empty (implementation, compar_fn,
 251                                           dispose_fn);
 252 }
 253
 254 GL_OSET_INLINE size_t
 255 gl_oset_size (gl_oset_t set)
 256 {
 257   return ((const struct gl_oset_impl_base *) set)->vtable->size (set);
 258 }
 259
 260 GL_OSET_INLINE bool
 261 gl_oset_search (gl_oset_t set, const void *elt)
 262 {
 263   return ((const struct gl_oset_impl_base *) set)->vtable->search (set, elt);
 264 }
 265
 266 GL_OSET_INLINE bool
 267 gl_oset_search_atleast (gl_oset_t set,
 268                         gl_setelement_threshold_fn threshold_fn,
 269                         const void *threshold, const void **eltp)
 270 {
 271   return ((const struct gl_oset_impl_base *) set)->vtable
 272          ->search_atleast (set, threshold_fn, threshold, eltp);
 273 }
 274
 275 GL_OSET_INLINE _GL_ATTRIBUTE_NODISCARD int
 276 gl_oset_nx_add (gl_oset_t set, const void *elt)
 277 {
 278   return ((const struct gl_oset_impl_base *) set)->vtable->nx_add (set, elt);
 279 }
 280
 281 GL_OSET_INLINE bool
 282 gl_oset_remove (gl_oset_t set, const void *elt)
 283 {
 284   return ((const struct gl_oset_impl_base *) set)->vtable
 285          ->remove_elt (set, elt);
 286 }
 287
 288 GL_OSET_INLINE int
 289 gl_oset_update (gl_oset_t set, const void *elt,
 290                 void (*action) (const void * /*elt*/, void * /*action_data*/),
 291                 void *action_data)
 292 {
 293   return ((const struct gl_oset_impl_base *) set)->vtable
 294          ->update (set, elt, action, action_data);
 295 }
 296
 297 GL_OSET_INLINE void
 298 gl_oset_free (gl_oset_t set)
 299 {
 300   ((const struct gl_oset_impl_base *) set)->vtable->oset_free (set);
 301 }
 302
 303 GL_OSET_INLINE gl_oset_iterator_t
 304 gl_oset_iterator (gl_oset_t set)
 305 {
 306   return ((const struct gl_oset_impl_base *) set)->vtable->iterator (set);
 307 }
 308
 309 GL_OSET_INLINE gl_oset_iterator_t
 310 gl_oset_iterator_atleast (gl_oset_t set,
 311                           gl_setelement_threshold_fn threshold_fn,
 312                           const void *threshold)
 313 {
 314   return ((const struct gl_oset_impl_base *) set)->vtable
 315          ->iterator_atleast (set, threshold_fn, threshold);
 316 }
 317
 318 GL_OSET_INLINE bool
 319 gl_oset_iterator_next (gl_oset_iterator_t *iterator, const void **eltp)
 320 {
 321   return iterator->vtable->iterator_next (iterator, eltp);
 322 }
 323
 324 GL_OSET_INLINE void
 325 gl_oset_iterator_free (gl_oset_iterator_t *iterator)
 326 {
 327   iterator->vtable->iterator_free (iterator);
 328 }
 329
 330 #ifdef __cplusplus
 331 }
 332 #endif
 333
 334 _GL_INLINE_HEADER_END
 335
 336 #endif /* _GL_OSET_H */