contrib/ldns/rbtree.c

64 /** rotate subtree left (to preserve redblack property) */
112  * Rotates the node to the left.
119 	node->right = right->left;
120 	if (right->left != LDNS_RBTREE_NULL)
121 		right->left->parent = node;
126 		if (node == node->parent->left) {
127 			node->parent->left = right;
134 	right->left = node;
145 	ldns_rbnode_t *left = node->left;
146 	node->left = left->right;
147 	if (left->right != LDNS_RBTREE_NULL)
148 		left->right->parent = node;
150 	left->parent = node->parent;
154 			node->parent->right = left;
156 			node->parent->left = left;
159 		rbtree->root = left;
161 	left->right = node;
162 	node->parent = left;
172 		/* If our parent is left child of our grandparent... */
173 		if (node->parent == node->parent->parent->left) {
193 				/* Now we're the left child, repaint and rotate... */
199 			uncle = node->parent->parent->left;
214 				if (node == node->parent->left) {
260 			node = node->left;
268 	data->left = data->right = LDNS_RBTREE_NULL;
275 			parent->left = data;
325 	if(parent->left == old) parent->left = new;
344 	if(to_delete->left != LDNS_RBTREE_NULL &&
347 		/* swap with smallest from right subtree (or largest from left) */
349 		while(smright->left != LDNS_RBTREE_NULL)
350 			smright = smright->left;
354 		 * readjust the pointers left,right,parent */
365 		change_child_ptr(smright->left, smright, to_delete);
366 		change_child_ptr(smright->left, smright, to_delete);
369 		change_child_ptr(to_delete->left, to_delete, smright);
381 		swap_np(&to_delete->left, &smright->left);
387 	if(to_delete->left != LDNS_RBTREE_NULL) child = to_delete->left;
407 	to_delete->left = LDNS_RBTREE_NULL;
419 	if(child_parent->right == child) sibling = child_parent->left;
438 			if(child_parent->right == child) sibling = child_parent->left;
444 			&& sibling->left->color == BLACK
453 			if(child_parent->right == child) sibling = child_parent->left;
461 		&& sibling->left->color == BLACK
476 		&& sibling->left->color == BLACK)
482 		if(child_parent->right == child) sibling = child_parent->left;
485 	else if(child_parent->left == child
487 		&& sibling->left->color == RED
491 		sibling->left->color = BLACK;
494 		if(child_parent->right == child) sibling = child_parent->left;
503 		sibling->left->color = BLACK;
533 			node = node->left;
553 		for (node = rbtree->root; node->left != LDNS_RBTREE_NULL; node = node->left);
579 		/* One right, then keep on going left... */
581 			node->left != LDNS_RBTREE_NULL;
582 			node = node->left);
599 	if (node->left != LDNS_RBTREE_NULL) {
600 		/* One left, then keep on going right... */
601 		for (node = node->left;
606 		while (parent != LDNS_RBTREE_NULL && node == parent->left) {
659 	traverse_post(func, arg, node->left);