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
wait
on an atomic, but the cost will be much like using a mutex. I'm assuming the use of
exchange
instead.
The code on the page you linked would also fail my code inspection:
o In C++, use
nullptr
instead of
NULL
.
o Replace
if (a == true)
and
if (a == false)
with
if (a)
and
if (!a)
.
o Remove
flag
and replace
if (T->isLock = true)...
by
if (T->isLock) return;