root/maint/gnulib/lib/gl_set.h

/* [previous][next][first][last][top][bottom][index][help] */

INCLUDED FROM


DEFINITIONS

This source file includes following definitions.
  1. gl_set_create_empty
  2. gl_set_nx_create_empty
  3. gl_set_size
  4. gl_set_search
  5. gl_set_nx_add
  6. gl_set_remove
  7. gl_set_free
  8. gl_set_iterator
  9. gl_set_iterator_next
  10. gl_set_iterator_free

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

/* [previous][next][first][last][top][bottom][index][help] */