From patchwork Wed May 31 20:47:05 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Praveen Kumar X-Patchwork-Id: 9758083 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id 8E04160390 for ; Wed, 31 May 2017 20:50:54 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 811FB284CF for ; Wed, 31 May 2017 20:50:54 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 75F0F284EE; Wed, 31 May 2017 20:50:54 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-3.6 required=2.0 tests=BAYES_00, DKIM_ADSP_CUSTOM_MED, DKIM_SIGNED, FREEMAIL_FROM, RCVD_IN_DNSWL_MED, RCVD_IN_SORBS_SPAM, T_DKIM_INVALID autolearn=ham version=3.3.1 Received: from lists.xenproject.org (lists.xenproject.org [192.237.175.120]) (using TLSv1.2 with cipher AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by mail.wl.linuxfoundation.org (Postfix) with ESMTPS id 20763284CF for ; Wed, 31 May 2017 20:50:54 +0000 (UTC) Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dGAXx-0008Ue-W1; Wed, 31 May 2017 20:48:49 +0000 Received: from mail6.bemta3.messagelabs.com ([195.245.230.39]) by lists.xenproject.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dGAXw-0008TG-FE for xen-devel@lists.xen.org; Wed, 31 May 2017 20:48:48 +0000 Received: from [85.158.137.68] by server-11.bemta-3.messagelabs.com id DB/92-01732-F2C2F295; Wed, 31 May 2017 20:48:47 +0000 X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFlrCIsWRWlGSWpSXmKPExsVyMfTAIV19Hf1 Ig/8uFks+LmZxYPQ4uvs3UwBjFGtmXlJ+RQJrxu3D/9gKpgtV3Lvxlq2B8Q9vFyMXh5DAREaJ /m8fWUAcFoGXLBKtD/8COZwcEgL9rBKXXvlD2EkSExuvQsXLJF7se8YOYgsJqElsmXeKGcL+x SjxY2pyFyMHB5uArkT7rQKQsIiAtMS1z5cZQeYzC7SzSPx8vZoJJCEs4CpxsfkoWC+LgKpE85 IJYDN5BWwlzl74ywixS15i0aYZYHs5geJXuhazQeyykVi4fgLbBEaBBYwMqxg1ilOLylKLdI0 s9JKKMtMzSnITM3N0DQ2M9XJTi4sT01NzEpOK9ZLzczcxAsOqnoGBcQdj+wm/Q4ySHExKorwV NnqRQnxJ+SmVGYnFGfFFpTmpxYcYZTg4lCR4jbX1I4UEi1LTUyvSMnOAAQ6TluDgURLhZQJJ8 xYXJOYWZ6ZDpE4xGnNcubLuCxPHlAPbvzAJseTl56VKifPqgpQKgJRmlObBDYJF3iVGWSlhXk YGBgYhnoLUotzMElT5V4ziHIxKwrziIFN4MvNK4Pa9AjqFCeiUXTu0QU4pSURISTUwyuletth h/ykto1CB46L3c1ljrdCnLP/VrHOaJjy8JbHhca9z0mNLA4kTmqxfeO+tSmm46/4tdsOFr4aV R9tm95W0ntksG/bkh5U/68EM91ezTv6ZxHQli+FoyLS1qlcEpabX3Vy851tEw1yNdw0PFzD1i Ef8+LpxY0J+QsH/a6xlATaL3sdlKLEUZyQaajEXFScCAJp7aj23AgAA X-Env-Sender: kpraveen.lkml@gmail.com X-Msg-Ref: server-3.tower-31.messagelabs.com!1496263725!103463782!1 X-Originating-IP: [209.85.192.194] X-SpamReason: No, hits=0.0 required=7.0 tests= X-StarScan-Received: X-StarScan-Version: 9.4.19; banners=-,-,- X-VirusChecked: Checked Received: (qmail 31053 invoked from network); 31 May 2017 20:48:46 -0000 Received: from mail-pf0-f194.google.com (HELO mail-pf0-f194.google.com) (209.85.192.194) by server-3.tower-31.messagelabs.com with AES128-GCM-SHA256 encrypted SMTP; 31 May 2017 20:48:46 -0000 Received: by mail-pf0-f194.google.com with SMTP id n23so4121840pfb.3 for ; Wed, 31 May 2017 13:48:46 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=5atQSJ/8vaAogCyc/MdxdLS3RmRNT/cdSQaCxOpl1kk=; b=ikmX5/LXPR62y7I+oRXjmJqc6Cgnmu0M0HF/vBj1hrfdGh114+mRXNLr6IwMLIYvmq SlcYCvIVwEu4n6FRJKm1ixaDLmGo2Taky4IZ4bD1j4r+u1iprfPHrzGIxHFMXxN2RBPV Q2YLNPb5DjYJDfhivdEbhOoDjQjnzFQT4TacCBO5+ldMH2JCYzodJGGPIj52opR274i2 J+sp3PCzTieoLltBNUPxdPZp4IVgCcQSE+vLump87J5Ns/kbZiMZmJvQVI+TvLq3BDOQ nor8JXOpfGno4khcM0wMPfqqL7rgE3JHiyjovaCxafdziAR0mu9WdD3zrepwrp5N/vMR 1N5A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=5atQSJ/8vaAogCyc/MdxdLS3RmRNT/cdSQaCxOpl1kk=; b=WrWxHC/IRhHqVW3qcmAL64WhVPJR5/jAbEEQL8zDML7M9QrBV7nu621HiGg0KCdbNA diG6ZdnQgJ0cuhEfBjsxZk2hoZjrT1ryHzVNHZ9QegjS/9KOClS/R/pt4UvULVar1Nwo ffJTartGLyYdRKBZfLXThWOXFCQHwz3CiYVGemcvR8kfMfqyHPKJ0Hp2vFjE5kOODAhB 7qc7OZ64uh1IzRGAxvY7JHGhnoBs3poD4Ge2TxcnRXdl1gmuiA+bd5eq/b1ihsasVYUb PnX9Q4tGdPH0pBzrVa0z9xaWjI3Qy/wcTTVG0chptVZYEqvmFSjfIFatTWS+E6+cqdOw m+LA== X-Gm-Message-State: AODbwcAbCf5Raj/k4w3DgUjjEA7QAB7LQIMHpzkhASnckAGOXASZNxwG 4PAq5Pef/VdJafLhReY= X-Received: by 10.98.32.92 with SMTP id g89mr39412pfg.153.1496263725225; Wed, 31 May 2017 13:48:45 -0700 (PDT) Received: from kpraveen.labs.blr.name ([103.227.99.58]) by smtp.gmail.com with ESMTPSA id d75sm31798444pfj.75.2017.05.31.13.48.40 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Wed, 31 May 2017 13:48:44 -0700 (PDT) From: Praveen Kumar To: xen-devel@lists.xen.org Date: Thu, 1 Jun 2017 02:17:05 +0530 Message-Id: <20170531204708.10470-15-kpraveen.lkml@gmail.com> X-Mailer: git-send-email 2.12.0 In-Reply-To: <20170531204708.10470-1-kpraveen.lkml@gmail.com> References: <20170531204708.10470-1-kpraveen.lkml@gmail.com> Cc: Andrea Arcangeli , sstabellini@kernel.org, wei.liu2@citrix.com, Peter Zijlstra , George.Dunlap@eu.citrix.com, andrew.cooper3@citrix.com, dario.faggioli@citrix.com, ian.jackson@eu.citrix.com, tim@xen.org, Linus Torvalds , Praveen Kumar , jbeulich@suse.com, Andrew Morton , Michel Lespinasse , David Woodhouse Subject: [Xen-devel] [PATCH 14/17] rbtree: place easiest case first in rb_erase() X-BeenThere: xen-devel@lists.xen.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Errors-To: xen-devel-bounces@lists.xen.org Sender: "Xen-devel" X-Virus-Scanned: ClamAV using ClamSMTP In rb_erase, move the easy case (node to erase has no more than 1 child) first. I feel the code reads easier that way. commit 60670b8034d6e2ba860af79c9379b7788d09db73 from Linux tree Signed-off-by: Michel Lespinasse Reviewed-by: Rik van Riel Cc: Peter Zijlstra Cc: Andrea Arcangeli Cc: David Woodhouse Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- xen/common/rbtree.c | 36 ++++++++++++++++++------------------ 1 file changed, 18 insertions(+), 18 deletions(-) diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c index 3b54c04bea..69c7496c65 100644 --- a/xen/common/rbtree.c +++ b/xen/common/rbtree.c @@ -376,18 +376,29 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, void rb_erase(struct rb_node *node, struct rb_root *root) { - struct rb_node *child, *parent; + struct rb_node *child = node->rb_right, *tmp = node->rb_left; + struct rb_node *parent; int color; - if (!node->rb_left) - child = node->rb_right; - else if (!node->rb_right) - child = node->rb_left; - else + if (!tmp) { + case1: + /* Case 1: node to erase has no more than 1 child (easy!) */ + + parent = rb_parent(node); + color = rb_color(node); + + if (child) + rb_set_parent(child, parent); + __rb_change_child(node, child, parent, root); + } else if (!child) { + /* Still case 1, but this time the child is node->rb_left */ + child = tmp; + goto case1; + } else { struct rb_node *old = node, *left; - node = node->rb_right; + node = child; while ((left = node->rb_left) != NULL) node = left; @@ -412,19 +423,8 @@ void rb_erase(struct rb_node *node, struct rb_root *root) node->rb_left = old->rb_left; rb_set_parent(old->rb_left, node); - - goto color; } - parent = rb_parent(node); - color = rb_color(node); - - if (child) - rb_set_parent(child, parent); - - __rb_change_child(node, child, parent, root); - - color: if (color == RB_BLACK) __rb_erase_color(child, parent, root); }