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

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

	/* Modify children and parents in the node copies */
	xc->right = y->left;
	xc->p = yc;
	yc->left = xc;
	yc->p = x->p;

	/*
	 * 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 */
	_STORE_SHARED(xc->right->p, xc);
	_STORE_SHARED(xc->left->p, xc);
	_STORE_SHARED(yc->right->p, yc);
	/* yc->left is xc, its parent is already set in node copy */

	defer_rcu(rbfree, x);
	defer_rcu(rbfree, y);
	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;

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

	/* Modify children and parents in the node copies */
	xc->left = y->right;
	xc->p = yc;
	yc->right = xc;
	yc->p = x->p;

	/*
	 * 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 */
	_STORE_SHARED(xc->left->p, xc);
	_STORE_SHARED(xc->right->p, xc);
	_STORE_SHARED(yc->left->p, yc);
	/* yc->right is xc, its parent is already set in node copy */

	defer_rcu(rbfree, x);
	defer_rcu(rbfree, y);
	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;

	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();

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

	/*
	 * 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
160	yc = rballoc();
161	xc = rballoc();
162	xc = x;
163	yc = y;
164
165	/* Modify children and parents in the node copies */
166	xc->right = y->left;
167	xc->p = yc;
168	yc->left = xc;
169	yc->p = x->p;
170
171	/*
172	* Order stores to node copies (children/parents) before stores that
173	* will make the copies visible to the rest of the tree.
174	*/
175	smp_wmb();
176
177	/* Make parents point to the copies */
db5b1669	178	if (x->p == &rcu_rbtree_nil)
00131368 MD	179	_STORE_SHARED(*root, yc);
	180	else if (x == x->p->left)
	181	_STORE_SHARED(x->p->left, yc);
	182	else
	183	_STORE_SHARED(x->p->right, yc);
	184
	185	/* Assign children parents to copies */
	186	_STORE_SHARED(xc->right->p, xc);
	187	_STORE_SHARED(xc->left->p, xc);
	188	_STORE_SHARED(yc->right->p, yc);
	189	/* yc->left is xc, its parent is already set in node copy */
	190
	191	defer_rcu(rbfree, x);
	192	defer_rcu(rbfree, y);
	193	return xc;
	194	}
	195
	196	#if 0 /* orig */
	197	static void left_rotate(struct rcu_rbtree_node **root,
	198	struct rcu_rbtree_node *x,
	199	rcu_rbtree_alloc rballoc)
	200	{
	201	struct rcu_rbtree_node *y;
	202
	203	y = x->right;
	204	x->right = y->left;
db5b1669	205	if (y->left != &rcu_rbtree_nil)
00131368 MD	206	y->left->p = x;
00131368 MD	207	y->p = x->p;
db5b1669	208	if (x->p == &rcu_rbtree_nil)
00131368 MD	209	*root = y;
	210	else if (x == x->p->left)
	211	x->p->left = y;
	212	else
	213	x->p->right = y;
	214	y->left = x;
	215	x->p = y;
	216	}
	217	#endif //0
	218
	219	/* RCU: copy x and y, atomically point to new versions. GC old. */
	220	/* Should be eventually followed by a smp_wmc() */
	221	/* Returns the new x. Previous x->left references are changed to yc. */
	222	static struct rcu_rbtree_node right_rotate(struct rcu_rbtree_node *root,
	223	struct rcu_rbtree_node *x,
	224	rcu_rbtree_alloc rballoc,
	225	rcu_rbtree_free rbfree)
	226	{
	227	struct rcu_rbtree_node xc, y, *yc;
	228
	229	y = x->left;
	230
	231	yc = rballoc();
	232	xc = rballoc();
	233	xc = x;
	234	yc = y;
	235
	236	/* Modify children and parents in the node copies */
	237	xc->left = y->right;
	238	xc->p = yc;
	239	yc->right = xc;
	240	yc->p = x->p;
	241
	242	/*
	243	* Order stores to node copies (children/parents) before stores that
	244	* will make the copies visible to the rest of the tree.
	245	*/
	246	smp_wmb();
	247
	248	/* Make parents point to the copies */
db5b1669	249	if (x->p == &rcu_rbtree_nil)
00131368 MD	250	_STORE_SHARED(*root, yc);
	251	else if (x == x->p->right)
	252	_STORE_SHARED(x->p->right, yc);
	253	else
	254	_STORE_SHARED(x->p->left, yc);
	255
	256	/* Assign children parents to copies */
	257	_STORE_SHARED(xc->left->p, xc);
	258	_STORE_SHARED(xc->right->p, xc);
	259	_STORE_SHARED(yc->left->p, yc);
	260	/* yc->right is xc, its parent is already set in node copy */
	261
	262	defer_rcu(rbfree, x);
	263	defer_rcu(rbfree, y);
	264	return xc;
	265	}
	266
	267	#if 0 //orig
	268	static void right_rotate(struct rcu_rbtree_node **root,
	269	struct rcu_rbtree_node *x,
	270	rcu_rbtree_alloc rballoc)
	271	{
	272	struct rcu_rbtree_node *y;
	273
	274	y = x->left;
	275	x->left = y->right;
db5b1669	276	if (y->right != &rcu_rbtree_nil)
00131368 MD	277	y->right->p = x;
00131368 MD	278	y->p = x->p;
db5b1669	279	if (x->p == &rcu_rbtree_nil)
00131368 MD	280	*root = y;
	281	else if (x == x->p->right)
	282	x->p->right = y;
	283	else
	284	x->p->left = y;
	285	y->right = x;
	286	x->p = y;
	287	}
	288	#endif //0
	289
	290	static void rcu_rbtree_insert_fixup(struct rcu_rbtree_node **root,
	291	struct rcu_rbtree_node *z,
	292	rcu_rbtree_alloc rballoc,
	293	rcu_rbtree_free rbfree)
	294	{
	295	struct rcu_rbtree_node *y;
	296
	297	while (z->p->color == COLOR_RED) {
	298	if (z->p == z->p->p->left) {
	299	y = z->p->p->right;
	300	if (y->color == COLOR_RED) {
	301	z->p->color = COLOR_BLACK;
	302	y->color = COLOR_BLACK;
	303	z->p->p->color = COLOR_RED;
	304	z = z->p->p;
	305	} else {
	306	if (z == z->p->right) {
	307	z = z->p;
	308	z = left_rotate(root, z,
	309	rballoc, rbfree);
	310	}
	311	z->p->color = COLOR_BLACK;
	312	z->p->p->color = COLOR_RED;
	313	z = right_rotate(root, z->p->p,
	314	rballoc, rbfree);
	315	}
	316	} else {
	317	y = z->p->p->left;
	318	if (y->color == COLOR_RED) {
	319	z->p->color = COLOR_BLACK;
	320	y->color = COLOR_BLACK;
	321	z->p->p->color = COLOR_RED;
	322	z = z->p->p;
	323	} else {
	324	if (z == z->p->left) {
	325	z = z->p;
	326	z = right_rotate(root, z,
	327	rballoc, rbfree);
	328	}
	329	z->p->color = COLOR_BLACK;
	330	z->p->p->color = COLOR_RED;
	331	z = left_rotate(root, z->p->p,
	332	rballoc, rbfree);
	333	}
	334	}
	335	}
	336	(*root)->color = COLOR_BLACK;
	337	}
	338
	339	/*
	340	* rcu_rbtree_insert - Insert a node in the RCU rbtree
	341	*
	342	* Returns 0 on success, or < 0 on error.
	343	*/
344	int rcu_rbtree_insert(struct rcu_rbtree_node **root,
345	struct rcu_rbtree_node *z,
346	rcu_rbtree_comp comp,
347	rcu_rbtree_alloc rballoc,
348	rcu_rbtree_free rbfree)
349	{
350	struct rcu_rbtree_node x, y;
351
db5b1669	352	y = &rcu_rbtree_nil;
00131368 MD	353	x = *root;
00131368 MD	354
db5b1669	355	while (x != &rcu_rbtree_nil) {
00131368 MD	356	y = x;
	357	if (comp(z->key, x->key) < 0)
	358	x = x->left;
	359	else
	360	x = x->right;
	361	}
	362
	363	z->p = y;
db5b1669 MD	364	z->left = &rcu_rbtree_nil;
db5b1669 MD	365	z->right = &rcu_rbtree_nil;
00131368 MD	366	z->color = COLOR_RED;
	367
	368	/*
	369	* Order stores to z (children/parents) before stores that will make it
	370	* visible to the rest of the tree.
	371	*/
	372	smp_wmb();
	373
db5b1669	374	if (y == &rcu_rbtree_nil)
00131368 MD	375	_STORE_SHARED(*root, z);
	376	else if (comp(z->key, y->key) < 0)
	377	_STORE_SHARED(y->left, z);
	378	else
	379	_STORE_SHARED(y->right, z);
	380	rcu_rbtree_insert_fixup(root, z, rballoc, rbfree);
	381	/*
	382	* Make sure to commit all _STORE_SHARED() for non-coherent caches.
	383	*/
	384	smp_wmc();
	385
	386	return 0;
	387	}
	388
	389	/*
	390	* Transplant v into u position.
	391	* Returns new copy of v.
	392	*/
	393	static struct rcu_rbtree_node *
	394	rcu_rbtree_transplant(struct rcu_rbtree_node **root,
	395	struct rcu_rbtree_node *u,
	396	struct rcu_rbtree_node *v,
	397	rcu_rbtree_alloc rballoc,
	398	rcu_rbtree_free rbfree)
	399	{
	400	struct rcu_rbtree_node *vc;
	401
	402	vc = rballoc();
	403	vc = v;
	404
	405	/* Change vc parent pointer */
	406	vc->p = u->p;
	407
	408	/*
	409	* Order stores to node copies (children/parents) before stores that
	410	* will make the copies visible to the rest of the tree.
	411	*/
	412	smp_wmb();
	413
	414	/* Assign upper-level pointer to vc, replacing u. */
db5b1669	415	if (u->p == &rcu_rbtree_nil)
00131368 MD	416	_STORE_SHARED(*root, vc);
	417	else if (u == u->p->left)
	418	_STORE_SHARED(u->p->left, vc);
	419	else
	420	_STORE_SHARED(u->p->right, vc);
	421
	422	/*
	423	* The children pointers in vc are the same as v. We can therefore
	424	* reparent v's children to vc safely.
	425	*/
	426	_STORE_SHARED(vc->right->p, vc);
	427	_STORE_SHARED(vc->left->p, vc);
	428
	429	defer_rcu(rbfree, v);
	430	return vc;
	431	}
	432
	433	static void rcu_rbtree_remove_fixup(struct rcu_rbtree_node **root,
	434	struct rcu_rbtree_node *x,
	435	rcu_rbtree_alloc rballoc,
	436	rcu_rbtree_free rbfree)
	437	{
	438	while (x != *root && x->color == COLOR_BLACK) {
	439	if (x == x->p->left) {
	440	struct rcu_rbtree_node *w;
	441
	442	w = x->p->right;
	443	if (w->color == COLOR_RED) {
	444	w->color == COLOR_BLACK;
	445	x->p->color = COLOR_RED;
	446	left_rotate(root, x->p, rballoc, rbfree);
	447	/* x is a left node, not copied by rotation */
	448	w = x->p->right;
	449	}
	450	if (w->left->color == COLOR_BLACK
	451	&& w->right->color == COLOR_BLACK) {
	452	w->color = COLOR_RED;
	453	x = x->p;
	454	} else {
	455	if (w->right->color == COLOR_BLACK) {
	456	w->left->color = COLOR_BLACK;
	457	w->color = COLOR_RED;
	458	right_rotate(root, w, rballoc, rbfree);
	459	w = x->p->right;
	460	}
	461	w->color = x->p->color;
	462	x->p->color = COLOR_BLACK;
	463	w->right->color = COLOR_BLACK;
	464	left_rotate(root, x->p, rballoc, rbfree);
	465	x = *root;
	466	}
	467	} else {
	468	struct rcu_rbtree_node *w;
	469
	470	w = x->p->left;
	471	if (w->color == COLOR_RED) {
	472	w->color == COLOR_BLACK;
	473	x->p->color = COLOR_RED;
	474	right_rotate(root, x->p, rballoc, rbfree);
	475	/* x is a right node, not copied by rotation */
	476	w = x->p->left;
	477	}
	478	if (w->right->color == COLOR_BLACK
	479	&& w->left->color == COLOR_BLACK) {
480	w->color = COLOR_RED;
481	x = x->p;
482	} else {
483	if (w->left->color == COLOR_BLACK) {
484	w->right->color = COLOR_BLACK;
485	w->color = COLOR_RED;
486	left_rotate(root, w, rballoc, rbfree);
487	w = x->p->left;
488	}
489	w->color = x->p->color;
490	x->p->color = COLOR_BLACK;
491	w->left->color = COLOR_BLACK;
492	right_rotate(root, x->p, rballoc, rbfree);
493	x = *root;
494	}
495	}
496	}
497	x->color = COLOR_BLACK;
498	}
499
500	/* Returns the new copy of y->right */
501	static struct rcu_rbtree_node *
502	rcu_rbtree_remove_nonil(struct rcu_rbtree_node **root,
503	struct rcu_rbtree_node *z,
504	struct rcu_rbtree_node *y,
505	rcu_rbtree_comp comp,
506	rcu_rbtree_alloc rballoc,
507	rcu_rbtree_free rbfree)
508	{
509	struct rcu_rbtree_node x, xc, *yc;
510
511	x = y->right;
512
513	xc = rballoc();
514	yc = rballoc();
515	xc = x;
516	yc = y;
517
518	/* Update parent and children pointers within copies */
519	if (y->p == z)
520	xc->p = yc;
521	else {
522	/* Transplant y->right (xc) into y, within copy */
523	xc->p = y->p;
524	/* But also change the right pointer of yc */
525	yc->right = z->right;
526	}
527	/* Transplant y into z, within copy */
528	yc->p = z->p;
529
530	yc->left = z->left;
531	yc->color = z->color;
532
533	/*
534	* Order stores to node copies (children/parents) before stores that
535	* will make the copies visible to the rest of the tree.
536	*/
537	smp_wmb();
538
539	/* Update external pointers */
540
541	if (y->p != z) {
542	/* Transplant y->right into y, external parent links */
543
544	/* Assign upper-level pointer to xc, replacing y. */
db5b1669	545	if (y->p == &rcu_rbtree_nil)
00131368 MD	546	_STORE_SHARED(*root, xc);
	547	else if (y == y->p->left)
	548	_STORE_SHARED(y->p->left, xc);
	549	else
	550	_STORE_SHARED(y->p->right, xc);
	551	}
	552
	553	/* Transplant y into z, update external parent links */
db5b1669	554	if (z->p == &rcu_rbtree_nil)
00131368 MD	555	_STORE_SHARED(*root, yc);
	556	else if (z == z->p->left)
	557	_STORE_SHARED(z->p->left, yc);
	558	else
	559	_STORE_SHARED(z->p->right, yc);
	560
	561	/* Reparent xc's children to xc. */
	562	_STORE_SHARED(xc->right->p, xc);
	563	_STORE_SHARED(xc->left->p, xc);
	564	/* Reparent yc's children to yc */
	565	_STORE_SHARED(yc->right->p, yc);
	566	_STORE_SHARED(yc->left->p, yc);
	567
	568	defer_rcu(rbfree, x);
	569	defer_rcu(rbfree, y);
	570
	571	return xc;
	572	}
	573
	574	int rcu_rbtree_remove(struct rcu_rbtree_node **root,
	575	struct rcu_rbtree_node *z,
	576	rcu_rbtree_comp comp,
	577	rcu_rbtree_alloc rballoc,
	578	rcu_rbtree_free rbfree)
	579	{
	580	struct rcu_rbtree_node x, y;
	581	unsigned int y_original_color;
	582
	583	y = z;
	584	y_original_color = y->color;
	585
db5b1669	586	if (z->left == &rcu_rbtree_nil) {
00131368	587	x = rcu_rbtree_transplant(root, z, z->right, rballoc, rbfree);
db5b1669	588	} else if (z->right == &rcu_rbtree_nil) {
00131368 MD	589	x = rcu_rbtree_transplant(root, z, z->left, rballoc, rbfree);
	590	} else {
	591	y = rcu_rbtree_min(z->right, comp);
	592	y_original_color = y->color;
	593	x = rcu_rbtree_remove_nonil(root, z, y, comp, rballoc, rbfree);
	594	}
	595	if (y_original_color == COLOR_BLACK)
	596	rcu_rbtree_remove_fixup(root, x, rballoc, rbfree);
	597	/*
	598	* Commit all _STORE_SHARED().
	599	*/
	600	smp_wmc();
	601
	602	return 0;
	603	}