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.
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.
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.
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/>. */
24 #ifndef _GL_INLINE_HEADER_BEGIN
25 #error "Please include config.h first."
27 _GL_INLINE_HEADER_BEGIN
28 #ifndef GL_OSET_INLINE
29 # define GL_OSET_INLINE _GL_INLINE
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
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.
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)
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.
60 The guaranteed average performance of the operations is, for a set of
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)
76 /* -------------------------- gl_oset_t Data Type -------------------------- */
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);
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
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);
94 /* Type representing an entire ordered set. */
95 typedef struct gl_oset_impl * gl_oset_t;
97 struct gl_oset_implementation;
98 /* Type representing a ordered set datatype implementation. */
99 typedef const struct gl_oset_implementation * gl_oset_implementation_t;
101 #if 0 /* Unless otherwise specified, these are defined inline below. */
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 /* Likewise. Returns NULL upon out-of-memory. */
112 extern gl_oset_t gl_oset_nx_create_empty (gl_oset_implementation_t implementation,
113 gl_setelement_compar_fn compar_fn,
114 gl_setelement_dispose_fn dispose_fn);
116 /* Returns the current number of elements in an ordered set. */
117 extern size_t gl_oset_size (gl_oset_t set);
119 /* Searches whether an element is already in the ordered set.
120 Returns true if found, or false if not present in the set. */
121 extern bool gl_oset_search (gl_oset_t set, const void *elt);
123 /* Searches the least element in the ordered set that compares greater or equal
124 to the given THRESHOLD. The representation of the THRESHOLD is defined
126 Returns true and stores the found element in *ELTP if found, otherwise returns
128 extern bool gl_oset_search_atleast (gl_oset_t set,
129 gl_setelement_threshold_fn threshold_fn,
130 const void *threshold,
133 /* Adds an element to an ordered set.
134 Returns true if it was not already in the set and added, false otherwise. */
135 /* declared in gl_xoset.h */
136 extern bool gl_oset_add (gl_oset_t set, const void *elt);
137 /* Likewise. Returns -1 upon out-of-memory. */
138 extern int gl_oset_nx_add (gl_oset_t set, const void *elt)
139 _GL_ATTRIBUTE_NODISCARD;
141 /* Removes an element from an ordered set.
142 Returns true if it was found and removed. */
143 extern bool gl_oset_remove (gl_oset_t set, const void *elt);
145 /* Invokes ACTION (ELT, ACTION_DATA) and updates the given ordered set if,
146 during this invocation, the attributes/properties of the element ELT change
147 in a way that influences the comparison function.
148 Warning: During the invocation of ACTION, the ordered set is inconsistent
149 and must not be accessed!
150 Returns 1 if the position of the element in the ordered set has changed as
151 a consequence, 0 if the element stayed at the same position, or -1 if it
152 collided with another element and was therefore removed. */
153 extern int gl_oset_update (gl_oset_t set, const void *elt,
154 void (*action) (const void *elt, void *action_data),
157 /* Frees an entire ordered set.
158 (But this call does not free the elements of the set. It only invokes
159 the DISPOSE_FN on each of the elements of the set.) */
160 extern void gl_oset_free (gl_oset_t set);
162 #endif /* End of inline and gl_xoset.h-defined functions. */
164 /* --------------------- gl_oset_iterator_t Data Type --------------------- */
166 /* Functions for iterating through an ordered set. */
168 /* Type of an iterator that traverses an ordered set.
169 This is a fixed-size struct, so that creation of an iterator doesn't need
170 memory allocation on the heap. */
173 /* For fast dispatch of gl_oset_iterator_next. */
174 const struct gl_oset_implementation *vtable;
175 /* For detecting whether the last returned element was removed. */
178 /* Other, implementation-private fields. */
181 } gl_oset_iterator_t;
183 #if 0 /* These are defined inline below. */
185 /* Creates an iterator traversing an ordered set.
186 The set's contents must not be modified while the iterator is in use,
187 except for removing the last returned element. */
188 extern gl_oset_iterator_t gl_oset_iterator (gl_oset_t set);
190 /* Creates an iterator traversing the tail of an ordered set, that comprises
191 the elements that compare greater or equal to the given THRESHOLD. The
192 representation of the THRESHOLD is defined by the THRESHOLD_FN. */
193 extern gl_oset_iterator_t gl_oset_iterator_atleast (gl_oset_t set,
194 gl_setelement_threshold_fn threshold_fn,
195 const void *threshold);
197 /* If there is a next element, stores the next element in *ELTP, advances the
198 iterator and returns true. Otherwise, returns false. */
199 extern bool gl_oset_iterator_next (gl_oset_iterator_t *iterator,
202 /* Frees an iterator. */
203 extern void gl_oset_iterator_free (gl_oset_iterator_t *iterator);
205 #endif /* End of inline functions. */
207 /* ------------------------ Implementation Details ------------------------ */
209 struct gl_oset_implementation
211 /* gl_oset_t functions. */
212 gl_oset_t (*nx_create_empty) (gl_oset_implementation_t implementation,
213 gl_setelement_compar_fn compar_fn,
214 gl_setelement_dispose_fn dispose_fn);
215 size_t (*size) (gl_oset_t set);
216 bool (*search) (gl_oset_t set, const void *elt);
217 bool (*search_atleast) (gl_oset_t set,
218 gl_setelement_threshold_fn threshold_fn,
219 const void *threshold, const void **eltp);
220 int (*nx_add) (gl_oset_t set, const void *elt);
221 bool (*remove_elt) (gl_oset_t set, const void *elt);
222 int (*update) (gl_oset_t set, const void *elt,
223 void (*action) (const void * /*elt*/, void * /*action_data*/),
225 void (*oset_free) (gl_oset_t set);
226 /* gl_oset_iterator_t functions. */
227 gl_oset_iterator_t (*iterator) (gl_oset_t set);
228 gl_oset_iterator_t (*iterator_atleast) (gl_oset_t set,
229 gl_setelement_threshold_fn threshold_fn,
230 const void *threshold);
231 bool (*iterator_next) (gl_oset_iterator_t *iterator, const void **eltp);
232 void (*iterator_free) (gl_oset_iterator_t *iterator);
235 struct gl_oset_impl_base
237 const struct gl_oset_implementation *vtable;
238 gl_setelement_compar_fn compar_fn;
239 gl_setelement_dispose_fn dispose_fn;
242 /* Define all functions of this file as accesses to the
243 struct gl_oset_implementation. */
245 GL_OSET_INLINE gl_oset_t
246 gl_oset_nx_create_empty (gl_oset_implementation_t implementation,
247 gl_setelement_compar_fn compar_fn,
248 gl_setelement_dispose_fn dispose_fn)
250 return implementation->nx_create_empty (implementation, compar_fn,
254 GL_OSET_INLINE size_t
255 gl_oset_size (gl_oset_t set)
257 return ((const struct gl_oset_impl_base *) set)->vtable->size (set);
261 gl_oset_search (gl_oset_t set, const void *elt)
263 return ((const struct gl_oset_impl_base *) set)->vtable->search (set, elt);
267 gl_oset_search_atleast (gl_oset_t set,
268 gl_setelement_threshold_fn threshold_fn,
269 const void *threshold, const void **eltp)
271 return ((const struct gl_oset_impl_base *) set)->vtable
272 ->search_atleast (set, threshold_fn, threshold, eltp);
275 GL_OSET_INLINE _GL_ATTRIBUTE_NODISCARD int
276 gl_oset_nx_add (gl_oset_t set, const void *elt)
278 return ((const struct gl_oset_impl_base *) set)->vtable->nx_add (set, elt);
282 gl_oset_remove (gl_oset_t set, const void *elt)
284 return ((const struct gl_oset_impl_base *) set)->vtable
285 ->remove_elt (set, elt);
289 gl_oset_update (gl_oset_t set, const void *elt,
290 void (*action) (const void * /*elt*/, void * /*action_data*/),
293 return ((const struct gl_oset_impl_base *) set)->vtable
294 ->update (set, elt, action, action_data);
298 gl_oset_free (gl_oset_t set)
300 ((const struct gl_oset_impl_base *) set)->vtable->oset_free (set);
303 GL_OSET_INLINE gl_oset_iterator_t
304 gl_oset_iterator (gl_oset_t set)
306 return ((const struct gl_oset_impl_base *) set)->vtable->iterator (set);
309 GL_OSET_INLINE gl_oset_iterator_t
310 gl_oset_iterator_atleast (gl_oset_t set,
311 gl_setelement_threshold_fn threshold_fn,
312 const void *threshold)
314 return ((const struct gl_oset_impl_base *) set)->vtable
315 ->iterator_atleast (set, threshold_fn, threshold);
319 gl_oset_iterator_next (gl_oset_iterator_t *iterator, const void **eltp)
321 return iterator->vtable->iterator_next (iterator, eltp);
325 gl_oset_iterator_free (gl_oset_iterator_t *iterator)
327 iterator->vtable->iterator_free (iterator);
334 _GL_INLINE_HEADER_END
336 #endif /* _GL_OSET_H */