X-Git-Url: https://git.kernel.dk/?p=fio.git;a=blobdiff_plain;f=lib%2Frbtree.c;h=883bc7231d0905b114e45fb57c9a0b525e252b98;hp=7cff649821e85260014efc0aca4916221575962b;hb=eb50727a93ce10568973d6fc6b267b966e65b698;hpb=c41a9d06a1957ba7c5a019e3d6088a5e8e8e0a47

diff --git a/lib/rbtree.c b/lib/rbtree.c
index 7cff6498..883bc723 100644
--- a/lib/rbtree.c
+++ b/lib/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;
+}