2  * rbtree.c -- generic red black tree
51 /** Node colour red */
52 #define	RED	1  macro
74  * Creates a new red black tree, initializes and returns a pointer to it.
171 	while (node != rbtree->root && node->parent->color == RED) {  in ldns_rbtree_insert_fixup()
176 			/* If our uncle is red... */  in ldns_rbtree_insert_fixup()
177 			if (uncle->color == RED) {  in ldns_rbtree_insert_fixup()
182 				/* And the grandparent red... */  in ldns_rbtree_insert_fixup()
183 				node->parent->parent->color = RED;  in ldns_rbtree_insert_fixup()
195 				node->parent->parent->color = RED;  in ldns_rbtree_insert_fixup()
201 			/* If our uncle is red... */  in ldns_rbtree_insert_fixup()
202 			if (uncle->color == RED) {  in ldns_rbtree_insert_fixup()
207 				/* And the grandparent red... */  in ldns_rbtree_insert_fixup()
208 				node->parent->parent->color = RED;  in ldns_rbtree_insert_fixup()
220 				node->parent->parent->color = RED;  in ldns_rbtree_insert_fixup()
236  * Inserts a node into a red black tree.
269 	data->color = RED;  in ldns_rbtree_insert()
283 	/* Fix up the red-black properties... */  in ldns_rbtree_insert()
290  * Searches the red black tree, returns the data if key is found or NULL otherwise.
394 	if(to_delete->color == RED)  in ldns_rbtree_delete()
396 		/* if node is red then the child (black) can be swapped in */  in ldns_rbtree_delete()
398 	else if(child->color == RED)  in ldns_rbtree_delete()
400 		/* change child to BLACK, removing a RED node is no problem */  in ldns_rbtree_delete()
430 		if(sibling->color == RED)  in ldns_rbtree_delete_fixup()
432 			child_parent->color = RED;  in ldns_rbtree_delete_fixup()
448 				sibling->color = RED;  in ldns_rbtree_delete_fixup()
459 	if(child_parent->color == RED  in ldns_rbtree_delete_fixup()
464 		/* move red to sibling to rebalance */  in ldns_rbtree_delete_fixup()
466 			sibling->color = RED;  in ldns_rbtree_delete_fixup()
472 	   of sibling is red */  in ldns_rbtree_delete_fixup()
475 		&& sibling->right->color == RED  in ldns_rbtree_delete_fixup()
478 		sibling->color = RED;  in ldns_rbtree_delete_fixup()
487 		&& sibling->left->color == RED  in ldns_rbtree_delete_fixup()
490 		sibling->color = RED;  in ldns_rbtree_delete_fixup()
498 	/* now we have a black sibling with a red child. rotate and exchange colors. */  in ldns_rbtree_delete_fixup()
544  * Finds the first element in the red black tree