From 3366b9c009f3d189dcb4e2f3a7b0ef63e1608ef7 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Wed, 1 Jun 2011 20:30:54 -0400 Subject: [PATCH] Rename node fields to begin/end This states the inclusiveness (begin) and exclusiveness (end) more explicitely. Signed-off-by: Mathieu Desnoyers --- tests/test_urcu_rbtree.c | 10 +++++----- urcu-rbtree.c | 32 +++++++++++++++++--------------- urcu/rcurbtree.h | 7 +++---- 3 files changed, 25 insertions(+), 24 deletions(-) diff --git a/tests/test_urcu_rbtree.c b/tests/test_urcu_rbtree.c index fe59496..f110462 100644 --- a/tests/test_urcu_rbtree.c +++ b/tests/test_urcu_rbtree.c @@ -218,7 +218,7 @@ void set_lookup_index(struct rcu_rbtree_node *node, int i; for (i = 0; i < global_items; i++) { - if (node->key == global_key[i] + if (node->begin == global_key[i] && !lookup_hit[i]) { lookup_hit[i] = 1; break; @@ -350,8 +350,8 @@ void *thr_writer(void *_count) node = rbtree_alloc(); //key[i] = (void *)(unsigned long)(rand() % 2048); key[i] = (void *)(unsigned long)(rand() % 6); - node->key = key[i]; - node->high = (void *)((unsigned long) key[i] + 1); + node->begin = key[i]; + node->end = (void *)((unsigned long) key[i] + 1); rcu_read_lock(); rcu_rbtree_insert(&rbtree, node); rcu_read_unlock(); @@ -541,8 +541,8 @@ int main(int argc, char **argv) for (i = 0; i < global_items; i++) { node = rbtree_alloc(); global_key[i] = (void *)(unsigned long)(rand() % 6); - node->key = global_key[i]; - node->high = (void *)((unsigned long) global_key[i] + 1); + node->begin = global_key[i]; + node->end = (void *)((unsigned long) global_key[i] + 1); rcu_rbtree_insert(&rbtree, node); } rcu_read_unlock(); diff --git a/urcu-rbtree.c b/urcu-rbtree.c index 478fbbe..e9e2485 100644 --- a/urcu-rbtree.c +++ b/urcu-rbtree.c @@ -193,9 +193,11 @@ void show_tree(struct rcu_rbtree *rbtree) node = rcu_rbtree_min(rbtree, rbtree->root); 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, + printf("{ b:%lX e:%lX pb: %lX pe: %lX r:%lX l:%lX %s %s %s} ", + (unsigned long) node->begin, + (unsigned long) node->end, + (unsigned long) get_parent(node)->begin, + (unsigned long) get_parent(node)->end, (unsigned long) node->_right->key, (unsigned long) node->_left->key, node->color ? "red" : "black", @@ -228,7 +230,7 @@ struct rcu_rbtree_node *rcu_rbtree_search(struct rcu_rbtree *rbtree, x = rcu_dereference(x); int comp; - while (!rcu_rbtree_is_nil(rbtree, x) && (comp = rbtree->comp(k, x->key)) != 0) { + while (!rcu_rbtree_is_nil(rbtree, x) && (comp = rbtree->comp(k, x->begin)) != 0) { dbg_usleep(10); if (comp < 0) x = rcu_dereference(x->_left); @@ -581,7 +583,7 @@ static void rcu_rbtree_insert_fixup(struct rcu_rbtree *rbtree, { 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) { @@ -643,14 +645,14 @@ int rcu_rbtree_insert(struct rcu_rbtree *rbtree, { struct rcu_rbtree_node *x, *y; - 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(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; @@ -663,7 +665,7 @@ int rcu_rbtree_insert(struct rcu_rbtree *rbtree, 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) + else if (rbtree->comp(z->begin, y->begin) < 0) set_parent(z, y, IS_LEFT); else set_parent(z, y, IS_RIGHT); @@ -675,7 +677,7 @@ int rcu_rbtree_insert(struct rcu_rbtree *rbtree, */ cmm_smp_wmb(); _CMM_STORE_SHARED(rbtree->root, z); - } else if (rbtree->comp(z->key, y->key) < 0) { + } else if (rbtree->comp(z->begin, y->begin) < 0) { set_left(rbtree, y, z); /* * Order stores to z (children/parents) before stores @@ -724,7 +726,7 @@ void rcu_rbtree_transplant(struct rcu_rbtree *rbtree, struct rcu_rbtree_node *v, unsigned int copy_parents) { - dbg_printf("transplant %p\n", v->key); + dbg_printf("transplant %p\n", v->begin); if (!rcu_rbtree_is_nil(rbtree, v)) v = dup_decay_node(rbtree, v); @@ -771,7 +773,7 @@ void rcu_rbtree_transplant(struct rcu_rbtree *rbtree, struct rcu_rbtree_node *v, unsigned int copy_parents) { - dbg_printf("transplant %p\n", v->key); + dbg_printf("transplant %p\n", v->begin); lock_test_mutex(); if (rcu_rbtree_is_nil(rbtree, get_parent(u))) @@ -789,7 +791,7 @@ void rcu_rbtree_transplant(struct rcu_rbtree *rbtree, 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))); @@ -879,7 +881,7 @@ void rcu_rbtree_remove_nonil(struct rcu_rbtree *rbtree, { 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)); @@ -906,7 +908,7 @@ void rcu_rbtree_remove_nonil(struct rcu_rbtree *rbtree, 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; @@ -944,7 +946,7 @@ int rcu_rbtree_remove(struct rcu_rbtree *rbtree, 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)); diff --git a/urcu/rcurbtree.h b/urcu/rcurbtree.h index 2321c83..df370fd 100644 --- a/urcu/rcurbtree.h +++ b/urcu/rcurbtree.h @@ -61,12 +61,11 @@ typedef void (*rcu_rbtree_free)(struct rcu_head *head); */ struct rcu_rbtree_node { /* must be set upon insertion */ - void *key; /* "key" is range low */ - void *high; /* high is range end (exclusive) */ - /* augmented tree */ - void *max_high; /* max high of node and children */ + void *begin; /* Start of range (inclusive) */ + void *end; /* range end (exclusive) */ /* internally reserved */ + void *max_end; /* max range end of node and children */ /* parent uses low bit for "0 -> is left, 1 -> is right" */ unsigned long parent; /* _left and _right must be updated with set_left(), set_right() */ -- 2.34.1