[urcu.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>

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

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

	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 ((yredir = rcu_dereference(y->redir)) != NULL)
		y = yredir;
	while (y != &rcu_rbtree_nil && x == rcu_dereference(y->right)) {
		x = y;
		y = rcu_dereference(y->p);
		while ((yredir = rcu_dereference(y->redir)) != NULL)
			y = yredir;
	}
	return y;
}

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

	x = rcu_dereference(x);

	if ((xl = rcu_dereference(x->left)) != &rcu_rbtree_nil)
		return rcu_rbtree_max(xl, comp);
	y = rcu_dereference(x->p);
	while ((yredir = rcu_dereference(y->redir)) != NULL)
		y = yredir;
	while (y != &rcu_rbtree_nil && x == rcu_dereference(y->left)) {
		x = y;
		y = rcu_dereference(y->p);
		while ((yredir = rcu_dereference(y->redir)) != NULL)
			y = yredir;
	}
	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;
	}

	if (y != &rcu_rbtree_nil) {
		yc = rballoc();
		*yc = *y;
	}

	/* Modify children and parents in the node copies */
	if (x != &rcu_rbtree_nil) {
		xc->right = y->left;
		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();

	/*
	 * redirect old nodes to new.
	 */
	_STORE_SHARED(x->redir, xc);
	_STORE_SHARED(y->redir, yc);

	/*
	 * Ensure that redirections are visible before updating external
	 * pointers.
	 */
	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;
	}

	if (y != &rcu_rbtree_nil) {
		yc = rballoc();
		*yc = *y;
	}

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

	if (y != &rcu_rbtree_nil) {
		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();

	/*
	 * redirect old nodes to new.
	 */
	_STORE_SHARED(x->redir, xc);
	_STORE_SHARED(y->redir, yc);

	/*
	 * Ensure that redirections are visible before updating external
	 * pointers.
	 */
	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;
				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;

	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;
	z->redir = NULL;

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

		/*
		 * redirect old node to new.
		 */
		_STORE_SHARED(v->redir, vc);

		/*
		 * Ensure that redirections are visible before updating external
		 * pointers.
		 */
		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, *t;

			w = x->p->right;
			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;

			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;

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

	/*
	 * redirect old nodes to new.
	 */
	if (x != &rcu_rbtree_nil)
		_STORE_SHARED(x->redir, xc);
	_STORE_SHARED(y->redir, yc);

	/*
	 * Ensure that redirections are visible before updating external
	 * pointers.
	 */
	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);
		_STORE_SHARED(xc->left->p, xc);
		defer_rcu(rbfree, x);
	}

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