![[first]](../icons/first.png){kind=icon}
![[previous]](../icons/n_left.png){kind=icon}
![[next]](../icons/n_right.png){kind=icon}
![[last]](../icons/last.png){kind=icon}
![[top]](../icons/n_top.png){kind=icon}
![[bottom]](../icons/bottom.png){kind=icon}
![[index]](../icons/index.png){kind=icon}
![[help]](../icons/help.png){kind=icon}
*/
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,
/* ![[next]](../icons/right.png)
![[first]](../icons/n_first.png)
![[top]](../icons/top.png)
*/
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]](../icons/left.png)
*/
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)
/* */
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)
/* */
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)
/* */
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)
/* ![[last]](../icons/n_last.png)
*/
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 */
![[bottom]](../icons/n_bottom.png){kind=icon}
*/