From: Michel Lespinasse <walken@google.com>
To: Peter Zijlstra <peterz@infradead.org>
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 17:39:27 -0700 [thread overview]
Message-ID: <CANN689GdKaACaCcvuFym5qp=QJEMRVmK1qzmV4PpyfxLYCgk+A@mail.gmail.com> (raw)
In-Reply-To: <1342102376.28010.7.camel@twins>
On Thu, Jul 12, 2012 at 7:12 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> 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..
Ah, good idea, I adopted that :)
> Yes, very nice.. someday when I'm bored I might expand the comments with
> the reason why we're doing the given operation.
There is a brief comment at the start of the loop that indicates which
rbtree invariants might be violated at that point; so someone could
deduce that we're trying to either fix these or move towards the root
until they get fixed. But yeah, this is never explicitly explained.
> Also, I was sorely tempted to rename your tmp1,tmp2 variables to sl and
> sr.
This could be done, but you'd *still* need one extra temporary, so
you'd end up with sl, sr and tmp. Which is fine, I guess, but I
preferred to have one less variable around.
--
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.
--
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>
prev parent reply other threads:[~2012-07-13 0:39 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 ` [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 [this message]
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='CANN689GdKaACaCcvuFym5qp=QJEMRVmK1qzmV4PpyfxLYCgk+A@mail.gmail.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