From: Peter Zijlstra <peterz@infradead.org>
To: Michel Lespinasse <walken@google.com>
Cc: aarcange@redhat.com, dwmw2@infradead.org, riel@redhat.com,
daniel.santos@pobox.com, axboe@kernel.dk, ebiederm@xmission.com,
linux-mm@kvack.org, akpm@linux-foundation.org,
linux-kernel@vger.kernel.org, torvalds@linux-foundation.org
Subject: Re: [PATCH 00/13] rbtree updates
Date: Wed, 11 Jul 2012 15:23:16 +0200 [thread overview]
Message-ID: <1342012996.3462.154.camel@twins> (raw)
In-Reply-To: <1341876923-12469-1-git-send-email-walken@google.com>
Looks nice.. How about something like the below on top.. I couldn't
immediately find a sane reason for the grand-parent to always be red in
the insertion case.
---
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -23,6 +23,25 @@
#include <linux/rbtree.h>
#include <linux/export.h>
+/*
+ * red-black trees properties: http://en.wikipedia.org/wiki/Rbtree
+ *
+ * 1) A node is either red or black
+ * 2) The root is black
+ * 3) All leaves (NULL) are black
+ * 4) Both children of every red node are black
+ * 5) Every simple path from a given node to any of its descendant leaves
+ * contains the same number of black nodes.
+ *
+ * 4 and 5 give the O(log n) guarantee, since 4 implies you cannot have two
+ * consecutive red nodes in a path and every red node is therefore followed by
+ * a black. So if B is the number of black nodes on every simple path (as per
+ * 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.
+ */
+
#define RB_RED 0
#define RB_BLACK 1
@@ -85,12 +104,27 @@ void rb_insert_color(struct rb_node *nod
} else if (rb_is_black(parent))
break;
+ /*
+ * XXX
+ */
gparent = rb_red_parent(parent);
if (parent == gparent->rb_left) {
tmp = gparent->rb_right;
if (tmp && rb_is_red(tmp)) {
- /* Case 1 - color flips */
+ /*
+ * Case 1 - color flips
+ *
+ * G g
+ * / \ / \
+ * p u --> P U
+ * / /
+ * n N
+ *
+ * However, since g's parent might be red, and
+ * 4) does not allow this, we need to recurse
+ * at g.
+ */
rb_set_parent_color(tmp, gparent, RB_BLACK);
rb_set_parent_color(parent, gparent, RB_BLACK);
node = gparent;
@@ -100,17 +134,35 @@ void rb_insert_color(struct rb_node *nod
}
if (parent->rb_right == node) {
- /* Case 2 - left rotate at parent */
+ /*
+ * Case 2 - left rotate at parent
+ *
+ * G G
+ * / \ / \
+ * p U --> n U
+ * \ /
+ * n p
+ *
+ * This still leaves us in violation of 4), the
+ * continuation into Case 3 will fix that.
+ */
parent->rb_right = tmp = node->rb_left;
node->rb_left = parent;
if (tmp)
- rb_set_parent_color(tmp, parent,
- RB_BLACK);
+ rb_set_parent_color(tmp, parent, RB_BLACK);
rb_set_parent_color(parent, node, RB_RED);
parent = node;
}
- /* Case 3 - right rotate at gparent */
+ /*
+ * Case 3 - right rotate at gparent
+ *
+ * G P
+ * / \ / \
+ * p U --> n g
+ * / \
+ * n U
+ */
gparent->rb_left = tmp = parent->rb_right;
parent->rb_right = gparent;
if (tmp)
@@ -134,8 +186,7 @@ void rb_insert_color(struct rb_node *nod
parent->rb_left = tmp = node->rb_right;
node->rb_right = parent;
if (tmp)
- rb_set_parent_color(tmp, parent,
- RB_BLACK);
+ rb_set_parent_color(tmp, parent, RB_BLACK);
rb_set_parent_color(parent, node, RB_RED);
parent = node;
}
@@ -175,43 +226,75 @@ static void __rb_erase_color(struct rb_n
} else if (parent->rb_left == node) {
sibling = parent->rb_right;
if (rb_is_red(sibling)) {
- /* Case 1 - left rotate at parent */
+ /*
+ * 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);
+ __rb_rotate_set_parents(parent, sibling, root, RB_RED);
sibling = tmp1;
}
tmp1 = sibling->rb_right;
if (!tmp1 || rb_is_black(tmp1)) {
tmp2 = sibling->rb_left;
if (!tmp2 || rb_is_black(tmp2)) {
- /* Case 2 - sibling color flip */
- rb_set_parent_color(sibling, parent,
- RB_RED);
+ /*
+ * Case 2 - sibling color flip
+ *
+ * P P
+ * / \ / \
+ * N S --> N s
+ * / \ / \
+ * Sl Sr Sl Sr
+ *
+ * This leaves us violating 5), recurse at p.
+ */
+ rb_set_parent_color(sibling, parent, RB_RED);
node = parent;
parent = rb_parent(node);
continue;
}
- /* Case 3 - right rotate at sibling */
+ /*
+ * Case 3 - right rotate at sibling
+ *
+ * P P
+ * / \ / \
+ * N S --> N sl
+ * / \ / \
+ * sl Sr 1 S
+ * / \ / \
+ * 1 2 2 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);
+ rb_set_parent_color(tmp1, sibling, RB_BLACK);
tmp1 = sibling;
sibling = tmp2;
}
- /* Case 4 - left rotate at parent + color flips */
+ /*
+ * Case 4 - left rotate at parent + color flips
+ *
+ * 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);
+ __rb_rotate_set_parents(parent, sibling, root, RB_BLACK);
break;
} else {
sibling = parent->rb_left;
@@ -220,8 +303,7 @@ static void __rb_erase_color(struct rb_n
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);
+ __rb_rotate_set_parents(parent, sibling, root, RB_RED);
sibling = tmp1;
}
tmp1 = sibling->rb_left;
@@ -229,8 +311,7 @@ static void __rb_erase_color(struct rb_n
tmp2 = sibling->rb_right;
if (!tmp2 || rb_is_black(tmp2)) {
/* Case 2 - sibling color flip */
- rb_set_parent_color(sibling, parent,
- RB_RED);
+ rb_set_parent_color(sibling, parent, RB_RED);
node = parent;
parent = rb_parent(node);
continue;
@@ -240,8 +321,7 @@ static void __rb_erase_color(struct rb_n
tmp2->rb_left = sibling;
parent->rb_left = tmp2;
if (tmp1)
- rb_set_parent_color(tmp1, sibling,
- RB_BLACK);
+ rb_set_parent_color(tmp1, sibling, RB_BLACK);
tmp1 = sibling;
sibling = tmp2;
}
@@ -251,8 +331,7 @@ static void __rb_erase_color(struct rb_n
rb_set_parent_color(tmp1, sibling, RB_BLACK);
if (tmp2)
rb_set_parent(tmp2, parent);
- __rb_rotate_set_parents(parent, sibling, root,
- RB_BLACK);
+ __rb_rotate_set_parents(parent, sibling, root, RB_BLACK);
break;
}
}
@@ -267,8 +346,7 @@ void rb_erase(struct rb_node *node, stru
child = node->rb_right;
else if (!node->rb_right)
child = node->rb_left;
- else
- {
+ else {
struct rb_node *old = node, *left;
node = node->rb_right;
@@ -310,17 +388,15 @@ void rb_erase(struct rb_node *node, stru
if (child)
rb_set_parent(child, parent);
- if (parent)
- {
+ if (parent) {
if (parent->rb_left == node)
parent->rb_left = child;
else
parent->rb_right = child;
- }
- else
+ } else
root->rb_node = child;
- color:
+color:
if (color == RB_BLACK)
__rb_erase_color(child, parent, root);
}
@@ -433,8 +509,10 @@ struct rb_node *rb_next(const struct rb_
if (RB_EMPTY_NODE(node))
return NULL;
- /* If we have a right-hand child, go down and then left as far
- as we can. */
+ /*
+ * If we have a right-hand child, go down and then left as far as we
+ * can.
+ */
if (node->rb_right) {
node = node->rb_right;
while (node->rb_left)
@@ -442,12 +520,13 @@ struct rb_node *rb_next(const struct rb_
return (struct rb_node *)node;
}
- /* No right-hand children. Everything down and left is
- smaller than us, so any 'next' node must be in the general
- direction of our parent. Go up the tree; any time the
- ancestor is a right-hand child of its parent, keep going
- up. First time it's a left-hand child of its parent, said
- parent is our 'next' node. */
+ /*
+ * No right-hand children. Everything down and left is smaller than
+ * us, so any 'next' node must be in the general direction of our
+ * parent. Go up the tree; any time the ancestor is a right-hand child
+ * of its parent, keep going up. First time it's a left-hand child of
+ * its parent, said parent is our 'next' node.
+ */
while ((parent = rb_parent(node)) && node == parent->rb_right)
node = parent;
@@ -462,8 +541,10 @@ struct rb_node *rb_prev(const struct rb_
if (RB_EMPTY_NODE(node))
return NULL;
- /* If we have a left-hand child, go down and then right as far
- as we can. */
+ /*
+ * If we have a left-hand child, go down and then right as far as we
+ * can.
+ */
if (node->rb_left) {
node = node->rb_left;
while (node->rb_right)
@@ -471,8 +552,10 @@ struct rb_node *rb_prev(const struct rb_
return (struct rb_node *)node;
}
- /* No left-hand children. Go up till we find an ancestor which
- is a right-hand child of its parent */
+ /*
+ * No left-hand children. Go up till we find an ancestor which is a
+ * right-hand child of its parent
+ */
while ((parent = rb_parent(node)) && node == parent->rb_left)
node = parent;
--
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-11 13:23 UTC|newest]
Thread overview: 29+ messages / expand[flat|nested] mbox.gz Atom feed top
2012-07-09 23:35 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 ` [PATCH 13/13] rbtree: optimize color flips " Michel Lespinasse
2012-07-11 13:23 ` Peter Zijlstra [this message]
2012-07-12 1:12 ` [PATCH 00/13] rbtree updates 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=1342012996.3462.154.camel@twins \
--to=peterz@infradead.org \
--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=riel@redhat.com \
--cc=torvalds@linux-foundation.org \
--cc=walken@google.com \
/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