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 16/17] rbtree: low level optimizations in rb_erase()
Date: Thu, 1 Jun 2017 02:50:55 +0530 [thread overview]
Message-ID: <20170531212056.10583-17-kpraveen.lkml@gmail.com> (raw)
In-Reply-To: <20170531212056.10583-1-kpraveen.lkml@gmail.com>
Various minor optimizations in rb_erase():
- Avoid multiple loading of node->__rb_parent_color when computing parent
and color information (possibly not in close sequence, as there might
be further branches in the algorithm)
- In the 1-child subcase of case 1, copy the __rb_parent_color field from
the erased node to the child instead of recomputing it from the desired
parent and color
- When searching for the erased node's successor, differentiate between
cases 2 and 3 based on whether any left links were followed. This avoids
a condition later down.
- In case 3, keep a pointer to the erased node's right child so we don't
have to refetch it later to adjust its parent.
- In the no-childs subcase of cases 2 and 3, place the rebalance assigment
last so that the compiler can remove the following if(rebalance) test.
Also, added some comments to illustrate cases 2 and 3.
commit 4f035ad67f4633c233cb3642711d49b4efc9c82d from Linux tree
Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
---
xen/common/rbtree.c | 102 ++++++++++++++++++++++++++++++++++------------------
1 file changed, 67 insertions(+), 35 deletions(-)
diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 6e37e960ab..83b4892f54 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -46,9 +46,14 @@
#define RB_RED 0
#define RB_BLACK 1
-#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_parent(pc) ((struct rb_node *)(pc & ~3))
+
+#define __rb_color(pc) ((pc) & 1)
+#define __rb_is_black(pc) __rb_color(pc)
+#define __rb_is_red(pc) (!__rb_color(pc))
+#define rb_color(rb) __rb_color((rb)->__rb_parent_color)
+#define rb_is_red(rb) __rb_is_red((rb)->__rb_parent_color)
+#define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color)
static inline void rb_set_black(struct rb_node *rb)
{
@@ -387,6 +392,7 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
{
struct rb_node *child = node->rb_right, *tmp = node->rb_left;
struct rb_node *parent, *rebalance;
+ unsigned long pc;
if (!tmp)
{
@@ -398,53 +404,79 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
* so as to bypass __rb_erase_color() later on.
*/
- parent = rb_parent(node);
+ pc = node->__rb_parent_color;
+ parent = __rb_parent(pc);
__rb_change_child(node, child, parent, root);
if (child)
{
- rb_set_parent_color(child, parent, RB_BLACK);
+ child->__rb_parent_color = pc;
rebalance = NULL;
- } else {
- rebalance = rb_is_black(node) ? parent : NULL;
- }
+ } else
+ rebalance = __rb_is_black(pc) ? parent : NULL;
} else if (!child) {
/* Still case 1, but this time the child is node->rb_left */
- parent = rb_parent(node);
+ tmp->__rb_parent_color = pc = node->__rb_parent_color;
+ parent = __rb_parent(pc);
__rb_change_child(node, tmp, parent, root);
- rb_set_parent_color(tmp, parent, RB_BLACK);
rebalance = NULL;
} else {
- struct rb_node *old = node, *left;
-
- node = child;
- while ((left = node->rb_left) != NULL)
- node = left;
-
- __rb_change_child(old, node, rb_parent(old), root);
-
- child = node->rb_right;
- parent = rb_parent(node);
-
- if (parent == old) {
- parent = node;
+ struct rb_node *successor = child, *child2;
+ tmp = child->rb_left;
+ if (!tmp)
+ {
+ /*
+ * Case 2: node's successor is its right child
+ *
+ * (n) (s)
+ * / \ / \
+ * (x) (s) -> (x) (c)
+ * \
+ * (c)
+ */
+ parent = child;
+ child2 = child->rb_right;
} else {
- parent->rb_left = child;
-
- node->rb_right = old->rb_right;
- rb_set_parent(old->rb_right, node);
+ /*
+ * Case 3: node's successor is leftmost under
+ * node's right child subtree
+ *
+ * (n) (s)
+ * / \ / \
+ * (x) (y) -> (x) (y)
+ * / /
+ * (p) (p)
+ * / /
+ * (s) (c)
+ * \
+ * (c)
+ */
+ do
+ {
+ parent = successor;
+ successor = tmp;
+ tmp = tmp->rb_left;
+ } while (tmp);
+ parent->rb_left = child2 = successor->rb_right;
+ successor->rb_right = child;
+ rb_set_parent(child, successor);
}
- if (child) {
- rb_set_parent_color(child, parent, RB_BLACK);
+ successor->rb_left = tmp = node->rb_left;
+ rb_set_parent(tmp, successor);
+
+ pc = node->__rb_parent_color;
+ tmp = __rb_parent(pc);
+ __rb_change_child(node, successor, tmp, root);
+ if (child2)
+ {
+ successor->__rb_parent_color = pc;
+ rb_set_parent_color(child2, parent, RB_BLACK);
rebalance = NULL;
} else {
- rebalance = rb_is_black(node) ? parent : NULL;
+ unsigned long pc2 = successor->__rb_parent_color;
+ successor->__rb_parent_color = pc;
+ rebalance = __rb_is_black(pc2) ? parent : NULL;
}
-
- node->__rb_parent_color = old->__rb_parent_color;
- node->rb_left = old->rb_left;
-
- rb_set_parent(old->rb_left, node);
}
if (rebalance)
--
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 ` [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 ` Praveen Kumar [this message]
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-17-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).