// Data Structure for the n-ary tree
struct node
{
int data;
node * child[m];
bool lockFlag; // Indicates if a node is locked or not
node *parent; //Holds the immediate parent of the node
int LockCount; //Holds how many nodes arrested this node
};
// Takes logm(N) in the worst case
bool check(node *NodeToBeLocked)
{
node *m=NodeToBeLocked;
if(m->flag==true || m->LockCount>0)
return false; // since the node is already locked or any of its
subtrees already locked, return false
while(m && !m->lockFlag)
m=m->parent;
if(m && m->lockFlag)
return false; // if any of its ancestors have been already locked
return true;
}
// Takes logm(N) in the worst case
bool lock(node *NodeToBeLocked)
{
if(check(NodeToBeLocked)) // If true, Node is free to be locked
{
node *m=NodeToBeLocked;
m->lock=true;
node *prevChild=m;
m=m->parent;
while(m)
{
m->LockCount++;
prevChild=m;
m=m->parent;
}
return true;
}
return false; //err.. cannot be locked
}
// Takes logm(N) in the worst case
bool unlock(node *NodeToBeUnLocked)
{
node *m=NodeToUnBeLocked;
m->lock=false; // Unlock the Node
node *prevChild=m;
m=m->parent;
while(m)
{
m->LockCount--;
prevChild=m;
m=m->parent;
}
}
Thanks,
Priya
On Sat, Aug 29, 2009 at 11:35 PM, nagendra kumar <[email protected]>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)
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
