WebSVN – Kolibri OS – Diff – /drivers/ddk/linux/rbtree.c


/*
  Red Black Trees
  (C) 1999  Andrea Arcangeli 
  (C) 2002  David Woodhouse 
  (C) 2012  Michel Lespinasse 
 
  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 
#include 
 
/*
 * red-black trees properties:  http://en.wikipedia.org/wiki/Rbtree
 *
 *  1) A node is either red or black
 *  2) The root is black
 *  3) All leaves (NULL) are black
 *  4) Both children of every red node are black
 *  5) Every simple path from root to leaves contains the same number
 *     of black nodes.
 *
 *  4 and 5 give the O(log n) guarantee, since 4 implies you cannot have two
 *  consecutive red nodes in a path and every red node is therefore followed by
 *  a black. So if B is the number of black nodes on every simple path (as per
 *  5), then the longest possible path due to 4 is 2B.
 *
 *  We shall indicate color with case, where black nodes are uppercase and red
 *  nodes will be lowercase. Unknown color nodes shall be drawn as red within
 *  parentheses and have some accompanying text comment.
 */
 
/*
 * Notes on lockless lookups:
 *
 * All stores to the tree structure (rb_left and rb_right) must be done using
 * WRITE_ONCE(). And we must not inadvertently cause (temporary) loops in the
 * tree structure as seen in program order.
 *
 * These two requirements will allow lockless iteration of the tree -- not
 * correct iteration mind you, tree rotations are not atomic so a lookup might
 * miss entire subtrees.
 *
 * But they do guarantee that any such traversal will only see valid elements
 * and that it will indeed complete -- does not get stuck in a loop.
 *
 * It also guarantees that if the lookup returns an element it is the 'correct'
 * one. But not returning an element does _NOT_ mean it's not present.
 *
 * NOTE:
 *
 * Stores to __rb_parent_color are not important for simple lookups so those
 * are left undone as of now. Nor did I check for loops involving parent
 * pointers.
 */
 
static inline void rb_set_black(struct rb_node *rb)
{
	rb->__rb_parent_color |= RB_BLACK;
}
 
static inline struct rb_node *rb_red_parent(struct rb_node *red)
{
	return (struct rb_node *)red->__rb_parent_color;
}
 
/*
 * Helper function for rotations:
 * - old's parent and color get assigned to new
 * - old gets assigned new as a parent and 'color' as a color.
 */
static inline void
__rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,
			struct rb_root *root, int color)
{
	struct rb_node *parent = rb_parent(old);
	new->__rb_parent_color = old->__rb_parent_color;
	rb_set_parent_color(old, new, color);
	__rb_change_child(old, new, parent, root);
}
 
static __always_inline void
__rb_insert(struct rb_node *node, struct rb_root *root,
	    void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
	struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;
 
	while (true) {
		/*
		 * Loop invariant: node is red
		 *
		 * If there is a black parent, we are done.
		 * Otherwise, take some corrective action as we don't
		 * want a red root or two consecutive red nodes.
		 */
		if (!parent) {
			rb_set_parent_color(node, NULL, RB_BLACK);
			break;
		} else if (rb_is_black(parent))
			break;
 
		gparent = rb_red_parent(parent);
 
		tmp = gparent->rb_right;
		if (parent != tmp) {	/* parent == gparent->rb_left */
			if (tmp && rb_is_red(tmp)) {
				/*
				 * Case 1 - color flips
				 *
				 *       G            g
				 *      / \          / \
				 *     p   u  -->   P   U
				 *    /            /
				 *   n            n
				 *
				 * However, since g's parent might be red, and
				 * 4) does not allow this, we need to recurse
				 * at g.
				 */
				rb_set_parent_color(tmp, gparent, RB_BLACK);
				rb_set_parent_color(parent, gparent, RB_BLACK);
				node = gparent;
				parent = rb_parent(node);
				rb_set_parent_color(node, parent, RB_RED);
				continue;
			}
 
			tmp = parent->rb_right;
			if (node == tmp) {
				/*
				 * Case 2 - left rotate at parent
				 *
				 *      G             G
				 *     / \           / \
				 *    p   U  -->    n   U
				 *     \           /
				 *      n         p
				 *
				 * This still leaves us in violation of 4), the
				 * continuation into Case 3 will fix that.
				 */
				tmp = node->rb_left;
				WRITE_ONCE(parent->rb_right, tmp);
				WRITE_ONCE(node->rb_left, parent);
				if (tmp)
					rb_set_parent_color(tmp, parent,
							    RB_BLACK);
				rb_set_parent_color(parent, node, RB_RED);
				augment_rotate(parent, node);
				parent = node;
				tmp = node->rb_right;
			}
 
			/*
			 * Case 3 - right rotate at gparent
			 *
			 *        G           P
			 *       / \         / \
			 *      p   U  -->  n   g
			 *     /                 \
			 *    n                   U
			 */
			WRITE_ONCE(gparent->rb_left, tmp); /* == parent->rb_right */
			WRITE_ONCE(parent->rb_right, gparent);
			if (tmp)
				rb_set_parent_color(tmp, gparent, RB_BLACK);
			__rb_rotate_set_parents(gparent, parent, root, RB_RED);
			augment_rotate(gparent, parent);
			break;
		} else {
			tmp = gparent->rb_left;
			if (tmp && rb_is_red(tmp)) {
				/* Case 1 - color flips */
				rb_set_parent_color(tmp, gparent, RB_BLACK);
				rb_set_parent_color(parent, gparent, RB_BLACK);
				node = gparent;
				parent = rb_parent(node);
				rb_set_parent_color(node, parent, RB_RED);
				continue;
			}
 
			tmp = parent->rb_left;
			if (node == tmp) {
				/* Case 2 - right rotate at parent */
				tmp = node->rb_right;
				WRITE_ONCE(parent->rb_left, tmp);
				WRITE_ONCE(node->rb_right, parent);
				if (tmp)
					rb_set_parent_color(tmp, parent,
							    RB_BLACK);
				rb_set_parent_color(parent, node, RB_RED);
				augment_rotate(parent, node);
				parent = node;
				tmp = node->rb_left;
			}
 
			/* Case 3 - left rotate at gparent */
			WRITE_ONCE(gparent->rb_right, tmp); /* == parent->rb_left */
			WRITE_ONCE(parent->rb_left, gparent);
			if (tmp)
				rb_set_parent_color(tmp, gparent, RB_BLACK);
			__rb_rotate_set_parents(gparent, parent, root, RB_RED);
			augment_rotate(gparent, parent);
			break;
		}
	}
}
 
/*
 * Inline version for rb_erase() use - we want to be able to inline
 * and eliminate the dummy_rotate callback there
 */
static __always_inline void
____rb_erase_color(struct rb_node *parent, struct rb_root *root,
	void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
	struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;
 
	while (true) {
		/*
		 * Loop invariants:
		 * - node is black (or NULL on first iteration)
		 * - node is not the root (parent is not NULL)
		 * - All leaf paths going through parent and node have a
		 *   black node count that is 1 lower than other leaf paths.
		 */
		sibling = parent->rb_right;
		if (node != sibling) {	/* node == parent->rb_left */
			if (rb_is_red(sibling)) {
				/*
				 * Case 1 - left rotate at parent
				 *
				 *     P               S
				 *    / \             / \
				 *   N   s    -->    p   Sr
				 *      / \         / \
				 *     Sl  Sr      N   Sl
				 */
				tmp1 = sibling->rb_left;
				WRITE_ONCE(parent->rb_right, tmp1);
				WRITE_ONCE(sibling->rb_left, parent);
				rb_set_parent_color(tmp1, parent, RB_BLACK);
				__rb_rotate_set_parents(parent, sibling, root,
							RB_RED);
				augment_rotate(parent, sibling);
				sibling = tmp1;
			}
			tmp1 = sibling->rb_right;
			if (!tmp1 || rb_is_black(tmp1)) {
				tmp2 = sibling->rb_left;
				if (!tmp2 || rb_is_black(tmp2)) {
					/*
					 * Case 2 - sibling color flip
					 * (p could be either color here)
					 *
					 *    (p)           (p)
					 *    / \           / \
					 *   N   S    -->  N   s
					 *      / \           / \
					 *     Sl  Sr        Sl  Sr
					 *
					 * This leaves us violating 5) which
					 * can be fixed by flipping p to black
					 * if it was red, or by recursing at p.
					 * p is red when coming from Case 1.
					 */
					rb_set_parent_color(sibling, parent,
							    RB_RED);
					if (rb_is_red(parent))
						rb_set_black(parent);
					else {
						node = parent;
						parent = rb_parent(node);
						if (parent)
							continue;
					}
					break;
				}
				/*
				 * Case 3 - right rotate at sibling
				 * (p could be either color here)
				 *
				 *   (p)           (p)
				 *   / \           / \
				 *  N   S    -->  N   Sl
				 *     / \             \
				 *    sl  Sr            s
				 *                       \
				 *                        Sr
				 */
				tmp1 = tmp2->rb_right;
				WRITE_ONCE(sibling->rb_left, tmp1);
				WRITE_ONCE(tmp2->rb_right, sibling);
				WRITE_ONCE(parent->rb_right, tmp2);
				if (tmp1)
					rb_set_parent_color(tmp1, sibling,
							    RB_BLACK);
				augment_rotate(sibling, tmp2);
				tmp1 = sibling;
				sibling = tmp2;
			}
			/*
			 * Case 4 - left rotate at parent + color flips
			 * (p and sl could be either color here.
			 *  After rotation, p becomes black, s acquires
			 *  p's color, and sl keeps its color)
			 *
			 *      (p)             (s)
			 *      / \             / \
			 *     N   S     -->   P   Sr
			 *        / \         / \
			 *      (sl) sr      N  (sl)
			 */
			tmp2 = sibling->rb_left;
			WRITE_ONCE(parent->rb_right, tmp2);
			WRITE_ONCE(sibling->rb_left, parent);
			rb_set_parent_color(tmp1, sibling, RB_BLACK);
			if (tmp2)
				rb_set_parent(tmp2, parent);
			__rb_rotate_set_parents(parent, sibling, root,
						RB_BLACK);
			augment_rotate(parent, sibling);
			break;
		} else {
			sibling = parent->rb_left;
			if (rb_is_red(sibling)) {
				/* Case 1 - right rotate at parent */
				tmp1 = sibling->rb_right;
				WRITE_ONCE(parent->rb_left, tmp1);
				WRITE_ONCE(sibling->rb_right, parent);
				rb_set_parent_color(tmp1, parent, RB_BLACK);
				__rb_rotate_set_parents(parent, sibling, root,
							RB_RED);
				augment_rotate(parent, sibling);
				sibling = tmp1;
			}
			tmp1 = sibling->rb_left;
			if (!tmp1 || rb_is_black(tmp1)) {
				tmp2 = sibling->rb_right;
				if (!tmp2 || rb_is_black(tmp2)) {
					/* Case 2 - sibling color flip */
					rb_set_parent_color(sibling, parent,
							    RB_RED);
					if (rb_is_red(parent))
						rb_set_black(parent);
					else {
						node = parent;
						parent = rb_parent(node);
						if (parent)
							continue;
					}
					break;
				}
				/* Case 3 - right rotate at sibling */
				tmp1 = tmp2->rb_left;
				WRITE_ONCE(sibling->rb_right, tmp1);
				WRITE_ONCE(tmp2->rb_left, sibling);
				WRITE_ONCE(parent->rb_left, tmp2);
				if (tmp1)
					rb_set_parent_color(tmp1, sibling,
							    RB_BLACK);
				augment_rotate(sibling, tmp2);
				tmp1 = sibling;
				sibling = tmp2;
			}
			/* Case 4 - left rotate at parent + color flips */
			tmp2 = sibling->rb_right;
			WRITE_ONCE(parent->rb_left, tmp2);
			WRITE_ONCE(sibling->rb_right, parent);
			rb_set_parent_color(tmp1, sibling, RB_BLACK);
			if (tmp2)
				rb_set_parent(tmp2, parent);
			__rb_rotate_set_parents(parent, sibling, root,
						RB_BLACK);
			augment_rotate(parent, sibling);
			break;
		}
	}
}
 
/* Non-inline version for rb_erase_augmented() use */
void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
	void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
	____rb_erase_color(parent, root, augment_rotate);
}
EXPORT_SYMBOL(__rb_erase_color);
 
/*
 * Non-augmented rbtree manipulation functions.
 *
 * We use dummy augmented callbacks here, and have the compiler optimize them
 * out of the rb_insert_color() and rb_erase() function definitions.
 */
 
static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {}
static inline void dummy_copy(struct rb_node *old, struct rb_node *new) {}
static inline void dummy_rotate(struct rb_node *old, struct rb_node *new) {}
 
static const struct rb_augment_callbacks dummy_callbacks = {
	dummy_propagate, dummy_copy, dummy_rotate
};
 
void rb_insert_color(struct rb_node *node, struct rb_root *root)
{
	__rb_insert(node, root, dummy_rotate);
}
EXPORT_SYMBOL(rb_insert_color);
 
void rb_erase(struct rb_node *node, struct rb_root *root)
{
	struct rb_node *rebalance;
	rebalance = __rb_erase_augmented(node, root, &dummy_callbacks);
	if (rebalance)
		____rb_erase_color(rebalance, root, dummy_rotate);
}
EXPORT_SYMBOL(rb_erase);
 
/*
 * Augmented rbtree manipulation functions.
 *
 * This instantiates the same __always_inline functions as in the non-augmented
 * case, but this time with user-defined callbacks.
 */
 
void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
	void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
	__rb_insert(node, root, augment_rotate);
}
EXPORT_SYMBOL(__rb_insert_augmented);
 
/*
 * 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 */
	__rb_change_child(victim, new, parent, root);
	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);
 
static struct rb_node *rb_left_deepest_node(const struct rb_node *node)
{
	for (;;) {
		if (node->rb_left)
			node = node->rb_left;
		else if (node->rb_right)
			node = node->rb_right;
		else
			return (struct rb_node *)node;
	}
}
 
struct rb_node *rb_next_postorder(const struct rb_node *node)
{
	const struct rb_node *parent;
	if (!node)
		return NULL;
	parent = rb_parent(node);
 
	/* If we're sitting on node, we've already seen our children */
	if (parent && node == parent->rb_left && parent->rb_right) {
		/* If we are the parent's left node, go to the parent's right
		 * node then all the way down to the left */
		return rb_left_deepest_node(parent->rb_right);
	} else
		/* Otherwise we are the parent's right node, and the parent
		 * should be next */
		return (struct rb_node *)parent;
}
EXPORT_SYMBOL(rb_next_postorder);
 
struct rb_node *rb_first_postorder(const struct rb_root *root)
{
	if (!root->rb_node)
		return NULL;
 
	return rb_left_deepest_node(root->rb_node);
}
EXPORT_SYMBOL(rb_first_postorder);

Rev 5270	Rev 6934
1	/*	1	/*
2	Red Black Trees	2	Red Black Trees
3	(C) 1999 Andrea Arcangeli	3	(C) 1999 Andrea Arcangeli
4	(C) 2002 David Woodhouse	4	(C) 2002 David Woodhouse
5	(C) 2012 Michel Lespinasse	5	(C) 2012 Michel Lespinasse
6		6
7	This program is free software; you can redistribute it and/or modify	7	This program is free software; you can redistribute it and/or modify
8	it under the terms of the GNU General Public License as published by	8	it under the terms of the GNU General Public License as published by
9	the Free Software Foundation; either version 2 of the License, or	9	the Free Software Foundation; either version 2 of the License, or
10	(at your option) any later version.	10	(at your option) any later version.
11		11
12	This program is distributed in the hope that it will be useful,	12	This program is distributed in the hope that it will be useful,
13	but WITHOUT ANY WARRANTY; without even the implied warranty of	13	but WITHOUT ANY WARRANTY; without even the implied warranty of
14	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the	14	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15	GNU General Public License for more details.	15	GNU General Public License for more details.
16		16
17	You should have received a copy of the GNU General Public License	17	You should have received a copy of the GNU General Public License
18	along with this program; if not, write to the Free Software	18	along with this program; if not, write to the Free Software
19	Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA	19	Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20		20
21	linux/lib/rbtree.c	21	linux/lib/rbtree.c
22	*/	22	*/
23		23
24	#include	24	#include
25	#include	25	#include
26		26
27	/*	27	/*
28	* red-black trees properties: http://en.wikipedia.org/wiki/Rbtree	28	* red-black trees properties: http://en.wikipedia.org/wiki/Rbtree
29	*	29	*
30	* 1) A node is either red or black	30	* 1) A node is either red or black
31	* 2) The root is black	31	* 2) The root is black
32	* 3) All leaves (NULL) are black	32	* 3) All leaves (NULL) are black
33	* 4) Both children of every red node are black	33	* 4) Both children of every red node are black
34	* 5) Every simple path from root to leaves contains the same number	34	* 5) Every simple path from root to leaves contains the same number
35	* of black nodes.	35	* of black nodes.
36	*	36	*
37	* 4 and 5 give the O(log n) guarantee, since 4 implies you cannot have two	37	* 4 and 5 give the O(log n) guarantee, since 4 implies you cannot have two
38	* consecutive red nodes in a path and every red node is therefore followed by	38	* consecutive red nodes in a path and every red node is therefore followed by
39	* a black. So if B is the number of black nodes on every simple path (as per	39	* a black. So if B is the number of black nodes on every simple path (as per
40	* 5), then the longest possible path due to 4 is 2B.	40	* 5), then the longest possible path due to 4 is 2B.
41	*	41	*
42	* We shall indicate color with case, where black nodes are uppercase and red	42	* We shall indicate color with case, where black nodes are uppercase and red
43	* nodes will be lowercase. Unknown color nodes shall be drawn as red within	43	* nodes will be lowercase. Unknown color nodes shall be drawn as red within
44	* parentheses and have some accompanying text comment.	44	* parentheses and have some accompanying text comment.
45	*/	45	*/
-		46
-		47	/*
-		48	* Notes on lockless lookups:
-		49	*
-		50	* All stores to the tree structure (rb_left and rb_right) must be done using
-		51	* WRITE_ONCE(). And we must not inadvertently cause (temporary) loops in the
-		52	* tree structure as seen in program order.
-		53	*
-		54	* These two requirements will allow lockless iteration of the tree -- not
-		55	* correct iteration mind you, tree rotations are not atomic so a lookup might
-		56	* miss entire subtrees.
-		57	*
-		58	* But they do guarantee that any such traversal will only see valid elements
-		59	* and that it will indeed complete -- does not get stuck in a loop.
-		60	*
-		61	* It also guarantees that if the lookup returns an element it is the 'correct'
-		62	* one. But not returning an element does _NOT_ mean it's not present.
-		63	*
-		64	* NOTE:
-		65	*
-		66	* Stores to __rb_parent_color are not important for simple lookups so those
-		67	* are left undone as of now. Nor did I check for loops involving parent
-		68	* pointers.
-		69	*/
46		70
47	static inline void rb_set_black(struct rb_node *rb)	71	static inline void rb_set_black(struct rb_node *rb)
48	{	72	{
49	rb->__rb_parent_color \|= RB_BLACK;	73	rb->__rb_parent_color \|= RB_BLACK;
50	}	74	}
51		75
52	static inline struct rb_node rb_red_parent(struct rb_node red)	76	static inline struct rb_node rb_red_parent(struct rb_node red)
53	{	77	{
54	return (struct rb_node *)red->__rb_parent_color;	78	return (struct rb_node *)red->__rb_parent_color;
55	}	79	}
56		80
57	/*	81	/*
58	* Helper function for rotations:	82	* Helper function for rotations:
59	* - old's parent and color get assigned to new	83	* - old's parent and color get assigned to new
60	* - old gets assigned new as a parent and 'color' as a color.	84	* - old gets assigned new as a parent and 'color' as a color.
61	*/	85	*/
62	static inline void	86	static inline void
63	__rb_rotate_set_parents(struct rb_node old, struct rb_node new,	87	__rb_rotate_set_parents(struct rb_node old, struct rb_node new,
64	struct rb_root *root, int color)	88	struct rb_root *root, int color)
65	{	89	{
66	struct rb_node *parent = rb_parent(old);	90	struct rb_node *parent = rb_parent(old);
67	new->__rb_parent_color = old->__rb_parent_color;	91	new->__rb_parent_color = old->__rb_parent_color;
68	rb_set_parent_color(old, new, color);	92	rb_set_parent_color(old, new, color);
69	__rb_change_child(old, new, parent, root);	93	__rb_change_child(old, new, parent, root);
70	}	94	}
71		95
72	static __always_inline void	96	static __always_inline void
73	__rb_insert(struct rb_node node, struct rb_root root,	97	__rb_insert(struct rb_node node, struct rb_root root,
74	void (augment_rotate)(struct rb_node old, struct rb_node *new))	98	void (augment_rotate)(struct rb_node old, struct rb_node *new))
75	{	99	{
76	struct rb_node parent = rb_red_parent(node), gparent, *tmp;	100	struct rb_node parent = rb_red_parent(node), gparent, *tmp;
77		101
78	while (true) {	102	while (true) {
79	/*	103	/*
80	* Loop invariant: node is red	104	* Loop invariant: node is red
81	*	105	*
82	* If there is a black parent, we are done.	106	* If there is a black parent, we are done.
83	* Otherwise, take some corrective action as we don't	107	* Otherwise, take some corrective action as we don't
84	* want a red root or two consecutive red nodes.	108	* want a red root or two consecutive red nodes.
85	*/	109	*/
86	if (!parent) {	110	if (!parent) {
87	rb_set_parent_color(node, NULL, RB_BLACK);	111	rb_set_parent_color(node, NULL, RB_BLACK);
88	break;	112	break;
89	} else if (rb_is_black(parent))	113	} else if (rb_is_black(parent))
90	break;	114	break;
91		115
92	gparent = rb_red_parent(parent);	116	gparent = rb_red_parent(parent);
93		117
94	tmp = gparent->rb_right;	118	tmp = gparent->rb_right;
95	if (parent != tmp) { /* parent == gparent->rb_left */	119	if (parent != tmp) { /* parent == gparent->rb_left */
96	if (tmp && rb_is_red(tmp)) {	120	if (tmp && rb_is_red(tmp)) {
97	/*	121	/*
98	* Case 1 - color flips	122	* Case 1 - color flips
99	*	123	*
100	* G g	124	* G g
101	* / \ / \	125	* / \ / \
102	* p u --> P U	126	* p u --> P U
103	* / /	127	* / /
104	* n n	128	* n n
105	*	129	*
106	* However, since g's parent might be red, and	130	* However, since g's parent might be red, and
107	* 4) does not allow this, we need to recurse	131	* 4) does not allow this, we need to recurse
108	* at g.	132	* at g.
109	*/	133	*/
110	rb_set_parent_color(tmp, gparent, RB_BLACK);	134	rb_set_parent_color(tmp, gparent, RB_BLACK);
111	rb_set_parent_color(parent, gparent, RB_BLACK);	135	rb_set_parent_color(parent, gparent, RB_BLACK);
112	node = gparent;	136	node = gparent;
113	parent = rb_parent(node);	137	parent = rb_parent(node);
114	rb_set_parent_color(node, parent, RB_RED);	138	rb_set_parent_color(node, parent, RB_RED);
115	continue;	139	continue;
116	}	140	}
117		141
118	tmp = parent->rb_right;	142	tmp = parent->rb_right;
119	if (node == tmp) {	143	if (node == tmp) {
120	/*	144	/*
121	* Case 2 - left rotate at parent	145	* Case 2 - left rotate at parent
122	*	146	*
123	* G G	147	* G G
124	* / \ / \	148	* / \ / \
125	* p U --> n U	149	* p U --> n U
126	* \ /	150	* \ /
127	* n p	151	* n p
128	*	152	*
129	* This still leaves us in violation of 4), the	153	* This still leaves us in violation of 4), the
130	* continuation into Case 3 will fix that.	154	* continuation into Case 3 will fix that.
131	*/	155	*/
132	parent->rb_right = tmp = node->rb_left;	156	tmp = node->rb_left;
-		157	WRITE_ONCE(parent->rb_right, tmp);
133	node->rb_left = parent;	158	WRITE_ONCE(node->rb_left, parent);
134	if (tmp)	159	if (tmp)
135	rb_set_parent_color(tmp, parent,	160	rb_set_parent_color(tmp, parent,
136	RB_BLACK);	161	RB_BLACK);
137	rb_set_parent_color(parent, node, RB_RED);	162	rb_set_parent_color(parent, node, RB_RED);
138	augment_rotate(parent, node);	163	augment_rotate(parent, node);
139	parent = node;	164	parent = node;
140	tmp = node->rb_right;	165	tmp = node->rb_right;
141	}	166	}
142		167
143	/*	168	/*
144	* Case 3 - right rotate at gparent	169	* Case 3 - right rotate at gparent
145	*	170	*
146	* G P	171	* G P
147	* / \ / \	172	* / \ / \
148	* p U --> n g	173	* p U --> n g
149	* / \	174	* / \
150	* n U	175	* n U
151	*/	176	*/
152	gparent->rb_left = tmp; /* == parent->rb_right */	177	WRITE_ONCE(gparent->rb_left, tmp); /* == parent->rb_right */
153	parent->rb_right = gparent;	178	WRITE_ONCE(parent->rb_right, gparent);
154	if (tmp)	179	if (tmp)
155	rb_set_parent_color(tmp, gparent, RB_BLACK);	180	rb_set_parent_color(tmp, gparent, RB_BLACK);
156	__rb_rotate_set_parents(gparent, parent, root, RB_RED);	181	__rb_rotate_set_parents(gparent, parent, root, RB_RED);
157	augment_rotate(gparent, parent);	182	augment_rotate(gparent, parent);
158	break;	183	break;
159	} else {	184	} else {
160	tmp = gparent->rb_left;	185	tmp = gparent->rb_left;
161	if (tmp && rb_is_red(tmp)) {	186	if (tmp && rb_is_red(tmp)) {
162	/* Case 1 - color flips */	187	/* Case 1 - color flips */
163	rb_set_parent_color(tmp, gparent, RB_BLACK);	188	rb_set_parent_color(tmp, gparent, RB_BLACK);
164	rb_set_parent_color(parent, gparent, RB_BLACK);	189	rb_set_parent_color(parent, gparent, RB_BLACK);
165	node = gparent;	190	node = gparent;
166	parent = rb_parent(node);	191	parent = rb_parent(node);
167	rb_set_parent_color(node, parent, RB_RED);	192	rb_set_parent_color(node, parent, RB_RED);
168	continue;	193	continue;
169	}	194	}
170		195
171	tmp = parent->rb_left;	196	tmp = parent->rb_left;
172	if (node == tmp) {	197	if (node == tmp) {
173	/* Case 2 - right rotate at parent */	198	/* Case 2 - right rotate at parent */
174	parent->rb_left = tmp = node->rb_right;	199	tmp = node->rb_right;
-		200	WRITE_ONCE(parent->rb_left, tmp);
175	node->rb_right = parent;	201	WRITE_ONCE(node->rb_right, parent);
176	if (tmp)	202	if (tmp)
177	rb_set_parent_color(tmp, parent,	203	rb_set_parent_color(tmp, parent,
178	RB_BLACK);	204	RB_BLACK);
179	rb_set_parent_color(parent, node, RB_RED);	205	rb_set_parent_color(parent, node, RB_RED);
180	augment_rotate(parent, node);	206	augment_rotate(parent, node);
181	parent = node;	207	parent = node;
182	tmp = node->rb_left;	208	tmp = node->rb_left;
183	}	209	}
184		210
185	/* Case 3 - left rotate at gparent */	211	/* Case 3 - left rotate at gparent */
186	gparent->rb_right = tmp; /* == parent->rb_left */	212	WRITE_ONCE(gparent->rb_right, tmp); /* == parent->rb_left */
187	parent->rb_left = gparent;	213	WRITE_ONCE(parent->rb_left, gparent);
188	if (tmp)	214	if (tmp)
189	rb_set_parent_color(tmp, gparent, RB_BLACK);	215	rb_set_parent_color(tmp, gparent, RB_BLACK);
190	__rb_rotate_set_parents(gparent, parent, root, RB_RED);	216	__rb_rotate_set_parents(gparent, parent, root, RB_RED);
191	augment_rotate(gparent, parent);	217	augment_rotate(gparent, parent);
192	break;	218	break;
193	}	219	}
194	}	220	}
195	}	221	}
196		222
197	/*	223	/*
198	* Inline version for rb_erase() use - we want to be able to inline	224	* Inline version for rb_erase() use - we want to be able to inline
199	* and eliminate the dummy_rotate callback there	225	* and eliminate the dummy_rotate callback there
200	*/	226	*/
201	static __always_inline void	227	static __always_inline void
202	____rb_erase_color(struct rb_node parent, struct rb_root root,	228	____rb_erase_color(struct rb_node parent, struct rb_root root,
203	void (augment_rotate)(struct rb_node old, struct rb_node *new))	229	void (augment_rotate)(struct rb_node old, struct rb_node *new))
204	{	230	{
205	struct rb_node node = NULL, sibling, tmp1, tmp2;	231	struct rb_node node = NULL, sibling, tmp1, tmp2;
206		232
207	while (true) {	233	while (true) {
208	/*	234	/*
209	* Loop invariants:	235	* Loop invariants:
210	* - node is black (or NULL on first iteration)	236	* - node is black (or NULL on first iteration)
211	* - node is not the root (parent is not NULL)	237	* - node is not the root (parent is not NULL)
212	* - All leaf paths going through parent and node have a	238	* - All leaf paths going through parent and node have a
213	* black node count that is 1 lower than other leaf paths.	239	* black node count that is 1 lower than other leaf paths.
214	*/	240	*/
215	sibling = parent->rb_right;	241	sibling = parent->rb_right;
216	if (node != sibling) { /* node == parent->rb_left */	242	if (node != sibling) { /* node == parent->rb_left */
217	if (rb_is_red(sibling)) {	243	if (rb_is_red(sibling)) {
218	/*	244	/*
219	* Case 1 - left rotate at parent	245	* Case 1 - left rotate at parent
220	*	246	*
221	* P S	247	* P S
222	* / \ / \	248	* / \ / \
223	* N s --> p Sr	249	* N s --> p Sr
224	* / \ / \	250	* / \ / \
225	* Sl Sr N Sl	251	* Sl Sr N Sl
226	*/	252	*/
227	parent->rb_right = tmp1 = sibling->rb_left;	253	tmp1 = sibling->rb_left;
-		254	WRITE_ONCE(parent->rb_right, tmp1);
228	sibling->rb_left = parent;	255	WRITE_ONCE(sibling->rb_left, parent);
229	rb_set_parent_color(tmp1, parent, RB_BLACK);	256	rb_set_parent_color(tmp1, parent, RB_BLACK);
230	__rb_rotate_set_parents(parent, sibling, root,	257	__rb_rotate_set_parents(parent, sibling, root,
231	RB_RED);	258	RB_RED);
232	augment_rotate(parent, sibling);	259	augment_rotate(parent, sibling);
233	sibling = tmp1;	260	sibling = tmp1;
234	}	261	}
235	tmp1 = sibling->rb_right;	262	tmp1 = sibling->rb_right;
236	if (!tmp1 \|\| rb_is_black(tmp1)) {	263	if (!tmp1 \|\| rb_is_black(tmp1)) {
237	tmp2 = sibling->rb_left;	264	tmp2 = sibling->rb_left;
238	if (!tmp2 \|\| rb_is_black(tmp2)) {	265	if (!tmp2 \|\| rb_is_black(tmp2)) {
239	/*	266	/*
240	* Case 2 - sibling color flip	267	* Case 2 - sibling color flip
241	* (p could be either color here)	268	* (p could be either color here)
242	*	269	*
243	* (p) (p)	270	* (p) (p)
244	* / \ / \	271	* / \ / \
245	* N S --> N s	272	* N S --> N s
246	* / \ / \	273	* / \ / \
247	* Sl Sr Sl Sr	274	* Sl Sr Sl Sr
248	*	275	*
249	* This leaves us violating 5) which	276	* This leaves us violating 5) which
250	* can be fixed by flipping p to black	277	* can be fixed by flipping p to black
251	* if it was red, or by recursing at p.	278	* if it was red, or by recursing at p.
252	* p is red when coming from Case 1.	279	* p is red when coming from Case 1.
253	*/	280	*/
254	rb_set_parent_color(sibling, parent,	281	rb_set_parent_color(sibling, parent,
255	RB_RED);	282	RB_RED);
256	if (rb_is_red(parent))	283	if (rb_is_red(parent))
257	rb_set_black(parent);	284	rb_set_black(parent);
258	else {	285	else {
259	node = parent;	286	node = parent;
260	parent = rb_parent(node);	287	parent = rb_parent(node);
261	if (parent)	288	if (parent)
262	continue;	289	continue;
263	}	290	}
264	break;	291	break;
265	}	292	}
266	/*	293	/*
267	* Case 3 - right rotate at sibling	294	* Case 3 - right rotate at sibling
268	* (p could be either color here)	295	* (p could be either color here)
269	*	296	*
270	* (p) (p)	297	* (p) (p)
271	* / \ / \	298	* / \ / \
272	* N S --> N Sl	299	* N S --> N Sl
273	* / \ \	300	* / \ \
274	* sl Sr s	301	* sl Sr s
275	* \	302	* \
276	* Sr	303	* Sr
277	*/	304	*/
278	sibling->rb_left = tmp1 = tmp2->rb_right;	305	tmp1 = tmp2->rb_right;
-		306	WRITE_ONCE(sibling->rb_left, tmp1);
279	tmp2->rb_right = sibling;	307	WRITE_ONCE(tmp2->rb_right, sibling);
280	parent->rb_right = tmp2;	308	WRITE_ONCE(parent->rb_right, tmp2);
281	if (tmp1)	309	if (tmp1)
282	rb_set_parent_color(tmp1, sibling,	310	rb_set_parent_color(tmp1, sibling,
283	RB_BLACK);	311	RB_BLACK);
284	augment_rotate(sibling, tmp2);	312	augment_rotate(sibling, tmp2);
285	tmp1 = sibling;	313	tmp1 = sibling;
286	sibling = tmp2;	314	sibling = tmp2;
287	}	315	}
288	/*	316	/*
289	* Case 4 - left rotate at parent + color flips	317	* Case 4 - left rotate at parent + color flips
290	* (p and sl could be either color here.	318	* (p and sl could be either color here.
291	* After rotation, p becomes black, s acquires	319	* After rotation, p becomes black, s acquires
292	* p's color, and sl keeps its color)	320	* p's color, and sl keeps its color)
293	*	321	*
294	* (p) (s)	322	* (p) (s)
295	* / \ / \	323	* / \ / \
296	* N S --> P Sr	324	* N S --> P Sr
297	* / \ / \	325	* / \ / \
298	* (sl) sr N (sl)	326	* (sl) sr N (sl)
299	*/	327	*/
300	parent->rb_right = tmp2 = sibling->rb_left;	328	tmp2 = sibling->rb_left;
-		329	WRITE_ONCE(parent->rb_right, tmp2);
301	sibling->rb_left = parent;	330	WRITE_ONCE(sibling->rb_left, parent);
302	rb_set_parent_color(tmp1, sibling, RB_BLACK);	331	rb_set_parent_color(tmp1, sibling, RB_BLACK);
303	if (tmp2)	332	if (tmp2)
304	rb_set_parent(tmp2, parent);	333	rb_set_parent(tmp2, parent);
305	__rb_rotate_set_parents(parent, sibling, root,	334	__rb_rotate_set_parents(parent, sibling, root,
306	RB_BLACK);	335	RB_BLACK);
307	augment_rotate(parent, sibling);	336	augment_rotate(parent, sibling);
308	break;	337	break;
309	} else {	338	} else {
310	sibling = parent->rb_left;	339	sibling = parent->rb_left;
311	if (rb_is_red(sibling)) {	340	if (rb_is_red(sibling)) {
312	/* Case 1 - right rotate at parent */	341	/* Case 1 - right rotate at parent */
313	parent->rb_left = tmp1 = sibling->rb_right;	342	tmp1 = sibling->rb_right;
-		343	WRITE_ONCE(parent->rb_left, tmp1);
314	sibling->rb_right = parent;	344	WRITE_ONCE(sibling->rb_right, parent);
315	rb_set_parent_color(tmp1, parent, RB_BLACK);	345	rb_set_parent_color(tmp1, parent, RB_BLACK);
316	__rb_rotate_set_parents(parent, sibling, root,	346	__rb_rotate_set_parents(parent, sibling, root,
317	RB_RED);	347	RB_RED);
318	augment_rotate(parent, sibling);	348	augment_rotate(parent, sibling);
319	sibling = tmp1;	349	sibling = tmp1;
320	}	350	}
321	tmp1 = sibling->rb_left;	351	tmp1 = sibling->rb_left;
322	if (!tmp1 \|\| rb_is_black(tmp1)) {	352	if (!tmp1 \|\| rb_is_black(tmp1)) {
323	tmp2 = sibling->rb_right;	353	tmp2 = sibling->rb_right;
324	if (!tmp2 \|\| rb_is_black(tmp2)) {	354	if (!tmp2 \|\| rb_is_black(tmp2)) {
325	/* Case 2 - sibling color flip */	355	/* Case 2 - sibling color flip */
326	rb_set_parent_color(sibling, parent,	356	rb_set_parent_color(sibling, parent,
327	RB_RED);	357	RB_RED);
328	if (rb_is_red(parent))	358	if (rb_is_red(parent))
329	rb_set_black(parent);	359	rb_set_black(parent);
330	else {	360	else {
331	node = parent;	361	node = parent;
332	parent = rb_parent(node);	362	parent = rb_parent(node);
333	if (parent)	363	if (parent)
334	continue;	364	continue;
335	}	365	}
336	break;	366	break;
337	}	367	}
338	/* Case 3 - right rotate at sibling */	368	/* Case 3 - right rotate at sibling */
339	sibling->rb_right = tmp1 = tmp2->rb_left;	369	tmp1 = tmp2->rb_left;
-		370	WRITE_ONCE(sibling->rb_right, tmp1);
340	tmp2->rb_left = sibling;	371	WRITE_ONCE(tmp2->rb_left, sibling);
341	parent->rb_left = tmp2;	372	WRITE_ONCE(parent->rb_left, tmp2);
342	if (tmp1)	373	if (tmp1)
343	rb_set_parent_color(tmp1, sibling,	374	rb_set_parent_color(tmp1, sibling,
344	RB_BLACK);	375	RB_BLACK);
345	augment_rotate(sibling, tmp2);	376	augment_rotate(sibling, tmp2);
346	tmp1 = sibling;	377	tmp1 = sibling;
347	sibling = tmp2;	378	sibling = tmp2;
348	}	379	}
349	/* Case 4 - left rotate at parent + color flips */	380	/* Case 4 - left rotate at parent + color flips */
350	parent->rb_left = tmp2 = sibling->rb_right;	381	tmp2 = sibling->rb_right;
-		382	WRITE_ONCE(parent->rb_left, tmp2);
351	sibling->rb_right = parent;	383	WRITE_ONCE(sibling->rb_right, parent);
352	rb_set_parent_color(tmp1, sibling, RB_BLACK);	384	rb_set_parent_color(tmp1, sibling, RB_BLACK);
353	if (tmp2)	385	if (tmp2)
354	rb_set_parent(tmp2, parent);	386	rb_set_parent(tmp2, parent);
355	__rb_rotate_set_parents(parent, sibling, root,	387	__rb_rotate_set_parents(parent, sibling, root,
356	RB_BLACK);	388	RB_BLACK);
357	augment_rotate(parent, sibling);	389	augment_rotate(parent, sibling);
358	break;	390	break;
359	}	391	}
360	}	392	}
361	}	393	}
362		394
363	/* Non-inline version for rb_erase_augmented() use */	395	/* Non-inline version for rb_erase_augmented() use */
364	void __rb_erase_color(struct rb_node parent, struct rb_root root,	396	void __rb_erase_color(struct rb_node parent, struct rb_root root,
365	void (augment_rotate)(struct rb_node old, struct rb_node *new))	397	void (augment_rotate)(struct rb_node old, struct rb_node *new))
366	{	398	{
367	____rb_erase_color(parent, root, augment_rotate);	399	____rb_erase_color(parent, root, augment_rotate);
368	}	400	}
369	EXPORT_SYMBOL(__rb_erase_color);	401	EXPORT_SYMBOL(__rb_erase_color);
370		402
371	/*	403	/*
372	* Non-augmented rbtree manipulation functions.	404	* Non-augmented rbtree manipulation functions.
373	*	405	*
374	* We use dummy augmented callbacks here, and have the compiler optimize them	406	* We use dummy augmented callbacks here, and have the compiler optimize them
375	* out of the rb_insert_color() and rb_erase() function definitions.	407	* out of the rb_insert_color() and rb_erase() function definitions.
376	*/	408	*/
377		409
378	static inline void dummy_propagate(struct rb_node node, struct rb_node stop) {}	410	static inline void dummy_propagate(struct rb_node node, struct rb_node stop) {}
379	static inline void dummy_copy(struct rb_node old, struct rb_node new) {}	411	static inline void dummy_copy(struct rb_node old, struct rb_node new) {}
380	static inline void dummy_rotate(struct rb_node old, struct rb_node new) {}	412	static inline void dummy_rotate(struct rb_node old, struct rb_node new) {}
381		413
382	static const struct rb_augment_callbacks dummy_callbacks = {	414	static const struct rb_augment_callbacks dummy_callbacks = {
383	dummy_propagate, dummy_copy, dummy_rotate	415	dummy_propagate, dummy_copy, dummy_rotate
384	};	416	};
385		417
386	void rb_insert_color(struct rb_node node, struct rb_root root)	418	void rb_insert_color(struct rb_node node, struct rb_root root)
387	{	419	{
388	__rb_insert(node, root, dummy_rotate);	420	__rb_insert(node, root, dummy_rotate);
389	}	421	}
390	EXPORT_SYMBOL(rb_insert_color);	422	EXPORT_SYMBOL(rb_insert_color);
391		423
392	void rb_erase(struct rb_node node, struct rb_root root)	424	void rb_erase(struct rb_node node, struct rb_root root)
393	{	425	{
394	struct rb_node *rebalance;	426	struct rb_node *rebalance;
395	rebalance = __rb_erase_augmented(node, root, &dummy_callbacks);	427	rebalance = __rb_erase_augmented(node, root, &dummy_callbacks);
396	if (rebalance)	428	if (rebalance)
397	____rb_erase_color(rebalance, root, dummy_rotate);	429	____rb_erase_color(rebalance, root, dummy_rotate);
398	}	430	}
399	EXPORT_SYMBOL(rb_erase);	431	EXPORT_SYMBOL(rb_erase);
400		432
401	/*	433	/*
402	* Augmented rbtree manipulation functions.	434	* Augmented rbtree manipulation functions.
403	*	435	*
404	* This instantiates the same __always_inline functions as in the non-augmented	436	* This instantiates the same __always_inline functions as in the non-augmented
405	* case, but this time with user-defined callbacks.	437	* case, but this time with user-defined callbacks.
406	*/	438	*/
407		439
408	void __rb_insert_augmented(struct rb_node node, struct rb_root root,	440	void __rb_insert_augmented(struct rb_node node, struct rb_root root,
409	void (augment_rotate)(struct rb_node old, struct rb_node *new))	441	void (augment_rotate)(struct rb_node old, struct rb_node *new))
410	{	442	{
411	__rb_insert(node, root, augment_rotate);	443	__rb_insert(node, root, augment_rotate);
412	}	444	}
413	EXPORT_SYMBOL(__rb_insert_augmented);	445	EXPORT_SYMBOL(__rb_insert_augmented);
414		446
415	/*	447	/*
416	* This function returns the first node (in sort order) of the tree.	448	* This function returns the first node (in sort order) of the tree.
417	*/	449	*/
418	struct rb_node rb_first(const struct rb_root root)	450	struct rb_node rb_first(const struct rb_root root)
419	{	451	{
420	struct rb_node *n;	452	struct rb_node *n;
421		453
422	n = root->rb_node;	454	n = root->rb_node;
423	if (!n)	455	if (!n)
424	return NULL;	456	return NULL;
425	while (n->rb_left)	457	while (n->rb_left)
426	n = n->rb_left;	458	n = n->rb_left;
427	return n;	459	return n;
428	}	460	}
429	EXPORT_SYMBOL(rb_first);	461	EXPORT_SYMBOL(rb_first);
430		462
431	struct rb_node rb_last(const struct rb_root root)	463	struct rb_node rb_last(const struct rb_root root)
432	{	464	{
433	struct rb_node *n;	465	struct rb_node *n;
434		466
435	n = root->rb_node;	467	n = root->rb_node;
436	if (!n)	468	if (!n)
437	return NULL;	469	return NULL;
438	while (n->rb_right)	470	while (n->rb_right)
439	n = n->rb_right;	471	n = n->rb_right;
440	return n;	472	return n;
441	}	473	}
442	EXPORT_SYMBOL(rb_last);	474	EXPORT_SYMBOL(rb_last);
443		475
444	struct rb_node rb_next(const struct rb_node node)	476	struct rb_node rb_next(const struct rb_node node)
445	{	477	{
446	struct rb_node *parent;	478	struct rb_node *parent;
447		479
448	if (RB_EMPTY_NODE(node))	480	if (RB_EMPTY_NODE(node))
449	return NULL;	481	return NULL;
450		482
451	/*	483	/*
452	* If we have a right-hand child, go down and then left as far	484	* If we have a right-hand child, go down and then left as far
453	* as we can.	485	* as we can.
454	*/	486	*/
455	if (node->rb_right) {	487	if (node->rb_right) {
456	node = node->rb_right;	488	node = node->rb_right;
457	while (node->rb_left)	489	while (node->rb_left)
458	node=node->rb_left;	490	node=node->rb_left;
459	return (struct rb_node *)node;	491	return (struct rb_node *)node;
460	}	492	}
461		493
462	/*	494	/*
463	* No right-hand children. Everything down and left is smaller than us,	495	* No right-hand children. Everything down and left is smaller than us,
464	* so any 'next' node must be in the general direction of our parent.	496	* so any 'next' node must be in the general direction of our parent.
465	* Go up the tree; any time the ancestor is a right-hand child of its	497	* Go up the tree; any time the ancestor is a right-hand child of its
466	* parent, keep going up. First time it's a left-hand child of its	498	* parent, keep going up. First time it's a left-hand child of its
467	* parent, said parent is our 'next' node.	499	* parent, said parent is our 'next' node.
468	*/	500	*/

Subversion Repositories Kolibri OS

(root)/drivers/ddk/linux/rbtree.c – Rev 5270 → 6934