[fio.git] / rbtree.c

/*
  Red Black Trees
  (C) 1999  Andrea Arcangeli <andrea@suse.de>
  (C) 2002  David Woodhouse <dwmw2@infradead.org>
  
  This program is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation; either version 2 of the License, or
  (at your option) any later version.

  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

  linux/lib/rbtree.c
*/

#include "rbtree.h"

static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
{
	struct rb_node *right = node->rb_right;
	struct rb_node *parent = rb_parent(node);

	if ((node->rb_right = right->rb_left))
		rb_set_parent(right->rb_left, node);
	right->rb_left = node;

	rb_set_parent(right, parent);

	if (parent)
	{
		if (node == parent->rb_left)
			parent->rb_left = right;
		else
			parent->rb_right = right;
	}
	else
		root->rb_node = right;
	rb_set_parent(node, right);
}

static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
{
	struct rb_node *left = node->rb_left;
	struct rb_node *parent = rb_parent(node);

	if ((node->rb_left = left->rb_right))
		rb_set_parent(left->rb_right, node);
	left->rb_right = node;

	rb_set_parent(left, parent);

	if (parent)
	{
		if (node == parent->rb_right)
			parent->rb_right = left;
		else
			parent->rb_left = left;
	}
	else
		root->rb_node = left;
	rb_set_parent(node, left);
}

void rb_insert_color(struct rb_node *node, struct rb_root *root)
{
	struct rb_node *parent, *gparent;

	while ((parent = rb_parent(node)) && rb_is_red(parent))
	{
		gparent = rb_parent(parent);

		if (parent == gparent->rb_left)
		{
			{
				register struct rb_node *uncle = gparent->rb_right;
				if (uncle && rb_is_red(uncle))
				{
					rb_set_black(uncle);
					rb_set_black(parent);
					rb_set_red(gparent);
					node = gparent;
					continue;
				}
			}

			if (parent->rb_right == node)
			{
				register struct rb_node *tmp;
				__rb_rotate_left(parent, root);
				tmp = parent;
				parent = node;
				node = tmp;
			}

			rb_set_black(parent);
			rb_set_red(gparent);
			__rb_rotate_right(gparent, root);
		} else {
			{
				register struct rb_node *uncle = gparent->rb_left;
				if (uncle && rb_is_red(uncle))
				{
					rb_set_black(uncle);
					rb_set_black(parent);
					rb_set_red(gparent);
					node = gparent;
					continue;
				}
			}

			if (parent->rb_left == node)
			{
				register struct rb_node *tmp;
				__rb_rotate_right(parent, root);
				tmp = parent;
				parent = node;
				node = tmp;
			}

			rb_set_black(parent);
			rb_set_red(gparent);
			__rb_rotate_left(gparent, root);
		}
	}

	rb_set_black(root->rb_node);
}

static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
			     struct rb_root *root)
{
	struct rb_node *other;

	while ((!node || rb_is_black(node)) && node != root->rb_node)
	{
		if (parent->rb_left == node)
		{
			other = parent->rb_right;
			if (rb_is_red(other))
			{
				rb_set_black(other);
				rb_set_red(parent);
				__rb_rotate_left(parent, root);
				other = parent->rb_right;
			}
			if ((!other->rb_left || rb_is_black(other->rb_left)) &&
			    (!other->rb_right || rb_is_black(other->rb_right)))
			{
				rb_set_red(other);
				node = parent;
				parent = rb_parent(node);
			}
			else
			{
				if (!other->rb_right || rb_is_black(other->rb_right))
				{
					struct rb_node *o_left;
					if ((o_left = other->rb_left))
						rb_set_black(o_left);
					rb_set_red(other);
					__rb_rotate_right(other, root);
					other = parent->rb_right;
				}
				rb_set_color(other, rb_color(parent));
				rb_set_black(parent);
				if (other->rb_right)
					rb_set_black(other->rb_right);
				__rb_rotate_left(parent, root);
				node = root->rb_node;
				break;
			}
		}
		else
		{
			other = parent->rb_left;
			if (rb_is_red(other))
			{
				rb_set_black(other);
				rb_set_red(parent);
				__rb_rotate_right(parent, root);
				other = parent->rb_left;
			}
			if ((!other->rb_left || rb_is_black(other->rb_left)) &&
			    (!other->rb_right || rb_is_black(other->rb_right)))
			{
				rb_set_red(other);
				node = parent;
				parent = rb_parent(node);
			}
			else
			{
				if (!other->rb_left || rb_is_black(other->rb_left))
				{
					register struct rb_node *o_right;
					if ((o_right = other->rb_right))
						rb_set_black(o_right);
					rb_set_red(other);
					__rb_rotate_left(other, root);
					other = parent->rb_left;
				}
				rb_set_color(other, rb_color(parent));
				rb_set_black(parent);
				if (other->rb_left)
					rb_set_black(other->rb_left);
				__rb_rotate_right(parent, root);
				node = root->rb_node;
				break;
			}
		}
	}
	if (node)
		rb_set_black(node);
}

void rb_erase(struct rb_node *node, struct rb_root *root)
{
	struct rb_node *child, *parent;
	int color;

	if (!node->rb_left)
		child = node->rb_right;
	else if (!node->rb_right)
		child = node->rb_left;
	else
	{
		struct rb_node *old = node, *left;

		node = node->rb_right;
		while ((left = node->rb_left) != NULL)
			node = left;
		child = node->rb_right;
		parent = rb_parent(node);
		color = rb_color(node);

		if (child)
			rb_set_parent(child, parent);
		if (parent == old) {
			parent->rb_right = child;
			parent = node;
		} else
			parent->rb_left = child;

		node->rb_parent_color = old->rb_parent_color;
		node->rb_right = old->rb_right;
		node->rb_left = old->rb_left;

		if (rb_parent(old))
		{
			if (rb_parent(old)->rb_left == old)
				rb_parent(old)->rb_left = node;
			else
				rb_parent(old)->rb_right = node;
		} else
			root->rb_node = node;

		rb_set_parent(old->rb_left, node);
		if (old->rb_right)
			rb_set_parent(old->rb_right, node);
		goto color;
	}

	parent = rb_parent(node);
	color = rb_color(node);

	if (child)
		rb_set_parent(child, parent);
	if (parent)
	{
		if (parent->rb_left == node)
			parent->rb_left = child;
		else
			parent->rb_right = child;
	}
	else
		root->rb_node = child;

 color:
	if (color == RB_BLACK)
		__rb_erase_color(child, parent, root);
}

/*
 * This function returns the first node (in sort order) of the tree.
 */
struct rb_node *rb_first(struct rb_root *root)
{
	struct rb_node	*n;

	n = root->rb_node;
	if (!n)
		return NULL;
	while (n->rb_left)
		n = n->rb_left;
	return n;
}
Commit	Line	Data
4b87898e JA	1	/*
	2	Red Black Trees
	3	(C) 1999 Andrea Arcangeli <andrea@suse.de>
	4	(C) 2002 David Woodhouse <dwmw2@infradead.org>
	5
	6	This program is free software; you can redistribute it and/or modify
	7	it under the terms of the GNU General Public License as published by
	8	the Free Software Foundation; either version 2 of the License, or
	9	(at your option) any later version.
	10
	11	This program is distributed in the hope that it will be useful,
	12	but WITHOUT ANY WARRANTY; without even the implied warranty of
	13	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	14	GNU General Public License for more details.
	15
	16	You should have received a copy of the GNU General Public License
	17	along with this program; if not, write to the Free Software
	18	Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
	19
	20	linux/lib/rbtree.c
	21	*/
	22
	23	#include "rbtree.h"
	24
	25	static void __rb_rotate_left(struct rb_node node, struct rb_root root)
	26	{
	27	struct rb_node *right = node->rb_right;
44b5374f	28	struct rb_node *parent = rb_parent(node);
4b87898e JA	29
4b87898e JA	30	if ((node->rb_right = right->rb_left))
44b5374f	31	rb_set_parent(right->rb_left, node);
4b87898e JA	32	right->rb_left = node;
4b87898e JA	33
44b5374f JA	34	rb_set_parent(right, parent);
	35
	36	if (parent)
4b87898e	37	{
44b5374f JA	38	if (node == parent->rb_left)
44b5374f JA	39	parent->rb_left = right;
4b87898e	40	else
44b5374f	41	parent->rb_right = right;
4b87898e JA	42	}
	43	else
	44	root->rb_node = right;
44b5374f	45	rb_set_parent(node, right);
4b87898e JA	46	}
	47
	48	static void __rb_rotate_right(struct rb_node node, struct rb_root root)
	49	{
	50	struct rb_node *left = node->rb_left;
44b5374f	51	struct rb_node *parent = rb_parent(node);
4b87898e JA	52
4b87898e JA	53	if ((node->rb_left = left->rb_right))
44b5374f	54	rb_set_parent(left->rb_right, node);
4b87898e JA	55	left->rb_right = node;
4b87898e JA	56
44b5374f JA	57	rb_set_parent(left, parent);
	58
	59	if (parent)
4b87898e	60	{
44b5374f JA	61	if (node == parent->rb_right)
44b5374f JA	62	parent->rb_right = left;
4b87898e	63	else
44b5374f	64	parent->rb_left = left;
4b87898e JA	65	}
	66	else
	67	root->rb_node = left;
44b5374f	68	rb_set_parent(node, left);
4b87898e JA	69	}
	70
	71	void rb_insert_color(struct rb_node node, struct rb_root root)
	72	{
	73	struct rb_node parent, gparent;
	74
44b5374f	75	while ((parent = rb_parent(node)) && rb_is_red(parent))
4b87898e	76	{
44b5374f	77	gparent = rb_parent(parent);
4b87898e JA	78
	79	if (parent == gparent->rb_left)
	80	{
	81	{
	82	register struct rb_node *uncle = gparent->rb_right;
44b5374f	83	if (uncle && rb_is_red(uncle))
4b87898e	84	{
44b5374f JA	85	rb_set_black(uncle);
	86	rb_set_black(parent);
	87	rb_set_red(gparent);
4b87898e JA	88	node = gparent;
	89	continue;
	90	}
	91	}
	92
	93	if (parent->rb_right == node)
	94	{
	95	register struct rb_node *tmp;
	96	__rb_rotate_left(parent, root);
	97	tmp = parent;
	98	parent = node;
	99	node = tmp;
	100	}
	101
44b5374f JA	102	rb_set_black(parent);
44b5374f JA	103	rb_set_red(gparent);
4b87898e JA	104	__rb_rotate_right(gparent, root);
	105	} else {
	106	{
	107	register struct rb_node *uncle = gparent->rb_left;
44b5374f	108	if (uncle && rb_is_red(uncle))
4b87898e	109	{
44b5374f JA	110	rb_set_black(uncle);
	111	rb_set_black(parent);
	112	rb_set_red(gparent);
4b87898e JA	113	node = gparent;
	114	continue;
	115	}
	116	}
	117
	118	if (parent->rb_left == node)
	119	{
	120	register struct rb_node *tmp;
	121	__rb_rotate_right(parent, root);
	122	tmp = parent;
	123	parent = node;
	124	node = tmp;
	125	}
	126
44b5374f JA	127	rb_set_black(parent);
44b5374f JA	128	rb_set_red(gparent);
4b87898e JA	129	__rb_rotate_left(gparent, root);
	130	}
	131	}
	132
44b5374f	133	rb_set_black(root->rb_node);
4b87898e JA	134	}
	135
	136	static void __rb_erase_color(struct rb_node node, struct rb_node parent,
	137	struct rb_root *root)
	138	{
	139	struct rb_node *other;
	140
44b5374f	141	while ((!node \|\| rb_is_black(node)) && node != root->rb_node)
4b87898e JA	142	{
	143	if (parent->rb_left == node)
	144	{
	145	other = parent->rb_right;
44b5374f	146	if (rb_is_red(other))
4b87898e	147	{
44b5374f JA	148	rb_set_black(other);
44b5374f JA	149	rb_set_red(parent);
4b87898e JA	150	__rb_rotate_left(parent, root);
	151	other = parent->rb_right;
	152	}
44b5374f JA	153	if ((!other->rb_left \|\| rb_is_black(other->rb_left)) &&
44b5374f JA	154	(!other->rb_right \|\| rb_is_black(other->rb_right)))
4b87898e	155	{
44b5374f	156	rb_set_red(other);
4b87898e	157	node = parent;
44b5374f	158	parent = rb_parent(node);
4b87898e JA	159	}
	160	else
	161	{
44b5374f	162	if (!other->rb_right \|\| rb_is_black(other->rb_right))
4b87898e	163	{
44b5374f	164	struct rb_node *o_left;
4b87898e	165	if ((o_left = other->rb_left))
44b5374f JA	166	rb_set_black(o_left);
44b5374f JA	167	rb_set_red(other);
4b87898e JA	168	__rb_rotate_right(other, root);
	169	other = parent->rb_right;
	170	}
44b5374f JA	171	rb_set_color(other, rb_color(parent));
44b5374f JA	172	rb_set_black(parent);
4b87898e	173	if (other->rb_right)
44b5374f	174	rb_set_black(other->rb_right);
4b87898e JA	175	__rb_rotate_left(parent, root);
	176	node = root->rb_node;
	177	break;
	178	}
	179	}
	180	else
	181	{
	182	other = parent->rb_left;
44b5374f	183	if (rb_is_red(other))
4b87898e	184	{
44b5374f JA	185	rb_set_black(other);
44b5374f JA	186	rb_set_red(parent);
4b87898e JA	187	__rb_rotate_right(parent, root);
	188	other = parent->rb_left;
	189	}
44b5374f JA	190	if ((!other->rb_left \|\| rb_is_black(other->rb_left)) &&
44b5374f JA	191	(!other->rb_right \|\| rb_is_black(other->rb_right)))
4b87898e	192	{
44b5374f	193	rb_set_red(other);
4b87898e	194	node = parent;
44b5374f	195	parent = rb_parent(node);
4b87898e JA	196	}
	197	else
	198	{
44b5374f	199	if (!other->rb_left \|\| rb_is_black(other->rb_left))
4b87898e JA	200	{
	201	register struct rb_node *o_right;
	202	if ((o_right = other->rb_right))
44b5374f JA	203	rb_set_black(o_right);
44b5374f JA	204	rb_set_red(other);
4b87898e JA	205	__rb_rotate_left(other, root);
	206	other = parent->rb_left;
	207	}
44b5374f JA	208	rb_set_color(other, rb_color(parent));
44b5374f JA	209	rb_set_black(parent);
4b87898e	210	if (other->rb_left)
44b5374f	211	rb_set_black(other->rb_left);
4b87898e JA	212	__rb_rotate_right(parent, root);
	213	node = root->rb_node;
	214	break;
	215	}
	216	}
	217	}
	218	if (node)
44b5374f	219	rb_set_black(node);
4b87898e JA	220	}
	221
	222	void rb_erase(struct rb_node node, struct rb_root root)
	223	{
	224	struct rb_node child, parent;
	225	int color;
	226
	227	if (!node->rb_left)
	228	child = node->rb_right;
	229	else if (!node->rb_right)
	230	child = node->rb_left;
	231	else
	232	{
	233	struct rb_node old = node, left;
	234
	235	node = node->rb_right;
	236	while ((left = node->rb_left) != NULL)
	237	node = left;
	238	child = node->rb_right;
44b5374f JA	239	parent = rb_parent(node);
44b5374f JA	240	color = rb_color(node);
4b87898e JA	241
4b87898e JA	242	if (child)
44b5374f JA	243	rb_set_parent(child, parent);
	244	if (parent == old) {
	245	parent->rb_right = child;
4b87898e	246	parent = node;
44b5374f JA	247	} else
	248	parent->rb_left = child;
	249
	250	node->rb_parent_color = old->rb_parent_color;
4b87898e JA	251	node->rb_right = old->rb_right;
	252	node->rb_left = old->rb_left;
	253
44b5374f	254	if (rb_parent(old))
4b87898e	255	{
44b5374f JA	256	if (rb_parent(old)->rb_left == old)
44b5374f JA	257	rb_parent(old)->rb_left = node;
4b87898e	258	else
44b5374f	259	rb_parent(old)->rb_right = node;
4b87898e JA	260	} else
	261	root->rb_node = node;
	262
44b5374f	263	rb_set_parent(old->rb_left, node);
4b87898e	264	if (old->rb_right)
44b5374f	265	rb_set_parent(old->rb_right, node);
4b87898e JA	266	goto color;
	267	}
	268
44b5374f JA	269	parent = rb_parent(node);
44b5374f JA	270	color = rb_color(node);
4b87898e JA	271
4b87898e JA	272	if (child)
44b5374f	273	rb_set_parent(child, parent);
4b87898e JA	274	if (parent)
	275	{
	276	if (parent->rb_left == node)
	277	parent->rb_left = child;
	278	else
	279	parent->rb_right = child;
	280	}
	281	else
	282	root->rb_node = child;
	283
	284	color:
	285	if (color == RB_BLACK)
	286	__rb_erase_color(child, parent, root);
	287	}
	288
	289	/*
	290	* This function returns the first node (in sort order) of the tree.
	291	*/
	292	struct rb_node rb_first(struct rb_root root)
	293	{
	294	struct rb_node *n;
	295
	296	n = root->rb_node;
	297	if (!n)
	298	return NULL;
	299	while (n->rb_left)
	300	n = n->rb_left;
	301	return n;
	302	}