65 static void ldns_rbtree_rotate_left(ldns_rbtree_t *rbtree, ldns_rbnode_t *node);
67 static void ldns_rbtree_rotate_right(ldns_rbtree_t *rbtree, ldns_rbnode_t *node);
69 static void ldns_rbtree_insert_fixup(ldns_rbtree_t *rbtree, ldns_rbnode_t *node);
116 ldns_rbtree_rotate_left(ldns_rbtree_t *rbtree, ldns_rbnode_t *node)  in ldns_rbtree_rotate_left()  argument
118 	ldns_rbnode_t *right = node->right;  in ldns_rbtree_rotate_left()
119 	node->right = right->left;  in ldns_rbtree_rotate_left()
121 		right->left->parent = node;  in ldns_rbtree_rotate_left()
123 	right->parent = node->parent;  in ldns_rbtree_rotate_left()
125 	if (node->parent != LDNS_RBTREE_NULL) {  in ldns_rbtree_rotate_left()
126 		if (node == node->parent->left) {  in ldns_rbtree_rotate_left()
127 			node->parent->left = right;  in ldns_rbtree_rotate_left()
129 			node->parent->right = right;  in ldns_rbtree_rotate_left()
134 	right->left = node;  in ldns_rbtree_rotate_left()
135 	node->parent = right;  in ldns_rbtree_rotate_left()
143 ldns_rbtree_rotate_right(ldns_rbtree_t *rbtree, ldns_rbnode_t *node)  in ldns_rbtree_rotate_right()  argument
145 	ldns_rbnode_t *left = node->left;  in ldns_rbtree_rotate_right()
146 	node->left = left->right;  in ldns_rbtree_rotate_right()
148 		left->right->parent = node;  in ldns_rbtree_rotate_right()
150 	left->parent = node->parent;  in ldns_rbtree_rotate_right()
152 	if (node->parent != LDNS_RBTREE_NULL) {  in ldns_rbtree_rotate_right()
153 		if (node == node->parent->right) {  in ldns_rbtree_rotate_right()
154 			node->parent->right = left;  in ldns_rbtree_rotate_right()
156 			node->parent->left = left;  in ldns_rbtree_rotate_right()
161 	left->right = node;  in ldns_rbtree_rotate_right()
162 	node->parent = left;  in ldns_rbtree_rotate_right()
166 ldns_rbtree_insert_fixup(ldns_rbtree_t *rbtree, ldns_rbnode_t *node)  in ldns_rbtree_insert_fixup()  argument
171 	while (node != rbtree->root && node->parent->color == RED) {  in ldns_rbtree_insert_fixup()
173 		if (node->parent == node->parent->parent->left) {  in ldns_rbtree_insert_fixup()
174 			uncle = node->parent->parent->right;  in ldns_rbtree_insert_fixup()
179 				node->parent->color = BLACK;  in ldns_rbtree_insert_fixup()
183 				node->parent->parent->color = RED;  in ldns_rbtree_insert_fixup()
186 				node = node->parent->parent;  in ldns_rbtree_insert_fixup()
189 				if (node == node->parent->right) {  in ldns_rbtree_insert_fixup()
190 					node = node->parent;  in ldns_rbtree_insert_fixup()
191 					ldns_rbtree_rotate_left(rbtree, node);  in ldns_rbtree_insert_fixup()
194 				node->parent->color = BLACK;  in ldns_rbtree_insert_fixup()
195 				node->parent->parent->color = RED;  in ldns_rbtree_insert_fixup()
196 				ldns_rbtree_rotate_right(rbtree, node->parent->parent);  in ldns_rbtree_insert_fixup()
199 			uncle = node->parent->parent->left;  in ldns_rbtree_insert_fixup()
204 				node->parent->color = BLACK;  in ldns_rbtree_insert_fixup()
208 				node->parent->parent->color = RED;  in ldns_rbtree_insert_fixup()
211 				node = node->parent->parent;  in ldns_rbtree_insert_fixup()
214 				if (node == node->parent->left) {  in ldns_rbtree_insert_fixup()
215 					node = node->parent;  in ldns_rbtree_insert_fixup()
216 					ldns_rbtree_rotate_right(rbtree, node);  in ldns_rbtree_insert_fixup()
219 				node->parent->color = BLACK;  in ldns_rbtree_insert_fixup()
220 				node->parent->parent->color = RED;  in ldns_rbtree_insert_fixup()
221 				ldns_rbtree_rotate_left(rbtree, node->parent->parent);  in ldns_rbtree_insert_fixup()
248 	ldns_rbnode_t	*node = rbtree->root;  in ldns_rbtree_insert()  local
252 	while (node != LDNS_RBTREE_NULL) {  in ldns_rbtree_insert()
254 		if ((r = rbtree->cmp(data->key, node->key)) == 0) {  in ldns_rbtree_insert()
257 		parent = node;  in ldns_rbtree_insert()
260 			node = node->left;  in ldns_rbtree_insert()
262 			node = node->right;  in ldns_rbtree_insert()
296 	ldns_rbnode_t *node;  in ldns_rbtree_search()  local
298 	if (ldns_rbtree_find_less_equal(rbtree, key, &node)) {  in ldns_rbtree_search()
299 		return node;  in ldns_rbtree_search()
517 	ldns_rbnode_t *node;  in ldns_rbtree_find_less_equal()  local
520 	node = rbtree->root;  in ldns_rbtree_find_less_equal()
525 	while (node != LDNS_RBTREE_NULL) {  in ldns_rbtree_find_less_equal()
526 		r = rbtree->cmp(key, node->key);  in ldns_rbtree_find_less_equal()
529 			*result = node;  in ldns_rbtree_find_less_equal()
533 			node = node->left;  in ldns_rbtree_find_less_equal()
536 			*result = node;  in ldns_rbtree_find_less_equal()
537 			node = node->right;  in ldns_rbtree_find_less_equal()
550 	ldns_rbnode_t *node = rbtree->root;  in ldns_rbtree_first()  local
553 		for (node = rbtree->root; node->left != LDNS_RBTREE_NULL; node = node->left);  in ldns_rbtree_first()
555 	return node;  in ldns_rbtree_first()
561 	ldns_rbnode_t *node = rbtree->root;  in ldns_rbtree_last()  local
564 		for (node = rbtree->root; node->right != LDNS_RBTREE_NULL; node = node->right);  in ldns_rbtree_last()
566 	return node;  in ldns_rbtree_last()
574 ldns_rbtree_next(ldns_rbnode_t *node)  in ldns_rbtree_next()  argument
578 	if (node->right != LDNS_RBTREE_NULL) {  in ldns_rbtree_next()
580 		for (node = node->right;  in ldns_rbtree_next()
581 			node->left != LDNS_RBTREE_NULL;  in ldns_rbtree_next()
582 			node = node->left);  in ldns_rbtree_next()
584 		parent = node->parent;  in ldns_rbtree_next()
585 		while (parent != LDNS_RBTREE_NULL && node == parent->right) {  in ldns_rbtree_next()
586 			node = parent;  in ldns_rbtree_next()
589 		node = parent;  in ldns_rbtree_next()
591 	return node;  in ldns_rbtree_next()
595 ldns_rbtree_previous(ldns_rbnode_t *node)  in ldns_rbtree_previous()  argument
599 	if (node->left != LDNS_RBTREE_NULL) {  in ldns_rbtree_previous()
601 		for (node = node->left;  in ldns_rbtree_previous()
602 			node->right != LDNS_RBTREE_NULL;  in ldns_rbtree_previous()
603 			node = node->right);  in ldns_rbtree_previous()
605 		parent = node->parent;  in ldns_rbtree_previous()
606 		while (parent != LDNS_RBTREE_NULL && node == parent->left) {  in ldns_rbtree_previous()
607 			node = parent;  in ldns_rbtree_previous()
610 		node = parent;  in ldns_rbtree_previous()
612 	return node;  in ldns_rbtree_previous()
654 	ldns_rbnode_t* node)  in traverse_post()  argument
656 	if(!node || node == LDNS_RBTREE_NULL)  in traverse_post()
659 	traverse_post(func, arg, node->left);  in traverse_post()
660 	traverse_post(func, arg, node->right);  in traverse_post()
662 	(*func)(node, arg);  in traverse_post()