1 /* Ordered set data type implemented by a binary tree.
2 Copyright (C) 2006 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. */
22 #include "gl_rbtree_oset.h"
28 /* A red-black tree is a binary tree where every node is colored black or
31 2. No red node has a red parent.
32 Or equivalently: No red node has a red child.
33 3. All paths from the root down to any NULL endpoint contain the same
34 number of black nodes.
35 Let's call this the "black-height" bh of the tree. It follows that every
36 such path contains exactly bh black and between 0 and bh red nodes. (The
37 extreme cases are a path containing only black nodes, and a path colored
38 alternatingly black-red-black-red-...-black-red.) The height of the tree
39 therefore is >= bh, <= 2*bh.
42 /* -------------------------- gl_oset_t Data Type -------------------------- */
44 /* Color of a node. */
45 typedef enum color { BLACK, RED } color_t;
47 /* Tree node implementation, valid for this file only. */
48 struct gl_oset_node_impl
50 struct gl_oset_node_impl *left; /* left branch, or NULL */
51 struct gl_oset_node_impl *right; /* right branch, or NULL */
52 /* Parent pointer, or NULL. The parent pointer is not needed for most
53 operations. It is needed so that a gl_oset_node_t can be returned
54 without memory allocation, on which the functions gl_oset_remove_node,
55 gl_oset_add_before, gl_oset_add_after can be implemented. */
56 struct gl_oset_node_impl *parent;
57 color_t color; /* node's color */
60 typedef struct gl_oset_node_impl * gl_oset_node_t;
62 /* Concrete gl_oset_impl type, valid for this file only. */
65 struct gl_oset_impl_base base;
66 struct gl_oset_node_impl *root; /* root node or NULL */
67 size_t count; /* number of nodes */
70 /* A red-black tree of height h has a black-height bh >= ceil(h/2) and
71 therefore at least 2^ceil(h/2) - 1 elements. So, h <= 116 (because a tree
72 of height h >= 117 would have at least 2^59 - 1 elements, and because even
74 sizeof (gl_oset_node_impl) * (2^59 - 1) > 2^64
75 this would exceed the address space of the machine. */
78 /* Rotate left a subtree.
86 Change the tree structure, update the branch sizes.
87 The caller must update the colors and register D as child of its parent. */
88 static inline gl_oset_node_t
89 rotate_left (gl_oset_node_t b_node, gl_oset_node_t d_node)
91 gl_oset_node_t c_node = d_node->left;
93 b_node->right = c_node;
94 d_node->left = b_node;
96 d_node->parent = b_node->parent;
97 b_node->parent = d_node;
99 c_node->parent = b_node;
104 /* Rotate right a subtree.
112 Change the tree structure, update the branch sizes.
113 The caller must update the colors and register B as child of its parent. */
114 static inline gl_oset_node_t
115 rotate_right (gl_oset_node_t b_node, gl_oset_node_t d_node)
117 gl_oset_node_t c_node = b_node->right;
119 d_node->left = c_node;
120 b_node->right = d_node;
122 b_node->parent = d_node->parent;
123 d_node->parent = b_node;
125 c_node->parent = d_node;
130 /* Ensure the tree is balanced, after an insertion operation.
131 Also assigns node->color.
132 parent is the given node's parent, known to be non-NULL. */
134 rebalance_after_add (gl_oset_t set, gl_oset_node_t node, gl_oset_node_t parent)
138 /* At this point, parent = node->parent != NULL.
139 Think of node->color being RED (although node->color is not yet
141 gl_oset_node_t grandparent;
142 gl_oset_node_t uncle;
144 if (parent->color == BLACK)
146 /* A RED color for node is acceptable. */
151 grandparent = parent->parent;
152 /* Since parent is RED, we know that
153 grandparent is != NULL and colored BLACK. */
155 if (grandparent->left == parent)
156 uncle = grandparent->right;
157 else if (grandparent->right == parent)
158 uncle = grandparent->left;
162 if (uncle != NULL && uncle->color == RED)
164 /* Change grandparent from BLACK to RED, and
165 change parent and uncle from RED to BLACK.
166 This makes it acceptable for node to be RED. */
168 parent->color = uncle->color = BLACK;
173 /* grandparent and uncle are BLACK. parent is RED. node wants
175 In this case, recoloring is not sufficient. Need to perform
176 one or two rotations. */
177 gl_oset_node_t *grandparentp;
179 if (grandparent->parent == NULL)
180 grandparentp = &set->root;
181 else if (grandparent->parent->left == grandparent)
182 grandparentp = &grandparent->parent->left;
183 else if (grandparent->parent->right == grandparent)
184 grandparentp = &grandparent->parent->right;
188 if (grandparent->left == parent)
190 if (parent->right == node)
192 /* Rotation between node and parent. */
193 grandparent->left = rotate_left (parent, node);
195 parent = grandparent->left;
197 /* grandparent and uncle are BLACK. parent and node want to be
198 RED. parent = grandparent->left. node = parent->left.
203 parent uncle --> node grandparent
209 *grandparentp = rotate_right (parent, grandparent);
210 parent->color = BLACK;
211 node->color = grandparent->color = RED;
213 else /* grandparent->right == parent */
215 if (parent->left == node)
217 /* Rotation between node and parent. */
218 grandparent->right = rotate_right (node, parent);
220 parent = grandparent->right;
222 /* grandparent and uncle are BLACK. parent and node want to be
223 RED. parent = grandparent->right. node = parent->right.
228 uncle parent --> grandparent node
234 *grandparentp = rotate_left (grandparent, parent);
235 parent->color = BLACK;
236 node->color = grandparent->color = RED;
241 /* Start again with a new (node, parent) pair. */
242 parent = node->parent;
246 /* Change node's color from RED to BLACK. This increases the
247 tree's black-height. */
254 /* Ensure the tree is balanced, after a deletion operation.
255 CHILD was a grandchild of PARENT and is now its child. Between them,
256 a black node was removed. CHILD is also black, or NULL.
257 (CHILD can also be NULL. But PARENT is non-NULL.) */
259 rebalance_after_remove (gl_oset_t set, gl_oset_node_t child, gl_oset_node_t parent)
263 /* At this point, we reduced the black-height of the CHILD subtree by 1.
264 To make up, either look for a possibility to turn a RED to a BLACK
265 node, or try to reduce the black-height tree of CHILD's sibling
267 gl_oset_node_t *parentp;
269 if (parent->parent == NULL)
270 parentp = &set->root;
271 else if (parent->parent->left == parent)
272 parentp = &parent->parent->left;
273 else if (parent->parent->right == parent)
274 parentp = &parent->parent->right;
278 if (parent->left == child)
280 gl_oset_node_t sibling = parent->right;
281 /* sibling's black-height is >= 1. In particular,
290 if (sibling->color == RED)
292 /* sibling is RED, hence parent is BLACK and sibling's children
293 are non-NULL and BLACK.
298 child sibling --> parent SR
304 *parentp = rotate_left (parent, sibling);
306 sibling->color = BLACK;
308 /* Concentrate on the subtree of parent. The new sibling is
309 one of the old sibling's children, and known to be BLACK. */
310 parentp = &sibling->left;
311 sibling = parent->right;
313 /* Now we know that sibling is BLACK.
320 if (sibling->right != NULL && sibling->right->color == RED)
326 child sibling --> parent SR
332 *parentp = rotate_left (parent, sibling);
333 sibling->color = parent->color;
334 parent->color = BLACK;
335 sibling->right->color = BLACK;
338 else if (sibling->left != NULL && sibling->left->color == RED)
344 child sibling --> child SL
353 where SLL, SLR, SR are all black.
355 parent->right = rotate_right (sibling->left, sibling);
356 /* Change sibling from BLACK to RED and SL from RED to BLACK. */
357 sibling->color = RED;
358 sibling = parent->right;
359 sibling->color = BLACK;
361 /* Now do as in the previous case. */
362 *parentp = rotate_left (parent, sibling);
363 sibling->color = parent->color;
364 parent->color = BLACK;
365 sibling->right->color = BLACK;
370 if (parent->color == BLACK)
372 /* Change sibling from BLACK to RED. Then the entire
373 subtree at parent has decreased its black-height.
377 child sibling --> child sibling
380 sibling->color = RED;
386 /* Change parent from RED to BLACK, but compensate by
387 changing sibling from BLACK to RED.
391 child sibling --> child sibling
394 parent->color = BLACK;
395 sibling->color = RED;
400 else if (parent->right == child)
402 gl_oset_node_t sibling = parent->left;
403 /* sibling's black-height is >= 1. In particular,
412 if (sibling->color == RED)
414 /* sibling is RED, hence parent is BLACK and sibling's children
415 are non-NULL and BLACK.
420 sibling child --> SR parent
426 *parentp = rotate_right (sibling, parent);
428 sibling->color = BLACK;
430 /* Concentrate on the subtree of parent. The new sibling is
431 one of the old sibling's children, and known to be BLACK. */
432 parentp = &sibling->right;
433 sibling = parent->left;
435 /* Now we know that sibling is BLACK.
442 if (sibling->left != NULL && sibling->left->color == RED)
448 sibling child --> SL parent
454 *parentp = rotate_right (sibling, parent);
455 sibling->color = parent->color;
456 parent->color = BLACK;
457 sibling->left->color = BLACK;
460 else if (sibling->right != NULL && sibling->right->color == RED)
466 sibling child --> SR child
475 where SL, SRL, SRR are all black.
477 parent->left = rotate_left (sibling, sibling->right);
478 /* Change sibling from BLACK to RED and SL from RED to BLACK. */
479 sibling->color = RED;
480 sibling = parent->left;
481 sibling->color = BLACK;
483 /* Now do as in the previous case. */
484 *parentp = rotate_right (sibling, parent);
485 sibling->color = parent->color;
486 parent->color = BLACK;
487 sibling->left->color = BLACK;
492 if (parent->color == BLACK)
494 /* Change sibling from BLACK to RED. Then the entire
495 subtree at parent has decreased its black-height.
499 sibling child --> sibling child
502 sibling->color = RED;
508 /* Change parent from RED to BLACK, but compensate by
509 changing sibling from BLACK to RED.
513 sibling child --> sibling child
516 parent->color = BLACK;
517 sibling->color = RED;
525 /* Start again with a new (child, parent) pair. */
526 parent = child->parent;
528 #if 0 /* Already handled. */
529 if (child != NULL && child->color == RED)
531 child->color = BLACK;
541 static gl_oset_node_t
542 gl_tree_add_first (gl_oset_t set, const void *elt)
544 /* Create new node. */
545 gl_oset_node_t new_node =
546 (struct gl_oset_node_impl *) xmalloc (sizeof (struct gl_oset_node_impl));
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_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 *) xmalloc (sizeof (struct gl_oset_node_impl));
584 new_node->left = NULL;
585 new_node->right = NULL;
586 new_node->value = elt;
588 /* Add it to the tree. */
589 if (node->left == NULL)
590 node->left = new_node;
593 for (node = node->left; node->right != NULL; )
595 node->right = new_node;
597 new_node->parent = node;
599 /* Color and rebalance. */
600 rebalance_after_add (set, new_node, node);
606 static gl_oset_node_t
607 gl_tree_add_after (gl_oset_t set, gl_oset_node_t node, const void *elt)
609 /* Create new node. */
610 gl_oset_node_t new_node =
611 (struct gl_oset_node_impl *) xmalloc (sizeof (struct gl_oset_node_impl));
613 new_node->left = NULL;
614 new_node->right = NULL;
615 new_node->value = elt;
617 /* Add it to the tree. */
618 if (node->right == NULL)
619 node->right = new_node;
622 for (node = node->right; node->left != NULL; )
624 node->left = new_node;
626 new_node->parent = node;
628 /* Color and rebalance. */
629 rebalance_after_add (set, new_node, node);
636 gl_tree_remove_node (gl_oset_t set, gl_oset_node_t node)
638 gl_oset_node_t parent = node->parent;
640 if (node->left == NULL)
642 /* Replace node with node->right. */
643 gl_oset_node_t child = node->right;
647 child->parent = parent;
648 /* Since node->left == NULL, child must be RED and of height 1,
649 hence node must have been BLACK. Recolor the child. */
650 child->color = BLACK;
656 if (parent->left == node)
657 parent->left = child;
658 else /* parent->right == node */
659 parent->right = child;
661 if (child == NULL && node->color == BLACK)
662 rebalance_after_remove (set, child, parent);
665 else if (node->right == NULL)
667 /* It is not absolutely necessary to treat this case. But the more
668 general case below is more complicated, hence slower. */
669 /* Replace node with node->left. */
670 gl_oset_node_t child = node->left;
672 child->parent = parent;
673 /* Since node->right == NULL, child must be RED and of height 1,
674 hence node must have been BLACK. Recolor the child. */
675 child->color = BLACK;
680 if (parent->left == node)
681 parent->left = child;
682 else /* parent->right == node */
683 parent->right = child;
688 /* Replace node with the rightmost element of the node->left subtree. */
689 gl_oset_node_t subst;
690 gl_oset_node_t subst_parent;
691 gl_oset_node_t child;
692 color_t removed_color;
694 for (subst = node->left; subst->right != NULL; )
695 subst = subst->right;
697 subst_parent = subst->parent;
701 removed_color = subst->color;
703 /* The case subst_parent == node is special: If we do nothing special,
704 we get confusion about node->left, subst->left and child->parent.
706 <==> The 'for' loop above terminated immediately.
707 <==> subst == subst_parent->left
708 [otherwise subst == subst_parent->right]
709 In this case, we would need to first set
710 child->parent = node; node->left = child;
711 and later - when we copy subst into node's position - again
712 child->parent = subst; subst->left = child;
713 Altogether a no-op. */
714 if (subst_parent != node)
717 child->parent = subst_parent;
718 subst_parent->right = child;
721 /* Copy subst into node's position.
722 (This is safer than to copy subst's value into node, keep node in
723 place, and free subst.) */
724 if (subst_parent != node)
726 subst->left = node->left;
727 subst->left->parent = subst;
729 subst->right = node->right;
730 subst->right->parent = subst;
731 subst->color = node->color;
732 subst->parent = parent;
735 else if (parent->left == node)
736 parent->left = subst;
737 else /* parent->right == node */
738 parent->right = subst;
740 if (removed_color == BLACK)
742 if (child != NULL && child->color == RED)
743 /* Recolor the child. */
744 child->color = BLACK;
746 /* Rebalancing starts at child's parent, that is subst_parent -
747 except when subst_parent == node. In this case, we need to use
748 its replacement, subst. */
749 rebalance_after_remove (set, child,
750 subst_parent != node ? subst_parent : subst);
759 /* Generic binary tree code. */
760 #include "gl_anytree_oset.h"
764 check_invariants (gl_oset_node_t node, gl_oset_node_t parent, size_t *counterp)
766 unsigned int left_blackheight =
767 (node->left != NULL ? check_invariants (node->left, node, counterp) : 0);
768 unsigned int right_blackheight =
769 (node->right != NULL ? check_invariants (node->right, node, counterp) : 0);
771 if (!(node->parent == parent))
773 if (!(node->color == BLACK || node->color == RED))
775 if (parent == NULL && !(node->color == BLACK))
777 if (!(left_blackheight == right_blackheight))
782 return left_blackheight + (node->color == BLACK ? 1 : 0);
785 gl_rbtree_oset_check_invariants (gl_oset_t set)
788 if (set->root != NULL)
789 check_invariants (set->root, NULL, &counter);
790 if (!(set->count == counter))
794 const struct gl_oset_implementation gl_rbtree_oset_implementation =
796 gl_tree_create_empty,
799 gl_tree_search_atleast,
804 gl_tree_iterator_next,
805 gl_tree_iterator_free