1 /* Sequential list data type implemented by a circular array.
2 Copyright (C) 2006-2018 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 <https://www.gnu.org/licenses/>. */
21 #include "gl_carray_list.h"
27 /* Checked size_t computations. */
31 # define uintptr_t unsigned long
34 /* -------------------------- gl_list_t Data Type -------------------------- */
36 /* Concrete gl_list_impl type, valid for this file only. */
39 struct gl_list_impl_base base
;
40 /* An array of ALLOCATED elements, of which the elements
41 OFFSET, (OFFSET + 1) % ALLOCATED, ..., (OFFSET + COUNT - 1) % ALLOCATED
42 are used. 0 <= COUNT <= ALLOCATED. Either OFFSET = ALLOCATED = 0 or
43 0 <= OFFSET < ALLOCATED. */
44 const void **elements
;
50 /* struct gl_list_node_impl doesn't exist here. The pointers are actually
52 #define INDEX_TO_NODE(index) (gl_list_node_t)(uintptr_t)(size_t)((index) + 1)
53 #define NODE_TO_INDEX(node) ((uintptr_t)(node) - 1)
56 gl_carray_nx_create_empty (gl_list_implementation_t implementation
,
57 gl_listelement_equals_fn equals_fn
,
58 gl_listelement_hashcode_fn hashcode_fn
,
59 gl_listelement_dispose_fn dispose_fn
,
60 bool allow_duplicates
)
62 struct gl_list_impl
*list
=
63 (struct gl_list_impl
*) malloc (sizeof (struct gl_list_impl
));
68 list
->base
.vtable
= implementation
;
69 list
->base
.equals_fn
= equals_fn
;
70 list
->base
.hashcode_fn
= hashcode_fn
;
71 list
->base
.dispose_fn
= dispose_fn
;
72 list
->base
.allow_duplicates
= allow_duplicates
;
73 list
->elements
= NULL
;
82 gl_carray_nx_create (gl_list_implementation_t implementation
,
83 gl_listelement_equals_fn equals_fn
,
84 gl_listelement_hashcode_fn hashcode_fn
,
85 gl_listelement_dispose_fn dispose_fn
,
86 bool allow_duplicates
,
87 size_t count
, const void **contents
)
89 struct gl_list_impl
*list
=
90 (struct gl_list_impl
*) malloc (sizeof (struct gl_list_impl
));
95 list
->base
.vtable
= implementation
;
96 list
->base
.equals_fn
= equals_fn
;
97 list
->base
.hashcode_fn
= hashcode_fn
;
98 list
->base
.dispose_fn
= dispose_fn
;
99 list
->base
.allow_duplicates
= allow_duplicates
;
102 if (size_overflow_p (xtimes (count
, sizeof (const void *))))
104 list
->elements
= (const void **) malloc (count
* sizeof (const void *));
105 if (list
->elements
== NULL
)
107 memcpy (list
->elements
, contents
, count
* sizeof (const void *));
110 list
->elements
= NULL
;
113 list
->allocated
= count
;
123 gl_carray_size (gl_list_t list
)
129 gl_carray_node_value (gl_list_t list
, gl_list_node_t node
)
131 uintptr_t index
= NODE_TO_INDEX (node
);
134 if (!(index
< list
->count
))
135 /* Invalid argument. */
137 i
= list
->offset
+ index
;
138 if (i
>= list
->allocated
)
139 i
-= list
->allocated
;
140 return list
->elements
[i
];
144 gl_carray_node_nx_set_value (gl_list_t list
, gl_list_node_t node
,
147 uintptr_t index
= NODE_TO_INDEX (node
);
150 if (!(index
< list
->count
))
151 /* Invalid argument. */
153 i
= list
->offset
+ index
;
154 if (i
>= list
->allocated
)
155 i
-= list
->allocated
;
156 list
->elements
[i
] = elt
;
160 static gl_list_node_t
161 gl_carray_next_node (gl_list_t list
, gl_list_node_t node
)
163 uintptr_t index
= NODE_TO_INDEX (node
);
164 if (!(index
< list
->count
))
165 /* Invalid argument. */
168 if (index
< list
->count
)
169 return INDEX_TO_NODE (index
);
174 static gl_list_node_t
175 gl_carray_previous_node (gl_list_t list
, gl_list_node_t node
)
177 uintptr_t index
= NODE_TO_INDEX (node
);
178 if (!(index
< list
->count
))
179 /* Invalid argument. */
182 return INDEX_TO_NODE (index
- 1);
188 gl_carray_get_at (gl_list_t list
, size_t position
)
190 size_t count
= list
->count
;
193 if (!(position
< count
))
194 /* Invalid argument. */
196 i
= list
->offset
+ position
;
197 if (i
>= list
->allocated
)
198 i
-= list
->allocated
;
199 return list
->elements
[i
];
202 static gl_list_node_t
203 gl_carray_nx_set_at (gl_list_t list
, size_t position
, const void *elt
)
205 size_t count
= list
->count
;
208 if (!(position
< count
))
209 /* Invalid argument. */
211 i
= list
->offset
+ position
;
212 if (i
>= list
->allocated
)
213 i
-= list
->allocated
;
214 list
->elements
[i
] = elt
;
215 return INDEX_TO_NODE (position
);
219 gl_carray_indexof_from_to (gl_list_t list
, size_t start_index
, size_t end_index
,
222 size_t count
= list
->count
;
224 if (!(start_index
<= end_index
&& end_index
<= count
))
225 /* Invalid arguments. */
228 if (start_index
< end_index
)
230 gl_listelement_equals_fn equals
= list
->base
.equals_fn
;
231 size_t allocated
= list
->allocated
;
234 i_end
= list
->offset
+ end_index
;
235 if (i_end
>= allocated
)
242 i
= list
->offset
+ start_index
;
243 if (i
>= allocated
) /* can only happen if start_index > 0 */
248 if (equals (elt
, list
->elements
[i
]))
249 return (i
>= list
->offset
? i
: i
+ allocated
) - list
->offset
;
261 i
= list
->offset
+ start_index
;
262 if (i
>= allocated
) /* can only happen if start_index > 0 */
267 if (elt
== list
->elements
[i
])
268 return (i
>= list
->offset
? i
: i
+ allocated
) - list
->offset
;
280 static gl_list_node_t
281 gl_carray_search_from_to (gl_list_t list
, size_t start_index
, size_t end_index
,
284 size_t index
= gl_carray_indexof_from_to (list
, start_index
, end_index
, elt
);
285 return INDEX_TO_NODE (index
);
288 /* Ensure that list->allocated > list->count.
289 Return 0 upon success, -1 upon out-of-memory. */
291 grow (gl_list_t list
)
293 size_t new_allocated
;
297 new_allocated
= xtimes (list
->allocated
, 2);
298 new_allocated
= xsum (new_allocated
, 1);
299 memory_size
= xtimes (new_allocated
, sizeof (const void *));
300 if (size_overflow_p (memory_size
))
301 /* Overflow, would lead to out of memory. */
303 if (list
->offset
> 0 && list
->count
> 0)
305 memory
= (const void **) malloc (memory_size
);
309 if (list
->offset
+ list
->count
> list
->allocated
)
311 memcpy (memory
, &list
->elements
[list
->offset
],
312 (list
->allocated
- list
->offset
) * sizeof (const void *));
313 memcpy (memory
+ (list
->allocated
- list
->offset
), list
->elements
,
314 (list
->offset
+ list
->count
- list
->allocated
)
315 * sizeof (const void *));
319 memcpy (memory
, &list
->elements
[list
->offset
],
320 list
->count
* sizeof (const void *));
321 if (list
->elements
!= NULL
)
322 free (list
->elements
);
326 memory
= (const void **) realloc (list
->elements
, memory_size
);
331 list
->elements
= memory
;
333 list
->allocated
= new_allocated
;
337 static gl_list_node_t
338 gl_carray_nx_add_first (gl_list_t list
, const void *elt
)
340 size_t count
= list
->count
;
342 if (count
== list
->allocated
)
345 list
->offset
= (list
->offset
== 0 ? list
->allocated
: list
->offset
) - 1;
346 list
->elements
[list
->offset
] = elt
;
347 list
->count
= count
+ 1;
348 return INDEX_TO_NODE (0);
351 static gl_list_node_t
352 gl_carray_nx_add_last (gl_list_t list
, const void *elt
)
354 size_t count
= list
->count
;
357 if (count
== list
->allocated
)
360 i
= list
->offset
+ count
;
361 if (i
>= list
->allocated
)
362 i
-= list
->allocated
;
363 list
->elements
[i
] = elt
;
364 list
->count
= count
+ 1;
365 return INDEX_TO_NODE (count
);
368 static gl_list_node_t
369 gl_carray_nx_add_at (gl_list_t list
, size_t position
, const void *elt
)
371 size_t count
= list
->count
;
372 const void **elements
;
374 if (!(position
<= count
))
375 /* Invalid argument. */
377 if (count
== list
->allocated
)
380 elements
= list
->elements
;
381 if (position
<= (count
/ 2))
383 /* Shift at most count/2 elements to the left. */
386 list
->offset
= (list
->offset
== 0 ? list
->allocated
: list
->offset
) - 1;
388 i2
= list
->offset
+ position
;
389 if (i2
>= list
->allocated
)
391 /* Here we must have list->offset > 0, hence list->allocated > 0. */
392 size_t i1
= list
->allocated
- 1;
393 i2
-= list
->allocated
;
394 for (i
= list
->offset
; i
< i1
; i
++)
395 elements
[i
] = elements
[i
+ 1];
396 elements
[i1
] = elements
[0];
397 for (i
= 0; i
< i2
; i
++)
398 elements
[i
] = elements
[i
+ 1];
402 for (i
= list
->offset
; i
< i2
; i
++)
403 elements
[i
] = elements
[i
+ 1];
409 /* Shift at most (count+1)/2 elements to the right. */
412 i1
= list
->offset
+ position
;
413 i3
= list
->offset
+ count
;
414 if (i1
>= list
->allocated
)
416 i1
-= list
->allocated
;
417 i3
-= list
->allocated
;
418 for (i
= i3
; i
> i1
; i
--)
419 elements
[i
] = elements
[i
- 1];
421 else if (i3
>= list
->allocated
)
423 /* Here we must have list->offset > 0, hence list->allocated > 0. */
424 size_t i2
= list
->allocated
- 1;
425 i3
-= list
->allocated
;
426 for (i
= i3
; i
> 0; i
--)
427 elements
[i
] = elements
[i
- 1];
428 elements
[0] = elements
[i2
];
429 for (i
= i2
; i
> i1
; i
--)
430 elements
[i
] = elements
[i
- 1];
434 for (i
= i3
; i
> i1
; i
--)
435 elements
[i
] = elements
[i
- 1];
439 list
->count
= count
+ 1;
440 return INDEX_TO_NODE (position
);
443 static gl_list_node_t
444 gl_carray_nx_add_before (gl_list_t list
, gl_list_node_t node
, const void *elt
)
446 size_t count
= list
->count
;
447 uintptr_t index
= NODE_TO_INDEX (node
);
449 if (!(index
< count
))
450 /* Invalid argument. */
452 return gl_carray_nx_add_at (list
, index
, elt
);
455 static gl_list_node_t
456 gl_carray_nx_add_after (gl_list_t list
, gl_list_node_t node
, const void *elt
)
458 size_t count
= list
->count
;
459 uintptr_t index
= NODE_TO_INDEX (node
);
461 if (!(index
< count
))
462 /* Invalid argument. */
464 return gl_carray_nx_add_at (list
, index
+ 1, elt
);
468 gl_carray_remove_at (gl_list_t list
, size_t position
)
470 size_t count
= list
->count
;
471 const void **elements
;
473 if (!(position
< count
))
474 /* Invalid argument. */
476 /* Here we know count > 0. */
477 elements
= list
->elements
;
478 if (position
<= ((count
- 1) / 2))
480 /* Shift at most (count-1)/2 elements to the right. */
484 i2
= list
->offset
+ position
;
485 if (i2
>= list
->allocated
)
487 /* Here we must have list->offset > 0, hence list->allocated > 0. */
488 size_t i1
= list
->allocated
- 1;
489 i2
-= list
->allocated
;
490 if (list
->base
.dispose_fn
!= NULL
)
491 list
->base
.dispose_fn (elements
[i2
]);
492 for (i
= i2
; i
> 0; i
--)
493 elements
[i
] = elements
[i
- 1];
494 elements
[0] = elements
[i1
];
495 for (i
= i1
; i
> i0
; i
--)
496 elements
[i
] = elements
[i
- 1];
500 if (list
->base
.dispose_fn
!= NULL
)
501 list
->base
.dispose_fn (elements
[i2
]);
502 for (i
= i2
; i
> i0
; i
--)
503 elements
[i
] = elements
[i
- 1];
507 list
->offset
= (i0
== list
->allocated
? 0 : i0
);
511 /* Shift at most count/2 elements to the left. */
514 i1
= list
->offset
+ position
;
515 i3
= list
->offset
+ count
- 1;
516 if (i1
>= list
->allocated
)
518 i1
-= list
->allocated
;
519 i3
-= list
->allocated
;
520 if (list
->base
.dispose_fn
!= NULL
)
521 list
->base
.dispose_fn (elements
[i1
]);
522 for (i
= i1
; i
< i3
; i
++)
523 elements
[i
] = elements
[i
+ 1];
525 else if (i3
>= list
->allocated
)
527 /* Here we must have list->offset > 0, hence list->allocated > 0. */
528 size_t i2
= list
->allocated
- 1;
529 i3
-= list
->allocated
;
530 if (list
->base
.dispose_fn
!= NULL
)
531 list
->base
.dispose_fn (elements
[i1
]);
532 for (i
= i1
; i
< i2
; i
++)
533 elements
[i
] = elements
[i
+ 1];
534 elements
[i2
] = elements
[0];
535 for (i
= 0; i
< i3
; i
++)
536 elements
[i
] = elements
[i
+ 1];
540 if (list
->base
.dispose_fn
!= NULL
)
541 list
->base
.dispose_fn (elements
[i1
]);
542 for (i
= i1
; i
< i3
; i
++)
543 elements
[i
] = elements
[i
+ 1];
546 list
->count
= count
- 1;
551 gl_carray_remove_node (gl_list_t list
, gl_list_node_t node
)
553 size_t count
= list
->count
;
554 uintptr_t index
= NODE_TO_INDEX (node
);
556 if (!(index
< count
))
557 /* Invalid argument. */
559 return gl_carray_remove_at (list
, index
);
563 gl_carray_remove (gl_list_t list
, const void *elt
)
565 size_t position
= gl_carray_indexof_from_to (list
, 0, list
->count
, elt
);
566 if (position
== (size_t)(-1))
569 return gl_carray_remove_at (list
, position
);
573 gl_carray_list_free (gl_list_t list
)
575 if (list
->elements
!= NULL
)
577 if (list
->base
.dispose_fn
!= NULL
)
579 size_t count
= list
->count
;
583 gl_listelement_dispose_fn dispose
= list
->base
.dispose_fn
;
584 const void **elements
= list
->elements
;
585 size_t i1
= list
->offset
;
586 size_t i3
= list
->offset
+ count
- 1;
588 if (i3
>= list
->allocated
)
590 /* Here we must have list->offset > 0, hence
591 list->allocated > 0. */
592 size_t i2
= list
->allocated
- 1;
595 i3
-= list
->allocated
;
596 for (i
= i1
; i
<= i2
; i
++)
597 dispose (elements
[i
]);
598 for (i
= 0; i
<= i3
; i
++)
599 dispose (elements
[i
]);
605 for (i
= i1
; i
<= i3
; i
++)
606 dispose (elements
[i
]);
610 free (list
->elements
);
615 /* --------------------- gl_list_iterator_t Data Type --------------------- */
617 static gl_list_iterator_t
618 gl_carray_iterator (gl_list_t list
)
620 gl_list_iterator_t result
;
622 result
.vtable
= list
->base
.vtable
;
624 result
.count
= list
->count
;
626 result
.j
= list
->count
;
627 #if defined GCC_LINT || defined lint
635 static gl_list_iterator_t
636 gl_carray_iterator_from_to (gl_list_t list
, size_t start_index
, size_t end_index
)
638 gl_list_iterator_t result
;
640 if (!(start_index
<= end_index
&& end_index
<= list
->count
))
641 /* Invalid arguments. */
643 result
.vtable
= list
->base
.vtable
;
645 result
.count
= list
->count
;
646 result
.i
= start_index
;
647 result
.j
= end_index
;
648 #if defined GCC_LINT || defined lint
657 gl_carray_iterator_next (gl_list_iterator_t
*iterator
,
658 const void **eltp
, gl_list_node_t
*nodep
)
660 gl_list_t list
= iterator
->list
;
661 if (iterator
->count
!= list
->count
)
663 if (iterator
->count
!= list
->count
+ 1)
664 /* Concurrent modifications were done on the list. */
666 /* The last returned element was removed. */
671 if (iterator
->i
< iterator
->j
)
673 size_t i
= list
->offset
+ iterator
->i
;
674 if (i
>= list
->allocated
)
675 i
-= list
->allocated
;
676 *eltp
= list
->elements
[i
];
678 *nodep
= INDEX_TO_NODE (iterator
->i
);
687 gl_carray_iterator_free (gl_list_iterator_t
*iterator
)
691 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
694 gl_carray_sortedlist_indexof_from_to (gl_list_t list
,
695 gl_listelement_compar_fn compar
,
696 size_t low
, size_t high
,
699 if (!(low
<= high
&& high
<= list
->count
))
700 /* Invalid arguments. */
704 /* At each loop iteration, low < high; for indices < low the values
705 are smaller than ELT; for indices >= high the values are greater
706 than ELT. So, if the element occurs in the list, it is at
707 low <= position < high. */
710 size_t mid
= low
+ (high
- low
) / 2; /* low <= mid < high */
714 i_mid
= list
->offset
+ mid
;
715 if (i_mid
>= list
->allocated
)
716 i_mid
-= list
->allocated
;
718 cmp
= compar (list
->elements
[i_mid
], elt
);
726 /* We have an element equal to ELT at index MID. But we need
727 the minimal such index. */
729 /* At each loop iteration, low <= high and
730 compar (list->elements[i_high], elt) == 0,
731 and we know that the first occurrence of the element is at
732 low <= position <= high. */
735 size_t mid2
= low
+ (high
- low
) / 2; /* low <= mid2 < high */
739 i_mid2
= list
->offset
+ mid2
;
740 if (i_mid2
>= list
->allocated
)
741 i_mid2
-= list
->allocated
;
743 cmp2
= compar (list
->elements
[i_mid2
], elt
);
748 /* The list was not sorted. */
761 /* Here low == high. */
767 gl_carray_sortedlist_indexof (gl_list_t list
, gl_listelement_compar_fn compar
,
770 return gl_carray_sortedlist_indexof_from_to (list
, compar
, 0, list
->count
,
774 static gl_list_node_t
775 gl_carray_sortedlist_search_from_to (gl_list_t list
,
776 gl_listelement_compar_fn compar
,
777 size_t low
, size_t high
,
781 gl_carray_sortedlist_indexof_from_to (list
, compar
, low
, high
, elt
);
782 return INDEX_TO_NODE (index
);
785 static gl_list_node_t
786 gl_carray_sortedlist_search (gl_list_t list
, gl_listelement_compar_fn compar
,
790 gl_carray_sortedlist_indexof_from_to (list
, compar
, 0, list
->count
, elt
);
791 return INDEX_TO_NODE (index
);
794 static gl_list_node_t
795 gl_carray_sortedlist_nx_add (gl_list_t list
, gl_listelement_compar_fn compar
,
798 size_t count
= list
->count
;
802 /* At each loop iteration, low <= high; for indices < low the values are
803 smaller than ELT; for indices >= high the values are greater than ELT. */
806 size_t mid
= low
+ (high
- low
) / 2; /* low <= mid < high */
810 i_mid
= list
->offset
+ mid
;
811 if (i_mid
>= list
->allocated
)
812 i_mid
-= list
->allocated
;
814 cmp
= compar (list
->elements
[i_mid
], elt
);
826 return gl_carray_nx_add_at (list
, low
, elt
);
830 gl_carray_sortedlist_remove (gl_list_t list
, gl_listelement_compar_fn compar
,
833 size_t index
= gl_carray_sortedlist_indexof (list
, compar
, elt
);
834 if (index
== (size_t)(-1))
837 return gl_carray_remove_at (list
, index
);
841 const struct gl_list_implementation gl_carray_list_implementation
=
843 gl_carray_nx_create_empty
,
846 gl_carray_node_value
,
847 gl_carray_node_nx_set_value
,
849 gl_carray_previous_node
,
852 gl_carray_search_from_to
,
853 gl_carray_indexof_from_to
,
854 gl_carray_nx_add_first
,
855 gl_carray_nx_add_last
,
856 gl_carray_nx_add_before
,
857 gl_carray_nx_add_after
,
859 gl_carray_remove_node
,
864 gl_carray_iterator_from_to
,
865 gl_carray_iterator_next
,
866 gl_carray_iterator_free
,
867 gl_carray_sortedlist_search
,
868 gl_carray_sortedlist_search_from_to
,
869 gl_carray_sortedlist_indexof
,
870 gl_carray_sortedlist_indexof_from_to
,
871 gl_carray_sortedlist_nx_add
,
872 gl_carray_sortedlist_remove