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 2, or (at your option)
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, write to the Free Software Foundation,
17 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
22 #include "gl_carray_list.h"
30 /* Checked size_t computations. */
34 # define uintptr_t unsigned long
37 /* -------------------------- gl_list_t Data Type -------------------------- */
39 /* Concrete gl_list_impl type, valid for this file only. */
42 struct gl_list_impl_base base;
43 /* An array of ALLOCATED elements, of which the elements
44 OFFSET, (OFFSET + 1) % ALLOCATED, ..., (OFFSET + COUNT - 1) % ALLOCATED
45 are used. 0 <= COUNT <= ALLOCATED. Either OFFSET = ALLOCATED = 0 or
46 0 <= OFFSET < ALLOCATED. */
47 const void **elements;
53 /* struct gl_list_node_impl doesn't exist here. The pointers are actually
55 #define INDEX_TO_NODE(index) (gl_list_node_t)(uintptr_t)(size_t)((index) + 1)
56 #define NODE_TO_INDEX(node) ((uintptr_t)(node) - 1)
59 gl_carray_create_empty (gl_list_implementation_t implementation,
60 gl_listelement_equals_fn equals_fn,
61 gl_listelement_hashcode_fn hashcode_fn,
62 gl_listelement_dispose_fn dispose_fn,
63 bool allow_duplicates)
65 struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
67 list->base.vtable = implementation;
68 list->base.equals_fn = equals_fn;
69 list->base.hashcode_fn = hashcode_fn;
70 list->base.dispose_fn = dispose_fn;
71 list->base.allow_duplicates = allow_duplicates;
72 list->elements = NULL;
81 gl_carray_create (gl_list_implementation_t implementation,
82 gl_listelement_equals_fn equals_fn,
83 gl_listelement_hashcode_fn hashcode_fn,
84 gl_listelement_dispose_fn dispose_fn,
85 bool allow_duplicates,
86 size_t count, const void **contents)
88 struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
90 list->base.vtable = implementation;
91 list->base.equals_fn = equals_fn;
92 list->base.hashcode_fn = hashcode_fn;
93 list->base.dispose_fn = dispose_fn;
94 list->base.allow_duplicates = allow_duplicates;
97 list->elements = XNMALLOC (count, const void *);
98 memcpy (list->elements, contents, count * sizeof (const void *));
101 list->elements = NULL;
104 list->allocated = count;
110 gl_carray_size (gl_list_t list)
116 gl_carray_node_value (gl_list_t list, gl_list_node_t node)
118 uintptr_t index = NODE_TO_INDEX (node);
121 if (!(index < list->count))
122 /* Invalid argument. */
124 i = list->offset + index;
125 if (i >= list->allocated)
126 i -= list->allocated;
127 return list->elements[i];
130 static gl_list_node_t
131 gl_carray_next_node (gl_list_t list, gl_list_node_t node)
133 uintptr_t index = NODE_TO_INDEX (node);
134 if (!(index < list->count))
135 /* Invalid argument. */
138 if (index < list->count)
139 return INDEX_TO_NODE (index);
144 static gl_list_node_t
145 gl_carray_previous_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 return INDEX_TO_NODE (index - 1);
158 gl_carray_get_at (gl_list_t list, size_t position)
160 size_t count = list->count;
163 if (!(position < count))
164 /* Invalid argument. */
166 i = list->offset + position;
167 if (i >= list->allocated)
168 i -= list->allocated;
169 return list->elements[i];
172 static gl_list_node_t
173 gl_carray_set_at (gl_list_t list, size_t position, const void *elt)
175 size_t count = list->count;
178 if (!(position < count))
179 /* Invalid argument. */
181 i = list->offset + position;
182 if (i >= list->allocated)
183 i -= list->allocated;
184 list->elements[i] = elt;
185 return INDEX_TO_NODE (position);
189 gl_carray_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
192 size_t count = list->count;
194 if (!(start_index <= end_index && end_index <= count))
195 /* Invalid arguments. */
198 if (start_index < end_index)
200 gl_listelement_equals_fn equals = list->base.equals_fn;
201 size_t allocated = list->allocated;
204 i_end = list->offset + end_index;
205 if (i_end >= allocated)
212 i = list->offset + start_index;
213 if (i >= allocated) /* can only happen if start_index > 0 */
218 if (equals (elt, list->elements[i]))
219 return (i >= list->offset ? i : i + allocated) - list->offset;
231 i = list->offset + start_index;
232 if (i >= allocated) /* can only happen if start_index > 0 */
237 if (elt == list->elements[i])
238 return (i >= list->offset ? i : i + allocated) - list->offset;
250 static gl_list_node_t
251 gl_carray_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
254 size_t index = gl_carray_indexof_from_to (list, start_index, end_index, elt);
255 return INDEX_TO_NODE (index);
258 /* Ensure that list->allocated > list->count. */
260 grow (gl_list_t list)
262 size_t new_allocated;
266 new_allocated = xtimes (list->allocated, 2);
267 new_allocated = xsum (new_allocated, 1);
268 memory_size = xtimes (new_allocated, sizeof (const void *));
269 if (size_overflow_p (memory_size))
270 /* Overflow, would lead to out of memory. */
272 if (list->offset > 0 && list->count > 0)
274 memory = (const void **) xmalloc (memory_size);
278 if (list->offset + list->count > list->allocated)
280 memcpy (memory, &list->elements[list->offset],
281 (list->allocated - list->offset) * sizeof (const void *));
282 memcpy (memory + (list->allocated - list->offset), list->elements,
283 (list->offset + list->count - list->allocated)
284 * sizeof (const void *));
288 memcpy (memory, &list->elements[list->offset],
289 list->count * sizeof (const void *));
290 if (list->elements != NULL)
291 free (list->elements);
295 memory = (const void **) xrealloc (list->elements, memory_size);
300 list->elements = memory;
302 list->allocated = new_allocated;
305 static gl_list_node_t
306 gl_carray_add_first (gl_list_t list, const void *elt)
308 size_t count = list->count;
310 if (count == list->allocated)
312 list->offset = (list->offset == 0 ? list->allocated : list->offset) - 1;
313 list->elements[list->offset] = elt;
314 list->count = count + 1;
315 return INDEX_TO_NODE (0);
318 static gl_list_node_t
319 gl_carray_add_last (gl_list_t list, const void *elt)
321 size_t count = list->count;
324 if (count == list->allocated)
326 i = list->offset + count;
327 if (i >= list->allocated)
328 i -= list->allocated;
329 list->elements[i] = elt;
330 list->count = count + 1;
331 return INDEX_TO_NODE (count);
334 static gl_list_node_t
335 gl_carray_add_at (gl_list_t list, size_t position, const void *elt)
337 size_t count = list->count;
338 const void **elements;
340 if (!(position <= count))
341 /* Invalid argument. */
343 if (count == list->allocated)
345 elements = list->elements;
346 if (position <= (count / 2))
348 /* Shift at most count/2 elements to the left. */
351 list->offset = (list->offset == 0 ? list->allocated : list->offset) - 1;
353 i2 = list->offset + position;
354 if (i2 >= list->allocated)
356 /* Here we must have list->offset > 0, hence list->allocated > 0. */
357 size_t i1 = list->allocated - 1;
358 i2 -= list->allocated;
359 for (i = list->offset; i < i1; i++)
360 elements[i] = elements[i + 1];
361 elements[i1] = elements[0];
362 for (i = 0; i < i2; i++)
363 elements[i] = elements[i + 1];
367 for (i = list->offset; i < i2; i++)
368 elements[i] = elements[i + 1];
374 /* Shift at most (count+1)/2 elements to the right. */
377 i1 = list->offset + position;
378 i3 = list->offset + count;
379 if (i1 >= list->allocated)
381 i1 -= list->allocated;
382 i3 -= list->allocated;
383 for (i = i3; i > i1; i--)
384 elements[i] = elements[i - 1];
386 else if (i3 >= list->allocated)
388 /* Here we must have list->offset > 0, hence list->allocated > 0. */
389 size_t i2 = list->allocated - 1;
390 i3 -= list->allocated;
391 for (i = i3; i > 0; i--)
392 elements[i] = elements[i - 1];
393 elements[0] = elements[i2];
394 for (i = i2; i > i1; i--)
395 elements[i] = elements[i - 1];
399 for (i = i3; i > i1; i--)
400 elements[i] = elements[i - 1];
404 list->count = count + 1;
405 return INDEX_TO_NODE (position);
408 static gl_list_node_t
409 gl_carray_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
411 size_t count = list->count;
412 uintptr_t index = NODE_TO_INDEX (node);
414 if (!(index < count))
415 /* Invalid argument. */
417 return gl_carray_add_at (list, index, elt);
420 static gl_list_node_t
421 gl_carray_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
423 size_t count = list->count;
424 uintptr_t index = NODE_TO_INDEX (node);
426 if (!(index < count))
427 /* Invalid argument. */
429 return gl_carray_add_at (list, index + 1, elt);
433 gl_carray_remove_at (gl_list_t list, size_t position)
435 size_t count = list->count;
436 const void **elements;
438 if (!(position < count))
439 /* Invalid argument. */
441 /* Here we know count > 0. */
442 elements = list->elements;
443 if (position <= ((count - 1) / 2))
445 /* Shift at most (count-1)/2 elements to the right. */
449 i2 = list->offset + position;
450 if (i2 >= list->allocated)
452 /* Here we must have list->offset > 0, hence list->allocated > 0. */
453 size_t i1 = list->allocated - 1;
454 i2 -= list->allocated;
455 if (list->base.dispose_fn != NULL)
456 list->base.dispose_fn (elements[i2]);
457 for (i = i2; i > 0; i--)
458 elements[i] = elements[i - 1];
459 elements[0] = elements[i1];
460 for (i = i1; i > i0; i--)
461 elements[i] = elements[i - 1];
465 if (list->base.dispose_fn != NULL)
466 list->base.dispose_fn (elements[i2]);
467 for (i = i2; i > i0; i--)
468 elements[i] = elements[i - 1];
472 list->offset = (i0 == list->allocated ? 0 : i0);
476 /* Shift at most count/2 elements to the left. */
479 i1 = list->offset + position;
480 i3 = list->offset + count - 1;
481 if (i1 >= list->allocated)
483 i1 -= list->allocated;
484 i3 -= list->allocated;
485 if (list->base.dispose_fn != NULL)
486 list->base.dispose_fn (elements[i1]);
487 for (i = i1; i < i3; i++)
488 elements[i] = elements[i + 1];
490 else if (i3 >= list->allocated)
492 /* Here we must have list->offset > 0, hence list->allocated > 0. */
493 size_t i2 = list->allocated - 1;
494 i3 -= list->allocated;
495 if (list->base.dispose_fn != NULL)
496 list->base.dispose_fn (elements[i1]);
497 for (i = i1; i < i2; i++)
498 elements[i] = elements[i + 1];
499 elements[i2] = elements[0];
500 for (i = 0; i < i3; i++)
501 elements[i] = elements[i + 1];
505 if (list->base.dispose_fn != NULL)
506 list->base.dispose_fn (elements[i1]);
507 for (i = i1; i < i3; i++)
508 elements[i] = elements[i + 1];
511 list->count = count - 1;
516 gl_carray_remove_node (gl_list_t list, gl_list_node_t node)
518 size_t count = list->count;
519 uintptr_t index = NODE_TO_INDEX (node);
521 if (!(index < count))
522 /* Invalid argument. */
524 return gl_carray_remove_at (list, index);
528 gl_carray_remove (gl_list_t list, const void *elt)
530 size_t position = gl_carray_indexof_from_to (list, 0, list->count, elt);
531 if (position == (size_t)(-1))
534 return gl_carray_remove_at (list, position);
538 gl_carray_list_free (gl_list_t list)
540 if (list->elements != NULL)
542 if (list->base.dispose_fn != NULL)
544 size_t count = list->count;
548 gl_listelement_dispose_fn dispose = list->base.dispose_fn;
549 const void **elements = list->elements;
550 size_t i1 = list->offset;
551 size_t i3 = list->offset + count - 1;
553 if (i3 >= list->allocated)
555 /* Here we must have list->offset > 0, hence
556 list->allocated > 0. */
557 size_t i2 = list->allocated - 1;
560 i3 -= list->allocated;
561 for (i = i1; i <= i2; i++)
562 dispose (elements[i]);
563 for (i = 0; i <= i3; i++)
564 dispose (elements[i]);
570 for (i = i1; i <= i3; i++)
571 dispose (elements[i]);
575 free (list->elements);
580 /* --------------------- gl_list_iterator_t Data Type --------------------- */
582 static gl_list_iterator_t
583 gl_carray_iterator (gl_list_t list)
585 gl_list_iterator_t result;
587 result.vtable = list->base.vtable;
589 result.count = list->count;
591 result.j = list->count;
600 static gl_list_iterator_t
601 gl_carray_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
603 gl_list_iterator_t result;
605 if (!(start_index <= end_index && end_index <= list->count))
606 /* Invalid arguments. */
608 result.vtable = list->base.vtable;
610 result.count = list->count;
611 result.i = start_index;
612 result.j = end_index;
622 gl_carray_iterator_next (gl_list_iterator_t *iterator,
623 const void **eltp, gl_list_node_t *nodep)
625 gl_list_t list = iterator->list;
626 if (iterator->count != list->count)
628 if (iterator->count != list->count + 1)
629 /* Concurrent modifications were done on the list. */
631 /* The last returned element was removed. */
636 if (iterator->i < iterator->j)
638 size_t i = list->offset + iterator->i;
639 if (i >= list->allocated)
640 i -= list->allocated;
641 *eltp = list->elements[i];
643 *nodep = INDEX_TO_NODE (iterator->i);
652 gl_carray_iterator_free (gl_list_iterator_t *iterator)
656 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
659 gl_carray_sortedlist_indexof_from_to (gl_list_t list,
660 gl_listelement_compar_fn compar,
661 size_t low, size_t high,
664 if (!(low <= high && high <= list->count))
665 /* Invalid arguments. */
669 /* At each loop iteration, low < high; for indices < low the values
670 are smaller than ELT; for indices >= high the values are greater
671 than ELT. So, if the element occurs in the list, it is at
672 low <= position < high. */
675 size_t mid = low + (high - low) / 2; /* low <= mid < high */
679 i_mid = list->offset + mid;
680 if (i_mid >= list->allocated)
681 i_mid -= list->allocated;
683 cmp = compar (list->elements[i_mid], elt);
691 /* We have an element equal to ELT at index MID. But we need
692 the minimal such index. */
694 /* At each loop iteration, low <= high and
695 compar (list->elements[i_high], elt) == 0,
696 and we know that the first occurrence of the element is at
697 low <= position <= high. */
700 size_t mid2 = low + (high - low) / 2; /* low <= mid2 < high */
704 i_mid2 = list->offset + mid2;
705 if (i_mid2 >= list->allocated)
706 i_mid2 -= list->allocated;
708 cmp2 = compar (list->elements[i_mid2], elt);
713 /* The list was not sorted. */
726 /* Here low == high. */
732 gl_carray_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
735 return gl_carray_sortedlist_indexof_from_to (list, compar, 0, list->count,
739 static gl_list_node_t
740 gl_carray_sortedlist_search_from_to (gl_list_t list,
741 gl_listelement_compar_fn compar,
742 size_t low, size_t high,
746 gl_carray_sortedlist_indexof_from_to (list, compar, low, high, elt);
747 return INDEX_TO_NODE (index);
750 static gl_list_node_t
751 gl_carray_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
755 gl_carray_sortedlist_indexof_from_to (list, compar, 0, list->count, elt);
756 return INDEX_TO_NODE (index);
759 static gl_list_node_t
760 gl_carray_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
763 size_t count = list->count;
767 /* At each loop iteration, low <= high; for indices < low the values are
768 smaller than ELT; for indices >= high the values are greater than ELT. */
771 size_t mid = low + (high - low) / 2; /* low <= mid < high */
775 i_mid = list->offset + mid;
776 if (i_mid >= list->allocated)
777 i_mid -= list->allocated;
779 cmp = compar (list->elements[i_mid], elt);
791 return gl_carray_add_at (list, low, elt);
795 gl_carray_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
798 size_t index = gl_carray_sortedlist_indexof (list, compar, elt);
799 if (index == (size_t)(-1))
802 return gl_carray_remove_at (list, index);
806 const struct gl_list_implementation gl_carray_list_implementation =
808 gl_carray_create_empty,
811 gl_carray_node_value,
813 gl_carray_previous_node,
816 gl_carray_search_from_to,
817 gl_carray_indexof_from_to,
820 gl_carray_add_before,
823 gl_carray_remove_node,
828 gl_carray_iterator_from_to,
829 gl_carray_iterator_next,
830 gl_carray_iterator_free,
831 gl_carray_sortedlist_search,
832 gl_carray_sortedlist_search_from_to,
833 gl_carray_sortedlist_indexof,
834 gl_carray_sortedlist_indexof_from_to,
835 gl_carray_sortedlist_add,
836 gl_carray_sortedlist_remove