From patchwork Fri Jul 14 14:57:50 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Praveen Kumar X-Patchwork-Id: 9841279 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 E20DE602BD for ; Fri, 14 Jul 2017 15:00:46 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id C620428799 for ; Fri, 14 Jul 2017 15:00:46 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id BAB35287A0; Fri, 14 Jul 2017 15:00:46 +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 DAF882879E for ; Fri, 14 Jul 2017 15:00:43 +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 1dW22d-0002w8-RD; Fri, 14 Jul 2017 14:58:03 +0000 Received: from mail6.bemta5.messagelabs.com ([195.245.231.135]) by lists.xenproject.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dW22c-0002w2-7h for xen-devel@lists.xen.org; Fri, 14 Jul 2017 14:58:02 +0000 Received: from [85.158.139.211] by server-3.bemta-5.messagelabs.com id E0/7F-02022-9FBD8695; Fri, 14 Jul 2017 14:58:01 +0000 X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFtrMIsWRWlGSWpSXmKPExsVyMfTAEd0ftzM iDU68FLFY8nExiwOjx9Hdv5kCGKNYM/OS8isSWDOuzr7MUnBhJ2PFkl9TWRsY57QzdjFycQgJ TGKU+P9hLguIwyLwkkVi2rVW1i5GTg4JgX5WibenXCDsOIlrCx8zQtgVEotffWADsYUE1CS2z DvFDDGpkUmi5/Q2pi5GDg42AV2J9lsFIDUiAtIS1z5fBtvGLPCdUWLN+ylgC4QFvCU+9WwDG8 QioCrx9Vg3G0gvr4C1xN7JFRC75CUWbZrBAmJzCthKNGzbygyx10Zi/cnjzBMYBRYwMqxi1Ch OLSpLLdI1NNNLKspMzyjJTczM0TU0MNXLTS0uTkxPzUlMKtZLzs/dxAgMLgYg2MF4/rTnIUZJ DiYlUd6gqRmRQnxJ+SmVGYnFGfFFpTmpxYcYZTg4lCR49YDBKiRYlJqeWpGWmQMMc5i0BAePk gjvbJA0b3FBYm5xZjpE6hSjPceVK+u+MHEs6NkAJKcc2A4kX034/41JiCUvPy9VSpxXFqRNAK QtozQPbigsLi8xykoJ8zICnSnEU5BalJtZgir/ilGcg1FJmFcXZApPZl4J3O5XQGcxAZ3VlgV 2VkkiQkqqgXFXeVjuote7tyTNbJzY2e3Y7e6s7MPkv+Doa8WfQcv3f3hyYvn/pfNui97gOnC/ vm5mvpbixDvMlq+UT7pd+TQ90H5P/7YJnS6fWjj69jYa171bbfWyz0Pr8uTiyYFRt9Nd5p5z3 KXVXDvDuldkk5mpdvybbecPmXzhye2cLs7JHf9ojr7WexclluKMREMt5qLiRAAFJtcixgIAAA == X-Env-Sender: kpraveen.lkml@gmail.com X-Msg-Ref: server-8.tower-206.messagelabs.com!1500044278!102797454!1 X-Originating-IP: [209.85.192.196] 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 35258 invoked from network); 14 Jul 2017 14:57:59 -0000 Received: from mail-pf0-f196.google.com (HELO mail-pf0-f196.google.com) (209.85.192.196) by server-8.tower-206.messagelabs.com with AES128-GCM-SHA256 encrypted SMTP; 14 Jul 2017 14:57:59 -0000 Received: by mail-pf0-f196.google.com with SMTP id c24so11297270pfe.1 for ; Fri, 14 Jul 2017 07:57:59 -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=6wT+8DiNvOSt21CwIditvjw8B82ORYA6vYLw7oVPp9k=; b=tIeUjkxTjvGwwXrPPksLAQ837uqoLa8F9N+vLNnCZ03/RA1T8xvZOVWYSwZmTNqSML aytjQn/GJM5K4QnTX77+Cz907S4xWjUbuOTHA+2a3CeDUrB4QofVwlBE/+dHwtJTAY4n UlRRcA9PRfbDZ7COjBbwERhhz9rSIPje92jvWnU7VulV1UF1jI7g0PijLQLpZbkdSt4/ aaRhH4/NexGDIStlbgynaMdEb5DsEP6C/GbgUjF15am68CLXe63PU6/RWRJqHfqcJ+T1 fCGZzGTC8MokZRmNd4vef87r3eLj6gQec4vsWp6GalpSMHRl6huzHBWVDE4iOw6SRSsN X5/A== 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=6wT+8DiNvOSt21CwIditvjw8B82ORYA6vYLw7oVPp9k=; b=W0V7fypE5EwWrSuile1AteSxO1Q0GmByQGn/YUYD3GnhCwaEbQ7SQ8VOPATQnioxsj 52OaTeNm9x1DKF1cFl0kNFCpIwFj2XAjvQOQ+SWyngQJcMi3YawNX1UaGezO1arrICfS wW9+iwZlDbAQMCJyIbQryfPXLXqdEJtvFyPhTdHU48yQ8SozBiprszoRKtsQ3E+lRwOJ nOwvh/torYmZfaha9RkET6YS7LcYanXn/jEshS5kENT/PBip55A041Y+rkc7TRDv4Rh5 HT9WiynjMd4A4TIl7hf5E8tFiDy8ihQ+R5GWCI9urk4gMNEc8Rf+Wl3yT38O19xt0lom hGcQ== X-Gm-Message-State: AIVw110RcGKs0BAyv/arp2c9WqkRj2tx/DDB40rKoVKHLiZWPDqnrL8I KNOFV5iZYPhqh+Hd X-Received: by 10.84.229.7 with SMTP id b7mr16519626plk.216.1500044277845; Fri, 14 Jul 2017 07:57:57 -0700 (PDT) Received: from kpraveen.labs.blr.novell.com ([117.192.28.144]) by smtp.gmail.com with ESMTPSA id r84sm18532528pfa.57.2017.07.14.07.57.51 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Fri, 14 Jul 2017 07:57:56 -0700 (PDT) From: Praveen Kumar To: xen-devel@lists.xen.org Date: Fri, 14 Jul 2017 20:27:50 +0530 Message-Id: <20170714145750.2943-1-kpraveen.lkml@gmail.com> X-Mailer: git-send-email 2.12.0 In-Reply-To: <20170714134736.29719-1-kpraveen.lkml@gmail.com> References: <20170714134736.29719-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 v7 01/17] rbtree: changes to align the code 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 code of rbtree related files with Linux tree. This will minimize the conflicts during any future porting from Linux tree. Linux commit till f4b477c47332367d35686bd2b808c2156b96d7c7 for rbtree.h This includes addition of commented inline functions in rbtree.h, to have complete replica from Linux tree. Linux commit till 4c60117811171d867d4f27f17ea07d7419d45dae for rbtree.c This includes updates in comments in header note in rbtree.c. 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__ */