unbound/util/rbtree.c

63 /** rotate subtree right (to preserve redblack property) */
110 	rbnode_type *right = node->right;
111 	node->right = right->left;
112 	if (right->left != RBTREE_NULL)
113 		right->left->parent = node;
115 	right->parent = node->parent;
119 			node->parent->left = right;
121 			node->parent->right = right;
124 		rbtree->root = right;
126 	right->left = node;
127 	node->parent = right;
131  * Rotates the node to the right.
138 	node->left = left->right;
139 	if (left->right != RBTREE_NULL)
140 		left->right->parent = node;
145 		if (node == node->parent->right) {
146 			node->parent->right = left;
153 	left->right = node;
166 			uncle = node->parent->parent->right;
180 				/* Are we the right child? */
181 				if (node == node->parent->right) {
205 				/* Are we the right child? */
210 				/* Now we're the right child, repaint and rotate... */
249 			node = node->right;
255 	data->left = data->right = RBTREE_NULL;
264 			parent->right = data;
314 	log_assert(parent->left == old || parent->right == old
315 		|| parent->left == new || parent->right == new);
317 	if(parent->right == old) parent->right = new;
337 	if(to_delete->left != RBTREE_NULL && to_delete->right != RBTREE_NULL)
339 		/* swap with smallest from right subtree (or largest from left) */
340 		rbnode_type *smright = to_delete->right;
346 		 * readjust the pointers left,right,parent */
353 		if(to_delete->right != smright)
359 		change_child_ptr(smright->right, smright, to_delete);
360 		change_child_ptr(smright->right, smright, to_delete);
362 		if(to_delete->right != smright)
363 			change_child_ptr(to_delete->right, to_delete, smright);
364 		if(to_delete->right == smright)
367 			to_delete->right = to_delete;
374 		swap_np(&to_delete->right, &smright->right);
378 	log_assert(to_delete->left == RBTREE_NULL || to_delete->right == RBTREE_NULL);
381 	else child = to_delete->right;
401 	to_delete->right = RBTREE_NULL;
413 	if(child_parent->right == child) sibling = child_parent->left;
414 	else sibling = child_parent->right;
428 			if(child_parent->right == child)
432 			if(child_parent->right == child) sibling = child_parent->left;
433 			else sibling = child_parent->right;
439 			&& sibling->right->color == BLACK)
447 			if(child_parent->right == child) sibling = child_parent->left;
448 			else sibling = child_parent->right;
456 		&& sibling->right->color == BLACK)
468 	if(child_parent->right == child
470 		&& sibling->right->color == RED
474 		sibling->right->color = BLACK;
477 		if(child_parent->right == child) sibling = child_parent->left;
478 		else sibling = child_parent->right;
483 		&& sibling->right->color == BLACK)
489 		if(child_parent->right == child) sibling = child_parent->left;
490 		else sibling = child_parent->right;
496 	if(child_parent->right == child)
504 		log_assert(sibling->right->color == RED);
505 		sibling->right->color = BLACK;
538 			node = node->right;
562 	for (node = rbtree->root; node->right != RBTREE_NULL; node = node->right);
575 	if (node->right != RBTREE_NULL) {
576 		/* One right, then keep on going left... */
577 		for (node = node->right; node->left != RBTREE_NULL; node = node->left);
580 		while (parent != RBTREE_NULL && node == parent->right) {
595 		/* One left, then keep on going right... */
596 		for (node = node->left; node->right != RBTREE_NULL; node = node->right);
616 	traverse_post(func, arg, node->right);