I. Installation.
 III. NonBlockingQueue.
 1 NonBlockingQueue design.
 2 Simplest example with NonBlockingQueue.
 3 NonBlockingQueue prototypes.
 A. NonBlockingQueue data fields.
 B. NonBlockingQueue::push member function.
 C. NonBlockingQueue::pop member function.
 D. NonBlockingQueue::Element.
 E. NonBlockingQueue::Node.
 4 Python-based acceptance test of NonBlockingQueue.
 VI. OTS Scheduler.
 VII. Bibliography

## NonBlockingQueue::Element.

he class NonBlockingQueue::Element acts as described around the figure ( NonBlockingQueue Design ).

The Element owns mutex-wise the entire double linked list of Nodes that originates from it. Such ownership is represented by the field theMutex, line 05 below.

The Element is a member of the circular structure, see the picture ( NonBlockingQueue Design ). Hence, it has the field theNext, line 06.

According to the common recipe for double linked list construction, the Element starts with two dummy Nodes in the list. These Nodes are represented by the fields theHead and theTail, lines 08,09. The dummy Nodes are never removed and always represent the head and the tail of the list. Hence, the pointers theHead and theTail are const. For the same reason the functions head() and tail() are volatile, lines 13,14.

Line 19: see explanation in the ( DataToString explanation ).

01\template <class Data>

02\ class NonBlockingQueue<Data>::Element : boost::noncopyable

03\ {

04\ private:

05\ mutable ElementMutex theMutex;

06\ Element* theNext;

07\ typedef NonBlockingQueue<Data> Queue;

09\ typename Queue::Node* const theTail;

10\ public:

11\ inline ElementMutex& mutex() const { return theMutex; }

12\ inline volatile Element* next() const volatile { return theNext; }

13\ inline volatile typename Queue::Node& head() const volatile { return *theHead; }

14\ inline volatile typename Queue::Node& tail() const volatile { return *theTail; }

15\ inline bool isEmpty() const { return theHead->next()==theTail; }

16\ public:

17\ Element();

18\ ~Element();

19\ std::string toString(

const boost::function1<std::pair<bool,std::string>,volatile Data*>& DataToString

) const volatile;

20\ };