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

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

	x = rcu_dereference(x);

	if ((xr = rcu_dereference(x->right)) != &rcu_rbtree_nil)
		return rcu_rbtree_min(xr, comp);
	y = rcu_dereference(x->p);
	for (;;) {
		int found = 0;
		if (y == &rcu_rbtree_nil)
			break;
		yr = rcu_dereference(y->right);
		/* Find out if x is one of the parent right children versions */
		if (x == yr) {
			goto found;
		} else {
			while ((yrredir = rcu_dereference(yr->redir)) != NULL) {
				yr = yrredir;
				if (x == yr)
					goto found;
			}
			break;
		}
found:
		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, *yredir, *yl, *ylredir;

	x = rcu_dereference(x);

	if ((xl = rcu_dereference(x->left)) != &rcu_rbtree_nil)
		return rcu_rbtree_min(xl, comp);
	y = rcu_dereference(x->p);
	for (;;) {
		int found = 0;
		if (y == &rcu_rbtree_nil)
			break;
		yl = rcu_dereference(y->left);
		/* Find out if x is one of the parent left children versions */
		if (x == yl) {
			goto found;
		} else {
			while ((ylredir = rcu_dereference(yl->redir)) != NULL) {
				yl = ylredir;
				if (x == yl)
					goto found;
			}
			break;
		}
found:
		x = y;
		y = rcu_dereference(y->p);
	}
	return y;
}

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

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

	y = x->right;

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

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