he pop() is written similarly to the push(): we attempt to gain ownership of
an Element, then we extract a Node.
The lines 07-22 are almost exactly the code of push(). If we find some Node
then we return it and exit (line 16). If we reach line 23 and the fullAccess
is true then the queue is empty and we return a dummy first Node of the double
linked list. If fullAccess is false then we were forced to skip some node.
Hence, we do another pass (lines 25-35) while demanding for exclusive
ownership at line 27 (instead of trying for it at line 09). Then we either
find some Node and return it (line 32) or establish that the queue is empty
and return a dummy Node.
01\template <class Data>
02\
typename
NonBlockingQueue<Data>::Node& NonBlockingQueue<Data>::pop()
volatile
03\
{
04\
volatile
Element* el=get();
05\
int
L=circleLength();
06\
bool
fullAccess=true;
07\
for(
int i=0; i<L; ++i )
08\
{
09\
ElementTryGuard
el_(el);
10\
if(
el_ )
11\
{
12\
if(
!el_->isEmpty() )
13\
{
14\
NodeWriterGuard
node_(el_->head().next(el_));
15\
Node::doRemove(el_,node_);
16\
return
*node_;
17\
}
18\
}
19\
else
20\
fullAccess=false;
21\
el=el->next();
22\
}
23\
if(
fullAccess )
24\
return
ElementWriterGuard(get())->head();
25\
for(
int i=0; i<L; ++i )
26\
{
27\
ElementWriterGuard
el_(el);
28\
if(
!el_->isEmpty() )
29\
{
30\
NodeWriterGuard
node_(el_->head().next(el_));
31\
Node::doRemove(el_,node_);
32\
return
*node_;
33\
}
34\
el=el->next();
35\
}
36\
return
ElementWriterGuard(get())->head();
37\
}
|
