rbtree: add rb_next()

Signed-off-by: Jens Axboe <axboe@kernel.dk>

diff --git a/rbtree.c b/rbtree.c
index 7cff649821e85260014efc0aca4916221575962b..883bc7231d0905b114e45fb57c9a0b525e252b98 100644 (file)
--- 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;
 }
                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 7563725e51a90e37cff54e81c546ed30b151b28f..c6cfe4a9384d8041c978d7cef4b31cc587125e65 100644 (file)
--- 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 *);
 
 /* 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)
 
 static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
                                struct rb_node ** rb_link)