1 /* Sequential list data type implemented by a binary tree.
2 Copyright (C) 2006-2017 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/>. */
18 /* Common code of gl_avltree_list.c, gl_rbtree_list.c,
19 gl_avltreehash_list.c, gl_rbtreehash_list.c. */
22 gl_tree_nx_create_empty (gl_list_implementation_t implementation
,
23 gl_listelement_equals_fn equals_fn
,
24 gl_listelement_hashcode_fn hashcode_fn
,
25 gl_listelement_dispose_fn dispose_fn
,
26 bool allow_duplicates
)
28 struct gl_list_impl
*list
= (struct gl_list_impl
*) malloc (sizeof (struct gl_list_impl
));
33 list
->base
.vtable
= implementation
;
34 list
->base
.equals_fn
= equals_fn
;
35 list
->base
.hashcode_fn
= hashcode_fn
;
36 list
->base
.dispose_fn
= dispose_fn
;
37 list
->base
.allow_duplicates
= allow_duplicates
;
39 list
->table_size
= 11;
41 (gl_hash_entry_t
*) calloc (list
->table_size
, sizeof (gl_hash_entry_t
));
42 if (list
->table
== NULL
)
57 gl_tree_size (gl_list_t list
)
59 return (list
->root
!= NULL
? list
->root
->branch_size
: 0);
63 gl_tree_node_value (gl_list_t list
, gl_list_node_t node
)
69 gl_tree_node_nx_set_value (gl_list_t list
, gl_list_node_t node
, const void *elt
)
72 if (elt
!= node
->value
)
75 (list
->base
.hashcode_fn
!= NULL
76 ? list
->base
.hashcode_fn (elt
)
77 : (size_t)(uintptr_t) elt
);
79 if (new_hashcode
!= node
->h
.hashcode
)
81 remove_from_bucket (list
, node
);
83 node
->h
.hashcode
= new_hashcode
;
84 if (add_to_bucket (list
, node
) < 0)
86 /* Out of memory. We removed node from a bucket but cannot add
87 it to another bucket. In order to avoid inconsistencies, we
88 must remove node entirely from the list. */
89 gl_tree_remove_node_from_tree (list
, node
);
103 static gl_list_node_t _GL_ATTRIBUTE_PURE
104 gl_tree_next_node (gl_list_t list
, gl_list_node_t node
)
106 if (node
->right
!= NULL
)
109 while (node
->left
!= NULL
)
114 while (node
->parent
!= NULL
&& node
->parent
->right
== node
)
121 static gl_list_node_t _GL_ATTRIBUTE_PURE
122 gl_tree_previous_node (gl_list_t list
, gl_list_node_t node
)
124 if (node
->left
!= NULL
)
127 while (node
->right
!= NULL
)
132 while (node
->parent
!= NULL
&& node
->parent
->left
== node
)
139 /* Return the node at the given position < gl_tree_size (list). */
140 static gl_list_node_t _GL_ATTRIBUTE_PURE
141 node_at (gl_list_node_t root
, size_t position
)
143 /* Here we know that root != NULL. */
144 gl_list_node_t node
= root
;
148 if (node
->left
!= NULL
)
150 if (position
< node
->left
->branch_size
)
155 position
-= node
->left
->branch_size
;
165 static const void * _GL_ATTRIBUTE_PURE
166 gl_tree_get_at (gl_list_t list
, size_t position
)
168 gl_list_node_t node
= list
->root
;
170 if (!(node
!= NULL
&& position
< node
->branch_size
))
171 /* Invalid argument. */
173 node
= node_at (node
, position
);
177 static gl_list_node_t
178 gl_tree_nx_set_at (gl_list_t list
, size_t position
, const void *elt
)
180 gl_list_node_t node
= list
->root
;
182 if (!(node
!= NULL
&& position
< node
->branch_size
))
183 /* Invalid argument. */
185 node
= node_at (node
, position
);
187 if (elt
!= node
->value
)
189 size_t new_hashcode
=
190 (list
->base
.hashcode_fn
!= NULL
191 ? list
->base
.hashcode_fn (elt
)
192 : (size_t)(uintptr_t) elt
);
194 if (new_hashcode
!= node
->h
.hashcode
)
196 remove_from_bucket (list
, node
);
198 node
->h
.hashcode
= new_hashcode
;
199 if (add_to_bucket (list
, node
) < 0)
201 /* Out of memory. We removed node from a bucket but cannot add
202 it to another bucket. In order to avoid inconsistencies, we
203 must remove node entirely from the list. */
204 gl_tree_remove_node_from_tree (list
, node
);
220 static gl_list_node_t
221 gl_tree_search_from_to (gl_list_t list
, size_t start_index
, size_t end_index
,
224 if (!(start_index
<= end_index
225 && end_index
<= (list
->root
!= NULL
? list
->root
->branch_size
: 0)))
226 /* Invalid arguments. */
229 gl_listelement_equals_fn equals
= list
->base
.equals_fn
;
230 /* Iterate across all elements. */
231 gl_list_node_t node
= list
->root
;
233 iterstack_item_t
*stack_ptr
= &stack
[0];
236 if (start_index
== 0)
238 /* Consider all elements. */
241 /* Descend on left branch. */
246 stack_ptr
->node
= node
;
247 stack_ptr
->rightp
= 0;
251 /* Climb up again. */
254 if (stack_ptr
== &stack
[0])
257 if (!stack_ptr
->rightp
)
260 node
= stack_ptr
->node
;
261 /* Test against current element. */
262 if (equals
!= NULL
? equals (elt
, node
->value
) : elt
== node
->value
)
265 if (index
>= end_index
)
267 /* Descend on right branch. */
268 stack_ptr
->rightp
= 1;
275 /* Consider only elements at indices >= start_index.
276 In this case, rightp contains the difference between the start_index
277 for the parent node and the one for the child node (0 when the child
278 node is the parent's left child, > 0 when the child is the parent's
282 /* Descend on left branch. */
287 if (node
->branch_size
<= start_index
)
289 stack_ptr
->node
= node
;
290 stack_ptr
->rightp
= 0;
294 /* Climb up again. */
297 if (stack_ptr
== &stack
[0])
300 if (!stack_ptr
->rightp
)
302 start_index
+= stack_ptr
->rightp
;
304 node
= stack_ptr
->node
;
306 size_t left_branch_size1
=
307 (node
->left
!= NULL
? node
->left
->branch_size
: 0) + 1;
308 if (start_index
< left_branch_size1
)
310 /* Test against current element. */
311 if (equals
!= NULL
? equals (elt
, node
->value
) : elt
== node
->value
)
313 /* Now that we have considered all indices < left_branch_size1,
314 we can increment start_index. */
315 start_index
= left_branch_size1
;
318 if (index
>= end_index
)
320 /* Descend on right branch. */
321 start_index
-= left_branch_size1
;
322 stack_ptr
->rightp
= left_branch_size1
;
332 gl_tree_indexof_from_to (gl_list_t list
, size_t start_index
, size_t end_index
,
335 if (!(start_index
<= end_index
336 && end_index
<= (list
->root
!= NULL
? list
->root
->branch_size
: 0)))
337 /* Invalid arguments. */
340 gl_listelement_equals_fn equals
= list
->base
.equals_fn
;
341 /* Iterate across all elements. */
342 gl_list_node_t node
= list
->root
;
344 iterstack_item_t
*stack_ptr
= &stack
[0];
347 if (start_index
== 0)
349 /* Consider all elements. */
352 /* Descend on left branch. */
357 stack_ptr
->node
= node
;
358 stack_ptr
->rightp
= 0;
362 /* Climb up again. */
365 if (stack_ptr
== &stack
[0])
368 if (!stack_ptr
->rightp
)
371 node
= stack_ptr
->node
;
372 /* Test against current element. */
373 if (equals
!= NULL
? equals (elt
, node
->value
) : elt
== node
->value
)
376 if (index
>= end_index
)
378 /* Descend on right branch. */
379 stack_ptr
->rightp
= 1;
386 /* Consider only elements at indices >= start_index.
387 In this case, rightp contains the difference between the start_index
388 for the parent node and the one for the child node (0 when the child
389 node is the parent's left child, > 0 when the child is the parent's
393 /* Descend on left branch. */
398 if (node
->branch_size
<= start_index
)
400 stack_ptr
->node
= node
;
401 stack_ptr
->rightp
= 0;
405 /* Climb up again. */
408 if (stack_ptr
== &stack
[0])
411 if (!stack_ptr
->rightp
)
413 start_index
+= stack_ptr
->rightp
;
415 node
= stack_ptr
->node
;
417 size_t left_branch_size1
=
418 (node
->left
!= NULL
? node
->left
->branch_size
: 0) + 1;
419 if (start_index
< left_branch_size1
)
421 /* Test against current element. */
422 if (equals
!= NULL
? equals (elt
, node
->value
) : elt
== node
->value
)
424 /* Now that we have considered all indices < left_branch_size1,
425 we can increment start_index. */
426 start_index
= left_branch_size1
;
429 if (index
>= end_index
)
431 /* Descend on right branch. */
432 start_index
-= left_branch_size1
;
433 stack_ptr
->rightp
= left_branch_size1
;
444 static gl_list_node_t
445 gl_tree_nx_add_at (gl_list_t list
, size_t position
, const void *elt
)
447 size_t count
= (list
->root
!= NULL
? list
->root
->branch_size
: 0);
449 if (!(position
<= count
))
450 /* Invalid argument. */
452 if (position
== count
)
453 return gl_tree_nx_add_last (list
, elt
);
455 return gl_tree_nx_add_before (list
, node_at (list
->root
, position
), elt
);
459 gl_tree_remove_node (gl_list_t list
, gl_list_node_t node
)
462 /* Remove node from the hash table.
463 Note that this is only possible _before_ the node is removed from the
464 tree structure, because remove_from_bucket() uses node_position(). */
465 remove_from_bucket (list
, node
);
468 gl_tree_remove_node_from_tree (list
, node
);
470 if (list
->base
.dispose_fn
!= NULL
)
471 list
->base
.dispose_fn (node
->value
);
477 gl_tree_remove_at (gl_list_t list
, size_t position
)
479 gl_list_node_t node
= list
->root
;
481 if (!(node
!= NULL
&& position
< node
->branch_size
))
482 /* Invalid argument. */
484 node
= node_at (node
, position
);
485 return gl_tree_remove_node (list
, node
);
489 gl_tree_remove (gl_list_t list
, const void *elt
)
491 if (list
->root
!= NULL
)
493 gl_list_node_t node
=
494 gl_tree_search_from_to (list
, 0, list
->root
->branch_size
, elt
);
497 return gl_tree_remove_node (list
, node
);
505 gl_tree_list_free (gl_list_t list
)
507 /* Iterate across all elements in post-order. */
508 gl_list_node_t node
= list
->root
;
510 iterstack_item_t
*stack_ptr
= &stack
[0];
514 /* Descend on left branch. */
519 stack_ptr
->node
= node
;
520 stack_ptr
->rightp
= false;
524 /* Climb up again. */
527 if (stack_ptr
== &stack
[0])
530 node
= stack_ptr
->node
;
531 if (!stack_ptr
->rightp
)
533 /* Free the current node. */
534 if (list
->base
.dispose_fn
!= NULL
)
535 list
->base
.dispose_fn (node
->value
);
538 /* Descend on right branch. */
539 stack_ptr
->rightp
= true;
549 /* --------------------- gl_list_iterator_t Data Type --------------------- */
551 static gl_list_iterator_t
552 gl_tree_iterator (gl_list_t list
)
554 gl_list_iterator_t result
;
557 result
.vtable
= list
->base
.vtable
;
559 /* Start node is the leftmost node. */
562 while (node
->left
!= NULL
)
565 /* End point is past the rightmost node. */
567 #if defined GCC_LINT || defined lint
576 static gl_list_iterator_t
577 gl_tree_iterator_from_to (gl_list_t list
, size_t start_index
, size_t end_index
)
579 size_t count
= (list
->root
!= NULL
? list
->root
->branch_size
: 0);
580 gl_list_iterator_t result
;
582 if (!(start_index
<= end_index
&& end_index
<= count
))
583 /* Invalid arguments. */
585 result
.vtable
= list
->base
.vtable
;
587 /* Start node is the node at position start_index. */
588 result
.p
= (start_index
< count
? node_at (list
->root
, start_index
) : NULL
);
589 /* End point is the node at position end_index. */
590 result
.q
= (end_index
< count
? node_at (list
->root
, end_index
) : NULL
);
591 #if defined GCC_LINT || defined lint
601 gl_tree_iterator_next (gl_list_iterator_t
*iterator
,
602 const void **eltp
, gl_list_node_t
*nodep
)
604 if (iterator
->p
!= iterator
->q
)
606 gl_list_node_t node
= (gl_list_node_t
) iterator
->p
;
610 /* Advance to the next node. */
611 if (node
->right
!= NULL
)
614 while (node
->left
!= NULL
)
619 while (node
->parent
!= NULL
&& node
->parent
->right
== node
)
631 gl_tree_iterator_free (gl_list_iterator_t
*iterator
)
635 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
637 static gl_list_node_t
638 gl_tree_sortedlist_search (gl_list_t list
, gl_listelement_compar_fn compar
,
643 for (node
= list
->root
; node
!= NULL
; )
645 int cmp
= compar (node
->value
, elt
);
653 /* We have an element equal to ELT. But we need the leftmost such
655 gl_list_node_t found
= node
;
657 for (; node
!= NULL
; )
659 int cmp2
= compar (node
->value
, elt
);
664 /* The list was not sorted. */
678 static gl_list_node_t
679 gl_tree_sortedlist_search_from_to (gl_list_t list
,
680 gl_listelement_compar_fn compar
,
681 size_t low
, size_t high
,
687 && high
<= (list
->root
!= NULL
? list
->root
->branch_size
: 0)))
688 /* Invalid arguments. */
691 for (node
= list
->root
; node
!= NULL
; )
693 size_t left_branch_size
=
694 (node
->left
!= NULL
? node
->left
->branch_size
: 0);
696 if (low
> left_branch_size
)
698 low
-= left_branch_size
+ 1;
699 high
-= left_branch_size
+ 1;
702 else if (high
<= left_branch_size
)
706 /* Here low <= left_branch_size < high. */
707 int cmp
= compar (node
->value
, elt
);
712 high
-= left_branch_size
+ 1;
719 /* We have an element equal to ELT. But we need the leftmost
721 gl_list_node_t found
= node
;
723 for (; node
!= NULL
; )
725 size_t left_branch_size2
=
726 (node
->left
!= NULL
? node
->left
->branch_size
: 0);
728 if (low
> left_branch_size2
)
730 low
-= left_branch_size2
+ 1;
735 /* Here low <= left_branch_size2. */
736 int cmp2
= compar (node
->value
, elt
);
744 /* The list was not sorted. */
761 gl_tree_sortedlist_indexof (gl_list_t list
, gl_listelement_compar_fn compar
,
767 for (node
= list
->root
, position
= 0; node
!= NULL
; )
769 int cmp
= compar (node
->value
, elt
);
773 if (node
->left
!= NULL
)
774 position
+= node
->left
->branch_size
;
782 /* We have an element equal to ELT. But we need the leftmost such
784 size_t found_position
=
785 position
+ (node
->left
!= NULL
? node
->left
->branch_size
: 0);
787 for (; node
!= NULL
; )
789 int cmp2
= compar (node
->value
, elt
);
793 if (node
->left
!= NULL
)
794 position
+= node
->left
->branch_size
;
799 /* The list was not sorted. */
805 + (node
->left
!= NULL
? node
->left
->branch_size
: 0);
809 return found_position
;
816 gl_tree_sortedlist_indexof_from_to (gl_list_t list
,
817 gl_listelement_compar_fn compar
,
818 size_t low
, size_t high
,
825 && high
<= (list
->root
!= NULL
? list
->root
->branch_size
: 0)))
826 /* Invalid arguments. */
829 for (node
= list
->root
, position
= 0; node
!= NULL
; )
831 size_t left_branch_size
=
832 (node
->left
!= NULL
? node
->left
->branch_size
: 0);
834 if (low
> left_branch_size
)
836 low
-= left_branch_size
+ 1;
837 high
-= left_branch_size
+ 1;
838 position
+= left_branch_size
+ 1;
841 else if (high
<= left_branch_size
)
845 /* Here low <= left_branch_size < high. */
846 int cmp
= compar (node
->value
, elt
);
851 high
-= left_branch_size
+ 1;
852 position
+= left_branch_size
+ 1;
859 /* We have an element equal to ELT. But we need the leftmost
861 size_t found_position
=
862 position
+ (node
->left
!= NULL
? node
->left
->branch_size
: 0);
864 for (; node
!= NULL
; )
866 size_t left_branch_size2
=
867 (node
->left
!= NULL
? node
->left
->branch_size
: 0);
869 if (low
> left_branch_size2
)
871 low
-= left_branch_size2
+ 1;
876 /* Here low <= left_branch_size2. */
877 int cmp2
= compar (node
->value
, elt
);
881 position
+= left_branch_size2
+ 1;
885 /* The list was not sorted. */
889 found_position
= position
+ left_branch_size2
;
894 return found_position
;
901 static gl_list_node_t
902 gl_tree_sortedlist_nx_add (gl_list_t list
, gl_listelement_compar_fn compar
,
905 gl_list_node_t node
= list
->root
;
908 return gl_tree_nx_add_first (list
, elt
);
912 int cmp
= compar (node
->value
, elt
);
916 if (node
->right
== NULL
)
917 return gl_tree_nx_add_after (list
, node
, elt
);
922 if (node
->left
== NULL
)
923 return gl_tree_nx_add_before (list
, node
, elt
);
927 return gl_tree_nx_add_before (list
, node
, elt
);
932 gl_tree_sortedlist_remove (gl_list_t list
, gl_listelement_compar_fn compar
,
935 gl_list_node_t node
= gl_tree_sortedlist_search (list
, compar
, elt
);
937 return gl_tree_remove_node (list
, node
);