[linux-block.git] / lib / 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 <linux/rbtree.h>
#include <linux/export.h>

#define	RB_RED		0
#define	RB_BLACK	1

#define rb_color(r)   ((r)->__rb_parent_color & 1)
#define rb_is_red(r)   (!rb_color(r))
#define rb_is_black(r) rb_color(r)
#define rb_set_red(r)  do { (r)->__rb_parent_color &= ~1; } while (0)
#define rb_set_black(r)  do { (r)->__rb_parent_color |= 1; } while (0)

static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
{
	rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;
}
static inline void rb_set_color(struct rb_node *rb, int color)
{
	rb->__rb_parent_color = (rb->__rb_parent_color & ~1) | color;
}

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) {
				__rb_rotate_left(parent, root);
				parent = node;
			}

			rb_set_black(parent);
			rb_set_red(gparent);
			__rb_rotate_right(gparent, root);
			break;
		} 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) {
				__rb_rotate_right(parent, root);
				parent = node;
			}

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

	rb_set_black(root->rb_node);
}
EXPORT_SYMBOL(rb_insert_color);

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))
				{
					rb_set_black(other->rb_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);
				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))
				{
					rb_set_black(other->rb_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);
				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;

		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;

		child = node->rb_right;
		parent = rb_parent(node);
		color = rb_color(node);

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

			node->rb_right = old->rb_right;
			rb_set_parent(old->rb_right, node);
		}

		node->__rb_parent_color = old->__rb_parent_color;
		node->rb_left = old->rb_left;
		rb_set_parent(old->rb_left, 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);
}
EXPORT_SYMBOL(rb_erase);

static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data)
{
	struct rb_node *parent;

up:
	func(node, data);
	parent = rb_parent(node);
	if (!parent)
		return;

	if (node == parent->rb_left && parent->rb_right)
		func(parent->rb_right, data);
	else if (parent->rb_left)
		func(parent->rb_left, data);

	node = parent;
	goto up;
}

/*
 * after inserting @node into the tree, update the tree to account for
 * both the new entry and any damage done by rebalance
 */
void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data)
{
	if (node->rb_left)
		node = node->rb_left;
	else if (node->rb_right)
		node = node->rb_right;

	rb_augment_path(node, func, data);
}
EXPORT_SYMBOL(rb_augment_insert);

/*
 * before removing the node, find the deepest node on the rebalance path
 * that will still be there after @node gets removed
 */
struct rb_node *rb_augment_erase_begin(struct rb_node *node)
{
	struct rb_node *deepest;

	if (!node->rb_right && !node->rb_left)
		deepest = rb_parent(node);
	else if (!node->rb_right)
		deepest = node->rb_left;
	else if (!node->rb_left)
		deepest = node->rb_right;
	else {
		deepest = rb_next(node);
		if (deepest->rb_right)
			deepest = deepest->rb_right;
		else if (rb_parent(deepest) != node)
			deepest = rb_parent(deepest);
	}

	return deepest;
}
EXPORT_SYMBOL(rb_augment_erase_begin);

/*
 * after removal, update the tree to account for the removed entry
 * and any rebalance damage.
 */
void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data)
{
	if (node)
		rb_augment_path(node, func, data);
}
EXPORT_SYMBOL(rb_augment_erase_end);

/*
 * This function returns the first node (in sort order) of the tree.
 */
struct rb_node *rb_first(const 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;
}
EXPORT_SYMBOL(rb_first);

struct rb_node *rb_last(const 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;
}
EXPORT_SYMBOL(rb_last);

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

	if (RB_EMPTY_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 (struct rb_node *)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;
}
EXPORT_SYMBOL(rb_next);

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

	if (RB_EMPTY_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 (struct rb_node *)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;
}
EXPORT_SYMBOL(rb_prev);

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;
}
EXPORT_SYMBOL(rb_replace_node);
Commit	Line	Data
1da177e4 LT	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 <linux/rbtree.h>
8bc3bcc9	24	#include <linux/export.h>
1da177e4	25
bf7ad8ee ML	26	#define RB_RED 0
	27	#define RB_BLACK 1
	28
	29	#define rb_color(r) ((r)->__rb_parent_color & 1)
	30	#define rb_is_red(r) (!rb_color(r))
	31	#define rb_is_black(r) rb_color(r)
	32	#define rb_set_red(r) do { (r)->__rb_parent_color &= ~1; } while (0)
	33	#define rb_set_black(r) do { (r)->__rb_parent_color \|= 1; } while (0)
	34
	35	static inline void rb_set_parent(struct rb_node rb, struct rb_node p)
	36	{
	37	rb->__rb_parent_color = rb_color(rb) \| (unsigned long)p;
	38	}
	39	static inline void rb_set_color(struct rb_node *rb, int color)
	40	{
	41	rb->__rb_parent_color = (rb->__rb_parent_color & ~1) \| color;
	42	}
	43
1da177e4 LT	44	static void __rb_rotate_left(struct rb_node node, struct rb_root root)
	45	{
	46	struct rb_node *right = node->rb_right;
55a98102	47	struct rb_node *parent = rb_parent(node);
1da177e4 LT	48
1da177e4 LT	49	if ((node->rb_right = right->rb_left))
55a98102	50	rb_set_parent(right->rb_left, node);
1da177e4 LT	51	right->rb_left = node;
1da177e4 LT	52
55a98102 DW	53	rb_set_parent(right, parent);
	54
	55	if (parent)
1da177e4	56	{
55a98102 DW	57	if (node == parent->rb_left)
55a98102 DW	58	parent->rb_left = right;
1da177e4	59	else
55a98102	60	parent->rb_right = right;
1da177e4 LT	61	}
	62	else
	63	root->rb_node = right;
55a98102	64	rb_set_parent(node, right);
1da177e4 LT	65	}
	66
	67	static void __rb_rotate_right(struct rb_node node, struct rb_root root)
	68	{
	69	struct rb_node *left = node->rb_left;
55a98102	70	struct rb_node *parent = rb_parent(node);
1da177e4 LT	71
1da177e4 LT	72	if ((node->rb_left = left->rb_right))
55a98102	73	rb_set_parent(left->rb_right, node);
1da177e4 LT	74	left->rb_right = node;
1da177e4 LT	75
55a98102 DW	76	rb_set_parent(left, parent);
	77
	78	if (parent)
1da177e4	79	{
55a98102 DW	80	if (node == parent->rb_right)
55a98102 DW	81	parent->rb_right = left;
1da177e4	82	else
55a98102	83	parent->rb_left = left;
1da177e4 LT	84	}
	85	else
	86	root->rb_node = left;
55a98102	87	rb_set_parent(node, left);
1da177e4 LT	88	}
	89
	90	void rb_insert_color(struct rb_node node, struct rb_root root)
	91	{
	92	struct rb_node parent, gparent;
	93
55a98102	94	while ((parent = rb_parent(node)) && rb_is_red(parent))
1da177e4	95	{
55a98102	96	gparent = rb_parent(parent);
1da177e4 LT	97
	98	if (parent == gparent->rb_left)
	99	{
	100	{
	101	register struct rb_node *uncle = gparent->rb_right;
55a98102	102	if (uncle && rb_is_red(uncle))
1da177e4	103	{
55a98102 DW	104	rb_set_black(uncle);
	105	rb_set_black(parent);
	106	rb_set_red(gparent);
1da177e4 LT	107	node = gparent;
	108	continue;
	109	}
	110	}
	111
1f052865	112	if (parent->rb_right == node) {
1da177e4	113	__rb_rotate_left(parent, root);
1da177e4	114	parent = node;
1da177e4 LT	115	}
1da177e4 LT	116
55a98102 DW	117	rb_set_black(parent);
55a98102 DW	118	rb_set_red(gparent);
1da177e4	119	__rb_rotate_right(gparent, root);
1f052865	120	break;
1da177e4 LT	121	} else {
	122	{
	123	register struct rb_node *uncle = gparent->rb_left;
55a98102	124	if (uncle && rb_is_red(uncle))
1da177e4	125	{
55a98102 DW	126	rb_set_black(uncle);
	127	rb_set_black(parent);
	128	rb_set_red(gparent);
1da177e4 LT	129	node = gparent;
	130	continue;
	131	}
	132	}
	133
1f052865	134	if (parent->rb_left == node) {
1da177e4	135	__rb_rotate_right(parent, root);
1da177e4	136	parent = node;
1da177e4 LT	137	}
1da177e4 LT	138
55a98102 DW	139	rb_set_black(parent);
55a98102 DW	140	rb_set_red(gparent);
1da177e4	141	__rb_rotate_left(gparent, root);
1f052865	142	break;
1da177e4 LT	143	}
	144	}
	145
55a98102	146	rb_set_black(root->rb_node);
1da177e4 LT	147	}
	148	EXPORT_SYMBOL(rb_insert_color);
	149
	150	static void __rb_erase_color(struct rb_node node, struct rb_node parent,
	151	struct rb_root *root)
	152	{
	153	struct rb_node *other;
	154
55a98102	155	while ((!node \|\| rb_is_black(node)) && node != root->rb_node)
1da177e4 LT	156	{
	157	if (parent->rb_left == node)
	158	{
	159	other = parent->rb_right;
55a98102	160	if (rb_is_red(other))
1da177e4	161	{
55a98102 DW	162	rb_set_black(other);
55a98102 DW	163	rb_set_red(parent);
1da177e4 LT	164	__rb_rotate_left(parent, root);
	165	other = parent->rb_right;
	166	}
55a98102 DW	167	if ((!other->rb_left \|\| rb_is_black(other->rb_left)) &&
55a98102 DW	168	(!other->rb_right \|\| rb_is_black(other->rb_right)))
1da177e4	169	{
55a98102	170	rb_set_red(other);
1da177e4	171	node = parent;
55a98102	172	parent = rb_parent(node);
1da177e4 LT	173	}
	174	else
	175	{
55a98102	176	if (!other->rb_right \|\| rb_is_black(other->rb_right))
1da177e4	177	{
55a63998	178	rb_set_black(other->rb_left);
55a98102	179	rb_set_red(other);
1da177e4 LT	180	__rb_rotate_right(other, root);
	181	other = parent->rb_right;
	182	}
2f3243ae	183	rb_set_color(other, rb_color(parent));
55a98102	184	rb_set_black(parent);
55a63998	185	rb_set_black(other->rb_right);
1da177e4 LT	186	__rb_rotate_left(parent, root);
	187	node = root->rb_node;
	188	break;
	189	}
	190	}
	191	else
	192	{
	193	other = parent->rb_left;
55a98102	194	if (rb_is_red(other))
1da177e4	195	{
55a98102 DW	196	rb_set_black(other);
55a98102 DW	197	rb_set_red(parent);
1da177e4 LT	198	__rb_rotate_right(parent, root);
	199	other = parent->rb_left;
	200	}
55a98102 DW	201	if ((!other->rb_left \|\| rb_is_black(other->rb_left)) &&
55a98102 DW	202	(!other->rb_right \|\| rb_is_black(other->rb_right)))
1da177e4	203	{
55a98102	204	rb_set_red(other);
1da177e4	205	node = parent;
55a98102	206	parent = rb_parent(node);
1da177e4 LT	207	}
	208	else
	209	{
55a98102	210	if (!other->rb_left \|\| rb_is_black(other->rb_left))
1da177e4	211	{
55a63998	212	rb_set_black(other->rb_right);
55a98102	213	rb_set_red(other);
1da177e4 LT	214	__rb_rotate_left(other, root);
	215	other = parent->rb_left;
	216	}
2f3243ae	217	rb_set_color(other, rb_color(parent));
55a98102	218	rb_set_black(parent);
55a63998	219	rb_set_black(other->rb_left);
1da177e4 LT	220	__rb_rotate_right(parent, root);
	221	node = root->rb_node;
	222	break;
	223	}
	224	}
	225	}
	226	if (node)
55a98102	227	rb_set_black(node);
1da177e4 LT	228	}
	229
	230	void rb_erase(struct rb_node node, struct rb_root root)
	231	{
	232	struct rb_node child, parent;
	233	int color;
	234
	235	if (!node->rb_left)
	236	child = node->rb_right;
	237	else if (!node->rb_right)
	238	child = node->rb_left;
	239	else
	240	{
	241	struct rb_node old = node, left;
	242
	243	node = node->rb_right;
	244	while ((left = node->rb_left) != NULL)
	245	node = left;
16c047ad WS	246
	247	if (rb_parent(old)) {
	248	if (rb_parent(old)->rb_left == old)
	249	rb_parent(old)->rb_left = node;
	250	else
	251	rb_parent(old)->rb_right = node;
	252	} else
	253	root->rb_node = node;
	254
1da177e4	255	child = node->rb_right;
55a98102	256	parent = rb_parent(node);
2f3243ae	257	color = rb_color(node);
1da177e4	258
55a98102	259	if (parent == old) {
1da177e4	260	parent = node;
4c601178 WS	261	} else {
	262	if (child)
	263	rb_set_parent(child, parent);
1975e593	264	parent->rb_left = child;
4b324126 WS	265
	266	node->rb_right = old->rb_right;
	267	rb_set_parent(old->rb_right, node);
4c601178	268	}
1975e593	269
bf7ad8ee	270	node->__rb_parent_color = old->__rb_parent_color;
1da177e4	271	node->rb_left = old->rb_left;
55a98102	272	rb_set_parent(old->rb_left, node);
4b324126	273
1da177e4 LT	274	goto color;
	275	}
	276
55a98102	277	parent = rb_parent(node);
2f3243ae	278	color = rb_color(node);
1da177e4 LT	279
1da177e4 LT	280	if (child)
55a98102	281	rb_set_parent(child, parent);
b945d6b2 PZ	282	if (parent)
b945d6b2 PZ	283	{
1da177e4 LT	284	if (parent->rb_left == node)
	285	parent->rb_left = child;
	286	else
	287	parent->rb_right = child;
17d9ddc7	288	}
b945d6b2 PZ	289	else
b945d6b2 PZ	290	root->rb_node = child;
1da177e4 LT	291
	292	color:
	293	if (color == RB_BLACK)
	294	__rb_erase_color(child, parent, root);
	295	}
	296	EXPORT_SYMBOL(rb_erase);
	297
b945d6b2 PZ	298	static void rb_augment_path(struct rb_node node, rb_augment_f func, void data)
	299	{
	300	struct rb_node *parent;
	301
	302	up:
	303	func(node, data);
	304	parent = rb_parent(node);
	305	if (!parent)
	306	return;
	307
	308	if (node == parent->rb_left && parent->rb_right)
	309	func(parent->rb_right, data);
	310	else if (parent->rb_left)
	311	func(parent->rb_left, data);
	312
	313	node = parent;
	314	goto up;
	315	}
	316
	317	/*
	318	* after inserting @node into the tree, update the tree to account for
	319	* both the new entry and any damage done by rebalance
	320	*/
	321	void rb_augment_insert(struct rb_node node, rb_augment_f func, void data)
	322	{
	323	if (node->rb_left)
	324	node = node->rb_left;
	325	else if (node->rb_right)
	326	node = node->rb_right;
	327
	328	rb_augment_path(node, func, data);
	329	}
0b6bb66d	330	EXPORT_SYMBOL(rb_augment_insert);
b945d6b2 PZ	331
	332	/*
	333	* before removing the node, find the deepest node on the rebalance path
	334	* that will still be there after @node gets removed
	335	*/
	336	struct rb_node rb_augment_erase_begin(struct rb_node node)
	337	{
	338	struct rb_node *deepest;
	339
	340	if (!node->rb_right && !node->rb_left)
	341	deepest = rb_parent(node);
	342	else if (!node->rb_right)
	343	deepest = node->rb_left;
	344	else if (!node->rb_left)
	345	deepest = node->rb_right;
	346	else {
	347	deepest = rb_next(node);
	348	if (deepest->rb_right)
	349	deepest = deepest->rb_right;
	350	else if (rb_parent(deepest) != node)
	351	deepest = rb_parent(deepest);
	352	}
	353
	354	return deepest;
	355	}
0b6bb66d	356	EXPORT_SYMBOL(rb_augment_erase_begin);
b945d6b2 PZ	357
	358	/*
	359	* after removal, update the tree to account for the removed entry
	360	* and any rebalance damage.
	361	*/
	362	void rb_augment_erase_end(struct rb_node node, rb_augment_f func, void data)
	363	{
	364	if (node)
	365	rb_augment_path(node, func, data);
	366	}
0b6bb66d	367	EXPORT_SYMBOL(rb_augment_erase_end);
b945d6b2	368
1da177e4 LT	369	/*
	370	* This function returns the first node (in sort order) of the tree.
	371	*/
f4b477c4	372	struct rb_node rb_first(const struct rb_root root)
1da177e4 LT	373	{
	374	struct rb_node *n;
	375
	376	n = root->rb_node;
	377	if (!n)
	378	return NULL;
	379	while (n->rb_left)
	380	n = n->rb_left;
	381	return n;
	382	}
	383	EXPORT_SYMBOL(rb_first);
	384
f4b477c4	385	struct rb_node rb_last(const struct rb_root root)
1da177e4 LT	386	{
	387	struct rb_node *n;
	388
	389	n = root->rb_node;
	390	if (!n)
	391	return NULL;
	392	while (n->rb_right)
	393	n = n->rb_right;
	394	return n;
	395	}
	396	EXPORT_SYMBOL(rb_last);
	397
f4b477c4	398	struct rb_node rb_next(const struct rb_node node)
1da177e4	399	{
55a98102 DW	400	struct rb_node *parent;
55a98102 DW	401
4c199a93	402	if (RB_EMPTY_NODE(node))
10fd48f2 JA	403	return NULL;
10fd48f2 JA	404
1da177e4 LT	405	/* If we have a right-hand child, go down and then left as far
	406	as we can. */
	407	if (node->rb_right) {
	408	node = node->rb_right;
	409	while (node->rb_left)
	410	node=node->rb_left;
f4b477c4	411	return (struct rb_node *)node;
1da177e4 LT	412	}
	413
	414	/* No right-hand children. Everything down and left is
	415	smaller than us, so any 'next' node must be in the general
	416	direction of our parent. Go up the tree; any time the
	417	ancestor is a right-hand child of its parent, keep going
	418	up. First time it's a left-hand child of its parent, said
	419	parent is our 'next' node. */
55a98102 DW	420	while ((parent = rb_parent(node)) && node == parent->rb_right)
55a98102 DW	421	node = parent;
1da177e4	422
55a98102	423	return parent;
1da177e4 LT	424	}
	425	EXPORT_SYMBOL(rb_next);
	426
f4b477c4	427	struct rb_node rb_prev(const struct rb_node node)
1da177e4	428	{
55a98102 DW	429	struct rb_node *parent;
55a98102 DW	430
4c199a93	431	if (RB_EMPTY_NODE(node))
10fd48f2 JA	432	return NULL;
10fd48f2 JA	433
1da177e4 LT	434	/* If we have a left-hand child, go down and then right as far
	435	as we can. */
	436	if (node->rb_left) {
	437	node = node->rb_left;
	438	while (node->rb_right)
	439	node=node->rb_right;
f4b477c4	440	return (struct rb_node *)node;
1da177e4 LT	441	}
	442
	443	/* No left-hand children. Go up till we find an ancestor which
	444	is a right-hand child of its parent */
55a98102 DW	445	while ((parent = rb_parent(node)) && node == parent->rb_left)
55a98102 DW	446	node = parent;
1da177e4	447
55a98102	448	return parent;
1da177e4 LT	449	}
	450	EXPORT_SYMBOL(rb_prev);
	451
	452	void rb_replace_node(struct rb_node victim, struct rb_node new,
	453	struct rb_root *root)
	454	{
55a98102	455	struct rb_node *parent = rb_parent(victim);
1da177e4 LT	456
	457	/* Set the surrounding nodes to point to the replacement */
	458	if (parent) {
	459	if (victim == parent->rb_left)
	460	parent->rb_left = new;
	461	else
	462	parent->rb_right = new;
	463	} else {
	464	root->rb_node = new;
	465	}
	466	if (victim->rb_left)
55a98102	467	rb_set_parent(victim->rb_left, new);
1da177e4	468	if (victim->rb_right)
55a98102	469	rb_set_parent(victim->rb_right, new);
1da177e4 LT	470
	471	/* Copy the pointers/colour from the victim to the replacement */
	472	new = victim;
	473	}
	474	EXPORT_SYMBOL(rb_replace_node);