#include "rbtree.h"static void __rb_rotate_left(struct rb_node *node, struct rb_root *root){	struct rb_node *right = node->right;	if ((node->right = right->left))		right->left->parent = node;	right->left = node;	if ((right->parent = node->parent))	{		if (node == node->parent->left)			node->parent->left = right;		else			node->parent->right = right;	}	else		root->node = right;	node->parent = right;}static void __rb_rotate_right(struct rb_node *node, struct rb_root *root){	struct rb_node *left = node->left;	if ((node->left = left->right))		left->right->parent = node;	left->right = node;	if ((left->parent = node->parent))	{		if (node == node->parent->right)			node->parent->right = left;		else			node->parent->left = left;	}	else		root->node = left;	node->parent = left;}void rb_insert_color(struct rb_node *node, struct rb_root *root){	struct rb_node *parent, *gparent;	while ((parent = node->parent) && parent->color == RB_RED)	{		gparent = parent->parent;		if (parent == gparent->left)		{			{				register struct rb_node *uncle = gparent->right;				if (uncle && uncle->color == RB_RED)				{					uncle->color = RB_BLACK;					parent->color = RB_BLACK;					gparent->color = RB_RED;					node = gparent;					continue;				}			}			if (parent->right == node)			{				register struct rb_node *tmp;				__rb_rotate_left(parent, root);				tmp = parent;				parent = node;				node = tmp;			}			parent->color = RB_BLACK;			gparent->color = RB_RED;			__rb_rotate_right(gparent, root);		} else {			{				register struct rb_node *uncle = gparent->left;				if (uncle && uncle->color == RB_RED)				{					uncle->color = RB_BLACK;					parent->color = RB_BLACK;					gparent->color = RB_RED;					node = gparent;					continue;				}			}			if (parent->left == node)			{				register struct rb_node *tmp;				__rb_rotate_right(parent, root);				tmp = parent;				parent = node;				node = tmp;			}			parent->color = RB_BLACK;			gparent->color = RB_RED;			__rb_rotate_left(gparent, root);		}	}	root->node->color = RB_BLACK;}static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,							 struct rb_root *root){	struct rb_node *other;	while ((!node || node->color == RB_BLACK) && node != root->node)	{		if (parent->left == node)		{			other = parent->right;			if (other->color == RB_RED)			{				other->color = RB_BLACK;				parent->color = RB_RED;				__rb_rotate_left(parent, root);				other = parent->right;			}			if ((!other->left || other->left->color == RB_BLACK) &&			    (!other->right || other->right->color == RB_BLACK))			{				other->color = RB_RED;				node = parent;				parent = node->parent;			}			else			{				if (!other->right || other->right->color == RB_BLACK)				{					register struct rb_node *o_left;					if ((o_left = other->left))						o_left->color = RB_BLACK;					other->color = RB_RED;					__rb_rotate_right(other, root);					other = parent->right;				}				other->color = parent->color;				parent->color = RB_BLACK;				if (other->right)					other->right->color = RB_BLACK;				__rb_rotate_left(parent, root);				node = root->node;				break;			}		}		else		{			other = parent->left;			if (other->color == RB_RED)			{				other->color = RB_BLACK;				parent->color = RB_RED;				__rb_rotate_right(parent, root);				other = parent->left;			}			if ((!other->left || other->left->color == RB_BLACK) &&				(!other->right || other->right->color == RB_BLACK))			{				other->color = RB_RED;				node = parent;				parent = node->parent;			}			else			{				if (!other->left || other->left->color == RB_BLACK)				{					register struct rb_node *o_right;					if ((o_right = other->right))						o_right->color = RB_BLACK;					other->color = RB_RED;					__rb_rotate_left(other, root);					other = parent->left;				}				other->color = parent->color;				parent->color = RB_BLACK;				if (other->left)					other->left->color = RB_BLACK;				__rb_rotate_right(parent, root);				node = root->node;				break;			}		}	}	if (node)		node->color = RB_BLACK;}void rb_erase(struct rb_node *node, struct rb_root *root){	struct rb_node *child, *parent;	int color;	if (!node->left)		child = node->right;	else if (!node->right)		child = node->left;	else	{		struct rb_node *old = node, *left;		node = node->right;		while ((left = node->left))			node = left;		child = node->right;		parent = node->parent;		color = node->color;		if (child)			child->parent = parent;		if (parent)		{			if (parent->left == node)				parent->left = child;			else				parent->right = child;		}		else			root->node = child;		if (node->parent == old)			parent = node;		node->parent = old->parent;		node->color = old->color;		node->right = old->right;		node->left = old->left;		if (old->parent)		{			if (old->parent->left == old)				old->parent->left = node;			else				old->parent->right = node;		} else			root->node = node;		old->left->parent = node;		if (old->right)			old->right->parent = node;		goto color;	}	parent = node->parent;	color = node->color;	if (child)		child->parent = parent;	if (parent)	{		if (parent->left == node)			parent->left = child;		else			parent->right = child;	}	else		root->node = child;color:	if (color == RB_BLACK)		__rb_erase_color(child, parent, root);}