[userspace-rcu.git] / urcu-rbtree.c

/*
 * urcu-rbtree.c
 *
 * Userspace RCU library - Red-Black Tree
 *
 * Copyright (c) 2010 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library 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
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 *
 * Implementation of RCU-adapted data structures and operations based on the RB
 * tree algorithms found in chapter 12 of:
 *
 * Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and
 * Clifford Stein. Introduction to Algorithms, Third Edition. The MIT
 * Press, September 2009.
 */

#define _BSD_SOURCE
#define _LGPL_SOURCE

#include <stdio.h>
#include <pthread.h>

#include <urcu-rbtree.h>
#include <urcu-pointer.h>

/*
 * TODO
 * Deal with memory allocation errors.
 * Can be ensured by reserving a pool of memory entries before doing the
 * insertion, which will have to be function of number of
 * transplantations/rotations required for the operation.
 */

/* Sentinel (bottom nodes). Don't care about p, left, right and key values */
struct rcu_rbtree_node rcu_rbtree_nil = {
	.color = COLOR_BLACK,
};

/*
 * Iterative rbtree search.
 */
struct rcu_rbtree_node* rcu_rbtree_search(struct rcu_rbtree_node *x,
					  void *k, rcu_rbtree_comp comp)
{
	x = rcu_dereference(x);

	while (x != NULL && k != x->key) {
		if (k < x->key)
			x = rcu_dereference(x->left);
		else
			x = rcu_dereference(x->right);
	}
	return x;
}

struct rcu_rbtree_node *rcu_rbtree_min(struct rcu_rbtree_node *x,
				       rcu_rbtree_comp comp)
{
	struct rcu_rbtree_node *xl;

	x = rcu_dereference(x);

	while ((xl = rcu_dereference(x->left)) != NULL)
		x = xl;
	return x;
}

struct rcu_rbtree_node *rcu_rbtree_max(struct rcu_rbtree_node *x,
				       rcu_rbtree_comp comp)
{
	struct rcu_rbtree_node *xr;

	x = rcu_dereference(x);

	while ((xr = rcu_dereference(x->right)) != NULL)
		x = xr;
	return x;
}

/*
 * next and prev need to have mutex held to ensure that parent pointer is
 * coherent.
 */
struct rcu_rbtree_node *rcu_rbtree_next(struct rcu_rbtree_node *x,
					rcu_rbtree_comp comp)
{
	struct rcu_rbtree_node *xr, *y;

	x = rcu_dereference(x);

	if ((xr = rcu_dereference(x->right)) != NULL)
		return rcu_rbtree_min(xr, comp);
	y = rcu_dereference(x->p);
	while (y != NULL && x == rcu_dereference(y->right)) {
		x = y;
		y = rcu_dereference(y->p);
	}
	return y;
}

struct rcu_rbtree_node *rcu_rbtree_prev(struct rcu_rbtree_node *x,
					rcu_rbtree_comp comp)
{
	struct rcu_rbtree_node *xl, *y;

	x = rcu_dereference(x);

	if ((xl = rcu_dereference(x->left)) != NULL)
		return rcu_rbtree_max(xl, comp);
	y = rcu_dereference(x->p);
	while (y != NULL && x == rcu_dereference(y->left)) {
		x = y;
		y = rcu_dereference(y->p);
	}
	return y;
}

/*
 * We have to ensure these assumptions are correct for prev/next
 * traversal:
 *
 * with x being a right child, the assumption that:
 *   x->p->right == x
 * or if x is a left child, the assumption that:
 *   x->p->left == x
 *
 * This explains why we have to allocate a vc copy of the node for left_rotate,
 * right_rotate and transplant operations.
 *
 * We always ensure that the right/left child and correct parent is set in the
 * node copies *before* we reparent the children and make the upper-level point
 * to the copy.
 */

/* RCU: copy x and y, atomically point to new versions. GC old. */
/* Should be eventually followed by a smp_wmc() */
/* Returns the new x. Previous x->right references are changed to yc. */
static struct rcu_rbtree_node *left_rotate(struct rcu_rbtree_node **root,
					   struct rcu_rbtree_node *x,
					   rcu_rbtree_alloc rballoc,
					   rcu_rbtree_free rbfree)
{
	struct rcu_rbtree_node *xc, *y, *yc;

	y = x->right;

	if (x != &rcu_rbtree_nil) {
		xc = rballoc();
		*xc = *x;
		/* Modify children and parents in the node copies */
		xc->right = y->left;
		xc->p = yc;
	} else
		xc = &rcu_rbtree_nil;

	if (y != &rcu_rbtree_nil) {
		yc = rballoc();
		*yc = *y;
		/* Modify children and parents in the node copies */
		yc->left = xc;
		yc->p = x->p;
	} else
		yc = &rcu_rbtree_nil;

	/*
	 * Order stores to node copies (children/parents) before stores that
	 * will make the copies visible to the rest of the tree.
	 */
	smp_wmb();

	/* Make parents point to the copies */
	if (x->p == &rcu_rbtree_nil)
		_STORE_SHARED(*root, yc);
	else if (x == x->p->left)
		_STORE_SHARED(x->p->left, yc);
	else
		_STORE_SHARED(x->p->right, yc);

	/* Assign children parents to copies */
	if (x != &rcu_rbtree_nil) {
		_STORE_SHARED(xc->right->p, xc);
		_STORE_SHARED(xc->left->p, xc);
		defer_rcu(rbfree, x);
	}
	if (y != &rcu_rbtree_nil) {
		_STORE_SHARED(yc->right->p, yc);
		defer_rcu(rbfree, y);
		/* yc->left is xc, its parent is already set in node copy */
	}
	return xc;
}

#if 0 /* orig */
static void left_rotate(struct rcu_rbtree_node **root,
			struct rcu_rbtree_node *x,
			rcu_rbtree_alloc rballoc)
{
	struct rcu_rbtree_node *y;

	y = x->right;
	x->right = y->left;
	if (y->left != &rcu_rbtree_nil)
		y->left->p = x;
	y->p = x->p;
	if (x->p == &rcu_rbtree_nil)
		*root = y;
	else if (x == x->p->left)
		x->p->left = y;
	else
		x->p->right = y;
	y->left = x;
	x->p = y;
}
#endif //0

/* RCU: copy x and y, atomically point to new versions. GC old. */
/* Should be eventually followed by a smp_wmc() */
/* Returns the new x. Previous x->left references are changed to yc. */
static struct rcu_rbtree_node *right_rotate(struct rcu_rbtree_node **root,
					    struct rcu_rbtree_node *x,
					    rcu_rbtree_alloc rballoc,
					    rcu_rbtree_free rbfree)
{
	struct rcu_rbtree_node *xc, *y, *yc;

	y = x->left;

	if (x != &rcu_rbtree_nil) {
		xc = rballoc();
		*xc = *x;
		/* Modify children and parents in the node copies */
		xc->left = y->right;
		xc->p = yc;
	} else
		xc = &rcu_rbtree_nil;

	if (y != &rcu_rbtree_nil) {
		yc = rballoc();
		*yc = *y;
		/* Modify children and parents in the node copies */
		yc->right = xc;
		yc->p = x->p;
	} else
		yc = &rcu_rbtree_nil;

	/*
	 * Order stores to node copies (children/parents) before stores that
	 * will make the copies visible to the rest of the tree.
	 */
	smp_wmb();

	/* Make parents point to the copies */
	if (x->p == &rcu_rbtree_nil)
		_STORE_SHARED(*root, yc);
	else if (x == x->p->right)
		_STORE_SHARED(x->p->right, yc);
	else
		_STORE_SHARED(x->p->left, yc);

	/* Assign children parents to copies */
	if (x != &rcu_rbtree_nil) {
		_STORE_SHARED(xc->left->p, xc);
		_STORE_SHARED(xc->right->p, xc);
		defer_rcu(rbfree, x);
	}
	if (y != &rcu_rbtree_nil) {
		_STORE_SHARED(yc->left->p, yc);
		defer_rcu(rbfree, y);
		/* yc->right is xc, its parent is already set in node copy */
	}
	return xc;
}

#if 0 //orig
static void right_rotate(struct rcu_rbtree_node **root,
			 struct rcu_rbtree_node *x,
			 rcu_rbtree_alloc rballoc)
{
	struct rcu_rbtree_node *y;

	y = x->left;
	x->left = y->right;
	if (y->right != &rcu_rbtree_nil)
		y->right->p = x;
	y->p = x->p;
	if (x->p == &rcu_rbtree_nil)
		*root = y;
	else if (x == x->p->right)
		x->p->right = y;
	else
		x->p->left = y;
	y->right = x;
	x->p = y;
}
#endif //0

static void rcu_rbtree_insert_fixup(struct rcu_rbtree_node **root,
				    struct rcu_rbtree_node *z,
				    rcu_rbtree_alloc rballoc,
				    rcu_rbtree_free rbfree)
{
	struct rcu_rbtree_node *y;

	while (z->p->color == COLOR_RED) {
		if (z->p == z->p->p->left) {
			y = z->p->p->right;
			if (y->color == COLOR_RED) {
				z->p->color = COLOR_BLACK;
				y->color = COLOR_BLACK;
				z->p->p->color = COLOR_RED;
				z = z->p->p;
			} else {
				if (z == z->p->right) {
					z = z->p;
					z = left_rotate(root, z,
							rballoc, rbfree);
				}
				z->p->color = COLOR_BLACK;
				z->p->p->color = COLOR_RED;
				z = right_rotate(root, z->p->p,
						 rballoc, rbfree);
			}
		} else {
			y = z->p->p->left;
			if (y->color == COLOR_RED) {
				z->p->color = COLOR_BLACK;
				y->color = COLOR_BLACK;
				z->p->p->color = COLOR_RED;
				z = z->p->p;
			} else {
				if (z == z->p->left) {
					z = z->p;
					z = right_rotate(root, z,
							 rballoc, rbfree);
				}
				z->p->color = COLOR_BLACK;
				z->p->p->color = COLOR_RED;
				z = left_rotate(root, z->p->p,
						rballoc, rbfree);
			}
		}
	}
	(*root)->color = COLOR_BLACK;
}

/*
 * rcu_rbtree_insert - Insert a node in the RCU rbtree
 *
 * Returns 0 on success, or < 0 on error.
 */
int rcu_rbtree_insert(struct rcu_rbtree_node **root,
		      struct rcu_rbtree_node *z,
		      rcu_rbtree_comp comp,
		      rcu_rbtree_alloc rballoc,
		      rcu_rbtree_free rbfree)
{
	struct rcu_rbtree_node *x, *y;

	y = &rcu_rbtree_nil;
	x = *root;

	while (x != &rcu_rbtree_nil) {
		y = x;
		if (comp(z->key, x->key) < 0)
			x = x->left;
		else
			x = x->right;
	}

	z->p = y;
	z->left = &rcu_rbtree_nil;
	z->right = &rcu_rbtree_nil;
	z->color = COLOR_RED;

	/*
	 * Order stores to z (children/parents) before stores that will make it
	 * visible to the rest of the tree.
	 */
	smp_wmb();

	if (y == &rcu_rbtree_nil)
		_STORE_SHARED(*root, z);
	else if (comp(z->key, y->key) < 0)
		_STORE_SHARED(y->left, z);
	else
		_STORE_SHARED(y->right, z);
	rcu_rbtree_insert_fixup(root, z, rballoc, rbfree);
	/*
	 * Make sure to commit all _STORE_SHARED() for non-coherent caches.
	 */
	smp_wmc();

	return 0;
}

/*
 * Transplant v into u position.
 * Returns new copy of v.
 */
static struct rcu_rbtree_node *
rcu_rbtree_transplant(struct rcu_rbtree_node **root,
		      struct rcu_rbtree_node *u,
		      struct rcu_rbtree_node *v,
		      rcu_rbtree_alloc rballoc,
		      rcu_rbtree_free rbfree)
{
	struct rcu_rbtree_node *vc;

	if (v != &rcu_rbtree_nil) {
		vc = rballoc();
		*vc = *v;

		/* Change vc parent pointer */
		vc->p = u->p;

		/*
		 * Order stores to node copies (children/parents) before stores
		 * that will make the copies visible to the rest of the tree.
		 */
		smp_wmb();
	} else {
		vc = &rcu_rbtree_nil;
	}

	/* Assign upper-level pointer to vc, replacing u. */
	if (u->p == &rcu_rbtree_nil)
		_STORE_SHARED(*root, vc);
	else if (u == u->p->left)
		_STORE_SHARED(u->p->left, vc);
	else
		_STORE_SHARED(u->p->right, vc);

	if (v != &rcu_rbtree_nil) {
		/*
		 * The children pointers in vc are the same as v. We can
		 * therefore reparent v's children to vc safely.
		 */
		_STORE_SHARED(vc->right->p, vc);
		_STORE_SHARED(vc->left->p, vc);

		defer_rcu(rbfree, v);
	}
	return vc;
}

static void rcu_rbtree_remove_fixup(struct rcu_rbtree_node **root,
				    struct rcu_rbtree_node *x,
				    rcu_rbtree_alloc rballoc,
				    rcu_rbtree_free rbfree)
{
	while (x != *root && x->color == COLOR_BLACK) {
		if (x == x->p->left) {
			struct rcu_rbtree_node *w;

			w = x->p->right;
			if (w->color == COLOR_RED) {
				w->color == COLOR_BLACK;
				x->p->color = COLOR_RED;
				left_rotate(root, x->p, rballoc, rbfree);
				/* x is a left node, not copied by rotation */
				w = x->p->right;
			}
			if (w->left->color == COLOR_BLACK
			    && w->right->color == COLOR_BLACK) {
				w->color = COLOR_RED;
				x = x->p;
			} else {
				if (w->right->color == COLOR_BLACK) {
					w->left->color = COLOR_BLACK;
					w->color = COLOR_RED;
					right_rotate(root, w, rballoc, rbfree);
					w = x->p->right;
				}
				w->color = x->p->color;
				x->p->color = COLOR_BLACK;
				w->right->color = COLOR_BLACK;
				left_rotate(root, x->p, rballoc, rbfree);
				x = *root;
			}
		} else {
			struct rcu_rbtree_node *w;

			w = x->p->left;
			if (w->color == COLOR_RED) {
				w->color == COLOR_BLACK;
				x->p->color = COLOR_RED;
				right_rotate(root, x->p, rballoc, rbfree);
				/* x is a right node, not copied by rotation */
				w = x->p->left;
			}
			if (w->right->color == COLOR_BLACK
			    && w->left->color == COLOR_BLACK) {
				w->color = COLOR_RED;
				x = x->p;
			} else {
				if (w->left->color == COLOR_BLACK) {
					w->right->color = COLOR_BLACK;
					w->color = COLOR_RED;
					left_rotate(root, w, rballoc, rbfree);
					w = x->p->left;
				}
				w->color = x->p->color;
				x->p->color = COLOR_BLACK;
				w->left->color = COLOR_BLACK;
				right_rotate(root, x->p, rballoc, rbfree);
				x = *root;
			}
		}
	}
	x->color = COLOR_BLACK;
}

/* Returns the new copy of y->right */
static struct rcu_rbtree_node *
rcu_rbtree_remove_nonil(struct rcu_rbtree_node **root,
			struct rcu_rbtree_node *z,
			struct rcu_rbtree_node *y,
			rcu_rbtree_comp comp,
			rcu_rbtree_alloc rballoc,
			rcu_rbtree_free rbfree)
{
	struct rcu_rbtree_node *x, *xc, *yc;

	x = y->right;

	xc = rballoc();
	yc = rballoc();
	*xc = *x;
	*yc = *y;

	/* Update parent and children pointers within copies */
	if (y->p == z)
		xc->p = yc;
	else {
		/* Transplant y->right (xc) into y, within copy */
		xc->p = y->p;
		/* But also change the right pointer of yc */
		yc->right = z->right;
	}
	/* Transplant y into z, within copy */
	yc->p = z->p;

	yc->left = z->left;
	yc->color = z->color;

	/*
	 * Order stores to node copies (children/parents) before stores that
	 * will make the copies visible to the rest of the tree.
	 */
	smp_wmb();

	/* Update external pointers */

	if (y->p != z) {
		/* Transplant y->right into y, external parent links */

		/* Assign upper-level pointer to xc, replacing y. */
		if (y->p == &rcu_rbtree_nil)
			_STORE_SHARED(*root, xc);
		else if (y == y->p->left)
			_STORE_SHARED(y->p->left, xc);
		else
			_STORE_SHARED(y->p->right, xc);
	}

	/* Transplant y into z, update external parent links */
	if (z->p == &rcu_rbtree_nil)
		_STORE_SHARED(*root, yc);
	else if (z == z->p->left)
		_STORE_SHARED(z->p->left, yc);
	else
		_STORE_SHARED(z->p->right, yc);

	/* Reparent xc's children to xc. */
	_STORE_SHARED(xc->right->p, xc);
	_STORE_SHARED(xc->left->p, xc);
	/* Reparent yc's children to yc */
	_STORE_SHARED(yc->right->p, yc);
	_STORE_SHARED(yc->left->p, yc);

	defer_rcu(rbfree, x);
	defer_rcu(rbfree, y);

	return xc;
}

int rcu_rbtree_remove(struct rcu_rbtree_node **root,
		      struct rcu_rbtree_node *z,
		      rcu_rbtree_comp comp,
		      rcu_rbtree_alloc rballoc,
		      rcu_rbtree_free rbfree)
{
	struct rcu_rbtree_node *x, *y;
	unsigned int y_original_color;

	y = z;
	y_original_color = y->color;

	if (z->left == &rcu_rbtree_nil) {
		x = rcu_rbtree_transplant(root, z, z->right, rballoc, rbfree);
	} else if (z->right == &rcu_rbtree_nil) {
		x = rcu_rbtree_transplant(root, z, z->left, rballoc, rbfree);
	} else {
		y = rcu_rbtree_min(z->right, comp);
		y_original_color = y->color;
		x = rcu_rbtree_remove_nonil(root, z, y, comp, rballoc, rbfree);
	}
	if (y_original_color == COLOR_BLACK)
		rcu_rbtree_remove_fixup(root, x, rballoc, rbfree);
	/*
	 * Commit all _STORE_SHARED().
	 */
	smp_wmc();

	return 0;
}
Commit	Line	Data
00131368 MD	1	/*
	2	* urcu-rbtree.c
	3	*
	4	* Userspace RCU library - Red-Black Tree
	5	*
	6	* Copyright (c) 2010 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
	7	*
	8	* This library is free software; you can redistribute it and/or
	9	* modify it under the terms of the GNU Lesser General Public
	10	* License as published by the Free Software Foundation; either
	11	* version 2.1 of the License, or (at your option) any later version.
	12	*
	13	* This library is distributed in the hope that it will be useful,
	14	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	15	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	16	* Lesser General Public License for more details.
	17	*
	18	* You should have received a copy of the GNU Lesser General Public
	19	* License along with this library; if not, write to the Free Software
	20	* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
	21	*
	22	* Implementation of RCU-adapted data structures and operations based on the RB
	23	* tree algorithms found in chapter 12 of:
	24	*
	25	* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and
	26	* Clifford Stein. Introduction to Algorithms, Third Edition. The MIT
	27	* Press, September 2009.
	28	*/
	29
	30	#define _BSD_SOURCE
	31	#define _LGPL_SOURCE
	32
	33	#include <stdio.h>
	34	#include <pthread.h>
	35
	36	#include <urcu-rbtree.h>
	37	#include <urcu-pointer.h>
	38
	39	/*
	40	* TODO
	41	* Deal with memory allocation errors.
	42	* Can be ensured by reserving a pool of memory entries before doing the
	43	* insertion, which will have to be function of number of
	44	* transplantations/rotations required for the operation.
	45	*/
	46
	47	/* Sentinel (bottom nodes). Don't care about p, left, right and key values */
db5b1669	48	struct rcu_rbtree_node rcu_rbtree_nil = {
00131368 MD	49	.color = COLOR_BLACK,
	50	};
	51
	52	/*
	53	* Iterative rbtree search.
	54	*/
	55	struct rcu_rbtree_node* rcu_rbtree_search(struct rcu_rbtree_node *x,
	56	void *k, rcu_rbtree_comp comp)
	57	{
	58	x = rcu_dereference(x);
	59
	60	while (x != NULL && k != x->key) {
	61	if (k < x->key)
	62	x = rcu_dereference(x->left);
	63	else
	64	x = rcu_dereference(x->right);
	65	}
	66	return x;
	67	}
	68
	69	struct rcu_rbtree_node rcu_rbtree_min(struct rcu_rbtree_node x,
	70	rcu_rbtree_comp comp)
	71	{
	72	struct rcu_rbtree_node *xl;
	73
	74	x = rcu_dereference(x);
	75
	76	while ((xl = rcu_dereference(x->left)) != NULL)
	77	x = xl;
	78	return x;
	79	}
	80
	81	struct rcu_rbtree_node rcu_rbtree_max(struct rcu_rbtree_node x,
	82	rcu_rbtree_comp comp)
	83	{
	84	struct rcu_rbtree_node *xr;
	85
	86	x = rcu_dereference(x);
	87
	88	while ((xr = rcu_dereference(x->right)) != NULL)
	89	x = xr;
	90	return x;
	91	}
	92
	93	/*
	94	* next and prev need to have mutex held to ensure that parent pointer is
	95	* coherent.
	96	*/
	97	struct rcu_rbtree_node rcu_rbtree_next(struct rcu_rbtree_node x,
	98	rcu_rbtree_comp comp)
	99	{
	100	struct rcu_rbtree_node xr, y;
	101
	102	x = rcu_dereference(x);
	103
	104	if ((xr = rcu_dereference(x->right)) != NULL)
	105	return rcu_rbtree_min(xr, comp);
	106	y = rcu_dereference(x->p);
	107	while (y != NULL && x == rcu_dereference(y->right)) {
	108	x = y;
	109	y = rcu_dereference(y->p);
	110	}
	111	return y;
	112	}
113
114	struct rcu_rbtree_node rcu_rbtree_prev(struct rcu_rbtree_node x,
115	rcu_rbtree_comp comp)
116	{
117	struct rcu_rbtree_node xl, y;
118
119	x = rcu_dereference(x);
120
121	if ((xl = rcu_dereference(x->left)) != NULL)
122	return rcu_rbtree_max(xl, comp);
123	y = rcu_dereference(x->p);
124	while (y != NULL && x == rcu_dereference(y->left)) {
125	x = y;
126	y = rcu_dereference(y->p);
127	}
128	return y;
129	}
130
131	/*
132	* We have to ensure these assumptions are correct for prev/next
133	* traversal:
134	*
135	* with x being a right child, the assumption that:
136	* x->p->right == x
137	* or if x is a left child, the assumption that:
138	* x->p->left == x
139	*
140	* This explains why we have to allocate a vc copy of the node for left_rotate,
141	* right_rotate and transplant operations.
142	*
143	* We always ensure that the right/left child and correct parent is set in the
144	* node copies before we reparent the children and make the upper-level point
145	* to the copy.
146	*/
147
148	/* RCU: copy x and y, atomically point to new versions. GC old. */
149	/* Should be eventually followed by a smp_wmc() */
150	/* Returns the new x. Previous x->right references are changed to yc. */
151	static struct rcu_rbtree_node left_rotate(struct rcu_rbtree_node *root,
152	struct rcu_rbtree_node *x,
153	rcu_rbtree_alloc rballoc,
154	rcu_rbtree_free rbfree)
155	{
156	struct rcu_rbtree_node xc, y, *yc;
157
158	y = x->right;
159
21cddea3 MD	160	if (x != &rcu_rbtree_nil) {
	161	xc = rballoc();
	162	xc = x;
	163	/* Modify children and parents in the node copies */
	164	xc->right = y->left;
	165	xc->p = yc;
	166	} else
	167	xc = &rcu_rbtree_nil;
	168
	169	if (y != &rcu_rbtree_nil) {
	170	yc = rballoc();
	171	yc = y;
	172	/* Modify children and parents in the node copies */
	173	yc->left = xc;
	174	yc->p = x->p;
	175	} else
	176	yc = &rcu_rbtree_nil;
00131368 MD	177
	178	/*
	179	* Order stores to node copies (children/parents) before stores that
	180	* will make the copies visible to the rest of the tree.
	181	*/
	182	smp_wmb();
	183
	184	/* Make parents point to the copies */
db5b1669	185	if (x->p == &rcu_rbtree_nil)
00131368 MD	186	_STORE_SHARED(*root, yc);
	187	else if (x == x->p->left)
	188	_STORE_SHARED(x->p->left, yc);
	189	else
	190	_STORE_SHARED(x->p->right, yc);
	191
	192	/* Assign children parents to copies */
21cddea3 MD	193	if (x != &rcu_rbtree_nil) {
	194	_STORE_SHARED(xc->right->p, xc);
	195	_STORE_SHARED(xc->left->p, xc);
	196	defer_rcu(rbfree, x);
	197	}
	198	if (y != &rcu_rbtree_nil) {
	199	_STORE_SHARED(yc->right->p, yc);
	200	defer_rcu(rbfree, y);
	201	/* yc->left is xc, its parent is already set in node copy */
	202	}
00131368 MD	203	return xc;
	204	}
	205
	206	#if 0 /* orig */
	207	static void left_rotate(struct rcu_rbtree_node **root,
	208	struct rcu_rbtree_node *x,
	209	rcu_rbtree_alloc rballoc)
	210	{
	211	struct rcu_rbtree_node *y;
	212
	213	y = x->right;
	214	x->right = y->left;
db5b1669	215	if (y->left != &rcu_rbtree_nil)
00131368 MD	216	y->left->p = x;
00131368 MD	217	y->p = x->p;
db5b1669	218	if (x->p == &rcu_rbtree_nil)
00131368 MD	219	*root = y;
	220	else if (x == x->p->left)
	221	x->p->left = y;
	222	else
	223	x->p->right = y;
	224	y->left = x;
	225	x->p = y;
	226	}
	227	#endif //0
	228
	229	/* RCU: copy x and y, atomically point to new versions. GC old. */
	230	/* Should be eventually followed by a smp_wmc() */
	231	/* Returns the new x. Previous x->left references are changed to yc. */
	232	static struct rcu_rbtree_node right_rotate(struct rcu_rbtree_node *root,
	233	struct rcu_rbtree_node *x,
	234	rcu_rbtree_alloc rballoc,
	235	rcu_rbtree_free rbfree)
	236	{
	237	struct rcu_rbtree_node xc, y, *yc;
	238
	239	y = x->left;
	240
21cddea3 MD	241	if (x != &rcu_rbtree_nil) {
	242	xc = rballoc();
	243	xc = x;
	244	/* Modify children and parents in the node copies */
	245	xc->left = y->right;
	246	xc->p = yc;
	247	} else
	248	xc = &rcu_rbtree_nil;
	249
	250	if (y != &rcu_rbtree_nil) {
	251	yc = rballoc();
	252	yc = y;
	253	/* Modify children and parents in the node copies */
	254	yc->right = xc;
	255	yc->p = x->p;
	256	} else
	257	yc = &rcu_rbtree_nil;
00131368 MD	258
	259	/*
	260	* Order stores to node copies (children/parents) before stores that
	261	* will make the copies visible to the rest of the tree.
	262	*/
	263	smp_wmb();
	264
	265	/* Make parents point to the copies */
db5b1669	266	if (x->p == &rcu_rbtree_nil)
00131368 MD	267	_STORE_SHARED(*root, yc);
	268	else if (x == x->p->right)
	269	_STORE_SHARED(x->p->right, yc);
	270	else
	271	_STORE_SHARED(x->p->left, yc);
	272
	273	/* Assign children parents to copies */
21cddea3 MD	274	if (x != &rcu_rbtree_nil) {
	275	_STORE_SHARED(xc->left->p, xc);
	276	_STORE_SHARED(xc->right->p, xc);
	277	defer_rcu(rbfree, x);
	278	}
	279	if (y != &rcu_rbtree_nil) {
	280	_STORE_SHARED(yc->left->p, yc);
	281	defer_rcu(rbfree, y);
	282	/* yc->right is xc, its parent is already set in node copy */
	283	}
00131368 MD	284	return xc;
	285	}
	286
	287	#if 0 //orig
	288	static void right_rotate(struct rcu_rbtree_node **root,
	289	struct rcu_rbtree_node *x,
	290	rcu_rbtree_alloc rballoc)
	291	{
	292	struct rcu_rbtree_node *y;
	293
	294	y = x->left;
	295	x->left = y->right;
db5b1669	296	if (y->right != &rcu_rbtree_nil)
00131368 MD	297	y->right->p = x;
00131368 MD	298	y->p = x->p;
db5b1669	299	if (x->p == &rcu_rbtree_nil)
00131368 MD	300	*root = y;
	301	else if (x == x->p->right)
	302	x->p->right = y;
	303	else
	304	x->p->left = y;
	305	y->right = x;
	306	x->p = y;
	307	}
	308	#endif //0
	309
	310	static void rcu_rbtree_insert_fixup(struct rcu_rbtree_node **root,
	311	struct rcu_rbtree_node *z,
	312	rcu_rbtree_alloc rballoc,
	313	rcu_rbtree_free rbfree)
	314	{
	315	struct rcu_rbtree_node *y;
	316
	317	while (z->p->color == COLOR_RED) {
	318	if (z->p == z->p->p->left) {
	319	y = z->p->p->right;
	320	if (y->color == COLOR_RED) {
	321	z->p->color = COLOR_BLACK;
	322	y->color = COLOR_BLACK;
	323	z->p->p->color = COLOR_RED;
	324	z = z->p->p;
	325	} else {
	326	if (z == z->p->right) {
	327	z = z->p;
	328	z = left_rotate(root, z,
	329	rballoc, rbfree);
	330	}
	331	z->p->color = COLOR_BLACK;
	332	z->p->p->color = COLOR_RED;
	333	z = right_rotate(root, z->p->p,
	334	rballoc, rbfree);
	335	}
	336	} else {
	337	y = z->p->p->left;
	338	if (y->color == COLOR_RED) {
	339	z->p->color = COLOR_BLACK;
	340	y->color = COLOR_BLACK;
	341	z->p->p->color = COLOR_RED;
	342	z = z->p->p;
	343	} else {
	344	if (z == z->p->left) {
	345	z = z->p;
	346	z = right_rotate(root, z,
	347	rballoc, rbfree);
	348	}
	349	z->p->color = COLOR_BLACK;
	350	z->p->p->color = COLOR_RED;
	351	z = left_rotate(root, z->p->p,
	352	rballoc, rbfree);
	353	}
	354	}
	355	}
	356	(*root)->color = COLOR_BLACK;
	357	}
	358
	359	/*
	360	* rcu_rbtree_insert - Insert a node in the RCU rbtree
	361	*
	362	* Returns 0 on success, or < 0 on error.
	363	*/
364	int rcu_rbtree_insert(struct rcu_rbtree_node **root,
365	struct rcu_rbtree_node *z,
366	rcu_rbtree_comp comp,
367	rcu_rbtree_alloc rballoc,
368	rcu_rbtree_free rbfree)
369	{
370	struct rcu_rbtree_node x, y;
371
db5b1669	372	y = &rcu_rbtree_nil;
00131368 MD	373	x = *root;
00131368 MD	374
db5b1669	375	while (x != &rcu_rbtree_nil) {
00131368 MD	376	y = x;
	377	if (comp(z->key, x->key) < 0)
	378	x = x->left;
	379	else
	380	x = x->right;
	381	}
	382
	383	z->p = y;
db5b1669 MD	384	z->left = &rcu_rbtree_nil;
db5b1669 MD	385	z->right = &rcu_rbtree_nil;
00131368 MD	386	z->color = COLOR_RED;
	387
	388	/*
	389	* Order stores to z (children/parents) before stores that will make it
	390	* visible to the rest of the tree.
	391	*/
	392	smp_wmb();
	393
db5b1669	394	if (y == &rcu_rbtree_nil)
00131368 MD	395	_STORE_SHARED(*root, z);
	396	else if (comp(z->key, y->key) < 0)
	397	_STORE_SHARED(y->left, z);
	398	else
	399	_STORE_SHARED(y->right, z);
	400	rcu_rbtree_insert_fixup(root, z, rballoc, rbfree);
	401	/*
	402	* Make sure to commit all _STORE_SHARED() for non-coherent caches.
	403	*/
	404	smp_wmc();
	405
	406	return 0;
	407	}
	408
	409	/*
	410	* Transplant v into u position.
	411	* Returns new copy of v.
	412	*/
	413	static struct rcu_rbtree_node *
	414	rcu_rbtree_transplant(struct rcu_rbtree_node **root,
	415	struct rcu_rbtree_node *u,
	416	struct rcu_rbtree_node *v,
	417	rcu_rbtree_alloc rballoc,
	418	rcu_rbtree_free rbfree)
	419	{
	420	struct rcu_rbtree_node *vc;
	421
21cddea3 MD	422	if (v != &rcu_rbtree_nil) {
	423	vc = rballoc();
	424	vc = v;
00131368	425
21cddea3 MD	426	/* Change vc parent pointer */
21cddea3 MD	427	vc->p = u->p;
00131368	428
21cddea3 MD	429	/*
	430	* Order stores to node copies (children/parents) before stores
	431	* that will make the copies visible to the rest of the tree.
	432	*/
	433	smp_wmb();
	434	} else {
	435	vc = &rcu_rbtree_nil;
	436	}
00131368 MD	437
00131368 MD	438	/* Assign upper-level pointer to vc, replacing u. */
db5b1669	439	if (u->p == &rcu_rbtree_nil)
00131368 MD	440	_STORE_SHARED(*root, vc);
	441	else if (u == u->p->left)
	442	_STORE_SHARED(u->p->left, vc);
	443	else
	444	_STORE_SHARED(u->p->right, vc);
	445
21cddea3 MD	446	if (v != &rcu_rbtree_nil) {
	447	/*
	448	* The children pointers in vc are the same as v. We can
	449	* therefore reparent v's children to vc safely.
	450	*/
	451	_STORE_SHARED(vc->right->p, vc);
	452	_STORE_SHARED(vc->left->p, vc);
00131368	453
21cddea3 MD	454	defer_rcu(rbfree, v);
21cddea3 MD	455	}
00131368 MD	456	return vc;
	457	}
	458
	459	static void rcu_rbtree_remove_fixup(struct rcu_rbtree_node **root,
	460	struct rcu_rbtree_node *x,
	461	rcu_rbtree_alloc rballoc,
	462	rcu_rbtree_free rbfree)
	463	{
	464	while (x != *root && x->color == COLOR_BLACK) {
	465	if (x == x->p->left) {
	466	struct rcu_rbtree_node *w;
	467
	468	w = x->p->right;
	469	if (w->color == COLOR_RED) {
	470	w->color == COLOR_BLACK;
	471	x->p->color = COLOR_RED;
	472	left_rotate(root, x->p, rballoc, rbfree);
	473	/* x is a left node, not copied by rotation */
	474	w = x->p->right;
	475	}
	476	if (w->left->color == COLOR_BLACK
	477	&& w->right->color == COLOR_BLACK) {
	478	w->color = COLOR_RED;
	479	x = x->p;
	480	} else {
	481	if (w->right->color == COLOR_BLACK) {
	482	w->left->color = COLOR_BLACK;
	483	w->color = COLOR_RED;
	484	right_rotate(root, w, rballoc, rbfree);
	485	w = x->p->right;
	486	}
	487	w->color = x->p->color;
	488	x->p->color = COLOR_BLACK;
	489	w->right->color = COLOR_BLACK;
	490	left_rotate(root, x->p, rballoc, rbfree);
	491	x = *root;
	492	}
	493	} else {
	494	struct rcu_rbtree_node *w;
	495
	496	w = x->p->left;
	497	if (w->color == COLOR_RED) {
	498	w->color == COLOR_BLACK;
	499	x->p->color = COLOR_RED;
	500	right_rotate(root, x->p, rballoc, rbfree);
	501	/* x is a right node, not copied by rotation */
	502	w = x->p->left;
	503	}
	504	if (w->right->color == COLOR_BLACK
	505	&& w->left->color == COLOR_BLACK) {
	506	w->color = COLOR_RED;
	507	x = x->p;
	508	} else {
	509	if (w->left->color == COLOR_BLACK) {
	510	w->right->color = COLOR_BLACK;
	511	w->color = COLOR_RED;
	512	left_rotate(root, w, rballoc, rbfree);
	513	w = x->p->left;
	514	}
	515	w->color = x->p->color;
	516	x->p->color = COLOR_BLACK;
	517	w->left->color = COLOR_BLACK;
	518	right_rotate(root, x->p, rballoc, rbfree);
	519	x = *root;
520	}
521	}
522	}
523	x->color = COLOR_BLACK;
524	}
525
526	/* Returns the new copy of y->right */
527	static struct rcu_rbtree_node *
528	rcu_rbtree_remove_nonil(struct rcu_rbtree_node **root,
529	struct rcu_rbtree_node *z,
530	struct rcu_rbtree_node *y,
531	rcu_rbtree_comp comp,
532	rcu_rbtree_alloc rballoc,
533	rcu_rbtree_free rbfree)
534	{
535	struct rcu_rbtree_node x, xc, *yc;
536
537	x = y->right;
538
539	xc = rballoc();
540	yc = rballoc();
541	xc = x;
542	yc = y;
543
544	/* Update parent and children pointers within copies */
545	if (y->p == z)
546	xc->p = yc;
547	else {
548	/* Transplant y->right (xc) into y, within copy */
549	xc->p = y->p;
550	/* But also change the right pointer of yc */
551	yc->right = z->right;
552	}
553	/* Transplant y into z, within copy */
554	yc->p = z->p;
555
556	yc->left = z->left;
557	yc->color = z->color;
558
559	/*
560	* Order stores to node copies (children/parents) before stores that
561	* will make the copies visible to the rest of the tree.
562	*/
563	smp_wmb();
564
565	/* Update external pointers */
566
567	if (y->p != z) {
568	/* Transplant y->right into y, external parent links */
569
570	/* Assign upper-level pointer to xc, replacing y. */
db5b1669	571	if (y->p == &rcu_rbtree_nil)
00131368 MD	572	_STORE_SHARED(*root, xc);
	573	else if (y == y->p->left)
	574	_STORE_SHARED(y->p->left, xc);
	575	else
	576	_STORE_SHARED(y->p->right, xc);
	577	}
	578
	579	/* Transplant y into z, update external parent links */
db5b1669	580	if (z->p == &rcu_rbtree_nil)
00131368 MD	581	_STORE_SHARED(*root, yc);
	582	else if (z == z->p->left)
	583	_STORE_SHARED(z->p->left, yc);
	584	else
	585	_STORE_SHARED(z->p->right, yc);
	586
	587	/* Reparent xc's children to xc. */
	588	_STORE_SHARED(xc->right->p, xc);
	589	_STORE_SHARED(xc->left->p, xc);
	590	/* Reparent yc's children to yc */
	591	_STORE_SHARED(yc->right->p, yc);
	592	_STORE_SHARED(yc->left->p, yc);
	593
	594	defer_rcu(rbfree, x);
	595	defer_rcu(rbfree, y);
	596
	597	return xc;
	598	}
	599
	600	int rcu_rbtree_remove(struct rcu_rbtree_node **root,
	601	struct rcu_rbtree_node *z,
	602	rcu_rbtree_comp comp,
	603	rcu_rbtree_alloc rballoc,
	604	rcu_rbtree_free rbfree)
	605	{
	606	struct rcu_rbtree_node x, y;
	607	unsigned int y_original_color;
	608
	609	y = z;
	610	y_original_color = y->color;
	611
db5b1669	612	if (z->left == &rcu_rbtree_nil) {
00131368	613	x = rcu_rbtree_transplant(root, z, z->right, rballoc, rbfree);
db5b1669	614	} else if (z->right == &rcu_rbtree_nil) {
00131368 MD	615	x = rcu_rbtree_transplant(root, z, z->left, rballoc, rbfree);
	616	} else {
	617	y = rcu_rbtree_min(z->right, comp);
	618	y_original_color = y->color;
	619	x = rcu_rbtree_remove_nonil(root, z, y, comp, rballoc, rbfree);
	620	}
	621	if (y_original_color == COLOR_BLACK)
	622	rcu_rbtree_remove_fixup(root, x, rballoc, rbfree);
	623	/*
	624	* Commit all _STORE_SHARED().
	625	*/
	626	smp_wmc();
	627
	628	return 0;
	629	}