[lttng-dev] URCU binary search tree

Mathieu Desnoyers mathieu.desnoyers at efficios.com
Thu Dec 14 20:05:23 UTC 2017


I did a URCU rbtree prototype branch around 2011, but it's not pretty, and it's complex. 

I went in a different direction afterward, and did a RCU Judy Array prototype instead. 

The basic problem with rbtree is that there will always be some form of 
higher contention on the nodes near the top. 

Anyway, the branch is there: 


See this Linux Plumbers Conference presentation introducing it: 


Note that I do _not_ consider my propotype branch to be production-ready. 



----- On Dec 14, 2017, at 2:38 PM, Navin Agrawal <anavin at gmail.com> wrote: 

> Hi,

> I have searched enough for any existing implementation of URCU based BST. But to
> no avail.

> I was keen to attempt develop it myself. But I wanted to cross if there is any
> particular reason it is not developed by anyone.

> Do let me know.

> Thanks
> Navin

> _______________________________________________
> lttng-dev mailing list
> lttng-dev at lists.lttng.org
> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

Mathieu Desnoyers 
EfficiOS Inc. 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.lttng.org/pipermail/lttng-dev/attachments/20171214/e34fc404/attachment.html>

More information about the lttng-dev mailing list