From 6ad1f7f7832a72368d2f502390224cc74f62087f Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Tue, 9 Mar 2010 09:52:37 -0500 Subject: [PATCH] urcu rbtree: use redirections when comparing to parent right/left in prev/next Signed-off-by: Mathieu Desnoyers --- urcu-rbtree.c | 22 ++++++++++++++++++---- 1 file changed, 18 insertions(+), 4 deletions(-) diff --git a/urcu-rbtree.c b/urcu-rbtree.c index 25ba43f..f834ef3 100644 --- a/urcu-rbtree.c +++ b/urcu-rbtree.c @@ -98,7 +98,7 @@ struct rcu_rbtree_node *rcu_rbtree_max(struct rcu_rbtree_node *x, 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, *yredir, *yr, *yrredir; x = rcu_dereference(x); @@ -107,7 +107,14 @@ struct rcu_rbtree_node *rcu_rbtree_next(struct rcu_rbtree_node *x, y = rcu_dereference(x->p); while ((yredir = rcu_dereference(y->redir)) != NULL) y = yredir; - while (y != &rcu_rbtree_nil && x == rcu_dereference(y->right)) { + for (;;) { + if (y == &rcu_rbtree_nil) + break; + yr = rcu_dereference(y->right); + while ((yrredir = rcu_dereference(yr->redir)) != NULL) + yr = yrredir; + if (x != yr) + break; x = y; y = rcu_dereference(y->p); while ((yredir = rcu_dereference(y->redir)) != NULL) @@ -119,7 +126,7 @@ struct rcu_rbtree_node *rcu_rbtree_next(struct rcu_rbtree_node *x, 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, *yredir, *yl, *ylredir;; x = rcu_dereference(x); @@ -128,7 +135,14 @@ struct rcu_rbtree_node *rcu_rbtree_prev(struct rcu_rbtree_node *x, y = rcu_dereference(x->p); while ((yredir = rcu_dereference(y->redir)) != NULL) y = yredir; - while (y != &rcu_rbtree_nil && x == rcu_dereference(y->left)) { + for (;;) { + if (y == &rcu_rbtree_nil) + break; + yl = rcu_dereference(y->left); + while ((ylredir = rcu_dereference(yl->redir)) != NULL) + yl = ylredir; + if (x != yl) + break; x = y; y = rcu_dereference(y->p); while ((yredir = rcu_dereference(y->redir)) != NULL) -- 2.34.1