When looking to fetch a node's sibling, we went through a sequence of:
- check if node is the parent's left child
- if it is, then fetch the parent's right child
This can be replaced with:
- fetch the parent's right child as an assumed sibling
- check that node is NOT the fetched child
This avoids fetching the parent's left child when node is actually
that child. Saves a bit on code size, though it doesn't seem to make
a large difference in speed.
Signed-off-by: Michel Lespinasse <wal...@google.com>
Cc: Andrea Arcangeli <aarca...@redhat.com>
Cc: David Woodhouse <david.woodho...@intel.com>
Acked-by: Rik van Riel <r...@redhat.com>
Cc: Peter Zijlstra <a.p.zijls...@chello.nl>
Cc: Daniel Santos <daniel.san...@pobox.com>
Cc: Jens Axboe <ax...@kernel.dk>
Cc: "Eric W. Biederman" <ebied...@xmission.com>
Signed-off-by: Andrew Morton <a...@linux-foundation.org>
Signed-off-by: Linus Torvalds <torva...@linux-foundation.org>
[Linux commit 59633abf34e2f44b8e772a2c12a92132aa7c2220]
Ported to Xen.
Signed-off-by: Praveen Kumar <kpraveen.l...@gmail.com>
---
xen/common/rbtree.c | 15 +++++++++------
1 file changed, 9 insertions(+), 6 deletions(-)
diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
index 1cbe9a53d7..8c28ab1967 100644
--- a/xen/common/rbtree.c
+++ b/xen/common/rbtree.c
@@ -108,9 +108,9 @@ void rb_insert_color(struct rb_node *node, struct rb_root
*root)
gparent = rb_red_parent(parent);
- if (parent == gparent->rb_left)
+ tmp = gparent->rb_right;
+ if (parent != tmp) /* parent == gparent->rb_left */
{
- tmp = gparent->rb_right;
if (tmp && rb_is_red(tmp))
{
/*
@@ -134,7 +134,8 @@ void rb_insert_color(struct rb_node *node, struct rb_root
*root)
continue;
}
- if (parent->rb_right == node)
+ tmp = parent->rb_right;
+ if (node == tmp)
{
/*
* Case 2 - left rotate at parent
@@ -164,7 +165,7 @@ void rb_insert_color(struct rb_node *node, struct rb_root
*root)
* / \
* n U
*/
- gparent->rb_left = tmp = parent->rb_right;
+ gparent->rb_left = tmp; /* == parent->rb_right */
parent->rb_right = gparent;
if (tmp)
rb_set_parent_color(tmp, gparent, RB_BLACK);
@@ -227,8 +228,10 @@ static void __rb_erase_color(struct rb_node *node, struct
rb_node *parent,
break;
} else if (!parent) {
break;
- } else if (parent->rb_left == node) {
- sibling = parent->rb_right;
+ }
+ sibling = parent->rb_right;
+ if ( node != sibling) /* node == parent->rb_left */
+ {
if (rb_is_red(sibling))
{
/*
--
2.12.0
_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel
