lib/gl_oset.h

   1 /* Abstract ordered set data type.
   2    Copyright (C) 2006-2007, 2009-2019 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_search            O(log n) O(log n)
  69    gl_oset_search_atleast    O(log n) O(log n)
  70    gl_oset_iterator            O(1)   O(log n)
  71    gl_oset_iterator_next       O(1)   O(log n)
  72  */
  73
  74 /* -------------------------- gl_oset_t Data Type -------------------------- */
  75
  76 /* Type of function used to compare two elements.  Same as for qsort().
  77    NULL denotes pointer comparison.  */
  78 typedef int (*gl_setelement_compar_fn) (const void *elt1, const void *elt2);
  79
  80 #ifndef _GL_SETELEMENT_DISPOSE_FN_DEFINED
  81 /* Type of function used to dispose an element once it's removed from a set.
  82    NULL denotes a no-op.  */
  83 typedef void (*gl_setelement_dispose_fn) (const void *elt);
  84 # define _GL_SETELEMENT_DISPOSE_FN_DEFINED 1
  85 #endif
  86
  87 /* Type of function used to compare an element with a threshold.
  88    Return true if the element is greater or equal than the threshold.  */
  89 typedef bool (*gl_setelement_threshold_fn) (const void *elt, const void *threshold);
  90
  91 struct gl_oset_impl;
  92 /* Type representing an entire ordered set.  */
  93 typedef struct gl_oset_impl * gl_oset_t;
  94
  95 struct gl_oset_implementation;
  96 /* Type representing a ordered set datatype implementation.  */
  97 typedef const struct gl_oset_implementation * gl_oset_implementation_t;
  98
  99 #if 0 /* Unless otherwise specified, these are defined inline below.  */
 100
 101 /* Create an empty set.
 102    IMPLEMENTATION is one of GL_ARRAY_OSET, GL_AVLTREE_OSET, GL_RBTREE_OSET.
 103    COMPAR_FN is an element comparison function or NULL.
 104    DISPOSE_FN is an element disposal function or NULL.  */
 105 /* declared in gl_xoset.h */
 106 extern gl_oset_t gl_oset_create_empty (gl_oset_implementation_t implementation,
 107                                        gl_setelement_compar_fn compar_fn,
 108                                        gl_setelement_dispose_fn dispose_fn);
 109 /* Likewise.  Return NULL upon out-of-memory.  */
 110 extern gl_oset_t gl_oset_nx_create_empty (gl_oset_implementation_t implementation,
 111                                           gl_setelement_compar_fn compar_fn,
 112                                           gl_setelement_dispose_fn dispose_fn);
 113
 114 /* Return the current number of elements in an ordered set.  */
 115 extern size_t gl_oset_size (gl_oset_t set);
 116
 117 /* Search whether an element is already in the ordered set.
 118    Return true if found, or false if not present in the set.  */
 119 extern bool gl_oset_search (gl_oset_t set, const void *elt);
 120
 121 /* Search the least element in the ordered set that compares greater or equal
 122    to the given THRESHOLD.  The representation of the THRESHOLD is defined
 123    by the THRESHOLD_FN.
 124    Return true and store the found element in *ELTP if found, otherwise return
 125    false.  */
 126 extern bool gl_oset_search_atleast (gl_oset_t set,
 127                                     gl_setelement_threshold_fn threshold_fn,
 128                                     const void *threshold,
 129                                     const void **eltp);
 130
 131 /* Add an element to an ordered set.
 132    Return true if it was not already in the set and added, false otherwise.  */
 133 /* declared in gl_xoset.h */
 134 extern bool gl_oset_add (gl_oset_t set, const void *elt);
 135 /* Likewise.  Return -1 upon out-of-memory.  */
 136 extern int gl_oset_nx_add (gl_oset_t set, const void *elt)
 137 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
 138   __attribute__ ((__warn_unused_result__))
 139 #endif
 140   ;
 141
 142 /* Remove an element from an ordered set.
 143    Return true if it was found and removed.  */
 144 extern bool gl_oset_remove (gl_oset_t set, const void *elt);
 145
 146 /* Free an entire ordered set.
 147    (But this call does not free the elements of the set.  It only invokes
 148    the DISPOSE_FN on each of the elements of the set.)  */
 149 extern void gl_oset_free (gl_oset_t set);
 150
 151 #endif /* End of inline and gl_xoset.h-defined functions.  */
 152
 153 /* --------------------- gl_oset_iterator_t Data Type --------------------- */
 154
 155 /* Functions for iterating through an ordered set.  */
 156
 157 /* Type of an iterator that traverses an ordered set.
 158    This is a fixed-size struct, so that creation of an iterator doesn't need
 159    memory allocation on the heap.  */
 160 typedef struct
 161 {
 162   /* For fast dispatch of gl_oset_iterator_next.  */
 163   const struct gl_oset_implementation *vtable;
 164   /* For detecting whether the last returned element was removed.  */
 165   gl_oset_t set;
 166   size_t count;
 167   /* Other, implementation-private fields.  */
 168   void *p; void *q;
 169   size_t i; size_t j;
 170 } gl_oset_iterator_t;
 171
 172 #if 0 /* These are defined inline below.  */
 173
 174 /* Create an iterator traversing an ordered set.
 175    The set's contents must not be modified while the iterator is in use,
 176    except for removing the last returned element.  */
 177 extern gl_oset_iterator_t gl_oset_iterator (gl_oset_t set);
 178
 179 /* If there is a next element, store the next element in *ELTP, advance the
 180    iterator and return true.  Otherwise, return false.  */
 181 extern bool gl_oset_iterator_next (gl_oset_iterator_t *iterator,
 182                                    const void **eltp);
 183
 184 /* Free an iterator.  */
 185 extern void gl_oset_iterator_free (gl_oset_iterator_t *iterator);
 186
 187 #endif /* End of inline functions.  */
 188
 189 /* ------------------------ Implementation Details ------------------------ */
 190
 191 struct gl_oset_implementation
 192 {
 193   /* gl_oset_t functions.  */
 194   gl_oset_t (*nx_create_empty) (gl_oset_implementation_t implementation,
 195                                 gl_setelement_compar_fn compar_fn,
 196                                 gl_setelement_dispose_fn dispose_fn);
 197   size_t (*size) (gl_oset_t set);
 198   bool (*search) (gl_oset_t set, const void *elt);
 199   bool (*search_atleast) (gl_oset_t set,
 200                           gl_setelement_threshold_fn threshold_fn,
 201                           const void *threshold, const void **eltp);
 202   int (*nx_add) (gl_oset_t set, const void *elt);
 203   bool (*remove_elt) (gl_oset_t set, const void *elt);
 204   void (*oset_free) (gl_oset_t set);
 205   /* gl_oset_iterator_t functions.  */
 206   gl_oset_iterator_t (*iterator) (gl_oset_t set);
 207   bool (*iterator_next) (gl_oset_iterator_t *iterator, const void **eltp);
 208   void (*iterator_free) (gl_oset_iterator_t *iterator);
 209 };
 210
 211 struct gl_oset_impl_base
 212 {
 213   const struct gl_oset_implementation *vtable;
 214   gl_setelement_compar_fn compar_fn;
 215   gl_setelement_dispose_fn dispose_fn;
 216 };
 217
 218 /* Define all functions of this file as accesses to the
 219    struct gl_oset_implementation.  */
 220
 221 GL_OSET_INLINE gl_oset_t
 222 gl_oset_nx_create_empty (gl_oset_implementation_t implementation,
 223                          gl_setelement_compar_fn compar_fn,
 224                          gl_setelement_dispose_fn dispose_fn)
 225 {
 226   return implementation->nx_create_empty (implementation, compar_fn,
 227                                           dispose_fn);
 228 }
 229
 230 GL_OSET_INLINE size_t
 231 gl_oset_size (gl_oset_t set)
 232 {
 233   return ((const struct gl_oset_impl_base *) set)->vtable->size (set);
 234 }
 235
 236 GL_OSET_INLINE bool
 237 gl_oset_search (gl_oset_t set, const void *elt)
 238 {
 239   return ((const struct gl_oset_impl_base *) set)->vtable->search (set, elt);
 240 }
 241
 242 GL_OSET_INLINE bool
 243 gl_oset_search_atleast (gl_oset_t set,
 244                         gl_setelement_threshold_fn threshold_fn,
 245                         const void *threshold, const void **eltp)
 246 {
 247   return ((const struct gl_oset_impl_base *) set)->vtable
 248          ->search_atleast (set, threshold_fn, threshold, eltp);
 249 }
 250
 251 GL_OSET_INLINE int
 252 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
 253   __attribute__ ((__warn_unused_result__))
 254 #endif
 255 gl_oset_nx_add (gl_oset_t set, const void *elt)
 256 {
 257   return ((const struct gl_oset_impl_base *) set)->vtable->nx_add (set, elt);
 258 }
 259
 260 GL_OSET_INLINE bool
 261 gl_oset_remove (gl_oset_t set, const void *elt)
 262 {
 263   return ((const struct gl_oset_impl_base *) set)->vtable
 264          ->remove_elt (set, elt);
 265 }
 266
 267 GL_OSET_INLINE void
 268 gl_oset_free (gl_oset_t set)
 269 {
 270   ((const struct gl_oset_impl_base *) set)->vtable->oset_free (set);
 271 }
 272
 273 GL_OSET_INLINE gl_oset_iterator_t
 274 gl_oset_iterator (gl_oset_t set)
 275 {
 276   return ((const struct gl_oset_impl_base *) set)->vtable->iterator (set);
 277 }
 278
 279 GL_OSET_INLINE bool
 280 gl_oset_iterator_next (gl_oset_iterator_t *iterator, const void **eltp)
 281 {
 282   return iterator->vtable->iterator_next (iterator, eltp);
 283 }
 284
 285 GL_OSET_INLINE void
 286 gl_oset_iterator_free (gl_oset_iterator_t *iterator)
 287 {
 288   iterator->vtable->iterator_free (iterator);
 289 }
 290
 291 #ifdef __cplusplus
 292 }
 293 #endif
 294
 295 _GL_INLINE_HEADER_END
 296
 297 #endif /* _GL_OSET_H */