From: Daniel Santos <danielfsantos@att.net>
To: Michel Lespinasse <walken@google.com>
Cc: Michal Nazarewicz <mina86@mina86.com>,
aarcange@redhat.com, dwmw2@infradead.org, riel@redhat.com,
peterz@infradead.org, 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 05/13] rbtree: performance and correctness test
Date: Wed, 11 Jul 2012 14:30:30 -0500 [thread overview]
Message-ID: <4FFDD456.7050809@att.net> (raw)
In-Reply-To: <CANN689EEHe+_W=pnnvf1u+BxpvY+BK6bLNZ-0Y-eoKNS=9L+rg@mail.gmail.com>
On 07/11/2012 01:14 AM, Michel Lespinasse wrote:
> On Tue, Jul 10, 2012 at 5:27 AM, Michal Nazarewicz <mina86@mina86.com> wrote:
>> On Tue, 10 Jul 2012 01:35:15 +0200, Michel Lespinasse <walken@google.com> wrote:
>>> + u32 prev_key = 0;
>>> +
>>> + for (rb = rb_first(&root); rb; rb = rb_next(rb)) {
>>> + struct test_node *node = rb_entry(rb, struct test_node,
>>> rb);
>>> + WARN_ON_ONCE(node->key < prev_key);
>> What if for some reason we generate node with key equal zero or two keys
>> with the same value? It may not be the case for current code, but someone
>> might change it in the future. I think <= is safer here.
> No, it's not illegal for two nodes to have the same key; the second
> one to be inserted will just get placed after the first one. The
> rbtree library doesn't care either way as it's not even aware of the
> key values :)
Right. This is strictly a function of your insert function. In my
generic rbtree patch set, there is a concept of unique or non-unique
keys, but this doesn't exist in the rbtree library its self.
--
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 19:30 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 [this message]
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
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=4FFDD456.7050809@att.net \
--to=danielfsantos@att.net \
--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=mina86@mina86.com \
--cc=peterz@infradead.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).