From ac5f39632596c358abb8cc4df79e852612598c3d Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Mon, 30 May 2011 13:49:28 -0400 Subject: [PATCH] Add search min/max for ranges Signed-off-by: Mathieu Desnoyers --- urcu-rbtree.c | 49 ++++++++++++++++++++++++++++++++++++++++++++++-- urcu/rcurbtree.h | 12 ++++++++++++ 2 files changed, 59 insertions(+), 2 deletions(-) diff --git a/urcu-rbtree.c b/urcu-rbtree.c index 824883d..5ad7763 100644 --- a/urcu-rbtree.c +++ b/urcu-rbtree.c @@ -389,10 +389,11 @@ struct rcu_rbtree_node* rcu_rbtree_search(struct rcu_rbtree *rbtree, void *k) { x = rcu_dereference(x); + int comp; - while (!rcu_rbtree_is_nil(x) && k != x->key) { + while (!rcu_rbtree_is_nil(x) && (comp = rbtree->comp(k, x->key)) != 0) { usleep(10); - if (rbtree->comp(k, x->key) < 0) + if (comp < 0) x = rcu_dereference(x->_left); else x = rcu_dereference(x->_right); @@ -400,6 +401,50 @@ struct rcu_rbtree_node* rcu_rbtree_search(struct rcu_rbtree *rbtree, return x; } +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) { + break; + } else if (rbtree->comp(range_low, x->min_child_key) > 0) { + x = rcu_dereference(x->_right); + } else { + x = make_nil(rbtree); + } + } + return x; +} + +struct rcu_rbtree_node* rcu_rbtree_search_max(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->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); + } + } + return x; +} + static struct rcu_rbtree_node *rcu_rbtree_min_dup_decay(struct rcu_rbtree *rbtree, struct rcu_rbtree_node *x, diff --git a/urcu/rcurbtree.h b/urcu/rcurbtree.h index 3efbbfa..dc59653 100644 --- a/urcu/rcurbtree.h +++ b/urcu/rcurbtree.h @@ -135,6 +135,18 @@ struct rcu_rbtree_node *rcu_rbtree_search(struct rcu_rbtree *rbtree, struct rcu_rbtree_node *x, void *key); +/* + * Search for node with, respectively, smallest or largest value within + * the ranges (ranges are inclusive). + */ +struct rcu_rbtree_node *rcu_rbtree_search_min(struct rcu_rbtree *rbtree, + struct rcu_rbtree_node *x, + void *range_low, void *range_high); + +struct rcu_rbtree_node *rcu_rbtree_search_max(struct rcu_rbtree *rbtree, + struct rcu_rbtree_node *x, + void *range_low, void *range_high); + struct rcu_rbtree_node *rcu_rbtree_min(struct rcu_rbtree *rbtree, struct rcu_rbtree_node *x); -- 2.34.1