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 11/17] rbtree: low level optimizations in __rb_erase_color()
Date: Thu, 1 Jun 2017 02:50:50 +0530 [thread overview]
Message-ID: <20170531212056.10583-12-kpraveen.lkml@gmail.com> (raw)
In-Reply-To: <20170531212056.10583-1-kpraveen.lkml@gmail.com>
In __rb_erase_color(), we often already have pointers to the nodes being
rotated and/or know what their colors must be, so we can generate more
efficient code than the generic __rb_rotate_left() and __rb_rotate_right()
functions.
Also when the current node is red or when flipping the sibling's color,
the parent is already known so we can use the more efficient
rb_set_parent_color() function to set the desired color.
commit 6280d2356fd8ad0936a63c10dc1e6accf48d0c61 from linux tree
Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
---
xen/common/rbtree.c | 197 ++++++++++++++++++++++++++++------------------------
1 file changed, 107 insertions(+), 90 deletions(-)
diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 1e4cb1ed2c..253861d889 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -38,7 +38,8 @@
* 5), then the longest possible path due to 4 is 2B.
*
* We shall indicate color with case, where black nodes are uppercase and red
- * nodes will be lowercase.
+ * nodes will be lowercase. Unknown color nodes shall be drawn as red within
+ * parentheses and have some accompanying text comment.
*/
#define RB_RED 0
@@ -47,17 +48,11 @@
#define rb_color(r) ((r)->__rb_parent_color & 1)
#define rb_is_red(r) (!rb_color(r))
#define rb_is_black(r) rb_color(r)
-#define rb_set_red(r) do { (r)->__rb_parent_color &= ~1; } while (0)
-#define rb_set_black(r) do { (r)->__rb_parent_color |= 1; } while (0)
static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
{
rb->__rb_parent_color = rb_color(rb) | (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;
-}
static inline void rb_set_parent_color(struct rb_node *rb,
struct rb_node *p, int color)
@@ -70,52 +65,6 @@ static inline struct rb_node *rb_red_parent(struct rb_node *red)
return (struct rb_node *)red->__rb_parent_color;
}
-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);
-}
-
-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);
-}
-
/*
* Helper function for rotations:
* - old's parent and color get assigned to new
@@ -260,7 +209,7 @@ EXPORT_SYMBOL(rb_insert_color);
static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
struct rb_root *root)
{
- struct rb_node *other;
+ struct rb_node *sibling, *tmp1, *tmp2;
while (true)
{
@@ -275,68 +224,136 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
*/
if (node && rb_is_red(node))
{
- rb_set_black(node);
+ rb_set_parent_color(node, parent, RB_BLACK);
break;
} else if (!parent) {
break;
} else 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;
+ sibling = parent->rb_right;
+ if (rb_is_red(sibling)) {
+ /*
+ * Case 1 - left rotate at parent
+ *
+ * P S
+ * / \ / \
+ * N s --> p Sr
+ * / \ / \
+ * Sl Sr N Sl
+ */
+ parent->rb_right = tmp1 = sibling->rb_left;
+ sibling->rb_left = parent;
+ rb_set_parent_color(tmp1, parent, RB_BLACK);
+ __rb_rotate_set_parents(parent, sibling, root, RB_RED);
+ sibling = tmp1;
}
- if (!other->rb_right || rb_is_black(other->rb_right))
+ tmp1 = sibling->rb_right;
+ if (!tmp1 || rb_is_black(tmp1))
{
- if (!other->rb_left || rb_is_black(other->rb_left))
+ tmp2 = sibling->rb_left;
+ if (!tmp2 || rb_is_black(tmp2))
{
- rb_set_red(other);
+ /*
+ * Case 2 - sibling color flip
+ * (p could be either color here)
+ *
+ * (p) (p)
+ * / \ / \
+ * N S --> N s
+ * / \ / \
+ * Sl Sr Sl Sr
+ *
+ * This leaves us violating 5), so
+ * recurse at p. If p is red, the
+ * recursion will just flip it to black
+ * and exit. If coming from Case 1,
+ * p is known to be red.
+ */
+ rb_set_parent_color(sibling, parent, RB_RED);
node = parent;
parent = rb_parent(node);
continue;
}
- rb_set_black(other->rb_left);
- rb_set_red(other);
- __rb_rotate_right(other, root);
- other = parent->rb_right;
+ /*
+ * Case 3 - right rotate at sibling
+ * (p could be either color here)
+ *
+ * (p) (p)
+ * / \ / \
+ * N S --> N Sl
+ * / \ \
+ * sl Sr s
+ * \
+ * Sr
+ */
+ sibling->rb_left = tmp1 = tmp2->rb_right;
+ tmp2->rb_right = sibling;
+ parent->rb_right = tmp2;
+ if (tmp1)
+ rb_set_parent_color(tmp1, sibling, RB_BLACK);
+ tmp1 = sibling;
+ sibling = tmp2;
}
- rb_set_color(other, rb_color(parent));
- rb_set_black(parent);
- rb_set_black(other->rb_right);
- __rb_rotate_left(parent, root);
+ /*
+ * Case 4 - left rotate at parent + color flips
+ * (p and sl could be either color here.
+ * After rotation, p becomes black, s acquires
+ * p's color, and sl keeps its color)
+ *
+ * (p) (s)
+ * / \ / \
+ * N S --> P Sr
+ * / \ / \
+ * (sl) sr N (sl)
+ */
+ parent->rb_right = tmp2 = sibling->rb_left;
+ sibling->rb_left = parent;
+ rb_set_parent_color(tmp1, sibling, RB_BLACK);
+ if (tmp2)
+ rb_set_parent(tmp2, parent);
+ __rb_rotate_set_parents(parent, sibling, root, RB_BLACK);
break;
}
else
{
- other = parent->rb_left;
- if (rb_is_red(other))
+ sibling = parent->rb_left;
+ if (rb_is_red(sibling))
{
- rb_set_black(other);
- rb_set_red(parent);
- __rb_rotate_right(parent, root);
- other = parent->rb_left;
+ /* Case 1 - right rotate at parent */
+ parent->rb_left = tmp1 = sibling->rb_right;
+ sibling->rb_right = parent;
+ rb_set_parent_color(tmp1, parent, RB_BLACK);
+ __rb_rotate_set_parents(parent, sibling, root, RB_RED);
+ sibling = tmp1;
}
- if (!other->rb_left || rb_is_black(other->rb_left))
+ tmp1 = sibling->rb_left;
+ if (!tmp1 || rb_is_black(tmp1))
{
- if (!other->rb_right || rb_is_black(other->rb_right))
+ tmp2 = sibling->rb_right;
+ if (!tmp2 || rb_is_black(tmp2))
{
- rb_set_red(other);
+ /* Case 2 - sibling color flip */
+ rb_set_parent_color(sibling, parent, RB_RED);
node = parent;
parent = rb_parent(node);
continue;
}
- rb_set_black(other->rb_right);
- rb_set_red(other);
- __rb_rotate_left(other, root);
- other = parent->rb_left;
+ /* Case 3 - right rotate at sibling */
+ sibling->rb_right = tmp1 = tmp2->rb_left;
+ tmp2->rb_left = sibling;
+ parent->rb_left = tmp2;
+ if (tmp1)
+ rb_set_parent_color(tmp1, sibling, RB_BLACK);
+ tmp1 = sibling;
+ sibling = tmp2;
}
- rb_set_color(other, rb_color(parent));
- rb_set_black(parent);
- rb_set_black(other->rb_left);
- __rb_rotate_right(parent, root);
+ /* Case 4 - left rotate at parent + color flips */
+ parent->rb_left = tmp2 = sibling->rb_right;
+ sibling->rb_right = parent;
+ rb_set_parent_color(tmp1, sibling, RB_BLACK);
+ if (tmp2)
+ rb_set_parent(tmp2, parent);
+ __rb_rotate_set_parents(parent, sibling, root, RB_BLACK);
break;
}
}
--
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 ` Praveen Kumar [this message]
2017-05-31 21:20 ` [Resend][PATCH 12/17] rbtree: optimize fetching of sibling node Praveen Kumar
2017-05-31 21:20 ` [Resend][PATCH 13/17] rbtree: add __rb_change_child() helper function Praveen Kumar
2017-06-12 16:14 ` 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-12-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).