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-d...@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.