Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1661159 > unrolled thread

Re: [PATCH 1/5] rbtree: Cache leftmost node internally

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [PATCH 1/5] rbtree: Cache leftmost node internally Peter Zijlstra <peterz@infradead.org> - 2017-06-08 15:10 +0200
    Re: [PATCH 1/5] rbtree: Cache leftmost node internally Davidlohr Bueso <dave@stgolabs.net> - 2017-06-08 17:40 +0200

#1661159 — Re: [PATCH 1/5] rbtree: Cache leftmost node internally

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?

[toc] | [next] | [standalone]

#1661401

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

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web