Locking the tree of space

Problem Statement

Locking the tree of space Problem Description A world map is stored as a tree. Every node of the tree has a unique name, and every user of the system has a unique integer id. Users take and release locks on nodes, and a lock on a node is meant to give its owner exclusive access to the whole subtree rooted at that node. You must support three operations, each performed by a user uid on a node named X . 1. Lock(X, uid) Lock(X, uid) succeeds only if all three of the following hold: node X is not currently locked, none of X 's ancestors is currently locked, none of X 's descendants is currently locked. On success, X becomes locked by user uid and the operation returns true . Otherwise nothing changes and it returns false . 2. Unlock(X, uid) Unlock(X, uid) succeeds only if node X is currently locked and its owner is exactly uid . On success, X becomes unlocked and the operation returns true . Otherwise nothing changes and it returns false . (inferred - the source defines Unlock only by the