Mercurial > gnulib
annotate lib/gl_set.h @ 40196:e63f5d3edab5
relocatable-prog: Update documentation.
* doc/relocatable-maint.texi (Supporting Relocation): Update to match
the recent changes.
| author | Bruno Haible <bruno@clisp.org> |
|---|---|
| date | Sun, 24 Feb 2019 01:49:15 +0100 |
| parents | b06060465f09 |
| children |
| rev | line source |
|---|---|
| 39991 | 1 /* Abstract set data type. |
|
40057
b06060465f09
maint: Run 'make update-copyright'
Paul Eggert <eggert@cs.ucla.edu>
parents:
39999
diff
changeset
|
2 Copyright (C) 2006-2007, 2009-2019 Free Software Foundation, Inc. |
| 39991 | 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 /* Create 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, | |
| 107 gl_setelement_equals_fn equals_fn, | |
| 108 gl_setelement_hashcode_fn hashcode_fn, | |
| 109 gl_setelement_dispose_fn dispose_fn); | |
| 110 /* Likewise. Return NULL upon out-of-memory. */ | |
| 111 extern gl_set_t gl_set_nx_create_empty (gl_set_implementation_t implementation, | |
| 112 gl_setelement_equals_fn equals_fn, | |
| 113 gl_setelement_hashcode_fn hashcode_fn, | |
| 114 gl_setelement_dispose_fn dispose_fn); | |
| 115 | |
| 116 /* Return the current number of elements in a set. */ | |
| 117 extern size_t gl_set_size (gl_set_t set); | |
| 118 | |
| 119 /* Search whether an element is already in the set. | |
| 120 Return true if found, or false if not present in the set. */ | |
| 121 extern bool gl_set_search (gl_set_t set, const void *elt); | |
| 122 | |
| 123 /* Add an element to a set. | |
| 124 Return true if it was not already in the set and added, false otherwise. */ | |
| 125 /* declared in gl_xset.h */ | |
| 126 extern bool gl_set_add (gl_set_t set, const void *elt); | |
| 127 /* Likewise. Return -1 upon out-of-memory. */ | |
| 128 extern int gl_set_nx_add (gl_set_t set, const void *elt) | |
| 129 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) | |
| 130 __attribute__ ((__warn_unused_result__)) | |
| 131 #endif | |
| 132 ; | |
| 133 | |
| 134 /* Remove an element from a set. | |
| 135 Return true if it was found and removed. */ | |
| 136 extern bool gl_set_remove (gl_set_t set, const void *elt); | |
| 137 | |
| 138 /* Free an entire set. | |
| 39999 | 139 (But this call does not free the elements of the set. It only invokes |
| 140 the DISPOSE_FN on each of the elements of the set.) */ | |
| 39991 | 141 extern void gl_set_free (gl_set_t set); |
| 142 | |
| 143 #endif /* End of inline and gl_xset.h-defined functions. */ | |
| 144 | |
| 145 /* ---------------------- gl_set_iterator_t Data Type ---------------------- */ | |
| 146 | |
| 147 /* Functions for iterating through a set. | |
| 148 Note: Iterating through a set of type GL_HASH_SET returns the elements in an | |
| 149 unpredictable order. If you need a predictable order, use GL_LINKEDHASH_SET | |
| 150 instead of GL_HASH_SET. */ | |
| 151 | |
| 152 /* Type of an iterator that traverses a set. | |
| 153 This is a fixed-size struct, so that creation of an iterator doesn't need | |
| 154 memory allocation on the heap. */ | |
| 155 typedef struct | |
| 156 { | |
| 157 /* For fast dispatch of gl_set_iterator_next. */ | |
| 158 const struct gl_set_implementation *vtable; | |
| 159 /* For detecting whether the last returned element was removed. */ | |
| 160 gl_set_t set; | |
| 161 size_t count; | |
| 162 /* Other, implementation-private fields. */ | |
| 163 void *p; void *q; | |
| 164 size_t i; size_t j; | |
| 165 } gl_set_iterator_t; | |
| 166 | |
| 167 #if 0 /* These are defined inline below. */ | |
| 168 | |
| 169 /* Create an iterator traversing a set. | |
| 170 The set's contents must not be modified while the iterator is in use, | |
| 171 except for removing the last returned element. */ | |
| 172 extern gl_set_iterator_t gl_set_iterator (gl_set_t set); | |
| 173 | |
| 174 /* If there is a next element, store the next element in *ELTP, advance the | |
| 175 iterator and return true. Otherwise, return false. */ | |
| 176 extern bool gl_set_iterator_next (gl_set_iterator_t *iterator, | |
| 177 const void **eltp); | |
| 178 | |
| 179 /* Free an iterator. */ | |
| 180 extern void gl_set_iterator_free (gl_set_iterator_t *iterator); | |
| 181 | |
| 182 #endif /* End of inline functions. */ | |
| 183 | |
| 184 /* ------------------------ Implementation Details ------------------------ */ | |
| 185 | |
| 186 struct gl_set_implementation | |
| 187 { | |
| 188 /* gl_set_t functions. */ | |
| 189 gl_set_t (*nx_create_empty) (gl_set_implementation_t implementation, | |
| 190 gl_setelement_equals_fn equals_fn, | |
| 191 gl_setelement_hashcode_fn hashcode_fn, | |
| 192 gl_setelement_dispose_fn dispose_fn); | |
| 193 size_t (*size) (gl_set_t set); | |
| 194 bool (*search) (gl_set_t set, const void *elt); | |
| 195 int (*nx_add) (gl_set_t set, const void *elt); | |
| 196 bool (*remove_elt) (gl_set_t set, const void *elt); | |
| 197 void (*set_free) (gl_set_t set); | |
| 198 /* gl_set_iterator_t functions. */ | |
| 199 gl_set_iterator_t (*iterator) (gl_set_t set); | |
| 200 bool (*iterator_next) (gl_set_iterator_t *iterator, const void **eltp); | |
| 201 void (*iterator_free) (gl_set_iterator_t *iterator); | |
| 202 }; | |
| 203 | |
| 204 struct gl_set_impl_base | |
| 205 { | |
| 206 const struct gl_set_implementation *vtable; | |
| 207 gl_setelement_equals_fn equals_fn; | |
| 208 gl_setelement_dispose_fn dispose_fn; | |
| 209 }; | |
| 210 | |
| 211 /* Define all functions of this file as accesses to the | |
| 212 struct gl_set_implementation. */ | |
| 213 | |
| 214 GL_SET_INLINE gl_set_t | |
| 215 gl_set_nx_create_empty (gl_set_implementation_t implementation, | |
| 216 gl_setelement_equals_fn equals_fn, | |
| 217 gl_setelement_hashcode_fn hashcode_fn, | |
| 218 gl_setelement_dispose_fn dispose_fn) | |
| 219 { | |
| 220 return implementation->nx_create_empty (implementation, equals_fn, | |
| 221 hashcode_fn, dispose_fn); | |
| 222 } | |
| 223 | |
| 224 GL_SET_INLINE size_t | |
| 225 gl_set_size (gl_set_t set) | |
| 226 { | |
| 227 return ((const struct gl_set_impl_base *) set)->vtable->size (set); | |
| 228 } | |
| 229 | |
| 230 GL_SET_INLINE bool | |
| 231 gl_set_search (gl_set_t set, const void *elt) | |
| 232 { | |
| 233 return ((const struct gl_set_impl_base *) set)->vtable->search (set, elt); | |
| 234 } | |
| 235 | |
| 236 GL_SET_INLINE int | |
| 237 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) | |
| 238 __attribute__ ((__warn_unused_result__)) | |
| 239 #endif | |
| 240 gl_set_nx_add (gl_set_t set, const void *elt) | |
| 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) | |
| 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) | |
| 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) | |
| 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) | |
| 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) | |
| 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 */ |