1 /*
2 * Copyright (c) International Business Machines Corp., 2001-2004
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See
12 * the GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17 */
18 #include <stdio.h>
19 #include <stdlib.h>
20 #include <assert.h>
21 #include "rbt.h"
22
23 /*
24 * ***********************************************
25 *
26 * D.H. IBM, S. Rao
27 *
28 * Module: Operations executed on red-black struct
29 *
30 * ***********************************************
31 */
32
33 /* Construct a red-black tree node */
34
rbnode_construct(datatype object,rb_color color)35 rb_node *rbnode_construct(datatype object, rb_color color)
36 {
37 rb_node *node = (rb_node *) malloc(sizeof(rb_node));
38 if (!node) {
39 fprintf(stderr, "Memory Shortage - No Execution Possible\n");
40 return NULL;
41 }
42 node->object = object;
43 node->color = color;
44 node->parent = node->right = node->left = NULL;
45 return node;
46 }
47
48 /* Destructor of a red-black tree node */
49
rbnode_destruct(rb_node * node,destructor d)50 void rbnode_destruct(rb_node * node, destructor d)
51 {
52 if (!node)
53 return;
54 if (d != NULL)
55 d(node->object);
56 rbnode_destruct(node->right, d);
57 rbnode_destruct(node->left, d);
58 free(node);
59 }
60
61 /* Determine the depth of the subtree spanned by a given node */
62
rbnode_depth(rb_node * node)63 int rbnode_depth(rb_node * node)
64 {
65 /* Recursively determine the depth of the left and right
66 * subtrees
67 */
68 int irightdepth = (node->right) ? rbnode_depth(node->right) : 0;
69 int ileftdepth = (node->left) ? rbnode_depth(node->left) : 0;
70
71 /* Return the maximal child depth + 1 (the current node) */
72 return ((irightdepth >
73 ileftdepth) ? (irightdepth + 1) : (ileftdepth + 1));
74 }
75
76 /* Return the leftmost leaf in the tree */
77
rbnode_minimum(rb_node * node)78 rb_node *rbnode_minimum(rb_node * node)
79 {
80 while (node->left)
81 node = node->left;
82 return node;
83 }
84
85 /* Return the rightmost leaf in the tree */
86
rbnode_maximum(rb_node * node)87 rb_node *rbnode_maximum(rb_node * node)
88 {
89 while (node->right)
90 node = node->right;
91 return node;
92 }
93
94 /* Replace an object */
95
rbnode_replace(rb_node * node,datatype object)96 void rbnode_replace(rb_node * node, datatype object)
97 {
98 /* Make sure the replacement does not violate the tree order
99 * Replace the object at the node
100 */
101 node->object = object;
102 }
103
104 /* Get the next node in the tree (according to the tree order) */
105
rbnode_successor(rb_node * node)106 rb_node *rbnode_successor(rb_node * node)
107 {
108 rb_node *succ_node;
109
110 if (node->right) {
111
112 /* If there is a right child, the successor is the
113 * minimal object in the sub-tree spanned by this
114 * child.
115 */
116
117 succ_node = node->right;
118 while (succ_node->left)
119 succ_node = succ_node->left;
120 } else {
121
122 /* Otherwise, go up the tree until reaching the parent
123 * from the left direction.
124 */
125
126 rb_node *prev_node = node;
127 succ_node = node->parent;
128 while (succ_node && prev_node == succ_node->right) {
129 prev_node = succ_node;
130 succ_node = succ_node->parent;
131 }
132 }
133
134 return (succ_node);
135 }
136
137 /* Get the previous node in the tree (according to the tree order) */
138
rbnode_predecessor(rb_node * node)139 rb_node *rbnode_predecessor(rb_node * node)
140 {
141 rb_node *pred_node;
142
143 if (node->left) {
144
145 /* If there is a left child, the predecessor is the
146 * maximal object in the sub-tree spanned by this
147 * child.
148 */
149
150 pred_node = node->left;
151 while (pred_node->right)
152 pred_node = pred_node->right;
153 } else {
154
155 /* Otherwise, go up the tree until reaching the parent
156 * from the right direction.
157 */
158
159 rb_node *prev_node = node;
160 pred_node = node->parent;
161 while (pred_node && prev_node == pred_node->left) {
162 prev_node = pred_node;
163 pred_node = pred_node->parent;
164 }
165 }
166
167 return (pred_node);
168 }
169
170 /* Return a pointer to a duplication of the given node */
171
rbnode_duplicate(rb_node * node)172 rb_node *rbnode_duplicate(rb_node * node)
173 {
174 /* Create a node of the same color, containing the same
175 * object
176 */
177 rb_node *dup_node = rbnode_construct(node->object, node->color);
178 if (!dup_node)
179 return NULL;
180
181 /* Duplicate the children recursively */
182 if (node->right) {
183 dup_node->right = rbnode_duplicate(node->right);
184 dup_node->right->parent = dup_node;
185 } else {
186 dup_node->right = NULL;
187 }
188
189 if (node->left) {
190 dup_node->left = rbnode_duplicate(node->left);
191 dup_node->left->parent = dup_node;
192 } else {
193 dup_node->left = NULL;
194 }
195
196 return dup_node; /* Return the duplicated node */
197 }
198
199 /* Traverse a red-black subtree */
200
rbnode_traverse(rb_node * node,opr * op)201 void rbnode_traverse(rb_node * node, opr * op)
202 {
203 if (!node)
204 return;
205 rbnode_traverse(node->left, op);
206 op(node->object);
207 rbnode_traverse(node->right, op);
208 }
209
210 /*
211 * ***********************************
212 *
213 * Operations on rb_tree struct
214 *
215 * ***********************************
216 */
217
218 /* Intialize a tree */
rbtree_init(rb_tree * tree)219 void rbtree_init(rb_tree * tree)
220 {
221 /* tree->comp = comp; */
222 tree->isize = 0;
223 tree->root = NULL;
224 }
225
226 /* Construct a tree given a comparison function */
227
rbtree_construct()228 rb_tree *rbtree_construct()
229 {
230 rb_tree *tree = (rb_tree *) malloc(sizeof(rb_tree));
231 if (!tree) {
232 fprintf(stderr, "Memory Issue - Shortge Exists!\n");
233 return NULL;
234 }
235 rbtree_init(tree);
236 return tree;
237 }
238
239 /* Remove all objects from a black-red tree */
240
rbtree_clean(rb_tree * tree,destructor d)241 void rbtree_clean(rb_tree * tree, destructor d)
242 {
243 if (tree->root)
244 rbnode_destruct(tree->root, d);
245 tree->root = NULL;
246 tree->isize = 0;
247 }
248
249 /* Destruct a red-black tree */
250
rbtree_destruct(rb_tree * tree,destructor d)251 void rbtree_destruct(rb_tree * tree, destructor d)
252 {
253 rbtree_clean(tree, d);
254 free(tree);
255 }
256
257 /* Returns the size of the tree */
258
rbtree_size(rb_tree * tree)259 int rbtree_size(rb_tree * tree)
260 {
261 return tree->isize;
262 }
263
264 /* Returns the depth of the tree */
265
rbtree_depth(rb_tree * tree)266 int rbtree_depth(rb_tree * tree)
267 {
268 if (!(tree->root))
269 return 0;
270 return rbnode_depth(tree->root);
271 }
272
273 /* Check whether the tree contains a certain object */
274
rbtree_contains(rb_tree * tree,datatype object)275 int rbtree_contains(rb_tree * tree, datatype object)
276 {
277 return (rbtree_find(tree, object) != NULL);
278 }
279
280 /* Insert an object into the rb-tree */
281
rbtree_insert(rb_tree * tree,datatype object)282 rb_node *rbtree_insert(rb_tree * tree, datatype object)
283 {
284 rb_node *cur_node;
285 rb_node *new_node;
286 int comp_result = 0;
287
288 if (!(tree->root)) {
289 /* Assign a new root node (the root is always
290 * black)
291 */
292 new_node = rbnode_construct(object, black);
293 if (!new_node)
294 return NULL;
295 tree->root = new_node;
296 tree->isize = 1;
297 return new_node;
298 }
299
300 /* Find a spot for the new object, insert the object as a red
301 * leaf
302 */
303
304 cur_node = tree->root;
305 new_node = rbnode_construct(object, red);
306 if (!new_node)
307 return NULL;
308
309 while (cur_node) {
310 /* Compare inserted object with the object stored in
311 * the current node
312 */
313 comp_result = COMP_NODES(object, cur_node->object);
314 if (comp_result == 0) {
315 printf
316 ("Attempted to insert duplicate node, aborting\n");
317 free(new_node);
318 return NULL;
319 }
320 if (comp_result > 0) {
321 if (!(cur_node->left)) {
322 /* Insert the new leaf as the left
323 * child of the current node
324 */
325 cur_node->left = new_node;
326 new_node->parent = cur_node;
327 cur_node = NULL; /* Terminate the while loop */
328 } else {
329 /* Go to the left subtree */
330 cur_node = cur_node->left;
331 }
332 } else {
333 if (!(cur_node->right)) {
334 /* Insert the new leaf as the right
335 * child of the current node
336 */
337 cur_node->right = new_node;
338 new_node->parent = cur_node;
339 cur_node = NULL; /* Terminate the while loop */
340 } else {
341 /* Go to the right subtree */
342 cur_node = cur_node->right;
343 }
344 }
345 }
346
347 /* Mark the fact that a new node was added */
348 tree->isize++;
349
350 /* Fix the tree properties */
351 rbtree_insert_fixup(tree, new_node);
352
353 return new_node;
354 }
355
356 /* Insert a new object to the tree as the a successor of a given
357 * node
358 */
359
insert_successor_at(rb_tree * tree,rb_node * at_node,datatype object)360 rb_node *insert_successor_at(rb_tree * tree, rb_node * at_node, datatype object)
361 {
362 rb_node *parent;
363 rb_node *new_node;
364
365 if (!(tree->root)) {
366 /* Assign a new root node (the root is always
367 * black)
368 */
369 new_node = rbnode_construct(object, black);
370 if (!new_node)
371 return NULL;
372 tree->root = new_node;
373 tree->isize = 1;
374 return new_node;
375 }
376
377 /* Insert the new object as a red leaf, being the successor of
378 * node
379 */
380 new_node = rbnode_construct(object, red);
381 if (!new_node)
382 return NULL;
383
384 if (!at_node) {
385 /* The new node should become the tree's minimum Place
386 * is as the left child of the current minimal leaf
387 */
388 parent = rbnode_minimum(tree->root);
389 parent->left = new_node;
390 } else {
391 /* Make sure the insertion does not violate the tree
392 * order In case given node has no right child, place
393 * the new node as its right child. Otherwise, place
394 * it at the leftmost position at the sub-tree rooted
395 * at its right side.
396 */
397 if (!at_node->right) {
398 parent = at_node;
399 parent->right = new_node;
400 } else {
401 parent = rbnode_minimum(at_node->right);
402 parent->left = new_node;
403 }
404 }
405
406 new_node->parent = parent;
407
408 /* Mark that a new node was added */
409 tree->isize++;
410
411 /* Fix the tree properties */
412 rbtree_insert_fixup(tree, new_node);
413
414 return new_node;
415 }
416
417 /* Insert a new object to the tree as the a predecessor of a given node */
418
insert_predecessor_at(rb_tree * tree,rb_node * at_node,datatype object)419 rb_node *insert_predecessor_at(rb_tree * tree, rb_node * at_node,
420 datatype object)
421 {
422 rb_node *parent;
423 rb_node *new_node;
424
425 if (!(tree->root)) {
426 /* Assign a new root node (the root is always
427 * black)
428 */
429 new_node = rbnode_construct(object, black);
430 if (!new_node)
431 return NULL;
432 tree->root = new_node;
433 tree->isize = 1;
434 return new_node;
435 }
436
437 /* Insert the new object as a red leaf, being the predecessor
438 * of at_node
439 */
440 new_node = rbnode_construct(object, red);
441 if (!new_node)
442 return NULL;
443
444 if (!at_node) {
445 /* The new node should become the tree maximum. Place
446 * is as the right child of the current maximal leaf
447 */
448 parent = rbnode_maximum(tree->root);
449 parent->right = new_node;
450 } else {
451 /* Make sure the insertion does not violate the tree
452 * order In case given node has no left child, place
453 * the new node as its left child. Otherwise, place it
454 * at the rightmost position at the sub-tree rooted at
455 * its left side.
456 */
457 if (!(at_node->left)) {
458 parent = at_node;
459 parent->left = new_node;
460 } else {
461 parent = rbnode_maximum(at_node->left);
462 parent->right = new_node;
463 }
464 }
465
466 new_node->parent = parent;
467
468 /* Mark that a new node was added */
469 tree->isize++;
470
471 /* Fix the tree properties */
472 rbtree_insert_fixup(tree, new_node);
473
474 return new_node;
475 }
476
477 /* Remove an object from the tree */
478
rbtree_remove(rb_tree * tree,datatype object,destructor d)479 void rbtree_remove(rb_tree * tree, datatype object, destructor d)
480 {
481 rb_node *node = rbtree_find(tree, object); /* Find the node */
482 rbtree_remove_at(tree, node, d); /* Remove the node */
483 }
484
485 /* Remove the object pointed by the given node. */
486
rbtree_remove_at(rb_tree * tree,rb_node * node,destructor d)487 void rbtree_remove_at(rb_tree * tree, rb_node * node, destructor d)
488 {
489 rb_node *child = NULL;
490
491 /* In case of deleting the single object stored in the tree,
492 * free the root, thus emptying the tree
493 */
494 if (tree->isize == 1) {
495 rbnode_destruct(tree->root, d);
496 tree->root = NULL;
497 tree->isize = 0;
498 return;
499 }
500
501 /* Remove the given node from the tree */
502 if (node->left && node->right) {
503 /* If the node we want to remove has two children,
504 * find its successor, which is the leftmost child in
505 * its right sub-tree and has at most one child (it
506 * may have a right child).
507 */
508 rb_node *succ_node = rbnode_minimum(node->right);
509
510 /* Now physically swap node and its successor. Notice
511 * this may temporarily violate the tree properties,
512 * but we are going to remove node anyway. This way
513 * we have moved node to a position were it is more
514 * convinient to delete it.
515 */
516 int immediate_succ = (node->right == succ_node);
517 rb_node *succ_parent = succ_node->parent;
518 rb_node *succ_left = succ_node->left;
519 rb_node *succ_right = succ_node->right;
520 rb_color succ_color = succ_node->color;
521
522 succ_node->parent = node->parent;
523 succ_node->left = node->left;
524 succ_node->right = immediate_succ ? node : node->right;
525 succ_node->color = node->color;
526
527 node->parent = immediate_succ ? succ_node : succ_parent;
528 node->left = succ_left;
529 node->right = succ_right;
530 node->color = succ_color;
531
532 if (!immediate_succ) {
533 if (succ_node == node->parent->left)
534 node->parent->left = node;
535 else
536 node->parent->right = node;
537 }
538
539 if (node->left)
540 node->left->parent = node;
541 if (node->right)
542 node->right->parent = node;
543
544 if (succ_node->parent) {
545 if (node == succ_node->parent->left)
546 succ_node->parent->left = succ_node;
547 else
548 succ_node->parent->right = succ_node;
549 } else {
550 tree->root = succ_node;
551 }
552
553 if (succ_node->left)
554 succ_node->left->parent = succ_node;
555 if (succ_node->right)
556 succ_node->right->parent = succ_node;
557 }
558
559 /* At this stage, the node we are going to remove has at most
560 * one child
561 */
562 child = (node->left) ? node->left : node->right;
563
564 /* Splice out the node to be removed, by linking its parent
565 * straight to the removed node's single child.
566 */
567 if (child)
568 child->parent = node->parent;
569
570 if (!(node->parent)) {
571 /* If we are deleting the root, make the child the new
572 * tree node
573 */
574 tree->root = child;
575 } else {
576 /* Link the removed node parent to its child */
577 if (node == node->parent->left)
578 node->parent->left = child;
579 else
580 node->parent->right = child;
581 }
582
583 /* Fix-up the red-black properties that may have been damaged:
584 * If we have just removed a black node, the black-depth
585 * property is no longer valid
586 */
587 if (node->color == black && child)
588 rbtree_remove_fixup(tree, child);
589
590 /* Delete the un-necessary node (nullify both its children
591 * because the node's destructor is recursive).
592 */
593 node->left = NULL;
594 node->right = NULL;
595 free(node);
596
597 /* Decrease the number of objects in the tree */
598 tree->isize--;
599 }
600
601 /* Get the tree minimum */
602
rbtree_minimum(rb_tree * tree)603 rb_node *rbtree_minimum(rb_tree * tree)
604 {
605 if (!(tree->root))
606 return NULL;
607
608 /* Return the leftmost leaf in the tree */
609 return rbnode_minimum(tree->root);
610 }
611
612 /* Get the tree maximum */
613
rbtree_maximum(rb_tree * tree)614 rb_node *rbtree_maximum(rb_tree * tree)
615 {
616 if (!(tree->root))
617 return NULL;
618
619 /* Return the rightmost leaf in the tree */
620 return rbnode_maximum(tree->root);
621 }
622
623 /* Return a pointer to the node containing the given object */
624
rbtree_find(rb_tree * tree,datatype object)625 rb_node *rbtree_find(rb_tree * tree, datatype object)
626 {
627 rb_node *cur_node = tree->root;
628 int comp_result;
629
630 while (cur_node) {
631 comp_result = COMP_NODES(object, cur_node->object);
632 /* In case of equality, we can return the current
633 * node.
634 */
635 if (comp_result == 0)
636 return cur_node;
637 /* Go down to the left or right child. */
638 cur_node = (comp_result > 0) ? cur_node->left : cur_node->right;
639 }
640
641 /* If we get here, the object is not in the tree */
642 return NULL;
643 }
644
rbtree_rotate_left(rb_tree * tree,rb_node * x_node)645 void rbtree_rotate_left(rb_tree * tree, rb_node * x_node)
646 {
647 /* Get the right child of the node */
648 rb_node *y_node = x_node->right;
649
650 /* Change its left subtree (T2) to x's right subtree */
651 x_node->right = y_node->left;
652
653 /* Link T2 to its new parent x */
654 if (y_node->left != NULL)
655 y_node->left->parent = x_node;
656
657 /* Assign x's parent to be y's parent */
658 y_node->parent = x_node->parent;
659
660 if (!(x_node->parent)) {
661 /* Make y the new tree root */
662 tree->root = y_node;
663 } else {
664 /* Assign a pointer to y from x's parent */
665 if (x_node == x_node->parent->left)
666 x_node->parent->left = y_node;
667 else
668 x_node->parent->right = y_node;
669 }
670
671 /* Assign x to be y's left child */
672 y_node->left = x_node;
673 x_node->parent = y_node;
674 }
675
676 /* Right-rotate the sub-tree spanned by the given node */
677
rbtree_rotate_right(rb_tree * tree,rb_node * y_node)678 void rbtree_rotate_right(rb_tree * tree, rb_node * y_node)
679 {
680 /* Get the left child of the node */
681 rb_node *x_node = y_node->left;
682
683 /* Change its right subtree (T2) to y's left subtree */
684 y_node->left = x_node->right;
685
686 /* Link T2 to its new parent y */
687 if (x_node->right != NULL)
688 x_node->right->parent = y_node;
689
690 /* Assign y's parent to be x's parent */
691 x_node->parent = y_node->parent;
692
693 if (!(y_node->parent)) {
694 /* Make x the new tree root */
695 tree->root = x_node;
696 } else {
697 /* Assign a pointer to x from y's parent */
698 if (y_node == y_node->parent->left)
699 y_node->parent->left = x_node;
700 else
701 y_node->parent->right = x_node;
702 }
703
704 /* Assign y to be x's right child */
705 x_node->right = y_node;
706 y_node->parent = x_node;
707 }
708
709 /* Fix the tree so it maintains the red-black properties after an insert */
710
rbtree_insert_fixup(rb_tree * tree,rb_node * node)711 void rbtree_insert_fixup(rb_tree * tree, rb_node * node)
712 {
713 /* Fix the red-black propreties. We may have inserted a red
714 * leaf as the child of a red parent - so we have to fix the
715 * coloring of the parent recursively.
716 */
717 rb_node *curr_node = node;
718 rb_node *grandparent;
719 rb_node *uncle;
720
721 assert(node && node->color == red);
722
723 while (curr_node != tree->root && curr_node->parent->color == red) {
724 /* Get a pointer to the current node's grandparent
725 * (the root is always black, so the red parent must
726 * have a parent).
727 */
728
729 grandparent = curr_node->parent->parent;
730
731 if (curr_node->parent == grandparent->left) {
732 /* If the red parent is a left child, the
733 * uncle is the right child of the grandparent.
734 */
735 uncle = grandparent->right;
736
737 if (uncle && uncle->color == red) {
738
739 /* If both parent and uncle are red,
740 * color them black and color the
741 * grandparent red. In case of a NULL
742 * uncle, treat it as a black node
743 */
744 curr_node->parent->color = black;
745 uncle->color = black;
746 grandparent->color = red;
747
748 /* Move to the grandparent */
749 curr_node = grandparent;
750 } else {
751 /* Make sure the current node is a
752 * right child. If not, left-rotate the
753 * parent's sub-tree so the parent
754 * becomes the right child of the
755 * current node (see _rotate_left).
756 */
757 if (curr_node == curr_node->parent->right) {
758 curr_node = curr_node->parent;
759 rbtree_rotate_left(tree, curr_node);
760 }
761
762 /* Color the parent black and the
763 * grandparent red
764 */
765 curr_node->parent->color = black;
766 grandparent->color = red;
767
768 /* Right-rotate the grandparent's
769 * sub-tree
770 */
771 rbtree_rotate_right(tree, grandparent);
772 }
773 } else {
774 /* If the red parent is a right child, the
775 * uncle is the left child of the grandparent.
776 */
777 uncle = grandparent->left;
778
779 if (uncle && uncle->color == red) {
780 /* If both parent and uncle are red,
781 * color them black and color the
782 * grandparent red. In case of a NULL
783 * uncle, treat it as a black node
784 */
785 curr_node->parent->color = black;
786 uncle->color = black;
787 grandparent->color = red;
788
789 /* Move to the grandparent */
790 curr_node = grandparent;
791 } else {
792 /* Make sure the current node is a
793 * left child. If not, right-rotate
794 * the parent's sub-tree so the parent
795 * becomes the left child of the
796 * current node.
797 */
798 if (curr_node == curr_node->parent->left) {
799 curr_node = curr_node->parent;
800 rbtree_rotate_right(tree, curr_node);
801 }
802
803 /* Color the parent black and the
804 * grandparent red
805 */
806 curr_node->parent->color = black;
807 grandparent->color = red;
808
809 /* Left-rotate the grandparent's
810 * sub-tree
811 */
812 rbtree_rotate_left(tree, grandparent);
813 }
814 }
815 }
816
817 /* Make sure that the root is black */
818 tree->root->color = black;
819 }
820
rbtree_remove_fixup(rb_tree * tree,rb_node * node)821 void rbtree_remove_fixup(rb_tree * tree, rb_node * node)
822 {
823 rb_node *curr_node = node;
824 rb_node *sibling;
825
826 while (curr_node != tree->root && curr_node->color == black) {
827 /* Get a pointer to the current node's sibling (notice
828 * that the node's parent must exist, since the node
829 * is not the root).
830 */
831 if (curr_node == curr_node->parent->left) {
832 /* If the current node is a left child, its
833 * sibling is the right child of the parent.
834 */
835 sibling = curr_node->parent->right;
836
837 /* Check the sibling's color. Notice that NULL
838 * nodes are treated as if they are colored
839 * black.
840 */
841 if (sibling && sibling->color == red) {
842 /* In case the sibling is red, color
843 * it black and rotate. Then color
844 * the parent red (the grandparent is
845 * now black)
846 */
847 sibling->color = black;
848 curr_node->parent->color = red;
849 rbtree_rotate_left(tree, curr_node->parent);
850 sibling = curr_node->parent->right;
851 }
852
853 if (sibling &&
854 (!(sibling->left) || sibling->left->color == black)
855 && (!(sibling->right)
856 || sibling->right->color == black)) {
857 /* If the sibling has two black
858 * children, color it red
859 */
860 sibling->color = red;
861 if (curr_node->parent->color == red) {
862 /* If the parent is red, we
863 * can safely color it black
864 * and terminate the fix
865 * process.
866 */
867 curr_node->parent->color = black;
868 /* In order to stop the while loop */
869 curr_node = tree->root;
870 } else {
871 /* The black depth of the
872 * entire sub-tree rooted at
873 * the parent is now too small
874 * - fix it up recursively.
875 */
876 curr_node = curr_node->parent;
877 }
878 } else {
879 if (!sibling) {
880 /* Take special care of the
881 * case of a NULL sibling
882 */
883 if (curr_node->parent->color == red) {
884 curr_node->parent->color =
885 black;
886 /* In order to stop
887 * the while loop */
888 curr_node = tree->root;
889 } else {
890 curr_node = curr_node->parent;
891 }
892 } else {
893 /* In this case, at least one
894 * of the sibling's children
895 * is red. It is therfore
896 * obvious that the sibling
897 * itself is black.
898 */
899 if (sibling->right
900 && sibling->right->color == red) {
901 /* If the right child
902 * of the sibling is
903 * red, color it black
904 * and rotate around
905 * the current parent.
906 */
907 sibling->right->color = black;
908 rbtree_rotate_left(tree,
909 curr_node->
910 parent);
911 } else {
912 /* If the left child
913 * of the sibling is
914 * red, rotate around
915 * the sibling, then
916 * rotate around the
917 * new sibling of our
918 * current node.
919 */
920 rbtree_rotate_right(tree,
921 sibling);
922 sibling =
923 curr_node->parent->right;
924 rbtree_rotate_left(tree,
925 sibling);
926 }
927
928 /* It is now safe to color the
929 * parent black and to
930 * terminate the fix process.
931 */
932 if (curr_node->parent->parent)
933 curr_node->parent->parent->
934 color =
935 curr_node->parent->color;
936 curr_node->parent->color = black;
937 /* In order to stop the while loop */
938 curr_node = tree->root;
939 }
940 }
941 } else {
942 /* If the current node is a right child, its
943 * sibling is the left child of the parent.
944 */
945 sibling = curr_node->parent->left;
946
947 /* Check the sibling's color. Notice that NULL
948 * nodes are treated as if they are colored
949 * black.
950 */
951 if (sibling && sibling->color == red) {
952 /* In case the sibling is red, color
953 * it black and rotate. Then color
954 * the parent red (the grandparent is
955 * now black).
956 */
957 sibling->color = black;
958 curr_node->parent->color = red;
959 rbtree_rotate_right(tree, curr_node->parent);
960
961 sibling = curr_node->parent->left;
962 }
963
964 if (sibling &&
965 (!(sibling->left) || sibling->left->color == black)
966 && (!(sibling->right)
967 || sibling->right->color == black)) {
968 /* If the sibling has two black children, color it red */
969 sibling->color = red;
970 if (curr_node->parent->color == red) {
971 /* If the parent is red, we
972 * can safely color it black
973 * and terminate the fix-up
974 * process.
975 */
976 curr_node->parent->color = black;
977 /* In order to stop the while
978 * loop
979 */
980 curr_node = tree->root;
981 } else {
982 /* The black depth of the
983 * entire sub-tree rooted at
984 * the parent is now too small
985 * - fix it up recursively.
986 */
987 curr_node = curr_node->parent;
988 }
989 } else {
990 if (!sibling) {
991 /* Take special care of the
992 * case of a NULL sibling */
993 if (curr_node->parent->color == red) {
994 curr_node->parent->color =
995 black;
996 /* In order to stop
997 * the while loop */
998 curr_node = tree->root;
999 } else {
1000 curr_node = curr_node->parent;
1001 }
1002 } else {
1003 /* In this case, at least one
1004 * of the sibling's children is
1005 * red. It is therfore obvious
1006 * that the sibling itself is
1007 * black.
1008 */
1009 if (sibling->left
1010 && sibling->left->color == red) {
1011 /* If the left child
1012 * of the sibling is
1013 * red, color it black
1014 * and rotate around
1015 * the current parent
1016 */
1017 sibling->left->color = black;
1018 rbtree_rotate_right(tree,
1019 curr_node->
1020 parent);
1021 } else {
1022 /* If the right child
1023 * of the sibling is
1024 * red, rotate around
1025 * the sibling, then
1026 * rotate around the
1027 * new sibling of our
1028 * current node
1029 */
1030 rbtree_rotate_left(tree,
1031 sibling);
1032 sibling =
1033 curr_node->parent->left;
1034 rbtree_rotate_right(tree,
1035 sibling);
1036 }
1037
1038 /* It is now safe to color the
1039 * parent black and to
1040 * terminate the fix process.
1041 */
1042 if (curr_node->parent->parent)
1043 curr_node->parent->parent->
1044 color =
1045 curr_node->parent->color;
1046 curr_node->parent->color = black;
1047 /* In order to stop the while loop */
1048 curr_node = tree->root;
1049 }
1050 }
1051 }
1052 }
1053
1054 /* The root can always be colored black */
1055 curr_node->color = black;
1056 }
1057
1058 /* Traverse a red-black tree */
1059
rbtree_traverse(rb_tree * tree,opr * op)1060 void rbtree_traverse(rb_tree * tree, opr * op)
1061 {
1062 rbnode_traverse(tree->root, op);
1063 }
1064