lkml.org 
[lkml]   [2021]   [Jan]   [26]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH v2 5/7] rbtree, uprobes: Use rbtree helpers
On Mon, Jan 25, 2021 at 09:59:49PM -0800, Davidlohr Bueso wrote:
> On Mon, 25 Jan 2021, Peter Zijlstra wrote:
>
> > Reduce rbtree boilerplate by using the new helpers.
>
> This reminds me of:
>
> https://lore.kernel.org/lkml/20200207180305.11092-6-dave@stgolabs.net/
>
> Would a walk optimization (list+rbtree) serve here? Not sure how big
> the uprobes_trees gets.

Oh, that's patch set is horrible.. You can do a linked list with the
unused node pointers directly.

https://en.wikipedia.org/wiki/Threaded_binary_tree

So instead of using NULL for the empty rb_{left,right} pointers, use
pointers with the LSB set to differentiate them from regular leaf
pointers.

Other than that, threaded rb-trees would be awesome. I've meant to
implement them a number of times but never had the time to do the
tree-wide clean up of the rb_tree API to enable them.

\
 
 \ /
  Last update: 2021-01-26 12:29    [W:0.187 / U:0.208 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site