#include <assert.h>
#include <string.h>
#include <unistd.h>
+#include <errno.h>
#include <urcu/rcurbtree.h>
#include <urcu-pointer.h>
#include <urcu-call-rcu.h>
#include <urcu/compiler.h>
+/*
+ * Explanation of next/prev walk coherency and search coherency when
+ * performed concurrently with updates.
+ *
+ * next/prev walk coherency with respect to concurrent updates:
+ *
+ * There are 3 scenarios for which we need to model and validate this:
+ * rotation, transplant and "teleportation" (the latter being a remote
+ * transplant in a remove non-nil case).
+ *
+ * - rotation left (right is symmetric)
+ * xl and yr point to the same parent nodes before/after left
+ * rotation. yll and ylr also point to the same parent node
+ * before/after left rotation.
+ * As we are copying x, y and yl (the 3 nodes which parent/child
+ * relationship are changed) to "new" version of this node cluster,
+ * all external references to the cluster either point to the old
+ * cluster or the new one. If we take this cluster as a "black box"
+ * from the point of view of next/prev traversal, all we have to
+ * ensure is that the old and the new cluster behave in the exact same
+ * way with respect to traversal order.
+ *
+ * - transplant
+ * In this operation, we transplant a copy of "v" into its parent
+ * location (u), thus replacing it. The children of "v", vl and vr,
+ * still point to v (new version) after the transplant, so it does not
+ * change the behavior when considering the next/prev traversal. "v"
+ * being copied to a new version ensures that the parent pointers of v
+ * are pointing to its new parent (parent of u) before it is published
+ * to readers (by setting the child pointer of u's parent to the new
+ * copy of v).
+ *
+ * - teleportation
+ * This one is probably the most tricky and will require some ascii
+ * art to explain.
+ *
+ * We want to remove z from this tree:
+ *
+ * zp
+ * \
+ * z
+ * / \
+ * zl zr
+ * /
+ * a
+ * / \
+ * b ar
+ * / \
+ * y br
+ * \
+ * yr
+ * / \
+ * yrl yrr
+ *
+ * What we are going to do is to "teleport" y into z's location,
+ * reparenting yr to b. We are taking care to create a new cluster
+ * copy that is isolated from any reader. We will represent the new
+ * members of the cluster with capital letters.
+ *
+ * zp
+ * \
+ * Y
+ * / \
+ * zl ZR
+ * /
+ * A
+ * / \
+ * B ar
+ * / \
+ * YR br
+ * / \
+ * yrl yrr
+ *
+ * In this transient state, we notice that the pointers within the
+ * cluster all point to the new cluster nodes, and they point to the
+ * correct external nodes. However, no external pointer point to the
+ * cluster (yet). The first pointer to point to this cluster will be
+ * "zp->right". It will therefore make the cluster visible for search.
+ *
+ * In this intermediate state, we can walk through the new cluster
+ * when coming from the top (in a next/prev traversal), but can come
+ * back to the old cluster when going back up from the children nodes.
+ * All we have to ensure is that the two clusters, taken as a black
+ * box from a next/prev traversal perspective, yield to the exact same
+ * result.
+ *
+ * Search coherency with concurrent updates:
+ *
+ * Simple "search" (only going down the tree) is also handled by this
+ * cluster scheme. The explanation is a subset of the prev/next
+ * explanation, where we don't have to care about the intermediate
+ * stages where the children point to the old cluster, because we only
+ * ever use the top level pointers to go down into the children nodes,
+ * we never go back up. So by simply making sure that all the cluster
+ * internal nodes pointers are setup correctly before making the
+ * cluster visible to the readers (by setting the parent pointer to
+ * the topmost new node in the cluster), we are sure that readers will
+ * see a coherent view of the cluster at all times.
+ */
+
#ifdef DEBUG
#define dbg_printf(args...) printf(args)
+#define dbg_usleep(usecs) usleep(usecs)
#else
#define dbg_printf(args...)
+#define dbg_usleep(usecs)
#endif
/*
* Undefine this to enable the non-RCU rotate and transplant functions
- * (for debugging).
+ * (for debugging). Note that these versions don't support the tree
+ * max_end updates, so lookups must be performed with
+ * rcu_rbtree_search_begin_key when using this debug facility.
*/
#define RBTREE_RCU_SUPPORT_ROTATE_LEFT
#define RBTREE_RCU_SUPPORT_ROTATE_RIGHT
#define RBTREE_RCU_SUPPORT_TRANSPLANT
+#define RBTREE_RCU_SUPPORT
+
+#ifdef RBTREE_RCU_SUPPORT
+#define c_rcu_dereference(x) rcu_dereference(x)
+#define c_cmm_smp_wmb() cmm_smp_wmb()
+#define c_cmm_smp_wmc() cmm_smp_wmc()
+#define C_CMM_STORE_SHARED(x, v) CMM_STORE_SHARED(x, v)
+#define C__CMM_STORE_SHARED(x, v) _CMM_STORE_SHARED(x, v)
+#else
+#define c_rcu_dereference(x) (x)
+#define c_cmm_smp_wmb()
+#define c_cmm_smp_wmc()
+#define C_CMM_STORE_SHARED(x, v) ((x) = (v))
+#define C__CMM_STORE_SHARED(x, v) ((x) = (v))
+#endif
+
+/*
+ * Add internal mutex locking within the RBTree, for debugging. Enable this
+ * define and add mutexes to RCU readers to debug races with with rotation or
+ * transplant.
+ */
+/* #define RBTREE_INTERNAL_LOCKING */
-#ifdef EXTRA_DEBUG
+#ifdef RBTREE_INTERNAL_LOCKING
static pthread_mutex_t test_mutex = PTHREAD_MUTEX_INITIALIZER;
static pthread_mutex_t outer_mutex = PTHREAD_MUTEX_INITIALIZER;
{
pthread_mutex_unlock(&test_mutex);
}
+#else
+static
+void lock_outer_mutex(void)
+{
+}
+
+static
+void unlock_outer_mutex(void)
+{
+}
+
+static
+void lock_test_mutex(void)
+{
+}
+
+static
+void unlock_test_mutex(void)
+{
+}
#endif
static
struct rcu_rbtree_node *parent,
unsigned int pos)
{
- _CMM_STORE_SHARED(node->parent, ((unsigned long) parent) | pos);
+ C__CMM_STORE_SHARED(node->parent, ((unsigned long) parent) | pos);
}
static
struct rcu_rbtree_node *get_parent_and_pos(struct rcu_rbtree_node *node,
unsigned int *pos)
{
- unsigned long parent_pos = rcu_dereference(node->parent);
+ unsigned long parent_pos = c_rcu_dereference(node->parent);
*pos = (unsigned int) (parent_pos & 1UL);
return (struct rcu_rbtree_node *) (parent_pos & ~1UL);
return x->decay_next;
}
+static
+struct rcu_rbtree_node *_rcu_rbtree_alloc_node(struct rcu_rbtree *rbtree)
+{
+ return rbtree->rballoc(sizeof(struct rcu_rbtree_node));
+}
+
+static
+void _rcu_rbtree_free_node(struct rcu_head *head)
+{
+ struct rcu_rbtree_node *node =
+ caa_container_of(head, struct rcu_rbtree_node, head);
+ node->rbtree->rbfree(node);
+}
+
+#ifdef RBTREE_RCU_SUPPORT
+
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))
+ if (rcu_rbtree_is_nil(rbtree, x))
return x;
- xc = rbtree->rballoc();
- memcpy(xc, x, sizeof(struct rcu_rbtree_node));
+ xc = _rcu_rbtree_alloc_node(rbtree);
+ memcpy(xc, x, sizeof(*xc));
xc->decay_next = NULL;
set_decay(x, xc);
- call_rcu(&x->head, rbtree->rbfree);
+ rbtree->call_rcu(&x->head, _rcu_rbtree_free_node);
return xc;
}
+#else /* RBTREE_RCU_SUPPORT */
+
+static
+struct rcu_rbtree_node *dup_decay_node(struct rcu_rbtree *rbtree,
+ struct rcu_rbtree_node *x)
+{
+ return x;
+}
+
+#endif
+
/*
* Info for range lookups:
* Range lookup information is only valid when used when searching for
* children range.
*/
static
-void _set_left_dup_decay(struct rcu_rbtree *rbtree,
- struct rcu_rbtree_node *node,
- struct rcu_rbtree_node *left,
- struct rcu_rbtree_node **top,
- struct rcu_rbtree_node **top_child,
- unsigned int *top_child_pos, int copy)
+void set_left(struct rcu_rbtree *rbtree, struct rcu_rbtree_node *node,
+ struct rcu_rbtree_node *left)
{
- struct rcu_rbtree_node *first_node = node; /* already a copy */
-
node->_left = left;
- do {
- void *min_child_key;
-
- if (rcu_rbtree_is_nil(left)) {
- min_child_key = node->key;
- } else {
- min_child_key = left->min_child_key;
- assert(rbtree->comp(left->key, left->min_child_key) >= 0);
- assert(rbtree->comp(node->key, left->min_child_key) >= 0);
- }
- if (min_child_key != node->min_child_key) {
- if (node != first_node) {
- if (copy) {
- node = dup_decay_node(rbtree, node);
- node->_left = left;
- set_parent(left, node, IS_LEFT);
- }
- }
- node->min_child_key = min_child_key;
- } else {
- if (node != first_node) {
- if (top)
- *top = node;
- if (top_child)
- *top_child = left;
- if (top_child_pos)
- *top_child_pos = get_pos(left);
- } else {
- if (top)
- *top = get_parent(node);
- if (top_child)
- *top_child = node;
- if (top_child_pos)
- *top_child_pos = get_pos(node);
- }
- return;
- }
- left = node;
- } while (get_pos(node) == IS_LEFT
- && !rcu_rbtree_is_nil(node = get_parent(node)));
-
- if (rcu_rbtree_is_nil(node)) {
- if (top)
- *top = node;
- if (top_child)
- *top_child = left;
- if (top_child_pos)
- *top_child_pos = IS_LEFT; /* arbitrary */
- } else {
- assert(get_pos(node) == IS_RIGHT);
- if (top)
- *top = get_parent(node);
- if (top_child)
- *top_child = node;
- if (top_child_pos)
- *top_child_pos = IS_RIGHT;
- }
-}
-
-static
-void set_left_dup_decay(struct rcu_rbtree *rbtree,
- struct rcu_rbtree_node *node,
- struct rcu_rbtree_node *left,
- struct rcu_rbtree_node **top,
- struct rcu_rbtree_node **top_child,
- unsigned int *top_child_pos)
-{
- _set_left_dup_decay(rbtree, node, left, top, top_child,
- top_child_pos, 1);
-}
-
-static
-void set_left_update_decay(struct rcu_rbtree *rbtree, struct rcu_rbtree_node *node,
- struct rcu_rbtree_node *left)
-{
- struct rcu_rbtree_node *first_node = node; /* already a copy */
-
- do {
- if (node != first_node) {
- set_parent(node->_right,
- get_decay(get_parent(node->_right)), IS_RIGHT);
- }
- } while (get_pos(node) == IS_LEFT
- && !rcu_rbtree_is_nil(node = get_parent(node)));
}
static
-void set_right_dup_decay(struct rcu_rbtree *rbtree, struct rcu_rbtree_node *node,
- struct rcu_rbtree_node *right,
- struct rcu_rbtree_node **top,
- struct rcu_rbtree_node **top_child,
- unsigned int *top_child_pos)
+void set_right(struct rcu_rbtree *rbtree, struct rcu_rbtree_node *node,
+ struct rcu_rbtree_node *right)
{
- struct rcu_rbtree_node *first_node = node; /* already a copy */
-
node->_right = right;
- do {
- void *max_child_key;
-
- if (rcu_rbtree_is_nil(right)) {
- max_child_key = node->key;
- } else {
- max_child_key = right->max_child_key;
- assert(rbtree->comp(right->key, right->max_child_key) <= 0);
- assert(rbtree->comp(node->key, right->max_child_key) <= 0);
- }
- if (max_child_key != node->max_child_key) {
- if (node != first_node) {
- node = dup_decay_node(rbtree, node);
- node->_right = right;
- set_parent(right, node, IS_RIGHT);
- }
- node->max_child_key = max_child_key;
- } else {
- if (node != first_node) {
- if (top)
- *top = node;
- if (top_child)
- *top_child = right;
- if (top_child_pos)
- *top_child_pos = get_pos(right);
- } else {
- if (top)
- *top = get_parent(node);
- if (top_child)
- *top_child = node;
- if (top_child_pos)
- *top_child_pos = get_pos(node);
- }
- return;
- }
- right = node;
- } while (get_pos(node) == IS_RIGHT
- && !rcu_rbtree_is_nil(node = get_parent(node)));
-
- if (rcu_rbtree_is_nil(node)) {
- if (top)
- *top = node;
- if (top_child)
- *top_child = right;
- if (top_child_pos)
- *top_child_pos = IS_RIGHT; /* arbitrary */
- } else {
- assert(get_pos(node) == IS_LEFT);
- if (top)
- *top = get_parent(node);
- if (top_child)
- *top_child = node;
- if (top_child_pos)
- *top_child_pos = IS_LEFT;
- }
}
static
-void set_right_update_decay(struct rcu_rbtree *rbtree, struct rcu_rbtree_node *node,
- struct rcu_rbtree_node *right)
+void *calculate_node_max_end(struct rcu_rbtree *rbtree, struct rcu_rbtree_node *node)
{
- struct rcu_rbtree_node *first_node = node; /* already a copy */
+ void *max_end;
- do {
- if (node != first_node) {
- set_parent(node->_left,
- get_decay(get_parent(node->_left)), IS_LEFT);
- }
- } while (get_pos(node) == IS_RIGHT
- && !rcu_rbtree_is_nil(node = get_parent(node)));
+ max_end = node->end;
+ if (!rcu_rbtree_is_nil(rbtree, node->_right)) {
+ if (rbtree->comp(max_end, node->_right->max_end) < 0)
+ max_end = node->_right->max_end;
+ }
+ if (!rcu_rbtree_is_nil(rbtree, node->_left)) {
+ if (rbtree->comp(max_end, node->_left->max_end) < 0)
+ max_end = node->_left->max_end;
+ }
+ return max_end;
}
/*
* 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.
+ * transplantations/rotations required for the operation (which is a
+ * multiple of the tree height).
*/
#ifdef DEBUG
struct rcu_rbtree_node *node;
node = rcu_rbtree_min(rbtree, rbtree->root);
- while (!rcu_rbtree_is_nil(node)) {
+ while (!rcu_rbtree_is_nil(rbtree, node)) {
assert(!is_decay(node));
- printf("{ 0x%lX p:%lX r:%lX l:%lX %s %s %s} ",
- (unsigned long)node->key,
- (unsigned long) get_parent(node)->key,
- (unsigned long) node->_right->key,
- (unsigned long) node->_left->key,
+ printf("{ b:%lX e:%lX pb: %lX r:%lX l:%lX %s %s %s} ",
+ (unsigned long) node->begin,
+ (unsigned long) node->end,
+ (unsigned long) get_parent(node)->begin,
+ (unsigned long) node->_right->begin,
+ (unsigned long) node->_left->begin,
node->color ? "red" : "black",
get_pos(node) ? "right" : "left",
- node->nil ? "nil" : "");
+ rcu_rbtree_is_nil(rbtree, node) ? "nil" : "");
node = rcu_rbtree_next(rbtree, node);
}
printf("\n");
}
+
+#define check_max_end(rbtree, x) \
+ do { \
+ if (rcu_rbtree_is_nil(rbtree, x)) \
+ break; \
+ assert(rbtree->comp(x->max_end, \
+ calculate_node_max_end(rbtree, x)) == 0); \
+ } while (0)
+
#else /* DEBUG */
static
void show_tree(struct rcu_rbtree *rbtree)
{
}
+
+static
+void check_max_end(struct rcu_rbtree *rbtree, struct rcu_rbtree_node *x)
+{
+}
#endif /* DEBUG */
static
/*
* Iterative rbtree search.
*/
-struct rcu_rbtree_node* rcu_rbtree_search(struct rcu_rbtree *rbtree,
+struct rcu_rbtree_node *rcu_rbtree_search(struct rcu_rbtree *rbtree,
struct rcu_rbtree_node *x,
- void *k)
+ void *point)
{
- x = rcu_dereference(x);
- int comp;
-
- while (!rcu_rbtree_is_nil(x) && (comp = rbtree->comp(k, x->key)) != 0) {
- usleep(10);
- if (comp < 0)
- x = rcu_dereference(x->_left);
- else
- x = rcu_dereference(x->_right);
- }
- return x;
-}
+ struct rcu_rbtree_node *xl;
-struct rcu_rbtree_node* rcu_rbtree_search_min(struct rcu_rbtree *rbtree,
- struct rcu_rbtree_node *x,
- void *range_low, void *range_high)
-{
- x = rcu_dereference(x);
-
- while (!rcu_rbtree_is_nil(x)) {
- usleep(10);
- if (rbtree->comp(x->max_child_key, range_low) > 0) {
- x = rcu_dereference(x->_left);
- } else if (rbtree->comp(x->key, range_low) >= 0
- && rbtree->comp(x->key, range_high) <= 0) {
+ dbg_printf("searching point 0x%lx\n", (unsigned long) point);
+ x = c_rcu_dereference(x);
+
+ while (!rcu_rbtree_is_nil(rbtree, x)) {
+ dbg_usleep(10);
+ xl = c_rcu_dereference(x->_left);
+ dbg_printf("search x %lx x_end %lx x_max_end %lx\n", (unsigned long) x->begin,
+ (unsigned long) x->end, (unsigned long) x->max_end);
+ dbg_printf("search xl %lx xl_end %lx xl_max_end %lx\n", (unsigned long) xl->begin,
+ (unsigned long) xl->end, (unsigned long) xl->max_end);
+ if (!rcu_rbtree_is_nil(rbtree, xl)
+ && (rbtree->comp(xl->max_end, point) > 0)) {
+ dbg_printf("go left\n");
+ x = xl;
+ } else if (rbtree->comp(x->begin, point) <= 0
+ && rbtree->comp(point, x->end) < 0) {
+ dbg_printf("got it!\n");
break;
- } else if (rbtree->comp(range_low, x->min_child_key) > 0) {
- x = rcu_dereference(x->_right);
+ } else if (rbtree->comp(point, x->begin) > 0) {
+ dbg_printf("go right\n");
+ x = c_rcu_dereference(x->_right);
} else {
+ dbg_printf("not found!\n");
x = make_nil(rbtree);
}
}
+ if (rcu_rbtree_is_nil(rbtree, x))
+ dbg_printf("Reached bottom of tree.\n");
+
return x;
}
-struct rcu_rbtree_node* rcu_rbtree_search_max(struct rcu_rbtree *rbtree,
+struct rcu_rbtree_node *rcu_rbtree_search_range(struct rcu_rbtree *rbtree,
struct rcu_rbtree_node *x,
- void *range_low, void *range_high)
+ void *begin, void *end)
{
- x = rcu_dereference(x);
-
- while (!rcu_rbtree_is_nil(x)) {
- usleep(10);
- if (rbtree->comp(x->min_child_key, range_high) < 0) {
- x = rcu_dereference(x->_right);
- } else if (rbtree->comp(x->key, range_low) >= 0
- && rbtree->comp(x->key, range_high) <= 0) {
- break;
- } else if (rbtree->comp(range_high, x->max_child_key) < 0) {
- x = rcu_dereference(x->_left);
- } else {
- x = make_nil(rbtree);
- }
+ struct rcu_rbtree_node *node;
+
+ node = rcu_rbtree_search(rbtree, x, begin);
+ if (rcu_rbtree_is_nil(rbtree, node))
+ return node;
+ if (rbtree->comp(node->end, end) < 0)
+ return NULL; /* High is outside lookup range */
+ return node;
+}
+
+/*
+ * Search by exact range start value.
+ */
+struct rcu_rbtree_node *rcu_rbtree_search_begin_key(struct rcu_rbtree *rbtree,
+ struct rcu_rbtree_node *x,
+ void *k)
+{
+ x = c_rcu_dereference(x);
+ int comp;
+
+ while (!rcu_rbtree_is_nil(rbtree, x) && (comp = rbtree->comp(k, x->begin)) != 0) {
+ dbg_usleep(10);
+ if (comp < 0)
+ x = c_rcu_dereference(x->_left);
+ else
+ x = c_rcu_dereference(x->_right);
}
return x;
}
{
struct rcu_rbtree_node *xl;
- x = rcu_dereference(x);
+ x = c_rcu_dereference(x);
- if (rcu_rbtree_is_nil(x)) {
+ if (rcu_rbtree_is_nil(rbtree, x)) {
*zr = x;
return x;
} else
*zr = x = dup_decay_node(rbtree, x);
- while (!rcu_rbtree_is_nil(xl = rcu_dereference(x->_left))) {
+ while (!rcu_rbtree_is_nil(rbtree, xl = c_rcu_dereference(x->_left))) {
x = dup_decay_node(rbtree, xl);
set_parent(x, get_decay(get_parent(x)), get_pos(x));
get_parent(x)->_left = get_decay(get_parent(x)->_left);
{
struct rcu_rbtree_node *xl;
- x = rcu_dereference(x);
+ x = c_rcu_dereference(x);
- if (rcu_rbtree_is_nil(x))
+ if (rcu_rbtree_is_nil(rbtree, x))
return x;
else {
set_parent(x->_right, get_decay(get_parent(x->_right)),
get_pos(x->_left));
}
- while (!rcu_rbtree_is_nil(xl = rcu_dereference(x->_left))) {
+ while (!rcu_rbtree_is_nil(rbtree, xl = c_rcu_dereference(x->_left))) {
x = xl;
set_parent(x->_right, get_decay(get_parent(x->_right)),
get_pos(x->_right));
{
struct rcu_rbtree_node *xl;
- x = rcu_dereference(x);
+ x = c_rcu_dereference(x);
- if (rcu_rbtree_is_nil(x))
+ if (rcu_rbtree_is_nil(rbtree, x))
return x;
- while (!rcu_rbtree_is_nil(xl = rcu_dereference(x->_left)))
+ while (!rcu_rbtree_is_nil(rbtree, xl = c_rcu_dereference(x->_left)))
x = xl;
return x;
}
{
struct rcu_rbtree_node *xr;
- x = rcu_dereference(x);
+ x = c_rcu_dereference(x);
- if (rcu_rbtree_is_nil(x))
+ if (rcu_rbtree_is_nil(rbtree, x))
return x;
- while (!rcu_rbtree_is_nil(xr = rcu_dereference(x->_right)))
+ while (!rcu_rbtree_is_nil(rbtree, xr = c_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.
- */
-
/*
* RCU read lock must be held across the next/prev calls to ensure validity of
* the returned node.
struct rcu_rbtree_node *xr, *y;
unsigned int x_pos;
- x = rcu_dereference(x);
+ x = c_rcu_dereference(x);
- if (!rcu_rbtree_is_nil(xr = rcu_dereference(x->_right)))
+ if (!rcu_rbtree_is_nil(rbtree, xr = c_rcu_dereference(x->_right)))
return rcu_rbtree_min(rbtree, xr);
y = get_parent_and_pos(x, &x_pos);
- while (!rcu_rbtree_is_nil(y) && x_pos == IS_RIGHT) {
+ while (!rcu_rbtree_is_nil(rbtree, y) && x_pos == IS_RIGHT) {
x = y;
y = get_parent_and_pos(y, &x_pos);
}
struct rcu_rbtree_node *xl, *y;
unsigned int x_pos;
- x = rcu_dereference(x);
+ x = c_rcu_dereference(x);
- if (!rcu_rbtree_is_nil(xl = rcu_dereference(x->_left)))
+ if (!rcu_rbtree_is_nil(rbtree, xl = c_rcu_dereference(x->_left)))
return rcu_rbtree_max(rbtree, xl);
y = get_parent_and_pos(x, &x_pos);
- while (!rcu_rbtree_is_nil(y) && x_pos == IS_LEFT) {
+ while (!rcu_rbtree_is_nil(rbtree, y) && x_pos == IS_LEFT) {
x = y;
y = get_parent_and_pos(y, &x_pos);
}
return y;
}
+/*
+ * "node" needs to be non-visible by readers.
+ */
+static
+void populate_node_end(struct rcu_rbtree *rbtree, struct rcu_rbtree_node *node,
+ unsigned int copy_parents, struct rcu_rbtree_node *stop)
+{
+ struct rcu_rbtree_node *prev = NULL, *orig_node = node, *top;
+
+ do {
+ void *max_end;
+
+ assert(node);
+ assert(!rcu_rbtree_is_nil(rbtree, node));
+
+ if (prev && copy_parents) {
+ node = dup_decay_node(rbtree, node);
+ if (get_pos(prev) == IS_RIGHT)
+ node->_right = prev;
+ else
+ node->_left = prev;
+ set_parent(prev, node, get_pos(prev));
+ }
+
+ max_end = calculate_node_max_end(rbtree, node);
+ /*
+ * Compare the node max_end keys to make sure we replace
+ * references to a key belonging to a node we remove
+ * from the tree. Otherwise we would still be using this
+ * pointer as an invalid reference after garbage
+ * collection of the node and of its associated
+ * begin/end pointers.
+ */
+ if (max_end != node->max_end) {
+ node->max_end = max_end;
+ } else {
+ top = get_parent(node);
+ c_cmm_smp_wmb(); /* write into node before publish */
+ /* make new branch visible to readers */
+ if (rcu_rbtree_is_nil(rbtree, top))
+ C__CMM_STORE_SHARED(rbtree->root, node);
+ if (get_pos(node) == IS_LEFT)
+ C__CMM_STORE_SHARED(top->_left, node);
+ else
+ C__CMM_STORE_SHARED(top->_right, node);
+ goto end;
+ }
+
+ /* Check for propagation stop */
+ if (node == stop)
+ return;
+
+ prev = node;
+ node = get_parent(node);
+ } while (!rcu_rbtree_is_nil(rbtree, node));
+
+ top = node; /* nil */
+ c_cmm_smp_wmb(); /* write into node before publish */
+ /* make new branch visible to readers */
+ C__CMM_STORE_SHARED(rbtree->root, prev);
+
+end:
+ if (!copy_parents)
+ return;
+ /* update children */
+ node = orig_node;
+ do {
+ assert(!rcu_rbtree_is_nil(rbtree, node));
+ set_parent(node->_left, get_decay(get_parent(node->_left)), IS_LEFT);
+ set_parent(node->_right, get_decay(get_parent(node->_right)), IS_RIGHT);
+ } while ((node = get_parent(node)) != top);
+}
+
/*
* We have to ensure these assumptions are correct for prev/next
* traversal:
void left_rotate(struct rcu_rbtree *rbtree,
struct rcu_rbtree_node *x)
{
- struct rcu_rbtree_node *y, *y_left, *top, *top_child;
- unsigned int top_child_pos;
+ struct rcu_rbtree_node *y, *y_left;
+
+ dbg_printf("left rotate %lx\n", (unsigned long) x->begin);
y = x->_right;
y_left = y->_left;
y = dup_decay_node(rbtree, y);
y_left = dup_decay_node(rbtree, y_left);
+ check_max_end(rbtree, get_parent(x));
+ check_max_end(rbtree, x);
+ check_max_end(rbtree, y);
+
/* Internal node modifications */
set_parent(y, get_parent(x), get_pos(x));
set_parent(x, y, IS_LEFT);
- set_left_dup_decay(rbtree, y, x, &top, &top_child, &top_child_pos);
- set_right_dup_decay(rbtree, x, y_left, NULL, NULL, NULL);
- assert(!is_decay(top));
- assert(!is_decay(top_child));
+ set_left(rbtree, y, x);
+ set_right(rbtree, x, y_left);
- if (!rcu_rbtree_is_nil(y_left))
+ if (!rcu_rbtree_is_nil(rbtree, y_left))
set_parent(y_left, x, IS_RIGHT);
- cmm_smp_wmb(); /* write into node before publish */
+ /*
+ * We only changed the relative position of x and y wrt their
+ * children, and reparented y (but are keeping the same nodes in
+ * place, so its parent does not need to have end value
+ * recalculated).
+ */
+ x->max_end = calculate_node_max_end(rbtree, x);
+ y->max_end = calculate_node_max_end(rbtree, y);
+
+ c_cmm_smp_wmb(); /* write into node before publish */
/* External references update (visible by readers) */
- if (rcu_rbtree_is_nil(top))
- _CMM_STORE_SHARED(rbtree->root, top_child);
- else if (top_child_pos == IS_LEFT)
- _CMM_STORE_SHARED(top->_left, top_child);
+ if (rcu_rbtree_is_nil(rbtree, get_parent(y)))
+ C__CMM_STORE_SHARED(rbtree->root, y);
+ else if (get_pos(y) == IS_LEFT)
+ C__CMM_STORE_SHARED(get_parent(y)->_left, y);
else
- _CMM_STORE_SHARED(top->_right, top_child);
+ C__CMM_STORE_SHARED(get_parent(y)->_right, y);
/* Point children to new copy (parent only used by updates/next/prev) */
set_parent(x->_left, get_decay(get_parent(x->_left)),
get_pos(x->_left));
set_parent(y->_right, get_decay(get_parent(y->_right)),
get_pos(y->_right));
- if (!rcu_rbtree_is_nil(y_left)) {
+ if (!rcu_rbtree_is_nil(rbtree, y_left)) {
set_parent(y_left->_right,
get_decay(get_parent(y_left->_right)),
get_pos(y_left->_right));
get_decay(get_parent(y_left->_left)),
get_pos(y_left->_left));
}
- set_left_update_decay(rbtree, y, x);
/* Sanity checks */
assert(y == rbtree->root || get_parent(y)->_left == y
|| get_parent(y)->_right == y);
assert(x == rbtree->root || get_parent(x)->_left == x
|| get_parent(x)->_right == x);
- assert(rcu_rbtree_is_nil(x->_right) || get_parent(x->_right) == x);
- assert(rcu_rbtree_is_nil(x->_left) || get_parent(x->_left) == x);
- assert(rcu_rbtree_is_nil(y->_right) || get_parent(y->_right) == y);
- assert(rcu_rbtree_is_nil(y->_left) || get_parent(y->_left) == y);
+ assert(rcu_rbtree_is_nil(rbtree, x->_right) || get_parent(x->_right) == x);
+ assert(rcu_rbtree_is_nil(rbtree, x->_left) || get_parent(x->_left) == x);
+ assert(rcu_rbtree_is_nil(rbtree, y->_right) || get_parent(y->_right) == y);
+ assert(rcu_rbtree_is_nil(rbtree, y->_left) || get_parent(y->_left) == y);
assert(!is_decay(rbtree->root));
assert(!is_decay(x));
assert(!is_decay(y));
assert(!is_decay(x->_left));
assert(!is_decay(y->_right));
assert(!is_decay(y->_left));
+ check_max_end(rbtree, get_parent(y));
+ check_max_end(rbtree, x);
+ check_max_end(rbtree, y);
}
#else
lock_test_mutex();
y = x->_right;
x->_right = y->_left;
- if (!rcu_rbtree_is_nil(y->_left))
+ if (!rcu_rbtree_is_nil(rbtree, y->_left))
set_parent(y->_left, x, IS_RIGHT);
set_parent(y, get_parent(x), get_pos(x));
- if (rcu_rbtree_is_nil(get_parent(x)))
+ if (rcu_rbtree_is_nil(rbtree, get_parent(x)))
rbtree->root = y;
else if (x == get_parent(x)->_left) {
get_parent(x)->_left = y;
}
y->_left = x;
set_parent(x, y, IS_LEFT);
+
+ /*
+ * We only changed the relative position of x and y wrt their
+ * children, and reparented y (but are keeping the same nodes in
+ * place, so its parent does not need to have end value
+ * recalculated).
+ */
+ x->max_end = calculate_node_max_end(rbtree, x);
+ y->max_end = calculate_node_max_end(rbtree, y);
+
unlock_test_mutex();
}
void right_rotate(struct rcu_rbtree *rbtree,
struct rcu_rbtree_node *x)
{
- struct rcu_rbtree_node *y, *y_right, *top, *top_child;
- unsigned int top_child_pos;
+ struct rcu_rbtree_node *y, *y_right;
+
+ dbg_printf("right rotate %lx\n", (unsigned long) x->begin);
y = x->_left;
y_right = y->_right;
y = dup_decay_node(rbtree, y);
y_right = dup_decay_node(rbtree, y_right);
+ check_max_end(rbtree, get_parent(x));
+ check_max_end(rbtree, x);
+ check_max_end(rbtree, y);
+
/* Internal node modifications */
set_parent(y, get_parent(x), get_pos(x));
set_parent(x, y, IS_RIGHT);
- set_right_dup_decay(rbtree, y, x, &top, &top_child, &top_child_pos);
- set_left_dup_decay(rbtree, x, y_right, NULL, NULL, NULL);
- assert(!is_decay(top));
- assert(!is_decay(top_child));
+ set_right(rbtree, y, x);
+ set_left(rbtree, x, y_right);
- if (!rcu_rbtree_is_nil(y_right))
+ if (!rcu_rbtree_is_nil(rbtree, y_right))
set_parent(y_right, x, IS_LEFT);
- cmm_smp_wmb(); /* write into node before publish */
+ /*
+ * We only changed the relative position of x and y wrt their
+ * children, and reparented y (but are keeping the same nodes in
+ * place, so its parent does not need to have end value
+ * recalculated).
+ */
+ x->max_end = calculate_node_max_end(rbtree, x);
+ y->max_end = calculate_node_max_end(rbtree, y);
+
+ c_cmm_smp_wmb(); /* write into node before publish */
/* External references update (visible by readers) */
- if (rcu_rbtree_is_nil(top))
- _CMM_STORE_SHARED(rbtree->root, top_child);
- else if (top_child_pos == IS_RIGHT)
- _CMM_STORE_SHARED(top->_right, top_child);
+ if (rcu_rbtree_is_nil(rbtree, get_parent(y)))
+ C__CMM_STORE_SHARED(rbtree->root, y);
+ else if (get_pos(y) == IS_RIGHT)
+ C__CMM_STORE_SHARED(get_parent(y)->_right, y);
else
- _CMM_STORE_SHARED(top->_left, top_child);
+ C__CMM_STORE_SHARED(get_parent(y)->_left, y);
/* Point children to new copy (parent only used by updates/next/prev) */
set_parent(x->_right, get_decay(get_parent(x->_right)),
get_pos(x->_right));
set_parent(y->_left, get_decay(get_parent(y->_left)),
get_pos(y->_left));
- if (!rcu_rbtree_is_nil(y_right)) {
+ if (!rcu_rbtree_is_nil(rbtree, y_right)) {
set_parent(y_right->_left,
get_decay(get_parent(y_right->_left)),
get_pos(y_right->_left));
get_decay(get_parent(y_right->_right)),
get_pos(y_right->_right));
}
- set_right_update_decay(rbtree, y, x);
-
/* Sanity checks */
assert(y == rbtree->root || get_parent(y)->_right == y
|| get_parent(y)->_left == y);
assert(x == rbtree->root || get_parent(x)->_right == x
|| get_parent(x)->_left == x);
- assert(rcu_rbtree_is_nil(x->_left) || get_parent(x->_left) == x);
- assert(rcu_rbtree_is_nil(x->_right) || get_parent(x->_right) == x);
- assert(rcu_rbtree_is_nil(y->_left) || get_parent(y->_left) == y);
- assert(rcu_rbtree_is_nil(y->_right) || get_parent(y->_right) == y);
+ assert(rcu_rbtree_is_nil(rbtree, x->_left) || get_parent(x->_left) == x);
+ assert(rcu_rbtree_is_nil(rbtree, x->_right) || get_parent(x->_right) == x);
+ assert(rcu_rbtree_is_nil(rbtree, y->_left) || get_parent(y->_left) == y);
+ assert(rcu_rbtree_is_nil(rbtree, y->_right) || get_parent(y->_right) == y);
assert(!is_decay(rbtree->root));
assert(!is_decay(x));
assert(!is_decay(y));
assert(!is_decay(x->_right));
assert(!is_decay(y->_left));
assert(!is_decay(y->_right));
+ check_max_end(rbtree, x);
+ check_max_end(rbtree, y);
+ check_max_end(rbtree, get_parent(y));
}
#else
lock_test_mutex();
y = x->_left;
x->_left = y->_right;
- if (!rcu_rbtree_is_nil(y->_right))
+ if (!rcu_rbtree_is_nil(rbtree, y->_right))
set_parent(y->_right, x, IS_LEFT);
set_parent(y, get_parent(x), get_pos(x));
- if (rcu_rbtree_is_nil(get_parent(x)))
+ if (rcu_rbtree_is_nil(rbtree, get_parent(x)))
rbtree->root = y;
else if (x == get_parent(x)->_right) {
get_parent(x)->_right = y;
}
y->_right = x;
set_parent(x, y, IS_RIGHT);
+
+ /*
+ * We only changed the relative position of x and y wrt their
+ * children, and reparented y (but are keeping the same nodes in
+ * place, so its parent does not need to have end value
+ * recalculated).
+ */
+ x->max_end = calculate_node_max_end(rbtree, x);
+ y->max_end = calculate_node_max_end(rbtree, y);
+
unlock_test_mutex();
}
{
struct rcu_rbtree_node *y;
- dbg_printf("insert fixup %p\n", z->key);
+ dbg_printf("insert fixup %p\n", z->begin);
assert(!is_decay(rbtree->root));
while (get_parent(z)->color == COLOR_RED) {
* Returns 0 on success, or < 0 on error.
*/
int rcu_rbtree_insert(struct rcu_rbtree *rbtree,
- struct rcu_rbtree_node *z)
+ void *begin, void *end)
{
- struct rcu_rbtree_node *x, *y, *top, *top_child;
- unsigned int top_child_pos;
+ struct rcu_rbtree_node *x, *y, *z;
+
+ z = _rcu_rbtree_alloc_node(rbtree);
+ if (!z)
+ return -ENOMEM;
+ z->begin = begin;
+ z->end = end;
- dbg_printf("insert %p\n", z->key);
+ dbg_printf("insert %p\n", z->begin);
assert(!is_decay(rbtree->root));
y = make_nil(rbtree);
x = rbtree->root;
- while (!rcu_rbtree_is_nil(x)) {
+ while (!rcu_rbtree_is_nil(rbtree, x)) {
y = x;
- if (rbtree->comp(z->key, x->key) < 0)
+ if (rbtree->comp(z->begin, x->begin) < 0)
x = x->_left;
else
x = x->_right;
z->_left = make_nil(rbtree);
z->_right = make_nil(rbtree);
- z->min_child_key = z->key;
- z->max_child_key = z->key;
z->color = COLOR_RED;
- z->nil = 0;
z->decay_next = NULL;
+ z->max_end = z->end;
+ z->rbtree = rbtree;
- if (rcu_rbtree_is_nil(y))
+ if (rcu_rbtree_is_nil(rbtree, y)) {
set_parent(z, y, IS_RIGHT); /* pos arbitrary for root node */
- else if (rbtree->comp(z->key, y->key) < 0)
+ /*
+ * Order stores to z (children/parents) before stores
+ * that will make it visible to the rest of the tree.
+ */
+ c_cmm_smp_wmb();
+ C__CMM_STORE_SHARED(rbtree->root, z);
+ } else if (rbtree->comp(z->begin, y->begin) < 0) {
+ y = dup_decay_node(rbtree, y);
set_parent(z, y, IS_LEFT);
- else
- set_parent(z, y, 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) {
- set_left_dup_decay(rbtree, y, z, &top, &top_child,
- &top_child_pos);
- if (rcu_rbtree_is_nil(top))
- _CMM_STORE_SHARED(rbtree->root, top_child);
- else if (top_child_pos == IS_LEFT)
- _CMM_STORE_SHARED(top->_left, top_child);
+ if (get_pos(z) == IS_LEFT)
+ C__CMM_STORE_SHARED(y->_left, z);
else
- _CMM_STORE_SHARED(top->_right, top_child);
- set_left_update_decay(rbtree, y, z);
+ C__CMM_STORE_SHARED(y->_right, z);
+ populate_node_end(rbtree, y, 1, NULL);
} else {
- set_right_dup_decay(rbtree, y, z, &top, &top_child,
- &top_child_pos);
- if (rcu_rbtree_is_nil(top))
- _CMM_STORE_SHARED(rbtree->root, top_child);
- else if (top_child_pos == IS_LEFT)
- _CMM_STORE_SHARED(top->_left, top_child);
+ y = dup_decay_node(rbtree, y);
+ set_parent(z, y, IS_RIGHT);
+ if (get_pos(z) == IS_LEFT)
+ C__CMM_STORE_SHARED(y->_left, z);
else
- _CMM_STORE_SHARED(top->_right, top_child);
- set_right_update_decay(rbtree, y, z);
+ C__CMM_STORE_SHARED(y->_right, z);
+ populate_node_end(rbtree, y, 1, NULL);
}
rcu_rbtree_insert_fixup(rbtree, z);
/*
- * Make sure to commit all _CMM_STORE_SHARED() for non-coherent caches.
+ * Make sure to commit all C__CMM_STORE_SHARED() for non-coherent caches.
*/
- cmm_smp_wmc();
+ c_cmm_smp_wmc();
show_tree(rbtree);
+ check_max_end(rbtree, z);
+ check_max_end(rbtree, y);
return 0;
}
void rcu_rbtree_transplant(struct rcu_rbtree *rbtree,
struct rcu_rbtree_node *u,
struct rcu_rbtree_node *v,
- unsigned int copy_parents)
+ unsigned int copy_parents,
+ struct rcu_rbtree_node *stop)
{
- struct rcu_rbtree_node *top, *top_child;
- unsigned int top_child_pos;
+ dbg_printf("transplant %p\n", v->begin);
- dbg_printf("transplant %p\n", v->key);
-
- if (!rcu_rbtree_is_nil(v))
+ if (!rcu_rbtree_is_nil(rbtree, v))
v = dup_decay_node(rbtree, v);
- if (rcu_rbtree_is_nil(get_parent(u))) {
+ if (rcu_rbtree_is_nil(rbtree, get_parent(u))) {
/* pos is arbitrary for root node */
set_parent(v, get_parent(u), IS_RIGHT);
- cmm_smp_wmb(); /* write into node before publish */
- _CMM_STORE_SHARED(rbtree->root, v);
+ c_cmm_smp_wmb(); /* write into node before publish */
+ C__CMM_STORE_SHARED(rbtree->root, v);
} else {
- set_parent(v, get_parent(u), get_pos(u));
- cmm_smp_wmb(); /* write into node before publish */
-
- if (get_pos(u) == IS_LEFT) {
- _set_left_dup_decay(rbtree, get_parent(u), v,
- &top, &top_child, &top_child_pos,
- copy_parents);
- } else {
- assert(copy_parents);
- set_right_dup_decay(rbtree, get_parent(u), v,
- &top, &top_child, &top_child_pos);
- }
-
- if (rcu_rbtree_is_nil(top))
- _CMM_STORE_SHARED(rbtree->root, top_child);
- else if (top_child_pos == IS_LEFT)
- _CMM_STORE_SHARED(top->_left, top_child);
+ struct rcu_rbtree_node *vp;
+
+ vp = get_parent(u);
+ if (copy_parents)
+ vp = dup_decay_node(rbtree, vp);
+ set_parent(v, vp, get_pos(u));
+ if (get_pos(v) == IS_LEFT)
+ C__CMM_STORE_SHARED(vp->_left, v);
else
- _CMM_STORE_SHARED(top->_right, top_child);
-
- /* Point children to new copy (parent only used by updates/next/prev) */
- if (get_pos(u) == IS_LEFT) {
- if (copy_parents)
- set_left_update_decay(rbtree, get_parent(u), v);
- } else {
- assert(copy_parents);
- set_right_update_decay(rbtree, get_parent(u), v);
- }
+ C__CMM_STORE_SHARED(vp->_right, v);
+ populate_node_end(rbtree, vp, copy_parents, stop);
+ check_max_end(rbtree, vp);
}
/* Point children to new copy (parent only used by updates/next/prev) */
- if (!rcu_rbtree_is_nil(v)) {
+ if (!rcu_rbtree_is_nil(rbtree, v)) {
set_parent(v->_right, get_decay(get_parent(v->_right)),
get_pos(v->_right));
set_parent(v->_left, get_decay(get_parent(v->_left)),
get_pos(v->_left));
}
assert(!is_decay(rbtree->root));
+ check_max_end(rbtree, v);
}
#else
void rcu_rbtree_transplant(struct rcu_rbtree *rbtree,
struct rcu_rbtree_node *u,
struct rcu_rbtree_node *v,
- unsigned int copy_parents)
+ unsigned int copy_parents,
+ struct rcu_rbtree_node *stop)
{
- dbg_printf("transplant %p\n", v->key);
+ dbg_printf("transplant %p\n", v->begin);
lock_test_mutex();
- if (rcu_rbtree_is_nil(get_parent(u)))
+ if (rcu_rbtree_is_nil(rbtree, get_parent(u))) {
rbtree->root = v;
- else if (u == get_parent(u)->_left)
- get_parent(u)->_left = v;
- else
- get_parent(u)->_right = v;
+ } else {
+ if (u == get_parent(u)->_left)
+ get_parent(u)->_left = v;
+ else
+ get_parent(u)->_right = v;
+ populate_node_end(rbtree, get_parent(u), copy_parents, stop);
+ }
set_parent(v, get_parent(u), get_pos(u));
unlock_test_mutex();
}
static void rcu_rbtree_remove_fixup(struct rcu_rbtree *rbtree,
struct rcu_rbtree_node *x)
{
- dbg_printf("remove fixup %p\n", x->key);
+ dbg_printf("remove fixup %p\n", x->begin);
while (x != rbtree->root && x->color == COLOR_BLACK) {
assert(!is_decay(get_parent(x)));
struct rcu_rbtree_node *z,
struct rcu_rbtree_node *y)
{
- struct rcu_rbtree_node *x, *top, *top_child;
- unsigned int top_child_pos;
+ struct rcu_rbtree_node *x;
- dbg_printf("remove nonil %p\n", z->key);
+ dbg_printf("remove nonil %p\n", z->begin);
show_tree(rbtree);
assert(!is_decay(z));
if (get_parent(y) == z) {
y = dup_decay_node(rbtree, y);
set_parent(x, y, get_pos(x)); /* parent for nil */
- /* y is z's right node: set left will just update y */
- set_left_dup_decay(rbtree, y, z->_left,
- &top, &top_child, &top_child_pos);
- assert(top_child == y);
- rcu_rbtree_transplant(rbtree, z, y, 1);
+ /* y is z's right node */
+ set_left(rbtree, y, z->_left);
+ y->max_end = calculate_node_max_end(rbtree, y);
+ rcu_rbtree_transplant(rbtree, z, y, 1, NULL);
} else {
struct rcu_rbtree_node *oy_right, *z_right;
oy_right = y->_right;
/*
- * The max child key of z_right does not change, because
+ * The max child begin of z_right does not change, because
* we're only changing its left children.
*/
y->_right = z_right;
set_parent(y->_right, y, IS_RIGHT);
- if (rcu_rbtree_is_nil(y->_right))
- y->max_child_key = y->key;
- else
- y->max_child_key = y->_right->max_child_key;
-
assert(!is_decay(z->_left));
y->_left = z->_left;
- if (rcu_rbtree_is_nil(y->_left))
- y->min_child_key = y->key;
- else
- y->min_child_key = y->_left->min_child_key;
-
assert(!is_decay(oy_right));
/*
* Transplant of oy_right to old y's location will only
- * trigger a min/max update of the already copied branch
+ * trigger a "end" value update of the already copied branch
* (which is not visible yet). We are transplanting
* oy_right as a left child of old y's parent, so the
* min values update propagated upward necessarily stops
* at z_right.
*/
- rcu_rbtree_transplant(rbtree, y, oy_right, 0);
- rcu_rbtree_transplant(rbtree, z, y, 1);
+ rcu_rbtree_transplant(rbtree, y, oy_right, 0, y);
+ y->max_end = calculate_node_max_end(rbtree, y);
+ rcu_rbtree_transplant(rbtree, z, y, 1, NULL);
/* Update children */
(void) rcu_rbtree_min_update_decay(rbtree, y->_right);
}
unsigned int y_original_color;
assert(!is_decay(rbtree->root));
- dbg_printf("remove %p\n", z->key);
+ dbg_printf("remove %p\n", z->begin);
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, 1);
+ if (rcu_rbtree_is_nil(rbtree, z->_left)) {
+ rcu_rbtree_transplant(rbtree, z, z->_right, 1, NULL);
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, 1);
+ } else if (rcu_rbtree_is_nil(rbtree, z->_right)) {
+ rcu_rbtree_transplant(rbtree, z, z->_left, 1, NULL);
assert(!is_decay(z));
x = get_decay(z->_left);
show_tree(rbtree);
if (y_original_color == COLOR_BLACK)
rcu_rbtree_remove_fixup(rbtree, x);
show_tree(rbtree);
+ check_max_end(rbtree, x);
+ check_max_end(rbtree, get_decay(y));
/*
- * Commit all _CMM_STORE_SHARED().
+ * Commit all C__CMM_STORE_SHARED().
*/
- cmm_smp_wmc();
+ c_cmm_smp_wmc();
+#ifdef RBTREE_RCU_SUPPORT
+ rbtree->call_rcu(&z->head, _rcu_rbtree_free_node);
+#else
+ _rcu_rbtree_free_node(&z->head);
+#endif
return 0;
}
projects / urcu.git / blobdiff