Why is unlock O(log(n)) - Shouldn't it be just O(1) ?
------------------------------------------------------------------------------------------------------------
template<int N>
struct Node
{
bool isLocked_;
Node *parent_;
Node *children_[N];
};
bool isLocked(Node<N> *node)
{
return node->isLocked_;
}
bool visitor(Node<N>* node)
{
if(node->isLocked_) return true;
for(int i = 0; i < N; ++i){
if(children_[i] && visitor(children_[i])) return true;
}
return false;
}
bool lock(Node<N> *node)
{
if(!node) return false;
if(node->isLocked_) return true;
//Is any ancestor locked?
Node<N> *n = node;
while(n->parent_){
if(n->parent_->isLocked_) return false;
n = node->parent_;
}
//Is any of the children locked?
if(visitor(node)) return false;
//Proceed to lock
node->isLocked_ = true;
return true;
}
void unlock(Node<N>* node)
{
node_->isLocked_ = false;
}
-------------------------------------------------------------------------------
On Fri, Mar 18, 2011 at 8:32 AM, DIPANKAR DUTTA <[email protected]>
wrote:
> this is something like Multiple granularity locking protocol in DBMS...
>
>
> On Fri, Mar 18, 2011 at 5:43 PM, bittu <[email protected]> wrote:
>>
>> Given an 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. You are
>> 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)
>>
>> Thanks & Regards
>> Shashank
>>
>> --
>> 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?hl=en.
>>
>
>
>
> --
> DIPANKAR DUTTA
> M-TECH,Computer Science & Engg.
> E&C Dept,IIT ROORKEE
> Uttarakhand , India – 247667
> -------------------------------------------
> website:http://people.iitr.ernet.in/shp/09535009/Website/index.html
> ph no-09045809987
> Lab: 286454
> email:[email protected]
>
> --
> 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?hl=en.
>
--
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?hl=en.
