unbound/util/rbtree.c

63 /** rotate subtree right (to preserve redblack property) */
109 	rbnode_t *right = node->right;
110 	node->right = right->left;
111 	if (right->left != RBTREE_NULL)
112 		right->left->parent = node;
114 	right->parent = node->parent;
118 			node->parent->left = right;
120 			node->parent->right = right;
123 		rbtree->root = right;
125 	right->left = node;
126 	node->parent = right;
130  * Rotates the node to the right.
137 	node->left = left->right;
138 	if (left->right != RBTREE_NULL)
139 		left->right->parent = node;
144 		if (node == node->parent->right) {
145 			node->parent->right = left;
152 	left->right = node;
165 			uncle = node->parent->parent->right;
179 				/* Are we the right child? */
180 				if (node == node->parent->right) {
204 				/* Are we the right child? */
209 				/* Now we're the right child, repaint and rotate... */
248 			node = node->right;
254 	data->left = data->right = RBTREE_NULL;
263 			parent->right = data;
312 	log_assert(parent->left == old || parent->right == old
313 		|| parent->left == new || parent->right == new);
315 	if(parent->right == old) parent->right = new;
334 	if(to_delete->left != RBTREE_NULL && to_delete->right != RBTREE_NULL)
336 		/* swap with smallest from right subtree (or largest from left) */
337 		rbnode_t *smright = to_delete->right;
343 		 * readjust the pointers left,right,parent */
350 		if(to_delete->right != smright)
356 		change_child_ptr(smright->right, smright, to_delete);
357 		change_child_ptr(smright->right, smright, to_delete);
359 		if(to_delete->right != smright)
360 			change_child_ptr(to_delete->right, to_delete, smright);
361 		if(to_delete->right == smright)
364 			to_delete->right = to_delete;
371 		swap_np(&to_delete->right, &smright->right);
375 	log_assert(to_delete->left == RBTREE_NULL || to_delete->right == RBTREE_NULL);
378 	else child = to_delete->right;
398 	to_delete->right = RBTREE_NULL;
409 	if(child_parent->right == child) sibling = child_parent->left;
410 	else sibling = child_parent->right;
424 			if(child_parent->right == child)
428 			if(child_parent->right == child) sibling = child_parent->left;
429 			else sibling = child_parent->right;
435 			&& sibling->right->color == BLACK)
443 			if(child_parent->right == child) sibling = child_parent->left;
444 			else sibling = child_parent->right;
452 		&& sibling->right->color == BLACK)
464 	if(child_parent->right == child
466 		&& sibling->right->color == RED
470 		sibling->right->color = BLACK;
473 		if(child_parent->right == child) sibling = child_parent->left;
474 		else sibling = child_parent->right;
479 		&& sibling->right->color == BLACK)
485 		if(child_parent->right == child) sibling = child_parent->left;
486 		else sibling = child_parent->right;
492 	if(child_parent->right == child)
500 		log_assert(sibling->right->color == RED);
501 		sibling->right->color = BLACK;
533 			node = node->right;
557 	for (node = rbtree->root; node->right != RBTREE_NULL; node = node->right);
570 	if (node->right != RBTREE_NULL) {
571 		/* One right, then keep on going left... */
572 		for (node = node->right; node->left != RBTREE_NULL; node = node->left);
575 		while (parent != RBTREE_NULL && node == parent->right) {
590 		/* One left, then keep on going right... */
591 		for (node = node->left; node->right != RBTREE_NULL; node = node->right);
611 	traverse_post(func, arg, node->right);