[linux-2.6-block.git] / tools / lib / rbtree.c

/*
  Red Black Trees
  (C) 1999  Andrea Arcangeli <andrea@suse.de>
  (C) 2002  David Woodhouse <dwmw2@infradead.org>
  (C) 2012  Michel Lespinasse <walken@google.com>

  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_augmented.h>
#include <linux/export.h>

/*
 * 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,
	    bool newleft, struct rb_node **leftmost,
	    void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
	struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;

	if (newleft)
		*leftmost = node;

	while (true) {
		/*
		 * Loop invariant: node is red.
		 */
		if (unlikely(!parent)) {
			/*
			 * The inserted node is root. Either this is the
			 * first node, or we recursed at Case 1 below and
			 * are no longer violating 4).
			 */
			rb_set_parent_color(node, NULL, RB_BLACK);
			break;
		}

		/*
		 * If there is a black parent, we are done.
		 * Otherwise, take some corrective action as,
		 * per 4), we don't want a red root or two
		 * consecutive red nodes.
		 */
		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 - node's uncle is red (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 - node's uncle is black and node is
				 * the parent's right child (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 - node's uncle is black and node is
			 * the parent's left child (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
				 *
				 * Note: p might be red, and then both
				 * p and sl are red after rotation(which
				 * breaks property 4). This is fixed in
				 * Case 4 (in __rb_rotate_set_parents()
				 *         which set sl the color of p
				 *         and set p RB_BLACK)
				 *
				 *   (p)            (sl)
				 *   / \            /  \
				 *  N   sl   -->   P    S
				 *       \        /      \
				 *        S      N        Sr
				 *         \
				 *          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 - left 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 - right 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);
}

/*
 * 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 = {
	.propagate = dummy_propagate,
	.copy = dummy_copy,
	.rotate = dummy_rotate
};

void rb_insert_color(struct rb_node *node, struct rb_root *root)
{
	__rb_insert(node, root, false, NULL, dummy_rotate);
}

void rb_erase(struct rb_node *node, struct rb_root *root)
{
	struct rb_node *rebalance;
	rebalance = __rb_erase_augmented(node, root,
					 NULL, &dummy_callbacks);
	if (rebalance)
		____rb_erase_color(rebalance, root, dummy_rotate);
}

void rb_insert_color_cached(struct rb_node *node,
			    struct rb_root_cached *root, bool leftmost)
{
	__rb_insert(node, &root->rb_root, leftmost,
		    &root->rb_leftmost, dummy_rotate);
}

void rb_erase_cached(struct rb_node *node, struct rb_root_cached *root)
{
	struct rb_node *rebalance;
	rebalance = __rb_erase_augmented(node, &root->rb_root,
					 &root->rb_leftmost, &dummy_callbacks);
	if (rebalance)
		____rb_erase_color(rebalance, &root->rb_root, dummy_rotate);
}

/*
 * 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,
			   bool newleft, struct rb_node **leftmost,
	void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
	__rb_insert(node, root, newleft, leftmost, augment_rotate);
}

/*
 * 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;
}

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

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

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

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

	/* Copy the pointers/colour from the victim to the replacement */
	*new = *victim;

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

void rb_replace_node_cached(struct rb_node *victim, struct rb_node *new,
			    struct rb_root_cached *root)
{
	rb_replace_node(victim, new, &root->rb_root);

	if (root->rb_leftmost == victim)
		root->rb_leftmost = new;
}

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

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);
}
Commit	Line	Data
3f735377 ACM	1	/*
	2	Red Black Trees
	3	(C) 1999 Andrea Arcangeli <andrea@suse.de>
	4	(C) 2002 David Woodhouse <dwmw2@infradead.org>
	5	(C) 2012 Michel Lespinasse <walken@google.com>
	6
	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
	9	the Free Software Foundation; either version 2 of the License, or
	10	(at your option) any later version.
	11
	12	This program is distributed in the hope that it will be useful,
	13	but WITHOUT ANY WARRANTY; without even the implied warranty of
	14	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	15	GNU General Public License for more details.
	16
	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
	19	Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
	20
	21	linux/lib/rbtree.c
	22	*/
	23
	24	#include <linux/rbtree_augmented.h>
3aef2cad	25	#include <linux/export.h>
3f735377 ACM	26
	27	/*
	28	* red-black trees properties: http://en.wikipedia.org/wiki/Rbtree
	29	*
	30	* 1) A node is either red or black
	31	* 2) The root is black
	32	* 3) All leaves (NULL) 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
	35	* of black nodes.
	36	*
	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
	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.
	41	*
	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
	44	* parentheses and have some accompanying text comment.
	45	*/
	46
3aef2cad DB	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	*/
	70
3f735377 ACM	71	static inline void rb_set_black(struct rb_node *rb)
	72	{
	73	rb->__rb_parent_color \|= RB_BLACK;
	74	}
	75
	76	static inline struct rb_node rb_red_parent(struct rb_node red)
	77	{
	78	return (struct rb_node *)red->__rb_parent_color;
	79	}
	80
	81	/*
	82	* Helper function for rotations:
	83	* - old's parent and color get assigned to new
	84	* - old gets assigned new as a parent and 'color' as a color.
	85	*/
	86	static inline void
	87	__rb_rotate_set_parents(struct rb_node old, struct rb_node new,
	88	struct rb_root *root, int color)
	89	{
	90	struct rb_node *parent = rb_parent(old);
	91	new->__rb_parent_color = old->__rb_parent_color;
	92	rb_set_parent_color(old, new, color);
	93	__rb_change_child(old, new, parent, root);
	94	}
	95
	96	static __always_inline void
	97	__rb_insert(struct rb_node node, struct rb_root root,
3aef2cad	98	bool newleft, struct rb_node **leftmost,
3f735377 ACM	99	void (augment_rotate)(struct rb_node old, struct rb_node *new))
	100	{
	101	struct rb_node parent = rb_red_parent(node), gparent, *tmp;
	102
3aef2cad DB	103	if (newleft)
	104	*leftmost = node;
	105
3f735377 ACM	106	while (true) {
3f735377 ACM	107	/*
3aef2cad	108	* Loop invariant: node is red.
3f735377	109	*/
3aef2cad DB	110	if (unlikely(!parent)) {
	111	/*
	112	* The inserted node is root. Either this is the
	113	* first node, or we recursed at Case 1 below and
	114	* are no longer violating 4).
	115	*/
3f735377 ACM	116	rb_set_parent_color(node, NULL, RB_BLACK);
3f735377 ACM	117	break;
3aef2cad DB	118	}
	119
	120	/*
	121	* If there is a black parent, we are done.
	122	* Otherwise, take some corrective action as,
	123	* per 4), we don't want a red root or two
	124	* consecutive red nodes.
	125	*/
	126	if(rb_is_black(parent))
3f735377 ACM	127	break;
	128
	129	gparent = rb_red_parent(parent);
	130
	131	tmp = gparent->rb_right;
	132	if (parent != tmp) { /* parent == gparent->rb_left */
	133	if (tmp && rb_is_red(tmp)) {
	134	/*
3aef2cad	135	* Case 1 - node's uncle is red (color flips).
3f735377 ACM	136	*
	137	* G g
	138	* / \ / \
	139	* p u --> P U
	140	* / /
	141	* n n
	142	*
	143	* However, since g's parent might be red, and
	144	* 4) does not allow this, we need to recurse
	145	* at g.
	146	*/
	147	rb_set_parent_color(tmp, gparent, RB_BLACK);
	148	rb_set_parent_color(parent, gparent, RB_BLACK);
	149	node = gparent;
	150	parent = rb_parent(node);
	151	rb_set_parent_color(node, parent, RB_RED);
	152	continue;
	153	}
	154
	155	tmp = parent->rb_right;
	156	if (node == tmp) {
	157	/*
3aef2cad DB	158	* Case 2 - node's uncle is black and node is
3aef2cad DB	159	* the parent's right child (left rotate at parent).
3f735377 ACM	160	*
	161	* G G
	162	* / \ / \
	163	* p U --> n U
	164	* \ /
	165	* n p
	166	*
	167	* This still leaves us in violation of 4), the
	168	* continuation into Case 3 will fix that.
	169	*/
3aef2cad DB	170	tmp = node->rb_left;
	171	WRITE_ONCE(parent->rb_right, tmp);
	172	WRITE_ONCE(node->rb_left, parent);
3f735377 ACM	173	if (tmp)
	174	rb_set_parent_color(tmp, parent,
	175	RB_BLACK);
	176	rb_set_parent_color(parent, node, RB_RED);
	177	augment_rotate(parent, node);
	178	parent = node;
	179	tmp = node->rb_right;
	180	}
	181
	182	/*
3aef2cad DB	183	* Case 3 - node's uncle is black and node is
3aef2cad DB	184	* the parent's left child (right rotate at gparent).
3f735377 ACM	185	*
	186	* G P
	187	* / \ / \
	188	* p U --> n g
	189	* / \
	190	* n U
	191	*/
3aef2cad DB	192	WRITE_ONCE(gparent->rb_left, tmp); /* == parent->rb_right */
3aef2cad DB	193	WRITE_ONCE(parent->rb_right, gparent);
3f735377 ACM	194	if (tmp)
	195	rb_set_parent_color(tmp, gparent, RB_BLACK);
	196	__rb_rotate_set_parents(gparent, parent, root, RB_RED);
	197	augment_rotate(gparent, parent);
	198	break;
	199	} else {
	200	tmp = gparent->rb_left;
	201	if (tmp && rb_is_red(tmp)) {
	202	/* Case 1 - color flips */
	203	rb_set_parent_color(tmp, gparent, RB_BLACK);
	204	rb_set_parent_color(parent, gparent, RB_BLACK);
	205	node = gparent;
	206	parent = rb_parent(node);
	207	rb_set_parent_color(node, parent, RB_RED);
	208	continue;
	209	}
	210
	211	tmp = parent->rb_left;
	212	if (node == tmp) {
	213	/* Case 2 - right rotate at parent */
3aef2cad DB	214	tmp = node->rb_right;
	215	WRITE_ONCE(parent->rb_left, tmp);
	216	WRITE_ONCE(node->rb_right, parent);
3f735377 ACM	217	if (tmp)
	218	rb_set_parent_color(tmp, parent,
	219	RB_BLACK);
	220	rb_set_parent_color(parent, node, RB_RED);
	221	augment_rotate(parent, node);
	222	parent = node;
	223	tmp = node->rb_left;
	224	}
	225
	226	/* Case 3 - left rotate at gparent */
3aef2cad DB	227	WRITE_ONCE(gparent->rb_right, tmp); /* == parent->rb_left */
3aef2cad DB	228	WRITE_ONCE(parent->rb_left, gparent);
3f735377 ACM	229	if (tmp)
	230	rb_set_parent_color(tmp, gparent, RB_BLACK);
	231	__rb_rotate_set_parents(gparent, parent, root, RB_RED);
	232	augment_rotate(gparent, parent);
	233	break;
	234	}
	235	}
	236	}
	237
	238	/*
	239	* Inline version for rb_erase() use - we want to be able to inline
	240	* and eliminate the dummy_rotate callback there
	241	*/
	242	static __always_inline void
	243	____rb_erase_color(struct rb_node parent, struct rb_root root,
	244	void (augment_rotate)(struct rb_node old, struct rb_node *new))
	245	{
	246	struct rb_node node = NULL, sibling, tmp1, tmp2;
	247
	248	while (true) {
	249	/*
	250	* Loop invariants:
	251	* - node is black (or NULL on first iteration)
	252	* - node is not the root (parent is not NULL)
	253	* - All leaf paths going through parent and node have a
	254	* black node count that is 1 lower than other leaf paths.
	255	*/
	256	sibling = parent->rb_right;
	257	if (node != sibling) { /* node == parent->rb_left */
	258	if (rb_is_red(sibling)) {
	259	/*
	260	* Case 1 - left rotate at parent
	261	*
	262	* P S
	263	* / \ / \
	264	* N s --> p Sr
	265	* / \ / \
	266	* Sl Sr N Sl
	267	*/
3aef2cad DB	268	tmp1 = sibling->rb_left;
	269	WRITE_ONCE(parent->rb_right, tmp1);
	270	WRITE_ONCE(sibling->rb_left, parent);
3f735377 ACM	271	rb_set_parent_color(tmp1, parent, RB_BLACK);
	272	__rb_rotate_set_parents(parent, sibling, root,
	273	RB_RED);
	274	augment_rotate(parent, sibling);
	275	sibling = tmp1;
	276	}
	277	tmp1 = sibling->rb_right;
	278	if (!tmp1 \|\| rb_is_black(tmp1)) {
	279	tmp2 = sibling->rb_left;
	280	if (!tmp2 \|\| rb_is_black(tmp2)) {
	281	/*
	282	* Case 2 - sibling color flip
	283	* (p could be either color here)
	284	*
	285	* (p) (p)
	286	* / \ / \
	287	* N S --> N s
	288	* / \ / \
	289	* Sl Sr Sl Sr
	290	*
	291	* This leaves us violating 5) which
	292	* can be fixed by flipping p to black
	293	* if it was red, or by recursing at p.
	294	* p is red when coming from Case 1.
	295	*/
	296	rb_set_parent_color(sibling, parent,
	297	RB_RED);
	298	if (rb_is_red(parent))
	299	rb_set_black(parent);
	300	else {
	301	node = parent;
	302	parent = rb_parent(node);
	303	if (parent)
	304	continue;
	305	}
	306	break;
	307	}
	308	/*
	309	* Case 3 - right rotate at sibling
	310	* (p could be either color here)
	311	*
	312	* (p) (p)
	313	* / \ / \
3aef2cad	314	* N S --> N sl
3f735377	315	* / \ \
3aef2cad	316	* sl Sr S
3f735377 ACM	317	* \
3f735377 ACM	318	* Sr
3aef2cad DB	319	*
	320	* Note: p might be red, and then both
	321	* p and sl are red after rotation(which
	322	* breaks property 4). This is fixed in
	323	* Case 4 (in __rb_rotate_set_parents()
	324	* which set sl the color of p
	325	* and set p RB_BLACK)
	326	*
	327	* (p) (sl)
	328	* / \ / \
	329	* N sl --> P S
	330	* \ / \
	331	* S N Sr
	332	* \
	333	* Sr
3f735377	334	*/
3aef2cad DB	335	tmp1 = tmp2->rb_right;
	336	WRITE_ONCE(sibling->rb_left, tmp1);
	337	WRITE_ONCE(tmp2->rb_right, sibling);
	338	WRITE_ONCE(parent->rb_right, tmp2);
3f735377 ACM	339	if (tmp1)
	340	rb_set_parent_color(tmp1, sibling,
	341	RB_BLACK);
	342	augment_rotate(sibling, tmp2);
	343	tmp1 = sibling;
	344	sibling = tmp2;
	345	}
	346	/*
	347	* Case 4 - left rotate at parent + color flips
	348	* (p and sl could be either color here.
	349	* After rotation, p becomes black, s acquires
	350	* p's color, and sl keeps its color)
	351	*
	352	* (p) (s)
	353	* / \ / \
	354	* N S --> P Sr
	355	* / \ / \
	356	* (sl) sr N (sl)
	357	*/
3aef2cad DB	358	tmp2 = sibling->rb_left;
	359	WRITE_ONCE(parent->rb_right, tmp2);
	360	WRITE_ONCE(sibling->rb_left, parent);
3f735377 ACM	361	rb_set_parent_color(tmp1, sibling, RB_BLACK);
	362	if (tmp2)
	363	rb_set_parent(tmp2, parent);
	364	__rb_rotate_set_parents(parent, sibling, root,
	365	RB_BLACK);
	366	augment_rotate(parent, sibling);
	367	break;
	368	} else {
	369	sibling = parent->rb_left;
	370	if (rb_is_red(sibling)) {
	371	/* Case 1 - right rotate at parent */
3aef2cad DB	372	tmp1 = sibling->rb_right;
	373	WRITE_ONCE(parent->rb_left, tmp1);
	374	WRITE_ONCE(sibling->rb_right, parent);
3f735377 ACM	375	rb_set_parent_color(tmp1, parent, RB_BLACK);
	376	__rb_rotate_set_parents(parent, sibling, root,
	377	RB_RED);
	378	augment_rotate(parent, sibling);
	379	sibling = tmp1;
	380	}
	381	tmp1 = sibling->rb_left;
	382	if (!tmp1 \|\| rb_is_black(tmp1)) {
	383	tmp2 = sibling->rb_right;
	384	if (!tmp2 \|\| rb_is_black(tmp2)) {
	385	/* Case 2 - sibling color flip */
	386	rb_set_parent_color(sibling, parent,
	387	RB_RED);
	388	if (rb_is_red(parent))
	389	rb_set_black(parent);
	390	else {
	391	node = parent;
	392	parent = rb_parent(node);
	393	if (parent)
	394	continue;
	395	}
	396	break;
	397	}
3aef2cad DB	398	/* Case 3 - left rotate at sibling */
	399	tmp1 = tmp2->rb_left;
	400	WRITE_ONCE(sibling->rb_right, tmp1);
	401	WRITE_ONCE(tmp2->rb_left, sibling);
	402	WRITE_ONCE(parent->rb_left, tmp2);
3f735377 ACM	403	if (tmp1)
	404	rb_set_parent_color(tmp1, sibling,
	405	RB_BLACK);
	406	augment_rotate(sibling, tmp2);
	407	tmp1 = sibling;
	408	sibling = tmp2;
	409	}
3aef2cad DB	410	/* Case 4 - right rotate at parent + color flips */
	411	tmp2 = sibling->rb_right;
	412	WRITE_ONCE(parent->rb_left, tmp2);
	413	WRITE_ONCE(sibling->rb_right, parent);
3f735377 ACM	414	rb_set_parent_color(tmp1, sibling, RB_BLACK);
	415	if (tmp2)
	416	rb_set_parent(tmp2, parent);
	417	__rb_rotate_set_parents(parent, sibling, root,
	418	RB_BLACK);
	419	augment_rotate(parent, sibling);
	420	break;
	421	}
	422	}
	423	}
	424
	425	/* Non-inline version for rb_erase_augmented() use */
	426	void __rb_erase_color(struct rb_node parent, struct rb_root root,
	427	void (augment_rotate)(struct rb_node old, struct rb_node *new))
	428	{
	429	____rb_erase_color(parent, root, augment_rotate);
	430	}
	431
	432	/*
	433	* Non-augmented rbtree manipulation functions.
	434	*
	435	* We use dummy augmented callbacks here, and have the compiler optimize them
	436	* out of the rb_insert_color() and rb_erase() function definitions.
	437	*/
	438
	439	static inline void dummy_propagate(struct rb_node node, struct rb_node stop) {}
	440	static inline void dummy_copy(struct rb_node old, struct rb_node new) {}
	441	static inline void dummy_rotate(struct rb_node old, struct rb_node new) {}
	442
	443	static const struct rb_augment_callbacks dummy_callbacks = {
3aef2cad DB	444	.propagate = dummy_propagate,
	445	.copy = dummy_copy,
	446	.rotate = dummy_rotate
3f735377 ACM	447	};
	448
	449	void rb_insert_color(struct rb_node node, struct rb_root root)
	450	{
3aef2cad	451	__rb_insert(node, root, false, NULL, dummy_rotate);
3f735377 ACM	452	}
	453
	454	void rb_erase(struct rb_node node, struct rb_root root)
	455	{
	456	struct rb_node *rebalance;
3aef2cad DB	457	rebalance = __rb_erase_augmented(node, root,
3aef2cad DB	458	NULL, &dummy_callbacks);
3f735377 ACM	459	if (rebalance)
	460	____rb_erase_color(rebalance, root, dummy_rotate);
	461	}
	462
3aef2cad DB	463	void rb_insert_color_cached(struct rb_node *node,
	464	struct rb_root_cached *root, bool leftmost)
	465	{
	466	__rb_insert(node, &root->rb_root, leftmost,
	467	&root->rb_leftmost, dummy_rotate);
	468	}
	469
	470	void rb_erase_cached(struct rb_node node, struct rb_root_cached root)
	471	{
	472	struct rb_node *rebalance;
	473	rebalance = __rb_erase_augmented(node, &root->rb_root,
	474	&root->rb_leftmost, &dummy_callbacks);
	475	if (rebalance)
	476	____rb_erase_color(rebalance, &root->rb_root, dummy_rotate);
	477	}
	478
3f735377 ACM	479	/*
	480	* Augmented rbtree manipulation functions.
	481	*
	482	* This instantiates the same __always_inline functions as in the non-augmented
	483	* case, but this time with user-defined callbacks.
	484	*/
	485
	486	void __rb_insert_augmented(struct rb_node node, struct rb_root root,
3aef2cad	487	bool newleft, struct rb_node **leftmost,
3f735377 ACM	488	void (augment_rotate)(struct rb_node old, struct rb_node *new))
3f735377 ACM	489	{
3aef2cad	490	__rb_insert(node, root, newleft, leftmost, augment_rotate);
3f735377 ACM	491	}
	492
	493	/*
	494	* This function returns the first node (in sort order) of the tree.
	495	*/
	496	struct rb_node rb_first(const struct rb_root root)
	497	{
	498	struct rb_node *n;
	499
	500	n = root->rb_node;
	501	if (!n)
	502	return NULL;
	503	while (n->rb_left)
	504	n = n->rb_left;
	505	return n;
	506	}
	507
	508	struct rb_node rb_last(const struct rb_root root)
	509	{
	510	struct rb_node *n;
	511
	512	n = root->rb_node;
	513	if (!n)
	514	return NULL;
	515	while (n->rb_right)
	516	n = n->rb_right;
	517	return n;
	518	}
	519
	520	struct rb_node rb_next(const struct rb_node node)
	521	{
	522	struct rb_node *parent;
	523
	524	if (RB_EMPTY_NODE(node))
	525	return NULL;
	526
	527	/*
	528	* If we have a right-hand child, go down and then left as far
	529	* as we can.
	530	*/
	531	if (node->rb_right) {
	532	node = node->rb_right;
	533	while (node->rb_left)
	534	node=node->rb_left;
	535	return (struct rb_node *)node;
	536	}
	537
	538	/*
	539	* No right-hand children. Everything down and left is smaller than us,
	540	* so any 'next' node must be in the general direction of our parent.
	541	* Go up the tree; any time the ancestor is a right-hand child of its
	542	* parent, keep going up. First time it's a left-hand child of its
	543	* parent, said parent is our 'next' node.
	544	*/
	545	while ((parent = rb_parent(node)) && node == parent->rb_right)
	546	node = parent;
	547
	548	return parent;
	549	}
	550
	551	struct rb_node rb_prev(const struct rb_node node)
	552	{
	553	struct rb_node *parent;
	554
555	if (RB_EMPTY_NODE(node))
556	return NULL;
557
558	/*
559	* If we have a left-hand child, go down and then right as far
560	* as we can.
561	*/
562	if (node->rb_left) {
563	node = node->rb_left;
564	while (node->rb_right)
565	node=node->rb_right;
566	return (struct rb_node *)node;
567	}
568
569	/*
570	* No left-hand children. Go up till we find an ancestor which
571	* is a right-hand child of its parent.
572	*/
573	while ((parent = rb_parent(node)) && node == parent->rb_left)
574	node = parent;
575
576	return parent;
577	}
578
579	void rb_replace_node(struct rb_node victim, struct rb_node new,
580	struct rb_root *root)
581	{
582	struct rb_node *parent = rb_parent(victim);
583
3aef2cad DB	584	/* Copy the pointers/colour from the victim to the replacement */
	585	new = victim;
	586
3f735377	587	/* Set the surrounding nodes to point to the replacement */
3f735377 ACM	588	if (victim->rb_left)
	589	rb_set_parent(victim->rb_left, new);
	590	if (victim->rb_right)
	591	rb_set_parent(victim->rb_right, new);
3aef2cad DB	592	__rb_change_child(victim, new, parent, root);
3aef2cad DB	593	}
3f735377	594
3aef2cad DB	595	void rb_replace_node_cached(struct rb_node victim, struct rb_node new,
	596	struct rb_root_cached *root)
	597	{
	598	rb_replace_node(victim, new, &root->rb_root);
	599
	600	if (root->rb_leftmost == victim)
	601	root->rb_leftmost = new;
3f735377 ACM	602	}
	603
	604	static struct rb_node rb_left_deepest_node(const struct rb_node node)
	605	{
	606	for (;;) {
	607	if (node->rb_left)
	608	node = node->rb_left;
	609	else if (node->rb_right)
	610	node = node->rb_right;
	611	else
	612	return (struct rb_node *)node;
	613	}
	614	}
	615
	616	struct rb_node rb_next_postorder(const struct rb_node node)
	617	{
	618	const struct rb_node *parent;
	619	if (!node)
	620	return NULL;
	621	parent = rb_parent(node);
	622
	623	/* If we're sitting on node, we've already seen our children */
	624	if (parent && node == parent->rb_left && parent->rb_right) {
	625	/* If we are the parent's left node, go to the parent's right
	626	* node then all the way down to the left */
	627	return rb_left_deepest_node(parent->rb_right);
	628	} else
	629	/* Otherwise we are the parent's right node, and the parent
	630	* should be next */
	631	return (struct rb_node *)parent;
	632	}
	633
	634	struct rb_node rb_first_postorder(const struct rb_root root)
	635	{
	636	if (!root->rb_node)
	637	return NULL;
	638
	639	return rb_left_deepest_node(root->rb_node);
	640	}