lib/gl_oset.h

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