From 8f2b1374214f6165a55daa6be602021b991418d5 Mon Sep 17 00:00:00 2001 From: Jens Axboe Date: Wed, 7 Nov 2012 11:40:03 +0100 Subject: [PATCH] rbtree: add rb_next() Signed-off-by: Jens Axboe --- rbtree.c | 31 +++++++++++++++++++++++++++++++ rbtree.h | 1 + 2 files changed, 32 insertions(+) diff --git a/rbtree.c b/rbtree.c index 7cff6498..883bc723 100644 --- a/rbtree.c +++ b/rbtree.c @@ -300,3 +300,34 @@ struct rb_node *rb_first(struct rb_root *root) n = n->rb_left; return n; } + +struct rb_node *rb_next(const struct rb_node *node) +{ + struct rb_node *parent; + + if (RB_EMPTY_NODE(node)) + return NULL; + + /* + * If we have a right-hand child, go down and then left as far + * as we can. + */ + if (node->rb_right) { + node = node->rb_right; + while (node->rb_left) + node=node->rb_left; + return (struct rb_node *)node; + } + + /* + * No right-hand children. Everything down and left is smaller than us, + * so any 'next' node must be in the general direction of our parent. + * Go up the tree; any time the ancestor is a right-hand child of its + * parent, keep going up. First time it's a left-hand child of its + * parent, said parent is our 'next' node. + */ + while ((parent = rb_parent(node)) && node == parent->rb_right) + node = parent; + + return parent; +} diff --git a/rbtree.h b/rbtree.h index 7563725e..c6cfe4a9 100644 --- a/rbtree.h +++ b/rbtree.h @@ -141,6 +141,7 @@ extern void rb_erase(struct rb_node *, struct rb_root *); /* Find logical next and previous nodes in a tree */ extern struct rb_node *rb_first(struct rb_root *); +extern struct rb_node *rb_next(const struct rb_node *); static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, struct rb_node ** rb_link) -- 2.25.1