1 /* Sequential list data type implemented by a circular array.
2 Copyright (C) 2006-2020 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"
28 /* Checked size_t computations. */
31 /* -------------------------- gl_list_t Data Type -------------------------- */
33 /* Concrete gl_list_impl type, valid for this file only. */
36 struct gl_list_impl_base base
;
37 /* An array of ALLOCATED elements, of which the elements
38 OFFSET, (OFFSET + 1) % ALLOCATED, ..., (OFFSET + COUNT - 1) % ALLOCATED
39 are used. 0 <= COUNT <= ALLOCATED. Either OFFSET = ALLOCATED = 0 or
40 0 <= OFFSET < ALLOCATED. */
41 const void **elements
;
47 /* struct gl_list_node_impl doesn't exist here. The pointers are actually
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)
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
)
59 struct gl_list_impl
*list
=
60 (struct gl_list_impl
*) malloc (sizeof (struct gl_list_impl
));
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
;
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
)
86 struct gl_list_impl
*list
=
87 (struct gl_list_impl
*) malloc (sizeof (struct gl_list_impl
));
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
;
99 if (size_overflow_p (xtimes (count
, sizeof (const void *))))
101 list
->elements
= (const void **) malloc (count
* sizeof (const void *));
102 if (list
->elements
== NULL
)
104 memcpy (list
->elements
, contents
, count
* sizeof (const void *));
107 list
->elements
= NULL
;
110 list
->allocated
= count
;
120 gl_carray_size (gl_list_t list
)
126 gl_carray_node_value (gl_list_t list
, gl_list_node_t node
)
128 uintptr_t index
= NODE_TO_INDEX (node
);
131 if (!(index
< list
->count
))
132 /* Invalid argument. */
134 i
= list
->offset
+ index
;
135 if (i
>= list
->allocated
)
136 i
-= list
->allocated
;
137 return list
->elements
[i
];
141 gl_carray_node_nx_set_value (gl_list_t list
, gl_list_node_t node
,
144 uintptr_t index
= NODE_TO_INDEX (node
);
147 if (!(index
< list
->count
))
148 /* Invalid argument. */
150 i
= list
->offset
+ index
;
151 if (i
>= list
->allocated
)
152 i
-= list
->allocated
;
153 list
->elements
[i
] = elt
;
157 static gl_list_node_t
158 gl_carray_next_node (gl_list_t list
, gl_list_node_t node
)
160 uintptr_t index
= NODE_TO_INDEX (node
);
161 if (!(index
< list
->count
))
162 /* Invalid argument. */
165 if (index
< list
->count
)
166 return INDEX_TO_NODE (index
);
171 static gl_list_node_t
172 gl_carray_previous_node (gl_list_t list
, gl_list_node_t node
)
174 uintptr_t index
= NODE_TO_INDEX (node
);
175 if (!(index
< list
->count
))
176 /* Invalid argument. */
179 return INDEX_TO_NODE (index
- 1);
185 gl_carray_get_at (gl_list_t list
, size_t position
)
187 size_t count
= list
->count
;
190 if (!(position
< count
))
191 /* Invalid argument. */
193 i
= list
->offset
+ position
;
194 if (i
>= list
->allocated
)
195 i
-= list
->allocated
;
196 return list
->elements
[i
];
199 static gl_list_node_t
200 gl_carray_nx_set_at (gl_list_t list
, size_t position
, const void *elt
)
202 size_t count
= list
->count
;
205 if (!(position
< count
))
206 /* Invalid argument. */
208 i
= list
->offset
+ position
;
209 if (i
>= list
->allocated
)
210 i
-= list
->allocated
;
211 list
->elements
[i
] = elt
;
212 return INDEX_TO_NODE (position
);
216 gl_carray_indexof_from_to (gl_list_t list
, size_t start_index
, size_t end_index
,
219 size_t count
= list
->count
;
221 if (!(start_index
<= end_index
&& end_index
<= count
))
222 /* Invalid arguments. */
225 if (start_index
< end_index
)
227 gl_listelement_equals_fn equals
= list
->base
.equals_fn
;
228 size_t allocated
= list
->allocated
;
231 i_end
= list
->offset
+ end_index
;
232 if (i_end
>= allocated
)
239 i
= list
->offset
+ start_index
;
240 if (i
>= allocated
) /* can only happen if start_index > 0 */
245 if (equals (elt
, list
->elements
[i
]))
246 return (i
>= list
->offset
? i
: i
+ allocated
) - list
->offset
;
258 i
= list
->offset
+ start_index
;
259 if (i
>= allocated
) /* can only happen if start_index > 0 */
264 if (elt
== list
->elements
[i
])
265 return (i
>= list
->offset
? i
: i
+ allocated
) - list
->offset
;
277 static gl_list_node_t
278 gl_carray_search_from_to (gl_list_t list
, size_t start_index
, size_t end_index
,
281 size_t index
= gl_carray_indexof_from_to (list
, start_index
, end_index
, elt
);
282 return INDEX_TO_NODE (index
);
285 /* Ensure that list->allocated > list->count.
286 Return 0 upon success, -1 upon out-of-memory. */
288 grow (gl_list_t list
)
290 size_t new_allocated
;
294 new_allocated
= xtimes (list
->allocated
, 2);
295 new_allocated
= xsum (new_allocated
, 1);
296 memory_size
= xtimes (new_allocated
, sizeof (const void *));
297 if (size_overflow_p (memory_size
))
298 /* Overflow, would lead to out of memory. */
300 if (list
->offset
> 0 && list
->count
> 0)
302 memory
= (const void **) malloc (memory_size
);
306 if (list
->offset
+ list
->count
> list
->allocated
)
308 memcpy (memory
, &list
->elements
[list
->offset
],
309 (list
->allocated
- list
->offset
) * sizeof (const void *));
310 memcpy (memory
+ (list
->allocated
- list
->offset
), list
->elements
,
311 (list
->offset
+ list
->count
- list
->allocated
)
312 * sizeof (const void *));
316 memcpy (memory
, &list
->elements
[list
->offset
],
317 list
->count
* sizeof (const void *));
318 if (list
->elements
!= NULL
)
319 free (list
->elements
);
323 memory
= (const void **) realloc (list
->elements
, memory_size
);
328 list
->elements
= memory
;
330 list
->allocated
= new_allocated
;
334 static gl_list_node_t
335 gl_carray_nx_add_first (gl_list_t list
, const void *elt
)
337 size_t count
= list
->count
;
339 if (count
== list
->allocated
)
342 list
->offset
= (list
->offset
== 0 ? list
->allocated
: list
->offset
) - 1;
343 list
->elements
[list
->offset
] = elt
;
344 list
->count
= count
+ 1;
345 return INDEX_TO_NODE (0);
348 static gl_list_node_t
349 gl_carray_nx_add_last (gl_list_t list
, const void *elt
)
351 size_t count
= list
->count
;
354 if (count
== list
->allocated
)
357 i
= list
->offset
+ count
;
358 if (i
>= list
->allocated
)
359 i
-= list
->allocated
;
360 list
->elements
[i
] = elt
;
361 list
->count
= count
+ 1;
362 return INDEX_TO_NODE (count
);
365 static gl_list_node_t
366 gl_carray_nx_add_at (gl_list_t list
, size_t position
, const void *elt
)
368 size_t count
= list
->count
;
369 const void **elements
;
371 if (!(position
<= count
))
372 /* Invalid argument. */
374 if (count
== list
->allocated
)
377 elements
= list
->elements
;
378 if (position
<= (count
/ 2))
380 /* Shift at most count/2 elements to the left. */
383 list
->offset
= (list
->offset
== 0 ? list
->allocated
: list
->offset
) - 1;
385 i2
= list
->offset
+ position
;
386 if (i2
>= list
->allocated
)
388 /* Here we must have list->offset > 0, hence list->allocated > 0. */
389 size_t i1
= list
->allocated
- 1;
390 i2
-= list
->allocated
;
391 for (i
= list
->offset
; i
< i1
; i
++)
392 elements
[i
] = elements
[i
+ 1];
393 elements
[i1
] = elements
[0];
394 for (i
= 0; i
< i2
; i
++)
395 elements
[i
] = elements
[i
+ 1];
399 for (i
= list
->offset
; i
< i2
; i
++)
400 elements
[i
] = elements
[i
+ 1];
406 /* Shift at most (count+1)/2 elements to the right. */
409 i1
= list
->offset
+ position
;
410 i3
= list
->offset
+ count
;
411 if (i1
>= list
->allocated
)
413 i1
-= list
->allocated
;
414 i3
-= list
->allocated
;
415 for (i
= i3
; i
> i1
; i
--)
416 elements
[i
] = elements
[i
- 1];
418 else if (i3
>= list
->allocated
)
420 /* Here we must have list->offset > 0, hence list->allocated > 0. */
421 size_t i2
= list
->allocated
- 1;
422 i3
-= list
->allocated
;
423 for (i
= i3
; i
> 0; i
--)
424 elements
[i
] = elements
[i
- 1];
425 elements
[0] = elements
[i2
];
426 for (i
= i2
; i
> i1
; i
--)
427 elements
[i
] = elements
[i
- 1];
431 for (i
= i3
; i
> i1
; i
--)
432 elements
[i
] = elements
[i
- 1];
436 list
->count
= count
+ 1;
437 return INDEX_TO_NODE (position
);
440 static gl_list_node_t
441 gl_carray_nx_add_before (gl_list_t list
, gl_list_node_t node
, const void *elt
)
443 size_t count
= list
->count
;
444 uintptr_t index
= NODE_TO_INDEX (node
);
446 if (!(index
< count
))
447 /* Invalid argument. */
449 return gl_carray_nx_add_at (list
, index
, elt
);
452 static gl_list_node_t
453 gl_carray_nx_add_after (gl_list_t list
, gl_list_node_t node
, const void *elt
)
455 size_t count
= list
->count
;
456 uintptr_t index
= NODE_TO_INDEX (node
);
458 if (!(index
< count
))
459 /* Invalid argument. */
461 return gl_carray_nx_add_at (list
, index
+ 1, elt
);
465 gl_carray_remove_at (gl_list_t list
, size_t position
)
467 size_t count
= list
->count
;
468 const void **elements
;
470 if (!(position
< count
))
471 /* Invalid argument. */
473 /* Here we know count > 0. */
474 elements
= list
->elements
;
475 if (position
<= ((count
- 1) / 2))
477 /* Shift at most (count-1)/2 elements to the right. */
481 i2
= list
->offset
+ position
;
482 if (i2
>= list
->allocated
)
484 /* Here we must have list->offset > 0, hence list->allocated > 0. */
485 size_t i1
= list
->allocated
- 1;
486 i2
-= list
->allocated
;
487 if (list
->base
.dispose_fn
!= NULL
)
488 list
->base
.dispose_fn (elements
[i2
]);
489 for (i
= i2
; i
> 0; i
--)
490 elements
[i
] = elements
[i
- 1];
491 elements
[0] = elements
[i1
];
492 for (i
= i1
; i
> i0
; i
--)
493 elements
[i
] = elements
[i
- 1];
497 if (list
->base
.dispose_fn
!= NULL
)
498 list
->base
.dispose_fn (elements
[i2
]);
499 for (i
= i2
; i
> i0
; i
--)
500 elements
[i
] = elements
[i
- 1];
504 list
->offset
= (i0
== list
->allocated
? 0 : i0
);
508 /* Shift at most count/2 elements to the left. */
511 i1
= list
->offset
+ position
;
512 i3
= list
->offset
+ count
- 1;
513 if (i1
>= list
->allocated
)
515 i1
-= list
->allocated
;
516 i3
-= list
->allocated
;
517 if (list
->base
.dispose_fn
!= NULL
)
518 list
->base
.dispose_fn (elements
[i1
]);
519 for (i
= i1
; i
< i3
; i
++)
520 elements
[i
] = elements
[i
+ 1];
522 else if (i3
>= list
->allocated
)
524 /* Here we must have list->offset > 0, hence list->allocated > 0. */
525 size_t i2
= list
->allocated
- 1;
526 i3
-= list
->allocated
;
527 if (list
->base
.dispose_fn
!= NULL
)
528 list
->base
.dispose_fn (elements
[i1
]);
529 for (i
= i1
; i
< i2
; i
++)
530 elements
[i
] = elements
[i
+ 1];
531 elements
[i2
] = elements
[0];
532 for (i
= 0; i
< i3
; i
++)
533 elements
[i
] = elements
[i
+ 1];
537 if (list
->base
.dispose_fn
!= NULL
)
538 list
->base
.dispose_fn (elements
[i1
]);
539 for (i
= i1
; i
< i3
; i
++)
540 elements
[i
] = elements
[i
+ 1];
543 list
->count
= count
- 1;
548 gl_carray_remove_node (gl_list_t list
, gl_list_node_t node
)
550 size_t count
= list
->count
;
551 uintptr_t index
= NODE_TO_INDEX (node
);
553 if (!(index
< count
))
554 /* Invalid argument. */
556 return gl_carray_remove_at (list
, index
);
560 gl_carray_remove (gl_list_t list
, const void *elt
)
562 size_t position
= gl_carray_indexof_from_to (list
, 0, list
->count
, elt
);
563 if (position
== (size_t)(-1))
566 return gl_carray_remove_at (list
, position
);
570 gl_carray_list_free (gl_list_t list
)
572 if (list
->elements
!= NULL
)
574 if (list
->base
.dispose_fn
!= NULL
)
576 size_t count
= list
->count
;
580 gl_listelement_dispose_fn dispose
= list
->base
.dispose_fn
;
581 const void **elements
= list
->elements
;
582 size_t i1
= list
->offset
;
583 size_t i3
= list
->offset
+ count
- 1;
585 if (i3
>= list
->allocated
)
587 /* Here we must have list->offset > 0, hence
588 list->allocated > 0. */
589 size_t i2
= list
->allocated
- 1;
592 i3
-= list
->allocated
;
593 for (i
= i1
; i
<= i2
; i
++)
594 dispose (elements
[i
]);
595 for (i
= 0; i
<= i3
; i
++)
596 dispose (elements
[i
]);
602 for (i
= i1
; i
<= i3
; i
++)
603 dispose (elements
[i
]);
607 free (list
->elements
);
612 /* --------------------- gl_list_iterator_t Data Type --------------------- */
614 static gl_list_iterator_t
615 gl_carray_iterator (gl_list_t list
)
617 gl_list_iterator_t result
;
619 result
.vtable
= list
->base
.vtable
;
621 result
.count
= list
->count
;
623 result
.j
= list
->count
;
624 #if defined GCC_LINT || defined lint
632 static gl_list_iterator_t
633 gl_carray_iterator_from_to (gl_list_t list
, size_t start_index
, size_t end_index
)
635 gl_list_iterator_t result
;
637 if (!(start_index
<= end_index
&& end_index
<= list
->count
))
638 /* Invalid arguments. */
640 result
.vtable
= list
->base
.vtable
;
642 result
.count
= list
->count
;
643 result
.i
= start_index
;
644 result
.j
= end_index
;
645 #if defined GCC_LINT || defined lint
654 gl_carray_iterator_next (gl_list_iterator_t
*iterator
,
655 const void **eltp
, gl_list_node_t
*nodep
)
657 gl_list_t list
= iterator
->list
;
658 if (iterator
->count
!= list
->count
)
660 if (iterator
->count
!= list
->count
+ 1)
661 /* Concurrent modifications were done on the list. */
663 /* The last returned element was removed. */
668 if (iterator
->i
< iterator
->j
)
670 size_t i
= list
->offset
+ iterator
->i
;
671 if (i
>= list
->allocated
)
672 i
-= list
->allocated
;
673 *eltp
= list
->elements
[i
];
675 *nodep
= INDEX_TO_NODE (iterator
->i
);
684 gl_carray_iterator_free (gl_list_iterator_t
*iterator
)
688 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
691 gl_carray_sortedlist_indexof_from_to (gl_list_t list
,
692 gl_listelement_compar_fn compar
,
693 size_t low
, size_t high
,
696 if (!(low
<= high
&& high
<= list
->count
))
697 /* Invalid arguments. */
701 /* At each loop iteration, low < high; for indices < low the values
702 are smaller than ELT; for indices >= high the values are greater
703 than ELT. So, if the element occurs in the list, it is at
704 low <= position < high. */
707 size_t mid
= low
+ (high
- low
) / 2; /* low <= mid < high */
711 i_mid
= list
->offset
+ mid
;
712 if (i_mid
>= list
->allocated
)
713 i_mid
-= list
->allocated
;
715 cmp
= compar (list
->elements
[i_mid
], elt
);
723 /* We have an element equal to ELT at index MID. But we need
724 the minimal such index. */
726 /* At each loop iteration, low <= high and
727 compar (list->elements[i_high], elt) == 0,
728 and we know that the first occurrence of the element is at
729 low <= position <= high. */
732 size_t mid2
= low
+ (high
- low
) / 2; /* low <= mid2 < high */
736 i_mid2
= list
->offset
+ mid2
;
737 if (i_mid2
>= list
->allocated
)
738 i_mid2
-= list
->allocated
;
740 cmp2
= compar (list
->elements
[i_mid2
], elt
);
745 /* The list was not sorted. */
758 /* Here low == high. */
764 gl_carray_sortedlist_indexof (gl_list_t list
, gl_listelement_compar_fn compar
,
767 return gl_carray_sortedlist_indexof_from_to (list
, compar
, 0, list
->count
,
771 static gl_list_node_t
772 gl_carray_sortedlist_search_from_to (gl_list_t list
,
773 gl_listelement_compar_fn compar
,
774 size_t low
, size_t high
,
778 gl_carray_sortedlist_indexof_from_to (list
, compar
, low
, high
, elt
);
779 return INDEX_TO_NODE (index
);
782 static gl_list_node_t
783 gl_carray_sortedlist_search (gl_list_t list
, gl_listelement_compar_fn compar
,
787 gl_carray_sortedlist_indexof_from_to (list
, compar
, 0, list
->count
, elt
);
788 return INDEX_TO_NODE (index
);
791 static gl_list_node_t
792 gl_carray_sortedlist_nx_add (gl_list_t list
, gl_listelement_compar_fn compar
,
795 size_t count
= list
->count
;
799 /* At each loop iteration, low <= high; for indices < low the values are
800 smaller than ELT; for indices >= high the values are greater than ELT. */
803 size_t mid
= low
+ (high
- low
) / 2; /* low <= mid < high */
807 i_mid
= list
->offset
+ mid
;
808 if (i_mid
>= list
->allocated
)
809 i_mid
-= list
->allocated
;
811 cmp
= compar (list
->elements
[i_mid
], elt
);
823 return gl_carray_nx_add_at (list
, low
, elt
);
827 gl_carray_sortedlist_remove (gl_list_t list
, gl_listelement_compar_fn compar
,
830 size_t index
= gl_carray_sortedlist_indexof (list
, compar
, elt
);
831 if (index
== (size_t)(-1))
834 return gl_carray_remove_at (list
, index
);
838 const struct gl_list_implementation gl_carray_list_implementation
=
840 gl_carray_nx_create_empty
,
843 gl_carray_node_value
,
844 gl_carray_node_nx_set_value
,
846 gl_carray_previous_node
,
849 gl_carray_search_from_to
,
850 gl_carray_indexof_from_to
,
851 gl_carray_nx_add_first
,
852 gl_carray_nx_add_last
,
853 gl_carray_nx_add_before
,
854 gl_carray_nx_add_after
,
856 gl_carray_remove_node
,
861 gl_carray_iterator_from_to
,
862 gl_carray_iterator_next
,
863 gl_carray_iterator_free
,
864 gl_carray_sortedlist_search
,
865 gl_carray_sortedlist_search_from_to
,
866 gl_carray_sortedlist_indexof
,
867 gl_carray_sortedlist_indexof_from_to
,
868 gl_carray_sortedlist_nx_add
,
869 gl_carray_sortedlist_remove