1 /* Abstract ordered set data type.
2 Copyright (C) 2006-2007, 2009-2021 Free Software Foundation, Inc.
3 Written by Bruno Haible <bruno@clisp.org>, 2006.
4
5 This file is free software: you can redistribute it and/or modify
6 it under the terms of the GNU Lesser General Public License as
7 published by the Free Software Foundation; either version 2.1 of the
8 License, or (at your option) any later version.
9
10 This file 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 Lesser General Public License for more details.
14
15 You should have received a copy of the GNU Lesser General Public License
16 along with this program. If not, see <https://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 #ifndef _GL_INLINE_HEADER_BEGIN
25 #error "Please include config.h first."
26 #endif
27 _GL_INLINE_HEADER_BEGIN
28 #ifndef GL_OSET_INLINE
29 # define GL_OSET_INLINE _GL_INLINE
30 #endif
31
32 #ifdef __cplusplus
33 extern "C" {
34 #endif
35
36
37 /* gl_oset is an abstract ordered set data type. It can contain any number
38 of objects ('void *' or 'const void *' pointers) in the order of a given
39 comparator function. Duplicates (in the sense of the comparator) are
40 forbidden.
41
42 There are several implementations of this ordered set datatype, optimized
43 for different operations or for memory. You can start using the simplest
44 ordered set implementation, GL_ARRAY_OSET, and switch to a different
45 implementation later, when you realize which operations are performed
46 the most frequently. The API of the different implementations is exactly
47 the same; when switching to a different implementation, you only have to
48 change the gl_oset_create call.
49
50 The implementations are:
51 GL_ARRAY_OSET a growable array
52 GL_AVLTREE_OSET a binary tree (AVL tree)
53 GL_RBTREE_OSET a binary tree (red-black tree)
54
55 The memory consumption is asymptotically the same: O(1) for every object
56 in the set. When looking more closely at the average memory consumed
57 for an object, GL_ARRAY_OSET is the most compact representation, and
58 GL_AVLTREE_OSET, GL_RBTREE_OSET need more memory.
59
60 The guaranteed average performance of the operations is, for a set of
61 n elements:
62
63 Operation ARRAY TREE
64
65 gl_oset_size O(1) O(1)
66 gl_oset_add O(n) O(log n)
67 gl_oset_remove O(n) O(log n)
68 gl_oset_update O(n) O(log n)
69 gl_oset_search O(log n) O(log n)
70 gl_oset_search_atleast O(log n) O(log n)
71 gl_oset_iterator O(1) O(log n)
72 gl_oset_iterator_atleast O(log n) O(log n)
73 gl_oset_iterator_next O(1) O(log n)
74 */
75
76 /* -------------------------- gl_oset_t Data Type -------------------------- */
77
78 /* Type of function used to compare two elements. Same as for qsort().
79 NULL denotes pointer comparison. */
80 typedef int (*gl_setelement_compar_fn) (const void *elt1, const void *elt2);
81
82 #ifndef _GL_SETELEMENT_DISPOSE_FN_DEFINED
83 /* Type of function used to dispose an element once it's removed from a set.
84 NULL denotes a no-op. */
85 typedef void (*gl_setelement_dispose_fn) (const void *elt);
86 # define _GL_SETELEMENT_DISPOSE_FN_DEFINED 1
87 #endif
88
89 /* Type of function used to compare an element with a threshold.
90 Returns true if the element is greater or equal than the threshold. */
91 typedef bool (*gl_setelement_threshold_fn) (const void *elt, const void *threshold);
92
93 struct gl_oset_impl;
94 /* Type representing an entire ordered set. */
95 typedef struct gl_oset_impl * gl_oset_t;
96
97 struct gl_oset_implementation;
98 /* Type representing a ordered set datatype implementation. */
99 typedef const struct gl_oset_implementation * gl_oset_implementation_t;
100
101 #if 0 /* Unless otherwise specified, these are defined inline below. */
102
103 /* Creates an empty set.
104 IMPLEMENTATION is one of GL_ARRAY_OSET, GL_AVLTREE_OSET, GL_RBTREE_OSET.
105 COMPAR_FN is an element comparison function or NULL.
106 DISPOSE_FN is an element disposal function or NULL. */
107 /* declared in gl_xoset.h */
108 extern gl_oset_t gl_oset_create_empty (gl_oset_implementation_t implementation,
109 gl_setelement_compar_fn compar_fn,
110 gl_setelement_dispose_fn dispose_fn)
111 /*_GL_ATTRIBUTE_DEALLOC (gl_oset_free, 1)*/
112 _GL_ATTRIBUTE_RETURNS_NONNULL;
113 /* Likewise. Returns NULL upon out-of-memory. */
114 extern gl_oset_t gl_oset_nx_create_empty (gl_oset_implementation_t implementation,
115 gl_setelement_compar_fn compar_fn,
116 gl_setelement_dispose_fn dispose_fn)
117 /*_GL_ATTRIBUTE_DEALLOC (gl_oset_free, 1)*/;
118
119 /* Returns the current number of elements in an ordered set. */
120 extern size_t gl_oset_size (gl_oset_t set);
121
122 /* Searches whether an element is already in the ordered set.
123 Returns true if found, or false if not present in the set. */
124 extern bool gl_oset_search (gl_oset_t set, const void *elt);
125
126 /* Searches the least element in the ordered set that compares greater or equal
127 to the given THRESHOLD. The representation of the THRESHOLD is defined
128 by the THRESHOLD_FN.
129 Returns true and stores the found element in *ELTP if found, otherwise returns
130 false. */
131 extern bool gl_oset_search_atleast (gl_oset_t set,
132 gl_setelement_threshold_fn threshold_fn,
133 const void *threshold,
134 const void **eltp);
135
136 /* Adds an element to an ordered set.
137 Returns true if it was not already in the set and added, false otherwise. */
138 /* declared in gl_xoset.h */
139 extern bool gl_oset_add (gl_oset_t set, const void *elt);
140
141 /* Likewise. Returns -1 upon out-of-memory. */
142 _GL_ATTRIBUTE_NODISCARD
143 extern int gl_oset_nx_add (gl_oset_t set, const void *elt);
144
145 /* Removes an element from an ordered set.
146 Returns true if it was found and removed. */
147 extern bool gl_oset_remove (gl_oset_t set, const void *elt);
148
149 /* Invokes ACTION (ELT, ACTION_DATA) and updates the given ordered set if,
150 during this invocation, the attributes/properties of the element ELT change
151 in a way that influences the comparison function.
152 Warning: During the invocation of ACTION, the ordered set is inconsistent
153 and must not be accessed!
154 Returns 1 if the position of the element in the ordered set has changed as
155 a consequence, 0 if the element stayed at the same position, or -1 if it
156 collided with another element and was therefore removed. */
157 extern int gl_oset_update (gl_oset_t set, const void *elt,
158 void (*action) (const void *elt, void *action_data),
159 void *action_data);
160
161 /* Frees an entire ordered set.
162 (But this call does not free the elements of the set. It only invokes
163 the DISPOSE_FN on each of the elements of the set.) */
164 extern void gl_oset_free (gl_oset_t set);
165
166 #endif /* End of inline and gl_xoset.h-defined functions. */
167
168 /* --------------------- gl_oset_iterator_t Data Type --------------------- */
169
170 /* Functions for iterating through an ordered set. */
171
172 /* Type of an iterator that traverses an ordered set.
173 This is a fixed-size struct, so that creation of an iterator doesn't need
174 memory allocation on the heap. */
175 typedef struct
176 {
177 /* For fast dispatch of gl_oset_iterator_next. */
178 const struct gl_oset_implementation *vtable;
179 /* For detecting whether the last returned element was removed. */
180 gl_oset_t set;
181 size_t count;
182 /* Other, implementation-private fields. */
183 void *p; void *q;
184 size_t i; size_t j;
185 } gl_oset_iterator_t;
186
187 #if 0 /* These are defined inline below. */
188
189 /* Creates an iterator traversing an ordered set.
190 The set's contents must not be modified while the iterator is in use,
191 except for removing the last returned element. */
192 extern gl_oset_iterator_t gl_oset_iterator (gl_oset_t set);
193
194 /* Creates an iterator traversing the tail of an ordered set, that comprises
195 the elements that compare greater or equal to the given THRESHOLD. The
196 representation of the THRESHOLD is defined by the THRESHOLD_FN. */
197 extern gl_oset_iterator_t gl_oset_iterator_atleast (gl_oset_t set,
198 gl_setelement_threshold_fn threshold_fn,
199 const void *threshold);
200
201 /* If there is a next element, stores the next element in *ELTP, advances the
202 iterator and returns true. Otherwise, returns false. */
203 extern bool gl_oset_iterator_next (gl_oset_iterator_t *iterator,
204 const void **eltp);
205
206 /* Frees an iterator. */
207 extern void gl_oset_iterator_free (gl_oset_iterator_t *iterator);
208
209 #endif /* End of inline functions. */
210
211 /* ------------------------ Implementation Details ------------------------ */
212
213 struct gl_oset_implementation
214 {
215 /* gl_oset_t functions. */
216 gl_oset_t (*nx_create_empty) (gl_oset_implementation_t implementation,
217 gl_setelement_compar_fn compar_fn,
218 gl_setelement_dispose_fn dispose_fn);
219 size_t (*size) (gl_oset_t set);
220 bool (*search) (gl_oset_t set, const void *elt);
221 bool (*search_atleast) (gl_oset_t set,
222 gl_setelement_threshold_fn threshold_fn,
223 const void *threshold, const void **eltp);
224 int (*nx_add) (gl_oset_t set, const void *elt);
225 bool (*remove_elt) (gl_oset_t set, const void *elt);
226 int (*update) (gl_oset_t set, const void *elt,
227 void (*action) (const void * /*elt*/, void * /*action_data*/),
228 void *action_data);
229 void (*oset_free) (gl_oset_t set);
230 /* gl_oset_iterator_t functions. */
231 gl_oset_iterator_t (*iterator) (gl_oset_t set);
232 gl_oset_iterator_t (*iterator_atleast) (gl_oset_t set,
233 gl_setelement_threshold_fn threshold_fn,
234 const void *threshold);
235 bool (*iterator_next) (gl_oset_iterator_t *iterator, const void **eltp);
236 void (*iterator_free) (gl_oset_iterator_t *iterator);
237 };
238
239 struct gl_oset_impl_base
240 {
241 const struct gl_oset_implementation *vtable;
242 gl_setelement_compar_fn compar_fn;
243 gl_setelement_dispose_fn dispose_fn;
244 };
245
246 /* Define all functions of this file as accesses to the
247 struct gl_oset_implementation. */
248
249 GL_OSET_INLINE
250 /*_GL_ATTRIBUTE_DEALLOC (gl_oset_free, 1)*/
251 gl_oset_t
252 gl_oset_nx_create_empty (gl_oset_implementation_t implementation,
253 gl_setelement_compar_fn compar_fn,
254 gl_setelement_dispose_fn dispose_fn)
255 {
256 return implementation->nx_create_empty (implementation, compar_fn,
257 dispose_fn);
258 }
259
260 GL_OSET_INLINE size_t
261 gl_oset_size (gl_oset_t set)
262 {
263 return ((const struct gl_oset_impl_base *) set)->vtable->size (set);
264 }
265
266 GL_OSET_INLINE bool
267 gl_oset_search (gl_oset_t set, const void *elt)
268 {
269 return ((const struct gl_oset_impl_base *) set)->vtable->search (set, elt);
270 }
271
272 GL_OSET_INLINE bool
273 gl_oset_search_atleast (gl_oset_t set,
274 gl_setelement_threshold_fn threshold_fn,
275 const void *threshold, const void **eltp)
276 {
277 return ((const struct gl_oset_impl_base *) set)->vtable
278 ->search_atleast (set, threshold_fn, threshold, eltp);
279 }
280
281 _GL_ATTRIBUTE_NODISCARD GL_OSET_INLINE int
282 gl_oset_nx_add (gl_oset_t set, const void *elt)
283 {
284 return ((const struct gl_oset_impl_base *) set)->vtable->nx_add (set, elt);
285 }
286
287 GL_OSET_INLINE bool
288 gl_oset_remove (gl_oset_t set, const void *elt)
289 {
290 return ((const struct gl_oset_impl_base *) set)->vtable
291 ->remove_elt (set, elt);
292 }
293
294 GL_OSET_INLINE int
295 gl_oset_update (gl_oset_t set, const void *elt,
296 void (*action) (const void * /*elt*/, void * /*action_data*/),
297 void *action_data)
298 {
299 return ((const struct gl_oset_impl_base *) set)->vtable
300 ->update (set, elt, action, action_data);
301 }
302
303 GL_OSET_INLINE void
304 gl_oset_free (gl_oset_t set)
305 {
306 ((const struct gl_oset_impl_base *) set)->vtable->oset_free (set);
307 }
308
309 GL_OSET_INLINE gl_oset_iterator_t
310 gl_oset_iterator (gl_oset_t set)
311 {
312 return ((const struct gl_oset_impl_base *) set)->vtable->iterator (set);
313 }
314
315 GL_OSET_INLINE gl_oset_iterator_t
316 gl_oset_iterator_atleast (gl_oset_t set,
317 gl_setelement_threshold_fn threshold_fn,
318 const void *threshold)
319 {
320 return ((const struct gl_oset_impl_base *) set)->vtable
321 ->iterator_atleast (set, threshold_fn, threshold);
322 }
323
324 GL_OSET_INLINE bool
325 gl_oset_iterator_next (gl_oset_iterator_t *iterator, const void **eltp)
326 {
327 return iterator->vtable->iterator_next (iterator, eltp);
328 }
329
330 GL_OSET_INLINE void
331 gl_oset_iterator_free (gl_oset_iterator_t *iterator)
332 {
333 iterator->vtable->iterator_free (iterator);
334 }
335
336 #ifdef __cplusplus
337 }
338 #endif
339
340 _GL_INLINE_HEADER_END
341
342 #endif /* _GL_OSET_H */