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