[J-u-boot.git] / lib / rbtree.c

// SPDX-License-Identifier: GPL-2.0+
/*
  Red Black Trees
  (C) 1999  Andrea Arcangeli <[email protected]>
  (C) 2002  David Woodhouse <[email protected]>
  (C) 2012  Michel Lespinasse <[email protected]>

  linux/lib/rbtree.c
*/

#include <linux/rbtree_augmented.h>
#ifndef __UBOOT__
#include <linux/export.h>
#else
#include <ubi_uboot.h>
#endif
/*
 * 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.
 */

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