[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 <assert.h>

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

#define DEBUG

#ifdef DEBUG
#define dbg_printf(args...)	printf(args)
#else
#define dbg_printf(args...)
#endif

/*
 * 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, pos 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 != &rcu_rbtree_nil && 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)) != &rcu_rbtree_nil)
		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)) != &rcu_rbtree_nil)
		x = xr;
	return x;
}

/*
 * FIXME:
 * Updates should wait for a grace period between update of the
 * redirect pointer and update of the parent child pointer. This is to make sure
 * that no reference to the old entry exist.
 */

/*
 * 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, *yr;

	x = rcu_dereference(x);

	if ((xr = rcu_dereference(x->right)) != &rcu_rbtree_nil)
		return rcu_rbtree_min(xr, comp);
	y = rcu_dereference(x->p);
	while (y != &rcu_rbtree_nil && x->pos == IS_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, *yl;

	x = rcu_dereference(x);

	if ((xl = rcu_dereference(x->left)) != &rcu_rbtree_nil)
		return rcu_rbtree_min(xl, comp);
	y = rcu_dereference(x->p);
	while (y != &rcu_rbtree_nil && x->pos == IS_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.
 * Previous y->left->right is changed to bc. */
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, *b, *bc;

	dbg_printf("left rotate %p\n", x->key);

	y = x->right;

	if (x != &rcu_rbtree_nil) {
		xc = rballoc();
		*xc = *x;
		xc->pos = IS_LEFT;
	}

	if (y != &rcu_rbtree_nil) {
		yc = rballoc();
		*yc = *y;
		yc->pos = x->pos;
		b = y->left;
	} else {
		b = &rcu_rbtree_nil;
	}

	if (b != &rcu_rbtree_nil) {
		/* Beta position changes from left to right. */
		bc = rballoc();
		*bc = *b;
		assert(b->pos == IS_LEFT);
		bc->pos = IS_RIGHT;
	} else
		bc = &rcu_rbtree_nil;

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

	if (y != &rcu_rbtree_nil) {
		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->pos == IS_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->left->p, xc);	/* alpha stays left */
		defer_rcu(rbfree, x);
	}
	if (y != &rcu_rbtree_nil) {
		_STORE_SHARED(yc->right->p, yc);/* gamma stays right */
		defer_rcu(rbfree, y);
		/* yc->left is xc, its parent is already set in node copy */
	}
	if (b != &rcu_rbtree_nil) {
		_STORE_SHARED(bc->right->p, bc);
		_STORE_SHARED(bc->left->p, bc);
		defer_rcu(rbfree, b);
	}
	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 y. Previous y->left references are changed to xc.
 * Previous y->left->right is changed to bc */
static struct rcu_rbtree_node *right_rotate(struct rcu_rbtree_node **root,
					    struct rcu_rbtree_node *y,
					    rcu_rbtree_alloc rballoc,
					    rcu_rbtree_free rbfree)
{
	struct rcu_rbtree_node *x, *xc, *yc, *b, *bc;;

	dbg_printf("right rotate %p\n", y->key);

	x = y->left;

	if (x != &rcu_rbtree_nil) {
		xc = rballoc();
		*xc = *x;
		xc->pos = y->pos;
		b = x->right;
	} else {
		b = &rcu_rbtree_nil;
	}

	if (y != &rcu_rbtree_nil) {
		yc = rballoc();
		*yc = *y;
		yc->pos = IS_RIGHT;
	}

	if (b != &rcu_rbtree_nil) {
		/* Beta position changes from right to left. */
		bc = rballoc();
		*bc = *b;
		assert(b->pos == IS_RIGHT);
		bc->pos = IS_LEFT;
	} else
		bc = &rcu_rbtree_nil;

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

	if (y != &rcu_rbtree_nil) {
		yc->left = bc;
		yc->p = xc;
	} 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 (y->p == &rcu_rbtree_nil)
		_STORE_SHARED(*root, xc);
	else if (y->pos == IS_RIGHT)
		_STORE_SHARED(y->p->right, xc);
	else
		_STORE_SHARED(y->p->left, xc);

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

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;

	dbg_printf("insert fixup %p\n", z->key);

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

	dbg_printf("insert %p\n", z->key);

	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;

	if (y == &rcu_rbtree_nil)
		z->pos = IS_RIGHT;	/* arbitrary for root node */
	else if (comp(z->key, y->key) < 0)
		z->pos = IS_LEFT;
	else
		z->pos = IS_RIGHT;

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

	dbg_printf("transplant %p\n", v->key);

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

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

		/*
		 * 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.
		 */
		if (vc->right != &rcu_rbtree_nil)
			_STORE_SHARED(vc->right->p, vc);
		if (vc->left != &rcu_rbtree_nil)
			_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)
{
	dbg_printf("remove fixup %p\n", x->key);

	while (x != *root && x->color == COLOR_BLACK) {
		if (x == x->p->left) {
			struct rcu_rbtree_node *w, *t;

			w = x->p->right;
			assert(w != &rcu_rbtree_nil);

			if (w->color == COLOR_RED) {
				w->color == COLOR_BLACK;
				x->p->color = COLOR_RED;
				t = left_rotate(root, x->p, rballoc, rbfree);
				assert(x->p->left == t->left);
				/* 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, *t;

			w = x->p->left;
			assert(w != &rcu_rbtree_nil);

			if (w->color == COLOR_RED) {
				w->color == COLOR_BLACK;
				x->p->color = COLOR_RED;
				t = right_rotate(root, x->p, rballoc, rbfree);
				assert(x->p->right == t->right);
				/* 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.
 * Delete z. All non-copied children left/right positions are unchanged. */
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;

	dbg_printf("remove nonil %p\n", z->key);

	x = y->right;

	if (x != &rcu_rbtree_nil) {
		xc = rballoc();
		*xc = *x;
	} else
		xc = &rcu_rbtree_nil;

	yc = rballoc();
	*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);

	if (x != &rcu_rbtree_nil) {
		/* Reparent xc's children to xc. */
		_STORE_SHARED(xc->right->p, xc);
		assert(yc->right == &rcu_rbtree_nil
		       || xc->right->pos == IS_RIGHT);
		_STORE_SHARED(xc->left->p, xc);
		assert(yc->right == &rcu_rbtree_nil
		       || xc->left->pos == IS_LEFT);
		defer_rcu(rbfree, x);
	}

	/* Reparent yc's children to yc */
	_STORE_SHARED(yc->right->p, yc);
	assert(yc->right == &rcu_rbtree_nil || yc->right->pos == IS_RIGHT);
	_STORE_SHARED(yc->left->p, yc);
	assert(yc->right == &rcu_rbtree_nil || yc->left->pos == IS_LEFT);
	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;

	dbg_printf("remove %p\n", z->key);

	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>
f6e888c5	35	#include <assert.h>
00131368 MD	36
	37	#include <urcu-rbtree.h>
	38	#include <urcu-pointer.h>
	39
ba16c81f MD	40	#define DEBUG
ba16c81f MD	41
a4f1873b MD	42	#ifdef DEBUG
	43	#define dbg_printf(args...) printf(args)
	44	#else
	45	#define dbg_printf(args...)
	46	#endif
	47
00131368 MD	48	/*
	49	* TODO
	50	* Deal with memory allocation errors.
	51	* Can be ensured by reserving a pool of memory entries before doing the
	52	* insertion, which will have to be function of number of
	53	* transplantations/rotations required for the operation.
	54	*/
	55
8c91bac8 MD	56	/* Sentinel (bottom nodes).
8c91bac8 MD	57	* Don't care about p, left, right, pos and key values */
db5b1669	58	struct rcu_rbtree_node rcu_rbtree_nil = {
00131368 MD	59	.color = COLOR_BLACK,
	60	};
	61
	62	/*
	63	* Iterative rbtree search.
	64	*/
	65	struct rcu_rbtree_node* rcu_rbtree_search(struct rcu_rbtree_node *x,
	66	void *k, rcu_rbtree_comp comp)
	67	{
	68	x = rcu_dereference(x);
	69
a23deda7	70	while (x != &rcu_rbtree_nil && k != x->key) {
00131368 MD	71	if (k < x->key)
	72	x = rcu_dereference(x->left);
	73	else
	74	x = rcu_dereference(x->right);
	75	}
	76	return x;
	77	}
	78
	79	struct rcu_rbtree_node rcu_rbtree_min(struct rcu_rbtree_node x,
	80	rcu_rbtree_comp comp)
	81	{
	82	struct rcu_rbtree_node *xl;
	83
	84	x = rcu_dereference(x);
	85
a23deda7	86	while ((xl = rcu_dereference(x->left)) != &rcu_rbtree_nil)
00131368 MD	87	x = xl;
	88	return x;
	89	}
	90
	91	struct rcu_rbtree_node rcu_rbtree_max(struct rcu_rbtree_node x,
	92	rcu_rbtree_comp comp)
	93	{
	94	struct rcu_rbtree_node *xr;
	95
	96	x = rcu_dereference(x);
	97
a23deda7	98	while ((xr = rcu_dereference(x->right)) != &rcu_rbtree_nil)
00131368 MD	99	x = xr;
	100	return x;
	101	}
	102
7ddb62c5 MD	103	/*
	104	* FIXME:
	105	* Updates should wait for a grace period between update of the
	106	* redirect pointer and update of the parent child pointer. This is to make sure
	107	* that no reference to the old entry exist.
	108	*/
	109
00131368 MD	110	/*
	111	* next and prev need to have mutex held to ensure that parent pointer is
	112	* coherent.
	113	*/
	114	struct rcu_rbtree_node rcu_rbtree_next(struct rcu_rbtree_node x,
	115	rcu_rbtree_comp comp)
	116	{
8c91bac8	117	struct rcu_rbtree_node xr, y, *yr;
00131368 MD	118
	119	x = rcu_dereference(x);
	120
a23deda7	121	if ((xr = rcu_dereference(x->right)) != &rcu_rbtree_nil)
00131368 MD	122	return rcu_rbtree_min(xr, comp);
00131368 MD	123	y = rcu_dereference(x->p);
8c91bac8	124	while (y != &rcu_rbtree_nil && x->pos == IS_RIGHT) {
00131368 MD	125	x = y;
	126	y = rcu_dereference(y->p);
	127	}
	128	return y;
	129	}
	130
	131	struct rcu_rbtree_node rcu_rbtree_prev(struct rcu_rbtree_node x,
	132	rcu_rbtree_comp comp)
	133	{
8c91bac8	134	struct rcu_rbtree_node xl, y, *yl;
00131368 MD	135
	136	x = rcu_dereference(x);
	137
a23deda7	138	if ((xl = rcu_dereference(x->left)) != &rcu_rbtree_nil)
9364f0c3	139	return rcu_rbtree_min(xl, comp);
00131368	140	y = rcu_dereference(x->p);
8c91bac8	141	while (y != &rcu_rbtree_nil && x->pos == IS_LEFT) {
00131368 MD	142	x = y;
	143	y = rcu_dereference(y->p);
	144	}
	145	return y;
	146	}
	147
	148	/*
	149	* We have to ensure these assumptions are correct for prev/next
	150	* traversal:
	151	*
	152	* with x being a right child, the assumption that:
	153	* x->p->right == x
	154	* or if x is a left child, the assumption that:
	155	* x->p->left == x
	156	*
	157	* This explains why we have to allocate a vc copy of the node for left_rotate,
	158	* right_rotate and transplant operations.
	159	*
	160	* We always ensure that the right/left child and correct parent is set in the
	161	* node copies before we reparent the children and make the upper-level point
	162	* to the copy.
	163	*/
	164
	165	/* RCU: copy x and y, atomically point to new versions. GC old. */
	166	/* Should be eventually followed by a smp_wmc() */
8c91bac8 MD	167	/* Returns the new x. Previous x->right references are changed to yc.
8c91bac8 MD	168	* Previous y->left->right is changed to bc. */
00131368 MD	169	static struct rcu_rbtree_node left_rotate(struct rcu_rbtree_node *root,
	170	struct rcu_rbtree_node *x,
	171	rcu_rbtree_alloc rballoc,
	172	rcu_rbtree_free rbfree)
	173	{
8c91bac8	174	struct rcu_rbtree_node xc, y, yc, b, *bc;
00131368	175
a4f1873b MD	176	dbg_printf("left rotate %p\n", x->key);
a4f1873b MD	177
00131368 MD	178	y = x->right;
00131368 MD	179
21cddea3 MD	180	if (x != &rcu_rbtree_nil) {
	181	xc = rballoc();
	182	xc = x;
8c91bac8	183	xc->pos = IS_LEFT;
a23deda7 MD	184	}
	185
	186	if (y != &rcu_rbtree_nil) {
	187	yc = rballoc();
	188	yc = y;
8c91bac8 MD	189	yc->pos = x->pos;
	190	b = y->left;
	191	} else {
	192	b = &rcu_rbtree_nil;
	193	}
	194
	195	if (b != &rcu_rbtree_nil) {
	196	/* Beta position changes from left to right. */
	197	bc = rballoc();
	198	bc = b;
	199	assert(b->pos == IS_LEFT);
	200	bc->pos = IS_RIGHT;
a4f1873b MD	201	} else
a4f1873b MD	202	bc = &rcu_rbtree_nil;
a23deda7 MD	203
	204	/* Modify children and parents in the node copies */
	205	if (x != &rcu_rbtree_nil) {
8c91bac8	206	xc->right = bc;
21cddea3 MD	207	xc->p = yc;
	208	} else
	209	xc = &rcu_rbtree_nil;
	210
	211	if (y != &rcu_rbtree_nil) {
21cddea3 MD	212	yc->left = xc;
	213	yc->p = x->p;
	214	} else
	215	yc = &rcu_rbtree_nil;
00131368 MD	216
	217	/*
	218	* Order stores to node copies (children/parents) before stores that
	219	* will make the copies visible to the rest of the tree.
	220	*/
	221	smp_wmb();
	222
	223	/* Make parents point to the copies */
db5b1669	224	if (x->p == &rcu_rbtree_nil)
00131368	225	_STORE_SHARED(*root, yc);
8c91bac8	226	else if (x->pos == IS_LEFT)
00131368 MD	227	_STORE_SHARED(x->p->left, yc);
	228	else
	229	_STORE_SHARED(x->p->right, yc);
	230
	231	/* Assign children parents to copies */
21cddea3	232	if (x != &rcu_rbtree_nil) {
8c91bac8	233	_STORE_SHARED(xc->left->p, xc); /* alpha stays left */
21cddea3 MD	234	defer_rcu(rbfree, x);
	235	}
	236	if (y != &rcu_rbtree_nil) {
8c91bac8	237	_STORE_SHARED(yc->right->p, yc);/* gamma stays right */
21cddea3 MD	238	defer_rcu(rbfree, y);
	239	/* yc->left is xc, its parent is already set in node copy */
	240	}
8c91bac8 MD	241	if (b != &rcu_rbtree_nil) {
	242	_STORE_SHARED(bc->right->p, bc);
	243	_STORE_SHARED(bc->left->p, bc);
	244	defer_rcu(rbfree, b);
	245	}
00131368 MD	246	return xc;
	247	}
	248
	249	#if 0 /* orig */
	250	static void left_rotate(struct rcu_rbtree_node **root,
	251	struct rcu_rbtree_node *x,
	252	rcu_rbtree_alloc rballoc)
	253	{
	254	struct rcu_rbtree_node *y;
	255
	256	y = x->right;
	257	x->right = y->left;
db5b1669	258	if (y->left != &rcu_rbtree_nil)
00131368 MD	259	y->left->p = x;
00131368 MD	260	y->p = x->p;
db5b1669	261	if (x->p == &rcu_rbtree_nil)
00131368 MD	262	*root = y;
	263	else if (x == x->p->left)
	264	x->p->left = y;
	265	else
	266	x->p->right = y;
	267	y->left = x;
	268	x->p = y;
	269	}
	270	#endif //0
	271
	272	/* RCU: copy x and y, atomically point to new versions. GC old. */
	273	/* Should be eventually followed by a smp_wmc() */
8c91bac8 MD	274	/* Returns the new y. Previous y->left references are changed to xc.
8c91bac8 MD	275	* Previous y->left->right is changed to bc */
00131368	276	static struct rcu_rbtree_node right_rotate(struct rcu_rbtree_node *root,
8c91bac8	277	struct rcu_rbtree_node *y,
00131368 MD	278	rcu_rbtree_alloc rballoc,
	279	rcu_rbtree_free rbfree)
	280	{
8c91bac8	281	struct rcu_rbtree_node x, xc, yc, b, *bc;;
00131368	282
a4f1873b MD	283	dbg_printf("right rotate %p\n", y->key);
a4f1873b MD	284
8c91bac8	285	x = y->left;
00131368	286
21cddea3 MD	287	if (x != &rcu_rbtree_nil) {
	288	xc = rballoc();
	289	xc = x;
8c91bac8 MD	290	xc->pos = y->pos;
	291	b = x->right;
	292	} else {
	293	b = &rcu_rbtree_nil;
a23deda7 MD	294	}
	295
	296	if (y != &rcu_rbtree_nil) {
	297	yc = rballoc();
	298	yc = y;
8c91bac8 MD	299	yc->pos = IS_RIGHT;
	300	}
	301
	302	if (b != &rcu_rbtree_nil) {
	303	/* Beta position changes from right to left. */
	304	bc = rballoc();
	305	bc = b;
	306	assert(b->pos == IS_RIGHT);
	307	bc->pos = IS_LEFT;
a4f1873b MD	308	} else
a4f1873b MD	309	bc = &rcu_rbtree_nil;
a23deda7 MD	310
	311	/* Modify children and parents in the node copies */
	312	if (x != &rcu_rbtree_nil) {
8c91bac8 MD	313	xc->right = yc;
8c91bac8 MD	314	xc->p = y->p;
21cddea3 MD	315	} else
	316	xc = &rcu_rbtree_nil;
	317
	318	if (y != &rcu_rbtree_nil) {
8c91bac8 MD	319	yc->left = bc;
8c91bac8 MD	320	yc->p = xc;
21cddea3 MD	321	} else
21cddea3 MD	322	yc = &rcu_rbtree_nil;
00131368 MD	323
	324	/*
	325	* Order stores to node copies (children/parents) before stores that
	326	* will make the copies visible to the rest of the tree.
	327	*/
	328	smp_wmb();
	329
	330	/* Make parents point to the copies */
8c91bac8 MD	331	if (y->p == &rcu_rbtree_nil)
	332	_STORE_SHARED(*root, xc);
	333	else if (y->pos == IS_RIGHT)
	334	_STORE_SHARED(y->p->right, xc);
00131368	335	else
8c91bac8	336	_STORE_SHARED(y->p->left, xc);
00131368 MD	337
00131368 MD	338	/* Assign children parents to copies */
21cddea3	339	if (x != &rcu_rbtree_nil) {
8c91bac8 MD	340	_STORE_SHARED(xc->left->p, xc); /* alpha stays left */
8c91bac8 MD	341	/* xc->right is yc, its parent is already set in node copy */
21cddea3 MD	342	defer_rcu(rbfree, x);
	343	}
	344	if (y != &rcu_rbtree_nil) {
8c91bac8	345	_STORE_SHARED(yc->right->p, yc);/* gamma stays right */
21cddea3	346	defer_rcu(rbfree, y);
21cddea3	347	}
8c91bac8 MD	348	if (b != &rcu_rbtree_nil) {
	349	_STORE_SHARED(bc->right->p, bc);
	350	_STORE_SHARED(bc->left->p, bc);
	351	defer_rcu(rbfree, b);
	352	}
	353	return yc;
00131368 MD	354	}
00131368 MD	355
00131368 MD	356	static void rcu_rbtree_insert_fixup(struct rcu_rbtree_node **root,
	357	struct rcu_rbtree_node *z,
	358	rcu_rbtree_alloc rballoc,
	359	rcu_rbtree_free rbfree)
	360	{
	361	struct rcu_rbtree_node *y;
	362
a4f1873b MD	363	dbg_printf("insert fixup %p\n", z->key);
a4f1873b MD	364
00131368 MD	365	while (z->p->color == COLOR_RED) {
	366	if (z->p == z->p->p->left) {
	367	y = z->p->p->right;
	368	if (y->color == COLOR_RED) {
	369	z->p->color = COLOR_BLACK;
	370	y->color = COLOR_BLACK;
	371	z->p->p->color = COLOR_RED;
	372	z = z->p->p;
	373	} else {
	374	if (z == z->p->right) {
	375	z = z->p;
	376	z = left_rotate(root, z,
	377	rballoc, rbfree);
	378	}
	379	z->p->color = COLOR_BLACK;
	380	z->p->p->color = COLOR_RED;
a23deda7	381	right_rotate(root, z->p->p, rballoc, rbfree);
00131368 MD	382	}
	383	} else {
	384	y = z->p->p->left;
	385	if (y->color == COLOR_RED) {
	386	z->p->color = COLOR_BLACK;
	387	y->color = COLOR_BLACK;
	388	z->p->p->color = COLOR_RED;
	389	z = z->p->p;
	390	} else {
	391	if (z == z->p->left) {
	392	z = z->p;
	393	z = right_rotate(root, z,
	394	rballoc, rbfree);
	395	}
	396	z->p->color = COLOR_BLACK;
	397	z->p->p->color = COLOR_RED;
a23deda7	398	left_rotate(root, z->p->p, rballoc, rbfree);
00131368 MD	399	}
	400	}
	401	}
	402	(*root)->color = COLOR_BLACK;
	403	}
	404
	405	/*
	406	* rcu_rbtree_insert - Insert a node in the RCU rbtree
	407	*
	408	* Returns 0 on success, or < 0 on error.
	409	*/
	410	int rcu_rbtree_insert(struct rcu_rbtree_node **root,
	411	struct rcu_rbtree_node *z,
	412	rcu_rbtree_comp comp,
	413	rcu_rbtree_alloc rballoc,
	414	rcu_rbtree_free rbfree)
	415	{
	416	struct rcu_rbtree_node x, y;
	417
a4f1873b MD	418	dbg_printf("insert %p\n", z->key);
a4f1873b MD	419
db5b1669	420	y = &rcu_rbtree_nil;
00131368 MD	421	x = *root;
00131368 MD	422
db5b1669	423	while (x != &rcu_rbtree_nil) {
00131368 MD	424	y = x;
	425	if (comp(z->key, x->key) < 0)
	426	x = x->left;
	427	else
	428	x = x->right;
	429	}
	430
	431	z->p = y;
db5b1669 MD	432	z->left = &rcu_rbtree_nil;
db5b1669 MD	433	z->right = &rcu_rbtree_nil;
00131368	434	z->color = COLOR_RED;
8c91bac8 MD	435
	436	if (y == &rcu_rbtree_nil)
	437	z->pos = IS_RIGHT; /* arbitrary for root node */
	438	else if (comp(z->key, y->key) < 0)
	439	z->pos = IS_LEFT;
	440	else
	441	z->pos = IS_RIGHT;
00131368 MD	442
	443	/*
	444	* Order stores to z (children/parents) before stores that will make it
	445	* visible to the rest of the tree.
	446	*/
	447	smp_wmb();
	448
db5b1669	449	if (y == &rcu_rbtree_nil)
00131368 MD	450	_STORE_SHARED(*root, z);
	451	else if (comp(z->key, y->key) < 0)
	452	_STORE_SHARED(y->left, z);
	453	else
	454	_STORE_SHARED(y->right, z);
	455	rcu_rbtree_insert_fixup(root, z, rballoc, rbfree);
	456	/*
	457	* Make sure to commit all _STORE_SHARED() for non-coherent caches.
	458	*/
	459	smp_wmc();
	460
	461	return 0;
	462	}
	463
	464	/*
	465	* Transplant v into u position.
	466	* Returns new copy of v.
	467	*/
	468	static struct rcu_rbtree_node *
	469	rcu_rbtree_transplant(struct rcu_rbtree_node **root,
	470	struct rcu_rbtree_node *u,
	471	struct rcu_rbtree_node *v,
	472	rcu_rbtree_alloc rballoc,
	473	rcu_rbtree_free rbfree)
	474	{
	475	struct rcu_rbtree_node *vc;
	476
a4f1873b MD	477	dbg_printf("transplant %p\n", v->key);
a4f1873b MD	478
21cddea3 MD	479	if (v != &rcu_rbtree_nil) {
	480	vc = rballoc();
	481	vc = v;
00131368	482
21cddea3 MD	483	/* Change vc parent pointer */
21cddea3 MD	484	vc->p = u->p;
8c91bac8	485	vc->pos = u->pos;
00131368	486
21cddea3 MD	487	/*
	488	* Order stores to node copies (children/parents) before stores
	489	* that will make the copies visible to the rest of the tree.
	490	*/
	491	smp_wmb();
	492	} else {
	493	vc = &rcu_rbtree_nil;
	494	}
00131368 MD	495
00131368 MD	496	/* Assign upper-level pointer to vc, replacing u. */
db5b1669	497	if (u->p == &rcu_rbtree_nil)
00131368 MD	498	_STORE_SHARED(*root, vc);
	499	else if (u == u->p->left)
	500	_STORE_SHARED(u->p->left, vc);
	501	else
	502	_STORE_SHARED(u->p->right, vc);
	503
21cddea3 MD	504	if (v != &rcu_rbtree_nil) {
	505	/*
	506	* The children pointers in vc are the same as v. We can
	507	* therefore reparent v's children to vc safely.
	508	*/
8c91bac8 MD	509	if (vc->right != &rcu_rbtree_nil)
	510	_STORE_SHARED(vc->right->p, vc);
	511	if (vc->left != &rcu_rbtree_nil)
	512	_STORE_SHARED(vc->left->p, vc);
00131368	513
21cddea3 MD	514	defer_rcu(rbfree, v);
21cddea3 MD	515	}
00131368 MD	516	return vc;
	517	}
	518
	519	static void rcu_rbtree_remove_fixup(struct rcu_rbtree_node **root,
	520	struct rcu_rbtree_node *x,
	521	rcu_rbtree_alloc rballoc,
	522	rcu_rbtree_free rbfree)
	523	{
a4f1873b MD	524	dbg_printf("remove fixup %p\n", x->key);
a4f1873b MD	525
00131368 MD	526	while (x != *root && x->color == COLOR_BLACK) {
00131368 MD	527	if (x == x->p->left) {
f6e888c5	528	struct rcu_rbtree_node w, t;
00131368 MD	529
00131368 MD	530	w = x->p->right;
ba16c81f MD	531	assert(w != &rcu_rbtree_nil);
ba16c81f MD	532
00131368 MD	533	if (w->color == COLOR_RED) {
	534	w->color == COLOR_BLACK;
	535	x->p->color = COLOR_RED;
f6e888c5 MD	536	t = left_rotate(root, x->p, rballoc, rbfree);
f6e888c5 MD	537	assert(x->p->left == t->left);
00131368 MD	538	/* x is a left node, not copied by rotation */
	539	w = x->p->right;
	540	}
	541	if (w->left->color == COLOR_BLACK
	542	&& w->right->color == COLOR_BLACK) {
	543	w->color = COLOR_RED;
	544	x = x->p;
	545	} else {
	546	if (w->right->color == COLOR_BLACK) {
	547	w->left->color = COLOR_BLACK;
	548	w->color = COLOR_RED;
	549	right_rotate(root, w, rballoc, rbfree);
	550	w = x->p->right;
	551	}
	552	w->color = x->p->color;
	553	x->p->color = COLOR_BLACK;
	554	w->right->color = COLOR_BLACK;
	555	left_rotate(root, x->p, rballoc, rbfree);
	556	x = *root;
	557	}
	558	} else {
8c91bac8	559	struct rcu_rbtree_node w, t;
00131368 MD	560
00131368 MD	561	w = x->p->left;
ba16c81f MD	562	assert(w != &rcu_rbtree_nil);
ba16c81f MD	563
00131368 MD	564	if (w->color == COLOR_RED) {
	565	w->color == COLOR_BLACK;
	566	x->p->color = COLOR_RED;
8c91bac8 MD	567	t = right_rotate(root, x->p, rballoc, rbfree);
8c91bac8 MD	568	assert(x->p->right == t->right);
00131368 MD	569	/* x is a right node, not copied by rotation */
	570	w = x->p->left;
	571	}
	572	if (w->right->color == COLOR_BLACK
	573	&& w->left->color == COLOR_BLACK) {
	574	w->color = COLOR_RED;
	575	x = x->p;
	576	} else {
	577	if (w->left->color == COLOR_BLACK) {
	578	w->right->color = COLOR_BLACK;
	579	w->color = COLOR_RED;
	580	left_rotate(root, w, rballoc, rbfree);
	581	w = x->p->left;
	582	}
	583	w->color = x->p->color;
	584	x->p->color = COLOR_BLACK;
	585	w->left->color = COLOR_BLACK;
	586	right_rotate(root, x->p, rballoc, rbfree);
	587	x = *root;
	588	}
	589	}
	590	}
	591	x->color = COLOR_BLACK;
	592	}
	593
8c91bac8 MD	594	/*
	595	* Returns the new copy of y->right.
	596	* Delete z. All non-copied children left/right positions are unchanged. */
00131368 MD	597	static struct rcu_rbtree_node *
	598	rcu_rbtree_remove_nonil(struct rcu_rbtree_node **root,
	599	struct rcu_rbtree_node *z,
	600	struct rcu_rbtree_node *y,
	601	rcu_rbtree_comp comp,
	602	rcu_rbtree_alloc rballoc,
	603	rcu_rbtree_free rbfree)
	604	{
	605	struct rcu_rbtree_node x, xc, *yc;
	606
a4f1873b MD	607	dbg_printf("remove nonil %p\n", z->key);
a4f1873b MD	608
00131368 MD	609	x = y->right;
00131368 MD	610
a23deda7 MD	611	if (x != &rcu_rbtree_nil) {
	612	xc = rballoc();
	613	xc = x;
	614	} else
	615	xc = &rcu_rbtree_nil;
	616
00131368	617	yc = rballoc();
00131368 MD	618	yc = y;
	619
	620	/* Update parent and children pointers within copies */
	621	if (y->p == z)
	622	xc->p = yc;
	623	else {
	624	/* Transplant y->right (xc) into y, within copy */
	625	xc->p = y->p;
	626	/* But also change the right pointer of yc */
	627	yc->right = z->right;
	628	}
	629	/* Transplant y into z, within copy */
	630	yc->p = z->p;
	631
	632	yc->left = z->left;
	633	yc->color = z->color;
	634
	635	/*
	636	* Order stores to node copies (children/parents) before stores that
	637	* will make the copies visible to the rest of the tree.
	638	*/
	639	smp_wmb();
	640
	641	/* Update external pointers */
	642
	643	if (y->p != z) {
	644	/* Transplant y->right into y, external parent links */
	645
	646	/* Assign upper-level pointer to xc, replacing y. */
db5b1669	647	if (y->p == &rcu_rbtree_nil)
00131368 MD	648	_STORE_SHARED(*root, xc);
	649	else if (y == y->p->left)
	650	_STORE_SHARED(y->p->left, xc);
	651	else
	652	_STORE_SHARED(y->p->right, xc);
	653	}
	654
	655	/* Transplant y into z, update external parent links */
db5b1669	656	if (z->p == &rcu_rbtree_nil)
00131368 MD	657	_STORE_SHARED(*root, yc);
	658	else if (z == z->p->left)
	659	_STORE_SHARED(z->p->left, yc);
	660	else
	661	_STORE_SHARED(z->p->right, yc);
	662
a23deda7 MD	663	if (x != &rcu_rbtree_nil) {
	664	/* Reparent xc's children to xc. */
	665	_STORE_SHARED(xc->right->p, xc);
8c91bac8 MD	666	assert(yc->right == &rcu_rbtree_nil
8c91bac8 MD	667	\|\| xc->right->pos == IS_RIGHT);
a23deda7	668	_STORE_SHARED(xc->left->p, xc);
8c91bac8 MD	669	assert(yc->right == &rcu_rbtree_nil
8c91bac8 MD	670	\|\| xc->left->pos == IS_LEFT);
a23deda7 MD	671	defer_rcu(rbfree, x);
	672	}
	673
00131368 MD	674	/* Reparent yc's children to yc */
00131368 MD	675	_STORE_SHARED(yc->right->p, yc);
8c91bac8	676	assert(yc->right == &rcu_rbtree_nil \|\| yc->right->pos == IS_RIGHT);
00131368	677	_STORE_SHARED(yc->left->p, yc);
8c91bac8	678	assert(yc->right == &rcu_rbtree_nil \|\| yc->left->pos == IS_LEFT);
00131368 MD	679	defer_rcu(rbfree, y);
	680
	681	return xc;
	682	}
	683
	684	int rcu_rbtree_remove(struct rcu_rbtree_node **root,
	685	struct rcu_rbtree_node *z,
	686	rcu_rbtree_comp comp,
	687	rcu_rbtree_alloc rballoc,
	688	rcu_rbtree_free rbfree)
	689	{
	690	struct rcu_rbtree_node x, y;
	691	unsigned int y_original_color;
	692
a4f1873b MD	693	dbg_printf("remove %p\n", z->key);
a4f1873b MD	694
00131368 MD	695	y = z;
	696	y_original_color = y->color;
	697
db5b1669	698	if (z->left == &rcu_rbtree_nil) {
00131368	699	x = rcu_rbtree_transplant(root, z, z->right, rballoc, rbfree);
db5b1669	700	} else if (z->right == &rcu_rbtree_nil) {
00131368 MD	701	x = rcu_rbtree_transplant(root, z, z->left, rballoc, rbfree);
	702	} else {
	703	y = rcu_rbtree_min(z->right, comp);
	704	y_original_color = y->color;
	705	x = rcu_rbtree_remove_nonil(root, z, y, comp, rballoc, rbfree);
	706	}
	707	if (y_original_color == COLOR_BLACK)
	708	rcu_rbtree_remove_fixup(root, x, rballoc, rbfree);
	709	/*
	710	* Commit all _STORE_SHARED().
	711	*/
	712	smp_wmc();
	713
	714	return 0;
	715	}