I'M working on the famous tree of space problem, where

Question

I'M working on the famous tree of space problem, where

we have an m-ary tree and can lock any node if none of its ancestors or descendants are already locked. I need to make the code thread-safe without using synchronized, mutex, or AtomicInteger.

Here's the Lock method:

static boolean Lock(Node node, int id) {
if (++node.locked > 1 || !node.lockedDescendents.isEmpty()) {
node.locked--;
return false;
}

// Informing ancestors
Node curr = node.parent;
while (curr != null) {
if (curr.locked > 0 || !node.lockedDescendent.isEmpty()) {
Node temp = node.parent;
while (temp != curr) {
temp.lockedDescendent.remove(node);
temp = temp.parent;
}
node.locked--;
return false;
}
curr.lockedDescendent.add(node);
curr = curr.parent;
}

node.id = id;
return true;
}

The issue arises when I lock a child node and a context switch occurs before updating the parent's locked descendants. This can lead to both the child and parent getting locked. How can I resolve this without using while loops or external libraries?

12$ bounty