1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
|
/* Abstract set data type.
Copyright (C) 2006-2007, 2009-2020 Free Software Foundation, Inc.
Written by Bruno Haible <bruno@clisp.org>, 2018.
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <https://www.gnu.org/licenses/>. */
#ifndef _GL_SET_H
#define _GL_SET_H
#include <stdbool.h>
#include <stddef.h>
#ifndef _GL_INLINE_HEADER_BEGIN
#error "Please include config.h first."
#endif
_GL_INLINE_HEADER_BEGIN
#ifndef GL_SET_INLINE
# define GL_SET_INLINE _GL_INLINE
#endif
#ifdef __cplusplus
extern "C" {
#endif
/* gl_set is an abstract set data type. It can contain any number of objects
('void *' or 'const void *' pointers); the order does not matter.
Duplicates (in the sense of the comparator) are forbidden.
There are several implementations of this set datatype, optimized for
different operations or for memory. You can start using the simplest set
implementation, GL_ARRAY_SET, and switch to a different implementation
later, when you realize which operations are performed the most frequently.
The API of the different implementations is exactly the same; when switching
to a different implementation, you only have to change the gl_set_create
call.
The implementations are:
GL_ARRAY_SET a growable array
GL_LINKEDHASH_SET a hash table with a linked list
GL_HASH_SET a hash table
The memory consumption is asymptotically the same: O(1) for every object
in the set. When looking more closely at the average memory consumed
for an object, GL_ARRAY_SET is the most compact representation, then comes
GL_HASH_SET, and GL_LINKEDHASH_SET needs the most memory.
The guaranteed average performance of the operations is, for a set of
n elements:
Operation ARRAY LINKEDHASH
HASH
gl_set_size O(1) O(1)
gl_set_add O(n) O(1)
gl_set_remove O(n) O(1)
gl_set_search O(n) O(1)
gl_set_iterator O(1) O(1)
gl_set_iterator_next O(1) O(1)
*/
/* --------------------------- gl_set_t Data Type --------------------------- */
/* Type of function used to compare two elements.
NULL denotes pointer comparison. */
typedef bool (*gl_setelement_equals_fn) (const void *elt1, const void *elt2);
/* Type of function used to compute a hash code.
NULL denotes a function that depends only on the pointer itself. */
typedef size_t (*gl_setelement_hashcode_fn) (const void *elt);
#ifndef _GL_SETELEMENT_DISPOSE_FN_DEFINED
/* Type of function used to dispose an element once it's removed from a set.
NULL denotes a no-op. */
typedef void (*gl_setelement_dispose_fn) (const void *elt);
# define _GL_SETELEMENT_DISPOSE_FN_DEFINED 1
#endif
struct gl_set_impl;
/* Type representing an entire set. */
typedef struct gl_set_impl * gl_set_t;
struct gl_set_implementation;
/* Type representing a set datatype implementation. */
typedef const struct gl_set_implementation * gl_set_implementation_t;
#if 0 /* Unless otherwise specified, these are defined inline below. */
/* Creates an empty set.
IMPLEMENTATION is one of GL_ARRAY_SET, GL_LINKEDHASH_SET, GL_HASH_SET.
EQUALS_FN is an element comparison function or NULL.
HASHCODE_FN is an element hash code function or NULL.
DISPOSE_FN is an element disposal function or NULL. */
/* declared in gl_xset.h */
extern gl_set_t gl_set_create_empty (gl_set_implementation_t implementation,
gl_setelement_equals_fn equals_fn,
gl_setelement_hashcode_fn hashcode_fn,
gl_setelement_dispose_fn dispose_fn);
/* Likewise. Returns NULL upon out-of-memory. */
extern gl_set_t gl_set_nx_create_empty (gl_set_implementation_t implementation,
gl_setelement_equals_fn equals_fn,
gl_setelement_hashcode_fn hashcode_fn,
gl_setelement_dispose_fn dispose_fn);
/* Returns the current number of elements in a set. */
extern size_t gl_set_size (gl_set_t set);
/* Searches whether an element is already in the set.
Returns true if found, or false if not present in the set. */
extern bool gl_set_search (gl_set_t set, const void *elt);
/* Adds an element to a set.
Returns true if it was not already in the set and added, false otherwise. */
/* declared in gl_xset.h */
extern bool gl_set_add (gl_set_t set, const void *elt);
/* Likewise. Returns -1 upon out-of-memory. */
extern int gl_set_nx_add (gl_set_t set, const void *elt)
_GL_ATTRIBUTE_NODISCARD;
/* Removes an element from a set.
Returns true if it was found and removed. */
extern bool gl_set_remove (gl_set_t set, const void *elt);
/* Frees an entire set.
(But this call does not free the elements of the set. It only invokes
the DISPOSE_FN on each of the elements of the set.) */
extern void gl_set_free (gl_set_t set);
#endif /* End of inline and gl_xset.h-defined functions. */
/* ---------------------- gl_set_iterator_t Data Type ---------------------- */
/* Functions for iterating through a set.
Note: Iterating through a set of type GL_HASH_SET returns the elements in an
unpredictable order. If you need a predictable order, use GL_LINKEDHASH_SET
instead of GL_HASH_SET. */
/* Type of an iterator that traverses a set.
This is a fixed-size struct, so that creation of an iterator doesn't need
memory allocation on the heap. */
typedef struct
{
/* For fast dispatch of gl_set_iterator_next. */
const struct gl_set_implementation *vtable;
/* For detecting whether the last returned element was removed. */
gl_set_t set;
size_t count;
/* Other, implementation-private fields. */
void *p; void *q;
size_t i; size_t j;
} gl_set_iterator_t;
#if 0 /* These are defined inline below. */
/* Creates an iterator traversing a set.
The set's contents must not be modified while the iterator is in use,
except for removing the last returned element. */
extern gl_set_iterator_t gl_set_iterator (gl_set_t set);
/* If there is a next element, stores the next element in *ELTP, advances the
iterator and returns true. Otherwise, returns false. */
extern bool gl_set_iterator_next (gl_set_iterator_t *iterator,
const void **eltp);
/* Frees an iterator. */
extern void gl_set_iterator_free (gl_set_iterator_t *iterator);
#endif /* End of inline functions. */
/* ------------------------ Implementation Details ------------------------ */
struct gl_set_implementation
{
/* gl_set_t functions. */
gl_set_t (*nx_create_empty) (gl_set_implementation_t implementation,
gl_setelement_equals_fn equals_fn,
gl_setelement_hashcode_fn hashcode_fn,
gl_setelement_dispose_fn dispose_fn);
size_t (*size) (gl_set_t set);
bool (*search) (gl_set_t set, const void *elt);
int (*nx_add) (gl_set_t set, const void *elt);
bool (*remove_elt) (gl_set_t set, const void *elt);
void (*set_free) (gl_set_t set);
/* gl_set_iterator_t functions. */
gl_set_iterator_t (*iterator) (gl_set_t set);
bool (*iterator_next) (gl_set_iterator_t *iterator, const void **eltp);
void (*iterator_free) (gl_set_iterator_t *iterator);
};
struct gl_set_impl_base
{
const struct gl_set_implementation *vtable;
gl_setelement_equals_fn equals_fn;
gl_setelement_dispose_fn dispose_fn;
};
/* Define all functions of this file as accesses to the
struct gl_set_implementation. */
GL_SET_INLINE gl_set_t
gl_set_nx_create_empty (gl_set_implementation_t implementation,
gl_setelement_equals_fn equals_fn,
gl_setelement_hashcode_fn hashcode_fn,
gl_setelement_dispose_fn dispose_fn)
{
return implementation->nx_create_empty (implementation, equals_fn,
hashcode_fn, dispose_fn);
}
GL_SET_INLINE size_t
gl_set_size (gl_set_t set)
{
return ((const struct gl_set_impl_base *) set)->vtable->size (set);
}
GL_SET_INLINE bool
gl_set_search (gl_set_t set, const void *elt)
{
return ((const struct gl_set_impl_base *) set)->vtable->search (set, elt);
}
GL_SET_INLINE _GL_ATTRIBUTE_NODISCARD int
gl_set_nx_add (gl_set_t set, const void *elt)
{
return ((const struct gl_set_impl_base *) set)->vtable->nx_add (set, elt);
}
GL_SET_INLINE bool
gl_set_remove (gl_set_t set, const void *elt)
{
return ((const struct gl_set_impl_base *) set)->vtable->remove_elt (set, elt);
}
GL_SET_INLINE void
gl_set_free (gl_set_t set)
{
((const struct gl_set_impl_base *) set)->vtable->set_free (set);
}
GL_SET_INLINE gl_set_iterator_t
gl_set_iterator (gl_set_t set)
{
return ((const struct gl_set_impl_base *) set)->vtable->iterator (set);
}
GL_SET_INLINE bool
gl_set_iterator_next (gl_set_iterator_t *iterator, const void **eltp)
{
return iterator->vtable->iterator_next (iterator, eltp);
}
GL_SET_INLINE void
gl_set_iterator_free (gl_set_iterator_t *iterator)
{
iterator->vtable->iterator_free (iterator);
}
#ifdef __cplusplus
}
#endif
_GL_INLINE_HEADER_END
#endif /* _GL_SET_H */
|
