Messages in this thread | | | Date | Tue, 26 Jan 2021 10:30:06 +0100 | From | Peter Zijlstra <> | Subject | Re: [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.
| |