uncontentious_queue.h
Go to the documentation of this file.
00001 #ifndef MEGATREE_UNCONTENTIOUS_QUEUE_H
00002 #define MEGATREE_UNCONTENTIOUS_QUEUE_H
00003 
00004 #include <boost/thread.hpp>
00005 
00006 namespace megatree {
00007 
00008 // http://www.cs.rochester.edu/research/synchronization/pseudocode/queues.html#tlq
00009 //
00010 // head always points to a dead node.  It's either the empty node from
00011 // initialization, or it's a node whose value has already been
00012 // returned.
00013 template <class T>
00014 class UncontentiousQueue
00015 {
00016 public:
00017   UncontentiousQueue();
00018   ~UncontentiousQueue();
00019 
00020   void enqueue(const T&);
00021   bool dequeue(T&);
00022   void dequeueBlocking(T&);
00023 
00024 private:
00025   struct Node
00026   {
00027     T data;
00028     Node* next;
00029   };
00030   
00031   boost::mutex head_mutex, tail_mutex;
00032   boost::condition grown_condition;
00033   Node* head;
00034   Node* tail;
00035 };
00036 
00037 template <class T>
00038 UncontentiousQueue<T>::UncontentiousQueue()
00039 {
00040   Node* dummy = new Node;
00041   dummy->next = NULL;
00042   head = tail = dummy;
00043 }
00044 
00045 template <class T>
00046 UncontentiousQueue<T>::~UncontentiousQueue()
00047 {
00048   boost::mutex::scoped_lock head_lock(head_mutex), tail_lock(tail_mutex);
00049   Node *n = head;
00050   while (n) {
00051     Node* old = n;
00052     n = n->next;
00053     delete old;
00054   }
00055 }
00056 
00057 template <class T>
00058 void UncontentiousQueue<T>::enqueue(const T& item)
00059 {
00060   Node* n = new Node;
00061   n->data = item;
00062   n->next = NULL;
00063 
00064   boost::mutex::scoped_lock lock(tail_mutex);
00065   tail->next = n;
00066   tail = n;
00067   grown_condition.notify_one();
00068 }
00069 
00070 template <class T>
00071 bool UncontentiousQueue<T>::dequeue(T& item)
00072 {
00073   boost::mutex::scoped_lock lock(head_mutex);
00074   Node* new_head = head->next;
00075   if (new_head == NULL)
00076     return false;
00077   item = new_head->data;
00078   delete head;
00079   head = new_head;
00080   return true;
00081 }
00082 
00083 template <class T>
00084 void UncontentiousQueue<T>::dequeueBlocking(T& item)
00085 {
00086   boost::mutex::scoped_lock lock(head_mutex);
00087   while (head->next == NULL)
00088     grown_condition.wait(head_mutex);
00089   
00090   Node* new_head = head->next;
00091   assert(new_head != NULL);
00092   item = new_head->data;
00093   delete head;
00094   head = new_head;
00095   return true;
00096 }
00097 
00098 } // namespace
00099 
00100 #endif


megatree_core
Author(s): Stuart Glaser
autogenerated on Thu Nov 28 2013 11:30:23