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