From patchwork Mon Jul 3 19:58:17 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Praveen Kumar X-Patchwork-Id: 9823921 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 A2BE960353 for ; Mon, 3 Jul 2017 20:02:20 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 9512F26D08 for ; Mon, 3 Jul 2017 20:02:20 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 8972727F3E; Mon, 3 Jul 2017 20:02:20 +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 2663826D08 for ; Mon, 3 Jul 2017 20:02:20 +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 1dS7Vq-0001kI-AZ; Mon, 03 Jul 2017 20:00:02 +0000 Received: from mail6.bemta3.messagelabs.com ([195.245.230.39]) by lists.xenproject.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dS7Vp-0001Rs-0W for xen-devel@lists.xen.org; Mon, 03 Jul 2017 20:00:01 +0000 Received: from [85.158.137.68] by server-17.bemta-3.messagelabs.com id 10/0C-01859-042AA595; Mon, 03 Jul 2017 20:00:00 +0000 X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFlrKIsWRWlGSWpSXmKPExsXiVRvkqGu/KCr S4O4LTYslHxezODB6HN39mymAMYo1My8pvyKBNePmn4csBcskK/7c+sTawDhTtIuRi0NIYAKj xKu5j5lBHBaBlywS16Y9YwdxJAT6WSW2fbnL0sXICeTESdz/Ox/KLpe4eOwVE4gtJKAmsWXeK WaIUf8ZJfZs/87YxcjBwSagK9F+qwCkRkRAWuLa58uMIDXMAt8ZJda8n8IKkhAW8JRoXNXNDG KzCKhKXN69gRWkl1fAVmLp+kyIXfISizbNANvLCRSe+WAG1F4biZ9X+hknMAosYGRYxahenFp Ullqka66XVJSZnlGSm5iZo2toYKyXm1pcnJiempOYVKyXnJ+7iREYWAxAsIOx8bvTIUZJDiYl UV7Xm5GRQnxJ+SmVGYnFGfFFpTmpxYcYZTg4lCR4WRdGRQoJFqWmp1akZeYAQxwmLcHBoyTCO 7kRKM1bXJCYW5yZDpE6xWjMMenA9i9MHK8m/P/GJMSSl5+XKiXOqwUySQCkNKM0D24QLPYuMc pKCfMyAp0mxFOQWpSbWYIq/4pRnINRSZi3fgHQFJ7MvBK4fa+ATmECOqWhJwLklJJEhJRUA+P R452PP98VWLPw3PY9bKcfXb0g8n2JTt18A12Do/vLhI51C0yTOOUze+7u2R/P7LE1vMnZctna YP+ayFWxB8+9iOwsnLpae1rAw7Xngg7uatvHY17CbXTAr3S7vd+VrXavNL637MlzsWrltM2/d oszLe7djK1fylf5ur0OO9fUN+mOd1LMlHm1SizFGYmGWsxFxYkAywamPbgCAAA= X-Env-Sender: kpraveen.lkml@gmail.com X-Msg-Ref: server-13.tower-31.messagelabs.com!1499111989!103113772!1 X-Originating-IP: [74.125.82.65] 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 60518 invoked from network); 3 Jul 2017 19:59:59 -0000 Received: from mail-wm0-f65.google.com (HELO mail-wm0-f65.google.com) (74.125.82.65) by server-13.tower-31.messagelabs.com with AES128-GCM-SHA256 encrypted SMTP; 3 Jul 2017 19:59:59 -0000 Received: by mail-wm0-f65.google.com with SMTP id y5so22373633wmh.3 for ; Mon, 03 Jul 2017 12:59:49 -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=a6s9DLeeJT4CwHfZMFYpqm9VttUnpcl6CTezn95dlqE=; b=Pv6xK6dMYzsyuPlFmFvCaMfEXHu5/aRP6Iw963whJIelhmQOA3YHlSkUMAc5AiOlg2 OkZQz0Upt4UGR/MdG/cYE0AkjvDZVnslsR1tf2gxkmYokf4TqGYdUH8atDTC541SuKK/ VswUI2ghH2gchMAH/eoH7sKdvZqrjlYBZl+ijG+p+jaLP59NNKVKIT8g5iJGiRS42Tha yC3AuJsgWmYzBiSbUKnpqsa7n/0CMKv9ZjvFRe6+O4eYSrcHL6PPzeYqSZcu1Y0kRCMA FkM0GN8VA6k6BTlX2UIsjXHqrQC+6/UJpV2toTl8OH9dTVIm3bVSVt7YBaFte/kxmTk1 CfVw== 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=a6s9DLeeJT4CwHfZMFYpqm9VttUnpcl6CTezn95dlqE=; b=TvaikF7cgYKhHN4x5hl/KVDPG1xOF94Js+WHgCWP2+sLtivLlx9gY/m5GQt9KEz8nI k4mIfTAhHe8UDR4Zs18wJ04Z0dmoaeIhsi2JrCbvW6imYDgBe7lYJ4hJZfqjTXgoYUWj RHtOhA1XVf0SCNem82p31JjvJsNMnioOJBaxhDEBk9ifjBAGBoaeYZ6ruNWVfIUIy4D7 ukVAjjmfJ8/JoZCRAKEhc9SQDUcNqeNKriNv4YDYzO11hcoCLev8sl/9XVArwTs3Iptr YcXNqZOV2OQQRRZLscLmHqUV1UoAWhK/zhkj6ySqipFVg0Vy2SC3Ab1ybdcoOw86Ztpg LDfw== X-Gm-Message-State: AIVw1102wgLyDCV9RTnJ2UZ8zkFoByaw49Az05w4dNtSLmdVGjZsR6lp bi8GNUGlon2FhRQW X-Received: by 10.28.144.6 with SMTP id s6mr10646575wmd.16.1499111989072; Mon, 03 Jul 2017 12:59:49 -0700 (PDT) Received: from kpraveen.labs.blr.novell.com ([106.51.128.11]) by smtp.gmail.com with ESMTPSA id 21sm25658979wmo.16.2017.07.03.12.59.43 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Mon, 03 Jul 2017 12:59:48 -0700 (PDT) From: Praveen Kumar To: xen-devel@lists.xen.org Date: Tue, 4 Jul 2017 01:28:17 +0530 Message-Id: <20170703195821.29845-14-kpraveen.lkml@gmail.com> X-Mailer: git-send-email 2.12.0 In-Reply-To: <20170703195821.29845-1-kpraveen.lkml@gmail.com> References: <20170703195821.29845-1-kpraveen.lkml@gmail.com> Cc: sstabellini@kernel.org, wei.liu2@citrix.com, George.Dunlap@eu.citrix.com, andrew.cooper3@citrix.com, dario.faggioli@citrix.com, ian.jackson@eu.citrix.com, tim@xen.org, kpraveen.lkml@gmail.com, jbeulich@suse.com Subject: [Xen-devel] [PATCH v4 13/17] rbtree: add __rb_change_child() helper function 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 From: Michel Lespinasse Add __rb_change_child() as an inline helper function to replace code that would otherwise be duplicated 4 times in the source. No changes to binary size or speed. 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 [Linux commit 7abc704ae399fcb9c51ca200b0456f8a975a8011] Ported to Xen. Signed-off-by: Praveen Kumar --- xen/common/rbtree.c | 46 +++++++++++++++++----------------------------- 1 file changed, 17 insertions(+), 29 deletions(-) diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c index 56c815b4a5..d438d50761 100644 --- a/xen/common/rbtree.c +++ b/xen/common/rbtree.c @@ -65,6 +65,19 @@ static inline struct rb_node *rb_red_parent(struct rb_node *red) return (struct rb_node *)red->__rb_parent_color; } +static inline void +__rb_change_child(struct rb_node *old, struct rb_node *new, + struct rb_node *parent, struct rb_root *root) +{ + if (parent) { + if (parent->rb_left == old) + parent->rb_left = new; + else + parent->rb_right = new; + } else + root->rb_node = new; +} + /* * Helper function for rotations: * - old's parent and color get assigned to new @@ -77,13 +90,7 @@ __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, struct rb_node *parent = rb_parent(old); new->__rb_parent_color = old->__rb_parent_color; rb_set_parent_color(old, new, color); - if (parent) { - if (parent->rb_left == old) - parent->rb_left = new; - else - parent->rb_right = new; - } else - root->rb_node = new; + __rb_change_child(old, new, parent, root); } void rb_insert_color(struct rb_node *node, struct rb_root *root) @@ -374,13 +381,7 @@ void rb_erase(struct rb_node *node, struct rb_root *root) while ((left = node->rb_left) != NULL) node = left; - if (rb_parent(old)) { - if (rb_parent(old)->rb_left == old) - rb_parent(old)->rb_left = node; - else - rb_parent(old)->rb_right = node; - } else - root->rb_node = node; + __rb_change_child(old, node, rb_parent(old), root); child = node->rb_right; parent = rb_parent(node); @@ -410,13 +411,7 @@ void rb_erase(struct rb_node *node, struct rb_root *root) if (child) rb_set_parent(child, parent); - if (parent) { - if (parent->rb_left == node) - parent->rb_left = child; - else - parent->rb_right = child; - } else - root->rb_node = child; + __rb_change_child(node, child, parent, root); color: if (color == RB_BLACK) @@ -520,14 +515,7 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new, struct rb_node *parent = rb_parent(victim); /* Set the surrounding nodes to point to the replacement */ - if (parent) { - if (victim == parent->rb_left) - parent->rb_left = new; - else - parent->rb_right = new; - } else { - root->rb_node = new; - } + __rb_change_child(victim, new, parent, root); if (victim->rb_left) rb_set_parent(victim->rb_left, new); if (victim->rb_right)