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: Thu, 12 Jul 2012 16:12:56 +0200 [thread overview]
Message-ID: <1342102376.28010.7.camel@twins> (raw)
In-Reply-To: <20120712011208.GA1152@google.com>
On Wed, 2012-07-11 at 18:12 -0700, Michel Lespinasse wrote:
>
> In __rb_erase_color(), some of the cases are more complicated than you drew however, because some node colors aren't known.
Right, the wikipedia article draws them blank, I couldn't come up with a
3rd case, although maybe we can annotate them like (P) to mean blank..
> This is what I ended up with:
>
> * 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.
> + * nodes will be lowercase. Unknown color nodes shall be drawn as red with
> + * some accompanying text comment.
> */
>
> + /*
> + * Case 2 - sibling color flip
> + * (p could be either color here)
> + *
> + * p p
> + * / \ / \
> + * N S --> N s
> + * / \ / \
> + * Sl Sr Sl Sr
> + *
> + * This leaves us violating 5), so
> + * recurse at p. If p is red, the
> + * recursion will just flip it to black
> + * and exit. If coming from Case 1,
> + * p is known to be red.
> + */
>
> + /*
> + * Case 3 - right rotate at sibling
> + * (p could be either color here)
> + *
> + * p p
> + * / \ / \
> + * N S --> N Sl
> + * / \ \
> + * sl Sr s
> + * \
> + * Sr
> + */
>
> + /*
> + * Case 4 - left rotate at parent + color flips
> + * (p and sl could be either color here.
> + * After rotation, p becomes black, s acquires
> + * p's color, and sl keeps its color)
> + *
> + * p s
> + * / \ / \
> + * N S --> P Sr
> + * / \ / \
> + * sl sr N sl
> + */
Yes, very nice.. someday when I'm bored I might expand the comments with
the reason why we're doing the given operation.
Also, I was sorely tempted to rename your tmp1,tmp2 variables to sl and
sr.
--
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-12 14:13 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 ` [PATCH 13/13] rbtree: optimize color flips " Michel Lespinasse
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 [this message]
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=1342102376.28010.7.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;
as well as URLs for NNTP newsgroup(s).