1 /* Abstract ordered set data type.
2 Copyright (C) 2006-2007, 2009-2014 Free Software Foundation, Inc.
3 Written by Bruno Haible <bruno@clisp.org>, 2006.
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 <http://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_search O(log n) O(log n)
69 gl_oset_search_atleast O(log n) O(log n)
70 gl_oset_iterator O(1) O(log n)
71 gl_oset_iterator_next O(1) O(log n)
72 */
73
74 /* -------------------------- gl_oset_t Data Type -------------------------- */
75
76 /* Type of function used to compare two elements. Same as for qsort().
77 NULL denotes pointer comparison. */
78 typedef int (*gl_setelement_compar_fn) (const void *elt1, const void *elt2);
79
80 /* Type of function used to dispose an element once it's removed from a set.
81 NULL denotes a no-op. */
82 typedef void (*gl_setelement_dispose_fn) (const void *elt);
83
84 /* Type of function used to compare an element with a threshold.
85 Return true if the element is greater or equal than the threshold. */
86 typedef bool (*gl_setelement_threshold_fn) (const void *elt, const void *threshold);
87
88 struct gl_oset_impl;
89 /* Type representing an entire ordered set. */
90 typedef struct gl_oset_impl * gl_oset_t;
91
92 struct gl_oset_implementation;
93 /* Type representing a ordered set datatype implementation. */
94 typedef const struct gl_oset_implementation * gl_oset_implementation_t;
95
96 #if 0 /* Unless otherwise specified, these are defined inline below. */
97
98 /* Create an empty set.
99 IMPLEMENTATION is one of GL_ARRAY_OSET, GL_AVLTREE_OSET, GL_RBTREE_OSET.
100 COMPAR_FN is an element comparison function or NULL.
101 DISPOSE_FN is an element disposal function or NULL. */
102 /* declared in gl_xoset.h */
103 extern gl_oset_t gl_oset_create_empty (gl_oset_implementation_t implementation,
104 gl_setelement_compar_fn compar_fn,
105 gl_setelement_dispose_fn dispose_fn);
106 /* Likewise. Return NULL upon out-of-memory. */
107 extern gl_oset_t gl_oset_nx_create_empty (gl_oset_implementation_t implementation,
108 gl_setelement_compar_fn compar_fn,
109 gl_setelement_dispose_fn dispose_fn);
110
111 /* Return the current number of elements in an ordered set. */
112 extern size_t gl_oset_size (gl_oset_t set);
113
114 /* Search whether an element is already in the ordered set.
115 Return true if found, or false if not present in the set. */
116 extern bool gl_oset_search (gl_oset_t set, const void *elt);
117
118 /* Search the least element in the ordered set that compares greater or equal
119 to the given THRESHOLD. The representation of the THRESHOLD is defined
120 by the THRESHOLD_FN.
121 Return true and store the found element in *ELTP if found, otherwise return
122 false. */
123 extern bool gl_oset_search_atleast (gl_oset_t set,
124 gl_setelement_threshold_fn threshold_fn,
125 const void *threshold,
126 const void **eltp);
127
128 /* Add an element to an ordered set.
129 Return true if it was not already in the set and added, false otherwise. */
130 /* declared in gl_xoset.h */
131 extern bool gl_oset_add (gl_oset_t set, const void *elt);
132 /* Likewise. Return -1 upon out-of-memory. */
133 extern int gl_oset_nx_add (gl_oset_t set, const void *elt)
134 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
135 __attribute__ ((__warn_unused_result__))
136 #endif
137 ;
138
139 /* Remove an element from an ordered set.
140 Return true if it was found and removed. */
141 extern bool gl_oset_remove (gl_oset_t set, const void *elt);
142
143 /* Free an entire ordered set.
144 (But this call does not free the elements of the set.) */
145 extern void gl_oset_free (gl_oset_t set);
146
147 #endif /* End of inline and gl_xlist.h-defined functions. */
148
149 /* --------------------- gl_oset_iterator_t Data Type --------------------- */
150
151 /* Functions for iterating through an ordered set. */
152
153 /* Type of an iterator that traverses an ordered 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_oset_iterator_next. */
159 const struct gl_oset_implementation *vtable;
160 /* For detecting whether the last returned element was removed. */
161 gl_oset_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_oset_iterator_t;
167
168 #if 0 /* These are defined inline below. */
169
170 /* Create an iterator traversing an ordered 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_oset_iterator_t gl_oset_iterator (gl_oset_t set);
174
175 /* If there is a next element, store the next element in *ELTP, advance the
176 iterator and return true. Otherwise, return false. */
177 extern bool gl_oset_iterator_next (gl_oset_iterator_t *iterator,
178 const void **eltp);
179
180 /* Free an iterator. */
181 extern void gl_oset_iterator_free (gl_oset_iterator_t *iterator);
182
183 #endif /* End of inline functions. */
184
185 /* ------------------------ Implementation Details ------------------------ */
186
187 struct gl_oset_implementation
188 {
189 /* gl_oset_t functions. */
190 gl_oset_t (*nx_create_empty) (gl_oset_implementation_t implementation,
191 gl_setelement_compar_fn compar_fn,
192 gl_setelement_dispose_fn dispose_fn);
193 size_t (*size) (gl_oset_t set);
194 bool (*search) (gl_oset_t set, const void *elt);
195 bool (*search_atleast) (gl_oset_t set,
196 gl_setelement_threshold_fn threshold_fn,
197 const void *threshold, const void **eltp);
198 int (*nx_add) (gl_oset_t set, const void *elt);
199 bool (*remove_elt) (gl_oset_t set, const void *elt);
200 void (*oset_free) (gl_oset_t set);
201 /* gl_oset_iterator_t functions. */
202 gl_oset_iterator_t (*iterator) (gl_oset_t set);
203 bool (*iterator_next) (gl_oset_iterator_t *iterator, const void **eltp);
204 void (*iterator_free) (gl_oset_iterator_t *iterator);
205 };
206
207 struct gl_oset_impl_base
208 {
209 const struct gl_oset_implementation *vtable;
210 gl_setelement_compar_fn compar_fn;
211 gl_setelement_dispose_fn dispose_fn;
212 };
213
214 /* Define all functions of this file as accesses to the
215 struct gl_oset_implementation. */
216
217 GL_OSET_INLINE gl_oset_t
gl_oset_nx_create_empty(gl_oset_implementation_t implementation,gl_setelement_compar_fn compar_fn,gl_setelement_dispose_fn dispose_fn)218 gl_oset_nx_create_empty (gl_oset_implementation_t implementation,
219 gl_setelement_compar_fn compar_fn,
220 gl_setelement_dispose_fn dispose_fn)
221 {
222 return implementation->nx_create_empty (implementation, compar_fn,
223 dispose_fn);
224 }
225
226 GL_OSET_INLINE size_t
gl_oset_size(gl_oset_t set)227 gl_oset_size (gl_oset_t set)
228 {
229 return ((const struct gl_oset_impl_base *) set)->vtable->size (set);
230 }
231
232 GL_OSET_INLINE bool
gl_oset_search(gl_oset_t set,const void * elt)233 gl_oset_search (gl_oset_t set, const void *elt)
234 {
235 return ((const struct gl_oset_impl_base *) set)->vtable->search (set, elt);
236 }
237
238 GL_OSET_INLINE bool
gl_oset_search_atleast(gl_oset_t set,gl_setelement_threshold_fn threshold_fn,const void * threshold,const void ** eltp)239 gl_oset_search_atleast (gl_oset_t set,
240 gl_setelement_threshold_fn threshold_fn,
241 const void *threshold, const void **eltp)
242 {
243 return ((const struct gl_oset_impl_base *) set)->vtable
244 ->search_atleast (set, threshold_fn, threshold, eltp);
245 }
246
247 GL_OSET_INLINE int
248 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
249 __attribute__ ((__warn_unused_result__))
250 #endif
gl_oset_nx_add(gl_oset_t set,const void * elt)251 gl_oset_nx_add (gl_oset_t set, const void *elt)
252 {
253 return ((const struct gl_oset_impl_base *) set)->vtable->nx_add (set, elt);
254 }
255
256 GL_OSET_INLINE bool
gl_oset_remove(gl_oset_t set,const void * elt)257 gl_oset_remove (gl_oset_t set, const void *elt)
258 {
259 return ((const struct gl_oset_impl_base *) set)->vtable
260 ->remove_elt (set, elt);
261 }
262
263 GL_OSET_INLINE void
gl_oset_free(gl_oset_t set)264 gl_oset_free (gl_oset_t set)
265 {
266 ((const struct gl_oset_impl_base *) set)->vtable->oset_free (set);
267 }
268
269 GL_OSET_INLINE gl_oset_iterator_t
gl_oset_iterator(gl_oset_t set)270 gl_oset_iterator (gl_oset_t set)
271 {
272 return ((const struct gl_oset_impl_base *) set)->vtable->iterator (set);
273 }
274
275 GL_OSET_INLINE bool
gl_oset_iterator_next(gl_oset_iterator_t * iterator,const void ** eltp)276 gl_oset_iterator_next (gl_oset_iterator_t *iterator, const void **eltp)
277 {
278 return iterator->vtable->iterator_next (iterator, eltp);
279 }
280
281 GL_OSET_INLINE void
gl_oset_iterator_free(gl_oset_iterator_t * iterator)282 gl_oset_iterator_free (gl_oset_iterator_t *iterator)
283 {
284 iterator->vtable->iterator_free (iterator);
285 }
286
287 #ifdef __cplusplus
288 }
289 #endif
290
291 _GL_INLINE_HEADER_END
292
293 #endif /* _GL_OSET_H */
294