lib/gl_oset.h

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