[1/2] kvm tools: Fix rbtree-interval balancing

Commit Message

Sasha Levin May 21, 2011, 8:51 a.m. UTC

Augmentation is started on the pre-rotation node found in the search,
augment the rotated node instead.

Max high is the max of max highs below it, not the max of highs below it.

Signed-off-by: Sasha Levin <[e-mail]>
---
 tools/kvm/util/rbtree-interval.c |    6 +++---
 1 files changed, 3 insertions(+), 3 deletions(-)

Patch

diff --git a/tools/kvm/util/rbtree-interval.c b/tools/kvm/util/rbtree-interval.c
index 735e912..d02fbf0 100644
--- a/tools/kvm/util/rbtree-interval.c
+++ b/tools/kvm/util/rbtree-interval.c
@@ -51,9 +51,9 @@  static void update_node_max_high(struct rb_node *node, void *arg)
 	i_node->max_high = i_node->high;
 
 	if (node->rb_left)
-		i_node->max_high = max(i_node->max_high, rb_int(node->rb_left)->high);
+		i_node->max_high = max(i_node->max_high, rb_int(node->rb_left)->max_high);
 	if (node->rb_right)
-		i_node->max_high = max(i_node->max_high, rb_int(node->rb_right)->high);
+		i_node->max_high = max(i_node->max_high, rb_int(node->rb_right)->max_high);
 }
 
 int rb_int_insert(struct rb_root *root, struct rb_int_node *i_node)
@@ -75,7 +75,7 @@  int rb_int_insert(struct rb_root *root, struct rb_int_node *i_node)
 	rb_link_node(&i_node->node, parent, node);
 	rb_insert_color(&i_node->node, root);
 
-	rb_augment_insert(*node, update_node_max_high, NULL);
+	rb_augment_insert(&i_node->node, update_node_max_high, NULL);
 	return 1;
 }