1 /* Ordered set data type implemented by an array.
2 Copyright (C) 2006-2007, 2009-2021 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 <https://www.gnu.org/licenses/>. */
17
18 #include <config.h>
19
20 /* Specification. */
21 #include "gl_array_oset.h"
22
23 #include <stdlib.h>
24
25 /* Checked size_t computations. */
26 #include "xsize.h"
27
28 /* -------------------------- gl_oset_t Data Type -------------------------- */
29
30 /* Concrete gl_oset_impl type, valid for this file only. */
31 struct gl_oset_impl
32 {
33 struct gl_oset_impl_base base;
34 /* An array of ALLOCATED elements, of which the first COUNT are used.
35 0 <= COUNT <= ALLOCATED. */
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 /* At each loop iteration, low < high; for indices < low the values
80 are smaller than ELT; for indices >= high the values are greater
81 than ELT. So, if the element occurs in the list, it is at
82 low <= position < high. */
83 do
84 {
85 size_t mid = low + (high - low) / 2; /* low <= mid < high */
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 /* cmp == 0 */
96 /* We have an element equal to ELT at index MID. */
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 /* Searches the least element in the ordered set that compares greater or equal
111 to the given THRESHOLD. The representation of the THRESHOLD is defined
112 by the THRESHOLD_FN.
113 Returns the position at which it was found, or gl_list_size (SET) if not
114 found. */
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 /* At each loop iteration, low < high; for indices < low the values are
128 smaller than THRESHOLD; for indices >= high the values are nonexistent.
129 So, if an element >= THRESHOLD occurs in the list, it is at
130 low <= position < high. */
131 do
132 {
133 size_t mid = low + (high - low) / 2; /* low <= mid < high */
134
135 if (! threshold_fn (set->elements[mid], threshold))
136 low = mid + 1;
137 else
138 {
139 /* We have an element >= THRESHOLD at index MID. But we need the
140 minimal such index. */
141 high = mid;
142 /* At each loop iteration, low <= high and
143 compar (set->elements[high], threshold) >= 0,
144 and we know that the first occurrence of the element is at
145 low <= position <= high. */
146 while (low < high)
147 {
148 size_t mid2 = low + (high - low) / 2; /* low <= mid2 < high */
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 /* Ensure that set->allocated > set->count.
181 Return 0 upon success, -1 upon out-of-memory. */
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 /* Overflow, would lead to out of memory. */
194 return -1;
195 memory = (const void **) realloc (set->elements, memory_size);
196 if (memory == NULL)
197 /* Out of memory. */
198 return -1;
199 set->elements = memory;
200 set->allocated = new_allocated;
201 return 0;
202 }
203
204 /* Add the given element ELT at the given position,
205 0 <= position <= gl_oset_size (set).
206 Return 1 upon success, -1 upon out-of-memory. */
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 /* Remove the element at the given position,
226 0 <= position < gl_oset_size (set). */
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 /* At each loop iteration, low < high; for indices < low the values
254 are smaller than ELT; for indices >= high the values are greater
255 than ELT. So, if the element occurs in the list, it is at
256 low <= position < high. */
257 do
258 {
259 size_t mid = low + (high - low) / 2; /* low <= mid < high */
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 /* cmp == 0 */
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 * /*elt*/, void * /*action_data*/),
293 void *action_data)
294 {
295 /* Like gl_array_remove, action (...), gl_array_nx_add, except that we don't
296 actually remove ELT. */
297 /* Remember the old position. */
298 size_t old_index = gl_array_indexof (set, elt);
299 /* Invoke ACTION. */
300 action (elt, action_data);
301 /* Determine the new position. */
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 /* cmp == 0 */
330 {
331 /* Two adjacent elements are the same. */
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 /* At each loop iteration, low <= high; for indices < low the values
343 are smaller than ELT; for indices >= high the values are greater
344 than ELT. So, if the element occurs in the list, it is at
345 low <= position < high. */
346 while (low < high)
347 {
348 size_t mid = low + (high - low) / 2; /* low <= mid < high */
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 /* cmp == 0 */
359 {
360 /* Two elements are the same. */
361 gl_array_remove_at (set, old_index);
362 return -1;
363 }
364 }
365
366 if (low < old_index)
367 {
368 /* Move the element from old_index to low. */
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 /* low > old_index. */
381 /* Move the element from old_index to low - 1. */
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 /* --------------------- gl_oset_iterator_t Data Type --------------------- */
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 /* Concurrent modifications were done on the set. */
473 abort ();
474 /* The last returned element was removed. */
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_oset_iterator_t *iterator _GL_ATTRIBUTE_MAYBE_UNUSED)
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 };