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 */
300 	/* Find a spot for the new object, insert the object as a red  in rbtree_insert()
305 	new_node = rbnode_construct(object, red);  in rbtree_insert()
377 	/* Insert the new object as a red leaf, being the successor of  in insert_successor_at()
380 	new_node = rbnode_construct(object, red);  in insert_successor_at()
437 	/* Insert the new object as a red leaf, being the predecessor  in insert_predecessor_at()
440 	new_node = rbnode_construct(object, red);  in insert_predecessor_at()
583 	/* Fix-up the red-black properties that may have been damaged:  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()
714 	 * leaf as the child of a red parent - so we have to fix the  in rbtree_insert_fixup()
721 	assert(node && node->color == red);  in rbtree_insert_fixup()
723 	while (curr_node != tree->root && curr_node->parent->color == red) {  in rbtree_insert_fixup()
725 		 * (the root is always black, so the red parent must  in rbtree_insert_fixup()
732 			/* If the red parent is a left child, the  in rbtree_insert_fixup()
737 			if (uncle && uncle->color == red) {  in rbtree_insert_fixup()
739 				/* If both parent and uncle are red,  in rbtree_insert_fixup()
741 				 * grandparent red. In case of a NULL  in rbtree_insert_fixup()
746 				grandparent->color = red;  in rbtree_insert_fixup()
763 				 * grandparent red  in rbtree_insert_fixup()
766 				grandparent->color = red;  in rbtree_insert_fixup()
774 			/* If the red parent is a right child, the  in rbtree_insert_fixup()
779 			if (uncle && uncle->color == red) {  in rbtree_insert_fixup()
780 				/* If both parent and uncle are red,  in rbtree_insert_fixup()
782 				 * grandparent red. In case of a NULL  in rbtree_insert_fixup()
787 				grandparent->color = red;  in rbtree_insert_fixup()
804 				 * grandparent red  in rbtree_insert_fixup()
807 				grandparent->color = red;  in rbtree_insert_fixup()
841 			if (sibling && sibling->color == red) {  in rbtree_remove_fixup()
842 				/* In case the sibling is red, color  in rbtree_remove_fixup()
844 				 * the parent red (the grandparent is  in rbtree_remove_fixup()
848 				curr_node->parent->color = red;  in rbtree_remove_fixup()
858 				 * children, color it red  in rbtree_remove_fixup()
860 				sibling->color = red;  in rbtree_remove_fixup()
861 				if (curr_node->parent->color == red) {  in rbtree_remove_fixup()
862 					/* If the parent is red, we  in rbtree_remove_fixup()
883 					if (curr_node->parent->color == red) {  in rbtree_remove_fixup()
895 					 * is red.  It is therfore  in rbtree_remove_fixup()
900 					    && sibling->right->color == red) {  in rbtree_remove_fixup()
903 						 * red, color it black  in rbtree_remove_fixup()
914 						 * red, rotate around  in rbtree_remove_fixup()
951 			if (sibling && sibling->color == red) {  in rbtree_remove_fixup()
952 				/* In case the sibling is red, color  in rbtree_remove_fixup()
954 				 * the parent red (the grandparent is  in rbtree_remove_fixup()
958 				curr_node->parent->color = red;  in rbtree_remove_fixup()
968 				/* If the sibling has two black children, color it red */  in rbtree_remove_fixup()
969 				sibling->color = red;  in rbtree_remove_fixup()
970 				if (curr_node->parent->color == red) {  in rbtree_remove_fixup()
971 					/* If the parent is red, we  in rbtree_remove_fixup()
993 					if (curr_node->parent->color == red) {  in rbtree_remove_fixup()
1005 					 * red.  It is therfore obvious  in rbtree_remove_fixup()
1010 					    && sibling->left->color == red) {  in rbtree_remove_fixup()
1013 						 * red, color it black  in rbtree_remove_fixup()
1024 						 * red, rotate around  in rbtree_remove_fixup()
1058 /* Traverse a red-black tree */