unbound/util/rbtree.c

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;
127 	node->parent = 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;
154 	node->parent = left;
163 	while (node != rbtree->root && node->parent->color == RED) {
164 		/* If our parent is left child of our grandparent... */
165 		if (node->parent == node->parent->parent->left) {
166 			uncle = node->parent->parent->right;
170 				/* Paint the parent and the uncle black... */
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;
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;
195 				/* Paint the parent and the uncle black... */
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;
211 				node->parent->color = BLACK;
212 				node->parent->parent->color = RED;
213 				rbtree_rotate_left(rbtree, node->parent->parent);
235 	rbnode_type	*parent = RBTREE_NULL;
238 	/* Lets find the new parent... */
244 		parent = node;
254 	data->parent = parent;
260 	if (parent != RBTREE_NULL) {
262 			parent->left = data;
264 			parent->right = data;
304 /** Update parent pointers of child trees of 'parent' */
305 static void change_parent_ptr(rbtree_type* rbtree, rbnode_type* parent,
308 	if(parent == RBTREE_NULL)
314 	log_assert(parent->left == old || parent->right == old
315 		|| parent->left == new || parent->right == new);
316 	if(parent->left == old) parent->left = new;
317 	if(parent->right == old) parent->right = new;
319 /** Update parent pointer of a node 'child' */
324 	log_assert(child->parent == old || child->parent == new);
325 	if(child->parent == old) child->parent = new;
346 		 * readjust the pointers left,right,parent */
352 		change_parent_ptr(rbtree, to_delete->parent, to_delete, smright);
354 			change_parent_ptr(rbtree, smright->parent, smright, to_delete);
356 		/* swap parent pointers in children of smright/to_delete */
368 			smright->parent = smright;
372 		swap_np(&to_delete->parent, &smright->parent);
384 	change_parent_ptr(rbtree, to_delete->parent, to_delete, child);
385 	change_child_ptr(child, to_delete, to_delete->parent);
396 	else rbtree_delete_fixup(rbtree, child, to_delete->parent);
399 	to_delete->parent = RBTREE_NULL;
420 			/* removed parent==black from root, every path, so ok */
445 			child_parent = child_parent->parent;
573 	rbnode_type *parent;
579 		parent = node->parent;
580 		while (parent != RBTREE_NULL && node == parent->right) {
581 			node = parent;
582 			parent = parent->parent;
584 		node = parent;
592 	rbnode_type *parent;
598 		parent = node->parent;
599 		while (parent != RBTREE_NULL && node == parent->left) {
600 			node = parent;
601 			parent = parent->parent;
603 		node = parent;