1 /* Ordered set 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/>. */
21 #include "gl_rbtree_oset.h"
27 /* A red-black tree is a binary tree where every node is colored black or
30 2. No red node has a red parent.
31 Or equivalently: No red node has a red child.
32 3. All paths from the root down to any NULL endpoint contain the same
33 number of black nodes.
34 Let's call this the "black-height" bh of the tree. It follows that every
35 such path contains exactly bh black and between 0 and bh red nodes. (The
36 extreme cases are a path containing only black nodes, and a path colored
37 alternatingly black-red-black-red-...-black-red.) The height of the tree
38 therefore is >= bh, <= 2*bh.
41 /* -------------------------- gl_oset_t Data Type -------------------------- */
43 /* Color of a node. */
44 typedef enum color { BLACK, RED } color_t;
46 /* Tree node implementation, valid for this file only. */
47 struct gl_oset_node_impl
49 struct gl_oset_node_impl *left; /* left branch, or NULL */
50 struct gl_oset_node_impl *right; /* right branch, or NULL */
51 /* Parent pointer, or NULL. The parent pointer is not needed for most
52 operations. It is needed so that a gl_oset_node_t can be returned
53 without memory allocation, on which the functions gl_oset_remove_node,
54 gl_oset_add_before, gl_oset_add_after can be implemented. */
55 struct gl_oset_node_impl *parent;
56 color_t color; /* node's color */
59 typedef struct gl_oset_node_impl * gl_oset_node_t;
61 /* Concrete gl_oset_impl type, valid for this file only. */
64 struct gl_oset_impl_base base;
65 struct gl_oset_node_impl *root; /* root node or NULL */
66 size_t count; /* number of nodes */
69 /* A red-black tree of height h has a black-height bh >= ceil(h/2) and
70 therefore at least 2^ceil(h/2) - 1 elements. So, h <= 116 (because a tree
71 of height h >= 117 would have at least 2^59 - 1 elements, and because even
73 sizeof (gl_oset_node_impl) * (2^59 - 1) > 2^64
74 this would exceed the address space of the machine. */
77 /* Rotate left a subtree.
85 Change the tree structure, update the branch sizes.
86 The caller must update the colors and register D as child of its parent. */
87 static inline gl_oset_node_t
88 rotate_left (gl_oset_node_t b_node, gl_oset_node_t d_node)
90 gl_oset_node_t c_node = d_node->left;
92 b_node->right = c_node;
93 d_node->left = b_node;
95 d_node->parent = b_node->parent;
96 b_node->parent = d_node;
98 c_node->parent = b_node;
103 /* Rotate right a subtree.
111 Change the tree structure, update the branch sizes.
112 The caller must update the colors and register B as child of its parent. */
113 static inline gl_oset_node_t
114 rotate_right (gl_oset_node_t b_node, gl_oset_node_t d_node)
116 gl_oset_node_t c_node = b_node->right;
118 d_node->left = c_node;
119 b_node->right = d_node;
121 b_node->parent = d_node->parent;
122 d_node->parent = b_node;
124 c_node->parent = d_node;
129 /* Ensure the tree is balanced, after an insertion operation.
130 Also assigns node->color.
131 parent is the given node's parent, known to be non-NULL. */
133 rebalance_after_add (gl_oset_t set, gl_oset_node_t node, gl_oset_node_t parent)
137 /* At this point, parent = node->parent != NULL.
138 Think of node->color being RED (although node->color is not yet
140 gl_oset_node_t grandparent;
141 gl_oset_node_t uncle;
143 if (parent->color == BLACK)
145 /* A RED color for node is acceptable. */
150 grandparent = parent->parent;
151 /* Since parent is RED, we know that
152 grandparent is != NULL and colored BLACK. */
154 if (grandparent->left == parent)
155 uncle = grandparent->right;
156 else if (grandparent->right == parent)
157 uncle = grandparent->left;
161 if (uncle != NULL && uncle->color == RED)
163 /* Change grandparent from BLACK to RED, and
164 change parent and uncle from RED to BLACK.
165 This makes it acceptable for node to be RED. */
167 parent->color = uncle->color = BLACK;
172 /* grandparent and uncle are BLACK. parent is RED. node wants
174 In this case, recoloring is not sufficient. Need to perform
175 one or two rotations. */
176 gl_oset_node_t *grandparentp;
178 if (grandparent->parent == NULL)
179 grandparentp = &set->root;
180 else if (grandparent->parent->left == grandparent)
181 grandparentp = &grandparent->parent->left;
182 else if (grandparent->parent->right == grandparent)
183 grandparentp = &grandparent->parent->right;
187 if (grandparent->left == parent)
189 if (parent->right == node)
191 /* Rotation between node and parent. */
192 grandparent->left = rotate_left (parent, node);
194 parent = grandparent->left;
196 /* grandparent and uncle are BLACK. parent and node want to be
197 RED. parent = grandparent->left. node = parent->left.
202 parent uncle --> node grandparent
208 *grandparentp = rotate_right (parent, grandparent);
209 parent->color = BLACK;
210 node->color = grandparent->color = RED;
212 else /* grandparent->right == parent */
214 if (parent->left == node)
216 /* Rotation between node and parent. */
217 grandparent->right = rotate_right (node, parent);
219 parent = grandparent->right;
221 /* grandparent and uncle are BLACK. parent and node want to be
222 RED. parent = grandparent->right. node = parent->right.
227 uncle parent --> grandparent node
233 *grandparentp = rotate_left (grandparent, parent);
234 parent->color = BLACK;
235 node->color = grandparent->color = RED;
240 /* Start again with a new (node, parent) pair. */
241 parent = node->parent;
245 /* Change node's color from RED to BLACK. This increases the
246 tree's black-height. */
253 /* Ensure the tree is balanced, after a deletion operation.
254 CHILD was a grandchild of PARENT and is now its child. Between them,
255 a black node was removed. CHILD is also black, or NULL.
256 (CHILD can also be NULL. But PARENT is non-NULL.) */
258 rebalance_after_remove (gl_oset_t set, gl_oset_node_t child, gl_oset_node_t parent)
262 /* At this point, we reduced the black-height of the CHILD subtree by 1.
263 To make up, either look for a possibility to turn a RED to a BLACK
264 node, or try to reduce the black-height tree of CHILD's sibling
266 gl_oset_node_t *parentp;
268 if (parent->parent == NULL)
269 parentp = &set->root;
270 else if (parent->parent->left == parent)
271 parentp = &parent->parent->left;
272 else if (parent->parent->right == parent)
273 parentp = &parent->parent->right;
277 if (parent->left == child)
279 gl_oset_node_t sibling = parent->right;
280 /* sibling's black-height is >= 1. In particular,
289 if (sibling->color == RED)
291 /* sibling is RED, hence parent is BLACK and sibling's children
292 are non-NULL and BLACK.
297 child sibling --> parent SR
303 *parentp = rotate_left (parent, sibling);
305 sibling->color = BLACK;
307 /* Concentrate on the subtree of parent. The new sibling is
308 one of the old sibling's children, and known to be BLACK. */
309 parentp = &sibling->left;
310 sibling = parent->right;
312 /* Now we know that sibling is BLACK.
319 if (sibling->right != NULL && sibling->right->color == RED)
325 child sibling --> parent SR
331 *parentp = rotate_left (parent, sibling);
332 sibling->color = parent->color;
333 parent->color = BLACK;
334 sibling->right->color = BLACK;
337 else if (sibling->left != NULL && sibling->left->color == RED)
343 child sibling --> child SL
352 where SLL, SLR, SR are all black.
354 parent->right = rotate_right (sibling->left, sibling);
355 /* Change sibling from BLACK to RED and SL from RED to BLACK. */
356 sibling->color = RED;
357 sibling = parent->right;
358 sibling->color = BLACK;
360 /* Now do as in the previous case. */
361 *parentp = rotate_left (parent, sibling);
362 sibling->color = parent->color;
363 parent->color = BLACK;
364 sibling->right->color = BLACK;
369 if (parent->color == BLACK)
371 /* Change sibling from BLACK to RED. Then the entire
372 subtree at parent has decreased its black-height.
376 child sibling --> child sibling
379 sibling->color = RED;
385 /* Change parent from RED to BLACK, but compensate by
386 changing sibling from BLACK to RED.
390 child sibling --> child sibling
393 parent->color = BLACK;
394 sibling->color = RED;
399 else if (parent->right == child)
401 gl_oset_node_t sibling = parent->left;
402 /* sibling's black-height is >= 1. In particular,
411 if (sibling->color == RED)
413 /* sibling is RED, hence parent is BLACK and sibling's children
414 are non-NULL and BLACK.
419 sibling child --> SR parent
425 *parentp = rotate_right (sibling, parent);
427 sibling->color = BLACK;
429 /* Concentrate on the subtree of parent. The new sibling is
430 one of the old sibling's children, and known to be BLACK. */
431 parentp = &sibling->right;
432 sibling = parent->left;
434 /* Now we know that sibling is BLACK.
441 if (sibling->left != NULL && sibling->left->color == RED)
447 sibling child --> SL parent
453 *parentp = rotate_right (sibling, parent);
454 sibling->color = parent->color;
455 parent->color = BLACK;
456 sibling->left->color = BLACK;
459 else if (sibling->right != NULL && sibling->right->color == RED)
465 sibling child --> SR child
474 where SL, SRL, SRR are all black.
476 parent->left = rotate_left (sibling, sibling->right);
477 /* Change sibling from BLACK to RED and SL from RED to BLACK. */
478 sibling->color = RED;
479 sibling = parent->left;
480 sibling->color = BLACK;
482 /* Now do as in the previous case. */
483 *parentp = rotate_right (sibling, parent);
484 sibling->color = parent->color;
485 parent->color = BLACK;
486 sibling->left->color = BLACK;
491 if (parent->color == BLACK)
493 /* Change sibling from BLACK to RED. Then the entire
494 subtree at parent has decreased its black-height.
498 sibling child --> sibling child
501 sibling->color = RED;
507 /* Change parent from RED to BLACK, but compensate by
508 changing sibling from BLACK to RED.
512 sibling child --> sibling child
515 parent->color = BLACK;
516 sibling->color = RED;
524 /* Start again with a new (child, parent) pair. */
525 parent = child->parent;
527 #if 0 /* Already handled. */
528 if (child != NULL && child->color == RED)
530 child->color = BLACK;
540 static gl_oset_node_t
541 gl_tree_add_first (gl_oset_t set, const void *elt)
543 /* Create new node. */
544 gl_oset_node_t new_node = XMALLOC (struct gl_oset_node_impl);
546 new_node->left = NULL;
547 new_node->right = NULL;
548 new_node->value = elt;
550 /* Add it to the tree. */
551 if (set->root == NULL)
553 new_node->color = BLACK;
554 set->root = new_node;
555 new_node->parent = NULL;
561 for (node = set->root; node->left != NULL; )
564 node->left = new_node;
565 new_node->parent = node;
567 /* Color and rebalance. */
568 rebalance_after_add (set, new_node, node);
575 static gl_oset_node_t
576 gl_tree_add_before (gl_oset_t set, gl_oset_node_t node, const void *elt)
578 /* Create new node. */
579 gl_oset_node_t new_node = XMALLOC (struct gl_oset_node_impl);
581 new_node->left = NULL;
582 new_node->right = NULL;
583 new_node->value = elt;
585 /* Add it to the tree. */
586 if (node->left == NULL)
587 node->left = new_node;
590 for (node = node->left; node->right != NULL; )
592 node->right = new_node;
594 new_node->parent = node;
596 /* Color and rebalance. */
597 rebalance_after_add (set, new_node, node);
603 static gl_oset_node_t
604 gl_tree_add_after (gl_oset_t set, gl_oset_node_t node, const void *elt)
606 /* Create new node. */
607 gl_oset_node_t new_node = XMALLOC (struct gl_oset_node_impl);
609 new_node->left = NULL;
610 new_node->right = NULL;
611 new_node->value = elt;
613 /* Add it to the tree. */
614 if (node->right == NULL)
615 node->right = new_node;
618 for (node = node->right; node->left != NULL; )
620 node->left = new_node;
622 new_node->parent = node;
624 /* Color and rebalance. */
625 rebalance_after_add (set, new_node, node);
632 gl_tree_remove_node (gl_oset_t set, gl_oset_node_t node)
634 gl_oset_node_t parent = node->parent;
636 if (node->left == NULL)
638 /* Replace node with node->right. */
639 gl_oset_node_t child = node->right;
643 child->parent = parent;
644 /* Since node->left == NULL, child must be RED and of height 1,
645 hence node must have been BLACK. Recolor the child. */
646 child->color = BLACK;
652 if (parent->left == node)
653 parent->left = child;
654 else /* parent->right == node */
655 parent->right = child;
657 if (child == NULL && node->color == BLACK)
658 rebalance_after_remove (set, child, parent);
661 else if (node->right == NULL)
663 /* It is not absolutely necessary to treat this case. But the more
664 general case below is more complicated, hence slower. */
665 /* Replace node with node->left. */
666 gl_oset_node_t child = node->left;
668 child->parent = parent;
669 /* Since node->right == NULL, child must be RED and of height 1,
670 hence node must have been BLACK. Recolor the child. */
671 child->color = BLACK;
676 if (parent->left == node)
677 parent->left = child;
678 else /* parent->right == node */
679 parent->right = child;
684 /* Replace node with the rightmost element of the node->left subtree. */
685 gl_oset_node_t subst;
686 gl_oset_node_t subst_parent;
687 gl_oset_node_t child;
688 color_t removed_color;
690 for (subst = node->left; subst->right != NULL; )
691 subst = subst->right;
693 subst_parent = subst->parent;
697 removed_color = subst->color;
699 /* The case subst_parent == node is special: If we do nothing special,
700 we get confusion about node->left, subst->left and child->parent.
702 <==> The 'for' loop above terminated immediately.
703 <==> subst == subst_parent->left
704 [otherwise subst == subst_parent->right]
705 In this case, we would need to first set
706 child->parent = node; node->left = child;
707 and later - when we copy subst into node's position - again
708 child->parent = subst; subst->left = child;
709 Altogether a no-op. */
710 if (subst_parent != node)
713 child->parent = subst_parent;
714 subst_parent->right = child;
717 /* Copy subst into node's position.
718 (This is safer than to copy subst's value into node, keep node in
719 place, and free subst.) */
720 if (subst_parent != node)
722 subst->left = node->left;
723 subst->left->parent = subst;
725 subst->right = node->right;
726 subst->right->parent = subst;
727 subst->color = node->color;
728 subst->parent = parent;
731 else if (parent->left == node)
732 parent->left = subst;
733 else /* parent->right == node */
734 parent->right = subst;
736 if (removed_color == BLACK)
738 if (child != NULL && child->color == RED)
739 /* Recolor the child. */
740 child->color = BLACK;
742 /* Rebalancing starts at child's parent, that is subst_parent -
743 except when subst_parent == node. In this case, we need to use
744 its replacement, subst. */
745 rebalance_after_remove (set, child,
746 subst_parent != node ? subst_parent : subst);
751 if (set->base.dispose_fn != NULL)
752 set->base.dispose_fn (node->value);
757 /* Generic binary tree code. */
758 #include "gl_anytree_oset.h"
762 check_invariants (gl_oset_node_t node, gl_oset_node_t parent, size_t *counterp)
764 unsigned int left_blackheight =
765 (node->left != NULL ? check_invariants (node->left, node, counterp) : 0);
766 unsigned int right_blackheight =
767 (node->right != NULL ? check_invariants (node->right, node, counterp) : 0);
769 if (!(node->parent == parent))
771 if (!(node->color == BLACK || node->color == RED))
773 if (parent == NULL && !(node->color == BLACK))
775 if (!(left_blackheight == right_blackheight))
780 return left_blackheight + (node->color == BLACK ? 1 : 0);
783 gl_rbtree_oset_check_invariants (gl_oset_t set)
786 if (set->root != NULL)
787 check_invariants (set->root, NULL, &counter);
788 if (!(set->count == counter))
792 const struct gl_oset_implementation gl_rbtree_oset_implementation =
794 gl_tree_create_empty,
797 gl_tree_search_atleast,
802 gl_tree_iterator_next,
803 gl_tree_iterator_free