From 8ad3466193d574b54cabb1a13713882a01ceb610 Mon Sep 17 00:00:00 2001 From: Sasha Levin Date: Sat, 21 May 2011 11:51:50 +0300 Subject: [PATCH] kvm tools: Fix rbtree-interval balancing 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 Signed-off-by: Pekka Enberg --- tools/kvm/util/rbtree-interval.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/tools/kvm/util/rbtree-interval.c b/tools/kvm/util/rbtree-interval.c index 735e912cf4c0..d02fbf0c469c 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; } -- 2.39.5