2  * rbtree.c -- generic red black tree
49 /** Node colour red */
50 #define	RED	1  macro
72  * Creates a new red black tree, initializes and returns a pointer to it.
163 	while (node != rbtree->root && node->parent->color == RED) {  in rbtree_insert_fixup()
168 			/* If our uncle is red... */  in rbtree_insert_fixup()
169 			if (uncle->color == RED) {  in rbtree_insert_fixup()
174 				/* And the grandparent red... */  in rbtree_insert_fixup()
175 				node->parent->parent->color = RED;  in rbtree_insert_fixup()
187 				node->parent->parent->color = RED;  in rbtree_insert_fixup()
193 			/* If our uncle is red... */  in rbtree_insert_fixup()
194 			if (uncle->color == RED) {  in rbtree_insert_fixup()
199 				/* And the grandparent red... */  in rbtree_insert_fixup()
200 				node->parent->parent->color = RED;  in rbtree_insert_fixup()
212 				node->parent->parent->color = RED;  in rbtree_insert_fixup()
222  * Inserts a node into a red black tree.
256 	data->color = RED;  in rbtree_insert()
270 	/* Fix up the red-black properties... */  in rbtree_insert()
277  * Searches the red black tree, returns the data if key is found or NULL otherwise.
387 	if(to_delete->color == RED)  in rbtree_delete()
389 		/* if node is red then the child (black) can be swapped in */  in rbtree_delete()
391 	else if(child->color == RED)  in rbtree_delete()
393 		/* change child to BLACK, removing a RED node is no problem */  in rbtree_delete()
424 		if(sibling->color == RED)  in rbtree_delete_fixup()
426 			child_parent->color = RED;  in rbtree_delete_fixup()
442 				sibling->color = RED;  in rbtree_delete_fixup()
453 	if(child_parent->color == RED  in rbtree_delete_fixup()
458 		/* move red to sibling to rebalance */  in rbtree_delete_fixup()
460 			sibling->color = RED;  in rbtree_delete_fixup()
467 	   of sibling is red */  in rbtree_delete_fixup()
470 		&& sibling->right->color == RED  in rbtree_delete_fixup()
473 		sibling->color = RED;  in rbtree_delete_fixup()
482 		&& sibling->left->color == RED  in rbtree_delete_fixup()
485 		sibling->color = RED;  in rbtree_delete_fixup()
493 	/* now we have a black sibling with a red child. rotate and exchange colors. */  in rbtree_delete_fixup()
498 		log_assert(sibling->left->color == RED);  in rbtree_delete_fixup()
504 		log_assert(sibling->right->color == RED);  in rbtree_delete_fixup()
545  * Finds the first element in the red black tree