lib/gl_set.h

   1 /* Abstract set data type.
   2    Copyright (C) 2006-2007, 2009-2024 Free Software Foundation, Inc.
   3    Written by Bruno Haible <bruno@clisp.org>, 2018.
   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 <https://www.gnu.org/licenses/>.  */
  17
  18 #ifndef _GL_SET_H
  19 #define _GL_SET_H
  20
  21 /* This file uses _GL_INLINE_HEADER_BEGIN, _GL_INLINE,
  22    _GL_ATTRIBUTE_NODISCARD.  */
  23 #if !_GL_CONFIG_H_INCLUDED
  24  #error "Please include config.h first."
  25 #endif
  26
  27 #include <stddef.h>
  28
  29 _GL_INLINE_HEADER_BEGIN
  30 #ifndef GL_SET_INLINE
  31 # define GL_SET_INLINE _GL_INLINE
  32 #endif
  33
  34 #ifdef __cplusplus
  35 extern "C" {
  36 #endif
  37
  38
  39 /* gl_set is an abstract set data type.  It can contain any number of objects
  40    ('void *' or 'const void *' pointers); the order does not matter.
  41    Duplicates (in the sense of the comparator) are forbidden.
  42
  43    There are several implementations of this set datatype, optimized for
  44    different operations or for memory.  You can start using the simplest set
  45    implementation, GL_ARRAY_SET, and switch to a different implementation
  46    later, when you realize which operations are performed the most frequently.
  47    The API of the different implementations is exactly the same; when switching
  48    to a different implementation, you only have to change the gl_set_create
  49    call.
  50
  51    The implementations are:
  52      GL_ARRAY_SET         a growable array
  53      GL_LINKEDHASH_SET    a hash table with a linked list
  54      GL_HASH_SET          a hash table
  55
  56    The memory consumption is asymptotically the same: O(1) for every object
  57    in the set.  When looking more closely at the average memory consumed
  58    for an object, GL_ARRAY_SET is the most compact representation, then comes
  59    GL_HASH_SET, and GL_LINKEDHASH_SET needs the most memory.
  60
  61    The guaranteed average performance of the operations is, for a set of
  62    n elements:
  63
  64    Operation                  ARRAY   LINKEDHASH
  65                                       HASH
  66
  67    gl_set_size                 O(1)   O(1)
  68    gl_set_add                  O(n)   O(1)
  69    gl_set_remove               O(n)   O(1)
  70    gl_set_search               O(n)   O(1)
  71    gl_set_iterator             O(1)   O(1)
  72    gl_set_iterator_next        O(1)   O(1)
  73  */
  74
  75 /* --------------------------- gl_set_t Data Type --------------------------- */
  76
  77 /* Type of function used to compare two elements.
  78    NULL denotes pointer comparison.  */
  79 typedef bool (*gl_setelement_equals_fn) (const void *elt1, const void *elt2);
  80
  81 /* Type of function used to compute a hash code.
  82    NULL denotes a function that depends only on the pointer itself.  */
  83 typedef size_t (*gl_setelement_hashcode_fn) (const void *elt);
  84
  85 #ifndef _GL_SETELEMENT_DISPOSE_FN_DEFINED
  86 /* Type of function used to dispose an element once it's removed from a set.
  87    NULL denotes a no-op.  */
  88 typedef void (*gl_setelement_dispose_fn) (const void *elt);
  89 # define _GL_SETELEMENT_DISPOSE_FN_DEFINED 1
  90 #endif
  91
  92 struct gl_set_impl;
  93 /* Type representing an entire set.  */
  94 typedef struct gl_set_impl * gl_set_t;
  95
  96 struct gl_set_implementation;
  97 /* Type representing a set datatype implementation.  */
  98 typedef const struct gl_set_implementation * gl_set_implementation_t;
  99
 100 #if 0 /* Unless otherwise specified, these are defined inline below.  */
 101
 102 /* Creates an empty set.
 103    IMPLEMENTATION is one of GL_ARRAY_SET, GL_LINKEDHASH_SET, GL_HASH_SET.
 104    EQUALS_FN is an element comparison function or NULL.
 105    HASHCODE_FN is an element hash code function or NULL.
 106    DISPOSE_FN is an element disposal function or NULL.  */
 107 /* declared in gl_xset.h */
 108 extern gl_set_t gl_set_create_empty (gl_set_implementation_t implementation,
 109                                      gl_setelement_equals_fn equals_fn,
 110                                      gl_setelement_hashcode_fn hashcode_fn,
 111                                      gl_setelement_dispose_fn dispose_fn)
 112   /*_GL_ATTRIBUTE_DEALLOC (gl_set_free, 1)*/
 113   _GL_ATTRIBUTE_RETURNS_NONNULL;
 114 /* Likewise.  Returns NULL upon out-of-memory.  */
 115 extern gl_set_t gl_set_nx_create_empty (gl_set_implementation_t implementation,
 116                                         gl_setelement_equals_fn equals_fn,
 117                                         gl_setelement_hashcode_fn hashcode_fn,
 118                                         gl_setelement_dispose_fn dispose_fn)
 119   /*_GL_ATTRIBUTE_DEALLOC (gl_set_free, 1)*/;
 120
 121 /* Returns the current number of elements in a set.  */
 122 extern size_t gl_set_size (gl_set_t set);
 123
 124 /* Searches whether an element is already in the set.
 125    Returns true if found, or false if not present in the set.  */
 126 extern bool gl_set_search (gl_set_t set, const void *elt);
 127
 128 /* Adds an element to a set.
 129    Returns true if it was not already in the set and added, false otherwise.  */
 130 /* declared in gl_xset.h */
 131 extern bool gl_set_add (gl_set_t set, const void *elt);
 132
 133 /* Likewise.  Returns -1 upon out-of-memory.  */
 134 _GL_ATTRIBUTE_NODISCARD
 135 extern int gl_set_nx_add (gl_set_t set, const void *elt);
 136
 137 /* Removes an element from a set.
 138    Returns true if it was found and removed.  */
 139 extern bool gl_set_remove (gl_set_t set, const void *elt);
 140
 141 /* Frees an entire set.
 142    (But this call does not free the elements of the set.  It only invokes
 143    the DISPOSE_FN on each of the elements of the set.)  */
 144 extern void gl_set_free (gl_set_t set);
 145
 146 #endif /* End of inline and gl_xset.h-defined functions.  */
 147
 148 /* ---------------------- gl_set_iterator_t Data Type ---------------------- */
 149
 150 /* Functions for iterating through a set.
 151    Note: Iterating through a set of type GL_HASH_SET returns the elements in an
 152    unpredictable order.  If you need a predictable order, use GL_LINKEDHASH_SET
 153    instead of GL_HASH_SET.  */
 154
 155 /* Type of an iterator that traverses a set.
 156    This is a fixed-size struct, so that creation of an iterator doesn't need
 157    memory allocation on the heap.  */
 158 typedef struct
 159 {
 160   /* For fast dispatch of gl_set_iterator_next.  */
 161   const struct gl_set_implementation *vtable;
 162   /* For detecting whether the last returned element was removed.  */
 163   gl_set_t set;
 164   size_t count;
 165   /* Other, implementation-private fields.  */
 166   void *p; void *q;
 167   size_t i; size_t j;
 168 } gl_set_iterator_t;
 169
 170 #if 0 /* These are defined inline below.  */
 171
 172 /* Creates an iterator traversing a set.
 173    The set's contents must not be modified while the iterator is in use,
 174    except for removing the last returned element.  */
 175 extern gl_set_iterator_t gl_set_iterator (gl_set_t set);
 176
 177 /* If there is a next element, stores the next element in *ELTP, advances the
 178    iterator and returns true.  Otherwise, returns false.  */
 179 extern bool gl_set_iterator_next (gl_set_iterator_t *iterator,
 180                                   const void **eltp);
 181
 182 /* Frees an iterator.  */
 183 extern void gl_set_iterator_free (gl_set_iterator_t *iterator);
 184
 185 #endif /* End of inline functions.  */
 186
 187 /* ------------------------ Implementation Details ------------------------ */
 188
 189 struct gl_set_implementation
 190 {
 191   /* gl_set_t functions.  */
 192   gl_set_t (*nx_create_empty) (gl_set_implementation_t implementation,
 193                                gl_setelement_equals_fn equals_fn,
 194                                gl_setelement_hashcode_fn hashcode_fn,
 195                                gl_setelement_dispose_fn dispose_fn);
 196   size_t (*size) (gl_set_t set);
 197   bool (*search) (gl_set_t set, const void *elt);
 198   int (*nx_add) (gl_set_t set, const void *elt);
 199   bool (*remove_elt) (gl_set_t set, const void *elt);
 200   void (*set_free) (gl_set_t set);
 201   /* gl_set_iterator_t functions.  */
 202   gl_set_iterator_t (*iterator) (gl_set_t set);
 203   bool (*iterator_next) (gl_set_iterator_t *iterator, const void **eltp);
 204   void (*iterator_free) (gl_set_iterator_t *iterator);
 205 };
 206
 207 struct gl_set_impl_base
 208 {
 209   const struct gl_set_implementation *vtable;
 210   gl_setelement_equals_fn equals_fn;
 211   gl_setelement_dispose_fn dispose_fn;
 212 };
 213
 214 /* Define all functions of this file as accesses to the
 215    struct gl_set_implementation.  */
 216
 217 GL_SET_INLINE
 218 /*_GL_ATTRIBUTE_DEALLOC (gl_set_free, 1)*/
 219 gl_set_t
 220 gl_set_nx_create_empty (gl_set_implementation_t implementation,
 221                         gl_setelement_equals_fn equals_fn,
 222                         gl_setelement_hashcode_fn hashcode_fn,
 223                         gl_setelement_dispose_fn dispose_fn)
 224 {
 225   return implementation->nx_create_empty (implementation, equals_fn,
 226                                           hashcode_fn, dispose_fn);
 227 }
 228
 229 GL_SET_INLINE size_t
 230 gl_set_size (gl_set_t set)
 231 {
 232   return ((const struct gl_set_impl_base *) set)->vtable->size (set);
 233 }
 234
 235 GL_SET_INLINE bool
 236 gl_set_search (gl_set_t set, const void *elt)
 237 {
 238   return ((const struct gl_set_impl_base *) set)->vtable->search (set, elt);
 239 }
 240
 241 _GL_ATTRIBUTE_NODISCARD GL_SET_INLINE int
 242 gl_set_nx_add (gl_set_t set, const void *elt)
 243 {
 244   return ((const struct gl_set_impl_base *) set)->vtable->nx_add (set, elt);
 245 }
 246
 247 GL_SET_INLINE bool
 248 gl_set_remove (gl_set_t set, const void *elt)
 249 {
 250   return ((const struct gl_set_impl_base *) set)->vtable->remove_elt (set, elt);
 251 }
 252
 253 GL_SET_INLINE void
 254 gl_set_free (gl_set_t set)
 255 {
 256   ((const struct gl_set_impl_base *) set)->vtable->set_free (set);
 257 }
 258
 259 GL_SET_INLINE gl_set_iterator_t
 260 gl_set_iterator (gl_set_t set)
 261 {
 262   return ((const struct gl_set_impl_base *) set)->vtable->iterator (set);
 263 }
 264
 265 GL_SET_INLINE bool
 266 gl_set_iterator_next (gl_set_iterator_t *iterator, const void **eltp)
 267 {
 268   return iterator->vtable->iterator_next (iterator, eltp);
 269 }
 270
 271 GL_SET_INLINE void
 272 gl_set_iterator_free (gl_set_iterator_t *iterator)
 273 {
 274   iterator->vtable->iterator_free (iterator);
 275 }
 276
 277 #ifdef __cplusplus
 278 }
 279 #endif
 280
 281 _GL_INLINE_HEADER_END
 282
 283 #endif /* _GL_SET_H */