#include <urcu-rbtree.h>
#include <urcu-pointer.h>
+#define DEBUG
+
+#ifdef DEBUG
+#define dbg_printf(args...) printf(args)
+#else
+#define dbg_printf(args...)
+#endif
+
/*
* TODO
* Deal with memory allocation errors.
* transplantations/rotations required for the operation.
*/
-/* Sentinel (bottom nodes). Don't care about p, left, right and key values */
+/* Sentinel (bottom nodes).
+ * Don't care about p, left, right, pos and key values */
struct rcu_rbtree_node rcu_rbtree_nil = {
.color = COLOR_BLACK,
};
return x;
}
+/*
+ * FIXME:
+ * Updates should wait for a grace period between update of the
+ * redirect pointer and update of the parent child pointer. This is to make sure
+ * that no reference to the old entry exist.
+ */
+
/*
* next and prev need to have mutex held to ensure that parent pointer is
* coherent.
struct rcu_rbtree_node *rcu_rbtree_next(struct rcu_rbtree_node *x,
rcu_rbtree_comp comp)
{
- struct rcu_rbtree_node *xr, *y, *yredir;
+ struct rcu_rbtree_node *xr, *y, *yr;
x = rcu_dereference(x);
if ((xr = rcu_dereference(x->right)) != &rcu_rbtree_nil)
return rcu_rbtree_min(xr, comp);
y = rcu_dereference(x->p);
- while ((yredir = rcu_dereference(y->redir)) != NULL)
- y = yredir;
- while (y != &rcu_rbtree_nil && x == rcu_dereference(y->right)) {
+ while (y != &rcu_rbtree_nil && x->pos == IS_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;
+ struct rcu_rbtree_node *xl, *y, *yl;
x = rcu_dereference(x);
if ((xl = rcu_dereference(x->left)) != &rcu_rbtree_nil)
- return rcu_rbtree_max(xl, comp);
+ return rcu_rbtree_min(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)) {
+ while (y != &rcu_rbtree_nil && x->pos == IS_LEFT) {
x = y;
y = rcu_dereference(y->p);
- while ((yredir = rcu_dereference(y->redir)) != NULL)
- y = yredir;
}
return y;
}
/* 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. */
+/* Returns the new x. Previous x->right references are changed to yc.
+ * Previous y->left->right is changed to bc. */
static struct rcu_rbtree_node *left_rotate(struct rcu_rbtree_node **root,
struct rcu_rbtree_node *x,
rcu_rbtree_alloc rballoc,
rcu_rbtree_free rbfree)
{
- struct rcu_rbtree_node *xc, *y, *yc;
+ struct rcu_rbtree_node *xc, *y, *yc, *b, *bc;
+
+ dbg_printf("left rotate %p\n", x->key);
y = x->right;
if (x != &rcu_rbtree_nil) {
xc = rballoc();
*xc = *x;
+ xc->pos = IS_LEFT;
}
if (y != &rcu_rbtree_nil) {
yc = rballoc();
*yc = *y;
+ yc->pos = x->pos;
+ b = y->left;
+ } else {
+ b = &rcu_rbtree_nil;
}
+ if (b != &rcu_rbtree_nil) {
+ /* Beta position changes from left to right. */
+ bc = rballoc();
+ *bc = *b;
+ assert(b->pos == IS_LEFT);
+ bc->pos = IS_RIGHT;
+ } else
+ bc = &rcu_rbtree_nil;
+
/* Modify children and parents in the node copies */
if (x != &rcu_rbtree_nil) {
- xc->right = y->left;
+ xc->right = bc;
xc->p = yc;
} else
xc = &rcu_rbtree_nil;
*/
smp_wmb();
- /*
- * redirect old nodes to new.
- */
- x->redir = xc;
- 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)
+ else if (x->pos == IS_LEFT)
_STORE_SHARED(x->p->left, yc);
else
_STORE_SHARED(x->p->right, yc);
/* Assign children parents to copies */
if (x != &rcu_rbtree_nil) {
- _STORE_SHARED(xc->right->p, xc);
- _STORE_SHARED(xc->left->p, xc);
+ _STORE_SHARED(xc->left->p, xc); /* alpha stays left */
defer_rcu(rbfree, x);
}
if (y != &rcu_rbtree_nil) {
- _STORE_SHARED(yc->right->p, yc);
+ _STORE_SHARED(yc->right->p, yc);/* gamma stays right */
defer_rcu(rbfree, y);
/* yc->left is xc, its parent is already set in node copy */
}
+ if (b != &rcu_rbtree_nil) {
+ _STORE_SHARED(bc->right->p, bc);
+ _STORE_SHARED(bc->left->p, bc);
+ defer_rcu(rbfree, b);
+ }
return xc;
}
/* 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. */
+/* Returns the new y. Previous y->left references are changed to xc.
+ * Previous y->left->right is changed to bc */
static struct rcu_rbtree_node *right_rotate(struct rcu_rbtree_node **root,
- struct rcu_rbtree_node *x,
+ struct rcu_rbtree_node *y,
rcu_rbtree_alloc rballoc,
rcu_rbtree_free rbfree)
{
- struct rcu_rbtree_node *xc, *y, *yc;
+ struct rcu_rbtree_node *x, *xc, *yc, *b, *bc;;
+
+ dbg_printf("right rotate %p\n", y->key);
- y = x->left;
+ x = y->left;
if (x != &rcu_rbtree_nil) {
xc = rballoc();
*xc = *x;
+ xc->pos = y->pos;
+ b = x->right;
+ } else {
+ b = &rcu_rbtree_nil;
}
if (y != &rcu_rbtree_nil) {
yc = rballoc();
*yc = *y;
+ yc->pos = IS_RIGHT;
}
+ if (b != &rcu_rbtree_nil) {
+ /* Beta position changes from right to left. */
+ bc = rballoc();
+ *bc = *b;
+ assert(b->pos == IS_RIGHT);
+ bc->pos = IS_LEFT;
+ } else
+ bc = &rcu_rbtree_nil;
+
/* Modify children and parents in the node copies */
if (x != &rcu_rbtree_nil) {
- xc->left = y->right;
- xc->p = yc;
+ xc->right = yc;
+ xc->p = y->p;
} else
xc = &rcu_rbtree_nil;
if (y != &rcu_rbtree_nil) {
- yc->right = xc;
- yc->p = x->p;
+ yc->left = bc;
+ yc->p = xc;
} else
yc = &rcu_rbtree_nil;
*/
smp_wmb();
- /*
- * redirect old nodes to new.
- */
- x->redir = xc;
- 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);
+ if (y->p == &rcu_rbtree_nil)
+ _STORE_SHARED(*root, xc);
+ else if (y->pos == IS_RIGHT)
+ _STORE_SHARED(y->p->right, xc);
else
- _STORE_SHARED(x->p->left, yc);
+ _STORE_SHARED(y->p->left, xc);
/* Assign children parents to copies */
if (x != &rcu_rbtree_nil) {
- _STORE_SHARED(xc->left->p, xc);
- _STORE_SHARED(xc->right->p, xc);
+ _STORE_SHARED(xc->left->p, xc); /* alpha stays left */
+ /* xc->right is yc, its parent is already set in node copy */
defer_rcu(rbfree, x);
}
if (y != &rcu_rbtree_nil) {
- _STORE_SHARED(yc->left->p, yc);
+ _STORE_SHARED(yc->right->p, yc);/* gamma stays right */
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;
+ if (b != &rcu_rbtree_nil) {
+ _STORE_SHARED(bc->right->p, bc);
+ _STORE_SHARED(bc->left->p, bc);
+ defer_rcu(rbfree, b);
+ }
+ return yc;
}
-#endif //0
static void rcu_rbtree_insert_fixup(struct rcu_rbtree_node **root,
struct rcu_rbtree_node *z,
{
struct rcu_rbtree_node *y;
+ dbg_printf("insert fixup %p\n", z->key);
+
while (z->p->color == COLOR_RED) {
if (z->p == z->p->p->left) {
y = z->p->p->right;
{
struct rcu_rbtree_node *x, *y;
+ dbg_printf("insert %p\n", z->key);
+
y = &rcu_rbtree_nil;
x = *root;
z->left = &rcu_rbtree_nil;
z->right = &rcu_rbtree_nil;
z->color = COLOR_RED;
- z->redir = NULL;
+
+ if (y == &rcu_rbtree_nil)
+ z->pos = IS_RIGHT; /* arbitrary for root node */
+ else if (comp(z->key, y->key) < 0)
+ z->pos = IS_LEFT;
+ else
+ z->pos = IS_RIGHT;
/*
* Order stores to z (children/parents) before stores that will make it
{
struct rcu_rbtree_node *vc;
+ dbg_printf("transplant %p\n", v->key);
+
if (v != &rcu_rbtree_nil) {
vc = rballoc();
*vc = *v;
/* Change vc parent pointer */
vc->p = u->p;
+ vc->pos = u->pos;
/*
* Order stores to node copies (children/parents) before stores
* that will make the copies visible to the rest of the tree.
*/
smp_wmb();
-
- /*
- * redirect old node to new.
- */
- v->redir = vc;
-
- /*
- * Ensure that redirections are visible before updating external
- * pointers.
- */
- smp_wmb();
} else {
vc = &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);
+ if (vc->right != &rcu_rbtree_nil)
+ _STORE_SHARED(vc->right->p, vc);
+ if (vc->left != &rcu_rbtree_nil)
+ _STORE_SHARED(vc->left->p, vc);
defer_rcu(rbfree, v);
}
rcu_rbtree_alloc rballoc,
rcu_rbtree_free rbfree)
{
+ dbg_printf("remove fixup %p\n", x->key);
+
while (x != *root && x->color == COLOR_BLACK) {
if (x == x->p->left) {
struct rcu_rbtree_node *w, *t;
w = x->p->right;
+ assert(w != &rcu_rbtree_nil);
+
if (w->color == COLOR_RED) {
w->color == COLOR_BLACK;
x->p->color = COLOR_RED;
x = *root;
}
} else {
- struct rcu_rbtree_node *w;
+ struct rcu_rbtree_node *w, *t;
w = x->p->left;
+ assert(w != &rcu_rbtree_nil);
+
if (w->color == COLOR_RED) {
w->color == COLOR_BLACK;
x->p->color = COLOR_RED;
- right_rotate(root, x->p, rballoc, rbfree);
+ t = right_rotate(root, x->p, rballoc, rbfree);
+ assert(x->p->right == t->right);
/* x is a right node, not copied by rotation */
w = x->p->left;
}
x->color = COLOR_BLACK;
}
-/* Returns the new copy of y->right */
+/*
+ * Returns the new copy of y->right.
+ * Delete z. All non-copied children left/right positions are unchanged. */
static struct rcu_rbtree_node *
rcu_rbtree_remove_nonil(struct rcu_rbtree_node **root,
struct rcu_rbtree_node *z,
{
struct rcu_rbtree_node *x, *xc, *yc;
+ dbg_printf("remove nonil %p\n", z->key);
+
x = y->right;
if (x != &rcu_rbtree_nil) {
*/
smp_wmb();
- /*
- * redirect old nodes to new.
- */
- if (x != &rcu_rbtree_nil)
- x->redir = xc;
- y->redir = yc;
-
- /*
- * Ensure that redirections are visible before updating external
- * pointers.
- */
- smp_wmb();
-
/* Update external pointers */
if (y->p != z) {
if (x != &rcu_rbtree_nil) {
/* Reparent xc's children to xc. */
_STORE_SHARED(xc->right->p, xc);
+ assert(yc->right == &rcu_rbtree_nil
+ || xc->right->pos == IS_RIGHT);
_STORE_SHARED(xc->left->p, xc);
+ assert(yc->right == &rcu_rbtree_nil
+ || xc->left->pos == IS_LEFT);
defer_rcu(rbfree, x);
}
/* Reparent yc's children to yc */
_STORE_SHARED(yc->right->p, yc);
+ assert(yc->right == &rcu_rbtree_nil || yc->right->pos == IS_RIGHT);
_STORE_SHARED(yc->left->p, yc);
+ assert(yc->right == &rcu_rbtree_nil || yc->left->pos == IS_LEFT);
defer_rcu(rbfree, y);
return xc;
struct rcu_rbtree_node *x, *y;
unsigned int y_original_color;
+ dbg_printf("remove %p\n", z->key);
+
y = z;
y_original_color = y->color;
projects / userspace-rcu.git / blobdiff