From patchwork Sat May 21 08:51:50 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sasha Levin X-Patchwork-Id: 805502 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by demeter1.kernel.org (8.14.4/8.14.3) with ESMTP id p4L8qHei032147 for ; Sat, 21 May 2011 08:52:18 GMT Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753494Ab1EUIwH (ORCPT ); Sat, 21 May 2011 04:52:07 -0400 Received: from mail-ww0-f44.google.com ([74.125.82.44]:45882 "EHLO mail-ww0-f44.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751145Ab1EUIwF (ORCPT ); Sat, 21 May 2011 04:52:05 -0400 Received: by wwa36 with SMTP id 36so4709689wwa.1 for ; Sat, 21 May 2011 01:52:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:from:to:cc:subject:date:message-id:x-mailer; bh=wZVVpOQaQMZFr1UwZxQUT2+ecvWOlV389ItiFCWtByI=; b=GF4yja0Dgovw9AyQUMGVzHU2qXSDie5ryI0zeyipYGFI9Fr/PulqJcbkMIR6BSMdpR A5DvKE2a7Vx3iZ88eZ4ConOU9wWRUzX53rVkQUPSJmeOUEWYfYVyxRb49n35R8f22F/c dlp4mgfMqkP5PlC9Q03gQWkLizosZU9XMpsgw= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=from:to:cc:subject:date:message-id:x-mailer; b=G2Ro/CagbTaauplNu+o6biN3qY5tU2ZHv/MGCf9rbtsKQ9o1d6HF7R7vjIxuVRBS1A Q3gPLjaw+c9M+VP5QMqYBEWdNBI3esmtf9msvBt2nR7VTj04zkjEZ+Lurrq0NdIlI2vs 0qZXXdVdmlCVdzNKK7hezmok5nhNcNBZd2xmc= Received: by 10.227.200.138 with SMTP id ew10mr446172wbb.21.1305967923579; Sat, 21 May 2011 01:52:03 -0700 (PDT) Received: from localhost.localdomain (bzq-79-179-206-38.red.bezeqint.net [79.179.206.38]) by mx.google.com with ESMTPS id ca12sm2765187wbb.19.2011.05.21.01.52.02 (version=TLSv1/SSLv3 cipher=OTHER); Sat, 21 May 2011 01:52:03 -0700 (PDT) From: Sasha Levin To: penberg@kernel.org Cc: mingo@elte.hu, asias.hejun@gmail.com, gorcunov@gmail.com, prasadjoshi124@gmail.com, kvm@vger.kernel.org, Sasha Levin Subject: [PATCH 1/2] kvm tools: Fix rbtree-interval balancing Date: Sat, 21 May 2011 11:51:50 +0300 Message-Id: <1305967911-30045-1-git-send-email-levinsasha928@gmail.com> X-Mailer: git-send-email 1.7.5.rc3 Sender: kvm-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: kvm@vger.kernel.org X-Greylist: IP, sender and recipient auto-whitelisted, not delayed by milter-greylist-4.2.6 (demeter1.kernel.org [140.211.167.41]); Sat, 21 May 2011 08:52:18 +0000 (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 --- tools/kvm/util/rbtree-interval.c | 6 +++--- 1 files changed, 3 insertions(+), 3 deletions(-) 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; }