he class NonBlockingQueue::Node acts as described around the figure
(
NonBlockingQueue Design
).
Lines 07, 07a below: This is the parent Element. This pointer is zero if the
Node is not in the queue. theMutex is used to protect theParent only. The
double linked list fields are protected by the mutex of theParent.
Line 08: Data is the information stored in the queue and the reason for
existence.
Lines 09-10: the double linked list fields.
Lines 13-25: These are basic accessors. The presence and absence of volatile
key-word explains the locking model.
Line 14: data() is volatile (thread-safe) because theData is a const pointer.
Lines 15,16,21,22,23,24: If Element is locked then list access is safe. Hence,
presence of ElementGuard allow for volatile qualifier for these functions.
Line 35: remove this Node from the queue.
Line 38: Debugging feature.
Lines 39,41: Basic double linked list operations. Both the Element and Node
has to be locked. Hence, the arguments.
Note that we cannot have a remove() operation accepting a Guard to Node. Such
operation would require that we lock the Node first and then lock the Element.
It would contradict the order of locking in the push/pop operations and lead
to deadlock. For the same reason we cannot reuse a mutex field that may exist
inside the Data. The Node must have mutex of its own. The implementation of
existing remove() operation uses the try-release pattern of locking.
01\template <class Data>
02\
class
NonBlockingQueue<Data>::Node : boost::noncopyable
03\
{
04\
public:
05\
class
UnableToRemove : public boost::exception, public std::exception {};
06\
private:
07\
typename
Queue::Element* theParent;
07a\
mutable
typename Queue::NodeMutex theMutex;
08\
volatile
Data* const theData;
09\
Node*
thePrev;
10\
Node*
theNext;
11\
friend
class NonBlockingQueue<Data>::Element;
12\
public:
13\
inline
NodeMutex& mutex() const { return theMutex; }
14\
inline
volatile Data* data() const volatile { return theData; }
15\
template
<class ElementGuard> bool isHead( ElementGuard& el ) volatile
const;
16\
template
<class ElementGuard> bool isTail( ElementGuard& el ) volatile
const;
17\
inline
bool hasData() const { return theData!=0; }
18\
inline
void parent( typename Queue::Element* p ) { theParent=p; }
19\
inline
volatile typename Queue::Element* parent() const { return theParent; }
20\
inline
bool isInQueue() const { return theParent!=0; }
21\
template
<class ElementGuard> volatile Node* prev( ElementGuard& el_ ) const
volatile;
22\
template
<class ElementGuard> void prev( ElementGuard& el_, Node* p )
volatile ;
23\
template
<class ElementGuard> volatile Node* next( ElementGuard& el_ ) const
volatile ;
24\
template
<class ElementGuard> void next( ElementGuard& el_, Node* n )
volatile ;
25\
inline
volatile Node* next() const { return theNext; }
26\
public:
27\
Node()
: theParent(0),theData(0) {}
28\
explicit
Node( Data& d ) : theParent(0),theData(&d) {}
29\
~Node()
30\
{
31\
//The
user has to make sure that the deleted Node is not in the queue.
32\
//This
has to be user's responsibility at least because we would need to Lock to do
anything
33\
//but
then we cannot handle a possible thread resource exception here.
34\
}
35\
void
remove() volatile;
38\
template
<class ElementGuard> std::pair<bool,std::string> toString(
ElementGuard&
el_,
const
boost::function1<std::string,volatile Data*>& DataToString
)
const volatile;
38a\
std::string
toString( const boost::function1<std::pair<bool,std::string>,volatile
Data*>& DataToString ) const;
39\
static
void doInsert( ElementTryGuard& el_, NodeWriterGuard& node_ );
41\
template
<class ElementGuard,class NodeGuard> static void doRemove(
ElementGuard& el_, NodeGuard& node_ );
42\
};
|
