lib/gl_oset.h

   1 /* Abstract ordered set data type.
   2    Copyright (C) 2006-2007, 2009-2010 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 #if 0 /* declared in gl_xoset.h */
  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 #endif
  97 /* Likewise.  Return NULL upon out-of-memory.  */
  98 extern gl_oset_t gl_oset_nx_create_empty (gl_oset_implementation_t implementation,
  99                                           gl_setelement_compar_fn compar_fn,
 100                                           gl_setelement_dispose_fn dispose_fn);
 101
 102 /* Return the current number of elements in an ordered set.  */
 103 extern size_t gl_oset_size (gl_oset_t set);
 104
 105 /* Search whether an element is already in the ordered set.
 106    Return true if found, or false if not present in the set.  */
 107 extern bool gl_oset_search (gl_oset_t set, const void *elt);
 108
 109 /* Search the least element in the ordered set that compares greater or equal
 110    to the given THRESHOLD.  The representation of the THRESHOLD is defined
 111    by the THRESHOLD_FN.
 112    Return true and store the found element in *ELTP if found, otherwise return
 113    false.  */
 114 extern bool gl_oset_search_atleast (gl_oset_t set,
 115                                     gl_setelement_threshold_fn threshold_fn,
 116                                     const void *threshold,
 117                                     const void **eltp);
 118
 119 /* Add an element to an ordered set.
 120    Return true if it was not already in the set and added, false otherwise.  */
 121 #if 0 /* declared in gl_xoset.h */
 122 extern bool gl_oset_add (gl_oset_t set, const void *elt);
 123 #endif
 124 /* Likewise.  Return -1 upon out-of-memory.  */
 125 extern int gl_oset_nx_add (gl_oset_t set, const void *elt)
 126 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
 127   __attribute__ ((__warn_unused_result__))
 128 #endif
 129   ;
 130
 131 /* Remove an element from an ordered set.
 132    Return true if it was found and removed.  */
 133 extern bool gl_oset_remove (gl_oset_t set, const void *elt);
 134
 135 /* Free an entire ordered set.
 136    (But this call does not free the elements of the set.)  */
 137 extern void gl_oset_free (gl_oset_t set);
 138
 139 /* --------------------- gl_oset_iterator_t Data Type --------------------- */
 140
 141 /* Functions for iterating through an ordered set.  */
 142
 143 /* Type of an iterator that traverses an ordered set.
 144    This is a fixed-size struct, so that creation of an iterator doesn't need
 145    memory allocation on the heap.  */
 146 typedef struct
 147 {
 148   /* For fast dispatch of gl_oset_iterator_next.  */
 149   const struct gl_oset_implementation *vtable;
 150   /* For detecting whether the last returned element was removed.  */
 151   gl_oset_t set;
 152   size_t count;
 153   /* Other, implementation-private fields.  */
 154   void *p; void *q;
 155   size_t i; size_t j;
 156 } gl_oset_iterator_t;
 157
 158 /* Create an iterator traversing an ordered set.
 159    The set's contents must not be modified while the iterator is in use,
 160    except for removing the last returned element.  */
 161 extern gl_oset_iterator_t gl_oset_iterator (gl_oset_t set);
 162
 163 /* If there is a next element, store the next element in *ELTP, advance the
 164    iterator and return true.  Otherwise, return false.  */
 165 extern bool gl_oset_iterator_next (gl_oset_iterator_t *iterator,
 166                                    const void **eltp);
 167
 168 /* Free an iterator.  */
 169 extern void gl_oset_iterator_free (gl_oset_iterator_t *iterator);
 170
 171 /* ------------------------ Implementation Details ------------------------ */
 172
 173 struct gl_oset_implementation
 174 {
 175   /* gl_oset_t functions.  */
 176   gl_oset_t (*nx_create_empty) (gl_oset_implementation_t implementation,
 177                                 gl_setelement_compar_fn compar_fn,
 178                                 gl_setelement_dispose_fn dispose_fn);
 179   size_t (*size) (gl_oset_t set);
 180   bool (*search) (gl_oset_t set, const void *elt);
 181   bool (*search_atleast) (gl_oset_t set,
 182                           gl_setelement_threshold_fn threshold_fn,
 183                           const void *threshold, const void **eltp);
 184   int (*nx_add) (gl_oset_t set, const void *elt);
 185   bool (*remove_elt) (gl_oset_t set, const void *elt);
 186   void (*oset_free) (gl_oset_t set);
 187   /* gl_oset_iterator_t functions.  */
 188   gl_oset_iterator_t (*iterator) (gl_oset_t set);
 189   bool (*iterator_next) (gl_oset_iterator_t *iterator, const void **eltp);
 190   void (*iterator_free) (gl_oset_iterator_t *iterator);
 191 };
 192
 193 struct gl_oset_impl_base
 194 {
 195   const struct gl_oset_implementation *vtable;
 196   gl_setelement_compar_fn compar_fn;
 197   gl_setelement_dispose_fn dispose_fn;
 198 };
 199
 200 #if HAVE_INLINE
 201
 202 /* Define all functions of this file as inline accesses to the
 203    struct gl_oset_implementation.
 204    Use #define to avoid a warning because of extern vs. static.  */
 205
 206 # define gl_oset_nx_create_empty gl_oset_nx_create_empty_inline
 207 static inline gl_oset_t
 208 gl_oset_nx_create_empty (gl_oset_implementation_t implementation,
 209                          gl_setelement_compar_fn compar_fn,
 210                          gl_setelement_dispose_fn dispose_fn)
 211 {
 212   return implementation->nx_create_empty (implementation, compar_fn,
 213                                           dispose_fn);
 214 }
 215
 216 # define gl_oset_size gl_oset_size_inline
 217 static inline size_t
 218 gl_oset_size (gl_oset_t set)
 219 {
 220   return ((const struct gl_oset_impl_base *) set)->vtable->size (set);
 221 }
 222
 223 # define gl_oset_search gl_oset_search_inline
 224 static inline bool
 225 gl_oset_search (gl_oset_t set, const void *elt)
 226 {
 227   return ((const struct gl_oset_impl_base *) set)->vtable->search (set, elt);
 228 }
 229
 230 # define gl_oset_search_atleast gl_oset_search_atleast_inline
 231 static inline bool
 232 gl_oset_search_atleast (gl_oset_t set,
 233                         gl_setelement_threshold_fn threshold_fn,
 234                         const void *threshold, const void **eltp)
 235 {
 236   return ((const struct gl_oset_impl_base *) set)->vtable
 237          ->search_atleast (set, threshold_fn, threshold, eltp);
 238 }
 239
 240 # define gl_oset_nx_add gl_oset_nx_add_inline
 241 static inline int
 242 gl_oset_nx_add (gl_oset_t set, const void *elt)
 243 {
 244   return ((const struct gl_oset_impl_base *) set)->vtable->nx_add (set, elt);
 245 }
 246
 247 # define gl_oset_remove gl_oset_remove_inline
 248 static inline bool
 249 gl_oset_remove (gl_oset_t set, const void *elt)
 250 {
 251   return ((const struct gl_oset_impl_base *) set)->vtable
 252          ->remove_elt (set, elt);
 253 }
 254
 255 # define gl_oset_free gl_oset_free_inline
 256 static inline void
 257 gl_oset_free (gl_oset_t set)
 258 {
 259   ((const struct gl_oset_impl_base *) set)->vtable->oset_free (set);
 260 }
 261
 262 # define gl_oset_iterator gl_oset_iterator_inline
 263 static inline gl_oset_iterator_t
 264 gl_oset_iterator (gl_oset_t set)
 265 {
 266   return ((const struct gl_oset_impl_base *) set)->vtable->iterator (set);
 267 }
 268
 269 # define gl_oset_iterator_next gl_oset_iterator_next_inline
 270 static inline bool
 271 gl_oset_iterator_next (gl_oset_iterator_t *iterator, const void **eltp)
 272 {
 273   return iterator->vtable->iterator_next (iterator, eltp);
 274 }
 275
 276 # define gl_oset_iterator_free gl_oset_iterator_free_inline
 277 static inline void
 278 gl_oset_iterator_free (gl_oset_iterator_t *iterator)
 279 {
 280   iterator->vtable->iterator_free (iterator);
 281 }
 282
 283 #endif
 284
 285 #ifdef __cplusplus
 286 }
 287 #endif
 288
 289 #endif /* _GL_OSET_H */