From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <linux-kernel-owner@vger.kernel.org>
Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand
	id S933108Ab2GKTaU (ORCPT <rfc822;w@1wt.eu>);
	Wed, 11 Jul 2012 15:30:20 -0400
Received: from nm16-vm0.access.bullet.mail.sp2.yahoo.com ([98.139.44.166]:26981
	"HELO nm16-vm0.access.bullet.mail.sp2.yahoo.com" rhost-flags-OK-OK-OK-OK)
	by vger.kernel.org with SMTP id S932307Ab2GKTaS (ORCPT
	<rfc822;linux-kernel@vger.kernel.org>);
	Wed, 11 Jul 2012 15:30:18 -0400
X-Yahoo-Newman-Id: 649136.27070.bm@omp1027.access.mail.sp2.yahoo.com
X-Yahoo-Newman-Property: ymail-3
X-YMail-OSG: 4HLFztUVM1n80GVQA0kza9bCr21Zq9iGjyPOaREG3T85GCk
 5v3y0Wpuj9HJ6Z96VMkSos9jlm3QllYcopmrPnCrXrs9692xTLrnKRxEOqTJ
 mblVx5fHGIWx9hnctR9b.5HMJM7LQDwipOPDCJTlUvWufa_9hqSppKOPHa.G
 2YKLOrCF39BRvSXj55ZQVWXqnJC_riftaV5B71WdEhPIT_XJ8l3B.oYbPkiq
 y9vPnfXS530ilV.J1HXFmeFCDj8HmgTXQtVWQ10OEp0YScbWC5rJFopNQ2Nl
 Rv0gOC1kXx9lGWSU.Omsx248ubKbKX7IkuFxElcjCSMyUaNvXjP3kUFS2E4P
 BMX5L2W5bKEfd3BecRlAxpEEQPrExr0s1JtoVBaAy9yHXQusNFsMhhUOcNcH
 7kKiK8w--
X-Yahoo-SMTP: xXkkXk6swBBAi.5wfkIWFW3ugxbrqyhyk_b4Z25Sfu.XGQ--
Message-ID: <4FFDD456.7050809@att.net>
Date: Wed, 11 Jul 2012 14:30:30 -0500
From: Daniel Santos <danielfsantos@att.net>
Reply-To: Daniel Santos <daniel.santos@pobox.com>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:10.0.4) Gecko/20120502 Thunderbird/10.0.4
MIME-Version: 1.0
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
References: <1341876923-12469-1-git-send-email-walken@google.com> <1341876923-12469-6-git-send-email-walken@google.com> <op.wg8cv6x53l0zgt@mpn-glaptop> <CANN689EEHe+_W=pnnvf1u+BxpvY+BK6bLNZ-0Y-eoKNS=9L+rg@mail.gmail.com>
In-Reply-To: <CANN689EEHe+_W=pnnvf1u+BxpvY+BK6bLNZ-0Y-eoKNS=9L+rg@mail.gmail.com>
X-Enigmail-Version: 1.3.5
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Sender: linux-kernel-owner@vger.kernel.org
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

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.