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.
