[blktrace.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;
}

struct rb_node *rb_last(struct rb_root *root)
{
	struct rb_node	*n;

	n = root->rb_node;
	if (!n)
		return NULL;
	while (n->rb_right)
		n = n->rb_right;
	return n;
}

struct rb_node *rb_next(struct rb_node *node)
{
	struct rb_node *parent;

	if (rb_parent(node) == node)
		return NULL;

	/* If we have a right-hand child, go down and then left as far
	   as we can. */
	if (node->rb_right) {
		node = node->rb_right; 
		while (node->rb_left)
			node=node->rb_left;
		return node;
	}

	/* No right-hand children.  Everything down and left is
	   smaller than us, so any 'next' node must be in the general
	   direction of our parent. Go up the tree; any time the
	   ancestor is a right-hand child of its parent, keep going
	   up. First time it's a left-hand child of its parent, said
	   parent is our 'next' node. */
	while ((parent = rb_parent(node)) && node == parent->rb_right)
		node = parent;

	return parent;
}

struct rb_node *rb_prev(struct rb_node *node)
{
	struct rb_node *parent;

	if (rb_parent(node) == node)
		return NULL;

	/* If we have a left-hand child, go down and then right as far
	   as we can. */
	if (node->rb_left) {
		node = node->rb_left; 
		while (node->rb_right)
			node=node->rb_right;
		return node;
	}

	/* No left-hand children. Go up till we find an ancestor which
	   is a right-hand child of its parent */
	while ((parent = rb_parent(node)) && node == parent->rb_left)
		node = parent;

	return parent;
}

void rb_replace_node(struct rb_node *victim, struct rb_node *new,
		     struct rb_root *root)
{
	struct rb_node *parent = rb_parent(victim);

	/* Set the surrounding nodes to point to the replacement */
	if (parent) {
		if (victim == parent->rb_left)
			parent->rb_left = new;
		else
			parent->rb_right = new;
	} else {
		root->rb_node = new;
	}
	if (victim->rb_left)
		rb_set_parent(victim->rb_left, new);
	if (victim->rb_right)
		rb_set_parent(victim->rb_right, new);

	/* Copy the pointers/colour from the victim to the replacement */
	*new = *victim;
}
Commit	Line	Data
8fc0abbc 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;
0bc6b061	28	struct rb_node *parent = rb_parent(node);
8fc0abbc JA	29
8fc0abbc JA	30	if ((node->rb_right = right->rb_left))
0bc6b061	31	rb_set_parent(right->rb_left, node);
8fc0abbc JA	32	right->rb_left = node;
8fc0abbc JA	33
0bc6b061 JA	34	rb_set_parent(right, parent);
	35
	36	if (parent)
8fc0abbc	37	{
0bc6b061 JA	38	if (node == parent->rb_left)
0bc6b061 JA	39	parent->rb_left = right;
8fc0abbc	40	else
0bc6b061	41	parent->rb_right = right;
8fc0abbc JA	42	}
	43	else
	44	root->rb_node = right;
0bc6b061	45	rb_set_parent(node, right);
8fc0abbc 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;
0bc6b061	51	struct rb_node *parent = rb_parent(node);
8fc0abbc JA	52
8fc0abbc JA	53	if ((node->rb_left = left->rb_right))
0bc6b061	54	rb_set_parent(left->rb_right, node);
8fc0abbc JA	55	left->rb_right = node;
8fc0abbc JA	56
0bc6b061 JA	57	rb_set_parent(left, parent);
	58
	59	if (parent)
8fc0abbc	60	{
0bc6b061 JA	61	if (node == parent->rb_right)
0bc6b061 JA	62	parent->rb_right = left;
8fc0abbc	63	else
0bc6b061	64	parent->rb_left = left;
8fc0abbc JA	65	}
	66	else
	67	root->rb_node = left;
0bc6b061	68	rb_set_parent(node, left);
8fc0abbc JA	69	}
	70
	71	void rb_insert_color(struct rb_node node, struct rb_root root)
	72	{
	73	struct rb_node parent, gparent;
	74
0bc6b061	75	while ((parent = rb_parent(node)) && rb_is_red(parent))
8fc0abbc	76	{
0bc6b061	77	gparent = rb_parent(parent);
8fc0abbc JA	78
	79	if (parent == gparent->rb_left)
	80	{
	81	{
	82	register struct rb_node *uncle = gparent->rb_right;
0bc6b061	83	if (uncle && rb_is_red(uncle))
8fc0abbc	84	{
0bc6b061 JA	85	rb_set_black(uncle);
	86	rb_set_black(parent);
	87	rb_set_red(gparent);
8fc0abbc 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
0bc6b061 JA	102	rb_set_black(parent);
0bc6b061 JA	103	rb_set_red(gparent);
8fc0abbc JA	104	__rb_rotate_right(gparent, root);
	105	} else {
	106	{
	107	register struct rb_node *uncle = gparent->rb_left;
0bc6b061	108	if (uncle && rb_is_red(uncle))
8fc0abbc	109	{
0bc6b061 JA	110	rb_set_black(uncle);
	111	rb_set_black(parent);
	112	rb_set_red(gparent);
8fc0abbc 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
0bc6b061 JA	127	rb_set_black(parent);
0bc6b061 JA	128	rb_set_red(gparent);
8fc0abbc JA	129	__rb_rotate_left(gparent, root);
	130	}
	131	}
	132
0bc6b061	133	rb_set_black(root->rb_node);
8fc0abbc 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
0bc6b061	141	while ((!node \|\| rb_is_black(node)) && node != root->rb_node)
8fc0abbc JA	142	{
	143	if (parent->rb_left == node)
	144	{
	145	other = parent->rb_right;
0bc6b061	146	if (rb_is_red(other))
8fc0abbc	147	{
0bc6b061 JA	148	rb_set_black(other);
0bc6b061 JA	149	rb_set_red(parent);
8fc0abbc JA	150	__rb_rotate_left(parent, root);
	151	other = parent->rb_right;
	152	}
0bc6b061 JA	153	if ((!other->rb_left \|\| rb_is_black(other->rb_left)) &&
0bc6b061 JA	154	(!other->rb_right \|\| rb_is_black(other->rb_right)))
8fc0abbc	155	{
0bc6b061	156	rb_set_red(other);
8fc0abbc	157	node = parent;
0bc6b061	158	parent = rb_parent(node);
8fc0abbc JA	159	}
	160	else
	161	{
0bc6b061	162	if (!other->rb_right \|\| rb_is_black(other->rb_right))
8fc0abbc	163	{
0bc6b061	164	struct rb_node *o_left;
8fc0abbc	165	if ((o_left = other->rb_left))
0bc6b061 JA	166	rb_set_black(o_left);
0bc6b061 JA	167	rb_set_red(other);
8fc0abbc JA	168	__rb_rotate_right(other, root);
	169	other = parent->rb_right;
	170	}
0bc6b061 JA	171	rb_set_color(other, rb_color(parent));
0bc6b061 JA	172	rb_set_black(parent);
8fc0abbc	173	if (other->rb_right)
0bc6b061	174	rb_set_black(other->rb_right);
8fc0abbc JA	175	__rb_rotate_left(parent, root);
	176	node = root->rb_node;
	177	break;
	178	}
	179	}
	180	else
	181	{
	182	other = parent->rb_left;
0bc6b061	183	if (rb_is_red(other))
8fc0abbc	184	{
0bc6b061 JA	185	rb_set_black(other);
0bc6b061 JA	186	rb_set_red(parent);
8fc0abbc JA	187	__rb_rotate_right(parent, root);
	188	other = parent->rb_left;
	189	}
0bc6b061 JA	190	if ((!other->rb_left \|\| rb_is_black(other->rb_left)) &&
0bc6b061 JA	191	(!other->rb_right \|\| rb_is_black(other->rb_right)))
8fc0abbc	192	{
0bc6b061	193	rb_set_red(other);
8fc0abbc	194	node = parent;
0bc6b061	195	parent = rb_parent(node);
8fc0abbc JA	196	}
	197	else
	198	{
0bc6b061	199	if (!other->rb_left \|\| rb_is_black(other->rb_left))
8fc0abbc JA	200	{
	201	register struct rb_node *o_right;
	202	if ((o_right = other->rb_right))
0bc6b061 JA	203	rb_set_black(o_right);
0bc6b061 JA	204	rb_set_red(other);
8fc0abbc JA	205	__rb_rotate_left(other, root);
	206	other = parent->rb_left;
	207	}
0bc6b061 JA	208	rb_set_color(other, rb_color(parent));
0bc6b061 JA	209	rb_set_black(parent);
8fc0abbc	210	if (other->rb_left)
0bc6b061	211	rb_set_black(other->rb_left);
8fc0abbc JA	212	__rb_rotate_right(parent, root);
	213	node = root->rb_node;
	214	break;
	215	}
	216	}
	217	}
	218	if (node)
0bc6b061	219	rb_set_black(node);
8fc0abbc 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;
0bc6b061 JA	239	parent = rb_parent(node);
0bc6b061 JA	240	color = rb_color(node);
8fc0abbc JA	241
8fc0abbc JA	242	if (child)
0bc6b061 JA	243	rb_set_parent(child, parent);
	244	if (parent == old) {
	245	parent->rb_right = child;
8fc0abbc	246	parent = node;
0bc6b061 JA	247	} else
	248	parent->rb_left = child;
	249
	250	node->rb_parent_color = old->rb_parent_color;
8fc0abbc JA	251	node->rb_right = old->rb_right;
	252	node->rb_left = old->rb_left;
	253
0bc6b061	254	if (rb_parent(old))
8fc0abbc	255	{
0bc6b061 JA	256	if (rb_parent(old)->rb_left == old)
0bc6b061 JA	257	rb_parent(old)->rb_left = node;
8fc0abbc	258	else
0bc6b061	259	rb_parent(old)->rb_right = node;
8fc0abbc JA	260	} else
	261	root->rb_node = node;
	262
0bc6b061	263	rb_set_parent(old->rb_left, node);
8fc0abbc	264	if (old->rb_right)
0bc6b061	265	rb_set_parent(old->rb_right, node);
8fc0abbc JA	266	goto color;
	267	}
	268
0bc6b061 JA	269	parent = rb_parent(node);
0bc6b061 JA	270	color = rb_color(node);
8fc0abbc JA	271
8fc0abbc JA	272	if (child)
0bc6b061	273	rb_set_parent(child, parent);
8fc0abbc 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	}
	303
	304	struct rb_node rb_last(struct rb_root root)
	305	{
	306	struct rb_node *n;
	307
	308	n = root->rb_node;
	309	if (!n)
	310	return NULL;
	311	while (n->rb_right)
	312	n = n->rb_right;
	313	return n;
	314	}
	315
	316	struct rb_node rb_next(struct rb_node node)
	317	{
0bc6b061 JA	318	struct rb_node *parent;
	319
	320	if (rb_parent(node) == node)
	321	return NULL;
	322
8fc0abbc JA	323	/* If we have a right-hand child, go down and then left as far
	324	as we can. */
	325	if (node->rb_right) {
	326	node = node->rb_right;
	327	while (node->rb_left)
	328	node=node->rb_left;
	329	return node;
	330	}
	331
	332	/* No right-hand children. Everything down and left is
	333	smaller than us, so any 'next' node must be in the general
	334	direction of our parent. Go up the tree; any time the
	335	ancestor is a right-hand child of its parent, keep going
	336	up. First time it's a left-hand child of its parent, said
	337	parent is our 'next' node. */
0bc6b061 JA	338	while ((parent = rb_parent(node)) && node == parent->rb_right)
0bc6b061 JA	339	node = parent;
8fc0abbc	340
0bc6b061	341	return parent;
8fc0abbc JA	342	}
	343
	344	struct rb_node rb_prev(struct rb_node node)
	345	{
0bc6b061 JA	346	struct rb_node *parent;
	347
	348	if (rb_parent(node) == node)
	349	return NULL;
	350
8fc0abbc JA	351	/* If we have a left-hand child, go down and then right as far
	352	as we can. */
	353	if (node->rb_left) {
	354	node = node->rb_left;
	355	while (node->rb_right)
	356	node=node->rb_right;
	357	return node;
	358	}
	359
	360	/* No left-hand children. Go up till we find an ancestor which
	361	is a right-hand child of its parent */
0bc6b061 JA	362	while ((parent = rb_parent(node)) && node == parent->rb_left)
0bc6b061 JA	363	node = parent;
8fc0abbc	364
0bc6b061	365	return parent;
8fc0abbc JA	366	}
	367
	368	void rb_replace_node(struct rb_node victim, struct rb_node new,
	369	struct rb_root *root)
	370	{
0bc6b061	371	struct rb_node *parent = rb_parent(victim);
8fc0abbc JA	372
	373	/* Set the surrounding nodes to point to the replacement */
	374	if (parent) {
	375	if (victim == parent->rb_left)
	376	parent->rb_left = new;
	377	else
	378	parent->rb_right = new;
	379	} else {
	380	root->rb_node = new;
	381	}
	382	if (victim->rb_left)
0bc6b061	383	rb_set_parent(victim->rb_left, new);
8fc0abbc	384	if (victim->rb_right)
0bc6b061	385	rb_set_parent(victim->rb_right, new);
8fc0abbc JA	386
	387	/* Copy the pointers/colour from the victim to the replacement */
	388	new = victim;
	389	}