X-Git-Url: https://git.kernel.dk/?a=blobdiff_plain;f=lib%2Frbtree.c;h=6f0feae3a54b7f00f72a853a539a93c0ea8e9397;hb=3740cfc89440001e393dee1a6abae41ec89bec27;hp=7cff649821e85260014efc0aca4916221575962b;hpb=61b29c20eb4b1d374636d5325fb56c0fa9a574ad;p=fio.git

diff --git a/lib/rbtree.c b/lib/rbtree.c
index 7cff6498..6f0feae3 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -15,17 +15,17 @@
 
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
-  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 
   linux/lib/rbtree.c
 */
 
 #include "rbtree.h"
 
-static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
+static void __rb_rotate_left(struct fio_rb_node *node, struct rb_root *root)
 {
-	struct rb_node *right = node->rb_right;
-	struct rb_node *parent = rb_parent(node);
+	struct fio_rb_node *right = node->rb_right;
+	struct fio_rb_node *parent = rb_parent(node);
 
 	if ((node->rb_right = right->rb_left))
 		rb_set_parent(right->rb_left, node);
@@ -45,10 +45,10 @@ static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
 	rb_set_parent(node, right);
 }
 
-static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
+static void __rb_rotate_right(struct fio_rb_node *node, struct rb_root *root)
 {
-	struct rb_node *left = node->rb_left;
-	struct rb_node *parent = rb_parent(node);
+	struct fio_rb_node *left = node->rb_left;
+	struct fio_rb_node *parent = rb_parent(node);
 
 	if ((node->rb_left = left->rb_right))
 		rb_set_parent(left->rb_right, node);
@@ -68,9 +68,9 @@ static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
 	rb_set_parent(node, left);
 }
 
-void rb_insert_color(struct rb_node *node, struct rb_root *root)
+void rb_insert_color(struct fio_rb_node *node, struct rb_root *root)
 {
-	struct rb_node *parent, *gparent;
+	struct fio_rb_node *parent, *gparent;
 
 	while ((parent = rb_parent(node)) && rb_is_red(parent))
 	{
@@ -79,7 +79,7 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
 		if (parent == gparent->rb_left)
 		{
 			{
-				register struct rb_node *uncle = gparent->rb_right;
+				register struct fio_rb_node *uncle = gparent->rb_right;
 				if (uncle && rb_is_red(uncle))
 				{
 					rb_set_black(uncle);
@@ -92,7 +92,7 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
 
 			if (parent->rb_right == node)
 			{
-				register struct rb_node *tmp;
+				register struct fio_rb_node *tmp;
 				__rb_rotate_left(parent, root);
 				tmp = parent;
 				parent = node;
@@ -104,7 +104,7 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
 			__rb_rotate_right(gparent, root);
 		} else {
 			{
-				register struct rb_node *uncle = gparent->rb_left;
+				register struct fio_rb_node *uncle = gparent->rb_left;
 				if (uncle && rb_is_red(uncle))
 				{
 					rb_set_black(uncle);
@@ -117,7 +117,7 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
 
 			if (parent->rb_left == node)
 			{
-				register struct rb_node *tmp;
+				register struct fio_rb_node *tmp;
 				__rb_rotate_right(parent, root);
 				tmp = parent;
 				parent = node;
@@ -133,10 +133,11 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
 	rb_set_black(root->rb_node);
 }
 
-static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
+static void __rb_erase_color(struct fio_rb_node *node,
+			     struct fio_rb_node *parent,
 			     struct rb_root *root)
 {
-	struct rb_node *other;
+	struct fio_rb_node *other;
 
 	while ((!node || rb_is_black(node)) && node != root->rb_node)
 	{
@@ -161,7 +162,7 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 			{
 				if (!other->rb_right || rb_is_black(other->rb_right))
 				{
-					struct rb_node *o_left;
+					struct fio_rb_node *o_left;
 					if ((o_left = other->rb_left))
 						rb_set_black(o_left);
 					rb_set_red(other);
@@ -198,7 +199,7 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 			{
 				if (!other->rb_left || rb_is_black(other->rb_left))
 				{
-					register struct rb_node *o_right;
+					register struct fio_rb_node *o_right;
 					if ((o_right = other->rb_right))
 						rb_set_black(o_right);
 					rb_set_red(other);
@@ -219,9 +220,9 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 		rb_set_black(node);
 }
 
-void rb_erase(struct rb_node *node, struct rb_root *root)
+void rb_erase(struct fio_rb_node *node, struct rb_root *root)
 {
-	struct rb_node *child, *parent;
+	struct fio_rb_node *child, *parent;
 	int color;
 
 	if (!node->rb_left)
@@ -230,7 +231,7 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
 		child = node->rb_left;
 	else
 	{
-		struct rb_node *old = node, *left;
+		struct fio_rb_node *old = node, *left;
 
 		node = node->rb_right;
 		while ((left = node->rb_left) != NULL)
@@ -289,9 +290,9 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
 /*
  * This function returns the first node (in sort order) of the tree.
  */
-struct rb_node *rb_first(struct rb_root *root)
+struct fio_rb_node *rb_first(struct rb_root *root)
 {
-	struct rb_node	*n;
+	struct fio_rb_node	*n;
 
 	n = root->rb_node;
 	if (!n)
@@ -300,3 +301,34 @@ struct rb_node *rb_first(struct rb_root *root)
 		n = n->rb_left;
 	return n;
 }
+
+struct fio_rb_node *rb_next(const struct fio_rb_node *node)
+{
+	struct fio_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 fio_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;
+}