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. */
24 #include "gl_carray_list.h"
32 /* Checked size_t computations. */
36 # define uintptr_t unsigned long
39 /* -------------------------- gl_list_t Data Type -------------------------- */
41 /* Concrete gl_list_impl type, valid for this file only. */
44 struct gl_list_impl_base base;
45 /* An array of ALLOCATED elements, of which the elements
46 OFFSET, (OFFSET + 1) % ALLOCATED, ..., (OFFSET + COUNT - 1) % ALLOCATED
47 are used. 0 <= COUNT <= ALLOCATED. Either OFFSET = ALLOCATED = 0 or
48 0 <= OFFSET < ALLOCATED. */
49 const void **elements;
55 /* struct gl_list_node_impl doesn't exist here. The pointers are actually
57 #define INDEX_TO_NODE(index) (gl_list_node_t)(uintptr_t)(size_t)((index) + 1)
58 #define NODE_TO_INDEX(node) ((uintptr_t)(node) - 1)
61 gl_carray_create_empty (gl_list_implementation_t implementation,
62 gl_listelement_equals_fn equals_fn,
63 gl_listelement_hashcode_fn hashcode_fn,
64 bool allow_duplicates)
66 struct gl_list_impl *list =
67 (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl));
69 list->base.vtable = implementation;
70 list->base.equals_fn = equals_fn;
71 list->base.hashcode_fn = hashcode_fn;
72 list->base.allow_duplicates = allow_duplicates;
73 list->elements = NULL;
82 gl_carray_create (gl_list_implementation_t implementation,
83 gl_listelement_equals_fn equals_fn,
84 gl_listelement_hashcode_fn hashcode_fn,
85 bool allow_duplicates,
86 size_t count, const void **contents)
88 struct gl_list_impl *list =
89 (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl));
91 list->base.vtable = implementation;
92 list->base.equals_fn = equals_fn;
93 list->base.hashcode_fn = hashcode_fn;
94 list->base.allow_duplicates = allow_duplicates;
98 (const void **) xmalloc (count * sizeof (const void *));
99 memcpy (list->elements, contents, count * sizeof (const void *));
102 list->elements = NULL;
105 list->allocated = count;
111 gl_carray_size (gl_list_t list)
117 gl_carray_node_value (gl_list_t list, gl_list_node_t node)
119 uintptr_t index = NODE_TO_INDEX (node);
122 if (!(index < list->count))
123 /* Invalid argument. */
125 i = list->offset + index;
126 if (i >= list->allocated)
127 i -= list->allocated;
128 return list->elements[i];
131 static gl_list_node_t
132 gl_carray_next_node (gl_list_t list, gl_list_node_t node)
134 uintptr_t index = NODE_TO_INDEX (node);
135 if (!(index < list->count))
136 /* Invalid argument. */
139 if (index < list->count)
140 return INDEX_TO_NODE (index);
145 static gl_list_node_t
146 gl_carray_previous_node (gl_list_t list, gl_list_node_t node)
148 uintptr_t index = NODE_TO_INDEX (node);
149 if (!(index < list->count))
150 /* Invalid argument. */
153 return INDEX_TO_NODE (index - 1);
159 gl_carray_get_at (gl_list_t list, size_t position)
161 size_t count = list->count;
164 if (!(position < count))
165 /* Invalid argument. */
167 i = list->offset + position;
168 if (i >= list->allocated)
169 i -= list->allocated;
170 return list->elements[i];
173 static gl_list_node_t
174 gl_carray_set_at (gl_list_t list, size_t position, const void *elt)
176 size_t count = list->count;
179 if (!(position < count))
180 /* Invalid argument. */
182 i = list->offset + position;
183 if (i >= list->allocated)
184 i -= list->allocated;
185 list->elements[i] = elt;
186 return INDEX_TO_NODE (position);
190 gl_carray_indexof (gl_list_t list, const void *elt)
192 size_t count = list->count;
195 gl_listelement_equals_fn equals = list->base.equals_fn;
196 size_t allocated = list->allocated;
199 i_end = list->offset + list->count;
200 if (i_end >= allocated)
207 for (i = list->offset;;)
209 if (equals (elt, list->elements[i]))
210 return (i >= list->offset ? i : i + allocated) - list->offset;
222 for (i = list->offset;;)
224 if (elt == list->elements[i])
225 return (i >= list->offset ? i : i + allocated) - list->offset;
237 static gl_list_node_t
238 gl_carray_search (gl_list_t list, const void *elt)
240 size_t index = gl_carray_indexof (list, elt);
241 return INDEX_TO_NODE (index);
244 /* Ensure that list->allocated > list->count. */
246 grow (gl_list_t list)
248 size_t new_allocated;
252 new_allocated = xtimes (list->allocated, 2);
253 new_allocated = xsum (new_allocated, 1);
254 memory_size = xtimes (new_allocated, sizeof (const void *));
255 if (size_overflow_p (memory_size))
256 /* Overflow, would lead to out of memory. */
258 if (list->offset > 0 && list->count > 0)
260 memory = (const void **) xmalloc (memory_size);
264 if (list->offset + list->count > list->allocated)
266 memcpy (memory, &list->elements[list->offset],
267 (list->allocated - list->offset) * sizeof (const void *));
268 memcpy (memory + (list->allocated - list->offset), list->elements,
269 (list->offset + list->count - list->allocated)
270 * sizeof (const void *));
274 memcpy (memory, &list->elements[list->offset],
275 list->count * sizeof (const void *));
276 if (list->elements != NULL)
277 free (list->elements);
281 memory = (const void **) xrealloc (list->elements, memory_size);
286 list->elements = memory;
288 list->allocated = new_allocated;
291 static gl_list_node_t
292 gl_carray_add_first (gl_list_t list, const void *elt)
294 size_t count = list->count;
296 if (count == list->allocated)
298 list->offset = (list->offset == 0 ? list->allocated : list->offset) - 1;
299 list->elements[list->offset] = elt;
300 list->count = count + 1;
301 return INDEX_TO_NODE (0);
304 static gl_list_node_t
305 gl_carray_add_last (gl_list_t list, const void *elt)
307 size_t count = list->count;
310 if (count == list->allocated)
312 i = list->offset + count;
313 if (i >= list->allocated)
314 i -= list->allocated;
315 list->elements[i] = elt;
316 list->count = count + 1;
317 return INDEX_TO_NODE (count);
320 static gl_list_node_t
321 gl_carray_add_at (gl_list_t list, size_t position, const void *elt)
323 size_t count = list->count;
324 const void **elements;
326 if (!(position <= count))
327 /* Invalid argument. */
329 if (count == list->allocated)
331 elements = list->elements;
332 if (position <= (count / 2))
334 /* Shift at most count/2 elements to the left. */
337 list->offset = (list->offset == 0 ? list->allocated : list->offset) - 1;
339 i2 = list->offset + position;
340 if (i2 >= list->allocated)
342 /* Here we must have list->offset > 0, hence list->allocated > 0. */
343 size_t i1 = list->allocated - 1;
344 i2 -= list->allocated;
345 for (i = list->offset; i < i1; i++)
346 elements[i] = elements[i + 1];
347 elements[i1] = elements[0];
348 for (i = 0; i < i2; i++)
349 elements[i] = elements[i + 1];
353 for (i = list->offset; i < i2; i++)
354 elements[i] = elements[i + 1];
360 /* Shift at most (count+1)/2 elements to the right. */
363 i1 = list->offset + position;
364 i3 = list->offset + count;
365 if (i1 >= list->allocated)
367 i1 -= list->allocated;
368 i3 -= list->allocated;
369 for (i = i3; i > i1; i--)
370 elements[i] = elements[i - 1];
372 else if (i3 >= list->allocated)
374 /* Here we must have list->offset > 0, hence list->allocated > 0. */
375 size_t i2 = list->allocated - 1;
376 i3 -= list->allocated;
377 for (i = i3; i > 0; i--)
378 elements[i] = elements[i - 1];
379 elements[0] = elements[i2];
380 for (i = i2; i > i1; i--)
381 elements[i] = elements[i - 1];
385 for (i = i3; i > i1; i--)
386 elements[i] = elements[i - 1];
390 list->count = count + 1;
391 return INDEX_TO_NODE (position);
394 static gl_list_node_t
395 gl_carray_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
397 size_t count = list->count;
398 uintptr_t index = NODE_TO_INDEX (node);
400 if (!(index < count))
401 /* Invalid argument. */
403 return gl_carray_add_at (list, index, elt);
406 static gl_list_node_t
407 gl_carray_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
409 size_t count = list->count;
410 uintptr_t index = NODE_TO_INDEX (node);
412 if (!(index < count))
413 /* Invalid argument. */
415 return gl_carray_add_at (list, index + 1, elt);
419 gl_carray_remove_at (gl_list_t list, size_t position)
421 size_t count = list->count;
422 const void **elements;
424 if (!(position < count))
425 /* Invalid argument. */
427 /* Here we know count > 0. */
428 elements = list->elements;
429 if (position <= ((count - 1) / 2))
431 /* Shift at most (count-1)/2 elements to the right. */
435 i2 = list->offset + position;
436 if (i2 >= list->allocated)
438 /* Here we must have list->offset > 0, hence list->allocated > 0. */
439 size_t i1 = list->allocated - 1;
440 i2 -= list->allocated;
441 for (i = i2; i > 0; i--)
442 elements[i] = elements[i - 1];
443 elements[0] = elements[i1];
444 for (i = i1; i > i0; i--)
445 elements[i] = elements[i - 1];
449 for (i = i2; i > i0; i--)
450 elements[i] = elements[i - 1];
454 list->offset = (i0 == list->allocated ? 0 : i0);
458 /* Shift at most count/2 elements to the left. */
461 i1 = list->offset + position;
462 i3 = list->offset + count - 1;
463 if (i1 >= list->allocated)
465 i1 -= list->allocated;
466 i3 -= list->allocated;
467 for (i = i1; i < i3; i++)
468 elements[i] = elements[i + 1];
470 else if (i3 >= list->allocated)
472 /* Here we must have list->offset > 0, hence list->allocated > 0. */
473 size_t i2 = list->allocated - 1;
474 i3 -= list->allocated;
475 for (i = i1; i < i2; i++)
476 elements[i] = elements[i + 1];
477 elements[i2] = elements[0];
478 for (i = 0; i < i3; i++)
479 elements[i] = elements[i + 1];
483 for (i = i1; i < i3; i++)
484 elements[i] = elements[i + 1];
487 list->count = count - 1;
492 gl_carray_remove_node (gl_list_t list, gl_list_node_t node)
494 size_t count = list->count;
495 uintptr_t index = NODE_TO_INDEX (node);
497 if (!(index < count))
498 /* Invalid argument. */
500 return gl_carray_remove_at (list, index);
504 gl_carray_remove (gl_list_t list, const void *elt)
506 size_t position = gl_carray_indexof (list, elt);
507 if (position == (size_t)(-1))
510 return gl_carray_remove_at (list, position);
514 gl_carray_list_free (gl_list_t list)
516 if (list->elements != NULL)
517 free (list->elements);
521 /* --------------------- gl_list_iterator_t Data Type --------------------- */
523 static gl_list_iterator_t
524 gl_carray_iterator (gl_list_t list)
526 gl_list_iterator_t result;
528 result.vtable = list->base.vtable;
530 result.count = list->count;
532 result.j = list->count;
537 static gl_list_iterator_t
538 gl_carray_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
540 gl_list_iterator_t result;
542 if (!(start_index <= end_index && end_index <= list->count))
543 /* Invalid arguments. */
545 result.vtable = list->base.vtable;
547 result.count = list->count;
548 result.i = start_index;
549 result.j = end_index;
555 gl_carray_iterator_next (gl_list_iterator_t *iterator,
556 const void **eltp, gl_list_node_t *nodep)
558 gl_list_t list = iterator->list;
559 if (iterator->count != list->count)
561 if (iterator->count != list->count + 1)
562 /* Concurrent modifications were done on the list. */
564 /* The last returned element was removed. */
569 if (iterator->i < iterator->j)
571 size_t i = list->offset + iterator->i;
572 if (i >= list->allocated)
573 i -= list->allocated;
574 *eltp = list->elements[i];
576 *nodep = INDEX_TO_NODE (iterator->i);
585 gl_carray_iterator_free (gl_list_iterator_t *iterator)
589 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
592 gl_carray_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
595 size_t count = list->count;
602 /* At each loop iteration, low < high; for indices < low the values
603 are smaller than ELT; for indices >= high the values are greater
604 than ELT. So, if the element occurs in the list, is at
605 low <= position < high. */
608 size_t mid = low + (high - low) / 2; /* low <= mid < high */
612 i_mid = list->offset + mid;
613 if (i_mid >= list->allocated)
614 i_mid -= list->allocated;
616 cmp = compar (list->elements[i_mid], elt);
624 /* We have an element equal to ELT at index MID. But we need
625 the minimal such index. */
627 /* At each loop iteration, low <= high and
628 compar (list->elements[i_high], elt) == 0,
629 and we know that the first occurrence of the element is at
630 low <= position <= high. */
633 size_t mid2 = low + (high - low) / 2; /* low <= mid < high */
637 i_mid2 = list->offset + mid2;
638 if (i_mid2 >= list->allocated)
639 i_mid2 -= list->allocated;
641 cmp2 = compar (list->elements[i_mid2], elt);
646 /* The list was not sorted. */
659 /* Here low == high. */
664 static gl_list_node_t
665 gl_carray_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
668 size_t index = gl_carray_sortedlist_indexof (list, compar, elt);
669 return INDEX_TO_NODE (index);
672 static gl_list_node_t
673 gl_carray_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
676 size_t count = list->count;
680 /* At each loop iteration, low <= high; for indices < low the values are
681 smaller than ELT; for indices >= high the values are greater than ELT. */
684 size_t mid = low + (high - low) / 2; /* low <= mid < high */
688 i_mid = list->offset + mid;
689 if (i_mid >= list->allocated)
690 i_mid -= list->allocated;
692 cmp = compar (list->elements[i_mid], elt);
704 return gl_carray_add_at (list, low, elt);
708 gl_carray_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
711 size_t index = gl_carray_sortedlist_indexof (list, compar, elt);
712 if (index == (size_t)(-1))
715 return gl_carray_remove_at (list, index);
719 const struct gl_list_implementation gl_carray_list_implementation =
721 gl_carray_create_empty,
724 gl_carray_node_value,
726 gl_carray_previous_node,
733 gl_carray_add_before,
736 gl_carray_remove_node,
741 gl_carray_iterator_from_to,
742 gl_carray_iterator_next,
743 gl_carray_iterator_free,
744 gl_carray_sortedlist_search,
745 gl_carray_sortedlist_indexof,
746 gl_carray_sortedlist_add,
747 gl_carray_sortedlist_remove