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

#include <urcu/rcurbtree.h>
#include <urcu-pointer.h>
#include <urcu-call-rcu.h>

#define DEBUG

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

static
void set_decay(struct rcu_rbtree_node *x, struct rcu_rbtree_node *xc)
{
	x->decay_next = xc;
}

static
struct rcu_rbtree_node *get_decay(struct rcu_rbtree_node *x)
{
	while (x->decay_next)
		x = x->decay_next;
	return x;
}

static
struct rcu_rbtree_node *is_decay(struct rcu_rbtree_node *x)
{
	return x->decay_next;
}

static
struct rcu_rbtree_node *dup_decay_node(struct rcu_rbtree *rbtree,
				struct rcu_rbtree_node *x)
{
	struct rcu_rbtree_node *xc;

	if (rcu_rbtree_is_nil(x))
		return x;

	xc = rbtree->rballoc();
	memcpy(xc, x, sizeof(struct rcu_rbtree_node));
	xc->decay_next = NULL;
	set_decay(x, xc);
	call_rcu(&x->head, rbtree->rbfree);
	return xc;
}

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

static
void show_tree(struct rcu_rbtree *rbtree)
{
	struct rcu_rbtree_node *node;

	node = rcu_rbtree_min(rbtree, rbtree->root);
	while (!rcu_rbtree_is_nil(node)) {
		assert(!is_decay(node));
		printf("{ 0x%lX p:%lX r:%lX l:%lX %s %s %s} ",
			(unsigned long)node->key,
			(unsigned long) node->p->key,
			(unsigned long) node->right->key,
			(unsigned long) node->left->key,
			node->color ? "red" : "black",
			node->pos ? "right" : "left",
			node->nil ? "nil" : "");
		node = rcu_rbtree_next(rbtree, node);
	}
	printf("\n");
}

static
struct rcu_rbtree_node *make_nil(struct rcu_rbtree *rbtree)
{
	return &rbtree->nil_node;
}

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

	while (!rcu_rbtree_is_nil(x) && k != x->key) {
		if (rbtree->comp(k, x->key) < 0)
			x = rcu_dereference(x->left);
		else
			x = rcu_dereference(x->right);
	}
	return x;
}

struct rcu_rbtree_node *rcu_rbtree_min(struct rcu_rbtree *rbtree,
				       struct rcu_rbtree_node *x)
{
	struct rcu_rbtree_node *xl;

	x = rcu_dereference(x);

	if (rcu_rbtree_is_nil(x))
		return x;

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

struct rcu_rbtree_node *rcu_rbtree_max(struct rcu_rbtree *rbtree,
				       struct rcu_rbtree_node *x)
{
	struct rcu_rbtree_node *xr;

	x = rcu_dereference(x);

	if (rcu_rbtree_is_nil(x))
		return x;

	while (!rcu_rbtree_is_nil(xr = rcu_dereference(x->right)))
		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 *rbtree,
					struct rcu_rbtree_node *x)
{
	struct rcu_rbtree_node *xr, *y;

	x = rcu_dereference(x);

	if (!rcu_rbtree_is_nil(xr = rcu_dereference(x->right)))
		return rcu_rbtree_min(rbtree, xr);
	y = rcu_dereference(x->p);
	while (!rcu_rbtree_is_nil(y) && x->pos == IS_RIGHT) {
		x = y;
		y = rcu_dereference(y->p);
	}
	return y;
}

struct rcu_rbtree_node *rcu_rbtree_prev(struct rcu_rbtree *rbtree,
					struct rcu_rbtree_node *x)
{
	struct rcu_rbtree_node *xl, *y;

	x = rcu_dereference(x);

	if (!rcu_rbtree_is_nil(xl = rcu_dereference(x->left)))
		return rcu_rbtree_min(rbtree, xl);
	y = rcu_dereference(x->p);
	while (!rcu_rbtree_is_nil(y) && 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 cmm_smp_wmc() */

static
void left_rotate(struct rcu_rbtree *rbtree,
		 struct rcu_rbtree_node *x)
{
	struct rcu_rbtree_node *y, *y_left, *x_p;
	unsigned int x_pos;

	y = x->right;
	y_left = y->left;

	/* Now operate on new copy, decay old versions */
	x = dup_decay_node(rbtree, x);
	y = dup_decay_node(rbtree, y);
	y_left = dup_decay_node(rbtree, y_left);

	x_pos = x->pos;
	x_p = x->p;

	/* Internal node modifications */
	x->right = y_left;
	y->p = x->p;
	y->pos = x->pos;
	x->pos = IS_LEFT;
	y->left = x;
	x->p = y;
	if (!rcu_rbtree_is_nil(y_left)) {
		y_left->p = x;
		y_left->pos = IS_RIGHT;
	}

	cmm_smp_wmb();	/* write into node before publish */

	/* External references update (visible by readers) */
	if (rcu_rbtree_is_nil(x_p))
		_CMM_STORE_SHARED(rbtree->root, y);
	else if (x_pos == IS_LEFT)
		_CMM_STORE_SHARED(x_p->left, y);
	else
		_CMM_STORE_SHARED(x_p->right, y);

	/* Point children to new copy (parent only used by updates) */
	if (!rcu_rbtree_is_nil(x->left))
		x->left->p = x;
	if (!rcu_rbtree_is_nil(y->right))
		y->right->p = y;

	/* Sanity checks */
	assert(y == rbtree->root || y->p->left == y || y->p->right == y);
	assert(x == rbtree->root || x->p->left == x || x->p->right == x);
	assert(rcu_rbtree_is_nil(x->right) || x->right->p == x);
	assert(rcu_rbtree_is_nil(x->left) || x->left->p == x);
	assert(rcu_rbtree_is_nil(y->right) || y->right->p == y);
	assert(rcu_rbtree_is_nil(y->left) || y->left->p == y);
	assert(!is_decay(rbtree->root));
	assert(!is_decay(x));
	assert(!is_decay(y));
	assert(!is_decay(x->right));
	assert(!is_decay(x->left));
	assert(!is_decay(y->right));
	assert(!is_decay(y->left));
}

static
void right_rotate(struct rcu_rbtree *rbtree,
		  struct rcu_rbtree_node *x)
{
	struct rcu_rbtree_node *y, *y_right, *x_p;
	unsigned int x_pos;

	y = x->left;
	y_right = y->right;

	/* Now operate on new copy, decay old versions */
	x = dup_decay_node(rbtree, x);
	y = dup_decay_node(rbtree, y);
	y_right = dup_decay_node(rbtree, y_right);

	x_pos = x->pos;
	x_p = x->p;

	/* Internal node modifications */
	x->left = y_right;
	y->p = x->p;
	y->pos = x->pos;
	x->pos = IS_RIGHT;
	y->right = x;
	x->p = y;
	if (!rcu_rbtree_is_nil(y_right)) {
		y_right->p = x;
		y_right->pos = IS_LEFT;
	}

	cmm_smp_wmb();	/* write into node before publish */

	/* External references update (visible by readers) */
	if (rcu_rbtree_is_nil(x_p))
		_CMM_STORE_SHARED(rbtree->root, y);
	else if (x_pos == IS_RIGHT)
		_CMM_STORE_SHARED(x_p->right, y);
	else
		_CMM_STORE_SHARED(x_p->left, y);

	/* Point children to new copy (parent only used by updates) */
	if (!rcu_rbtree_is_nil(x->right))
		x->right->p = x;
	if (!rcu_rbtree_is_nil(y->left))
		y->left->p = y;

	/* Sanity checks */
	assert(y == rbtree->root || y->p->right == y || y->p->left == y);
	assert(x == rbtree->root || x->p->right == x || x->p->left == x);
	assert(rcu_rbtree_is_nil(x->left) || x->left->p == x);
	assert(rcu_rbtree_is_nil(x->right) || x->right->p == x);
	assert(rcu_rbtree_is_nil(y->left) || y->left->p == y);
	assert(rcu_rbtree_is_nil(y->right) || y->right->p == y);
	assert(!is_decay(rbtree->root));
	assert(!is_decay(x));
	assert(!is_decay(y));
	assert(!is_decay(x->left));
	assert(!is_decay(x->right));
	assert(!is_decay(y->left));
	assert(!is_decay(y->right));
}

static void rcu_rbtree_insert_fixup(struct rcu_rbtree *rbtree,
				    struct rcu_rbtree_node *z)
{
	struct rcu_rbtree_node *y;

	dbg_printf("insert fixup %p\n", z->key);
	assert(!is_decay(rbtree->root));

	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;
					left_rotate(rbtree, z);
					z = get_decay(z);
					assert(!is_decay(rbtree->root));
				}
				z->p->color = COLOR_BLACK;
				z->p->p->color = COLOR_RED;
				assert(!is_decay(z));
				assert(!is_decay(z->p));
				assert(!is_decay(z->p->p));
				right_rotate(rbtree, z->p->p);
				assert(!is_decay(z));
				assert(!is_decay(rbtree->root));
			}
		} 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;
					right_rotate(rbtree, z);
					z = get_decay(z);
					assert(!is_decay(rbtree->root));
				}
				z->p->color = COLOR_BLACK;
				z->p->p->color = COLOR_RED;
				left_rotate(rbtree, z->p->p);
				assert(!is_decay(z));
				assert(!is_decay(rbtree->root));
			}
		}
	}
	rbtree->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 *rbtree,
		      struct rcu_rbtree_node *z)
{
	struct rcu_rbtree_node *x, *y;

	dbg_printf("insert %p\n", z->key);
	assert(!is_decay(rbtree->root));

	y = make_nil(rbtree);
	if (!rbtree->root)
		rbtree->root = make_nil(rbtree);
	x = rbtree->root;
	while (!rcu_rbtree_is_nil(x)) {
		y = x;
		if (rbtree->comp(z->key, x->key) < 0)
			x = x->left;
		else
			x = x->right;
	}

	z->p = y;

	z->left = make_nil(rbtree);
	z->right = make_nil(rbtree);
	z->color = COLOR_RED;
	z->nil = 0;
	z->decay_next = NULL;

	if (rcu_rbtree_is_nil(y))
		z->pos = IS_RIGHT;	/* arbitrary for root node */
	else if (rbtree->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.
	 */
	cmm_smp_wmb();

	if (rcu_rbtree_is_nil(y))
		_CMM_STORE_SHARED(rbtree->root, z);
	else if (rbtree->comp(z->key, y->key) < 0)
		_CMM_STORE_SHARED(y->left, z);
	else
		_CMM_STORE_SHARED(y->right, z);
	rcu_rbtree_insert_fixup(rbtree, z);
	/*
	 * Make sure to commit all _CMM_STORE_SHARED() for non-coherent caches.
	 */
	cmm_smp_wmc();
	show_tree(rbtree);

	return 0;
}

/*
 * Transplant v into u position.
 */
static
void rcu_rbtree_transplant(struct rcu_rbtree *rbtree,
			struct rcu_rbtree_node *u,
			struct rcu_rbtree_node *v)
{
	dbg_printf("transplant %p\n", v->key);

	if (!rcu_rbtree_is_nil(v))
		v = dup_decay_node(rbtree, v);

	if (rcu_rbtree_is_nil(u->p)) {
		v->p = u->p;
		cmm_smp_wmb();	/* write into node before publish */
		_CMM_STORE_SHARED(rbtree->root, v);
	} else if (u == u->p->left) {
		v->pos = IS_LEFT;
		v->p = u->p;
		cmm_smp_wmb();	/* write into node before publish */
		_CMM_STORE_SHARED(u->p->left, v);
	} else {
		v->pos = IS_RIGHT;
		v->p = u->p;
		cmm_smp_wmb();	/* write into node before publish */
		_CMM_STORE_SHARED(u->p->right, v);
	}
	/* Set children parent to new node (only used by updates) */
	if (!rcu_rbtree_is_nil(v)) {
		v->right->p = v;
		v->left->p = v;
	}
	assert(!is_decay(rbtree->root));
}

static void rcu_rbtree_remove_fixup(struct rcu_rbtree *rbtree,
				    struct rcu_rbtree_node *x)
{
	dbg_printf("remove fixup %p\n", x->key);

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

			w = x->p->right;

			if (w->color == COLOR_RED) {
				w->color = COLOR_BLACK;
				x->p->color = COLOR_RED;
				left_rotate(rbtree, x->p);
				x = get_decay(x);
				assert(!is_decay(rbtree->root));
				w = x->p->right;
			}
			if (w->left->color == COLOR_BLACK
			    && w->right->color == COLOR_BLACK) {
				w->color = COLOR_RED;
				x = x->p;
				assert(!is_decay(rbtree->root));
				assert(!is_decay(x));
			} else {
				if (w->right->color == COLOR_BLACK) {
					w->left->color = COLOR_BLACK;
					w->color = COLOR_RED;
					right_rotate(rbtree, w);
					assert(!is_decay(rbtree->root));
					x = get_decay(x);
					w = x->p->right;
				}
				w->color = x->p->color;
				x->p->color = COLOR_BLACK;
				w->right->color = COLOR_BLACK;
				left_rotate(rbtree, x->p);
				assert(!is_decay(rbtree->root));
				x = rbtree->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(rbtree, x->p);
				assert(!is_decay(rbtree->root));
				x = get_decay(x);
				w = x->p->left;
			}
			if (w->right->color == COLOR_BLACK
			    && w->left->color == COLOR_BLACK) {
				w->color = COLOR_RED;
				x = x->p;
				assert(!is_decay(rbtree->root));
				assert(!is_decay(x));
			} else {
				if (w->left->color == COLOR_BLACK) {
					w->right->color = COLOR_BLACK;
					w->color = COLOR_RED;
					left_rotate(rbtree, w);
					assert(!is_decay(rbtree->root));
					x = get_decay(x);
					w = x->p->left;
				}
				w->color = x->p->color;
				x->p->color = COLOR_BLACK;
				w->left->color = COLOR_BLACK;
				right_rotate(rbtree, x->p);
				assert(!is_decay(rbtree->root));
				x = rbtree->root;
			}
		}
	}
	x->color = COLOR_BLACK;
}

/*
 * Delete z. All non-copied children left/right positions are unchanged.
 */
static
void rcu_rbtree_remove_nonil(struct rcu_rbtree *rbtree,
			     struct rcu_rbtree_node *z,
			     struct rcu_rbtree_node *y)
{
	struct rcu_rbtree_node *x;

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

	assert(!is_decay(z));
	assert(!is_decay(y));
	assert(!is_decay(y->right));
	assert(!is_decay(y->p));
	x = y->right;
	assert(!is_decay(x));
	if (y->p == z)
		x->p = y;
	else {
		rcu_rbtree_transplant(rbtree, y, y->right);
		assert(!is_decay(y));
		assert(!is_decay(z));
		assert(!is_decay(z->right));
		y->right = z->right;
		y->right->p = y;
	}
	rcu_rbtree_transplant(rbtree, z, y);
	y = get_decay(y);
	assert(!is_decay(z));
	assert(!is_decay(z->left));
	y->left = z->left;
	y->left->p = y;
	y->color = z->color;
}

int rcu_rbtree_remove(struct rcu_rbtree *rbtree,
		      struct rcu_rbtree_node *z)
{
	struct rcu_rbtree_node *x, *y;
	unsigned int y_original_color;

	assert(!is_decay(rbtree->root));
	dbg_printf("remove %p\n", z->key);
	show_tree(rbtree);

	assert(!is_decay(z));
	y = z;
	y_original_color = y->color;

	if (rcu_rbtree_is_nil(z->left)) {
		rcu_rbtree_transplant(rbtree, z, z->right);
		assert(!is_decay(z));
		x = get_decay(z->right);
		show_tree(rbtree);
	} else if (rcu_rbtree_is_nil(z->right)) {
		rcu_rbtree_transplant(rbtree, z, z->left);
		assert(!is_decay(z));
		x = get_decay(z->left);
		show_tree(rbtree);
	} else {
		y = rcu_rbtree_min(rbtree, z->right);
		assert(!is_decay(y));
		y_original_color = y->color;
		rcu_rbtree_remove_nonil(rbtree, z, y);
		x = get_decay(y->right);
		show_tree(rbtree);
	}
	if (y_original_color == COLOR_BLACK)
		rcu_rbtree_remove_fixup(rbtree, x);
	show_tree(rbtree);
	/*
	 * Commit all _CMM_STORE_SHARED().
	 */
	cmm_smp_wmc();

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