2  * rbtree.c -- generic red black tree
49 /** Node colour black */
50 #define	BLACK	0  macro
61 	BLACK		     /* Color.  */
74  * Creates a new red black tree, initializes and returns a pointer to it.
178 				/* Paint the parent and the uncle black... */  in ldns_rbtree_insert_fixup()
179 				node->parent->color = BLACK;  in ldns_rbtree_insert_fixup()
180 				uncle->color = BLACK;  in ldns_rbtree_insert_fixup()
187 			} else {				/* Our uncle is black... */  in ldns_rbtree_insert_fixup()
194 				node->parent->color = BLACK;  in ldns_rbtree_insert_fixup()
203 				/* Paint the parent and the uncle black... */  in ldns_rbtree_insert_fixup()
204 				node->parent->color = BLACK;  in ldns_rbtree_insert_fixup()
205 				uncle->color = BLACK;  in ldns_rbtree_insert_fixup()
212 			} else {				/* Our uncle is black... */  in ldns_rbtree_insert_fixup()
219 				node->parent->color = BLACK;  in ldns_rbtree_insert_fixup()
225 	rbtree->root->color = BLACK;  in ldns_rbtree_insert_fixup()
236  * Inserts a node into a red black tree.
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.
396 		/* if node is red then the child (black) can be swapped in */  in ldns_rbtree_delete()
400 		/* change child to BLACK, removing a RED node is no problem */  in ldns_rbtree_delete()
401 		if(child!=LDNS_RBTREE_NULL) child->color = BLACK;  in ldns_rbtree_delete()
409 	to_delete->color = BLACK;  in ldns_rbtree_delete()
418 	/* determine sibling to the node that is one-black short */  in ldns_rbtree_delete_fixup()
426 			/* removed parent==black from root, every path, so ok */  in ldns_rbtree_delete_fixup()
431 		{	/* rotate to get a black sibling */  in ldns_rbtree_delete_fixup()
433 			sibling->color = BLACK;  in ldns_rbtree_delete_fixup()
442 		if(child_parent->color == BLACK   in ldns_rbtree_delete_fixup()
443 			&& sibling->color == BLACK  in ldns_rbtree_delete_fixup()
444 			&& sibling->left->color == BLACK  in ldns_rbtree_delete_fixup()
445 			&& sibling->right->color == BLACK)  in ldns_rbtree_delete_fixup()
460 		&& sibling->color == BLACK  in ldns_rbtree_delete_fixup()
461 		&& sibling->left->color == BLACK  in ldns_rbtree_delete_fixup()
462 		&& sibling->right->color == BLACK)   in ldns_rbtree_delete_fixup()
467 		child_parent->color = BLACK;  in ldns_rbtree_delete_fixup()
474 		&& sibling->color == BLACK  in ldns_rbtree_delete_fixup()
476 		&& sibling->left->color == BLACK)  in ldns_rbtree_delete_fixup()
479 		sibling->right->color = BLACK;  in ldns_rbtree_delete_fixup()
486 		&& sibling->color == BLACK  in ldns_rbtree_delete_fixup()
488 		&& sibling->right->color == BLACK)  in ldns_rbtree_delete_fixup()
491 		sibling->left->color = BLACK;  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()
500 	child_parent->color = BLACK;  in ldns_rbtree_delete_fixup()
503 		sibling->left->color = BLACK;  in ldns_rbtree_delete_fixup()
508 		sibling->right->color = BLACK;  in ldns_rbtree_delete_fixup()
544  * Finds the first element in the red black tree