1
/* Sequential list data type implemented by a binary tree.
2
Copyright (C) 2006-2007 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. */
19
/* Common code of gl_rbtree_list.c and gl_rbtreehash_list.c. */
21
/* -------------------------- gl_list_t Data Type -------------------------- */
23
/* Create a subtree for count >= 1 elements.
24
Its black-height bh is passed as argument, with
25
2^bh - 1 <= count <= 2^(bh+1) - 1. bh == 0 implies count == 1.
26
Its height is h where 2^(h-1) <= count <= 2^h - 1. */
28
create_subtree_with_contents (unsigned int bh,
29
size_t count, const void **contents)
31
size_t half1 = (count - 1) / 2;
32
size_t half2 = count / 2;
33
/* Note: half1 + half2 = count - 1. */
34
gl_list_node_t node = XMALLOC (struct gl_list_node_impl);
38
/* half1 > 0 implies count > 1, implies bh >= 1, implies
39
2^(bh-1) - 1 <= half1 <= 2^bh - 1. */
41
create_subtree_with_contents (bh - 1, half1, contents);
42
node->left->parent = node;
47
node->value = contents[half1];
51
/* half2 > 0 implies count > 1, implies bh >= 1, implies
52
2^(bh-1) - 1 <= half2 <= 2^bh - 1. */
54
create_subtree_with_contents (bh - 1, half2, contents + half1 + 1);
55
node->right->parent = node;
60
node->color = (bh == 0 ? RED : BLACK);
62
node->branch_size = count;
68
gl_tree_create (gl_list_implementation_t implementation,
69
gl_listelement_equals_fn equals_fn,
70
gl_listelement_hashcode_fn hashcode_fn,
71
gl_listelement_dispose_fn dispose_fn,
72
bool allow_duplicates,
73
size_t count, const void **contents)
75
struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
77
list->base.vtable = implementation;
78
list->base.equals_fn = equals_fn;
79
list->base.hashcode_fn = hashcode_fn;
80
list->base.dispose_fn = dispose_fn;
81
list->base.allow_duplicates = allow_duplicates;
84
size_t estimate = xsum (count, count / 2); /* 1.5 * count */
87
list->table_size = next_prime (estimate);
88
list->table = XCALLOC (list->table_size, gl_hash_entry_t);
93
/* Assuming 2^bh - 1 <= count <= 2^(bh+1) - 2, we create a tree whose
94
upper bh levels are black, and only the partially present lowest
99
for (n = count + 1, bh = 0; n > 1; n = n >> 1)
103
list->root = create_subtree_with_contents (bh, count, contents);
104
list->root->parent = NULL;
107
/* Now that the tree is built, node_position() works. Now we can
108
add the nodes to the hash table. */
109
add_nodes_to_buckets (list);
118
/* Rotate left a subtree.
126
Change the tree structure, update the branch sizes.
127
The caller must update the colors and register D as child of its parent. */
128
static inline gl_list_node_t
129
rotate_left (gl_list_node_t b_node, gl_list_node_t d_node)
131
gl_list_node_t a_node = b_node->left;
132
gl_list_node_t c_node = d_node->left;
133
gl_list_node_t e_node = d_node->right;
135
b_node->right = c_node;
136
d_node->left = b_node;
138
d_node->parent = b_node->parent;
139
b_node->parent = d_node;
141
c_node->parent = b_node;
143
b_node->branch_size =
144
(a_node != NULL ? a_node->branch_size : 0)
145
+ 1 + (c_node != NULL ? c_node->branch_size : 0);
146
d_node->branch_size =
147
b_node->branch_size + 1 + (e_node != NULL ? e_node->branch_size : 0);
152
/* Rotate right a subtree.
160
Change the tree structure, update the branch sizes.
161
The caller must update the colors and register B as child of its parent. */
162
static inline gl_list_node_t
163
rotate_right (gl_list_node_t b_node, gl_list_node_t d_node)
165
gl_list_node_t a_node = b_node->left;
166
gl_list_node_t c_node = b_node->right;
167
gl_list_node_t e_node = d_node->right;
169
d_node->left = c_node;
170
b_node->right = d_node;
172
b_node->parent = d_node->parent;
173
d_node->parent = b_node;
175
c_node->parent = d_node;
177
d_node->branch_size =
178
(c_node != NULL ? c_node->branch_size : 0)
179
+ 1 + (e_node != NULL ? e_node->branch_size : 0);
180
b_node->branch_size =
181
(a_node != NULL ? a_node->branch_size : 0) + 1 + d_node->branch_size;
186
/* Ensure the tree is balanced, after an insertion operation.
187
Also assigns node->color.
188
parent is the given node's parent, known to be non-NULL. */
190
rebalance_after_add (gl_list_t list, gl_list_node_t node, gl_list_node_t parent)
194
/* At this point, parent = node->parent != NULL.
195
Think of node->color being RED (although node->color is not yet
197
gl_list_node_t grandparent;
198
gl_list_node_t uncle;
200
if (parent->color == BLACK)
202
/* A RED color for node is acceptable. */
207
grandparent = parent->parent;
208
/* Since parent is RED, we know that
209
grandparent is != NULL and colored BLACK. */
211
if (grandparent->left == parent)
212
uncle = grandparent->right;
213
else if (grandparent->right == parent)
214
uncle = grandparent->left;
218
if (uncle != NULL && uncle->color == RED)
220
/* Change grandparent from BLACK to RED, and
221
change parent and uncle from RED to BLACK.
222
This makes it acceptable for node to be RED. */
224
parent->color = uncle->color = BLACK;
229
/* grandparent and uncle are BLACK. parent is RED. node wants
231
In this case, recoloring is not sufficient. Need to perform
232
one or two rotations. */
233
gl_list_node_t *grandparentp;
235
if (grandparent->parent == NULL)
236
grandparentp = &list->root;
237
else if (grandparent->parent->left == grandparent)
238
grandparentp = &grandparent->parent->left;
239
else if (grandparent->parent->right == grandparent)
240
grandparentp = &grandparent->parent->right;
244
if (grandparent->left == parent)
246
if (parent->right == node)
248
/* Rotation between node and parent. */
249
grandparent->left = rotate_left (parent, node);
251
parent = grandparent->left;
253
/* grandparent and uncle are BLACK. parent and node want to be
254
RED. parent = grandparent->left. node = parent->left.
259
parent uncle --> node grandparent
265
*grandparentp = rotate_right (parent, grandparent);
266
parent->color = BLACK;
267
node->color = grandparent->color = RED;
269
else /* grandparent->right == parent */
271
if (parent->left == node)
273
/* Rotation between node and parent. */
274
grandparent->right = rotate_right (node, parent);
276
parent = grandparent->right;
278
/* grandparent and uncle are BLACK. parent and node want to be
279
RED. parent = grandparent->right. node = parent->right.
284
uncle parent --> grandparent node
290
*grandparentp = rotate_left (grandparent, parent);
291
parent->color = BLACK;
292
node->color = grandparent->color = RED;
297
/* Start again with a new (node, parent) pair. */
298
parent = node->parent;
302
/* Change node's color from RED to BLACK. This increases the
303
tree's black-height. */
310
/* Ensure the tree is balanced, after a deletion operation.
311
CHILD was a grandchild of PARENT and is now its child. Between them,
312
a black node was removed. CHILD is also black, or NULL.
313
(CHILD can also be NULL. But PARENT is non-NULL.) */
315
rebalance_after_remove (gl_list_t list, gl_list_node_t child, gl_list_node_t parent)
319
/* At this point, we reduced the black-height of the CHILD subtree by 1.
320
To make up, either look for a possibility to turn a RED to a BLACK
321
node, or try to reduce the black-height tree of CHILD's sibling
323
gl_list_node_t *parentp;
325
if (parent->parent == NULL)
326
parentp = &list->root;
327
else if (parent->parent->left == parent)
328
parentp = &parent->parent->left;
329
else if (parent->parent->right == parent)
330
parentp = &parent->parent->right;
334
if (parent->left == child)
336
gl_list_node_t sibling = parent->right;
337
/* sibling's black-height is >= 1. In particular,
346
if (sibling->color == RED)
348
/* sibling is RED, hence parent is BLACK and sibling's children
349
are non-NULL and BLACK.
354
child sibling --> parent SR
360
*parentp = rotate_left (parent, sibling);
362
sibling->color = BLACK;
364
/* Concentrate on the subtree of parent. The new sibling is
365
one of the old sibling's children, and known to be BLACK. */
366
parentp = &sibling->left;
367
sibling = parent->right;
369
/* Now we know that sibling is BLACK.
376
if (sibling->right != NULL && sibling->right->color == RED)
382
child sibling --> parent SR
388
*parentp = rotate_left (parent, sibling);
389
sibling->color = parent->color;
390
parent->color = BLACK;
391
sibling->right->color = BLACK;
394
else if (sibling->left != NULL && sibling->left->color == RED)
400
child sibling --> child SL
409
where SLL, SLR, SR are all black.
411
parent->right = rotate_right (sibling->left, sibling);
412
/* Change sibling from BLACK to RED and SL from RED to BLACK. */
413
sibling->color = RED;
414
sibling = parent->right;
415
sibling->color = BLACK;
417
/* Now do as in the previous case. */
418
*parentp = rotate_left (parent, sibling);
419
sibling->color = parent->color;
420
parent->color = BLACK;
421
sibling->right->color = BLACK;
426
if (parent->color == BLACK)
428
/* Change sibling from BLACK to RED. Then the entire
429
subtree at parent has decreased its black-height.
433
child sibling --> child sibling
436
sibling->color = RED;
442
/* Change parent from RED to BLACK, but compensate by
443
changing sibling from BLACK to RED.
447
child sibling --> child sibling
450
parent->color = BLACK;
451
sibling->color = RED;
456
else if (parent->right == child)
458
gl_list_node_t sibling = parent->left;
459
/* sibling's black-height is >= 1. In particular,
468
if (sibling->color == RED)
470
/* sibling is RED, hence parent is BLACK and sibling's children
471
are non-NULL and BLACK.
476
sibling child --> SR parent
482
*parentp = rotate_right (sibling, parent);
484
sibling->color = BLACK;
486
/* Concentrate on the subtree of parent. The new sibling is
487
one of the old sibling's children, and known to be BLACK. */
488
parentp = &sibling->right;
489
sibling = parent->left;
491
/* Now we know that sibling is BLACK.
498
if (sibling->left != NULL && sibling->left->color == RED)
504
sibling child --> SL parent
510
*parentp = rotate_right (sibling, parent);
511
sibling->color = parent->color;
512
parent->color = BLACK;
513
sibling->left->color = BLACK;
516
else if (sibling->right != NULL && sibling->right->color == RED)
522
sibling child --> SR child
531
where SL, SRL, SRR are all black.
533
parent->left = rotate_left (sibling, sibling->right);
534
/* Change sibling from BLACK to RED and SL from RED to BLACK. */
535
sibling->color = RED;
536
sibling = parent->left;
537
sibling->color = BLACK;
539
/* Now do as in the previous case. */
540
*parentp = rotate_right (sibling, parent);
541
sibling->color = parent->color;
542
parent->color = BLACK;
543
sibling->left->color = BLACK;
548
if (parent->color == BLACK)
550
/* Change sibling from BLACK to RED. Then the entire
551
subtree at parent has decreased its black-height.
555
sibling child --> sibling child
558
sibling->color = RED;
564
/* Change parent from RED to BLACK, but compensate by
565
changing sibling from BLACK to RED.
569
sibling child --> sibling child
572
parent->color = BLACK;
573
sibling->color = RED;
581
/* Start again with a new (child, parent) pair. */
582
parent = child->parent;
584
#if 0 /* Already handled. */
585
if (child != NULL && child->color == RED)
587
child->color = BLACK;
597
static gl_list_node_t
598
gl_tree_add_first (gl_list_t list, const void *elt)
600
/* Create new node. */
601
gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
603
new_node->left = NULL;
604
new_node->right = NULL;
605
new_node->branch_size = 1;
606
new_node->value = elt;
608
new_node->h.hashcode =
609
(list->base.hashcode_fn != NULL
610
? list->base.hashcode_fn (new_node->value)
611
: (size_t)(uintptr_t) new_node->value);
614
/* Add it to the tree. */
615
if (list->root == NULL)
617
new_node->color = BLACK;
618
list->root = new_node;
619
new_node->parent = NULL;
625
for (node = list->root; node->left != NULL; )
628
node->left = new_node;
629
new_node->parent = node;
631
/* Update branch_size fields of the parent nodes. */
635
for (p = node; p != NULL; p = p->parent)
639
/* Color and rebalance. */
640
rebalance_after_add (list, new_node, node);
644
/* Add node to the hash table.
645
Note that this is only possible _after_ the node has been added to the
646
tree structure, because add_to_bucket() uses node_position(). */
647
add_to_bucket (list, new_node);
648
hash_resize_after_add (list);
654
static gl_list_node_t
655
gl_tree_add_last (gl_list_t list, const void *elt)
657
/* Create new node. */
658
gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
660
new_node->left = NULL;
661
new_node->right = NULL;
662
new_node->branch_size = 1;
663
new_node->value = elt;
665
new_node->h.hashcode =
666
(list->base.hashcode_fn != NULL
667
? list->base.hashcode_fn (new_node->value)
668
: (size_t)(uintptr_t) new_node->value);
671
/* Add it to the tree. */
672
if (list->root == NULL)
674
new_node->color = BLACK;
675
list->root = new_node;
676
new_node->parent = NULL;
682
for (node = list->root; node->right != NULL; )
685
node->right = new_node;
686
new_node->parent = node;
688
/* Update branch_size fields of the parent nodes. */
692
for (p = node; p != NULL; p = p->parent)
696
/* Color and rebalance. */
697
rebalance_after_add (list, new_node, node);
701
/* Add node to the hash table.
702
Note that this is only possible _after_ the node has been added to the
703
tree structure, because add_to_bucket() uses node_position(). */
704
add_to_bucket (list, new_node);
705
hash_resize_after_add (list);
711
static gl_list_node_t
712
gl_tree_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
714
/* Create new node. */
715
gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
717
new_node->left = NULL;
718
new_node->right = NULL;
719
new_node->branch_size = 1;
720
new_node->value = elt;
722
new_node->h.hashcode =
723
(list->base.hashcode_fn != NULL
724
? list->base.hashcode_fn (new_node->value)
725
: (size_t)(uintptr_t) new_node->value);
728
/* Add it to the tree. */
729
if (node->left == NULL)
730
node->left = new_node;
733
for (node = node->left; node->right != NULL; )
735
node->right = new_node;
737
new_node->parent = node;
739
/* Update branch_size fields of the parent nodes. */
743
for (p = node; p != NULL; p = p->parent)
747
/* Color and rebalance. */
748
rebalance_after_add (list, new_node, node);
751
/* Add node to the hash table.
752
Note that this is only possible _after_ the node has been added to the
753
tree structure, because add_to_bucket() uses node_position(). */
754
add_to_bucket (list, new_node);
755
hash_resize_after_add (list);
761
static gl_list_node_t
762
gl_tree_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
764
/* Create new node. */
765
gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
767
new_node->left = NULL;
768
new_node->right = NULL;
769
new_node->branch_size = 1;
770
new_node->value = elt;
772
new_node->h.hashcode =
773
(list->base.hashcode_fn != NULL
774
? list->base.hashcode_fn (new_node->value)
775
: (size_t)(uintptr_t) new_node->value);
778
/* Add it to the tree. */
779
if (node->right == NULL)
780
node->right = new_node;
783
for (node = node->right; node->left != NULL; )
785
node->left = new_node;
787
new_node->parent = node;
789
/* Update branch_size fields of the parent nodes. */
793
for (p = node; p != NULL; p = p->parent)
797
/* Color and rebalance. */
798
rebalance_after_add (list, new_node, node);
801
/* Add node to the hash table.
802
Note that this is only possible _after_ the node has been added to the
803
tree structure, because add_to_bucket() uses node_position(). */
804
add_to_bucket (list, new_node);
805
hash_resize_after_add (list);
812
gl_tree_remove_node (gl_list_t list, gl_list_node_t node)
814
gl_list_node_t parent;
817
/* Remove node from the hash table.
818
Note that this is only possible _before_ the node is removed from the
819
tree structure, because remove_from_bucket() uses node_position(). */
820
remove_from_bucket (list, node);
823
parent = node->parent;
825
if (node->left == NULL)
827
/* Replace node with node->right. */
828
gl_list_node_t child = node->right;
832
child->parent = parent;
833
/* Since node->left == NULL, child must be RED and of height 1,
834
hence node must have been BLACK. Recolor the child. */
835
child->color = BLACK;
841
if (parent->left == node)
842
parent->left = child;
843
else /* parent->right == node */
844
parent->right = child;
846
/* Update branch_size fields of the parent nodes. */
850
for (p = parent; p != NULL; p = p->parent)
854
if (child == NULL && node->color == BLACK)
855
rebalance_after_remove (list, child, parent);
858
else if (node->right == NULL)
860
/* It is not absolutely necessary to treat this case. But the more
861
general case below is more complicated, hence slower. */
862
/* Replace node with node->left. */
863
gl_list_node_t child = node->left;
865
child->parent = parent;
866
/* Since node->right == NULL, child must be RED and of height 1,
867
hence node must have been BLACK. Recolor the child. */
868
child->color = BLACK;
873
if (parent->left == node)
874
parent->left = child;
875
else /* parent->right == node */
876
parent->right = child;
878
/* Update branch_size fields of the parent nodes. */
882
for (p = parent; p != NULL; p = p->parent)
889
/* Replace node with the rightmost element of the node->left subtree. */
890
gl_list_node_t subst;
891
gl_list_node_t subst_parent;
892
gl_list_node_t child;
893
color_t removed_color;
895
for (subst = node->left; subst->right != NULL; )
896
subst = subst->right;
898
subst_parent = subst->parent;
902
removed_color = subst->color;
904
/* The case subst_parent == node is special: If we do nothing special,
905
we get confusion about node->left, subst->left and child->parent.
907
<==> The 'for' loop above terminated immediately.
908
<==> subst == subst_parent->left
909
[otherwise subst == subst_parent->right]
910
In this case, we would need to first set
911
child->parent = node; node->left = child;
912
and later - when we copy subst into node's position - again
913
child->parent = subst; subst->left = child;
914
Altogether a no-op. */
915
if (subst_parent != node)
918
child->parent = subst_parent;
919
subst_parent->right = child;
922
/* Update branch_size fields of the parent nodes. */
926
for (p = subst_parent; p != NULL; p = p->parent)
930
/* Copy subst into node's position.
931
(This is safer than to copy subst's value into node, keep node in
932
place, and free subst.) */
933
if (subst_parent != node)
935
subst->left = node->left;
936
subst->left->parent = subst;
938
subst->right = node->right;
939
subst->right->parent = subst;
940
subst->color = node->color;
941
subst->branch_size = node->branch_size;
942
subst->parent = parent;
945
else if (parent->left == node)
946
parent->left = subst;
947
else /* parent->right == node */
948
parent->right = subst;
950
if (removed_color == BLACK)
952
if (child != NULL && child->color == RED)
953
/* Recolor the child. */
954
child->color = BLACK;
956
/* Rebalancing starts at child's parent, that is subst_parent -
957
except when subst_parent == node. In this case, we need to use
958
its replacement, subst. */
959
rebalance_after_remove (list, child,
960
subst_parent != node ? subst_parent : subst);
964
if (list->base.dispose_fn != NULL)
965
list->base.dispose_fn (node->value);
added
removed
gnulib/lib/gl_anyrbtree_list2.h
