This source file includes following definitions.
- gl_array_nx_create_empty
- gl_array_size
- gl_array_indexof
- gl_array_search
- gl_array_indexof_atleast
- gl_array_search_atleast
- grow
- gl_array_nx_add_at
- gl_array_remove_at
- gl_array_nx_add
- gl_array_remove
- gl_array_update
- gl_array_free
- gl_array_iterator
- gl_array_iterator_atleast
- 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_oset.h"
22
23 #include <stdlib.h>
24
25
26 #include "xsize.h"
27
28
29
30
31 struct gl_oset_impl
32 {
33 struct gl_oset_impl_base base;
34
35
36 const void **elements;
37 size_t count;
38 size_t allocated;
39 };
40
41 static gl_oset_t
42 gl_array_nx_create_empty (gl_oset_implementation_t implementation,
43 gl_setelement_compar_fn compar_fn,
44 gl_setelement_dispose_fn dispose_fn)
45 {
46 struct gl_oset_impl *set =
47 (struct gl_oset_impl *) malloc (sizeof (struct gl_oset_impl));
48
49 if (set == NULL)
50 return NULL;
51
52 set->base.vtable = implementation;
53 set->base.compar_fn = compar_fn;
54 set->base.dispose_fn = dispose_fn;
55 set->elements = NULL;
56 set->count = 0;
57 set->allocated = 0;
58
59 return set;
60 }
61
62 static size_t _GL_ATTRIBUTE_PURE
63 gl_array_size (gl_oset_t set)
64 {
65 return set->count;
66 }
67
68 static size_t _GL_ATTRIBUTE_PURE
69 gl_array_indexof (gl_oset_t set, const void *elt)
70 {
71 size_t count = set->count;
72
73 if (count > 0)
74 {
75 gl_setelement_compar_fn compar = set->base.compar_fn;
76 size_t low = 0;
77 size_t high = count;
78
79
80
81
82
83 do
84 {
85 size_t mid = low + (high - low) / 2;
86 int cmp = (compar != NULL
87 ? compar (set->elements[mid], elt)
88 : (set->elements[mid] > elt ? 1 :
89 set->elements[mid] < elt ? -1 : 0));
90
91 if (cmp < 0)
92 low = mid + 1;
93 else if (cmp > 0)
94 high = mid;
95 else
96
97 return mid;
98 }
99 while (low < high);
100 }
101 return (size_t)(-1);
102 }
103
104 static bool _GL_ATTRIBUTE_PURE
105 gl_array_search (gl_oset_t set, const void *elt)
106 {
107 return gl_array_indexof (set, elt) != (size_t)(-1);
108 }
109
110
111
112
113
114
115 static size_t _GL_ATTRIBUTE_PURE
116 gl_array_indexof_atleast (gl_oset_t set,
117 gl_setelement_threshold_fn threshold_fn,
118 const void *threshold)
119 {
120 size_t count = set->count;
121
122 if (count > 0)
123 {
124 size_t low = 0;
125 size_t high = count;
126
127
128
129
130
131 do
132 {
133 size_t mid = low + (high - low) / 2;
134
135 if (! threshold_fn (set->elements[mid], threshold))
136 low = mid + 1;
137 else
138 {
139
140
141 high = mid;
142
143
144
145
146 while (low < high)
147 {
148 size_t mid2 = low + (high - low) / 2;
149
150 if (! threshold_fn (set->elements[mid2], threshold))
151 low = mid2 + 1;
152 else
153 high = mid2;
154 }
155 return low;
156 }
157 }
158 while (low < high);
159 }
160 return count;
161 }
162
163 static bool _GL_ATTRIBUTE_PURE
164 gl_array_search_atleast (gl_oset_t set,
165 gl_setelement_threshold_fn threshold_fn,
166 const void *threshold,
167 const void **eltp)
168 {
169 size_t index = gl_array_indexof_atleast (set, threshold_fn, threshold);
170
171 if (index == set->count)
172 return false;
173 else
174 {
175 *eltp = set->elements[index];
176 return true;
177 }
178 }
179
180
181
182 static int
183 grow (gl_oset_t set)
184 {
185 size_t new_allocated;
186 size_t memory_size;
187 const void **memory;
188
189 new_allocated = xtimes (set->allocated, 2);
190 new_allocated = xsum (new_allocated, 1);
191 memory_size = xtimes (new_allocated, sizeof (const void *));
192 if (size_overflow_p (memory_size))
193
194 return -1;
195 memory = (const void **) realloc (set->elements, memory_size);
196 if (memory == NULL)
197
198 return -1;
199 set->elements = memory;
200 set->allocated = new_allocated;
201 return 0;
202 }
203
204
205
206
207 static int
208 gl_array_nx_add_at (gl_oset_t set, size_t position, const void *elt)
209 {
210 size_t count = set->count;
211 const void **elements;
212 size_t i;
213
214 if (count == set->allocated)
215 if (grow (set) < 0)
216 return -1;
217 elements = set->elements;
218 for (i = count; i > position; i--)
219 elements[i] = elements[i - 1];
220 elements[position] = elt;
221 set->count = count + 1;
222 return 1;
223 }
224
225
226
227 static void
228 gl_array_remove_at (gl_oset_t set, size_t position)
229 {
230 size_t count = set->count;
231 const void **elements;
232 size_t i;
233
234 elements = set->elements;
235 if (set->base.dispose_fn != NULL)
236 set->base.dispose_fn (elements[position]);
237 for (i = position + 1; i < count; i++)
238 elements[i - 1] = elements[i];
239 set->count = count - 1;
240 }
241
242 static int
243 gl_array_nx_add (gl_oset_t set, const void *elt)
244 {
245 size_t count = set->count;
246 size_t low = 0;
247
248 if (count > 0)
249 {
250 gl_setelement_compar_fn compar = set->base.compar_fn;
251 size_t high = count;
252
253
254
255
256
257 do
258 {
259 size_t mid = low + (high - low) / 2;
260 int cmp = (compar != NULL
261 ? compar (set->elements[mid], elt)
262 : (set->elements[mid] > elt ? 1 :
263 set->elements[mid] < elt ? -1 : 0));
264
265 if (cmp < 0)
266 low = mid + 1;
267 else if (cmp > 0)
268 high = mid;
269 else
270 return false;
271 }
272 while (low < high);
273 }
274 return gl_array_nx_add_at (set, low, elt);
275 }
276
277 static bool
278 gl_array_remove (gl_oset_t set, const void *elt)
279 {
280 size_t index = gl_array_indexof (set, elt);
281 if (index != (size_t)(-1))
282 {
283 gl_array_remove_at (set, index);
284 return true;
285 }
286 else
287 return false;
288 }
289
290 static int
291 gl_array_update (gl_oset_t set, const void *elt,
292 void (*action) (const void * , void * ),
293 void *action_data)
294 {
295
296
297
298 size_t old_index = gl_array_indexof (set, elt);
299
300 action (elt, action_data);
301
302 if (old_index != (size_t)(-1))
303 {
304 size_t count = set->count;
305
306 if (count > 1)
307 {
308 gl_setelement_compar_fn compar = set->base.compar_fn;
309 size_t low;
310 size_t high;
311
312 if (old_index > 0)
313 {
314 size_t mid = old_index - 1;
315 int cmp = (compar != NULL
316 ? compar (set->elements[mid], elt)
317 : (set->elements[mid] > elt ? 1 :
318 set->elements[mid] < elt ? -1 : 0));
319 if (cmp < 0)
320 {
321 low = old_index + 1;
322 high = count;
323 }
324 else if (cmp > 0)
325 {
326 low = 0;
327 high = mid;
328 }
329 else
330 {
331
332 gl_array_remove_at (set, old_index);
333 return -1;
334 }
335 }
336 else
337 {
338 low = old_index + 1;
339 high = count;
340 }
341
342
343
344
345
346 while (low < high)
347 {
348 size_t mid = low + (high - low) / 2;
349 int cmp = (compar != NULL
350 ? compar (set->elements[mid], elt)
351 : (set->elements[mid] > elt ? 1 :
352 set->elements[mid] < elt ? -1 : 0));
353
354 if (cmp < 0)
355 low = mid + 1;
356 else if (cmp > 0)
357 high = mid;
358 else
359 {
360
361 gl_array_remove_at (set, old_index);
362 return -1;
363 }
364 }
365
366 if (low < old_index)
367 {
368
369 size_t new_index = low;
370 const void **elements = set->elements;
371 size_t i;
372
373 for (i = old_index; i > new_index; i--)
374 elements[i] = elements[i - 1];
375 elements[new_index] = elt;
376 return true;
377 }
378 else
379 {
380
381
382 size_t new_index = low - 1;
383
384 if (new_index > old_index)
385 {
386 const void **elements = set->elements;
387 size_t i;
388
389 for (i = old_index; i < new_index; i++)
390 elements[i] = elements[i + 1];
391 elements[new_index] = elt;
392 return true;
393 }
394 }
395 }
396 }
397 return false;
398 }
399
400 static void
401 gl_array_free (gl_oset_t set)
402 {
403 if (set->elements != NULL)
404 {
405 if (set->base.dispose_fn != NULL)
406 {
407 size_t count = set->count;
408
409 if (count > 0)
410 {
411 gl_setelement_dispose_fn dispose = set->base.dispose_fn;
412 const void **elements = set->elements;
413
414 do
415 dispose (*elements++);
416 while (--count > 0);
417 }
418 }
419 free (set->elements);
420 }
421 free (set);
422 }
423
424
425
426 static gl_oset_iterator_t _GL_ATTRIBUTE_PURE
427 gl_array_iterator (gl_oset_t set)
428 {
429 gl_oset_iterator_t result;
430
431 result.vtable = set->base.vtable;
432 result.set = set;
433 result.count = set->count;
434 result.p = set->elements + 0;
435 result.q = set->elements + set->count;
436 #if defined GCC_LINT || defined lint
437 result.i = 0;
438 result.j = 0;
439 #endif
440
441 return result;
442 }
443
444 static gl_oset_iterator_t _GL_ATTRIBUTE_PURE
445 gl_array_iterator_atleast (gl_oset_t set,
446 gl_setelement_threshold_fn threshold_fn,
447 const void *threshold)
448 {
449 size_t index = gl_array_indexof_atleast (set, threshold_fn, threshold);
450 gl_oset_iterator_t result;
451
452 result.vtable = set->base.vtable;
453 result.set = set;
454 result.count = set->count;
455 result.p = set->elements + index;
456 result.q = set->elements + set->count;
457 #if defined GCC_LINT || defined lint
458 result.i = 0;
459 result.j = 0;
460 #endif
461
462 return result;
463 }
464
465 static bool
466 gl_array_iterator_next (gl_oset_iterator_t *iterator, const void **eltp)
467 {
468 gl_oset_t set = iterator->set;
469 if (iterator->count != set->count)
470 {
471 if (iterator->count != set->count + 1)
472
473 abort ();
474
475 iterator->count--;
476 iterator->p = (const void **) iterator->p - 1;
477 iterator->q = (const void **) iterator->q - 1;
478 }
479 if (iterator->p < iterator->q)
480 {
481 const void **p = (const void **) iterator->p;
482 *eltp = *p;
483 iterator->p = p + 1;
484 return true;
485 }
486 else
487 return false;
488 }
489
490 static void
491 gl_array_iterator_free (_GL_ATTRIBUTE_MAYBE_UNUSED gl_oset_iterator_t *iterator)
492 {
493 }
494
495
496 const struct gl_oset_implementation gl_array_oset_implementation =
497 {
498 gl_array_nx_create_empty,
499 gl_array_size,
500 gl_array_search,
501 gl_array_search_atleast,
502 gl_array_nx_add,
503 gl_array_remove,
504 gl_array_update,
505 gl_array_free,
506 gl_array_iterator,
507 gl_array_iterator_atleast,
508 gl_array_iterator_next,
509 gl_array_iterator_free
510 };