unbound/util/rbtree.c

405 	rbnode_t* sibling;
408 	/* determine sibling to the node that is one-black short */
409 	if(child_parent->right == child) sibling = child_parent->left;
410 	else sibling = child_parent->right;
420 		if(sibling->color == RED)
421 		{	/* rotate to get a black sibling */
423 			sibling->color = BLACK;
427 			/* new sibling after rotation */
428 			if(child_parent->right == child) sibling = child_parent->left;
429 			else sibling = child_parent->right;
433 			&& sibling->color == BLACK
434 			&& sibling->left->color == BLACK
435 			&& sibling->right->color == BLACK)
436 		{	/* fixup local with recolor of sibling */
437 			if(sibling != RBTREE_NULL)
438 				sibling->color = RED;
442 			/* prepare to go up, new sibling */
443 			if(child_parent->right == child) sibling = child_parent->left;
444 			else sibling = child_parent->right;
450 		&& sibling->color == BLACK
451 		&& sibling->left->color == BLACK
452 		&& sibling->right->color == BLACK)
454 		/* move red to sibling to rebalance */
455 		if(sibling != RBTREE_NULL)
456 			sibling->color = RED;
460 	log_assert(sibling != RBTREE_NULL);
462 	/* get a new sibling, by rotating at sibling. See which child
463 	   of sibling is red */
465 		&& sibling->color == BLACK
466 		&& sibling->right->color == RED
467 		&& sibling->left->color == BLACK)
469 		sibling->color = RED;
470 		sibling->right->color = BLACK;
471 		rbtree_rotate_left(rbtree, sibling);
472 		/* new sibling after rotation */
473 		if(child_parent->right == child) sibling = child_parent->left;
474 		else sibling = child_parent->right;
477 		&& sibling->color == BLACK
478 		&& sibling->left->color == RED
479 		&& sibling->right->color == BLACK)
481 		sibling->color = RED;
482 		sibling->left->color = BLACK;
483 		rbtree_rotate_right(rbtree, sibling);
484 		/* new sibling after rotation */
485 		if(child_parent->right == child) sibling = child_parent->left;
486 		else sibling = child_parent->right;
489 	/* now we have a black sibling with a red child. rotate and exchange colors. */
490 	sibling->color = child_parent->color;
494 		log_assert(sibling->left->color == RED);
495 		sibling->left->color = BLACK;
500 		log_assert(sibling->right->color == RED);
501 		sibling->right->color = BLACK;