1 | /* Sequential list data type implemented by an array. |
2 | Copyright (C) 2006-2019 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_list.h" |
22 | |
23 | #include <stdint.h> |
24 | #include <stdlib.h> |
25 | /* Get memcpy. */ |
26 | #include <string.h> |
27 | |
28 | /* Checked size_t computations. */ |
29 | #include "xsize.h" |
30 | |
31 | /* -------------------------- gl_list_t Data Type -------------------------- */ |
32 | |
33 | /* Concrete gl_list_impl type, valid for this file only. */ |
34 | struct gl_list_impl |
35 | { |
36 | struct gl_list_impl_base base; |
37 | /* An array of ALLOCATED elements, of which the first COUNT are used. |
38 | 0 <= COUNT <= ALLOCATED. */ |
39 | const void **elements; |
40 | size_t count; |
41 | size_t allocated; |
42 | }; |
43 | |
44 | /* struct gl_list_node_impl doesn't exist here. The pointers are actually |
45 | indices + 1. */ |
46 | #define INDEX_TO_NODE(index) (gl_list_node_t)(uintptr_t)(size_t)((index) + 1) |
47 | #define NODE_TO_INDEX(node) ((uintptr_t)(node) - 1) |
48 | |
49 | static gl_list_t |
50 | gl_array_nx_create_empty (gl_list_implementation_t implementation, |
51 | gl_listelement_equals_fn equals_fn, |
52 | gl_listelement_hashcode_fn hashcode_fn, |
53 | gl_listelement_dispose_fn dispose_fn, |
54 | bool allow_duplicates) |
55 | { |
56 | struct gl_list_impl *list = |
57 | (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl)); |
58 | |
59 | if (list == NULL) |
60 | return NULL; |
61 | |
62 | list->base.vtable = implementation; |
63 | list->base.equals_fn = equals_fn; |
64 | list->base.hashcode_fn = hashcode_fn; |
65 | list->base.dispose_fn = dispose_fn; |
66 | list->base.allow_duplicates = allow_duplicates; |
67 | list->elements = NULL; |
68 | list->count = 0; |
69 | list->allocated = 0; |
70 | |
71 | return list; |
72 | } |
73 | |
74 | static gl_list_t |
75 | gl_array_nx_create (gl_list_implementation_t implementation, |
76 | gl_listelement_equals_fn equals_fn, |
77 | gl_listelement_hashcode_fn hashcode_fn, |
78 | gl_listelement_dispose_fn dispose_fn, |
79 | bool allow_duplicates, |
80 | size_t count, const void **contents) |
81 | { |
82 | struct gl_list_impl *list = |
83 | (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl)); |
84 | |
85 | if (list == NULL) |
86 | return NULL; |
87 | |
88 | list->base.vtable = implementation; |
89 | list->base.equals_fn = equals_fn; |
90 | list->base.hashcode_fn = hashcode_fn; |
91 | list->base.dispose_fn = dispose_fn; |
92 | list->base.allow_duplicates = allow_duplicates; |
93 | if (count > 0) |
94 | { |
95 | if (size_overflow_p (xtimes (count, sizeof (const void *)))) |
96 | goto fail; |
97 | list->elements = (const void **) malloc (count * sizeof (const void *)); |
98 | if (list->elements == NULL) |
99 | goto fail; |
100 | memcpy (list->elements, contents, count * sizeof (const void *)); |
101 | } |
102 | else |
103 | list->elements = NULL; |
104 | list->count = count; |
105 | list->allocated = count; |
106 | |
107 | return list; |
108 | |
109 | fail: |
110 | free (list); |
111 | return NULL; |
112 | } |
113 | |
114 | static size_t |
115 | gl_array_size (gl_list_t list) |
116 | { |
117 | return list->count; |
118 | } |
119 | |
120 | static const void * _GL_ATTRIBUTE_PURE |
121 | gl_array_node_value (gl_list_t list, gl_list_node_t node) |
122 | { |
123 | uintptr_t index = NODE_TO_INDEX (node); |
124 | if (!(index < list->count)) |
125 | /* Invalid argument. */ |
126 | abort (); |
127 | return list->elements[index]; |
128 | } |
129 | |
130 | static int |
131 | gl_array_node_nx_set_value (gl_list_t list, gl_list_node_t node, |
132 | const void *elt) |
133 | { |
134 | uintptr_t index = NODE_TO_INDEX (node); |
135 | if (!(index < list->count)) |
136 | /* Invalid argument. */ |
137 | abort (); |
138 | list->elements[index] = elt; |
139 | return 0; |
140 | } |
141 | |
142 | static gl_list_node_t _GL_ATTRIBUTE_PURE |
143 | gl_array_next_node (gl_list_t list, gl_list_node_t node) |
144 | { |
145 | uintptr_t index = NODE_TO_INDEX (node); |
146 | if (!(index < list->count)) |
147 | /* Invalid argument. */ |
148 | abort (); |
149 | index++; |
150 | if (index < list->count) |
151 | return INDEX_TO_NODE (index); |
152 | else |
153 | return NULL; |
154 | } |
155 | |
156 | static gl_list_node_t _GL_ATTRIBUTE_PURE |
157 | gl_array_previous_node (gl_list_t list, gl_list_node_t node) |
158 | { |
159 | uintptr_t index = NODE_TO_INDEX (node); |
160 | if (!(index < list->count)) |
161 | /* Invalid argument. */ |
162 | abort (); |
163 | if (index > 0) |
164 | return INDEX_TO_NODE (index - 1); |
165 | else |
166 | return NULL; |
167 | } |
168 | |
169 | static const void * _GL_ATTRIBUTE_PURE |
170 | gl_array_get_at (gl_list_t list, size_t position) |
171 | { |
172 | size_t count = list->count; |
173 | |
174 | if (!(position < count)) |
175 | /* Invalid argument. */ |
176 | abort (); |
177 | return list->elements[position]; |
178 | } |
179 | |
180 | static gl_list_node_t |
181 | gl_array_nx_set_at (gl_list_t list, size_t position, const void *elt) |
182 | { |
183 | size_t count = list->count; |
184 | |
185 | if (!(position < count)) |
186 | /* Invalid argument. */ |
187 | abort (); |
188 | list->elements[position] = elt; |
189 | return INDEX_TO_NODE (position); |
190 | } |
191 | |
192 | static size_t |
193 | gl_array_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index, |
194 | const void *elt) |
195 | { |
196 | size_t count = list->count; |
197 | |
198 | if (!(start_index <= end_index && end_index <= count)) |
199 | /* Invalid arguments. */ |
200 | abort (); |
201 | |
202 | if (start_index < end_index) |
203 | { |
204 | gl_listelement_equals_fn equals = list->base.equals_fn; |
205 | if (equals != NULL) |
206 | { |
207 | size_t i; |
208 | |
209 | for (i = start_index;;) |
210 | { |
211 | if (equals (elt, list->elements[i])) |
212 | return i; |
213 | i++; |
214 | if (i == end_index) |
215 | break; |
216 | } |
217 | } |
218 | else |
219 | { |
220 | size_t i; |
221 | |
222 | for (i = start_index;;) |
223 | { |
224 | if (elt == list->elements[i]) |
225 | return i; |
226 | i++; |
227 | if (i == end_index) |
228 | break; |
229 | } |
230 | } |
231 | } |
232 | return (size_t)(-1); |
233 | } |
234 | |
235 | static gl_list_node_t |
236 | gl_array_search_from_to (gl_list_t list, size_t start_index, size_t end_index, |
237 | const void *elt) |
238 | { |
239 | size_t index = gl_array_indexof_from_to (list, start_index, end_index, elt); |
240 | return INDEX_TO_NODE (index); |
241 | } |
242 | |
243 | /* Ensure that list->allocated > list->count. |
244 | Return 0 upon success, -1 upon out-of-memory. */ |
245 | static int |
246 | grow (gl_list_t list) |
247 | { |
248 | size_t new_allocated; |
249 | size_t memory_size; |
250 | const void **memory; |
251 | |
252 | new_allocated = xtimes (list->allocated, 2); |
253 | new_allocated = xsum (new_allocated, 1); |
254 | memory_size = xtimes (new_allocated, sizeof (const void *)); |
255 | if (size_overflow_p (memory_size)) |
256 | /* Overflow, would lead to out of memory. */ |
257 | return -1; |
258 | memory = (const void **) realloc (list->elements, memory_size); |
259 | if (memory == NULL) |
260 | /* Out of memory. */ |
261 | return -1; |
262 | list->elements = memory; |
263 | list->allocated = new_allocated; |
264 | return 0; |
265 | } |
266 | |
267 | static gl_list_node_t |
268 | gl_array_nx_add_first (gl_list_t list, const void *elt) |
269 | { |
270 | size_t count = list->count; |
271 | const void **elements; |
272 | size_t i; |
273 | |
274 | if (count == list->allocated) |
275 | if (grow (list) < 0) |
276 | return NULL; |
277 | elements = list->elements; |
278 | for (i = count; i > 0; i--) |
279 | elements[i] = elements[i - 1]; |
280 | elements[0] = elt; |
281 | list->count = count + 1; |
282 | return INDEX_TO_NODE (0); |
283 | } |
284 | |
285 | static gl_list_node_t |
286 | gl_array_nx_add_last (gl_list_t list, const void *elt) |
287 | { |
288 | size_t count = list->count; |
289 | |
290 | if (count == list->allocated) |
291 | if (grow (list) < 0) |
292 | return NULL; |
293 | list->elements[count] = elt; |
294 | list->count = count + 1; |
295 | return INDEX_TO_NODE (count); |
296 | } |
297 | |
298 | static gl_list_node_t |
299 | gl_array_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt) |
300 | { |
301 | size_t count = list->count; |
302 | uintptr_t index = NODE_TO_INDEX (node); |
303 | size_t position; |
304 | const void **elements; |
305 | size_t i; |
306 | |
307 | if (!(index < count)) |
308 | /* Invalid argument. */ |
309 | abort (); |
310 | position = index; |
311 | if (count == list->allocated) |
312 | if (grow (list) < 0) |
313 | return NULL; |
314 | elements = list->elements; |
315 | for (i = count; i > position; i--) |
316 | elements[i] = elements[i - 1]; |
317 | elements[position] = elt; |
318 | list->count = count + 1; |
319 | return INDEX_TO_NODE (position); |
320 | } |
321 | |
322 | static gl_list_node_t |
323 | gl_array_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt) |
324 | { |
325 | size_t count = list->count; |
326 | uintptr_t index = NODE_TO_INDEX (node); |
327 | size_t position; |
328 | const void **elements; |
329 | size_t i; |
330 | |
331 | if (!(index < count)) |
332 | /* Invalid argument. */ |
333 | abort (); |
334 | position = index + 1; |
335 | if (count == list->allocated) |
336 | if (grow (list) < 0) |
337 | return NULL; |
338 | elements = list->elements; |
339 | for (i = count; i > position; i--) |
340 | elements[i] = elements[i - 1]; |
341 | elements[position] = elt; |
342 | list->count = count + 1; |
343 | return INDEX_TO_NODE (position); |
344 | } |
345 | |
346 | static gl_list_node_t |
347 | gl_array_nx_add_at (gl_list_t list, size_t position, const void *elt) |
348 | { |
349 | size_t count = list->count; |
350 | const void **elements; |
351 | size_t i; |
352 | |
353 | if (!(position <= count)) |
354 | /* Invalid argument. */ |
355 | abort (); |
356 | if (count == list->allocated) |
357 | if (grow (list) < 0) |
358 | return NULL; |
359 | elements = list->elements; |
360 | for (i = count; i > position; i--) |
361 | elements[i] = elements[i - 1]; |
362 | elements[position] = elt; |
363 | list->count = count + 1; |
364 | return INDEX_TO_NODE (position); |
365 | } |
366 | |
367 | static bool |
368 | gl_array_remove_node (gl_list_t list, gl_list_node_t node) |
369 | { |
370 | size_t count = list->count; |
371 | uintptr_t index = NODE_TO_INDEX (node); |
372 | size_t position; |
373 | const void **elements; |
374 | size_t i; |
375 | |
376 | if (!(index < count)) |
377 | /* Invalid argument. */ |
378 | abort (); |
379 | position = index; |
380 | elements = list->elements; |
381 | if (list->base.dispose_fn != NULL) |
382 | list->base.dispose_fn (elements[position]); |
383 | for (i = position + 1; i < count; i++) |
384 | elements[i - 1] = elements[i]; |
385 | list->count = count - 1; |
386 | return true; |
387 | } |
388 | |
389 | static bool |
390 | gl_array_remove_at (gl_list_t list, size_t position) |
391 | { |
392 | size_t count = list->count; |
393 | const void **elements; |
394 | size_t i; |
395 | |
396 | if (!(position < count)) |
397 | /* Invalid argument. */ |
398 | abort (); |
399 | elements = list->elements; |
400 | if (list->base.dispose_fn != NULL) |
401 | list->base.dispose_fn (elements[position]); |
402 | for (i = position + 1; i < count; i++) |
403 | elements[i - 1] = elements[i]; |
404 | list->count = count - 1; |
405 | return true; |
406 | } |
407 | |
408 | static bool |
409 | gl_array_remove (gl_list_t list, const void *elt) |
410 | { |
411 | size_t position = gl_array_indexof_from_to (list, 0, list->count, elt); |
412 | if (position == (size_t)(-1)) |
413 | return false; |
414 | else |
415 | return gl_array_remove_at (list, position); |
416 | } |
417 | |
418 | static void |
419 | gl_array_list_free (gl_list_t list) |
420 | { |
421 | if (list->elements != NULL) |
422 | { |
423 | if (list->base.dispose_fn != NULL) |
424 | { |
425 | size_t count = list->count; |
426 | |
427 | if (count > 0) |
428 | { |
429 | gl_listelement_dispose_fn dispose = list->base.dispose_fn; |
430 | const void **elements = list->elements; |
431 | |
432 | do |
433 | dispose (*elements++); |
434 | while (--count > 0); |
435 | } |
436 | } |
437 | free (list->elements); |
438 | } |
439 | free (list); |
440 | } |
441 | |
442 | /* --------------------- gl_list_iterator_t Data Type --------------------- */ |
443 | |
444 | static gl_list_iterator_t |
445 | gl_array_iterator (gl_list_t list) |
446 | { |
447 | gl_list_iterator_t result; |
448 | |
449 | result.vtable = list->base.vtable; |
450 | result.list = list; |
451 | result.count = list->count; |
452 | result.p = list->elements + 0; |
453 | result.q = list->elements + list->count; |
454 | #if defined GCC_LINT || defined lint |
455 | result.i = 0; |
456 | result.j = 0; |
457 | #endif |
458 | |
459 | return result; |
460 | } |
461 | |
462 | static gl_list_iterator_t |
463 | gl_array_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index) |
464 | { |
465 | gl_list_iterator_t result; |
466 | |
467 | if (!(start_index <= end_index && end_index <= list->count)) |
468 | /* Invalid arguments. */ |
469 | abort (); |
470 | result.vtable = list->base.vtable; |
471 | result.list = list; |
472 | result.count = list->count; |
473 | result.p = list->elements + start_index; |
474 | result.q = list->elements + end_index; |
475 | #if defined GCC_LINT || defined lint |
476 | result.i = 0; |
477 | result.j = 0; |
478 | #endif |
479 | |
480 | return result; |
481 | } |
482 | |
483 | static bool |
484 | gl_array_iterator_next (gl_list_iterator_t *iterator, |
485 | const void **eltp, gl_list_node_t *nodep) |
486 | { |
487 | gl_list_t list = iterator->list; |
488 | if (iterator->count != list->count) |
489 | { |
490 | if (iterator->count != list->count + 1) |
491 | /* Concurrent modifications were done on the list. */ |
492 | abort (); |
493 | /* The last returned element was removed. */ |
494 | iterator->count--; |
495 | iterator->p = (const void **) iterator->p - 1; |
496 | iterator->q = (const void **) iterator->q - 1; |
497 | } |
498 | if (iterator->p < iterator->q) |
499 | { |
500 | const void **p = (const void **) iterator->p; |
501 | *eltp = *p; |
502 | if (nodep != NULL) |
503 | *nodep = INDEX_TO_NODE (p - list->elements); |
504 | iterator->p = p + 1; |
505 | return true; |
506 | } |
507 | else |
508 | return false; |
509 | } |
510 | |
511 | static void |
512 | gl_array_iterator_free (gl_list_iterator_t *iterator _GL_UNUSED) |
513 | { |
514 | } |
515 | |
516 | /* ---------------------- Sorted gl_list_t Data Type ---------------------- */ |
517 | |
518 | static size_t |
519 | gl_array_sortedlist_indexof_from_to (gl_list_t list, |
520 | gl_listelement_compar_fn compar, |
521 | size_t low, size_t high, |
522 | const void *elt) |
523 | { |
524 | if (!(low <= high && high <= list->count)) |
525 | /* Invalid arguments. */ |
526 | abort (); |
527 | if (low < high) |
528 | { |
529 | /* At each loop iteration, low < high; for indices < low the values |
530 | are smaller than ELT; for indices >= high the values are greater |
531 | than ELT. So, if the element occurs in the list, it is at |
532 | low <= position < high. */ |
533 | do |
534 | { |
535 | size_t mid = low + (high - low) / 2; /* low <= mid < high */ |
536 | int cmp = compar (list->elements[mid], elt); |
537 | |
538 | if (cmp < 0) |
539 | low = mid + 1; |
540 | else if (cmp > 0) |
541 | high = mid; |
542 | else /* cmp == 0 */ |
543 | { |
544 | /* We have an element equal to ELT at index MID. But we need |
545 | the minimal such index. */ |
546 | high = mid; |
547 | /* At each loop iteration, low <= high and |
548 | compar (list->elements[high], elt) == 0, |
549 | and we know that the first occurrence of the element is at |
550 | low <= position <= high. */ |
551 | while (low < high) |
552 | { |
553 | size_t mid2 = low + (high - low) / 2; /* low <= mid2 < high */ |
554 | int cmp2 = compar (list->elements[mid2], elt); |
555 | |
556 | if (cmp2 < 0) |
557 | low = mid2 + 1; |
558 | else if (cmp2 > 0) |
559 | /* The list was not sorted. */ |
560 | abort (); |
561 | else /* cmp2 == 0 */ |
562 | { |
563 | if (mid2 == low) |
564 | break; |
565 | high = mid2 - 1; |
566 | } |
567 | } |
568 | return low; |
569 | } |
570 | } |
571 | while (low < high); |
572 | /* Here low == high. */ |
573 | } |
574 | return (size_t)(-1); |
575 | } |
576 | |
577 | static size_t |
578 | gl_array_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, |
579 | const void *elt) |
580 | { |
581 | return gl_array_sortedlist_indexof_from_to (list, compar, 0, list->count, |
582 | elt); |
583 | } |
584 | |
585 | static gl_list_node_t |
586 | gl_array_sortedlist_search_from_to (gl_list_t list, |
587 | gl_listelement_compar_fn compar, |
588 | size_t low, size_t high, |
589 | const void *elt) |
590 | { |
591 | size_t index = |
592 | gl_array_sortedlist_indexof_from_to (list, compar, low, high, elt); |
593 | return INDEX_TO_NODE (index); |
594 | } |
595 | |
596 | static gl_list_node_t |
597 | gl_array_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, |
598 | const void *elt) |
599 | { |
600 | size_t index = |
601 | gl_array_sortedlist_indexof_from_to (list, compar, 0, list->count, elt); |
602 | return INDEX_TO_NODE (index); |
603 | } |
604 | |
605 | static gl_list_node_t |
606 | gl_array_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar, |
607 | const void *elt) |
608 | { |
609 | size_t count = list->count; |
610 | size_t low = 0; |
611 | size_t high = count; |
612 | |
613 | /* At each loop iteration, low <= high; for indices < low the values are |
614 | smaller than ELT; for indices >= high the values are greater than ELT. */ |
615 | while (low < high) |
616 | { |
617 | size_t mid = low + (high - low) / 2; /* low <= mid < high */ |
618 | int cmp = compar (list->elements[mid], elt); |
619 | |
620 | if (cmp < 0) |
621 | low = mid + 1; |
622 | else if (cmp > 0) |
623 | high = mid; |
624 | else /* cmp == 0 */ |
625 | { |
626 | low = mid; |
627 | break; |
628 | } |
629 | } |
630 | return gl_array_nx_add_at (list, low, elt); |
631 | } |
632 | |
633 | static bool |
634 | gl_array_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar, |
635 | const void *elt) |
636 | { |
637 | size_t index = gl_array_sortedlist_indexof (list, compar, elt); |
638 | if (index == (size_t)(-1)) |
639 | return false; |
640 | else |
641 | return gl_array_remove_at (list, index); |
642 | } |
643 | |
644 | |
645 | const struct gl_list_implementation gl_array_list_implementation = |
646 | { |
647 | gl_array_nx_create_empty, |
648 | gl_array_nx_create, |
649 | gl_array_size, |
650 | gl_array_node_value, |
651 | gl_array_node_nx_set_value, |
652 | gl_array_next_node, |
653 | gl_array_previous_node, |
654 | gl_array_get_at, |
655 | gl_array_nx_set_at, |
656 | gl_array_search_from_to, |
657 | gl_array_indexof_from_to, |
658 | gl_array_nx_add_first, |
659 | gl_array_nx_add_last, |
660 | gl_array_nx_add_before, |
661 | gl_array_nx_add_after, |
662 | gl_array_nx_add_at, |
663 | gl_array_remove_node, |
664 | gl_array_remove_at, |
665 | gl_array_remove, |
666 | gl_array_list_free, |
667 | gl_array_iterator, |
668 | gl_array_iterator_from_to, |
669 | gl_array_iterator_next, |
670 | gl_array_iterator_free, |
671 | gl_array_sortedlist_search, |
672 | gl_array_sortedlist_search_from_to, |
673 | gl_array_sortedlist_indexof, |
674 | gl_array_sortedlist_indexof_from_to, |
675 | gl_array_sortedlist_nx_add, |
676 | gl_array_sortedlist_remove |
677 | }; |
678 | |