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