1 /* Sequential list data type implemented by a circular array.
2 Copyright (C) 2006-2008 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"
29 /* Checked size_t computations. */
33 # define uintptr_t unsigned long
36 /* -------------------------- gl_list_t Data Type -------------------------- */
38 /* Concrete gl_list_impl type, valid for this file only. */
41 struct gl_list_impl_base base;
42 /* An array of ALLOCATED elements, of which the elements
43 OFFSET, (OFFSET + 1) % ALLOCATED, ..., (OFFSET + COUNT - 1) % ALLOCATED
44 are used. 0 <= COUNT <= ALLOCATED. Either OFFSET = ALLOCATED = 0 or
45 0 <= OFFSET < ALLOCATED. */
46 const void **elements;
52 /* struct gl_list_node_impl doesn't exist here. The pointers are actually
54 #define INDEX_TO_NODE(index) (gl_list_node_t)(uintptr_t)(size_t)((index) + 1)
55 #define NODE_TO_INDEX(node) ((uintptr_t)(node) - 1)
58 gl_carray_create_empty (gl_list_implementation_t implementation,
59 gl_listelement_equals_fn equals_fn,
60 gl_listelement_hashcode_fn hashcode_fn,
61 gl_listelement_dispose_fn dispose_fn,
62 bool allow_duplicates)
64 struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
66 list->base.vtable = implementation;
67 list->base.equals_fn = equals_fn;
68 list->base.hashcode_fn = hashcode_fn;
69 list->base.dispose_fn = dispose_fn;
70 list->base.allow_duplicates = allow_duplicates;
71 list->elements = NULL;
80 gl_carray_create (gl_list_implementation_t implementation,
81 gl_listelement_equals_fn equals_fn,
82 gl_listelement_hashcode_fn hashcode_fn,
83 gl_listelement_dispose_fn dispose_fn,
84 bool allow_duplicates,
85 size_t count, const void **contents)
87 struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
89 list->base.vtable = implementation;
90 list->base.equals_fn = equals_fn;
91 list->base.hashcode_fn = hashcode_fn;
92 list->base.dispose_fn = dispose_fn;
93 list->base.allow_duplicates = allow_duplicates;
96 list->elements = XNMALLOC (count, const void *);
97 memcpy (list->elements, contents, count * sizeof (const void *));
100 list->elements = NULL;
103 list->allocated = count;
109 gl_carray_size (gl_list_t list)
115 gl_carray_node_value (gl_list_t list, gl_list_node_t node)
117 uintptr_t index = NODE_TO_INDEX (node);
120 if (!(index < list->count))
121 /* Invalid argument. */
123 i = list->offset + index;
124 if (i >= list->allocated)
125 i -= list->allocated;
126 return list->elements[i];
130 gl_carray_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt)
132 uintptr_t index = NODE_TO_INDEX (node);
135 if (!(index < list->count))
136 /* Invalid argument. */
138 i = list->offset + index;
139 if (i >= list->allocated)
140 i -= list->allocated;
141 list->elements[i] = elt;
144 static gl_list_node_t
145 gl_carray_next_node (gl_list_t list, gl_list_node_t node)
147 uintptr_t index = NODE_TO_INDEX (node);
148 if (!(index < list->count))
149 /* Invalid argument. */
152 if (index < list->count)
153 return INDEX_TO_NODE (index);
158 static gl_list_node_t
159 gl_carray_previous_node (gl_list_t list, gl_list_node_t node)
161 uintptr_t index = NODE_TO_INDEX (node);
162 if (!(index < list->count))
163 /* Invalid argument. */
166 return INDEX_TO_NODE (index - 1);
172 gl_carray_get_at (gl_list_t list, size_t position)
174 size_t count = list->count;
177 if (!(position < count))
178 /* Invalid argument. */
180 i = list->offset + position;
181 if (i >= list->allocated)
182 i -= list->allocated;
183 return list->elements[i];
186 static gl_list_node_t
187 gl_carray_set_at (gl_list_t list, size_t position, const void *elt)
189 size_t count = list->count;
192 if (!(position < count))
193 /* Invalid argument. */
195 i = list->offset + position;
196 if (i >= list->allocated)
197 i -= list->allocated;
198 list->elements[i] = elt;
199 return INDEX_TO_NODE (position);
203 gl_carray_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
206 size_t count = list->count;
208 if (!(start_index <= end_index && end_index <= count))
209 /* Invalid arguments. */
212 if (start_index < end_index)
214 gl_listelement_equals_fn equals = list->base.equals_fn;
215 size_t allocated = list->allocated;
218 i_end = list->offset + end_index;
219 if (i_end >= allocated)
226 i = list->offset + start_index;
227 if (i >= allocated) /* can only happen if start_index > 0 */
232 if (equals (elt, list->elements[i]))
233 return (i >= list->offset ? i : i + allocated) - list->offset;
245 i = list->offset + start_index;
246 if (i >= allocated) /* can only happen if start_index > 0 */
251 if (elt == list->elements[i])
252 return (i >= list->offset ? i : i + allocated) - list->offset;
264 static gl_list_node_t
265 gl_carray_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
268 size_t index = gl_carray_indexof_from_to (list, start_index, end_index, elt);
269 return INDEX_TO_NODE (index);
272 /* Ensure that list->allocated > list->count. */
274 grow (gl_list_t list)
276 size_t new_allocated;
280 new_allocated = xtimes (list->allocated, 2);
281 new_allocated = xsum (new_allocated, 1);
282 memory_size = xtimes (new_allocated, sizeof (const void *));
283 if (size_overflow_p (memory_size))
284 /* Overflow, would lead to out of memory. */
286 if (list->offset > 0 && list->count > 0)
288 memory = (const void **) xmalloc (memory_size);
292 if (list->offset + list->count > list->allocated)
294 memcpy (memory, &list->elements[list->offset],
295 (list->allocated - list->offset) * sizeof (const void *));
296 memcpy (memory + (list->allocated - list->offset), list->elements,
297 (list->offset + list->count - list->allocated)
298 * sizeof (const void *));
302 memcpy (memory, &list->elements[list->offset],
303 list->count * sizeof (const void *));
304 if (list->elements != NULL)
305 free (list->elements);
309 memory = (const void **) xrealloc (list->elements, memory_size);
314 list->elements = memory;
316 list->allocated = new_allocated;
319 static gl_list_node_t
320 gl_carray_add_first (gl_list_t list, const void *elt)
322 size_t count = list->count;
324 if (count == list->allocated)
326 list->offset = (list->offset == 0 ? list->allocated : list->offset) - 1;
327 list->elements[list->offset] = elt;
328 list->count = count + 1;
329 return INDEX_TO_NODE (0);
332 static gl_list_node_t
333 gl_carray_add_last (gl_list_t list, const void *elt)
335 size_t count = list->count;
338 if (count == list->allocated)
340 i = list->offset + count;
341 if (i >= list->allocated)
342 i -= list->allocated;
343 list->elements[i] = elt;
344 list->count = count + 1;
345 return INDEX_TO_NODE (count);
348 static gl_list_node_t
349 gl_carray_add_at (gl_list_t list, size_t position, const void *elt)
351 size_t count = list->count;
352 const void **elements;
354 if (!(position <= count))
355 /* Invalid argument. */
357 if (count == list->allocated)
359 elements = list->elements;
360 if (position <= (count / 2))
362 /* Shift at most count/2 elements to the left. */
365 list->offset = (list->offset == 0 ? list->allocated : list->offset) - 1;
367 i2 = list->offset + position;
368 if (i2 >= list->allocated)
370 /* Here we must have list->offset > 0, hence list->allocated > 0. */
371 size_t i1 = list->allocated - 1;
372 i2 -= list->allocated;
373 for (i = list->offset; i < i1; i++)
374 elements[i] = elements[i + 1];
375 elements[i1] = elements[0];
376 for (i = 0; i < i2; i++)
377 elements[i] = elements[i + 1];
381 for (i = list->offset; i < i2; i++)
382 elements[i] = elements[i + 1];
388 /* Shift at most (count+1)/2 elements to the right. */
391 i1 = list->offset + position;
392 i3 = list->offset + count;
393 if (i1 >= list->allocated)
395 i1 -= list->allocated;
396 i3 -= list->allocated;
397 for (i = i3; i > i1; i--)
398 elements[i] = elements[i - 1];
400 else if (i3 >= list->allocated)
402 /* Here we must have list->offset > 0, hence list->allocated > 0. */
403 size_t i2 = list->allocated - 1;
404 i3 -= list->allocated;
405 for (i = i3; i > 0; i--)
406 elements[i] = elements[i - 1];
407 elements[0] = elements[i2];
408 for (i = i2; i > i1; i--)
409 elements[i] = elements[i - 1];
413 for (i = i3; i > i1; i--)
414 elements[i] = elements[i - 1];
418 list->count = count + 1;
419 return INDEX_TO_NODE (position);
422 static gl_list_node_t
423 gl_carray_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
425 size_t count = list->count;
426 uintptr_t index = NODE_TO_INDEX (node);
428 if (!(index < count))
429 /* Invalid argument. */
431 return gl_carray_add_at (list, index, elt);
434 static gl_list_node_t
435 gl_carray_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
437 size_t count = list->count;
438 uintptr_t index = NODE_TO_INDEX (node);
440 if (!(index < count))
441 /* Invalid argument. */
443 return gl_carray_add_at (list, index + 1, elt);
447 gl_carray_remove_at (gl_list_t list, size_t position)
449 size_t count = list->count;
450 const void **elements;
452 if (!(position < count))
453 /* Invalid argument. */
455 /* Here we know count > 0. */
456 elements = list->elements;
457 if (position <= ((count - 1) / 2))
459 /* Shift at most (count-1)/2 elements to the right. */
463 i2 = list->offset + position;
464 if (i2 >= list->allocated)
466 /* Here we must have list->offset > 0, hence list->allocated > 0. */
467 size_t i1 = list->allocated - 1;
468 i2 -= list->allocated;
469 if (list->base.dispose_fn != NULL)
470 list->base.dispose_fn (elements[i2]);
471 for (i = i2; i > 0; i--)
472 elements[i] = elements[i - 1];
473 elements[0] = elements[i1];
474 for (i = i1; i > i0; i--)
475 elements[i] = elements[i - 1];
479 if (list->base.dispose_fn != NULL)
480 list->base.dispose_fn (elements[i2]);
481 for (i = i2; i > i0; i--)
482 elements[i] = elements[i - 1];
486 list->offset = (i0 == list->allocated ? 0 : i0);
490 /* Shift at most count/2 elements to the left. */
493 i1 = list->offset + position;
494 i3 = list->offset + count - 1;
495 if (i1 >= list->allocated)
497 i1 -= list->allocated;
498 i3 -= list->allocated;
499 if (list->base.dispose_fn != NULL)
500 list->base.dispose_fn (elements[i1]);
501 for (i = i1; i < i3; i++)
502 elements[i] = elements[i + 1];
504 else if (i3 >= list->allocated)
506 /* Here we must have list->offset > 0, hence list->allocated > 0. */
507 size_t i2 = list->allocated - 1;
508 i3 -= list->allocated;
509 if (list->base.dispose_fn != NULL)
510 list->base.dispose_fn (elements[i1]);
511 for (i = i1; i < i2; i++)
512 elements[i] = elements[i + 1];
513 elements[i2] = elements[0];
514 for (i = 0; i < i3; i++)
515 elements[i] = elements[i + 1];
519 if (list->base.dispose_fn != NULL)
520 list->base.dispose_fn (elements[i1]);
521 for (i = i1; i < i3; i++)
522 elements[i] = elements[i + 1];
525 list->count = count - 1;
530 gl_carray_remove_node (gl_list_t list, gl_list_node_t node)
532 size_t count = list->count;
533 uintptr_t index = NODE_TO_INDEX (node);
535 if (!(index < count))
536 /* Invalid argument. */
538 return gl_carray_remove_at (list, index);
542 gl_carray_remove (gl_list_t list, const void *elt)
544 size_t position = gl_carray_indexof_from_to (list, 0, list->count, elt);
545 if (position == (size_t)(-1))
548 return gl_carray_remove_at (list, position);
552 gl_carray_list_free (gl_list_t list)
554 if (list->elements != NULL)
556 if (list->base.dispose_fn != NULL)
558 size_t count = list->count;
562 gl_listelement_dispose_fn dispose = list->base.dispose_fn;
563 const void **elements = list->elements;
564 size_t i1 = list->offset;
565 size_t i3 = list->offset + count - 1;
567 if (i3 >= list->allocated)
569 /* Here we must have list->offset > 0, hence
570 list->allocated > 0. */
571 size_t i2 = list->allocated - 1;
574 i3 -= list->allocated;
575 for (i = i1; i <= i2; i++)
576 dispose (elements[i]);
577 for (i = 0; i <= i3; i++)
578 dispose (elements[i]);
584 for (i = i1; i <= i3; i++)
585 dispose (elements[i]);
589 free (list->elements);
594 /* --------------------- gl_list_iterator_t Data Type --------------------- */
596 static gl_list_iterator_t
597 gl_carray_iterator (gl_list_t list)
599 gl_list_iterator_t result;
601 result.vtable = list->base.vtable;
603 result.count = list->count;
605 result.j = list->count;
614 static gl_list_iterator_t
615 gl_carray_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
617 gl_list_iterator_t result;
619 if (!(start_index <= end_index && end_index <= list->count))
620 /* Invalid arguments. */
622 result.vtable = list->base.vtable;
624 result.count = list->count;
625 result.i = start_index;
626 result.j = end_index;
636 gl_carray_iterator_next (gl_list_iterator_t *iterator,
637 const void **eltp, gl_list_node_t *nodep)
639 gl_list_t list = iterator->list;
640 if (iterator->count != list->count)
642 if (iterator->count != list->count + 1)
643 /* Concurrent modifications were done on the list. */
645 /* The last returned element was removed. */
650 if (iterator->i < iterator->j)
652 size_t i = list->offset + iterator->i;
653 if (i >= list->allocated)
654 i -= list->allocated;
655 *eltp = list->elements[i];
657 *nodep = INDEX_TO_NODE (iterator->i);
666 gl_carray_iterator_free (gl_list_iterator_t *iterator)
670 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
673 gl_carray_sortedlist_indexof_from_to (gl_list_t list,
674 gl_listelement_compar_fn compar,
675 size_t low, size_t high,
678 if (!(low <= high && high <= list->count))
679 /* Invalid arguments. */
683 /* At each loop iteration, low < high; for indices < low the values
684 are smaller than ELT; for indices >= high the values are greater
685 than ELT. So, if the element occurs in the list, it is at
686 low <= position < high. */
689 size_t mid = low + (high - low) / 2; /* low <= mid < high */
693 i_mid = list->offset + mid;
694 if (i_mid >= list->allocated)
695 i_mid -= list->allocated;
697 cmp = compar (list->elements[i_mid], elt);
705 /* We have an element equal to ELT at index MID. But we need
706 the minimal such index. */
708 /* At each loop iteration, low <= high and
709 compar (list->elements[i_high], elt) == 0,
710 and we know that the first occurrence of the element is at
711 low <= position <= high. */
714 size_t mid2 = low + (high - low) / 2; /* low <= mid2 < high */
718 i_mid2 = list->offset + mid2;
719 if (i_mid2 >= list->allocated)
720 i_mid2 -= list->allocated;
722 cmp2 = compar (list->elements[i_mid2], elt);
727 /* The list was not sorted. */
740 /* Here low == high. */
746 gl_carray_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
749 return gl_carray_sortedlist_indexof_from_to (list, compar, 0, list->count,
753 static gl_list_node_t
754 gl_carray_sortedlist_search_from_to (gl_list_t list,
755 gl_listelement_compar_fn compar,
756 size_t low, size_t high,
760 gl_carray_sortedlist_indexof_from_to (list, compar, low, high, elt);
761 return INDEX_TO_NODE (index);
764 static gl_list_node_t
765 gl_carray_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
769 gl_carray_sortedlist_indexof_from_to (list, compar, 0, list->count, elt);
770 return INDEX_TO_NODE (index);
773 static gl_list_node_t
774 gl_carray_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
777 size_t count = list->count;
781 /* At each loop iteration, low <= high; for indices < low the values are
782 smaller than ELT; for indices >= high the values are greater than ELT. */
785 size_t mid = low + (high - low) / 2; /* low <= mid < high */
789 i_mid = list->offset + mid;
790 if (i_mid >= list->allocated)
791 i_mid -= list->allocated;
793 cmp = compar (list->elements[i_mid], elt);
805 return gl_carray_add_at (list, low, elt);
809 gl_carray_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
812 size_t index = gl_carray_sortedlist_indexof (list, compar, elt);
813 if (index == (size_t)(-1))
816 return gl_carray_remove_at (list, index);
820 const struct gl_list_implementation gl_carray_list_implementation =
822 gl_carray_create_empty,
825 gl_carray_node_value,
826 gl_carray_node_set_value,
828 gl_carray_previous_node,
831 gl_carray_search_from_to,
832 gl_carray_indexof_from_to,
835 gl_carray_add_before,
838 gl_carray_remove_node,
843 gl_carray_iterator_from_to,
844 gl_carray_iterator_next,
845 gl_carray_iterator_free,
846 gl_carray_sortedlist_search,
847 gl_carray_sortedlist_search_from_to,
848 gl_carray_sortedlist_indexof,
849 gl_carray_sortedlist_indexof_from_to,
850 gl_carray_sortedlist_add,
851 gl_carray_sortedlist_remove