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 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 <http://www.gnu.org/licenses/>. */
18 /* Common code of gl_rbtree_list.c and gl_rbtreehash_list.c. */
20 /* -------------------------- gl_list_t Data Type -------------------------- */
22 /* Create a subtree for count >= 1 elements.
23 Its black-height bh is passed as argument, with
24 2^bh - 1 <= count <= 2^(bh+1) - 1. bh == 0 implies count == 1.
25 Its height is h where 2^(h-1) <= count <= 2^h - 1. */
27 create_subtree_with_contents (unsigned int bh,
28 size_t count, const void **contents)
30 size_t half1 = (count - 1) / 2;
31 size_t half2 = count / 2;
32 /* Note: half1 + half2 = count - 1. */
33 gl_list_node_t node = XMALLOC (struct gl_list_node_impl);
37 /* half1 > 0 implies count > 1, implies bh >= 1, implies
38 2^(bh-1) - 1 <= half1 <= 2^bh - 1. */
40 create_subtree_with_contents (bh - 1, half1, contents);
41 node->left->parent = node;
46 node->value = contents[half1];
50 /* half2 > 0 implies count > 1, implies bh >= 1, implies
51 2^(bh-1) - 1 <= half2 <= 2^bh - 1. */
53 create_subtree_with_contents (bh - 1, half2, contents + half1 + 1);
54 node->right->parent = node;
59 node->color = (bh == 0 ? RED : BLACK);
61 node->branch_size = count;
67 gl_tree_create (gl_list_implementation_t implementation,
68 gl_listelement_equals_fn equals_fn,
69 gl_listelement_hashcode_fn hashcode_fn,
70 gl_listelement_dispose_fn dispose_fn,
71 bool allow_duplicates,
72 size_t count, const void **contents)
74 struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
76 list->base.vtable = implementation;
77 list->base.equals_fn = equals_fn;
78 list->base.hashcode_fn = hashcode_fn;
79 list->base.dispose_fn = dispose_fn;
80 list->base.allow_duplicates = allow_duplicates;
83 size_t estimate = xsum (count, count / 2); /* 1.5 * count */
86 list->table_size = next_prime (estimate);
87 list->table = XCALLOC (list->table_size, gl_hash_entry_t);
92 /* Assuming 2^bh - 1 <= count <= 2^(bh+1) - 2, we create a tree whose
93 upper bh levels are black, and only the partially present lowest
98 for (n = count + 1, bh = 0; n > 1; n = n >> 1)
102 list->root = create_subtree_with_contents (bh, count, contents);
103 list->root->parent = NULL;
106 /* Now that the tree is built, node_position() works. Now we can
107 add the nodes to the hash table. */
108 add_nodes_to_buckets (list);
117 /* Rotate left a subtree.
125 Change the tree structure, update the branch sizes.
126 The caller must update the colors and register D as child of its parent. */
127 static inline gl_list_node_t
128 rotate_left (gl_list_node_t b_node, gl_list_node_t d_node)
130 gl_list_node_t a_node = b_node->left;
131 gl_list_node_t c_node = d_node->left;
132 gl_list_node_t e_node = d_node->right;
134 b_node->right = c_node;
135 d_node->left = b_node;
137 d_node->parent = b_node->parent;
138 b_node->parent = d_node;
140 c_node->parent = b_node;
142 b_node->branch_size =
143 (a_node != NULL ? a_node->branch_size : 0)
144 + 1 + (c_node != NULL ? c_node->branch_size : 0);
145 d_node->branch_size =
146 b_node->branch_size + 1 + (e_node != NULL ? e_node->branch_size : 0);
151 /* Rotate right a subtree.
159 Change the tree structure, update the branch sizes.
160 The caller must update the colors and register B as child of its parent. */
161 static inline gl_list_node_t
162 rotate_right (gl_list_node_t b_node, gl_list_node_t d_node)
164 gl_list_node_t a_node = b_node->left;
165 gl_list_node_t c_node = b_node->right;
166 gl_list_node_t e_node = d_node->right;
168 d_node->left = c_node;
169 b_node->right = d_node;
171 b_node->parent = d_node->parent;
172 d_node->parent = b_node;
174 c_node->parent = d_node;
176 d_node->branch_size =
177 (c_node != NULL ? c_node->branch_size : 0)
178 + 1 + (e_node != NULL ? e_node->branch_size : 0);
179 b_node->branch_size =
180 (a_node != NULL ? a_node->branch_size : 0) + 1 + d_node->branch_size;
185 /* Ensure the tree is balanced, after an insertion operation.
186 Also assigns node->color.
187 parent is the given node's parent, known to be non-NULL. */
189 rebalance_after_add (gl_list_t list, gl_list_node_t node, gl_list_node_t parent)
193 /* At this point, parent = node->parent != NULL.
194 Think of node->color being RED (although node->color is not yet
196 gl_list_node_t grandparent;
197 gl_list_node_t uncle;
199 if (parent->color == BLACK)
201 /* A RED color for node is acceptable. */
206 grandparent = parent->parent;
207 /* Since parent is RED, we know that
208 grandparent is != NULL and colored BLACK. */
210 if (grandparent->left == parent)
211 uncle = grandparent->right;
212 else if (grandparent->right == parent)
213 uncle = grandparent->left;
217 if (uncle != NULL && uncle->color == RED)
219 /* Change grandparent from BLACK to RED, and
220 change parent and uncle from RED to BLACK.
221 This makes it acceptable for node to be RED. */
223 parent->color = uncle->color = BLACK;
228 /* grandparent and uncle are BLACK. parent is RED. node wants
230 In this case, recoloring is not sufficient. Need to perform
231 one or two rotations. */
232 gl_list_node_t *grandparentp;
234 if (grandparent->parent == NULL)
235 grandparentp = &list->root;
236 else if (grandparent->parent->left == grandparent)
237 grandparentp = &grandparent->parent->left;
238 else if (grandparent->parent->right == grandparent)
239 grandparentp = &grandparent->parent->right;
243 if (grandparent->left == parent)
245 if (parent->right == node)
247 /* Rotation between node and parent. */
248 grandparent->left = rotate_left (parent, node);
250 parent = grandparent->left;
252 /* grandparent and uncle are BLACK. parent and node want to be
253 RED. parent = grandparent->left. node = parent->left.
258 parent uncle --> node grandparent
264 *grandparentp = rotate_right (parent, grandparent);
265 parent->color = BLACK;
266 node->color = grandparent->color = RED;
268 else /* grandparent->right == parent */
270 if (parent->left == node)
272 /* Rotation between node and parent. */
273 grandparent->right = rotate_right (node, parent);
275 parent = grandparent->right;
277 /* grandparent and uncle are BLACK. parent and node want to be
278 RED. parent = grandparent->right. node = parent->right.
283 uncle parent --> grandparent node
289 *grandparentp = rotate_left (grandparent, parent);
290 parent->color = BLACK;
291 node->color = grandparent->color = RED;
296 /* Start again with a new (node, parent) pair. */
297 parent = node->parent;
301 /* Change node's color from RED to BLACK. This increases the
302 tree's black-height. */
309 /* Ensure the tree is balanced, after a deletion operation.
310 CHILD was a grandchild of PARENT and is now its child. Between them,
311 a black node was removed. CHILD is also black, or NULL.
312 (CHILD can also be NULL. But PARENT is non-NULL.) */
314 rebalance_after_remove (gl_list_t list, gl_list_node_t child, gl_list_node_t parent)
318 /* At this point, we reduced the black-height of the CHILD subtree by 1.
319 To make up, either look for a possibility to turn a RED to a BLACK
320 node, or try to reduce the black-height tree of CHILD's sibling
322 gl_list_node_t *parentp;
324 if (parent->parent == NULL)
325 parentp = &list->root;
326 else if (parent->parent->left == parent)
327 parentp = &parent->parent->left;
328 else if (parent->parent->right == parent)
329 parentp = &parent->parent->right;
333 if (parent->left == child)
335 gl_list_node_t sibling = parent->right;
336 /* sibling's black-height is >= 1. In particular,
345 if (sibling->color == RED)
347 /* sibling is RED, hence parent is BLACK and sibling's children
348 are non-NULL and BLACK.
353 child sibling --> parent SR
359 *parentp = rotate_left (parent, sibling);
361 sibling->color = BLACK;
363 /* Concentrate on the subtree of parent. The new sibling is
364 one of the old sibling's children, and known to be BLACK. */
365 parentp = &sibling->left;
366 sibling = parent->right;
368 /* Now we know that sibling is BLACK.
375 if (sibling->right != NULL && sibling->right->color == RED)
381 child sibling --> parent SR
387 *parentp = rotate_left (parent, sibling);
388 sibling->color = parent->color;
389 parent->color = BLACK;
390 sibling->right->color = BLACK;
393 else if (sibling->left != NULL && sibling->left->color == RED)
399 child sibling --> child SL
408 where SLL, SLR, SR are all black.
410 parent->right = rotate_right (sibling->left, sibling);
411 /* Change sibling from BLACK to RED and SL from RED to BLACK. */
412 sibling->color = RED;
413 sibling = parent->right;
414 sibling->color = BLACK;
416 /* Now do as in the previous case. */
417 *parentp = rotate_left (parent, sibling);
418 sibling->color = parent->color;
419 parent->color = BLACK;
420 sibling->right->color = BLACK;
425 if (parent->color == BLACK)
427 /* Change sibling from BLACK to RED. Then the entire
428 subtree at parent has decreased its black-height.
432 child sibling --> child sibling
435 sibling->color = RED;
441 /* Change parent from RED to BLACK, but compensate by
442 changing sibling from BLACK to RED.
446 child sibling --> child sibling
449 parent->color = BLACK;
450 sibling->color = RED;
455 else if (parent->right == child)
457 gl_list_node_t sibling = parent->left;
458 /* sibling's black-height is >= 1. In particular,
467 if (sibling->color == RED)
469 /* sibling is RED, hence parent is BLACK and sibling's children
470 are non-NULL and BLACK.
475 sibling child --> SR parent
481 *parentp = rotate_right (sibling, parent);
483 sibling->color = BLACK;
485 /* Concentrate on the subtree of parent. The new sibling is
486 one of the old sibling's children, and known to be BLACK. */
487 parentp = &sibling->right;
488 sibling = parent->left;
490 /* Now we know that sibling is BLACK.
497 if (sibling->left != NULL && sibling->left->color == RED)
503 sibling child --> SL parent
509 *parentp = rotate_right (sibling, parent);
510 sibling->color = parent->color;
511 parent->color = BLACK;
512 sibling->left->color = BLACK;
515 else if (sibling->right != NULL && sibling->right->color == RED)
521 sibling child --> SR child
530 where SL, SRL, SRR are all black.
532 parent->left = rotate_left (sibling, sibling->right);
533 /* Change sibling from BLACK to RED and SL from RED to BLACK. */
534 sibling->color = RED;
535 sibling = parent->left;
536 sibling->color = BLACK;
538 /* Now do as in the previous case. */
539 *parentp = rotate_right (sibling, parent);
540 sibling->color = parent->color;
541 parent->color = BLACK;
542 sibling->left->color = BLACK;
547 if (parent->color == BLACK)
549 /* Change sibling from BLACK to RED. Then the entire
550 subtree at parent has decreased its black-height.
554 sibling child --> sibling child
557 sibling->color = RED;
563 /* Change parent from RED to BLACK, but compensate by
564 changing sibling from BLACK to RED.
568 sibling child --> sibling child
571 parent->color = BLACK;
572 sibling->color = RED;
580 /* Start again with a new (child, parent) pair. */
581 parent = child->parent;
583 #if 0 /* Already handled. */
584 if (child != NULL && child->color == RED)
586 child->color = BLACK;
596 static gl_list_node_t
597 gl_tree_add_first (gl_list_t list, const void *elt)
599 /* Create new node. */
600 gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
602 new_node->left = NULL;
603 new_node->right = NULL;
604 new_node->branch_size = 1;
605 new_node->value = elt;
607 new_node->h.hashcode =
608 (list->base.hashcode_fn != NULL
609 ? list->base.hashcode_fn (new_node->value)
610 : (size_t)(uintptr_t) new_node->value);
613 /* Add it to the tree. */
614 if (list->root == NULL)
616 new_node->color = BLACK;
617 list->root = new_node;
618 new_node->parent = NULL;
624 for (node = list->root; node->left != NULL; )
627 node->left = new_node;
628 new_node->parent = node;
630 /* Update branch_size fields of the parent nodes. */
634 for (p = node; p != NULL; p = p->parent)
638 /* Color and rebalance. */
639 rebalance_after_add (list, new_node, node);
643 /* Add node to the hash table.
644 Note that this is only possible _after_ the node has been added to the
645 tree structure, because add_to_bucket() uses node_position(). */
646 add_to_bucket (list, new_node);
647 hash_resize_after_add (list);
653 static gl_list_node_t
654 gl_tree_add_last (gl_list_t list, const void *elt)
656 /* Create new node. */
657 gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
659 new_node->left = NULL;
660 new_node->right = NULL;
661 new_node->branch_size = 1;
662 new_node->value = elt;
664 new_node->h.hashcode =
665 (list->base.hashcode_fn != NULL
666 ? list->base.hashcode_fn (new_node->value)
667 : (size_t)(uintptr_t) new_node->value);
670 /* Add it to the tree. */
671 if (list->root == NULL)
673 new_node->color = BLACK;
674 list->root = new_node;
675 new_node->parent = NULL;
681 for (node = list->root; node->right != NULL; )
684 node->right = new_node;
685 new_node->parent = node;
687 /* Update branch_size fields of the parent nodes. */
691 for (p = node; p != NULL; p = p->parent)
695 /* Color and rebalance. */
696 rebalance_after_add (list, new_node, node);
700 /* Add node to the hash table.
701 Note that this is only possible _after_ the node has been added to the
702 tree structure, because add_to_bucket() uses node_position(). */
703 add_to_bucket (list, new_node);
704 hash_resize_after_add (list);
710 static gl_list_node_t
711 gl_tree_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
713 /* Create new node. */
714 gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
716 new_node->left = NULL;
717 new_node->right = NULL;
718 new_node->branch_size = 1;
719 new_node->value = elt;
721 new_node->h.hashcode =
722 (list->base.hashcode_fn != NULL
723 ? list->base.hashcode_fn (new_node->value)
724 : (size_t)(uintptr_t) new_node->value);
727 /* Add it to the tree. */
728 if (node->left == NULL)
729 node->left = new_node;
732 for (node = node->left; node->right != NULL; )
734 node->right = new_node;
736 new_node->parent = node;
738 /* Update branch_size fields of the parent nodes. */
742 for (p = node; p != NULL; p = p->parent)
746 /* Color and rebalance. */
747 rebalance_after_add (list, new_node, node);
750 /* Add node to the hash table.
751 Note that this is only possible _after_ the node has been added to the
752 tree structure, because add_to_bucket() uses node_position(). */
753 add_to_bucket (list, new_node);
754 hash_resize_after_add (list);
760 static gl_list_node_t
761 gl_tree_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
763 /* Create new node. */
764 gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
766 new_node->left = NULL;
767 new_node->right = NULL;
768 new_node->branch_size = 1;
769 new_node->value = elt;
771 new_node->h.hashcode =
772 (list->base.hashcode_fn != NULL
773 ? list->base.hashcode_fn (new_node->value)
774 : (size_t)(uintptr_t) new_node->value);
777 /* Add it to the tree. */
778 if (node->right == NULL)
779 node->right = new_node;
782 for (node = node->right; node->left != NULL; )
784 node->left = new_node;
786 new_node->parent = node;
788 /* Update branch_size fields of the parent nodes. */
792 for (p = node; p != NULL; p = p->parent)
796 /* Color and rebalance. */
797 rebalance_after_add (list, new_node, node);
800 /* Add node to the hash table.
801 Note that this is only possible _after_ the node has been added to the
802 tree structure, because add_to_bucket() uses node_position(). */
803 add_to_bucket (list, new_node);
804 hash_resize_after_add (list);
811 gl_tree_remove_node (gl_list_t list, gl_list_node_t node)
813 gl_list_node_t parent;
816 /* Remove node from the hash table.
817 Note that this is only possible _before_ the node is removed from the
818 tree structure, because remove_from_bucket() uses node_position(). */
819 remove_from_bucket (list, node);
822 parent = node->parent;
824 if (node->left == NULL)
826 /* Replace node with node->right. */
827 gl_list_node_t child = node->right;
831 child->parent = parent;
832 /* Since node->left == NULL, child must be RED and of height 1,
833 hence node must have been BLACK. Recolor the child. */
834 child->color = BLACK;
840 if (parent->left == node)
841 parent->left = child;
842 else /* parent->right == node */
843 parent->right = child;
845 /* Update branch_size fields of the parent nodes. */
849 for (p = parent; p != NULL; p = p->parent)
853 if (child == NULL && node->color == BLACK)
854 rebalance_after_remove (list, child, parent);
857 else if (node->right == NULL)
859 /* It is not absolutely necessary to treat this case. But the more
860 general case below is more complicated, hence slower. */
861 /* Replace node with node->left. */
862 gl_list_node_t child = node->left;
864 child->parent = parent;
865 /* Since node->right == NULL, child must be RED and of height 1,
866 hence node must have been BLACK. Recolor the child. */
867 child->color = BLACK;
872 if (parent->left == node)
873 parent->left = child;
874 else /* parent->right == node */
875 parent->right = child;
877 /* Update branch_size fields of the parent nodes. */
881 for (p = parent; p != NULL; p = p->parent)
888 /* Replace node with the rightmost element of the node->left subtree. */
889 gl_list_node_t subst;
890 gl_list_node_t subst_parent;
891 gl_list_node_t child;
892 color_t removed_color;
894 for (subst = node->left; subst->right != NULL; )
895 subst = subst->right;
897 subst_parent = subst->parent;
901 removed_color = subst->color;
903 /* The case subst_parent == node is special: If we do nothing special,
904 we get confusion about node->left, subst->left and child->parent.
906 <==> The 'for' loop above terminated immediately.
907 <==> subst == subst_parent->left
908 [otherwise subst == subst_parent->right]
909 In this case, we would need to first set
910 child->parent = node; node->left = child;
911 and later - when we copy subst into node's position - again
912 child->parent = subst; subst->left = child;
913 Altogether a no-op. */
914 if (subst_parent != node)
917 child->parent = subst_parent;
918 subst_parent->right = child;
921 /* Update branch_size fields of the parent nodes. */
925 for (p = subst_parent; p != NULL; p = p->parent)
929 /* Copy subst into node's position.
930 (This is safer than to copy subst's value into node, keep node in
931 place, and free subst.) */
932 if (subst_parent != node)
934 subst->left = node->left;
935 subst->left->parent = subst;
937 subst->right = node->right;
938 subst->right->parent = subst;
939 subst->color = node->color;
940 subst->branch_size = node->branch_size;
941 subst->parent = parent;
944 else if (parent->left == node)
945 parent->left = subst;
946 else /* parent->right == node */
947 parent->right = subst;
949 if (removed_color == BLACK)
951 if (child != NULL && child->color == RED)
952 /* Recolor the child. */
953 child->color = BLACK;
955 /* Rebalancing starts at child's parent, that is subst_parent -
956 except when subst_parent == node. In this case, we need to use
957 its replacement, subst. */
958 rebalance_after_remove (list, child,
959 subst_parent != node ? subst_parent : subst);
963 if (list->base.dispose_fn != NULL)
964 list->base.dispose_fn (node->value);