28  * Module: Operations executed on red-black struct
33 /* Construct a red-black tree node */
48 /* Destructor of a red-black tree node */
199 /* Traverse a red-black subtree */
239 /* Remove all objects from a black-red tree */
249 /* Destruct a red-black tree */
290 		 * black)  in rbtree_insert()
292 		new_node = rbnode_construct(object, black);  in rbtree_insert()
367 		 * black)  in insert_successor_at()
369 		new_node = rbnode_construct(object, black);  in insert_successor_at()
427 		 * black)  in insert_predecessor_at()
429 		new_node = rbnode_construct(object, black);  in insert_predecessor_at()
583 	/* Fix-up the red-black properties that may have been damaged:  in rbtree_remove_at()
584 	 * If we have just removed a black node, the black-depth  in rbtree_remove_at()
587 	if (node->color == black && child)  in rbtree_remove_at()
709 /* Fix the tree so it maintains the red-black properties after an insert */
713 	/* Fix the red-black propreties. We may have inserted a red  in rbtree_insert_fixup()
725 		 * (the root is always black, so the red parent must  in rbtree_insert_fixup()
740 				 * color them black and color the  in rbtree_insert_fixup()
742 				 * uncle, treat it as a black node  in rbtree_insert_fixup()
744 				curr_node->parent->color = black;  in rbtree_insert_fixup()
745 				uncle->color = black;  in rbtree_insert_fixup()
762 				/* Color the parent black and the  in rbtree_insert_fixup()
765 				curr_node->parent->color = black;  in rbtree_insert_fixup()
781 				 * color them black and color the  in rbtree_insert_fixup()
783 				 * uncle, treat it as a black node  in rbtree_insert_fixup()
785 				curr_node->parent->color = black;  in rbtree_insert_fixup()
786 				uncle->color = black;  in rbtree_insert_fixup()
803 				/* Color the parent black and the  in rbtree_insert_fixup()
806 				curr_node->parent->color = black;  in rbtree_insert_fixup()
817 	/* Make sure that the root is black */  in rbtree_insert_fixup()
818 	tree->root->color = black;  in rbtree_insert_fixup()
826 	while (curr_node != tree->root && curr_node->color == black) {  in rbtree_remove_fixup()
839 			 * black.  in rbtree_remove_fixup()
843 				 * it black and rotate.  Then color  in rbtree_remove_fixup()
845 				 * now black)  in rbtree_remove_fixup()
847 				sibling->color = black;  in rbtree_remove_fixup()
854 			    (!(sibling->left) || sibling->left->color == black)  in rbtree_remove_fixup()
856 				|| sibling->right->color == black)) {  in rbtree_remove_fixup()
857 				/* If the sibling has two black  in rbtree_remove_fixup()
863 					 * can safely color it black  in rbtree_remove_fixup()
867 					curr_node->parent->color = black;  in rbtree_remove_fixup()
871 					/* The black depth of the  in rbtree_remove_fixup()
885 						    black;  in rbtree_remove_fixup()
897 					 * itself is black.  in rbtree_remove_fixup()
903 						 * red, color it black  in rbtree_remove_fixup()
907 						sibling->right->color = black;  in rbtree_remove_fixup()
929 					 * parent black and to  in rbtree_remove_fixup()
936 					curr_node->parent->color = black;  in rbtree_remove_fixup()
949 			 * black.  in rbtree_remove_fixup()
953 				 * it black and rotate.  Then color  in rbtree_remove_fixup()
955 				 * now black).  in rbtree_remove_fixup()
957 				sibling->color = black;  in rbtree_remove_fixup()
965 			    (!(sibling->left) || sibling->left->color == black)  in rbtree_remove_fixup()
967 				|| sibling->right->color == black)) {  in rbtree_remove_fixup()
968 				/* If the sibling has two black children, color it red */  in rbtree_remove_fixup()
972 					 * can safely color it black  in rbtree_remove_fixup()
976 					curr_node->parent->color = black;  in rbtree_remove_fixup()
982 					/* The black depth of the  in rbtree_remove_fixup()
995 						    black;  in rbtree_remove_fixup()
1007 					 * black.  in rbtree_remove_fixup()
1013 						 * red, color it black  in rbtree_remove_fixup()
1017 						sibling->left->color = black;  in rbtree_remove_fixup()
1039 					 * parent black and to  in rbtree_remove_fixup()
1046 					curr_node->parent->color = black;  in rbtree_remove_fixup()
1054 	/* The root can always be colored black */  in rbtree_remove_fixup()
1055 	curr_node->color = black;  in rbtree_remove_fixup()
1058 /* Traverse a red-black tree */