1 /* Ordered set data type implemented by a binary tree.
2 Copyright (C) 2006-2007, 2009-2011 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"
25 /* A red-black tree is a binary tree where every node is colored black or
28 2. No red node has a red parent.
29 Or equivalently: No red node has a red child.
30 3. All paths from the root down to any NULL endpoint contain the same
31 number of black nodes.
32 Let's call this the "black-height" bh of the tree. It follows that every
33 such path contains exactly bh black and between 0 and bh red nodes. (The
34 extreme cases are a path containing only black nodes, and a path colored
35 alternatingly black-red-black-red-...-black-red.) The height of the tree
36 therefore is >= bh, <= 2*bh.
39 /* -------------------------- gl_oset_t Data Type -------------------------- */
41 /* Color of a node. */
42 typedef enum color { BLACK, RED } color_t;
44 /* Tree node implementation, valid for this file only. */
45 struct gl_oset_node_impl
47 struct gl_oset_node_impl *left; /* left branch, or NULL */
48 struct gl_oset_node_impl *right; /* right branch, or NULL */
49 /* Parent pointer, or NULL. The parent pointer is not needed for most
50 operations. It is needed so that a gl_oset_node_t can be returned
51 without memory allocation, on which the functions gl_oset_remove_node,
52 gl_oset_add_before, gl_oset_add_after can be implemented. */
53 struct gl_oset_node_impl *parent;
54 color_t color; /* node's color */
57 typedef struct gl_oset_node_impl * gl_oset_node_t;
59 /* Concrete gl_oset_impl type, valid for this file only. */
62 struct gl_oset_impl_base base;
63 struct gl_oset_node_impl *root; /* root node or NULL */
64 size_t count; /* number of nodes */
67 /* A red-black tree of height h has a black-height bh >= ceil(h/2) and
68 therefore at least 2^ceil(h/2) - 1 elements. So, h <= 116 (because a tree
69 of height h >= 117 would have at least 2^59 - 1 elements, and because even
71 sizeof (gl_oset_node_impl) * (2^59 - 1) > 2^64
72 this would exceed the address space of the machine. */
75 /* Rotate left a subtree.
83 Change the tree structure, update the branch sizes.
84 The caller must update the colors and register D as child of its parent. */
85 static inline gl_oset_node_t
86 rotate_left (gl_oset_node_t b_node, gl_oset_node_t d_node)
88 gl_oset_node_t c_node = d_node->left;
90 b_node->right = c_node;
91 d_node->left = b_node;
93 d_node->parent = b_node->parent;
94 b_node->parent = d_node;
96 c_node->parent = b_node;
101 /* Rotate right a subtree.
109 Change the tree structure, update the branch sizes.
110 The caller must update the colors and register B as child of its parent. */
111 static inline gl_oset_node_t
112 rotate_right (gl_oset_node_t b_node, gl_oset_node_t d_node)
114 gl_oset_node_t c_node = b_node->right;
116 d_node->left = c_node;
117 b_node->right = d_node;
119 b_node->parent = d_node->parent;
120 d_node->parent = b_node;
122 c_node->parent = d_node;
127 /* Ensure the tree is balanced, after an insertion operation.
128 Also assigns node->color.
129 parent is the given node's parent, known to be non-NULL. */
131 rebalance_after_add (gl_oset_t set, gl_oset_node_t node, gl_oset_node_t parent)
135 /* At this point, parent = node->parent != NULL.
136 Think of node->color being RED (although node->color is not yet
138 gl_oset_node_t grandparent;
139 gl_oset_node_t uncle;
141 if (parent->color == BLACK)
143 /* A RED color for node is acceptable. */
148 grandparent = parent->parent;
149 /* Since parent is RED, we know that
150 grandparent is != NULL and colored BLACK. */
152 if (grandparent->left == parent)
153 uncle = grandparent->right;
154 else if (grandparent->right == parent)
155 uncle = grandparent->left;
159 if (uncle != NULL && uncle->color == RED)
161 /* Change grandparent from BLACK to RED, and
162 change parent and uncle from RED to BLACK.
163 This makes it acceptable for node to be RED. */
165 parent->color = uncle->color = BLACK;
170 /* grandparent and uncle are BLACK. parent is RED. node wants
172 In this case, recoloring is not sufficient. Need to perform
173 one or two rotations. */
174 gl_oset_node_t *grandparentp;
176 if (grandparent->parent == NULL)
177 grandparentp = &set->root;
178 else if (grandparent->parent->left == grandparent)
179 grandparentp = &grandparent->parent->left;
180 else if (grandparent->parent->right == grandparent)
181 grandparentp = &grandparent->parent->right;
185 if (grandparent->left == parent)
187 if (parent->right == node)
189 /* Rotation between node and parent. */
190 grandparent->left = rotate_left (parent, node);
192 parent = grandparent->left;
194 /* grandparent and uncle are BLACK. parent and node want to be
195 RED. parent = grandparent->left. node = parent->left.
200 parent uncle --> node grandparent
206 *grandparentp = rotate_right (parent, grandparent);
207 parent->color = BLACK;
208 node->color = grandparent->color = RED;
210 else /* grandparent->right == parent */
212 if (parent->left == node)
214 /* Rotation between node and parent. */
215 grandparent->right = rotate_right (node, parent);
217 parent = grandparent->right;
219 /* grandparent and uncle are BLACK. parent and node want to be
220 RED. parent = grandparent->right. node = parent->right.
225 uncle parent --> grandparent node
231 *grandparentp = rotate_left (grandparent, parent);
232 parent->color = BLACK;
233 node->color = grandparent->color = RED;
238 /* Start again with a new (node, parent) pair. */
239 parent = node->parent;
243 /* Change node's color from RED to BLACK. This increases the
244 tree's black-height. */
251 /* Ensure the tree is balanced, after a deletion operation.
252 CHILD was a grandchild of PARENT and is now its child. Between them,
253 a black node was removed. CHILD is also black, or NULL.
254 (CHILD can also be NULL. But PARENT is non-NULL.) */
256 rebalance_after_remove (gl_oset_t set, gl_oset_node_t child, gl_oset_node_t parent)
260 /* At this point, we reduced the black-height of the CHILD subtree by 1.
261 To make up, either look for a possibility to turn a RED to a BLACK
262 node, or try to reduce the black-height tree of CHILD's sibling
264 gl_oset_node_t *parentp;
266 if (parent->parent == NULL)
267 parentp = &set->root;
268 else if (parent->parent->left == parent)
269 parentp = &parent->parent->left;
270 else if (parent->parent->right == parent)
271 parentp = &parent->parent->right;
275 if (parent->left == child)
277 gl_oset_node_t sibling = parent->right;
278 /* sibling's black-height is >= 1. In particular,
287 if (sibling->color == RED)
289 /* sibling is RED, hence parent is BLACK and sibling's children
290 are non-NULL and BLACK.
295 child sibling --> parent SR
301 *parentp = rotate_left (parent, sibling);
303 sibling->color = BLACK;
305 /* Concentrate on the subtree of parent. The new sibling is
306 one of the old sibling's children, and known to be BLACK. */
307 parentp = &sibling->left;
308 sibling = parent->right;
310 /* Now we know that sibling is BLACK.
317 if (sibling->right != NULL && sibling->right->color == RED)
323 child sibling --> parent SR
329 *parentp = rotate_left (parent, sibling);
330 sibling->color = parent->color;
331 parent->color = BLACK;
332 sibling->right->color = BLACK;
335 else if (sibling->left != NULL && sibling->left->color == RED)
341 child sibling --> child SL
350 where SLL, SLR, SR are all black.
352 parent->right = rotate_right (sibling->left, sibling);
353 /* Change sibling from BLACK to RED and SL from RED to BLACK. */
354 sibling->color = RED;
355 sibling = parent->right;
356 sibling->color = BLACK;
358 /* Now do as in the previous case. */
359 *parentp = rotate_left (parent, sibling);
360 sibling->color = parent->color;
361 parent->color = BLACK;
362 sibling->right->color = BLACK;
367 if (parent->color == BLACK)
369 /* Change sibling from BLACK to RED. Then the entire
370 subtree at parent has decreased its black-height.
374 child sibling --> child sibling
377 sibling->color = RED;
383 /* Change parent from RED to BLACK, but compensate by
384 changing sibling from BLACK to RED.
388 child sibling --> child sibling
391 parent->color = BLACK;
392 sibling->color = RED;
397 else if (parent->right == child)
399 gl_oset_node_t sibling = parent->left;
400 /* sibling's black-height is >= 1. In particular,
409 if (sibling->color == RED)
411 /* sibling is RED, hence parent is BLACK and sibling's children
412 are non-NULL and BLACK.
417 sibling child --> SR parent
423 *parentp = rotate_right (sibling, parent);
425 sibling->color = BLACK;
427 /* Concentrate on the subtree of parent. The new sibling is
428 one of the old sibling's children, and known to be BLACK. */
429 parentp = &sibling->right;
430 sibling = parent->left;
432 /* Now we know that sibling is BLACK.
439 if (sibling->left != NULL && sibling->left->color == RED)
445 sibling child --> SL parent
451 *parentp = rotate_right (sibling, parent);
452 sibling->color = parent->color;
453 parent->color = BLACK;
454 sibling->left->color = BLACK;
457 else if (sibling->right != NULL && sibling->right->color == RED)
463 sibling child --> SR child
472 where SL, SRL, SRR are all black.
474 parent->left = rotate_left (sibling, sibling->right);
475 /* Change sibling from BLACK to RED and SL from RED to BLACK. */
476 sibling->color = RED;
477 sibling = parent->left;
478 sibling->color = BLACK;
480 /* Now do as in the previous case. */
481 *parentp = rotate_right (sibling, parent);
482 sibling->color = parent->color;
483 parent->color = BLACK;
484 sibling->left->color = BLACK;
489 if (parent->color == BLACK)
491 /* Change sibling from BLACK to RED. Then the entire
492 subtree at parent has decreased its black-height.
496 sibling child --> sibling child
499 sibling->color = RED;
505 /* Change parent from RED to BLACK, but compensate by
506 changing sibling from BLACK to RED.
510 sibling child --> sibling child
513 parent->color = BLACK;
514 sibling->color = RED;
522 /* Start again with a new (child, parent) pair. */
523 parent = child->parent;
525 #if 0 /* Already handled. */
526 if (child != NULL && child->color == RED)
528 child->color = BLACK;
538 static gl_oset_node_t
539 gl_tree_nx_add_first (gl_oset_t set, const void *elt)
541 /* Create new node. */
542 gl_oset_node_t new_node =
543 (struct gl_oset_node_impl *) malloc (sizeof (struct gl_oset_node_impl));
545 if (new_node == NULL)
548 new_node->left = NULL;
549 new_node->right = NULL;
550 new_node->value = elt;
552 /* Add it to the tree. */
553 if (set->root == NULL)
555 new_node->color = BLACK;
556 set->root = new_node;
557 new_node->parent = NULL;
563 for (node = set->root; node->left != NULL; )
566 node->left = new_node;
567 new_node->parent = node;
569 /* Color and rebalance. */
570 rebalance_after_add (set, new_node, node);
577 static gl_oset_node_t
578 gl_tree_nx_add_before (gl_oset_t set, gl_oset_node_t node, const void *elt)
580 /* Create new node. */
581 gl_oset_node_t new_node =
582 (struct gl_oset_node_impl *) malloc (sizeof (struct gl_oset_node_impl));
584 if (new_node == NULL)
587 new_node->left = NULL;
588 new_node->right = NULL;
589 new_node->value = elt;
591 /* Add it to the tree. */
592 if (node->left == NULL)
593 node->left = new_node;
596 for (node = node->left; node->right != NULL; )
598 node->right = new_node;
600 new_node->parent = node;
602 /* Color and rebalance. */
603 rebalance_after_add (set, new_node, node);
609 static gl_oset_node_t
610 gl_tree_nx_add_after (gl_oset_t set, gl_oset_node_t node, const void *elt)
612 /* Create new node. */
613 gl_oset_node_t new_node =
614 (struct gl_oset_node_impl *) malloc (sizeof (struct gl_oset_node_impl));
616 if (new_node == NULL)
619 new_node->left = NULL;
620 new_node->right = NULL;
621 new_node->value = elt;
623 /* Add it to the tree. */
624 if (node->right == NULL)
625 node->right = new_node;
628 for (node = node->right; node->left != NULL; )
630 node->left = new_node;
632 new_node->parent = node;
634 /* Color and rebalance. */
635 rebalance_after_add (set, new_node, node);
642 gl_tree_remove_node (gl_oset_t set, gl_oset_node_t node)
644 gl_oset_node_t parent = node->parent;
646 if (node->left == NULL)
648 /* Replace node with node->right. */
649 gl_oset_node_t child = node->right;
653 child->parent = parent;
654 /* Since node->left == NULL, child must be RED and of height 1,
655 hence node must have been BLACK. Recolor the child. */
656 child->color = BLACK;
662 if (parent->left == node)
663 parent->left = child;
664 else /* parent->right == node */
665 parent->right = child;
667 if (child == NULL && node->color == BLACK)
668 rebalance_after_remove (set, child, parent);
671 else if (node->right == NULL)
673 /* It is not absolutely necessary to treat this case. But the more
674 general case below is more complicated, hence slower. */
675 /* Replace node with node->left. */
676 gl_oset_node_t child = node->left;
678 child->parent = parent;
679 /* Since node->right == NULL, child must be RED and of height 1,
680 hence node must have been BLACK. Recolor the child. */
681 child->color = BLACK;
686 if (parent->left == node)
687 parent->left = child;
688 else /* parent->right == node */
689 parent->right = child;
694 /* Replace node with the rightmost element of the node->left subtree. */
695 gl_oset_node_t subst;
696 gl_oset_node_t subst_parent;
697 gl_oset_node_t child;
698 color_t removed_color;
700 for (subst = node->left; subst->right != NULL; )
701 subst = subst->right;
703 subst_parent = subst->parent;
707 removed_color = subst->color;
709 /* The case subst_parent == node is special: If we do nothing special,
710 we get confusion about node->left, subst->left and child->parent.
712 <==> The 'for' loop above terminated immediately.
713 <==> subst == subst_parent->left
714 [otherwise subst == subst_parent->right]
715 In this case, we would need to first set
716 child->parent = node; node->left = child;
717 and later - when we copy subst into node's position - again
718 child->parent = subst; subst->left = child;
719 Altogether a no-op. */
720 if (subst_parent != node)
723 child->parent = subst_parent;
724 subst_parent->right = child;
727 /* Copy subst into node's position.
728 (This is safer than to copy subst's value into node, keep node in
729 place, and free subst.) */
730 if (subst_parent != node)
732 subst->left = node->left;
733 subst->left->parent = subst;
735 subst->right = node->right;
736 subst->right->parent = subst;
737 subst->color = node->color;
738 subst->parent = parent;
741 else if (parent->left == node)
742 parent->left = subst;
743 else /* parent->right == node */
744 parent->right = subst;
746 if (removed_color == BLACK)
748 if (child != NULL && child->color == RED)
749 /* Recolor the child. */
750 child->color = BLACK;
752 /* Rebalancing starts at child's parent, that is subst_parent -
753 except when subst_parent == node. In this case, we need to use
754 its replacement, subst. */
755 rebalance_after_remove (set, child,
756 subst_parent != node ? subst_parent : subst);
761 if (set->base.dispose_fn != NULL)
762 set->base.dispose_fn (node->value);
767 /* Generic binary tree code. */
768 #include "gl_anytree_oset.h"
772 check_invariants (gl_oset_node_t node, gl_oset_node_t parent, size_t *counterp)
774 unsigned int left_blackheight =
775 (node->left != NULL ? check_invariants (node->left, node, counterp) : 0);
776 unsigned int right_blackheight =
777 (node->right != NULL ? check_invariants (node->right, node, counterp) : 0);
779 if (!(node->parent == parent))
781 if (!(node->color == BLACK || node->color == RED))
783 if (parent == NULL && !(node->color == BLACK))
785 if (!(left_blackheight == right_blackheight))
790 return left_blackheight + (node->color == BLACK ? 1 : 0);
793 gl_rbtree_oset_check_invariants (gl_oset_t set)
796 if (set->root != NULL)
797 check_invariants (set->root, NULL, &counter);
798 if (!(set->count == counter))
802 const struct gl_oset_implementation gl_rbtree_oset_implementation =
804 gl_tree_nx_create_empty,
807 gl_tree_search_atleast,
812 gl_tree_iterator_next,
813 gl_tree_iterator_free