This source file includes following definitions.
- gl_array_nx_create_empty
- gl_array_size
- gl_array_search
- grow
- gl_array_nx_add
- gl_array_remove_at
- gl_array_remove
- gl_array_free
- gl_array_iterator
- gl_array_iterator_next
- gl_array_iterator_free
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 #include <config.h>
19
20
21 #include "gl_array_set.h"
22
23 #include <stdint.h>
24 #include <stdlib.h>
25
26
27 #include "xsize.h"
28
29
30
31
32 struct gl_set_impl
33 {
34 struct gl_set_impl_base base;
35
36
37 const void **elements;
38 size_t count;
39 size_t allocated;
40 };
41
42 static gl_set_t
43 gl_array_nx_create_empty (gl_set_implementation_t implementation,
44 gl_setelement_equals_fn equals_fn,
45 gl_setelement_hashcode_fn hashcode_fn,
46 gl_setelement_dispose_fn dispose_fn)
47 {
48 struct gl_set_impl *set =
49 (struct gl_set_impl *) malloc (sizeof (struct gl_set_impl));
50
51 if (set == NULL)
52 return NULL;
53
54 set->base.vtable = implementation;
55 set->base.equals_fn = equals_fn;
56 set->base.dispose_fn = dispose_fn;
57 set->elements = NULL;
58 set->count = 0;
59 set->allocated = 0;
60
61 return set;
62 }
63
64 static size_t
65 gl_array_size (gl_set_t set)
66 {
67 return set->count;
68 }
69
70 static bool
71 gl_array_search (gl_set_t set, const void *elt)
72 {
73 size_t count = set->count;
74
75 if (count > 0)
76 {
77 gl_setelement_equals_fn equals = set->base.equals_fn;
78 const void **elements = set->elements;
79 if (equals != NULL)
80 {
81 size_t i;
82
83 for (i = 0; i < count; i++)
84 if (equals (elements[i], elt))
85 return true;
86 }
87 else
88 {
89 size_t i;
90
91 for (i = 0; i < count; i++)
92 if (elements[i] == elt)
93 return true;
94 }
95 }
96 return false;
97 }
98
99
100
101 static int
102 grow (gl_set_t set)
103 {
104 size_t new_allocated;
105 size_t memory_size;
106 const void **memory;
107
108 new_allocated = xtimes (set->allocated, 2);
109 new_allocated = xsum (new_allocated, 1);
110 memory_size = xtimes (new_allocated, sizeof (const void *));
111 if (size_overflow_p (memory_size))
112
113 return -1;
114 memory = (const void **) realloc (set->elements, memory_size);
115 if (memory == NULL)
116
117 return -1;
118 set->elements = memory;
119 set->allocated = new_allocated;
120 return 0;
121 }
122
123 static int
124 gl_array_nx_add (gl_set_t set, const void *elt)
125 {
126 if (gl_array_search (set, elt))
127 return 0;
128 else
129 {
130 size_t count = set->count;
131
132 if (count == set->allocated)
133 if (grow (set) < 0)
134 return -1;
135 set->elements[count] = elt;
136 set->count = count + 1;
137 return 1;
138 }
139 }
140
141
142
143 static void
144 gl_array_remove_at (gl_set_t set, size_t position)
145 {
146 size_t count = set->count;
147 const void **elements = set->elements;
148 size_t i;
149
150 if (set->base.dispose_fn != NULL)
151 set->base.dispose_fn (elements[position]);
152 for (i = position + 1; i < count; i++)
153 elements[i - 1] = elements[i];
154 set->count = count - 1;
155 }
156
157 static bool
158 gl_array_remove (gl_set_t set, const void *elt)
159 {
160 size_t count = set->count;
161
162 if (count > 0)
163 {
164 gl_setelement_equals_fn equals = set->base.equals_fn;
165 const void **elements = set->elements;
166
167 if (equals != NULL)
168 {
169 size_t i;
170
171 for (i = 0; i < count; i++)
172 if (equals (elements[i], elt))
173 {
174 gl_array_remove_at (set, i);
175 return true;
176 }
177 }
178 else
179 {
180 size_t i;
181
182 for (i = 0; i < count; i++)
183 if (elements[i] == elt)
184 {
185 gl_array_remove_at (set, i);
186 return true;
187 }
188 }
189 }
190 return false;
191 }
192
193 static void
194 gl_array_free (gl_set_t set)
195 {
196 if (set->elements != NULL)
197 {
198 if (set->base.dispose_fn != NULL)
199 {
200 size_t count = set->count;
201
202 if (count > 0)
203 {
204 gl_setelement_dispose_fn dispose = set->base.dispose_fn;
205 const void **elements = set->elements;
206
207 do
208 dispose (*elements++);
209 while (--count > 0);
210 }
211 }
212 free (set->elements);
213 }
214 free (set);
215 }
216
217
218
219 static gl_set_iterator_t
220 gl_array_iterator (gl_set_t set)
221 {
222 gl_set_iterator_t result;
223
224 result.vtable = set->base.vtable;
225 result.set = set;
226 result.count = set->count;
227 result.p = set->elements + 0;
228 result.q = set->elements + set->count;
229 #if defined GCC_LINT || defined lint
230 result.i = 0;
231 result.j = 0;
232 #endif
233
234 return result;
235 }
236
237 static bool
238 gl_array_iterator_next (gl_set_iterator_t *iterator, const void **eltp)
239 {
240 gl_set_t set = iterator->set;
241 if (iterator->count != set->count)
242 {
243 if (iterator->count != set->count + 1)
244
245 abort ();
246
247 iterator->count--;
248 iterator->p = (const void **) iterator->p - 1;
249 iterator->q = (const void **) iterator->q - 1;
250 }
251 if (iterator->p < iterator->q)
252 {
253 const void **p = (const void **) iterator->p;
254 *eltp = *p;
255 iterator->p = p + 1;
256 return true;
257 }
258 else
259 return false;
260 }
261
262 static void
263 gl_array_iterator_free (gl_set_iterator_t *iterator)
264 {
265 }
266
267
268 const struct gl_set_implementation gl_array_set_implementation =
269 {
270 gl_array_nx_create_empty,
271 gl_array_size,
272 gl_array_search,
273 gl_array_nx_add,
274 gl_array_remove,
275 gl_array_free,
276 gl_array_iterator,
277 gl_array_iterator_next,
278 gl_array_iterator_free
279 };