Date: Thu, 8 Jun 2017 08:36:08 -0700
From: Davidlohr Bueso <dave@stgolabs.net>
To: Peter Zijlstra <peterz@infradead.org>
Cc: mingo@kernel.org, akpm@linux-foundation.org, jack@suse.cz,
        kirill.shutemov@linux.intel.com, ldufour@linux.vnet.ibm.com,
        mhocko@suse.com, mgorman@techsingularity.net,
        linux-kernel@vger.kernel.org, Davidlohr Bueso <dbueso@suse.de>
Subject: Re: [PATCH 1/5] rbtree: Cache leftmost node internally
Message-ID: <20170608153608.GA2464@linux-80c1.suse>
References: <20170530020940.7918-1-dave@stgolabs.net>
 <20170530020940.7918-2-dave@stgolabs.net>
 <20170608130328.dsljjblut2eew2kd@hirez.programming.kicks-ass.net>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Disposition: inline
In-Reply-To: <20170608130328.dsljjblut2eew2kd@hirez.programming.kicks-ass.net>
User-Agent: Mutt/1.5.24 (2015-08-30)
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 1079
Lines: 31

On Thu, 08 Jun 2017, Peter Zijlstra wrote:

>On Mon, May 29, 2017 at 07:09:36PM -0700, Davidlohr Bueso wrote:
>>
>>  static __always_inline struct rb_node *
>>  __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
>> +		     bool cached, struct rb_node **leftmost,
>>  		     const struct rb_augment_callbacks *augment)
>>  {
>>  	struct rb_node *child = node->rb_right;
>> @@ -157,6 +169,9 @@ __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
>>  	struct rb_node *parent, *rebalance;
>>  	unsigned long pc;
>>
>> +	if (cached && node == *leftmost)
>> +		*leftmost = rb_next(node);
>> +
>>  	if (!tmp) {
>>  		/*
>>  		 * Case 1: node to erase has no more than 1 child (easy!)
>
>Why do we have @cached ? Wouldn't simply testing @leftmost for NULL not
>do the same?

I added that so that we can differentiate between regular rbtrees and the
cached flavor. However, you are right, we can avoid that arg considering
that the tree is never empty (this is an erase call), thus if leftmost
is nil, it was never cached in the first place.

Thanks,
Davidlohr