From: Michel Lespinasse <walken@google.com>
To: aarcange@redhat.com, dwmw2@infradead.org, riel@redhat.com,
peterz@infradead.org, daniel.santos@pobox.com, axboe@kernel.dk,
ebiederm@xmission.com
Cc: linux-mm@kvack.org, akpm@linux-foundation.org,
linux-kernel@vger.kernel.org, torvalds@linux-foundation.org
Subject: [PATCH 13/13] rbtree: optimize color flips in __rb_erase_color()
Date: Mon, 9 Jul 2012 16:35:23 -0700 [thread overview]
Message-ID: <1341876923-12469-14-git-send-email-walken@google.com> (raw)
In-Reply-To: <1341876923-12469-1-git-send-email-walken@google.com>
In __rb_erase_color(), 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.
Signed-off-by: Michel Lespinasse <walken@google.com>
---
lib/rbtree.c | 10 +++++-----
1 files changed, 5 insertions(+), 5 deletions(-)
diff --git a/lib/rbtree.c b/lib/rbtree.c
index c956248..f8c1a75 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -29,8 +29,6 @@
#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)
{
@@ -170,7 +168,7 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
* and tree rotations as per one of the 4 cases below.
*/
if (node && rb_is_red(node)) {
- rb_set_black(node);
+ rb_set_parent_color(node, parent, RB_BLACK);
break;
} else if (!parent) {
break;
@@ -190,7 +188,8 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
tmp2 = sibling->rb_left;
if (!tmp2 || rb_is_black(tmp2)) {
/* Case 2 - sibling color flip */
- rb_set_red(sibling);
+ rb_set_parent_color(sibling, parent,
+ RB_RED);
node = parent;
parent = rb_parent(node);
continue;
@@ -230,7 +229,8 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
tmp2 = sibling->rb_right;
if (!tmp2 || rb_is_black(tmp2)) {
/* Case 2 - sibling color flip */
- rb_set_red(sibling);
+ rb_set_parent_color(sibling, parent,
+ RB_RED);
node = parent;
parent = rb_parent(node);
continue;
--
1.7.7.3
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
next prev parent reply other threads:[~2012-07-09 23:35 UTC|newest]
Thread overview: 29+ messages / expand[flat|nested] mbox.gz Atom feed top
2012-07-09 23:35 [PATCH 00/13] rbtree updates Michel Lespinasse
2012-07-09 23:35 ` [PATCH 01/13] rbtree: reference Documentation/rbtree.txt for usage instructions Michel Lespinasse
2012-07-10 1:45 ` Rik van Riel
2012-07-09 23:35 ` [PATCH 02/13] rbtree: empty nodes have no color Michel Lespinasse
2012-07-10 10:59 ` Daniel Santos
2012-07-10 23:10 ` Michel Lespinasse
2012-07-09 23:35 ` [PATCH 03/13] rbtree: fix incorrect rbtree node insertion in fs/proc/proc_sysctl.c Michel Lespinasse
2012-07-09 23:35 ` [PATCH 04/13] rbtree: move some implementation details from rbtree.h to rbtree.c Michel Lespinasse
2012-07-10 12:19 ` Michal Nazarewicz
2012-07-10 23:12 ` Michel Lespinasse
2012-07-11 15:48 ` Michal Nazarewicz
2012-07-09 23:35 ` [PATCH 05/13] rbtree: performance and correctness test Michel Lespinasse
2012-07-10 12:27 ` Michal Nazarewicz
2012-07-10 23:18 ` Michel Lespinasse
2012-07-11 6:14 ` Michel Lespinasse
2012-07-11 19:30 ` Daniel Santos
2012-07-09 23:35 ` [PATCH 06/13] rbtree: break out of rb_insert_color loop after tree rotation Michel Lespinasse
2012-07-09 23:35 ` [PATCH 07/13] rbtree: adjust root color in rb_insert_color() only when necessary Michel Lespinasse
2012-07-09 23:35 ` [PATCH 08/13] rbtree: optimize tree rotations in rb_insert_color() Michel Lespinasse
2012-07-09 23:35 ` [PATCH 09/13] rbtree: optimize color flips and parent fetching " Michel Lespinasse
2012-07-09 23:35 ` [PATCH 10/13] rbtree: adjust node color in __rb_erase_color() only when necessary Michel Lespinasse
2012-07-09 23:35 ` [PATCH 11/13] rbtree: optimize case selection logic in __rb_erase_color() Michel Lespinasse
2012-07-09 23:35 ` [PATCH 12/13] rbtree: optimize tree rotations " Michel Lespinasse
2012-07-09 23:35 ` Michel Lespinasse [this message]
2012-07-11 13:23 ` [PATCH 00/13] rbtree updates Peter Zijlstra
2012-07-12 1:12 ` Michel Lespinasse
2012-07-12 14:09 ` Peter Zijlstra
2012-07-12 14:12 ` Peter Zijlstra
2012-07-13 0:39 ` Michel Lespinasse
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=1341876923-12469-14-git-send-email-walken@google.com \
--to=walken@google.com \
--cc=aarcange@redhat.com \
--cc=akpm@linux-foundation.org \
--cc=axboe@kernel.dk \
--cc=daniel.santos@pobox.com \
--cc=dwmw2@infradead.org \
--cc=ebiederm@xmission.com \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mm@kvack.org \
--cc=peterz@infradead.org \
--cc=riel@redhat.com \
--cc=torvalds@linux-foundation.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).