From: Praveen Kumar <kpraveen.lkml@gmail.com>
To: xen-devel@lists.xen.org
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, Praveen Kumar <kpraveen.lkml@gmail.com>,
jbeulich@suse.com
Subject: [Resend][PATCH 13/17] rbtree: add __rb_change_child() helper function
Date: Thu, 1 Jun 2017 02:50:52 +0530 [thread overview]
Message-ID: <20170531212056.10583-14-kpraveen.lkml@gmail.com> (raw)
In-Reply-To: <20170531212056.10583-1-kpraveen.lkml@gmail.com>
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.
commit 7abc704ae399fcb9c51ca200b0456f8a975a8011 from Linux tree
Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
---
xen/common/rbtree.c | 54 ++++++++++++++++++++++-------------------------------
1 file changed, 22 insertions(+), 32 deletions(-)
diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index b65f00ca1f..3b54c04bea 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -65,6 +65,22 @@ 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 +93,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)
@@ -381,14 +391,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);
@@ -418,15 +421,8 @@ 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)
@@ -523,14 +519,8 @@ 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)
--
2.12.0
_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel
next prev parent reply other threads:[~2017-05-31 21:20 UTC|newest]
Thread overview: 34+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-05-31 21:20 [Xen-devel[PATCH Resend v2] xen: common: rbtree: ported updates from linux tree Praveen Kumar
2017-05-31 21:20 ` [Resend][PATCH 01/17] rb_tree: reorganize code in rb_erase() for additional changes Praveen Kumar
2017-05-31 22:40 ` Dario Faggioli
2017-05-31 22:56 ` Andrew Cooper
2017-06-01 8:01 ` Dario Faggioli
2017-06-02 16:28 ` Praveen Kumar
2017-06-08 15:57 ` Jan Beulich
2017-05-31 21:20 ` [Resend][PATCH 02/17] rb_tree: make clear distinction between two different cases in rb_erase() Praveen Kumar
2017-05-31 21:20 ` [Resend][PATCH 03/17] rb_tree: remove redundant if()-condition " Praveen Kumar
2017-05-31 21:20 ` [Resend][PATCH 04/17] rbtree: empty nodes have no color Praveen Kumar
2017-06-12 16:42 ` Dario Faggioli
2017-06-13 8:21 ` Jan Beulich
2017-05-31 21:20 ` [Resend][PATCH 05/17] rbtree: move some implementation details from rbtree.h to rbtree.c Praveen Kumar
2017-05-31 21:20 ` [Resend][PATCH 06/17] rbtree: break out of rb_insert_color loop after tree rotation Praveen Kumar
2017-06-12 16:41 ` Dario Faggioli
2017-05-31 21:20 ` [Resend][PATCH 07/17] rbtree: adjust root color in rb_insert_color() only when necessary Praveen Kumar
2017-05-31 21:20 ` [Resend][PATCH 08/17] rbtree: low level optimizations in rb_insert_color() Praveen Kumar
2017-05-31 21:20 ` [Resend][PATCH 09/17] rbtree: adjust node color in __rb_erase_color() only when necessary Praveen Kumar
2017-05-31 21:20 ` [Resend][PATCH 10/17] rbtree: optimize case selection logic in __rb_erase_color() Praveen Kumar
2017-05-31 21:20 ` [Resend][PATCH 11/17] rbtree: low level optimizations " Praveen Kumar
2017-05-31 21:20 ` [Resend][PATCH 12/17] rbtree: optimize fetching of sibling node Praveen Kumar
2017-05-31 21:20 ` Praveen Kumar [this message]
2017-06-12 16:14 ` [Resend][PATCH 13/17] rbtree: add __rb_change_child() helper function Dario Faggioli
2017-05-31 21:20 ` [Resend][PATCH 14/17] rbtree: place easiest case first in rb_erase() Praveen Kumar
2017-06-12 16:19 ` Dario Faggioli
2017-05-31 21:20 ` [Resend][PATCH 15/17] rbtree: handle 1-child recoloring in rb_erase() instead of rb_erase_color() Praveen Kumar
2017-05-31 21:20 ` [Resend][PATCH 16/17] rbtree: low level optimizations in rb_erase() Praveen Kumar
2017-05-31 21:20 ` [Resend][PATCH 17/17] rbtree: add postorder iteration functions Praveen Kumar
2017-05-31 22:34 ` [Xen-devel[PATCH Resend v2] xen: common: rbtree: ported updates from linux tree Dario Faggioli
2017-06-01 7:26 ` Jan Beulich
2017-06-01 7:43 ` Dario Faggioli
2017-06-02 16:35 ` Praveen Kumar
2017-06-02 16:31 ` Praveen Kumar
2017-06-12 16:44 ` Dario Faggioli
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20170531212056.10583-14-kpraveen.lkml@gmail.com \
--to=kpraveen.lkml@gmail.com \
--cc=George.Dunlap@eu.citrix.com \
--cc=andrew.cooper3@citrix.com \
--cc=dario.faggioli@citrix.com \
--cc=ian.jackson@eu.citrix.com \
--cc=jbeulich@suse.com \
--cc=sstabellini@kernel.org \
--cc=tim@xen.org \
--cc=wei.liu2@citrix.com \
--cc=xen-devel@lists.xen.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).