You could use an atomic
] rather than a mutex. That's the only thing I can think of that's faster.
The entire tree must be locked because it's in a transient state until all of the ancestors have been updated.
When using an atomic, a thread that fails to lock a resource simply fails to obtain it. The benefit of a mutex is that the thread gets scheduled out by the operating system until the resource becomes available. Here, the resource is the entire tree, which means that if a thread is currently updating the tree, another thread will fail to obtain the resources associated with a node even if those resources are currently available
In C++20, it is possibly to
on an atomic, but the cost will be much like using a mutex. I'm assuming the use of
The code on the page you linked would also fail my code inspection:
o In C++, use
if (a == true)
if (a == false)
if (T->isLock = true)...
if (T->isLock) return;