// 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-LockCount0)
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 nagendra@gmail.comwrote:
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 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
-~--~~~~--~~--~--~---
