1 /* Abstract ordered set data type.
2 Copyright (C) 2006-2007, 2009-2013 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 <http://www.gnu.org/licenses/>. */
24 _GL_INLINE_HEADER_BEGIN
25 #ifndef GL_OSET_INLINE
26 # define GL_OSET_INLINE _GL_INLINE
34 /* gl_oset is an abstract ordered set data type. It can contain any number
35 of objects ('void *' or 'const void *' pointers) in the order of a given
36 comparator function. Duplicates (in the sense of the comparator) are
39 There are several implementations of this ordered set datatype, optimized
40 for different operations or for memory. You can start using the simplest
41 ordered set implementation, GL_ARRAY_OSET, and switch to a different
42 implementation later, when you realize which operations are performed
43 the most frequently. The API of the different implementations is exactly
44 the same; when switching to a different implementation, you only have to
45 change the gl_oset_create call.
47 The implementations are:
48 GL_ARRAY_OSET a growable array
49 GL_AVLTREE_OSET a binary tree (AVL tree)
50 GL_RBTREE_OSET a binary tree (red-black tree)
52 The memory consumption is asymptotically the same: O(1) for every object
53 in the set. When looking more closely at the average memory consumed
54 for an object, GL_ARRAY_OSET is the most compact representation, and
55 GL_AVLTREE_OSET, GL_RBTREE_OSET need more memory.
57 The guaranteed average performance of the operations is, for a set of
62 gl_oset_size O(1) O(1)
63 gl_oset_add O(n) O(log n)
64 gl_oset_remove O(n) O(log n)
65 gl_oset_search O(log n) O(log n)
66 gl_oset_search_atleast O(log n) O(log n)
67 gl_oset_iterator O(1) O(log n)
68 gl_oset_iterator_next O(1) O(log n)
71 /* -------------------------- gl_oset_t Data Type -------------------------- */
73 /* Type of function used to compare two elements. Same as for qsort().
74 NULL denotes pointer comparison. */
75 typedef int (*gl_setelement_compar_fn) (const void *elt1, const void *elt2);
77 /* Type of function used to dispose an element once it's removed from a set.
78 NULL denotes a no-op. */
79 typedef void (*gl_setelement_dispose_fn) (const void *elt);
81 /* Type of function used to compare an element with a threshold.
82 Return true if the element is greater or equal than the threshold. */
83 typedef bool (*gl_setelement_threshold_fn) (const void *elt, const void *threshold);
86 /* Type representing an entire ordered set. */
87 typedef struct gl_oset_impl * gl_oset_t;
89 struct gl_oset_implementation;
90 /* Type representing a ordered set datatype implementation. */
91 typedef const struct gl_oset_implementation * gl_oset_implementation_t;
93 #if 0 /* Unless otherwise specified, these are defined inline below. */
95 /* Create an empty set.
96 IMPLEMENTATION is one of GL_ARRAY_OSET, GL_AVLTREE_OSET, GL_RBTREE_OSET.
97 COMPAR_FN is an element comparison function or NULL.
98 DISPOSE_FN is an element disposal function or NULL. */
99 /* declared in gl_xoset.h */
100 extern gl_oset_t gl_oset_create_empty (gl_oset_implementation_t implementation,
101 gl_setelement_compar_fn compar_fn,
102 gl_setelement_dispose_fn dispose_fn);
103 /* Likewise. Return NULL upon out-of-memory. */
104 extern gl_oset_t gl_oset_nx_create_empty (gl_oset_implementation_t implementation,
105 gl_setelement_compar_fn compar_fn,
106 gl_setelement_dispose_fn dispose_fn);
108 /* Return the current number of elements in an ordered set. */
109 extern size_t gl_oset_size (gl_oset_t set);
111 /* Search whether an element is already in the ordered set.
112 Return true if found, or false if not present in the set. */
113 extern bool gl_oset_search (gl_oset_t set, const void *elt);
115 /* Search the least element in the ordered set that compares greater or equal
116 to the given THRESHOLD. The representation of the THRESHOLD is defined
118 Return true and store the found element in *ELTP if found, otherwise return
120 extern bool gl_oset_search_atleast (gl_oset_t set,
121 gl_setelement_threshold_fn threshold_fn,
122 const void *threshold,
125 /* Add an element to an ordered set.
126 Return true if it was not already in the set and added, false otherwise. */
127 /* declared in gl_xoset.h */
128 extern bool gl_oset_add (gl_oset_t set, const void *elt);
129 /* Likewise. Return -1 upon out-of-memory. */
130 extern int gl_oset_nx_add (gl_oset_t set, const void *elt)
131 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
132 __attribute__ ((__warn_unused_result__))
136 /* Remove an element from an ordered set.
137 Return true if it was found and removed. */
138 extern bool gl_oset_remove (gl_oset_t set, const void *elt);
140 /* Free an entire ordered set.
141 (But this call does not free the elements of the set.) */
142 extern void gl_oset_free (gl_oset_t set);
144 #endif /* End of inline and gl_xlist.h-defined functions. */
146 /* --------------------- gl_oset_iterator_t Data Type --------------------- */
148 /* Functions for iterating through an ordered set. */
150 /* Type of an iterator that traverses an ordered set.
151 This is a fixed-size struct, so that creation of an iterator doesn't need
152 memory allocation on the heap. */
155 /* For fast dispatch of gl_oset_iterator_next. */
156 const struct gl_oset_implementation *vtable;
157 /* For detecting whether the last returned element was removed. */
160 /* Other, implementation-private fields. */
163 } gl_oset_iterator_t;
165 #if 0 /* These are defined inline below. */
167 /* Create an iterator traversing an ordered set.
168 The set's contents must not be modified while the iterator is in use,
169 except for removing the last returned element. */
170 extern gl_oset_iterator_t gl_oset_iterator (gl_oset_t set);
172 /* If there is a next element, store the next element in *ELTP, advance the
173 iterator and return true. Otherwise, return false. */
174 extern bool gl_oset_iterator_next (gl_oset_iterator_t *iterator,
177 /* Free an iterator. */
178 extern void gl_oset_iterator_free (gl_oset_iterator_t *iterator);
180 #endif /* End of inline functions. */
182 /* ------------------------ Implementation Details ------------------------ */
184 struct gl_oset_implementation
186 /* gl_oset_t functions. */
187 gl_oset_t (*nx_create_empty) (gl_oset_implementation_t implementation,
188 gl_setelement_compar_fn compar_fn,
189 gl_setelement_dispose_fn dispose_fn);
190 size_t (*size) (gl_oset_t set);
191 bool (*search) (gl_oset_t set, const void *elt);
192 bool (*search_atleast) (gl_oset_t set,
193 gl_setelement_threshold_fn threshold_fn,
194 const void *threshold, const void **eltp);
195 int (*nx_add) (gl_oset_t set, const void *elt);
196 bool (*remove_elt) (gl_oset_t set, const void *elt);
197 void (*oset_free) (gl_oset_t set);
198 /* gl_oset_iterator_t functions. */
199 gl_oset_iterator_t (*iterator) (gl_oset_t set);
200 bool (*iterator_next) (gl_oset_iterator_t *iterator, const void **eltp);
201 void (*iterator_free) (gl_oset_iterator_t *iterator);
204 struct gl_oset_impl_base
206 const struct gl_oset_implementation *vtable;
207 gl_setelement_compar_fn compar_fn;
208 gl_setelement_dispose_fn dispose_fn;
211 /* Define all functions of this file as accesses to the
212 struct gl_oset_implementation. */
214 GL_OSET_INLINE gl_oset_t
215 gl_oset_nx_create_empty (gl_oset_implementation_t implementation,
216 gl_setelement_compar_fn compar_fn,
217 gl_setelement_dispose_fn dispose_fn)
219 return implementation->nx_create_empty (implementation, compar_fn,
223 GL_OSET_INLINE size_t
224 gl_oset_size (gl_oset_t set)
226 return ((const struct gl_oset_impl_base *) set)->vtable->size (set);
230 gl_oset_search (gl_oset_t set, const void *elt)
232 return ((const struct gl_oset_impl_base *) set)->vtable->search (set, elt);
236 gl_oset_search_atleast (gl_oset_t set,
237 gl_setelement_threshold_fn threshold_fn,
238 const void *threshold, const void **eltp)
240 return ((const struct gl_oset_impl_base *) set)->vtable
241 ->search_atleast (set, threshold_fn, threshold, eltp);
245 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
246 __attribute__ ((__warn_unused_result__))
248 gl_oset_nx_add (gl_oset_t set, const void *elt)
250 return ((const struct gl_oset_impl_base *) set)->vtable->nx_add (set, elt);
254 gl_oset_remove (gl_oset_t set, const void *elt)
256 return ((const struct gl_oset_impl_base *) set)->vtable
257 ->remove_elt (set, elt);
261 gl_oset_free (gl_oset_t set)
263 ((const struct gl_oset_impl_base *) set)->vtable->oset_free (set);
266 GL_OSET_INLINE gl_oset_iterator_t
267 gl_oset_iterator (gl_oset_t set)
269 return ((const struct gl_oset_impl_base *) set)->vtable->iterator (set);
273 gl_oset_iterator_next (gl_oset_iterator_t *iterator, const void **eltp)
275 return iterator->vtable->iterator_next (iterator, eltp);
279 gl_oset_iterator_free (gl_oset_iterator_t *iterator)
281 iterator->vtable->iterator_free (iterator);
288 _GL_INLINE_HEADER_END
290 #endif /* _GL_OSET_H */