Locking the tree of space

Problem Statement

Locking the tree of space Problem Description A world map is stored as an m-ary tree : the root is the whole world, its children are continents, their children are countries, and so on. Every node carries a unique name. Several users share this map, and a user takes exclusive access to a region by locking the node that represents it. Locking a node reserves the entire subtree rooted at that node, so two locks may never sit on the same root-to-leaf path. You must support three operations. lock(X, uid) - user uid takes exclusive access to the subtree rooted at node X . It succeeds only if all of the following hold: X is not currently locked (by anyone, including uid itself); no ancestor of X is locked; no descendant of X is locked. unlock(X, uid) - releases a lock on X . It succeeds only if X is currently locked and the user holding that lock is uid . upgradeLock(X, uid) - moves the user's locks up to the ancestor node X . It succeeds only if all of the following hold: X is not currently