rbtree.c

TCP/IP商品扫描器 0.1

#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);
}