unbound/util/rbtree.c

61 /** rotate subtree left (to preserve redblack property) */
104  * Rotates the node to the left.
111 	node->right = right->left;
112 	if (right->left != RBTREE_NULL)
113 		right->left->parent = node;
118 		if (node == node->parent->left) {
119 			node->parent->left = right;
126 	right->left = node;
137 	rbnode_type *left = node->left;
138 	node->left = left->right;
139 	if (left->right != RBTREE_NULL)
140 		left->right->parent = node;
142 	left->parent = node->parent;
146 			node->parent->right = left;
148 			node->parent->left = left;
151 		rbtree->root = left;
153 	left->right = node;
154 	node->parent = left;
164 		/* If our parent is left child of our grandparent... */
165 		if (node->parent == node->parent->parent->left) {
185 				/* Now we're the left child, repaint and rotate... */
191 			uncle = node->parent->parent->left;
206 				if (node == node->parent->left) {
247 			node = node->left;
255 	data->left = data->right = RBTREE_NULL;
262 			parent->left = data;
314 	log_assert(parent->left == old || parent->right == old
315 		|| parent->left == new || parent->right == new);
316 	if(parent->left == old) parent->left = new;
337 	if(to_delete->left != RBTREE_NULL && to_delete->right != RBTREE_NULL)
339 		/* swap with smallest from right subtree (or largest from left) */
341 		while(smright->left != RBTREE_NULL)
342 			smright = smright->left;
346 		 * readjust the pointers left,right,parent */
357 		change_child_ptr(smright->left, smright, to_delete);
358 		change_child_ptr(smright->left, smright, to_delete);
361 		change_child_ptr(to_delete->left, to_delete, smright);
373 		swap_np(&to_delete->left, &smright->left);
378 	log_assert(to_delete->left == RBTREE_NULL || to_delete->right == RBTREE_NULL);
380 	if(to_delete->left != RBTREE_NULL) child = to_delete->left;
400 	to_delete->left = RBTREE_NULL;
413 	if(child_parent->right == child) sibling = child_parent->left;
432 			if(child_parent->right == child) sibling = child_parent->left;
438 			&& sibling->left->color == BLACK
447 			if(child_parent->right == child) sibling = child_parent->left;
455 		&& sibling->left->color == BLACK
471 		&& sibling->left->color == BLACK)
477 		if(child_parent->right == child) sibling = child_parent->left;
480 	else if(child_parent->left == child
482 		&& sibling->left->color == RED
486 		sibling->left->color = BLACK;
489 		if(child_parent->right == child) sibling = child_parent->left;
498 		log_assert(sibling->left->color == RED);
499 		sibling->left->color = BLACK;
534 			node = node->left;
553 	for (node = rbtree->root; node->left != RBTREE_NULL; node = node->left);
576 		/* One right, then keep on going left... */
577 		for (node = node->right; node->left != RBTREE_NULL; node = node->left);
594 	if (node->left != RBTREE_NULL) {
595 		/* One left, then keep on going right... */
596 		for (node = node->left; node->right != RBTREE_NULL; node = node->right);
599 		while (parent != RBTREE_NULL && node == parent->left) {
615 	traverse_post(func, arg, node->left);