lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
Open Source and information security mailing list archives
| ||
|
Date: Thu, 2 Aug 2012 15:34:11 -0700 From: Michel Lespinasse <walken@...gle.com> To: riel@...hat.com, peterz@...radead.org, daniel.santos@...ox.com, aarcange@...hat.com, dwmw2@...radead.org, akpm@...ux-foundation.org Cc: linux-mm@...ck.org, linux-kernel@...r.kernel.org, torvalds@...ux-foundation.org Subject: [PATCH v2 2/9] rbtree: optimize fetching of sibling node 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 <walken@...gle.com> --- lib/rbtree.c | 21 +++++++++++++-------- 1 files changed, 13 insertions(+), 8 deletions(-) diff --git a/lib/rbtree.c b/lib/rbtree.c index 0892670..61cdd0e 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -107,8 +107,8 @@ 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; + tmp = gparent->rb_right; + if (parent != tmp) { /* parent == gparent->rb_left */ if (tmp && rb_is_red(tmp)) { /* * Case 1 - color flips @@ -131,7 +131,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 * @@ -151,6 +152,7 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) RB_BLACK); rb_set_parent_color(parent, node, RB_RED); parent = node; + tmp = node->rb_right; } /* @@ -162,7 +164,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); @@ -180,7 +182,8 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) continue; } - if (parent->rb_left == node) { + tmp = parent->rb_left; + if (node == tmp) { /* Case 2 - right rotate at parent */ parent->rb_left = tmp = node->rb_right; node->rb_right = parent; @@ -189,10 +192,11 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root) RB_BLACK); rb_set_parent_color(parent, node, RB_RED); parent = node; + tmp = node->rb_left; } /* Case 3 - left rotate at gparent */ - gparent->rb_right = tmp = parent->rb_left; + gparent->rb_right = tmp; /* == parent->rb_left */ parent->rb_left = gparent; if (tmp) rb_set_parent_color(tmp, gparent, RB_BLACK); @@ -223,8 +227,9 @@ 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)) { /* * Case 1 - left rotate at parent -- 1.7.7.3 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@...r.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists