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
35rb_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
50void 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
63int 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
78rb_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
87rb_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
96void 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
106rb_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
139rb_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
172rb_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
201void 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 */
219void 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
228rb_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
241void 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
251void 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
259int rbtree_size(rb_tree * tree)
260{
261	return tree->isize;
262}
263
264/* Returns the depth of the tree */
265
266int 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
275int 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
282rb_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
360rb_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
419rb_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
479void 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
487void 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
603rb_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
614rb_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
625rb_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
645void 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
678void 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
711void 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
821void 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
1060void rbtree_traverse(rb_tree * tree, opr * op)
1061{
1062	rbnode_traverse(tree->root, op);
1063}
1064