On Aug 29, 2:05 pm, nagendra kumar <nagendra....@gmail.com> wrote:
> Given a n-ary tree of resources arranged hierarchically. A process
> needs to lock a resource node in order to use it. But,
> A node cannot be locked if any of its descendant or ancestor is
> locked.
> I was supposed to
> -> write the structure of node
> -> write codes for
> -> islock()- returns true if a given node is locked and false if it is
> not
> -> lock()- locks the given node if possible and updates lock
> information
> -> unlock()- unlocks the node and updates information.
> Codes should be :
> Islock –O(1)
> Lock()- O(log n)
> unLock()- O(log n)
I'd go with
struct node
{
node *descendants[n];
node *lockingElement;
node *parent;
bool isLock(){return lockingElement!=null;}
void Lock()
{
LockParent(this);
foreach(node * n in descendants) n->LockChildren(this);
}
void Unlock() // because unlock isn't two words
{
// gets messy if you allow arbitrary nodes to be unlocked
if(lockingElement!=this)throw;
UnlockParent();
foreach(node * in descendants) n->UnlockChildren();
}
void LockParent(node *locker)
{
lockingElement=locker;
if(parent!=null) parent->LockParent(locker);
}
void UnlockParent()
{
lockingElement=null;
if(parent!=null) parent->UnlockParent();
}
void LockChildren(node *locker)
{
lockingElement=locker;
foreach(node *n in descendants) n->LockChildren(locker);
}
void UnlockChildren(node *locker)
{
lockingElement=null;
foreach(node *n in descendants) n->UnlockChildren(locker);
}
}
untested and coded on the fly UAYOR
--
Geoff
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
