lib/gl_oset.h

   1 /* Abstract ordered set data type.
   2    Copyright (C) 2006-2007, 2009 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 <http://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 #ifdef __cplusplus
  25 extern "C" {
  26 #endif
  27
  28
  29 /* gl_oset is an abstract ordered set data type.  It can contain any number
  30    of objects ('void *' or 'const void *' pointers) in the order of a given
  31    comparator function.  Duplicates (in the sense of the comparator) are
  32    forbidden.
  33
  34    There are several implementations of this ordered set datatype, optimized
  35    for different operations or for memory.  You can start using the simplest
  36    ordered set implementation, GL_ARRAY_OSET, and switch to a different
  37    implementation later, when you realize which operations are performed
  38    the most frequently.  The API of the different implementations is exactly
  39    the same; when switching to a different implementation, you only have to
  40    change the gl_oset_create call.
  41
  42    The implementations are:
  43      GL_ARRAY_OSET        a growable array
  44      GL_AVLTREE_OSET      a binary tree (AVL tree)
  45      GL_RBTREE_OSET       a binary tree (red-black tree)
  46
  47    The memory consumption is asymptotically the same: O(1) for every object
  48    in the set.  When looking more closely at the average memory consumed
  49    for an object, GL_ARRAY_OSET is the most compact representation, and
  50    GL_AVLTREE_OSET, GL_RBTREE_OSET need more memory.
  51
  52    The guaranteed average performance of the operations is, for a set of
  53    n elements:
  54
  55    Operation                  ARRAY     TREE
  56
  57    gl_oset_size                O(1)     O(1)
  58    gl_oset_add                 O(n)   O(log n)
  59    gl_oset_remove              O(n)   O(log n)
  60    gl_oset_search            O(log n) O(log n)
  61    gl_oset_search_atleast    O(log n) O(log n)
  62    gl_oset_iterator            O(1)   O(log n)
  63    gl_oset_iterator_next       O(1)   O(log n)
  64  */
  65
  66 /* -------------------------- gl_oset_t Data Type -------------------------- */
  67
  68 /* Type of function used to compare two elements.  Same as for qsort().
  69    NULL denotes pointer comparison.  */
  70 typedef int (*gl_setelement_compar_fn) (const void *elt1, const void *elt2);
  71
  72 /* Type of function used to dispose an element once it's removed from a set.
  73    NULL denotes a no-op.  */
  74 typedef void (*gl_setelement_dispose_fn) (const void *elt);
  75
  76 /* Type of function used to compare an element with a threshold.
  77    Return true if the element is greater or equal than the threshold.  */
  78 typedef bool (*gl_setelement_threshold_fn) (const void *elt, const void *threshold);
  79
  80 struct gl_oset_impl;
  81 /* Type representing an entire ordered set.  */
  82 typedef struct gl_oset_impl * gl_oset_t;
  83
  84 struct gl_oset_implementation;
  85 /* Type representing a ordered set datatype implementation.  */
  86 typedef const struct gl_oset_implementation * gl_oset_implementation_t;
  87
  88 /* Create an empty set.
  89    IMPLEMENTATION is one of GL_ARRAY_OSET, GL_AVLTREE_OSET, GL_RBTREE_OSET.
  90    COMPAR_FN is an element comparison function or NULL.
  91    DISPOSE_FN is an element disposal function or NULL.  */
  92 extern gl_oset_t gl_oset_create_empty (gl_oset_implementation_t implementation,
  93                                        gl_setelement_compar_fn compar_fn,
  94                                        gl_setelement_dispose_fn dispose_fn);
  95
  96 /* Return the current number of elements in an ordered set.  */
  97 extern size_t gl_oset_size (gl_oset_t set);
  98
  99 /* Search whether an element is already in the ordered set.
 100    Return true if found, or false if not present in the set.  */
 101 extern bool gl_oset_search (gl_oset_t set, const void *elt);
 102
 103 /* Search the least element in the ordered set that compares greater or equal
 104    to the given THRESHOLD.  The representation of the THRESHOLD is defined
 105    by the THRESHOLD_FN.
 106    Return true and store the found element in *ELTP if found, otherwise return
 107    false.  */
 108 extern bool gl_oset_search_atleast (gl_oset_t set,
 109                                     gl_setelement_threshold_fn threshold_fn,
 110                                     const void *threshold,
 111                                     const void **eltp);
 112
 113 /* Add an element to an ordered set.
 114    Return true if it was not already in the set and added.  */
 115 extern bool gl_oset_add (gl_oset_t set, const void *elt);
 116
 117 /* Remove an element from an ordered set.
 118    Return true if it was found and removed.  */
 119 extern bool gl_oset_remove (gl_oset_t set, const void *elt);
 120
 121 /* Free an entire ordered set.
 122    (But this call does not free the elements of the set.)  */
 123 extern void gl_oset_free (gl_oset_t set);
 124
 125 /* --------------------- gl_oset_iterator_t Data Type --------------------- */
 126
 127 /* Functions for iterating through an ordered set.  */
 128
 129 /* Type of an iterator that traverses an ordered set.
 130    This is a fixed-size struct, so that creation of an iterator doesn't need
 131    memory allocation on the heap.  */
 132 typedef struct
 133 {
 134   /* For fast dispatch of gl_oset_iterator_next.  */
 135   const struct gl_oset_implementation *vtable;
 136   /* For detecting whether the last returned element was removed.  */
 137   gl_oset_t set;
 138   size_t count;
 139   /* Other, implementation-private fields.  */
 140   void *p; void *q;
 141   size_t i; size_t j;
 142 } gl_oset_iterator_t;
 143
 144 /* Create an iterator traversing an ordered set.
 145    The set's contents must not be modified while the iterator is in use,
 146    except for removing the last returned element.  */
 147 extern gl_oset_iterator_t gl_oset_iterator (gl_oset_t set);
 148
 149 /* If there is a next element, store the next element in *ELTP, advance the
 150    iterator and return true.  Otherwise, return false.  */
 151 extern bool gl_oset_iterator_next (gl_oset_iterator_t *iterator,
 152                                    const void **eltp);
 153
 154 /* Free an iterator.  */
 155 extern void gl_oset_iterator_free (gl_oset_iterator_t *iterator);
 156
 157 /* ------------------------ Implementation Details ------------------------ */
 158
 159 struct gl_oset_implementation
 160 {
 161   /* gl_oset_t functions.  */
 162   gl_oset_t (*create_empty) (gl_oset_implementation_t implementation,
 163                              gl_setelement_compar_fn compar_fn,
 164                              gl_setelement_dispose_fn dispose_fn);
 165   size_t (*size) (gl_oset_t set);
 166   bool (*search) (gl_oset_t set, const void *elt);
 167   bool (*search_atleast) (gl_oset_t set,
 168                           gl_setelement_threshold_fn threshold_fn,
 169                           const void *threshold, const void **eltp);
 170   bool (*add) (gl_oset_t set, const void *elt);
 171   bool (*remove_elt) (gl_oset_t set, const void *elt);
 172   void (*oset_free) (gl_oset_t set);
 173   /* gl_oset_iterator_t functions.  */
 174   gl_oset_iterator_t (*iterator) (gl_oset_t set);
 175   bool (*iterator_next) (gl_oset_iterator_t *iterator, const void **eltp);
 176   void (*iterator_free) (gl_oset_iterator_t *iterator);
 177 };
 178
 179 struct gl_oset_impl_base
 180 {
 181   const struct gl_oset_implementation *vtable;
 182   gl_setelement_compar_fn compar_fn;
 183   gl_setelement_dispose_fn dispose_fn;
 184 };
 185
 186 #if HAVE_INLINE
 187
 188 /* Define all functions of this file as inline accesses to the
 189    struct gl_oset_implementation.
 190    Use #define to avoid a warning because of extern vs. static.  */
 191
 192 # define gl_oset_create_empty gl_oset_create_empty_inline
 193 static inline gl_oset_t
 194 gl_oset_create_empty (gl_oset_implementation_t implementation,
 195                       gl_setelement_compar_fn compar_fn,
 196                       gl_setelement_dispose_fn dispose_fn)
 197 {
 198   return implementation->create_empty (implementation, compar_fn, dispose_fn);
 199 }
 200
 201 # define gl_oset_size gl_oset_size_inline
 202 static inline size_t
 203 gl_oset_size (gl_oset_t set)
 204 {
 205   return ((const struct gl_oset_impl_base *) set)->vtable->size (set);
 206 }
 207
 208 # define gl_oset_search gl_oset_search_inline
 209 static inline bool
 210 gl_oset_search (gl_oset_t set, const void *elt)
 211 {
 212   return ((const struct gl_oset_impl_base *) set)->vtable->search (set, elt);
 213 }
 214
 215 # define gl_oset_search_atleast gl_oset_search_atleast_inline
 216 static inline bool
 217 gl_oset_search_atleast (gl_oset_t set,
 218                         gl_setelement_threshold_fn threshold_fn,
 219                         const void *threshold, const void **eltp)
 220 {
 221   return ((const struct gl_oset_impl_base *) set)->vtable
 222          ->search_atleast (set, threshold_fn, threshold, eltp);
 223 }
 224
 225 # define gl_oset_add gl_oset_add_inline
 226 static inline bool
 227 gl_oset_add (gl_oset_t set, const void *elt)
 228 {
 229   return ((const struct gl_oset_impl_base *) set)->vtable->add (set, elt);
 230 }
 231
 232 # define gl_oset_remove gl_oset_remove_inline
 233 static inline bool
 234 gl_oset_remove (gl_oset_t set, const void *elt)
 235 {
 236   return ((const struct gl_oset_impl_base *) set)->vtable
 237          ->remove_elt (set, elt);
 238 }
 239
 240 # define gl_oset_free gl_oset_free_inline
 241 static inline void
 242 gl_oset_free (gl_oset_t set)
 243 {
 244   ((const struct gl_oset_impl_base *) set)->vtable->oset_free (set);
 245 }
 246
 247 # define gl_oset_iterator gl_oset_iterator_inline
 248 static inline gl_oset_iterator_t
 249 gl_oset_iterator (gl_oset_t set)
 250 {
 251   return ((const struct gl_oset_impl_base *) set)->vtable->iterator (set);
 252 }
 253
 254 # define gl_oset_iterator_next gl_oset_iterator_next_inline
 255 static inline bool
 256 gl_oset_iterator_next (gl_oset_iterator_t *iterator, const void **eltp)
 257 {
 258   return iterator->vtable->iterator_next (iterator, eltp);
 259 }
 260
 261 # define gl_oset_iterator_free gl_oset_iterator_free_inline
 262 static inline void
 263 gl_oset_iterator_free (gl_oset_iterator_t *iterator)
 264 {
 265   iterator->vtable->iterator_free (iterator);
 266 }
 267
 268 #endif
 269
 270 #ifdef __cplusplus
 271 }
 272 #endif
 273
 274 #endif /* _GL_OSET_H */