1 /* Sequential list data type implemented by a circular array.
2 Copyright (C) 2006 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 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.allow_duplicates = allow_duplicates;
70 list->elements = NULL;
79 gl_carray_create (gl_list_implementation_t implementation,
80 gl_listelement_equals_fn equals_fn,
81 gl_listelement_hashcode_fn hashcode_fn,
82 bool allow_duplicates,
83 size_t count, const void **contents)
85 struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
87 list->base.vtable = implementation;
88 list->base.equals_fn = equals_fn;
89 list->base.hashcode_fn = hashcode_fn;
90 list->base.allow_duplicates = allow_duplicates;
93 list->elements = XNMALLOC (count, const void *);
94 memcpy (list->elements, contents, count * sizeof (const void *));
97 list->elements = NULL;
100 list->allocated = count;
106 gl_carray_size (gl_list_t list)
112 gl_carray_node_value (gl_list_t list, gl_list_node_t node)
114 uintptr_t index = NODE_TO_INDEX (node);
117 if (!(index < list->count))
118 /* Invalid argument. */
120 i = list->offset + index;
121 if (i >= list->allocated)
122 i -= list->allocated;
123 return list->elements[i];
126 static gl_list_node_t
127 gl_carray_next_node (gl_list_t list, gl_list_node_t node)
129 uintptr_t index = NODE_TO_INDEX (node);
130 if (!(index < list->count))
131 /* Invalid argument. */
134 if (index < list->count)
135 return INDEX_TO_NODE (index);
140 static gl_list_node_t
141 gl_carray_previous_node (gl_list_t list, gl_list_node_t node)
143 uintptr_t index = NODE_TO_INDEX (node);
144 if (!(index < list->count))
145 /* Invalid argument. */
148 return INDEX_TO_NODE (index - 1);
154 gl_carray_get_at (gl_list_t list, size_t position)
156 size_t count = list->count;
159 if (!(position < count))
160 /* Invalid argument. */
162 i = list->offset + position;
163 if (i >= list->allocated)
164 i -= list->allocated;
165 return list->elements[i];
168 static gl_list_node_t
169 gl_carray_set_at (gl_list_t list, size_t position, const void *elt)
171 size_t count = list->count;
174 if (!(position < count))
175 /* Invalid argument. */
177 i = list->offset + position;
178 if (i >= list->allocated)
179 i -= list->allocated;
180 list->elements[i] = elt;
181 return INDEX_TO_NODE (position);
185 gl_carray_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
188 size_t count = list->count;
190 if (!(start_index <= end_index && end_index <= count))
191 /* Invalid arguments. */
194 if (start_index < end_index)
196 gl_listelement_equals_fn equals = list->base.equals_fn;
197 size_t allocated = list->allocated;
200 i_end = list->offset + end_index;
201 if (i_end >= allocated)
208 i = list->offset + start_index;
209 if (i >= allocated) /* can only happen if start_index > 0 */
214 if (equals (elt, list->elements[i]))
215 return (i >= list->offset ? i : i + allocated) - list->offset;
227 i = list->offset + start_index;
228 if (i >= allocated) /* can only happen if start_index > 0 */
233 if (elt == list->elements[i])
234 return (i >= list->offset ? i : i + allocated) - list->offset;
246 static gl_list_node_t
247 gl_carray_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
250 size_t index = gl_carray_indexof_from_to (list, start_index, end_index, elt);
251 return INDEX_TO_NODE (index);
254 /* Ensure that list->allocated > list->count. */
256 grow (gl_list_t list)
258 size_t new_allocated;
262 new_allocated = xtimes (list->allocated, 2);
263 new_allocated = xsum (new_allocated, 1);
264 memory_size = xtimes (new_allocated, sizeof (const void *));
265 if (size_overflow_p (memory_size))
266 /* Overflow, would lead to out of memory. */
268 if (list->offset > 0 && list->count > 0)
270 memory = (const void **) xmalloc (memory_size);
274 if (list->offset + list->count > list->allocated)
276 memcpy (memory, &list->elements[list->offset],
277 (list->allocated - list->offset) * sizeof (const void *));
278 memcpy (memory + (list->allocated - list->offset), list->elements,
279 (list->offset + list->count - list->allocated)
280 * sizeof (const void *));
284 memcpy (memory, &list->elements[list->offset],
285 list->count * sizeof (const void *));
286 if (list->elements != NULL)
287 free (list->elements);
291 memory = (const void **) xrealloc (list->elements, memory_size);
296 list->elements = memory;
298 list->allocated = new_allocated;
301 static gl_list_node_t
302 gl_carray_add_first (gl_list_t list, const void *elt)
304 size_t count = list->count;
306 if (count == list->allocated)
308 list->offset = (list->offset == 0 ? list->allocated : list->offset) - 1;
309 list->elements[list->offset] = elt;
310 list->count = count + 1;
311 return INDEX_TO_NODE (0);
314 static gl_list_node_t
315 gl_carray_add_last (gl_list_t list, const void *elt)
317 size_t count = list->count;
320 if (count == list->allocated)
322 i = list->offset + count;
323 if (i >= list->allocated)
324 i -= list->allocated;
325 list->elements[i] = elt;
326 list->count = count + 1;
327 return INDEX_TO_NODE (count);
330 static gl_list_node_t
331 gl_carray_add_at (gl_list_t list, size_t position, const void *elt)
333 size_t count = list->count;
334 const void **elements;
336 if (!(position <= count))
337 /* Invalid argument. */
339 if (count == list->allocated)
341 elements = list->elements;
342 if (position <= (count / 2))
344 /* Shift at most count/2 elements to the left. */
347 list->offset = (list->offset == 0 ? list->allocated : list->offset) - 1;
349 i2 = list->offset + position;
350 if (i2 >= list->allocated)
352 /* Here we must have list->offset > 0, hence list->allocated > 0. */
353 size_t i1 = list->allocated - 1;
354 i2 -= list->allocated;
355 for (i = list->offset; i < i1; i++)
356 elements[i] = elements[i + 1];
357 elements[i1] = elements[0];
358 for (i = 0; i < i2; i++)
359 elements[i] = elements[i + 1];
363 for (i = list->offset; i < i2; i++)
364 elements[i] = elements[i + 1];
370 /* Shift at most (count+1)/2 elements to the right. */
373 i1 = list->offset + position;
374 i3 = list->offset + count;
375 if (i1 >= list->allocated)
377 i1 -= list->allocated;
378 i3 -= list->allocated;
379 for (i = i3; i > i1; i--)
380 elements[i] = elements[i - 1];
382 else if (i3 >= list->allocated)
384 /* Here we must have list->offset > 0, hence list->allocated > 0. */
385 size_t i2 = list->allocated - 1;
386 i3 -= list->allocated;
387 for (i = i3; i > 0; i--)
388 elements[i] = elements[i - 1];
389 elements[0] = elements[i2];
390 for (i = i2; i > i1; i--)
391 elements[i] = elements[i - 1];
395 for (i = i3; i > i1; i--)
396 elements[i] = elements[i - 1];
400 list->count = count + 1;
401 return INDEX_TO_NODE (position);
404 static gl_list_node_t
405 gl_carray_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
407 size_t count = list->count;
408 uintptr_t index = NODE_TO_INDEX (node);
410 if (!(index < count))
411 /* Invalid argument. */
413 return gl_carray_add_at (list, index, elt);
416 static gl_list_node_t
417 gl_carray_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
419 size_t count = list->count;
420 uintptr_t index = NODE_TO_INDEX (node);
422 if (!(index < count))
423 /* Invalid argument. */
425 return gl_carray_add_at (list, index + 1, elt);
429 gl_carray_remove_at (gl_list_t list, size_t position)
431 size_t count = list->count;
432 const void **elements;
434 if (!(position < count))
435 /* Invalid argument. */
437 /* Here we know count > 0. */
438 elements = list->elements;
439 if (position <= ((count - 1) / 2))
441 /* Shift at most (count-1)/2 elements to the right. */
445 i2 = list->offset + position;
446 if (i2 >= list->allocated)
448 /* Here we must have list->offset > 0, hence list->allocated > 0. */
449 size_t i1 = list->allocated - 1;
450 i2 -= list->allocated;
451 for (i = i2; i > 0; i--)
452 elements[i] = elements[i - 1];
453 elements[0] = elements[i1];
454 for (i = i1; i > i0; i--)
455 elements[i] = elements[i - 1];
459 for (i = i2; i > i0; i--)
460 elements[i] = elements[i - 1];
464 list->offset = (i0 == list->allocated ? 0 : i0);
468 /* Shift at most count/2 elements to the left. */
471 i1 = list->offset + position;
472 i3 = list->offset + count - 1;
473 if (i1 >= list->allocated)
475 i1 -= list->allocated;
476 i3 -= list->allocated;
477 for (i = i1; i < i3; i++)
478 elements[i] = elements[i + 1];
480 else if (i3 >= list->allocated)
482 /* Here we must have list->offset > 0, hence list->allocated > 0. */
483 size_t i2 = list->allocated - 1;
484 i3 -= list->allocated;
485 for (i = i1; i < i2; i++)
486 elements[i] = elements[i + 1];
487 elements[i2] = elements[0];
488 for (i = 0; i < i3; i++)
489 elements[i] = elements[i + 1];
493 for (i = i1; i < i3; i++)
494 elements[i] = elements[i + 1];
497 list->count = count - 1;
502 gl_carray_remove_node (gl_list_t list, gl_list_node_t node)
504 size_t count = list->count;
505 uintptr_t index = NODE_TO_INDEX (node);
507 if (!(index < count))
508 /* Invalid argument. */
510 return gl_carray_remove_at (list, index);
514 gl_carray_remove (gl_list_t list, const void *elt)
516 size_t position = gl_carray_indexof_from_to (list, 0, list->count, elt);
517 if (position == (size_t)(-1))
520 return gl_carray_remove_at (list, position);
524 gl_carray_list_free (gl_list_t list)
526 if (list->elements != NULL)
527 free (list->elements);
531 /* --------------------- gl_list_iterator_t Data Type --------------------- */
533 static gl_list_iterator_t
534 gl_carray_iterator (gl_list_t list)
536 gl_list_iterator_t result;
538 result.vtable = list->base.vtable;
540 result.count = list->count;
542 result.j = list->count;
551 static gl_list_iterator_t
552 gl_carray_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
554 gl_list_iterator_t result;
556 if (!(start_index <= end_index && end_index <= list->count))
557 /* Invalid arguments. */
559 result.vtable = list->base.vtable;
561 result.count = list->count;
562 result.i = start_index;
563 result.j = end_index;
573 gl_carray_iterator_next (gl_list_iterator_t *iterator,
574 const void **eltp, gl_list_node_t *nodep)
576 gl_list_t list = iterator->list;
577 if (iterator->count != list->count)
579 if (iterator->count != list->count + 1)
580 /* Concurrent modifications were done on the list. */
582 /* The last returned element was removed. */
587 if (iterator->i < iterator->j)
589 size_t i = list->offset + iterator->i;
590 if (i >= list->allocated)
591 i -= list->allocated;
592 *eltp = list->elements[i];
594 *nodep = INDEX_TO_NODE (iterator->i);
603 gl_carray_iterator_free (gl_list_iterator_t *iterator)
607 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
610 gl_carray_sortedlist_indexof_from_to (gl_list_t list,
611 gl_listelement_compar_fn compar,
612 size_t low, size_t high,
615 if (!(low <= high && high <= list->count))
616 /* Invalid arguments. */
620 /* At each loop iteration, low < high; for indices < low the values
621 are smaller than ELT; for indices >= high the values are greater
622 than ELT. So, if the element occurs in the list, it is at
623 low <= position < high. */
626 size_t mid = low + (high - low) / 2; /* low <= mid < high */
630 i_mid = list->offset + mid;
631 if (i_mid >= list->allocated)
632 i_mid -= list->allocated;
634 cmp = compar (list->elements[i_mid], elt);
642 /* We have an element equal to ELT at index MID. But we need
643 the minimal such index. */
645 /* At each loop iteration, low <= high and
646 compar (list->elements[i_high], elt) == 0,
647 and we know that the first occurrence of the element is at
648 low <= position <= high. */
651 size_t mid2 = low + (high - low) / 2; /* low <= mid2 < high */
655 i_mid2 = list->offset + mid2;
656 if (i_mid2 >= list->allocated)
657 i_mid2 -= list->allocated;
659 cmp2 = compar (list->elements[i_mid2], elt);
664 /* The list was not sorted. */
677 /* Here low == high. */
683 gl_carray_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
686 return gl_carray_sortedlist_indexof_from_to (list, compar, 0, list->count,
690 static gl_list_node_t
691 gl_carray_sortedlist_search_from_to (gl_list_t list,
692 gl_listelement_compar_fn compar,
693 size_t low, size_t high,
697 gl_carray_sortedlist_indexof_from_to (list, compar, low, high, elt);
698 return INDEX_TO_NODE (index);
701 static gl_list_node_t
702 gl_carray_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
706 gl_carray_sortedlist_indexof_from_to (list, compar, 0, list->count, elt);
707 return INDEX_TO_NODE (index);
710 static gl_list_node_t
711 gl_carray_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
714 size_t count = list->count;
718 /* At each loop iteration, low <= high; for indices < low the values are
719 smaller than ELT; for indices >= high the values are greater than ELT. */
722 size_t mid = low + (high - low) / 2; /* low <= mid < high */
726 i_mid = list->offset + mid;
727 if (i_mid >= list->allocated)
728 i_mid -= list->allocated;
730 cmp = compar (list->elements[i_mid], elt);
742 return gl_carray_add_at (list, low, elt);
746 gl_carray_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
749 size_t index = gl_carray_sortedlist_indexof (list, compar, elt);
750 if (index == (size_t)(-1))
753 return gl_carray_remove_at (list, index);
757 const struct gl_list_implementation gl_carray_list_implementation =
759 gl_carray_create_empty,
762 gl_carray_node_value,
764 gl_carray_previous_node,
767 gl_carray_search_from_to,
768 gl_carray_indexof_from_to,
771 gl_carray_add_before,
774 gl_carray_remove_node,
779 gl_carray_iterator_from_to,
780 gl_carray_iterator_next,
781 gl_carray_iterator_free,
782 gl_carray_sortedlist_search,
783 gl_carray_sortedlist_search_from_to,
784 gl_carray_sortedlist_indexof,
785 gl_carray_sortedlist_indexof_from_to,
786 gl_carray_sortedlist_add,
787 gl_carray_sortedlist_remove