This source file includes following definitions.
- gl_carray_nx_create_empty
- gl_carray_nx_create
- gl_carray_size
- gl_carray_node_value
- gl_carray_node_nx_set_value
- gl_carray_next_node
- gl_carray_previous_node
- gl_carray_first_node
- gl_carray_last_node
- gl_carray_get_at
- gl_carray_nx_set_at
- gl_carray_indexof_from_to
- gl_carray_search_from_to
- grow
- gl_carray_nx_add_first
- gl_carray_nx_add_last
- gl_carray_nx_add_at
- gl_carray_nx_add_before
- gl_carray_nx_add_after
- gl_carray_remove_at
- gl_carray_remove_node
- gl_carray_remove
- gl_carray_list_free
- gl_carray_iterator
- gl_carray_iterator_from_to
- gl_carray_iterator_next
- gl_carray_iterator_free
- gl_carray_sortedlist_indexof_from_to
- gl_carray_sortedlist_indexof
- gl_carray_sortedlist_search_from_to
- gl_carray_sortedlist_search
- gl_carray_sortedlist_nx_add
- gl_carray_sortedlist_remove
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 #include <config.h>
19
20
21 #include "gl_carray_list.h"
22
23 #include <stdint.h>
24 #include <stdlib.h>
25
26 #include <string.h>
27
28
29 #include "xsize.h"
30
31
32
33
34 struct gl_list_impl
35 {
36 struct gl_list_impl_base base;
37
38
39
40
41 const void **elements;
42 size_t offset;
43 size_t count;
44 size_t allocated;
45 };
46
47
48
49 #define INDEX_TO_NODE(index) (gl_list_node_t)(uintptr_t)(size_t)((index) + 1)
50 #define NODE_TO_INDEX(node) ((uintptr_t)(node) - 1)
51
52 static gl_list_t
53 gl_carray_nx_create_empty (gl_list_implementation_t implementation,
54 gl_listelement_equals_fn equals_fn,
55 gl_listelement_hashcode_fn hashcode_fn,
56 gl_listelement_dispose_fn dispose_fn,
57 bool allow_duplicates)
58 {
59 struct gl_list_impl *list =
60 (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
61
62 if (list == NULL)
63 return NULL;
64
65 list->base.vtable = implementation;
66 list->base.equals_fn = equals_fn;
67 list->base.hashcode_fn = hashcode_fn;
68 list->base.dispose_fn = dispose_fn;
69 list->base.allow_duplicates = allow_duplicates;
70 list->elements = NULL;
71 list->offset = 0;
72 list->count = 0;
73 list->allocated = 0;
74
75 return list;
76 }
77
78 static gl_list_t
79 gl_carray_nx_create (gl_list_implementation_t implementation,
80 gl_listelement_equals_fn equals_fn,
81 gl_listelement_hashcode_fn hashcode_fn,
82 gl_listelement_dispose_fn dispose_fn,
83 bool allow_duplicates,
84 size_t count, const void **contents)
85 {
86 struct gl_list_impl *list =
87 (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
88
89 if (list == NULL)
90 return NULL;
91
92 list->base.vtable = implementation;
93 list->base.equals_fn = equals_fn;
94 list->base.hashcode_fn = hashcode_fn;
95 list->base.dispose_fn = dispose_fn;
96 list->base.allow_duplicates = allow_duplicates;
97 if (count > 0)
98 {
99 if (size_overflow_p (xtimes (count, sizeof (const void *))))
100 goto fail;
101 list->elements = (const void **) malloc (count * sizeof (const void *));
102 if (list->elements == NULL)
103 goto fail;
104 memcpy (list->elements, contents, count * sizeof (const void *));
105 }
106 else
107 list->elements = NULL;
108 list->offset = 0;
109 list->count = count;
110 list->allocated = count;
111
112 return list;
113
114 fail:
115 free (list);
116 return NULL;
117 }
118
119 static size_t _GL_ATTRIBUTE_PURE
120 gl_carray_size (gl_list_t list)
121 {
122 return list->count;
123 }
124
125 static const void * _GL_ATTRIBUTE_PURE
126 gl_carray_node_value (gl_list_t list, gl_list_node_t node)
127 {
128 uintptr_t index = NODE_TO_INDEX (node);
129 size_t i;
130
131 if (!(index < list->count))
132
133 abort ();
134 i = list->offset + index;
135 if (i >= list->allocated)
136 i -= list->allocated;
137 return list->elements[i];
138 }
139
140 static int
141 gl_carray_node_nx_set_value (gl_list_t list, gl_list_node_t node,
142 const void *elt)
143 {
144 uintptr_t index = NODE_TO_INDEX (node);
145 size_t i;
146
147 if (!(index < list->count))
148
149 abort ();
150 i = list->offset + index;
151 if (i >= list->allocated)
152 i -= list->allocated;
153 list->elements[i] = elt;
154 return 0;
155 }
156
157 static gl_list_node_t _GL_ATTRIBUTE_PURE
158 gl_carray_next_node (gl_list_t list, gl_list_node_t node)
159 {
160 uintptr_t index = NODE_TO_INDEX (node);
161 if (!(index < list->count))
162
163 abort ();
164 index++;
165 if (index < list->count)
166 return INDEX_TO_NODE (index);
167 else
168 return NULL;
169 }
170
171 static gl_list_node_t _GL_ATTRIBUTE_PURE
172 gl_carray_previous_node (gl_list_t list, gl_list_node_t node)
173 {
174 uintptr_t index = NODE_TO_INDEX (node);
175 if (!(index < list->count))
176
177 abort ();
178 if (index > 0)
179 return INDEX_TO_NODE (index - 1);
180 else
181 return NULL;
182 }
183
184 static gl_list_node_t _GL_ATTRIBUTE_PURE
185 gl_carray_first_node (gl_list_t list)
186 {
187 if (list->count > 0)
188 return INDEX_TO_NODE (0);
189 else
190 return NULL;
191 }
192
193 static gl_list_node_t _GL_ATTRIBUTE_PURE
194 gl_carray_last_node (gl_list_t list)
195 {
196 if (list->count > 0)
197 return INDEX_TO_NODE (list->count - 1);
198 else
199 return NULL;
200 }
201
202 static const void * _GL_ATTRIBUTE_PURE
203 gl_carray_get_at (gl_list_t list, size_t position)
204 {
205 size_t count = list->count;
206 size_t i;
207
208 if (!(position < count))
209
210 abort ();
211 i = list->offset + position;
212 if (i >= list->allocated)
213 i -= list->allocated;
214 return list->elements[i];
215 }
216
217 static gl_list_node_t
218 gl_carray_nx_set_at (gl_list_t list, size_t position, const void *elt)
219 {
220 size_t count = list->count;
221 size_t i;
222
223 if (!(position < count))
224
225 abort ();
226 i = list->offset + position;
227 if (i >= list->allocated)
228 i -= list->allocated;
229 list->elements[i] = elt;
230 return INDEX_TO_NODE (position);
231 }
232
233 static size_t _GL_ATTRIBUTE_PURE
234 gl_carray_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
235 const void *elt)
236 {
237 size_t count = list->count;
238
239 if (!(start_index <= end_index && end_index <= count))
240
241 abort ();
242
243 if (start_index < end_index)
244 {
245 gl_listelement_equals_fn equals = list->base.equals_fn;
246 size_t allocated = list->allocated;
247 size_t i_end;
248
249 i_end = list->offset + end_index;
250 if (i_end >= allocated)
251 i_end -= allocated;
252
253 if (equals != NULL)
254 {
255 size_t i;
256
257 i = list->offset + start_index;
258 if (i >= allocated)
259 i -= allocated;
260
261 for (;;)
262 {
263 if (equals (elt, list->elements[i]))
264 return (i >= list->offset ? i : i + allocated) - list->offset;
265 i++;
266 if (i == allocated)
267 i = 0;
268 if (i == i_end)
269 break;
270 }
271 }
272 else
273 {
274 size_t i;
275
276 i = list->offset + start_index;
277 if (i >= allocated)
278 i -= allocated;
279
280 for (;;)
281 {
282 if (elt == list->elements[i])
283 return (i >= list->offset ? i : i + allocated) - list->offset;
284 i++;
285 if (i == allocated)
286 i = 0;
287 if (i == i_end)
288 break;
289 }
290 }
291 }
292 return (size_t)(-1);
293 }
294
295 static gl_list_node_t _GL_ATTRIBUTE_PURE
296 gl_carray_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
297 const void *elt)
298 {
299 size_t index = gl_carray_indexof_from_to (list, start_index, end_index, elt);
300 return INDEX_TO_NODE (index);
301 }
302
303
304
305 static int
306 grow (gl_list_t list)
307 {
308 size_t new_allocated;
309 size_t memory_size;
310 const void **memory;
311
312 new_allocated = xtimes (list->allocated, 2);
313 new_allocated = xsum (new_allocated, 1);
314 memory_size = xtimes (new_allocated, sizeof (const void *));
315 if (size_overflow_p (memory_size))
316
317 return -1;
318 if (list->offset > 0 && list->count > 0)
319 {
320 memory = (const void **) malloc (memory_size);
321 if (memory == NULL)
322
323 return -1;
324 if (list->offset + list->count > list->allocated)
325 {
326 memcpy (memory, &list->elements[list->offset],
327 (list->allocated - list->offset) * sizeof (const void *));
328 memcpy (memory + (list->allocated - list->offset), list->elements,
329 (list->offset + list->count - list->allocated)
330 * sizeof (const void *));
331
332 }
333 else
334 memcpy (memory, &list->elements[list->offset],
335 list->count * sizeof (const void *));
336 if (list->elements != NULL)
337 free (list->elements);
338 }
339 else
340 {
341 memory = (const void **) realloc (list->elements, memory_size);
342 if (memory == NULL)
343
344 return -1;
345 }
346 list->elements = memory;
347 list->offset = 0;
348 list->allocated = new_allocated;
349 return 0;
350 }
351
352 static gl_list_node_t
353 gl_carray_nx_add_first (gl_list_t list, const void *elt)
354 {
355 size_t count = list->count;
356
357 if (count == list->allocated)
358 if (grow (list) < 0)
359 return NULL;
360 list->offset = (list->offset == 0 ? list->allocated : list->offset) - 1;
361 list->elements[list->offset] = elt;
362 list->count = count + 1;
363 return INDEX_TO_NODE (0);
364 }
365
366 static gl_list_node_t
367 gl_carray_nx_add_last (gl_list_t list, const void *elt)
368 {
369 size_t count = list->count;
370 size_t i;
371
372 if (count == list->allocated)
373 if (grow (list) < 0)
374 return NULL;
375 i = list->offset + count;
376 if (i >= list->allocated)
377 i -= list->allocated;
378 list->elements[i] = elt;
379 list->count = count + 1;
380 return INDEX_TO_NODE (count);
381 }
382
383 static gl_list_node_t
384 gl_carray_nx_add_at (gl_list_t list, size_t position, const void *elt)
385 {
386 size_t count = list->count;
387 const void **elements;
388
389 if (!(position <= count))
390
391 abort ();
392 if (count == list->allocated)
393 if (grow (list) < 0)
394 return NULL;
395 elements = list->elements;
396 if (position <= (count / 2))
397 {
398
399 size_t i2, i;
400
401 list->offset = (list->offset == 0 ? list->allocated : list->offset) - 1;
402
403 i2 = list->offset + position;
404 if (i2 >= list->allocated)
405 {
406
407 size_t i1 = list->allocated - 1;
408 i2 -= list->allocated;
409 for (i = list->offset; i < i1; i++)
410 elements[i] = elements[i + 1];
411 elements[i1] = elements[0];
412 for (i = 0; i < i2; i++)
413 elements[i] = elements[i + 1];
414 }
415 else
416 {
417 for (i = list->offset; i < i2; i++)
418 elements[i] = elements[i + 1];
419 }
420 elements[i2] = elt;
421 }
422 else
423 {
424
425 size_t i1, i3, i;
426
427 i1 = list->offset + position;
428 i3 = list->offset + count;
429 if (i1 >= list->allocated)
430 {
431 i1 -= list->allocated;
432 i3 -= list->allocated;
433 for (i = i3; i > i1; i--)
434 elements[i] = elements[i - 1];
435 }
436 else if (i3 >= list->allocated)
437 {
438
439 size_t i2 = list->allocated - 1;
440 i3 -= list->allocated;
441 for (i = i3; i > 0; i--)
442 elements[i] = elements[i - 1];
443 elements[0] = elements[i2];
444 for (i = i2; i > i1; i--)
445 elements[i] = elements[i - 1];
446 }
447 else
448 {
449 for (i = i3; i > i1; i--)
450 elements[i] = elements[i - 1];
451 }
452 elements[i1] = elt;
453 }
454 list->count = count + 1;
455 return INDEX_TO_NODE (position);
456 }
457
458 static gl_list_node_t
459 gl_carray_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
460 {
461 size_t count = list->count;
462 uintptr_t index = NODE_TO_INDEX (node);
463
464 if (!(index < count))
465
466 abort ();
467 return gl_carray_nx_add_at (list, index, elt);
468 }
469
470 static gl_list_node_t
471 gl_carray_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
472 {
473 size_t count = list->count;
474 uintptr_t index = NODE_TO_INDEX (node);
475
476 if (!(index < count))
477
478 abort ();
479 return gl_carray_nx_add_at (list, index + 1, elt);
480 }
481
482 static bool
483 gl_carray_remove_at (gl_list_t list, size_t position)
484 {
485 size_t count = list->count;
486 const void **elements;
487
488 if (!(position < count))
489
490 abort ();
491
492 elements = list->elements;
493 if (position <= ((count - 1) / 2))
494 {
495
496 size_t i0, i2, i;
497
498 i0 = list->offset;
499 i2 = list->offset + position;
500 if (i2 >= list->allocated)
501 {
502
503 size_t i1 = list->allocated - 1;
504 i2 -= list->allocated;
505 if (list->base.dispose_fn != NULL)
506 list->base.dispose_fn (elements[i2]);
507 for (i = i2; i > 0; i--)
508 elements[i] = elements[i - 1];
509 elements[0] = elements[i1];
510 for (i = i1; i > i0; i--)
511 elements[i] = elements[i - 1];
512 }
513 else
514 {
515 if (list->base.dispose_fn != NULL)
516 list->base.dispose_fn (elements[i2]);
517 for (i = i2; i > i0; i--)
518 elements[i] = elements[i - 1];
519 }
520
521 i0++;
522 list->offset = (i0 == list->allocated ? 0 : i0);
523 }
524 else
525 {
526
527 size_t i1, i3, i;
528
529 i1 = list->offset + position;
530 i3 = list->offset + count - 1;
531 if (i1 >= list->allocated)
532 {
533 i1 -= list->allocated;
534 i3 -= list->allocated;
535 if (list->base.dispose_fn != NULL)
536 list->base.dispose_fn (elements[i1]);
537 for (i = i1; i < i3; i++)
538 elements[i] = elements[i + 1];
539 }
540 else if (i3 >= list->allocated)
541 {
542
543 size_t i2 = list->allocated - 1;
544 i3 -= list->allocated;
545 if (list->base.dispose_fn != NULL)
546 list->base.dispose_fn (elements[i1]);
547 for (i = i1; i < i2; i++)
548 elements[i] = elements[i + 1];
549 elements[i2] = elements[0];
550 for (i = 0; i < i3; i++)
551 elements[i] = elements[i + 1];
552 }
553 else
554 {
555 if (list->base.dispose_fn != NULL)
556 list->base.dispose_fn (elements[i1]);
557 for (i = i1; i < i3; i++)
558 elements[i] = elements[i + 1];
559 }
560 }
561 list->count = count - 1;
562 return true;
563 }
564
565 static bool
566 gl_carray_remove_node (gl_list_t list, gl_list_node_t node)
567 {
568 size_t count = list->count;
569 uintptr_t index = NODE_TO_INDEX (node);
570
571 if (!(index < count))
572
573 abort ();
574 return gl_carray_remove_at (list, index);
575 }
576
577 static bool
578 gl_carray_remove (gl_list_t list, const void *elt)
579 {
580 size_t position = gl_carray_indexof_from_to (list, 0, list->count, elt);
581 if (position == (size_t)(-1))
582 return false;
583 else
584 return gl_carray_remove_at (list, position);
585 }
586
587 static void
588 gl_carray_list_free (gl_list_t list)
589 {
590 if (list->elements != NULL)
591 {
592 if (list->base.dispose_fn != NULL)
593 {
594 size_t count = list->count;
595
596 if (count > 0)
597 {
598 gl_listelement_dispose_fn dispose = list->base.dispose_fn;
599 const void **elements = list->elements;
600 size_t i1 = list->offset;
601 size_t i3 = list->offset + count - 1;
602
603 if (i3 >= list->allocated)
604 {
605
606
607 size_t i2 = list->allocated - 1;
608 size_t i;
609
610 i3 -= list->allocated;
611 for (i = i1; i <= i2; i++)
612 dispose (elements[i]);
613 for (i = 0; i <= i3; i++)
614 dispose (elements[i]);
615 }
616 else
617 {
618 size_t i;
619
620 for (i = i1; i <= i3; i++)
621 dispose (elements[i]);
622 }
623 }
624 }
625 free (list->elements);
626 }
627 free (list);
628 }
629
630
631
632 static gl_list_iterator_t _GL_ATTRIBUTE_PURE
633 gl_carray_iterator (gl_list_t list)
634 {
635 gl_list_iterator_t result;
636
637 result.vtable = list->base.vtable;
638 result.list = list;
639 result.count = list->count;
640 result.i = 0;
641 result.j = list->count;
642 #if defined GCC_LINT || defined lint
643 result.p = 0;
644 result.q = 0;
645 #endif
646
647 return result;
648 }
649
650 static gl_list_iterator_t _GL_ATTRIBUTE_PURE
651 gl_carray_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
652 {
653 gl_list_iterator_t result;
654
655 if (!(start_index <= end_index && end_index <= list->count))
656
657 abort ();
658 result.vtable = list->base.vtable;
659 result.list = list;
660 result.count = list->count;
661 result.i = start_index;
662 result.j = end_index;
663 #if defined GCC_LINT || defined lint
664 result.p = 0;
665 result.q = 0;
666 #endif
667
668 return result;
669 }
670
671 static bool
672 gl_carray_iterator_next (gl_list_iterator_t *iterator,
673 const void **eltp, gl_list_node_t *nodep)
674 {
675 gl_list_t list = iterator->list;
676 if (iterator->count != list->count)
677 {
678 if (iterator->count != list->count + 1)
679
680 abort ();
681
682 iterator->count--;
683 iterator->i--;
684 iterator->j--;
685 }
686 if (iterator->i < iterator->j)
687 {
688 size_t i = list->offset + iterator->i;
689 if (i >= list->allocated)
690 i -= list->allocated;
691 *eltp = list->elements[i];
692 if (nodep != NULL)
693 *nodep = INDEX_TO_NODE (iterator->i);
694 iterator->i++;
695 return true;
696 }
697 else
698 return false;
699 }
700
701 static void
702 gl_carray_iterator_free (_GL_ATTRIBUTE_MAYBE_UNUSED gl_list_iterator_t *iterator)
703 {
704 }
705
706
707
708 static size_t _GL_ATTRIBUTE_PURE
709 gl_carray_sortedlist_indexof_from_to (gl_list_t list,
710 gl_listelement_compar_fn compar,
711 size_t low, size_t high,
712 const void *elt)
713 {
714 if (!(low <= high && high <= list->count))
715
716 abort ();
717 if (low < high)
718 {
719
720
721
722
723 do
724 {
725 size_t mid = low + (high - low) / 2;
726 size_t i_mid;
727 int cmp;
728
729 i_mid = list->offset + mid;
730 if (i_mid >= list->allocated)
731 i_mid -= list->allocated;
732
733 cmp = compar (list->elements[i_mid], elt);
734
735 if (cmp < 0)
736 low = mid + 1;
737 else if (cmp > 0)
738 high = mid;
739 else
740 {
741
742
743 high = mid;
744
745
746
747
748 while (low < high)
749 {
750 size_t mid2 = low + (high - low) / 2;
751 size_t i_mid2;
752 int cmp2;
753
754 i_mid2 = list->offset + mid2;
755 if (i_mid2 >= list->allocated)
756 i_mid2 -= list->allocated;
757
758 cmp2 = compar (list->elements[i_mid2], elt);
759
760 if (cmp2 < 0)
761 low = mid2 + 1;
762 else if (cmp2 > 0)
763
764 abort ();
765 else
766 {
767 if (mid2 == low)
768 break;
769 high = mid2 - 1;
770 }
771 }
772 return low;
773 }
774 }
775 while (low < high);
776
777 }
778 return (size_t)(-1);
779 }
780
781 static size_t _GL_ATTRIBUTE_PURE
782 gl_carray_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
783 const void *elt)
784 {
785 return gl_carray_sortedlist_indexof_from_to (list, compar, 0, list->count,
786 elt);
787 }
788
789 static gl_list_node_t _GL_ATTRIBUTE_PURE
790 gl_carray_sortedlist_search_from_to (gl_list_t list,
791 gl_listelement_compar_fn compar,
792 size_t low, size_t high,
793 const void *elt)
794 {
795 size_t index =
796 gl_carray_sortedlist_indexof_from_to (list, compar, low, high, elt);
797 return INDEX_TO_NODE (index);
798 }
799
800 static gl_list_node_t _GL_ATTRIBUTE_PURE
801 gl_carray_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
802 const void *elt)
803 {
804 size_t index =
805 gl_carray_sortedlist_indexof_from_to (list, compar, 0, list->count, elt);
806 return INDEX_TO_NODE (index);
807 }
808
809 static gl_list_node_t
810 gl_carray_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar,
811 const void *elt)
812 {
813 size_t count = list->count;
814 size_t low = 0;
815 size_t high = count;
816
817
818
819 while (low < high)
820 {
821 size_t mid = low + (high - low) / 2;
822 size_t i_mid;
823 int cmp;
824
825 i_mid = list->offset + mid;
826 if (i_mid >= list->allocated)
827 i_mid -= list->allocated;
828
829 cmp = compar (list->elements[i_mid], elt);
830
831 if (cmp < 0)
832 low = mid + 1;
833 else if (cmp > 0)
834 high = mid;
835 else
836 {
837 low = mid;
838 break;
839 }
840 }
841 return gl_carray_nx_add_at (list, low, elt);
842 }
843
844 static bool
845 gl_carray_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
846 const void *elt)
847 {
848 size_t index = gl_carray_sortedlist_indexof (list, compar, elt);
849 if (index == (size_t)(-1))
850 return false;
851 else
852 return gl_carray_remove_at (list, index);
853 }
854
855
856 const struct gl_list_implementation gl_carray_list_implementation =
857 {
858 gl_carray_nx_create_empty,
859 gl_carray_nx_create,
860 gl_carray_size,
861 gl_carray_node_value,
862 gl_carray_node_nx_set_value,
863 gl_carray_next_node,
864 gl_carray_previous_node,
865 gl_carray_first_node,
866 gl_carray_last_node,
867 gl_carray_get_at,
868 gl_carray_nx_set_at,
869 gl_carray_search_from_to,
870 gl_carray_indexof_from_to,
871 gl_carray_nx_add_first,
872 gl_carray_nx_add_last,
873 gl_carray_nx_add_before,
874 gl_carray_nx_add_after,
875 gl_carray_nx_add_at,
876 gl_carray_remove_node,
877 gl_carray_remove_at,
878 gl_carray_remove,
879 gl_carray_list_free,
880 gl_carray_iterator,
881 gl_carray_iterator_from_to,
882 gl_carray_iterator_next,
883 gl_carray_iterator_free,
884 gl_carray_sortedlist_search,
885 gl_carray_sortedlist_search_from_to,
886 gl_carray_sortedlist_indexof,
887 gl_carray_sortedlist_indexof_from_to,
888 gl_carray_sortedlist_nx_add,
889 gl_carray_sortedlist_remove
890 };