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. */
24 #include "gl_rbtree_oset.h"
30 /* A red-black tree is a binary tree where every node is colored black or
33 2. No red node has a red parent.
34 Or equivalently: No red node has a red child.
35 3. All paths from the root down to any NULL endpoint contain the same
36 number of black nodes.
37 Let's call this the "black-height" bh of the tree. It follows that every
38 such path contains exactly bh black and between 0 and bh red nodes. (The
39 extreme cases are a path containing only black nodes, and a path colored
40 alternatingly black-red-black-red-...-black-red.) The height of the tree
41 therefore is >= bh, <= 2*bh.
44 /* -------------------------- gl_oset_t Data Type -------------------------- */
46 /* Color of a node. */
47 typedef enum color { BLACK, RED } color_t;
49 /* Tree node implementation, valid for this file only. */
50 struct gl_oset_node_impl
52 struct gl_oset_node_impl *left; /* left branch, or NULL */
53 struct gl_oset_node_impl *right; /* right branch, or NULL */
54 /* Parent pointer, or NULL. The parent pointer is not needed for most
55 operations. It is needed so that a gl_oset_node_t can be returned
56 without memory allocation, on which the functions gl_oset_remove_node,
57 gl_oset_add_before, gl_oset_add_after can be implemented. */
58 struct gl_oset_node_impl *parent;
59 color_t color; /* node's color */
62 typedef struct gl_oset_node_impl * gl_oset_node_t;
64 /* Concrete gl_oset_impl type, valid for this file only. */
67 struct gl_oset_impl_base base;
68 struct gl_oset_node_impl *root; /* root node or NULL */
69 size_t count; /* number of nodes */
72 /* A red-black tree of height h has a black-height bh >= ceil(h/2) and
73 therefore at least 2^ceil(h/2) - 1 elements. So, h <= 116 (because a tree
74 of height h >= 117 would have at least 2^59 - 1 elements, and because even
76 sizeof (gl_oset_node_impl) * (2^59 - 1) > 2^64
77 this would exceed the address space of the machine. */
80 /* Rotate left a subtree.
88 Change the tree structure, update the branch sizes.
89 The caller must update the colors and register D as child of its parent. */
90 static inline gl_oset_node_t
91 rotate_left (gl_oset_node_t b_node, gl_oset_node_t d_node)
93 gl_oset_node_t c_node = d_node->left;
95 b_node->right = c_node;
96 d_node->left = b_node;
98 d_node->parent = b_node->parent;
99 b_node->parent = d_node;
101 c_node->parent = b_node;
106 /* Rotate right a subtree.
114 Change the tree structure, update the branch sizes.
115 The caller must update the colors and register B as child of its parent. */
116 static inline gl_oset_node_t
117 rotate_right (gl_oset_node_t b_node, gl_oset_node_t d_node)
119 gl_oset_node_t c_node = b_node->right;
121 d_node->left = c_node;
122 b_node->right = d_node;
124 b_node->parent = d_node->parent;
125 d_node->parent = b_node;
127 c_node->parent = d_node;
132 /* Ensure the tree is balanced, after an insertion operation.
133 Also assigns node->color.
134 parent is the given node's parent, known to be non-NULL. */
136 rebalance_after_add (gl_oset_t set, gl_oset_node_t node, gl_oset_node_t parent)
140 /* At this point, parent = node->parent != NULL.
141 Think of node->color being RED (although node->color is not yet
143 gl_oset_node_t grandparent;
144 gl_oset_node_t uncle;
146 if (parent->color == BLACK)
148 /* A RED color for node is acceptable. */
153 grandparent = parent->parent;
154 /* Since parent is RED, we know that
155 grandparent is != NULL and colored BLACK. */
157 if (grandparent->left == parent)
158 uncle = grandparent->right;
159 else if (grandparent->right == parent)
160 uncle = grandparent->left;
164 if (uncle != NULL && uncle->color == RED)
166 /* Change grandparent from BLACK to RED, and
167 change parent and uncle from RED to BLACK.
168 This makes it acceptable for node to be RED. */
170 parent->color = uncle->color = BLACK;
175 /* grandparent and uncle are BLACK. parent is RED. node wants
177 In this case, recoloring is not sufficient. Need to perform
178 one or two rotations. */
179 gl_oset_node_t *grandparentp;
181 if (grandparent->parent == NULL)
182 grandparentp = &set->root;
183 else if (grandparent->parent->left == grandparent)
184 grandparentp = &grandparent->parent->left;
185 else if (grandparent->parent->right == grandparent)
186 grandparentp = &grandparent->parent->right;
190 if (grandparent->left == parent)
192 if (parent->right == node)
194 /* Rotation between node and parent. */
195 grandparent->left = rotate_left (parent, node);
197 parent = grandparent->left;
199 /* grandparent and uncle are BLACK. parent and node want to be
200 RED. parent = grandparent->left. node = parent->left.
205 parent uncle --> node grandparent
211 *grandparentp = rotate_right (parent, grandparent);
212 parent->color = BLACK;
213 node->color = grandparent->color = RED;
215 else /* grandparent->right == parent */
217 if (parent->left == node)
219 /* Rotation between node and parent. */
220 grandparent->right = rotate_right (node, parent);
222 parent = grandparent->right;
224 /* grandparent and uncle are BLACK. parent and node want to be
225 RED. parent = grandparent->right. node = parent->right.
230 uncle parent --> grandparent node
236 *grandparentp = rotate_left (grandparent, parent);
237 parent->color = BLACK;
238 node->color = grandparent->color = RED;
243 /* Start again with a new (node, parent) pair. */
244 parent = node->parent;
248 /* Change node's color from RED to BLACK. This increases the
249 tree's black-height. */
256 /* Ensure the tree is balanced, after a deletion operation.
257 CHILD was a grandchild of PARENT and is now its child. Between them,
258 a black node was removed. CHILD is also black, or NULL.
259 (CHILD can also be NULL. But PARENT is non-NULL.) */
261 rebalance_after_remove (gl_oset_t set, gl_oset_node_t child, gl_oset_node_t parent)
265 /* At this point, we reduced the black-height of the CHILD subtree by 1.
266 To make up, either look for a possibility to turn a RED to a BLACK
267 node, or try to reduce the black-height tree of CHILD's sibling
269 gl_oset_node_t *parentp;
271 if (parent->parent == NULL)
272 parentp = &set->root;
273 else if (parent->parent->left == parent)
274 parentp = &parent->parent->left;
275 else if (parent->parent->right == parent)
276 parentp = &parent->parent->right;
280 if (parent->left == child)
282 gl_oset_node_t sibling = parent->right;
283 /* sibling's black-height is >= 1. In particular,
292 if (sibling->color == RED)
294 /* sibling is RED, hence parent is BLACK and sibling's children
295 are non-NULL and BLACK.
300 child sibling --> parent SR
306 *parentp = rotate_left (parent, sibling);
308 sibling->color = BLACK;
310 /* Concentrate on the subtree of parent. The new sibling is
311 one of the old sibling's children, and known to be BLACK. */
312 parentp = &sibling->left;
313 sibling = parent->right;
315 /* Now we know that sibling is BLACK.
322 if (sibling->right != NULL && sibling->right->color == RED)
328 child sibling --> parent SR
334 *parentp = rotate_left (parent, sibling);
335 sibling->color = parent->color;
336 parent->color = BLACK;
337 sibling->right->color = BLACK;
340 else if (sibling->left != NULL && sibling->left->color == RED)
346 child sibling --> child SL
355 where SLL, SLR, SR are all black.
357 parent->right = rotate_right (sibling->left, sibling);
358 /* Change sibling from BLACK to RED and SL from RED to BLACK. */
359 sibling->color = RED;
360 sibling = parent->right;
361 sibling->color = BLACK;
363 /* Now do as in the previous case. */
364 *parentp = rotate_left (parent, sibling);
365 sibling->color = parent->color;
366 parent->color = BLACK;
367 sibling->right->color = BLACK;
372 if (parent->color == BLACK)
374 /* Change sibling from BLACK to RED. Then the entire
375 subtree at parent has decreased its black-height.
379 child sibling --> child sibling
382 sibling->color = RED;
388 /* Change parent from RED to BLACK, but compensate by
389 changing sibling from BLACK to RED.
393 child sibling --> child sibling
396 parent->color = BLACK;
397 sibling->color = RED;
402 else if (parent->right == child)
404 gl_oset_node_t sibling = parent->left;
405 /* sibling's black-height is >= 1. In particular,
414 if (sibling->color == RED)
416 /* sibling is RED, hence parent is BLACK and sibling's children
417 are non-NULL and BLACK.
422 sibling child --> SR parent
428 *parentp = rotate_right (sibling, parent);
430 sibling->color = BLACK;
432 /* Concentrate on the subtree of parent. The new sibling is
433 one of the old sibling's children, and known to be BLACK. */
434 parentp = &sibling->right;
435 sibling = parent->left;
437 /* Now we know that sibling is BLACK.
444 if (sibling->left != NULL && sibling->left->color == RED)
450 sibling child --> SL parent
456 *parentp = rotate_right (sibling, parent);
457 sibling->color = parent->color;
458 parent->color = BLACK;
459 sibling->left->color = BLACK;
462 else if (sibling->right != NULL && sibling->right->color == RED)
468 sibling child --> SR child
477 where SL, SRL, SRR are all black.
479 parent->left = rotate_left (sibling, sibling->right);
480 /* Change sibling from BLACK to RED and SL from RED to BLACK. */
481 sibling->color = RED;
482 sibling = parent->left;
483 sibling->color = BLACK;
485 /* Now do as in the previous case. */
486 *parentp = rotate_right (sibling, parent);
487 sibling->color = parent->color;
488 parent->color = BLACK;
489 sibling->left->color = BLACK;
494 if (parent->color == BLACK)
496 /* Change sibling from BLACK to RED. Then the entire
497 subtree at parent has decreased its black-height.
501 sibling child --> sibling child
504 sibling->color = RED;
510 /* Change parent from RED to BLACK, but compensate by
511 changing sibling from BLACK to RED.
515 sibling child --> sibling child
518 parent->color = BLACK;
519 sibling->color = RED;
527 /* Start again with a new (child, parent) pair. */
528 parent = child->parent;
530 #if 0 /* Already handled. */
531 if (child != NULL && child->color == RED)
533 child->color = BLACK;
543 static gl_oset_node_t
544 gl_tree_add_first (gl_oset_t set, const void *elt)
546 /* Create new node. */
547 gl_oset_node_t new_node =
548 (struct gl_oset_node_impl *) xmalloc (sizeof (struct gl_oset_node_impl));
550 new_node->left = NULL;
551 new_node->right = NULL;
552 new_node->value = elt;
554 /* Add it to the tree. */
555 if (set->root == NULL)
557 new_node->color = BLACK;
558 set->root = new_node;
559 new_node->parent = NULL;
565 for (node = set->root; node->left != NULL; )
568 node->left = new_node;
569 new_node->parent = node;
571 /* Color and rebalance. */
572 rebalance_after_add (set, new_node, node);
579 static gl_oset_node_t
580 gl_tree_add_before (gl_oset_t set, gl_oset_node_t node, const void *elt)
582 /* Create new node. */
583 gl_oset_node_t new_node =
584 (struct gl_oset_node_impl *) xmalloc (sizeof (struct gl_oset_node_impl));
586 new_node->left = NULL;
587 new_node->right = NULL;
588 new_node->value = elt;
590 /* Add it to the tree. */
591 if (node->left == NULL)
592 node->left = new_node;
595 for (node = node->left; node->right != NULL; )
597 node->right = new_node;
599 new_node->parent = node;
601 /* Color and rebalance. */
602 rebalance_after_add (set, new_node, node);
608 static gl_oset_node_t
609 gl_tree_add_after (gl_oset_t set, gl_oset_node_t node, const void *elt)
611 /* Create new node. */
612 gl_oset_node_t new_node =
613 (struct gl_oset_node_impl *) xmalloc (sizeof (struct gl_oset_node_impl));
615 new_node->left = NULL;
616 new_node->right = NULL;
617 new_node->value = elt;
619 /* Add it to the tree. */
620 if (node->right == NULL)
621 node->right = new_node;
624 for (node = node->right; node->left != NULL; )
626 node->left = new_node;
628 new_node->parent = node;
630 /* Color and rebalance. */
631 rebalance_after_add (set, new_node, node);
638 gl_tree_remove_node (gl_oset_t set, gl_oset_node_t node)
640 gl_oset_node_t parent = node->parent;
642 if (node->left == NULL)
644 /* Replace node with node->right. */
645 gl_oset_node_t child = node->right;
649 child->parent = parent;
650 /* Since node->left == NULL, child must be RED and of height 1,
651 hence node must have been BLACK. Recolor the child. */
652 child->color = BLACK;
658 if (parent->left == node)
659 parent->left = child;
660 else /* parent->right == node */
661 parent->right = child;
663 if (child == NULL && node->color == BLACK)
664 rebalance_after_remove (set, child, parent);
667 else if (node->right == NULL)
669 /* It is not absolutely necessary to treat this case. But the more
670 general case below is more complicated, hence slower. */
671 /* Replace node with node->left. */
672 gl_oset_node_t child = node->left;
674 child->parent = parent;
675 /* Since node->right == NULL, child must be RED and of height 1,
676 hence node must have been BLACK. Recolor the child. */
677 child->color = BLACK;
682 if (parent->left == node)
683 parent->left = child;
684 else /* parent->right == node */
685 parent->right = child;
690 /* Replace node with the rightmost element of the node->left subtree. */
691 gl_oset_node_t subst;
692 gl_oset_node_t subst_parent;
693 gl_oset_node_t child;
694 color_t removed_color;
696 for (subst = node->left; subst->right != NULL; )
697 subst = subst->right;
699 subst_parent = subst->parent;
703 removed_color = subst->color;
705 /* The case subst_parent == node is special: If we do nothing special,
706 we get confusion about node->left, subst->left and child->parent.
708 <==> The 'for' loop above terminated immediately.
709 <==> subst == subst_parent->left
710 [otherwise subst == subst_parent->right]
711 In this case, we would need to first set
712 child->parent = node; node->left = child;
713 and later - when we copy subst into node's position - again
714 child->parent = subst; subst->left = child;
715 Altogether a no-op. */
716 if (subst_parent != node)
719 child->parent = subst_parent;
720 subst_parent->right = child;
723 /* Copy subst into node's position.
724 (This is safer than to copy subst's value into node, keep node in
725 place, and free subst.) */
726 if (subst_parent != node)
728 subst->left = node->left;
729 subst->left->parent = subst;
731 subst->right = node->right;
732 subst->right->parent = subst;
733 subst->color = node->color;
734 subst->parent = parent;
737 else if (parent->left == node)
738 parent->left = subst;
739 else /* parent->right == node */
740 parent->right = subst;
742 if (removed_color == BLACK)
744 if (child != NULL && child->color == RED)
745 /* Recolor the child. */
746 child->color = BLACK;
748 /* Rebalancing starts at child's parent, that is subst_parent -
749 except when subst_parent == node. In this case, we need to use
750 its replacement, subst. */
751 rebalance_after_remove (set, child,
752 subst_parent != node ? subst_parent : subst);
761 /* Generic binary tree code. */
762 #include "gl_anytree_oset.h"
766 check_invariants (gl_oset_node_t node, gl_oset_node_t parent, size_t *counterp)
768 unsigned int left_blackheight =
769 (node->left != NULL ? check_invariants (node->left, node, counterp) : 0);
770 unsigned int right_blackheight =
771 (node->right != NULL ? check_invariants (node->right, node, counterp) : 0);
773 if (!(node->parent == parent))
775 if (!(node->color == BLACK || node->color == RED))
777 if (parent == NULL && !(node->color == BLACK))
779 if (!(left_blackheight == right_blackheight))
784 return left_blackheight + (node->color == BLACK ? 1 : 0);
787 gl_rbtree_oset_check_invariants (gl_oset_t set)
790 if (set->root != NULL)
791 check_invariants (set->root, NULL, &counter);
792 if (!(set->count == counter))
796 const struct gl_oset_implementation gl_rbtree_oset_implementation =
798 gl_tree_create_empty,
805 gl_tree_iterator_next,
806 gl_tree_iterator_free