1 /* Sequential list data type implemented by a circular array.
2 Copyright (C) 2006-2007 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];
129 static gl_list_node_t
130 gl_carray_next_node (gl_list_t list, gl_list_node_t node)
132 uintptr_t index = NODE_TO_INDEX (node);
133 if (!(index < list->count))
134 /* Invalid argument. */
137 if (index < list->count)
138 return INDEX_TO_NODE (index);
143 static gl_list_node_t
144 gl_carray_previous_node (gl_list_t list, gl_list_node_t node)
146 uintptr_t index = NODE_TO_INDEX (node);
147 if (!(index < list->count))
148 /* Invalid argument. */
151 return INDEX_TO_NODE (index - 1);
157 gl_carray_get_at (gl_list_t list, size_t position)
159 size_t count = list->count;
162 if (!(position < count))
163 /* Invalid argument. */
165 i = list->offset + position;
166 if (i >= list->allocated)
167 i -= list->allocated;
168 return list->elements[i];
171 static gl_list_node_t
172 gl_carray_set_at (gl_list_t list, size_t position, const void *elt)
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 list->elements[i] = elt;
184 return INDEX_TO_NODE (position);
188 gl_carray_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
191 size_t count = list->count;
193 if (!(start_index <= end_index && end_index <= count))
194 /* Invalid arguments. */
197 if (start_index < end_index)
199 gl_listelement_equals_fn equals = list->base.equals_fn;
200 size_t allocated = list->allocated;
203 i_end = list->offset + end_index;
204 if (i_end >= allocated)
211 i = list->offset + start_index;
212 if (i >= allocated) /* can only happen if start_index > 0 */
217 if (equals (elt, list->elements[i]))
218 return (i >= list->offset ? i : i + allocated) - list->offset;
230 i = list->offset + start_index;
231 if (i >= allocated) /* can only happen if start_index > 0 */
236 if (elt == list->elements[i])
237 return (i >= list->offset ? i : i + allocated) - list->offset;
249 static gl_list_node_t
250 gl_carray_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
253 size_t index = gl_carray_indexof_from_to (list, start_index, end_index, elt);
254 return INDEX_TO_NODE (index);
257 /* Ensure that list->allocated > list->count. */
259 grow (gl_list_t list)
261 size_t new_allocated;
265 new_allocated = xtimes (list->allocated, 2);
266 new_allocated = xsum (new_allocated, 1);
267 memory_size = xtimes (new_allocated, sizeof (const void *));
268 if (size_overflow_p (memory_size))
269 /* Overflow, would lead to out of memory. */
271 if (list->offset > 0 && list->count > 0)
273 memory = (const void **) xmalloc (memory_size);
277 if (list->offset + list->count > list->allocated)
279 memcpy (memory, &list->elements[list->offset],
280 (list->allocated - list->offset) * sizeof (const void *));
281 memcpy (memory + (list->allocated - list->offset), list->elements,
282 (list->offset + list->count - list->allocated)
283 * sizeof (const void *));
287 memcpy (memory, &list->elements[list->offset],
288 list->count * sizeof (const void *));
289 if (list->elements != NULL)
290 free (list->elements);
294 memory = (const void **) xrealloc (list->elements, memory_size);
299 list->elements = memory;
301 list->allocated = new_allocated;
304 static gl_list_node_t
305 gl_carray_add_first (gl_list_t list, const void *elt)
307 size_t count = list->count;
309 if (count == list->allocated)
311 list->offset = (list->offset == 0 ? list->allocated : list->offset) - 1;
312 list->elements[list->offset] = elt;
313 list->count = count + 1;
314 return INDEX_TO_NODE (0);
317 static gl_list_node_t
318 gl_carray_add_last (gl_list_t list, const void *elt)
320 size_t count = list->count;
323 if (count == list->allocated)
325 i = list->offset + count;
326 if (i >= list->allocated)
327 i -= list->allocated;
328 list->elements[i] = elt;
329 list->count = count + 1;
330 return INDEX_TO_NODE (count);
333 static gl_list_node_t
334 gl_carray_add_at (gl_list_t list, size_t position, const void *elt)
336 size_t count = list->count;
337 const void **elements;
339 if (!(position <= count))
340 /* Invalid argument. */
342 if (count == list->allocated)
344 elements = list->elements;
345 if (position <= (count / 2))
347 /* Shift at most count/2 elements to the left. */
350 list->offset = (list->offset == 0 ? list->allocated : list->offset) - 1;
352 i2 = list->offset + position;
353 if (i2 >= list->allocated)
355 /* Here we must have list->offset > 0, hence list->allocated > 0. */
356 size_t i1 = list->allocated - 1;
357 i2 -= list->allocated;
358 for (i = list->offset; i < i1; i++)
359 elements[i] = elements[i + 1];
360 elements[i1] = elements[0];
361 for (i = 0; i < i2; i++)
362 elements[i] = elements[i + 1];
366 for (i = list->offset; i < i2; i++)
367 elements[i] = elements[i + 1];
373 /* Shift at most (count+1)/2 elements to the right. */
376 i1 = list->offset + position;
377 i3 = list->offset + count;
378 if (i1 >= list->allocated)
380 i1 -= list->allocated;
381 i3 -= list->allocated;
382 for (i = i3; i > i1; i--)
383 elements[i] = elements[i - 1];
385 else if (i3 >= list->allocated)
387 /* Here we must have list->offset > 0, hence list->allocated > 0. */
388 size_t i2 = list->allocated - 1;
389 i3 -= list->allocated;
390 for (i = i3; i > 0; i--)
391 elements[i] = elements[i - 1];
392 elements[0] = elements[i2];
393 for (i = i2; i > i1; i--)
394 elements[i] = elements[i - 1];
398 for (i = i3; i > i1; i--)
399 elements[i] = elements[i - 1];
403 list->count = count + 1;
404 return INDEX_TO_NODE (position);
407 static gl_list_node_t
408 gl_carray_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
410 size_t count = list->count;
411 uintptr_t index = NODE_TO_INDEX (node);
413 if (!(index < count))
414 /* Invalid argument. */
416 return gl_carray_add_at (list, index, elt);
419 static gl_list_node_t
420 gl_carray_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
422 size_t count = list->count;
423 uintptr_t index = NODE_TO_INDEX (node);
425 if (!(index < count))
426 /* Invalid argument. */
428 return gl_carray_add_at (list, index + 1, elt);
432 gl_carray_remove_at (gl_list_t list, size_t position)
434 size_t count = list->count;
435 const void **elements;
437 if (!(position < count))
438 /* Invalid argument. */
440 /* Here we know count > 0. */
441 elements = list->elements;
442 if (position <= ((count - 1) / 2))
444 /* Shift at most (count-1)/2 elements to the right. */
448 i2 = list->offset + position;
449 if (i2 >= list->allocated)
451 /* Here we must have list->offset > 0, hence list->allocated > 0. */
452 size_t i1 = list->allocated - 1;
453 i2 -= list->allocated;
454 if (list->base.dispose_fn != NULL)
455 list->base.dispose_fn (elements[i2]);
456 for (i = i2; i > 0; i--)
457 elements[i] = elements[i - 1];
458 elements[0] = elements[i1];
459 for (i = i1; i > i0; i--)
460 elements[i] = elements[i - 1];
464 if (list->base.dispose_fn != NULL)
465 list->base.dispose_fn (elements[i2]);
466 for (i = i2; i > i0; i--)
467 elements[i] = elements[i - 1];
471 list->offset = (i0 == list->allocated ? 0 : i0);
475 /* Shift at most count/2 elements to the left. */
478 i1 = list->offset + position;
479 i3 = list->offset + count - 1;
480 if (i1 >= list->allocated)
482 i1 -= list->allocated;
483 i3 -= list->allocated;
484 if (list->base.dispose_fn != NULL)
485 list->base.dispose_fn (elements[i1]);
486 for (i = i1; i < i3; i++)
487 elements[i] = elements[i + 1];
489 else if (i3 >= list->allocated)
491 /* Here we must have list->offset > 0, hence list->allocated > 0. */
492 size_t i2 = list->allocated - 1;
493 i3 -= list->allocated;
494 if (list->base.dispose_fn != NULL)
495 list->base.dispose_fn (elements[i1]);
496 for (i = i1; i < i2; i++)
497 elements[i] = elements[i + 1];
498 elements[i2] = elements[0];
499 for (i = 0; i < i3; i++)
500 elements[i] = elements[i + 1];
504 if (list->base.dispose_fn != NULL)
505 list->base.dispose_fn (elements[i1]);
506 for (i = i1; i < i3; i++)
507 elements[i] = elements[i + 1];
510 list->count = count - 1;
515 gl_carray_remove_node (gl_list_t list, gl_list_node_t node)
517 size_t count = list->count;
518 uintptr_t index = NODE_TO_INDEX (node);
520 if (!(index < count))
521 /* Invalid argument. */
523 return gl_carray_remove_at (list, index);
527 gl_carray_remove (gl_list_t list, const void *elt)
529 size_t position = gl_carray_indexof_from_to (list, 0, list->count, elt);
530 if (position == (size_t)(-1))
533 return gl_carray_remove_at (list, position);
537 gl_carray_list_free (gl_list_t list)
539 if (list->elements != NULL)
541 if (list->base.dispose_fn != NULL)
543 size_t count = list->count;
547 gl_listelement_dispose_fn dispose = list->base.dispose_fn;
548 const void **elements = list->elements;
549 size_t i1 = list->offset;
550 size_t i3 = list->offset + count - 1;
552 if (i3 >= list->allocated)
554 /* Here we must have list->offset > 0, hence
555 list->allocated > 0. */
556 size_t i2 = list->allocated - 1;
559 i3 -= list->allocated;
560 for (i = i1; i <= i2; i++)
561 dispose (elements[i]);
562 for (i = 0; i <= i3; i++)
563 dispose (elements[i]);
569 for (i = i1; i <= i3; i++)
570 dispose (elements[i]);
574 free (list->elements);
579 /* --------------------- gl_list_iterator_t Data Type --------------------- */
581 static gl_list_iterator_t
582 gl_carray_iterator (gl_list_t list)
584 gl_list_iterator_t result;
586 result.vtable = list->base.vtable;
588 result.count = list->count;
590 result.j = list->count;
599 static gl_list_iterator_t
600 gl_carray_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
602 gl_list_iterator_t result;
604 if (!(start_index <= end_index && end_index <= list->count))
605 /* Invalid arguments. */
607 result.vtable = list->base.vtable;
609 result.count = list->count;
610 result.i = start_index;
611 result.j = end_index;
621 gl_carray_iterator_next (gl_list_iterator_t *iterator,
622 const void **eltp, gl_list_node_t *nodep)
624 gl_list_t list = iterator->list;
625 if (iterator->count != list->count)
627 if (iterator->count != list->count + 1)
628 /* Concurrent modifications were done on the list. */
630 /* The last returned element was removed. */
635 if (iterator->i < iterator->j)
637 size_t i = list->offset + iterator->i;
638 if (i >= list->allocated)
639 i -= list->allocated;
640 *eltp = list->elements[i];
642 *nodep = INDEX_TO_NODE (iterator->i);
651 gl_carray_iterator_free (gl_list_iterator_t *iterator)
655 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
658 gl_carray_sortedlist_indexof_from_to (gl_list_t list,
659 gl_listelement_compar_fn compar,
660 size_t low, size_t high,
663 if (!(low <= high && high <= list->count))
664 /* Invalid arguments. */
668 /* At each loop iteration, low < high; for indices < low the values
669 are smaller than ELT; for indices >= high the values are greater
670 than ELT. So, if the element occurs in the list, it is at
671 low <= position < high. */
674 size_t mid = low + (high - low) / 2; /* low <= mid < high */
678 i_mid = list->offset + mid;
679 if (i_mid >= list->allocated)
680 i_mid -= list->allocated;
682 cmp = compar (list->elements[i_mid], elt);
690 /* We have an element equal to ELT at index MID. But we need
691 the minimal such index. */
693 /* At each loop iteration, low <= high and
694 compar (list->elements[i_high], elt) == 0,
695 and we know that the first occurrence of the element is at
696 low <= position <= high. */
699 size_t mid2 = low + (high - low) / 2; /* low <= mid2 < high */
703 i_mid2 = list->offset + mid2;
704 if (i_mid2 >= list->allocated)
705 i_mid2 -= list->allocated;
707 cmp2 = compar (list->elements[i_mid2], elt);
712 /* The list was not sorted. */
725 /* Here low == high. */
731 gl_carray_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
734 return gl_carray_sortedlist_indexof_from_to (list, compar, 0, list->count,
738 static gl_list_node_t
739 gl_carray_sortedlist_search_from_to (gl_list_t list,
740 gl_listelement_compar_fn compar,
741 size_t low, size_t high,
745 gl_carray_sortedlist_indexof_from_to (list, compar, low, high, elt);
746 return INDEX_TO_NODE (index);
749 static gl_list_node_t
750 gl_carray_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
754 gl_carray_sortedlist_indexof_from_to (list, compar, 0, list->count, elt);
755 return INDEX_TO_NODE (index);
758 static gl_list_node_t
759 gl_carray_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
762 size_t count = list->count;
766 /* At each loop iteration, low <= high; for indices < low the values are
767 smaller than ELT; for indices >= high the values are greater than ELT. */
770 size_t mid = low + (high - low) / 2; /* low <= mid < high */
774 i_mid = list->offset + mid;
775 if (i_mid >= list->allocated)
776 i_mid -= list->allocated;
778 cmp = compar (list->elements[i_mid], elt);
790 return gl_carray_add_at (list, low, elt);
794 gl_carray_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
797 size_t index = gl_carray_sortedlist_indexof (list, compar, elt);
798 if (index == (size_t)(-1))
801 return gl_carray_remove_at (list, index);
805 const struct gl_list_implementation gl_carray_list_implementation =
807 gl_carray_create_empty,
810 gl_carray_node_value,
812 gl_carray_previous_node,
815 gl_carray_search_from_to,
816 gl_carray_indexof_from_to,
819 gl_carray_add_before,
822 gl_carray_remove_node,
827 gl_carray_iterator_from_to,
828 gl_carray_iterator_next,
829 gl_carray_iterator_free,
830 gl_carray_sortedlist_search,
831 gl_carray_sortedlist_search_from_to,
832 gl_carray_sortedlist_indexof,
833 gl_carray_sortedlist_indexof_from_to,
834 gl_carray_sortedlist_add,
835 gl_carray_sortedlist_remove