unbound/util/rbtree.c

52 /** the NULL node, global alloc */
62 static void rbtree_rotate_left(rbtree_type *rbtree, rbnode_type *node);
64 static void rbtree_rotate_right(rbtree_type *rbtree, rbnode_type *node);
65 /** Fixup node colours when insert happened */
66 static void rbtree_insert_fixup(rbtree_type *rbtree, rbnode_type *node);
67 /** Fixup node colours when delete happened */
104  * Rotates the node to the left.
108 rbtree_rotate_left(rbtree_type *rbtree, rbnode_type *node)
110 	rbnode_type *right = node->right;
111 	node->right = right->left;
113 		right->left->parent = node;
115 	right->parent = node->parent;
117 	if (node->parent != RBTREE_NULL) {
118 		if (node == node->parent->left) {
119 			node->parent->left = right;
121 			node->parent->right = right;
126 	right->left = node;
127 	node->parent = right;
131  * Rotates the node to the right.
135 rbtree_rotate_right(rbtree_type *rbtree, rbnode_type *node)
137 	rbnode_type *left = node->left;
138 	node->left = left->right;
140 		left->right->parent = node;
142 	left->parent = node->parent;
144 	if (node->parent != RBTREE_NULL) {
145 		if (node == node->parent->right) {
146 			node->parent->right = left;
148 			node->parent->left = left;
153 	left->right = node;
154 	node->parent = left;
158 rbtree_insert_fixup(rbtree_type *rbtree, rbnode_type *node)
163 	while (node != rbtree->root && node->parent->color == RED) {
165 		if (node->parent == node->parent->parent->left) {
166 			uncle = node->parent->parent->right;
171 				node->parent->color = BLACK;
175 				node->parent->parent->color = RED;
178 				node = node->parent->parent;
181 				if (node == node->parent->right) {
182 					node = node->parent;
183 					rbtree_rotate_left(rbtree, node);
186 				node->parent->color = BLACK;
187 				node->parent->parent->color = RED;
188 				rbtree_rotate_right(rbtree, node->parent->parent);
191 			uncle = node->parent->parent->left;
196 				node->parent->color = BLACK;
200 				node->parent->parent->color = RED;
203 				node = node->parent->parent;
206 				if (node == node->parent->left) {
207 					node = node->parent;
208 					rbtree_rotate_right(rbtree, node);
211 				node->parent->color = BLACK;
212 				node->parent->parent->color = RED;
213 				rbtree_rotate_left(rbtree, node->parent->parent);
222  * Inserts a node into a red black tree.
224  * Returns NULL on failure or the pointer to the newly added node
234 	rbnode_type	*node = rbtree->root;
239 	while (node != RBTREE_NULL) {
241 		if ((r = rbtree->cmp(data->key, node->key)) == 0) {
244 		parent = node;
247 			node = node->left;
249 			node = node->right;
253 	/* Initialize the new node */
283 	rbnode_type *node;
285 	if (rbtree_find_less_equal(rbtree, key, &node)) {
286 		return node;
292 /** helpers for delete: swap node colours */
298 /** helpers for delete: swap node pointers */
319 /** Update parent pointer of a node 'child' */
389 		/* if node is red then the child (black) can be swapped in */
393 		/* change child to BLACK, removing a RED node is no problem */
412 	/* determine sibling to the node that is one-black short */
515 	rbnode_type *node;
520 	node = rbtree->root;
526 	while (node != RBTREE_NULL) {
527 		r = rbtree->cmp(key, node->key);
530 			*result = node;
534 			node = node->left;
537 			*result = node;
538 			node = node->right;
551 	rbnode_type *node;
553 	for (node = rbtree->root; node->left != RBTREE_NULL; node = node->left);
554 	return node;
560 	rbnode_type *node;
562 	for (node = rbtree->root; node->right != RBTREE_NULL; node = node->right);
563 	return node;
567  * Returns the next node...
571 rbtree_next (rbnode_type *node)
575 	if (node->right != RBTREE_NULL) {
577 		for (node = node->right; node->left != RBTREE_NULL; node = node->left);
579 		parent = node->parent;
580 		while (parent != RBTREE_NULL && node == parent->right) {
581 			node = parent;
584 		node = parent;
586 	return node;
590 rbtree_previous(rbnode_type *node)
594 	if (node->left != RBTREE_NULL) {
596 		for (node = node->left; node->right != RBTREE_NULL; node = node->right);
598 		parent = node->parent;
599 		while (parent != RBTREE_NULL && node == parent->left) {
600 			node = parent;
603 		node = parent;
605 	return node;
610 traverse_post(void (*func)(rbnode_type*, void*), void* arg, rbnode_type* node)
612 	if(!node || node == RBTREE_NULL)
615 	traverse_post(func, arg, node->left);
616 	traverse_post(func, arg, node->right);
618 	(*func)(node, arg);