Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751511AbdFHNDh (ORCPT ); Thu, 8 Jun 2017 09:03:37 -0400 Received: from bombadil.infradead.org ([65.50.211.133]:52906 "EHLO bombadil.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750914AbdFHNDg (ORCPT ); Thu, 8 Jun 2017 09:03:36 -0400 Date: Thu, 8 Jun 2017 15:03:28 +0200 From: Peter Zijlstra To: Davidlohr Bueso 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 Subject: Re: [PATCH 1/5] rbtree: Cache leftmost node internally Message-ID: <20170608130328.dsljjblut2eew2kd@hirez.programming.kicks-ass.net> References: <20170530020940.7918-1-dave@stgolabs.net> <20170530020940.7918-2-dave@stgolabs.net> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20170530020940.7918-2-dave@stgolabs.net> User-Agent: NeoMutt/20170113 (1.7.2) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 1535 Lines: 38 On Mon, May 29, 2017 at 07:09:36PM -0700, Davidlohr Bueso wrote: > diff --git a/include/linux/rbtree_augmented.h b/include/linux/rbtree_augmented.h > index 9702b6e183bc..b84ee26c19d9 100644 > --- a/include/linux/rbtree_augmented.h > +++ b/include/linux/rbtree_augmented.h > @@ -41,7 +41,9 @@ struct rb_augment_callbacks { > void (*rotate)(struct rb_node *old, struct rb_node *new); > }; > > -extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root, > +extern void __rb_insert_augmented(struct rb_node *node, > + struct rb_root *root, > + bool newleft, struct rb_node **leftmost, > void (*augment_rotate)(struct rb_node *old, struct rb_node *new)); > /* > * Fixup the rbtree and update the augmented information when rebalancing. > @@ -150,6 +161,7 @@ extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root, > > 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?