1 /* Sequential list data type implemented by a circular array.
2 Copyright (C) 2006-2013 Free Software Foundation, Inc.
3 Written by Bruno Haible <bruno@clisp.org>, 2006.
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.
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.
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>. */
21 #include "gl_carray_list.h"
27 /* Checked size_t computations. */
31 # define uintptr_t unsigned long
34 /* -------------------------- gl_list_t Data Type -------------------------- */
36 /* Concrete gl_list_impl type, valid for this file only. */
39 struct gl_list_impl_base base;
40 /* An array of ALLOCATED elements, of which the elements
41 OFFSET, (OFFSET + 1) % ALLOCATED, ..., (OFFSET + COUNT - 1) % ALLOCATED
42 are used. 0 <= COUNT <= ALLOCATED. Either OFFSET = ALLOCATED = 0 or
43 0 <= OFFSET < ALLOCATED. */
44 const void **elements;
50 /* struct gl_list_node_impl doesn't exist here. The pointers are actually
52 #define INDEX_TO_NODE(index) (gl_list_node_t)(uintptr_t)(size_t)((index) + 1)
53 #define NODE_TO_INDEX(node) ((uintptr_t)(node) - 1)
56 gl_carray_nx_create_empty (gl_list_implementation_t implementation,
57 gl_listelement_equals_fn equals_fn,
58 gl_listelement_hashcode_fn hashcode_fn,
59 gl_listelement_dispose_fn dispose_fn,
60 bool allow_duplicates)
62 struct gl_list_impl *list =
63 (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
68 list->base.vtable = implementation;
69 list->base.equals_fn = equals_fn;
70 list->base.hashcode_fn = hashcode_fn;
71 list->base.dispose_fn = dispose_fn;
72 list->base.allow_duplicates = allow_duplicates;
73 list->elements = NULL;
82 gl_carray_nx_create (gl_list_implementation_t implementation,
83 gl_listelement_equals_fn equals_fn,
84 gl_listelement_hashcode_fn hashcode_fn,
85 gl_listelement_dispose_fn dispose_fn,
86 bool allow_duplicates,
87 size_t count, const void **contents)
89 struct gl_list_impl *list =
90 (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
95 list->base.vtable = implementation;
96 list->base.equals_fn = equals_fn;
97 list->base.hashcode_fn = hashcode_fn;
98 list->base.dispose_fn = dispose_fn;
99 list->base.allow_duplicates = allow_duplicates;
102 if (size_overflow_p (xtimes (count, sizeof (const void *))))
104 list->elements = (const void **) malloc (count * sizeof (const void *));
105 if (list->elements == NULL)
107 memcpy (list->elements, contents, count * sizeof (const void *));
110 list->elements = NULL;
113 list->allocated = count;
123 gl_carray_size (gl_list_t list)
129 gl_carray_node_value (gl_list_t list, gl_list_node_t node)
131 uintptr_t index = NODE_TO_INDEX (node);
134 if (!(index < list->count))
135 /* Invalid argument. */
137 i = list->offset + index;
138 if (i >= list->allocated)
139 i -= list->allocated;
140 return list->elements[i];
144 gl_carray_node_nx_set_value (gl_list_t list, gl_list_node_t node,
147 uintptr_t index = NODE_TO_INDEX (node);
150 if (!(index < list->count))
151 /* Invalid argument. */
153 i = list->offset + index;
154 if (i >= list->allocated)
155 i -= list->allocated;
156 list->elements[i] = elt;
160 static gl_list_node_t
161 gl_carray_next_node (gl_list_t list, gl_list_node_t node)
163 uintptr_t index = NODE_TO_INDEX (node);
164 if (!(index < list->count))
165 /* Invalid argument. */
168 if (index < list->count)
169 return INDEX_TO_NODE (index);
174 static gl_list_node_t
175 gl_carray_previous_node (gl_list_t list, gl_list_node_t node)
177 uintptr_t index = NODE_TO_INDEX (node);
178 if (!(index < list->count))
179 /* Invalid argument. */
182 return INDEX_TO_NODE (index - 1);
188 gl_carray_get_at (gl_list_t list, size_t position)
190 size_t count = list->count;
193 if (!(position < count))
194 /* Invalid argument. */
196 i = list->offset + position;
197 if (i >= list->allocated)
198 i -= list->allocated;
199 return list->elements[i];
202 static gl_list_node_t
203 gl_carray_nx_set_at (gl_list_t list, size_t position, const void *elt)
205 size_t count = list->count;
208 if (!(position < count))
209 /* Invalid argument. */
211 i = list->offset + position;
212 if (i >= list->allocated)
213 i -= list->allocated;
214 list->elements[i] = elt;
215 return INDEX_TO_NODE (position);
219 gl_carray_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
222 size_t count = list->count;
224 if (!(start_index <= end_index && end_index <= count))
225 /* Invalid arguments. */
228 if (start_index < end_index)
230 gl_listelement_equals_fn equals = list->base.equals_fn;
231 size_t allocated = list->allocated;
234 i_end = list->offset + end_index;
235 if (i_end >= allocated)
242 i = list->offset + start_index;
243 if (i >= allocated) /* can only happen if start_index > 0 */
248 if (equals (elt, list->elements[i]))
249 return (i >= list->offset ? i : i + allocated) - list->offset;
261 i = list->offset + start_index;
262 if (i >= allocated) /* can only happen if start_index > 0 */
267 if (elt == list->elements[i])
268 return (i >= list->offset ? i : i + allocated) - list->offset;
280 static gl_list_node_t
281 gl_carray_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
284 size_t index = gl_carray_indexof_from_to (list, start_index, end_index, elt);
285 return INDEX_TO_NODE (index);
288 /* Ensure that list->allocated > list->count.
289 Return 0 upon success, -1 upon out-of-memory. */
291 grow (gl_list_t list)
293 size_t new_allocated;
297 new_allocated = xtimes (list->allocated, 2);
298 new_allocated = xsum (new_allocated, 1);
299 memory_size = xtimes (new_allocated, sizeof (const void *));
300 if (size_overflow_p (memory_size))
301 /* Overflow, would lead to out of memory. */
303 if (list->offset > 0 && list->count > 0)
305 memory = (const void **) malloc (memory_size);
309 if (list->offset + list->count > list->allocated)
311 memcpy (memory, &list->elements[list->offset],
312 (list->allocated - list->offset) * sizeof (const void *));
313 memcpy (memory + (list->allocated - list->offset), list->elements,
314 (list->offset + list->count - list->allocated)
315 * sizeof (const void *));
319 memcpy (memory, &list->elements[list->offset],
320 list->count * sizeof (const void *));
321 if (list->elements != NULL)
322 free (list->elements);
326 memory = (const void **) realloc (list->elements, memory_size);
331 list->elements = memory;
333 list->allocated = new_allocated;
337 static gl_list_node_t
338 gl_carray_nx_add_first (gl_list_t list, const void *elt)
340 size_t count = list->count;
342 if (count == list->allocated)
345 list->offset = (list->offset == 0 ? list->allocated : list->offset) - 1;
346 list->elements[list->offset] = elt;
347 list->count = count + 1;
348 return INDEX_TO_NODE (0);
351 static gl_list_node_t
352 gl_carray_nx_add_last (gl_list_t list, const void *elt)
354 size_t count = list->count;
357 if (count == list->allocated)
360 i = list->offset + count;
361 if (i >= list->allocated)
362 i -= list->allocated;
363 list->elements[i] = elt;
364 list->count = count + 1;
365 return INDEX_TO_NODE (count);
368 static gl_list_node_t
369 gl_carray_nx_add_at (gl_list_t list, size_t position, const void *elt)
371 size_t count = list->count;
372 const void **elements;
374 if (!(position <= count))
375 /* Invalid argument. */
377 if (count == list->allocated)
380 elements = list->elements;
381 if (position <= (count / 2))
383 /* Shift at most count/2 elements to the left. */
386 list->offset = (list->offset == 0 ? list->allocated : list->offset) - 1;
388 i2 = list->offset + position;
389 if (i2 >= list->allocated)
391 /* Here we must have list->offset > 0, hence list->allocated > 0. */
392 size_t i1 = list->allocated - 1;
393 i2 -= list->allocated;
394 for (i = list->offset; i < i1; i++)
395 elements[i] = elements[i + 1];
396 elements[i1] = elements[0];
397 for (i = 0; i < i2; i++)
398 elements[i] = elements[i + 1];
402 for (i = list->offset; i < i2; i++)
403 elements[i] = elements[i + 1];
409 /* Shift at most (count+1)/2 elements to the right. */
412 i1 = list->offset + position;
413 i3 = list->offset + count;
414 if (i1 >= list->allocated)
416 i1 -= list->allocated;
417 i3 -= list->allocated;
418 for (i = i3; i > i1; i--)
419 elements[i] = elements[i - 1];
421 else if (i3 >= list->allocated)
423 /* Here we must have list->offset > 0, hence list->allocated > 0. */
424 size_t i2 = list->allocated - 1;
425 i3 -= list->allocated;
426 for (i = i3; i > 0; i--)
427 elements[i] = elements[i - 1];
428 elements[0] = elements[i2];
429 for (i = i2; i > i1; i--)
430 elements[i] = elements[i - 1];
434 for (i = i3; i > i1; i--)
435 elements[i] = elements[i - 1];
439 list->count = count + 1;
440 return INDEX_TO_NODE (position);
443 static gl_list_node_t
444 gl_carray_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
446 size_t count = list->count;
447 uintptr_t index = NODE_TO_INDEX (node);
449 if (!(index < count))
450 /* Invalid argument. */
452 return gl_carray_nx_add_at (list, index, elt);
455 static gl_list_node_t
456 gl_carray_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
458 size_t count = list->count;
459 uintptr_t index = NODE_TO_INDEX (node);
461 if (!(index < count))
462 /* Invalid argument. */
464 return gl_carray_nx_add_at (list, index + 1, elt);
468 gl_carray_remove_at (gl_list_t list, size_t position)
470 size_t count = list->count;
471 const void **elements;
473 if (!(position < count))
474 /* Invalid argument. */
476 /* Here we know count > 0. */
477 elements = list->elements;
478 if (position <= ((count - 1) / 2))
480 /* Shift at most (count-1)/2 elements to the right. */
484 i2 = list->offset + position;
485 if (i2 >= list->allocated)
487 /* Here we must have list->offset > 0, hence list->allocated > 0. */
488 size_t i1 = list->allocated - 1;
489 i2 -= list->allocated;
490 if (list->base.dispose_fn != NULL)
491 list->base.dispose_fn (elements[i2]);
492 for (i = i2; i > 0; i--)
493 elements[i] = elements[i - 1];
494 elements[0] = elements[i1];
495 for (i = i1; i > i0; i--)
496 elements[i] = elements[i - 1];
500 if (list->base.dispose_fn != NULL)
501 list->base.dispose_fn (elements[i2]);
502 for (i = i2; i > i0; i--)
503 elements[i] = elements[i - 1];
507 list->offset = (i0 == list->allocated ? 0 : i0);
511 /* Shift at most count/2 elements to the left. */
514 i1 = list->offset + position;
515 i3 = list->offset + count - 1;
516 if (i1 >= list->allocated)
518 i1 -= list->allocated;
519 i3 -= list->allocated;
520 if (list->base.dispose_fn != NULL)
521 list->base.dispose_fn (elements[i1]);
522 for (i = i1; i < i3; i++)
523 elements[i] = elements[i + 1];
525 else if (i3 >= list->allocated)
527 /* Here we must have list->offset > 0, hence list->allocated > 0. */
528 size_t i2 = list->allocated - 1;
529 i3 -= list->allocated;
530 if (list->base.dispose_fn != NULL)
531 list->base.dispose_fn (elements[i1]);
532 for (i = i1; i < i2; i++)
533 elements[i] = elements[i + 1];
534 elements[i2] = elements[0];
535 for (i = 0; i < i3; i++)
536 elements[i] = elements[i + 1];
540 if (list->base.dispose_fn != NULL)
541 list->base.dispose_fn (elements[i1]);
542 for (i = i1; i < i3; i++)
543 elements[i] = elements[i + 1];
546 list->count = count - 1;
551 gl_carray_remove_node (gl_list_t list, gl_list_node_t node)
553 size_t count = list->count;
554 uintptr_t index = NODE_TO_INDEX (node);
556 if (!(index < count))
557 /* Invalid argument. */
559 return gl_carray_remove_at (list, index);
563 gl_carray_remove (gl_list_t list, const void *elt)
565 size_t position = gl_carray_indexof_from_to (list, 0, list->count, elt);
566 if (position == (size_t)(-1))
569 return gl_carray_remove_at (list, position);
573 gl_carray_list_free (gl_list_t list)
575 if (list->elements != NULL)
577 if (list->base.dispose_fn != NULL)
579 size_t count = list->count;
583 gl_listelement_dispose_fn dispose = list->base.dispose_fn;
584 const void **elements = list->elements;
585 size_t i1 = list->offset;
586 size_t i3 = list->offset + count - 1;
588 if (i3 >= list->allocated)
590 /* Here we must have list->offset > 0, hence
591 list->allocated > 0. */
592 size_t i2 = list->allocated - 1;
595 i3 -= list->allocated;
596 for (i = i1; i <= i2; i++)
597 dispose (elements[i]);
598 for (i = 0; i <= i3; i++)
599 dispose (elements[i]);
605 for (i = i1; i <= i3; i++)
606 dispose (elements[i]);
610 free (list->elements);
615 /* --------------------- gl_list_iterator_t Data Type --------------------- */
617 static gl_list_iterator_t
618 gl_carray_iterator (gl_list_t list)
620 gl_list_iterator_t result;
622 result.vtable = list->base.vtable;
624 result.count = list->count;
626 result.j = list->count;
635 static gl_list_iterator_t
636 gl_carray_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
638 gl_list_iterator_t result;
640 if (!(start_index <= end_index && end_index <= list->count))
641 /* Invalid arguments. */
643 result.vtable = list->base.vtable;
645 result.count = list->count;
646 result.i = start_index;
647 result.j = end_index;
657 gl_carray_iterator_next (gl_list_iterator_t *iterator,
658 const void **eltp, gl_list_node_t *nodep)
660 gl_list_t list = iterator->list;
661 if (iterator->count != list->count)
663 if (iterator->count != list->count + 1)
664 /* Concurrent modifications were done on the list. */
666 /* The last returned element was removed. */
671 if (iterator->i < iterator->j)
673 size_t i = list->offset + iterator->i;
674 if (i >= list->allocated)
675 i -= list->allocated;
676 *eltp = list->elements[i];
678 *nodep = INDEX_TO_NODE (iterator->i);
687 gl_carray_iterator_free (gl_list_iterator_t *iterator)
691 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
694 gl_carray_sortedlist_indexof_from_to (gl_list_t list,
695 gl_listelement_compar_fn compar,
696 size_t low, size_t high,
699 if (!(low <= high && high <= list->count))
700 /* Invalid arguments. */
704 /* At each loop iteration, low < high; for indices < low the values
705 are smaller than ELT; for indices >= high the values are greater
706 than ELT. So, if the element occurs in the list, it is at
707 low <= position < high. */
710 size_t mid = low + (high - low) / 2; /* low <= mid < high */
714 i_mid = list->offset + mid;
715 if (i_mid >= list->allocated)
716 i_mid -= list->allocated;
718 cmp = compar (list->elements[i_mid], elt);
726 /* We have an element equal to ELT at index MID. But we need
727 the minimal such index. */
729 /* At each loop iteration, low <= high and
730 compar (list->elements[i_high], elt) == 0,
731 and we know that the first occurrence of the element is at
732 low <= position <= high. */
735 size_t mid2 = low + (high - low) / 2; /* low <= mid2 < high */
739 i_mid2 = list->offset + mid2;
740 if (i_mid2 >= list->allocated)
741 i_mid2 -= list->allocated;
743 cmp2 = compar (list->elements[i_mid2], elt);
748 /* The list was not sorted. */
761 /* Here low == high. */
767 gl_carray_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
770 return gl_carray_sortedlist_indexof_from_to (list, compar, 0, list->count,
774 static gl_list_node_t
775 gl_carray_sortedlist_search_from_to (gl_list_t list,
776 gl_listelement_compar_fn compar,
777 size_t low, size_t high,
781 gl_carray_sortedlist_indexof_from_to (list, compar, low, high, elt);
782 return INDEX_TO_NODE (index);
785 static gl_list_node_t
786 gl_carray_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
790 gl_carray_sortedlist_indexof_from_to (list, compar, 0, list->count, elt);
791 return INDEX_TO_NODE (index);
794 static gl_list_node_t
795 gl_carray_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar,
798 size_t count = list->count;
802 /* At each loop iteration, low <= high; for indices < low the values are
803 smaller than ELT; for indices >= high the values are greater than ELT. */
806 size_t mid = low + (high - low) / 2; /* low <= mid < high */
810 i_mid = list->offset + mid;
811 if (i_mid >= list->allocated)
812 i_mid -= list->allocated;
814 cmp = compar (list->elements[i_mid], elt);
826 return gl_carray_nx_add_at (list, low, elt);
830 gl_carray_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
833 size_t index = gl_carray_sortedlist_indexof (list, compar, elt);
834 if (index == (size_t)(-1))
837 return gl_carray_remove_at (list, index);
841 const struct gl_list_implementation gl_carray_list_implementation =
843 gl_carray_nx_create_empty,
846 gl_carray_node_value,
847 gl_carray_node_nx_set_value,
849 gl_carray_previous_node,
852 gl_carray_search_from_to,
853 gl_carray_indexof_from_to,
854 gl_carray_nx_add_first,
855 gl_carray_nx_add_last,
856 gl_carray_nx_add_before,
857 gl_carray_nx_add_after,
859 gl_carray_remove_node,
864 gl_carray_iterator_from_to,
865 gl_carray_iterator_next,
866 gl_carray_iterator_free,
867 gl_carray_sortedlist_search,
868 gl_carray_sortedlist_search_from_to,
869 gl_carray_sortedlist_indexof,
870 gl_carray_sortedlist_indexof_from_to,
871 gl_carray_sortedlist_nx_add,
872 gl_carray_sortedlist_remove