From patchwork Fri Jul 14 08:26:20 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Praveen Kumar X-Patchwork-Id: 9840173 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 5B39260393 for ; Fri, 14 Jul 2017 08:29:28 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 489BC27FB6 for ; Fri, 14 Jul 2017 08:29:28 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 3BD2C2874F; Fri, 14 Jul 2017 08:29:28 +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=-2.1 required=2.0 tests=BAYES_00, DKIM_ADSP_CUSTOM_MED, DKIM_SIGNED,FREEMAIL_FROM,RCVD_IN_DNSWL_MED,RCVD_IN_SORBS_SPAM, RCVD_IN_SORBS_WEB,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 E63AD27FB6 for ; Fri, 14 Jul 2017 08:29:26 +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 1dVvvt-0007Ci-Kd; Fri, 14 Jul 2017 08:26:41 +0000 Received: from mail6.bemta5.messagelabs.com ([195.245.231.135]) by lists.xenproject.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dVvvs-0007Cb-BJ for xen-devel@lists.xen.org; Fri, 14 Jul 2017 08:26:40 +0000 Received: from [85.158.139.211] by server-13.bemta-5.messagelabs.com id CF/32-01732-F3088695; Fri, 14 Jul 2017 08:26:39 +0000 X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFlrNIsWRWlGSWpSXmKPExsXiVRvsqGvbkBF pMKVV0WLJx8UsDoweR3f/ZgpgjGLNzEvKr0hgzXj7chpzwZ0djBW3Z7UzNzDuamPsYuTiEBKY yCgxbU43G4jDIvCSRWLZtKvsII6EQD+rRMfTS0BlnEBOnMTXtVfYIOxqiR93NrKD2EICahJb5 p1ihrD/M0q871PtYuTgYBPQlWi/VQASFhGQlrj2+TLYNmaB74wSa95PYQVJCAtESsz5+wnMZh FQlXi35RCYzStgI7F7witWiF3yEos2zWABmckpYCvx5GkGiCkEVLLwWv0ERoEFjAyrGNWLU4v KUot0TfWSijLTM0pyEzNzdA0NTPVyU4uLE9NTcxKTivWS83M3MQIDiwEIdjB+6Xc+xCjJwaQk yluanhEpxJeUn1KZkVicEV9UmpNafIhRhoNDSYLXrB4oJ1iUmp5akZaZAwxxmLQEB4+SCK8CS Jq3uCAxtzgzHSJ1itGSY0HPhi9MHJMObAeSryb8/8YkxJKXn5cqJc6bBNIgANKQUZoHNw4Wh5 cYZaWEeRmBDhTiKUgtys0sQZV/xSjOwagkzBsHMoUnM68EbusroIOYgA5qywI7qCQRISXVwBj 8PfOI9KqMvmP1r7dzPdsXsCYjSiz9fti8XtclcyVXHZtQfO2tt+U6yWzm3abn9F6FLU3caLJs Mw9n6ct5ElInmhdpfrgtVXvsb6pC6u6nd+rfKT+M/sAo2q7BKlEXdevAhuxJMjcWrtvasPrKa lWOnwVeiWcjhc+fuFm2NXSFNeemuP+KluFKLMUZiYZazEXFiQDVuBDuvgIAAA== X-Env-Sender: kpraveen.lkml@gmail.com X-Msg-Ref: server-6.tower-206.messagelabs.com!1500020795!102665380!1 X-Originating-IP: [74.125.83.65] X-SpamReason: No, hits=0.0 required=7.0 tests= X-StarScan-Received: X-StarScan-Version: 9.4.25; banners=-,-,- X-VirusChecked: Checked Received: (qmail 46730 invoked from network); 14 Jul 2017 08:26:37 -0000 Received: from mail-pg0-f65.google.com (HELO mail-pg0-f65.google.com) (74.125.83.65) by server-6.tower-206.messagelabs.com with AES128-GCM-SHA256 encrypted SMTP; 14 Jul 2017 08:26:37 -0000 Received: by mail-pg0-f65.google.com with SMTP id d193so9864375pgc.2 for ; Fri, 14 Jul 2017 01:26:37 -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=djrmKVl4N9DufHrWMEAOAqlK78FU3smXQ9m+3Ak/R1A=; b=WfKDqHzcuYcPR7F1pGjOrTUZKtVM+6rXrmkgqU2R5T4XN6PhoN3A3asgjRAOKA7o2l /jnxAa+GOSsMYv69aZVGtPxt1L28GAMKcn7EXW/kRVGvDmnGA2RKpwhZt3ARzVALBst8 ZbNUxLvIncr+vRcvr2hWwFZReQV0dFxOEVH6X2iWYaB/VsqoPc7JPUaouTtawVDjRzLT +GacZ9UxkNq201bpJZc07hSeC4vOrCtlvTrKxDaXnxso0NSVu65kXghbMyku4v+fSYo+ C2nloBOi4SNF6mnJLkZ+aVxwfhaiSSgREF6cXDX1UYatL1/NWCeiAd/DVSPhKHzWNVoB rj9g== 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=djrmKVl4N9DufHrWMEAOAqlK78FU3smXQ9m+3Ak/R1A=; b=DpY76M/IB0VfAjwppVZsK+RE1RVfygJBejwOK/eYTfX7O70cBUtxJ5ouHkz5fipX6C fw62JbLPYK844s7XV80Z95LsKajinZlsYXC2GXk2kRkC02JpandjQJ/eHWWcqs+T2JJo pvBIs19lGOML2CjNKqGBuUiGm6sVf7VSsq+nHadqdG+t8S/WayffSqzg7qgMwd9S79th RowcEPYaqSGafoFGkDIEWuXljJUGPMHH4C/GiMQ8mRiEu8cJbkl4xR/8qMk21ojfTcnq CBDwN2/SCK62QHOuOCU6yNY4mQfW2JdBgKXPJ80zGjMabXLfiesCVl0xuiVKUSqIvyf0 Sk8Q== X-Gm-Message-State: AIVw111MaLm4zw+0CjnB430TUL3/R1QaOvL0SfbevZYUII/wQ8kKCH5y TB1t4Ziw+KX4Vyjm X-Received: by 10.84.232.207 with SMTP id x15mr14754793plm.173.1500020795088; Fri, 14 Jul 2017 01:26:35 -0700 (PDT) Received: from kpraveen.labs.blr.novell.com ([192.31.114.252]) by smtp.gmail.com with ESMTPSA id u13sm1533836pgc.3.2017.07.14.01.26.31 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Fri, 14 Jul 2017 01:26:34 -0700 (PDT) From: Praveen Kumar To: xen-devel@lists.xen.org Date: Fri, 14 Jul 2017 13:56:20 +0530 Message-Id: <20170714082636.29511-2-kpraveen.lkml@gmail.com> X-Mailer: git-send-email 2.12.0 In-Reply-To: <20170714082636.29511-1-kpraveen.lkml@gmail.com> References: <20170714082636.29511-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 v5 01/17] rbtree: changes to align the coding conventions with Linux tree 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 The patch aligns the coding style of rbtree related files to Linux coding conventions to have limited conflicts in future while porting from Linux tree. This patch includes only the style changes. Linux commit till 4c60117811171d867d4f27f17ea07d7419d45dae for rbtree.c Linux commit till f4b477c47332367d35686bd2b808c2156b96d7c7 for rbtree.h Signed-off-by: Praveen Kumar --- xen/common/rbtree.c | 633 ++++++++++++++++++++++++----------------------- xen/include/xen/rbtree.h | 116 +++++++-- 2 files changed, 413 insertions(+), 336 deletions(-) diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c index d91d651d77..167ebfdc4d 100644 --- a/xen/common/rbtree.c +++ b/xen/common/rbtree.c @@ -14,7 +14,8 @@ GNU General Public License for more details. You should have received a copy of the GNU General Public License - along with this program; If not, see . + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA linux/lib/rbtree.c */ @@ -24,261 +25,261 @@ static void __rb_rotate_left(struct rb_node *node, struct rb_root *root) { - struct rb_node *right = node->rb_right; - struct rb_node *parent = rb_parent(node); - - if ((node->rb_right = right->rb_left)) - rb_set_parent(right->rb_left, node); - right->rb_left = node; - - rb_set_parent(right, parent); - - if (parent) - { - if (node == parent->rb_left) - parent->rb_left = right; - else - parent->rb_right = right; - } - else - root->rb_node = right; - rb_set_parent(node, right); + struct rb_node *right = node->rb_right; + struct rb_node *parent = rb_parent(node); + + if ((node->rb_right = right->rb_left)) + rb_set_parent(right->rb_left, node); + right->rb_left = node; + + rb_set_parent(right, parent); + + if (parent) + { + if (node == parent->rb_left) + parent->rb_left = right; + else + parent->rb_right = right; + } + else + root->rb_node = right; + rb_set_parent(node, right); } static void __rb_rotate_right(struct rb_node *node, struct rb_root *root) { - struct rb_node *left = node->rb_left; - struct rb_node *parent = rb_parent(node); - - if ((node->rb_left = left->rb_right)) - rb_set_parent(left->rb_right, node); - left->rb_right = node; - - rb_set_parent(left, parent); - - if (parent) - { - if (node == parent->rb_right) - parent->rb_right = left; - else - parent->rb_left = left; - } - else - root->rb_node = left; - rb_set_parent(node, left); + struct rb_node *left = node->rb_left; + struct rb_node *parent = rb_parent(node); + + if ((node->rb_left = left->rb_right)) + rb_set_parent(left->rb_right, node); + left->rb_right = node; + + rb_set_parent(left, parent); + + if (parent) + { + if (node == parent->rb_right) + parent->rb_right = left; + else + parent->rb_left = left; + } + else + root->rb_node = left; + rb_set_parent(node, left); } void rb_insert_color(struct rb_node *node, struct rb_root *root) { - struct rb_node *parent, *gparent; - - while ((parent = rb_parent(node)) && rb_is_red(parent)) - { - gparent = rb_parent(parent); - - if (parent == gparent->rb_left) - { - { - register struct rb_node *uncle = gparent->rb_right; - if (uncle && rb_is_red(uncle)) - { - rb_set_black(uncle); - rb_set_black(parent); - rb_set_red(gparent); - node = gparent; - continue; - } - } - - if (parent->rb_right == node) - { - register struct rb_node *tmp; - __rb_rotate_left(parent, root); - tmp = parent; - parent = node; - node = tmp; - } - - rb_set_black(parent); - rb_set_red(gparent); - __rb_rotate_right(gparent, root); - } else { - { - register struct rb_node *uncle = gparent->rb_left; - if (uncle && rb_is_red(uncle)) - { - rb_set_black(uncle); - rb_set_black(parent); - rb_set_red(gparent); - node = gparent; - continue; - } - } - - if (parent->rb_left == node) - { - register struct rb_node *tmp; - __rb_rotate_right(parent, root); - tmp = parent; - parent = node; - node = tmp; - } - - rb_set_black(parent); - rb_set_red(gparent); - __rb_rotate_left(gparent, root); - } - } - - rb_set_black(root->rb_node); + struct rb_node *parent, *gparent; + + while ((parent = rb_parent(node)) && rb_is_red(parent)) + { + gparent = rb_parent(parent); + + if (parent == gparent->rb_left) + { + { + register struct rb_node *uncle = gparent->rb_right; + if (uncle && rb_is_red(uncle)) + { + rb_set_black(uncle); + rb_set_black(parent); + rb_set_red(gparent); + node = gparent; + continue; + } + } + + if (parent->rb_right == node) + { + register struct rb_node *tmp; + __rb_rotate_left(parent, root); + tmp = parent; + parent = node; + node = tmp; + } + + rb_set_black(parent); + rb_set_red(gparent); + __rb_rotate_right(gparent, root); + } else { + { + register struct rb_node *uncle = gparent->rb_left; + if (uncle && rb_is_red(uncle)) + { + rb_set_black(uncle); + rb_set_black(parent); + rb_set_red(gparent); + node = gparent; + continue; + } + } + + if (parent->rb_left == node) + { + register struct rb_node *tmp; + __rb_rotate_right(parent, root); + tmp = parent; + parent = node; + node = tmp; + } + + rb_set_black(parent); + rb_set_red(gparent); + __rb_rotate_left(gparent, root); + } + } + + rb_set_black(root->rb_node); } EXPORT_SYMBOL(rb_insert_color); static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, - struct rb_root *root) + struct rb_root *root) { - struct rb_node *other; - - while ((!node || rb_is_black(node)) && node != root->rb_node) - { - if (parent->rb_left == node) - { - other = parent->rb_right; - if (rb_is_red(other)) - { - rb_set_black(other); - rb_set_red(parent); - __rb_rotate_left(parent, root); - other = parent->rb_right; - } - if ((!other->rb_left || rb_is_black(other->rb_left)) && - (!other->rb_right || rb_is_black(other->rb_right))) - { - rb_set_red(other); - node = parent; - parent = rb_parent(node); - } - else - { - if (!other->rb_right || rb_is_black(other->rb_right)) - { - rb_set_black(other->rb_left); - rb_set_red(other); - __rb_rotate_right(other, root); - other = parent->rb_right; - } - rb_set_color(other, rb_color(parent)); - rb_set_black(parent); - rb_set_black(other->rb_right); - __rb_rotate_left(parent, root); - node = root->rb_node; - break; - } - } - else - { - other = parent->rb_left; - if (rb_is_red(other)) - { - rb_set_black(other); - rb_set_red(parent); - __rb_rotate_right(parent, root); - other = parent->rb_left; - } - if ((!other->rb_left || rb_is_black(other->rb_left)) && - (!other->rb_right || rb_is_black(other->rb_right))) - { - rb_set_red(other); - node = parent; - parent = rb_parent(node); - } - else - { - if (!other->rb_left || rb_is_black(other->rb_left)) - { - rb_set_black(other->rb_right); - rb_set_red(other); - __rb_rotate_left(other, root); - other = parent->rb_left; - } - rb_set_color(other, rb_color(parent)); - rb_set_black(parent); - rb_set_black(other->rb_left); - __rb_rotate_right(parent, root); - node = root->rb_node; - break; - } - } - } - if (node) - rb_set_black(node); + struct rb_node *other; + + while ((!node || rb_is_black(node)) && node != root->rb_node) + { + if (parent->rb_left == node) + { + other = parent->rb_right; + if (rb_is_red(other)) + { + rb_set_black(other); + rb_set_red(parent); + __rb_rotate_left(parent, root); + other = parent->rb_right; + } + if ((!other->rb_left || rb_is_black(other->rb_left)) && + (!other->rb_right || rb_is_black(other->rb_right))) + { + rb_set_red(other); + node = parent; + parent = rb_parent(node); + } + else + { + if (!other->rb_right || rb_is_black(other->rb_right)) + { + rb_set_black(other->rb_left); + rb_set_red(other); + __rb_rotate_right(other, root); + other = parent->rb_right; + } + rb_set_color(other, rb_color(parent)); + rb_set_black(parent); + rb_set_black(other->rb_right); + __rb_rotate_left(parent, root); + node = root->rb_node; + break; + } + } + else + { + other = parent->rb_left; + if (rb_is_red(other)) + { + rb_set_black(other); + rb_set_red(parent); + __rb_rotate_right(parent, root); + other = parent->rb_left; + } + if ((!other->rb_left || rb_is_black(other->rb_left)) && + (!other->rb_right || rb_is_black(other->rb_right))) + { + rb_set_red(other); + node = parent; + parent = rb_parent(node); + } + else + { + if (!other->rb_left || rb_is_black(other->rb_left)) + { + rb_set_black(other->rb_right); + rb_set_red(other); + __rb_rotate_left(other, root); + other = parent->rb_left; + } + rb_set_color(other, rb_color(parent)); + rb_set_black(parent); + rb_set_black(other->rb_left); + __rb_rotate_right(parent, root); + node = root->rb_node; + break; + } + } + } + if (node) + rb_set_black(node); } void rb_erase(struct rb_node *node, struct rb_root *root) { - struct rb_node *child, *parent; - int color; - - if (!node->rb_left) - child = node->rb_right; - else if (!node->rb_right) - child = node->rb_left; - else - { - struct rb_node *old = node, *left; - - node = node->rb_right; - 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; - - child = node->rb_right; - parent = rb_parent(node); - color = rb_color(node); - - if (parent == old) { - parent = node; - } else { - if (child) - rb_set_parent(child, parent); - parent->rb_left = child; - } - - node->rb_parent_color = old->rb_parent_color; - node->rb_right = old->rb_right; - node->rb_left = old->rb_left; - - rb_set_parent(old->rb_left, node); - if (old->rb_right) - rb_set_parent(old->rb_right, node); - goto color; - } - - parent = rb_parent(node); - color = rb_color(node); - - 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; + struct rb_node *child, *parent; + int color; + + if (!node->rb_left) + child = node->rb_right; + else if (!node->rb_right) + child = node->rb_left; + else + { + struct rb_node *old = node, *left; + + node = node->rb_right; + 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; + + child = node->rb_right; + parent = rb_parent(node); + color = rb_color(node); + + if (parent == old) { + parent = node; + } else { + if (child) + rb_set_parent(child, parent); + parent->rb_left = child; + } + + node->rb_parent_color = old->rb_parent_color; + node->rb_right = old->rb_right; + node->rb_left = old->rb_left; + + rb_set_parent(old->rb_left, node); + if (old->rb_right) + rb_set_parent(old->rb_right, node); + goto color; + } + + parent = rb_parent(node); + color = rb_color(node); + + 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; color: - if (color == RB_BLACK) - __rb_erase_color(child, parent, root); + if (color == RB_BLACK) + __rb_erase_color(child, parent, root); } EXPORT_SYMBOL(rb_erase); @@ -287,104 +288,104 @@ EXPORT_SYMBOL(rb_erase); */ struct rb_node *rb_first(const struct rb_root *root) { - struct rb_node *n; - - n = root->rb_node; - if (!n) - return NULL; - while (n->rb_left) - n = n->rb_left; - return n; + struct rb_node *n; + + n = root->rb_node; + if (!n) + return NULL; + while (n->rb_left) + n = n->rb_left; + return n; } EXPORT_SYMBOL(rb_first); struct rb_node *rb_last(const struct rb_root *root) { - struct rb_node *n; - - n = root->rb_node; - if (!n) - return NULL; - while (n->rb_right) - n = n->rb_right; - return n; + struct rb_node *n; + + n = root->rb_node; + if (!n) + return NULL; + while (n->rb_right) + n = n->rb_right; + return n; } EXPORT_SYMBOL(rb_last); struct rb_node *rb_next(const struct rb_node *node) { - struct rb_node *parent; - - if (rb_parent(node) == node) - return NULL; - - /* If we have a right-hand child, go down and then left as far - as we can. */ - if (node->rb_right) { - node = node->rb_right; - while (node->rb_left) - node=node->rb_left; - return (struct rb_node *)node; - } - - /* No right-hand children. Everything down and left is - smaller than us, so any 'next' node must be in the general - direction of our parent. Go up the tree; any time the - ancestor is a right-hand child of its parent, keep going - up. First time it's a left-hand child of its parent, said - parent is our 'next' node. */ - while ((parent = rb_parent(node)) && node == parent->rb_right) - node = parent; - - return parent; + struct rb_node *parent; + + if (rb_parent(node) == node) + return NULL; + + /* If we have a right-hand child, go down and then left as far + as we can. */ + if (node->rb_right) { + node = node->rb_right; + while (node->rb_left) + node=node->rb_left; + return (struct rb_node *)node; + } + + /* No right-hand children. Everything down and left is + smaller than us, so any 'next' node must be in the general + direction of our parent. Go up the tree; any time the + ancestor is a right-hand child of its parent, keep going + up. First time it's a left-hand child of its parent, said + parent is our 'next' node. */ + while ((parent = rb_parent(node)) && node == parent->rb_right) + node = parent; + + return parent; } EXPORT_SYMBOL(rb_next); struct rb_node *rb_prev(const struct rb_node *node) { - struct rb_node *parent; - - if (rb_parent(node) == node) - return NULL; - - /* If we have a left-hand child, go down and then right as far - as we can. */ - if (node->rb_left) { - node = node->rb_left; - while (node->rb_right) - node=node->rb_right; - return (struct rb_node *)node; - } - - /* No left-hand children. Go up till we find an ancestor which - is a right-hand child of its parent */ - while ((parent = rb_parent(node)) && node == parent->rb_left) - node = parent; - - return parent; + struct rb_node *parent; + + if (rb_parent(node) == node) + return NULL; + + /* If we have a left-hand child, go down and then right as far + as we can. */ + if (node->rb_left) { + node = node->rb_left; + while (node->rb_right) + node=node->rb_right; + return (struct rb_node *)node; + } + + /* No left-hand children. Go up till we find an ancestor which + is a right-hand child of its parent */ + while ((parent = rb_parent(node)) && node == parent->rb_left) + node = parent; + + return parent; } EXPORT_SYMBOL(rb_prev); void rb_replace_node(struct rb_node *victim, struct rb_node *new, - struct rb_root *root) + struct rb_root *root) { - 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; - } - if (victim->rb_left) - rb_set_parent(victim->rb_left, new); - if (victim->rb_right) - rb_set_parent(victim->rb_right, new); - - /* Copy the pointers/colour from the victim to the replacement */ - *new = *victim; + 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; + } + if (victim->rb_left) + rb_set_parent(victim->rb_left, new); + if (victim->rb_right) + rb_set_parent(victim->rb_right, new); + + /* Copy the pointers/colour from the victim to the replacement */ + *new = *victim; } EXPORT_SYMBOL(rb_replace_node); diff --git a/xen/include/xen/rbtree.h b/xen/include/xen/rbtree.h index 3eb527eb37..9496f099f8 100644 --- a/xen/include/xen/rbtree.h +++ b/xen/include/xen/rbtree.h @@ -13,7 +13,82 @@ GNU General Public License for more details. You should have received a copy of the GNU General Public License - along with this program; If not, see . + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + + linux/include/linux/rbtree.h + + To use rbtrees you'll have to implement your own insert and search cores. + This will avoid us to use callbacks and to drop drammatically performances. + I know it's not the cleaner way, but in C (not in C++) to get + performances and genericity... + + Some example of insert and search follows here. The search is a plain + normal search over an ordered tree. The insert instead must be implemented + int two steps: as first thing the code must insert the element in + order as a red leaf in the tree, then the support library function + rb_insert_color() must be called. Such function will do the + not trivial work to rebalance the rbtree if necessary. + +----------------------------------------------------------------------- +static inline struct page * rb_search_page_cache(struct inode * inode, + unsigned long offset) +{ + struct rb_node * n = inode->i_rb_page_cache.rb_node; + struct page * page; + + while (n) + { + page = rb_entry(n, struct page, rb_page_cache); + + if (offset < page->offset) + n = n->rb_left; + else if (offset > page->offset) + n = n->rb_right; + else + return page; + } + return NULL; +} + +static inline struct page * __rb_insert_page_cache(struct inode * inode, + unsigned long offset, + struct rb_node * node) +{ + struct rb_node ** p = &inode->i_rb_page_cache.rb_node; + struct rb_node * parent = NULL; + struct page * page; + + while (*p) + { + parent = *p; + page = rb_entry(parent, struct page, rb_page_cache); + + if (offset < page->offset) + p = &(*p)->rb_left; + else if (offset > page->offset) + p = &(*p)->rb_right; + else + return page; + } + + rb_link_node(node, parent, p); + + return NULL; +} + +static inline struct page * rb_insert_page_cache(struct inode * inode, + unsigned long offset, + struct rb_node * node) +{ + struct page * ret; + if ((ret = __rb_insert_page_cache(inode, offset, node))) + goto out; + rb_insert_color(node, &inode->i_rb_page_cache); + out: + return ret; +} +----------------------------------------------------------------------- */ #ifndef __RBTREE_H__ @@ -21,16 +96,17 @@ struct rb_node { - unsigned long rb_parent_color; -#define RB_RED 0 -#define RB_BLACK 1 - struct rb_node *rb_right; - struct rb_node *rb_left; -}; + unsigned long rb_parent_color; +#define RB_RED 0 +#define RB_BLACK 1 + struct rb_node *rb_right; + struct rb_node *rb_left; +} __attribute__((aligned(sizeof(long)))); + /* The alignment might seem pointless, but allegedly CRIS needs it */ struct rb_root { - struct rb_node *rb_node; + struct rb_node *rb_node; }; #define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3)) @@ -42,19 +118,19 @@ struct rb_root static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) { - rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p; + rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p; } static inline void rb_set_color(struct rb_node *rb, int color) { - rb->rb_parent_color = (rb->rb_parent_color & ~1) | color; + rb->rb_parent_color = (rb->rb_parent_color & ~1) | color; } -#define RB_ROOT (struct rb_root) { NULL, } -#define rb_entry(ptr, type, member) container_of(ptr, type, member) +#define RB_ROOT (struct rb_root) { NULL, } +#define rb_entry(ptr, type, member) container_of(ptr, type, member) -#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL) -#define RB_EMPTY_NODE(node) (rb_parent(node) == node) -#define RB_CLEAR_NODE(node) (rb_set_parent(node, node)) +#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL) +#define RB_EMPTY_NODE(node) (rb_parent(node) == node) +#define RB_CLEAR_NODE(node) (rb_set_parent(node, node)) extern void rb_insert_color(struct rb_node *, struct rb_root *); extern void rb_erase(struct rb_node *, struct rb_root *); @@ -67,15 +143,15 @@ extern struct rb_node *rb_last(const struct rb_root *); /* Fast replacement of a single node without remove/rebalance/add/rebalance */ extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, - struct rb_root *root); + struct rb_root *root); static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, - struct rb_node ** rb_link) + struct rb_node ** rb_link) { - node->rb_parent_color = (unsigned long )parent; - node->rb_left = node->rb_right = NULL; + node->rb_parent_color = (unsigned long )parent; + node->rb_left = node->rb_right = NULL; - *rb_link = node; + *rb_link = node; } #endif /* __RBTREE_H__ */