lib/gl_oset.h

   1 /* Abstract ordered set data type.
   2    Copyright (C) 2006-2007 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 dispose an element once it's removed from a set.
  74    NULL denotes a no-op.  */
  75 typedef void (*gl_setelement_dispose_fn) (const void *elt);
  76
  77 /* Type of function used to compare an element with a threshold.
  78    Return true if the element is greater or equal than the threshold.  */
  79 typedef bool (*gl_setelement_threshold_fn) (const void *elt, const void *threshold);
  80
  81 struct gl_oset_impl;
  82 /* Type representing an entire ordered set.  */
  83 typedef struct gl_oset_impl * gl_oset_t;
  84
  85 struct gl_oset_implementation;
  86 /* Type representing a ordered set datatype implementation.  */
  87 typedef const struct gl_oset_implementation * gl_oset_implementation_t;
  88
  89 /* Create an empty set.
  90    IMPLEMENTATION is one of GL_ARRAY_OSET, GL_AVLTREE_OSET, GL_RBTREE_OSET.
  91    COMPAR_FN is an element comparison function or NULL.
  92    DISPOSE_FN is an element disposal function or NULL.  */
  93 extern gl_oset_t gl_oset_create_empty (gl_oset_implementation_t implementation,
  94                                        gl_setelement_compar_fn compar_fn,
  95                                        gl_setelement_dispose_fn dispose_fn);
  96
  97 /* Return the current number of elements in an ordered set.  */
  98 extern size_t gl_oset_size (gl_oset_t set);
  99
 100 /* Search whether an element is already in the ordered set.
 101    Return true if found, or false if not present in the set.  */
 102 extern bool gl_oset_search (gl_oset_t set, const void *elt);
 103
 104 /* Search the least element in the ordered set that compares greater or equal
 105    to the given THRESHOLD.  The representation of the THRESHOLD is defined
 106    by the THRESHOLD_FN.
 107    Return true and store the found element in *ELTP if found, otherwise return
 108    false.  */
 109 extern bool gl_oset_search_atleast (gl_oset_t set,
 110                                     gl_setelement_threshold_fn threshold_fn,
 111                                     const void *threshold,
 112                                     const void **eltp);
 113
 114 /* Add an element to an ordered set.
 115    Return true if it was not already in the set and added.  */
 116 extern bool gl_oset_add (gl_oset_t set, const void *elt);
 117
 118 /* Remove an element from an ordered set.
 119    Return true if it was found and removed.  */
 120 extern bool gl_oset_remove (gl_oset_t set, const void *elt);
 121
 122 /* Free an entire ordered set.
 123    (But this call does not free the elements of the set.)  */
 124 extern void gl_oset_free (gl_oset_t set);
 125
 126 /* --------------------- gl_oset_iterator_t Data Type --------------------- */
 127
 128 /* Functions for iterating through an ordered set.  */
 129
 130 /* Type of an iterator that traverses an ordered set.
 131    This is a fixed-size struct, so that creation of an iterator doesn't need
 132    memory allocation on the heap.  */
 133 typedef struct
 134 {
 135   /* For fast dispatch of gl_oset_iterator_next.  */
 136   const struct gl_oset_implementation *vtable;
 137   /* For detecting whether the last returned element was removed.  */
 138   gl_oset_t set;
 139   size_t count;
 140   /* Other, implementation-private fields.  */
 141   void *p; void *q;
 142   size_t i; size_t j;
 143 } gl_oset_iterator_t;
 144
 145 /* Create an iterator traversing an ordered set.
 146    The set's contents must not be modified while the iterator is in use,
 147    except for removing the last returned element.  */
 148 extern gl_oset_iterator_t gl_oset_iterator (gl_oset_t set);
 149
 150 /* If there is a next element, store the next element in *ELTP, advance the
 151    iterator and return true.  Otherwise, return false.  */
 152 extern bool gl_oset_iterator_next (gl_oset_iterator_t *iterator,
 153                                    const void **eltp);
 154
 155 /* Free an iterator.  */
 156 extern void gl_oset_iterator_free (gl_oset_iterator_t *iterator);
 157
 158 /* ------------------------ Implementation Details ------------------------ */
 159
 160 struct gl_oset_implementation
 161 {
 162   /* gl_oset_t functions.  */
 163   gl_oset_t (*create_empty) (gl_oset_implementation_t implementation,
 164                              gl_setelement_compar_fn compar_fn,
 165                              gl_setelement_dispose_fn dispose_fn);
 166   size_t (*size) (gl_oset_t set);
 167   bool (*search) (gl_oset_t set, const void *elt);
 168   bool (*search_atleast) (gl_oset_t set,
 169                           gl_setelement_threshold_fn threshold_fn,
 170                           const void *threshold, const void **eltp);
 171   bool (*add) (gl_oset_t set, const void *elt);
 172   bool (*remove) (gl_oset_t set, const void *elt);
 173   void (*oset_free) (gl_oset_t set);
 174   /* gl_oset_iterator_t functions.  */
 175   gl_oset_iterator_t (*iterator) (gl_oset_t set);
 176   bool (*iterator_next) (gl_oset_iterator_t *iterator, const void **eltp);
 177   void (*iterator_free) (gl_oset_iterator_t *iterator);
 178 };
 179
 180 struct gl_oset_impl_base
 181 {
 182   const struct gl_oset_implementation *vtable;
 183   gl_setelement_compar_fn compar_fn;
 184   gl_setelement_dispose_fn dispose_fn;
 185 };
 186
 187 #if HAVE_INLINE
 188
 189 /* Define all functions of this file as inline accesses to the
 190    struct gl_oset_implementation.
 191    Use #define to avoid a warning because of extern vs. static.  */
 192
 193 # define gl_oset_create_empty gl_oset_create_empty_inline
 194 static inline gl_oset_t
 195 gl_oset_create_empty (gl_oset_implementation_t implementation,
 196                       gl_setelement_compar_fn compar_fn,
 197                       gl_setelement_dispose_fn dispose_fn)
 198 {
 199   return implementation->create_empty (implementation, compar_fn, dispose_fn);
 200 }
 201
 202 # define gl_oset_size gl_oset_size_inline
 203 static inline size_t
 204 gl_oset_size (gl_oset_t set)
 205 {
 206   return ((const struct gl_oset_impl_base *) set)->vtable->size (set);
 207 }
 208
 209 # define gl_oset_search gl_oset_search_inline
 210 static inline bool
 211 gl_oset_search (gl_oset_t set, const void *elt)
 212 {
 213   return ((const struct gl_oset_impl_base *) set)->vtable->search (set, elt);
 214 }
 215
 216 # define gl_oset_search_atleast gl_oset_search_atleast_inline
 217 static inline bool
 218 gl_oset_search_atleast (gl_oset_t set,
 219                         gl_setelement_threshold_fn threshold_fn,
 220                         const void *threshold, const void **eltp)
 221 {
 222   return ((const struct gl_oset_impl_base *) set)->vtable
 223          ->search_atleast (set, threshold_fn, threshold, eltp);
 224 }
 225
 226 # define gl_oset_add gl_oset_add_inline
 227 static inline bool
 228 gl_oset_add (gl_oset_t set, const void *elt)
 229 {
 230   return ((const struct gl_oset_impl_base *) set)->vtable->add (set, elt);
 231 }
 232
 233 # define gl_oset_remove gl_oset_remove_inline
 234 static inline bool
 235 gl_oset_remove (gl_oset_t set, const void *elt)
 236 {
 237   return ((const struct gl_oset_impl_base *) set)->vtable->remove (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 */