00001 00023 #ifndef GALOIS_RUNTIME_WORKLISTHELPERS_H 00024 #define GALOIS_RUNTIME_WORKLISTHELPERS_H 00025 00026 #include "WLCompileCheck.h" 00027 00028 #include "Galois/Runtime/ll/PtrLock.h" 00029 00030 #include <boost/iterator/iterator_facade.hpp> 00031 00032 namespace Galois { 00033 namespace WorkList { 00034 00035 template<typename T> 00036 class ConExtListNode { 00037 T* next; 00038 public: 00039 ConExtListNode() :next(0) {} 00040 T*& getNext() { return next; } 00041 T*const& getNext() const { return next; } 00042 }; 00043 00044 template<typename T> 00045 class ConExtIterator: public boost::iterator_facade< 00046 ConExtIterator<T>, T, boost::forward_traversal_tag> { 00047 friend class boost::iterator_core_access; 00048 T* at; 00049 00050 template<typename OtherTy> 00051 bool equal(const ConExtIterator<OtherTy>& o) const { return at == o.at; } 00052 00053 T& dereference() const { return *at; } 00054 void increment() { at = at->getNext(); } 00055 00056 public: 00057 ConExtIterator(): at(0) { } 00058 00059 template<typename OtherTy> 00060 ConExtIterator(const ConExtIterator<OtherTy>& o): at(o.at) { } 00061 00062 explicit ConExtIterator(T* x): at(x) { } 00063 }; 00064 00065 template<typename T, bool concurrent> 00066 class ConExtLinkedStack { 00067 Runtime::LL::PtrLock<T, concurrent> head; 00068 00069 public: 00070 typedef ConExtListNode<T> ListNode; 00071 00072 bool empty() const { 00073 return !head.getValue(); 00074 } 00075 00076 void push(T* C) { 00077 T* oldhead(0); 00078 do { 00079 oldhead = head.getValue(); 00080 C->getNext() = oldhead; 00081 } while (!head.CAS(oldhead, C)); 00082 } 00083 00084 T* pop() { 00085 //lock free Fast path (empty) 00086 if (empty()) return 0; 00087 00088 //Disable CAS 00089 head.lock(); 00090 T* C = head.getValue(); 00091 if (!C) { 00092 head.unlock(); 00093 return 0; 00094 } 00095 head.unlock_and_set(C->getNext()); 00096 C->getNext() = 0; 00097 return C; 00098 } 00099 00101 typedef T value_type; 00102 typedef T& reference; 00103 typedef ConExtIterator<T> iterator; 00104 typedef ConExtIterator<const T> const_iterator; 00105 00106 iterator begin() { return iterator(head.getValue()); } 00107 iterator end() { return iterator(); } 00108 00109 const_iterator begin() const { return const_iterator(head.getValue()); } 00110 const_iterator end() const { return const_iterator(); } 00111 }; 00112 00113 template<typename T, bool concurrent> 00114 class ConExtLinkedQueue { 00115 Runtime::LL::PtrLock<T,concurrent> head; 00116 T* tail; 00117 00118 public: 00119 typedef ConExtListNode<T> ListNode; 00120 00121 ConExtLinkedQueue() :tail(0) { } 00122 00123 bool empty() const { 00124 return !tail; 00125 } 00126 00127 void push(T* C) { 00128 head.lock(); 00129 //std::cerr << "in(" << C << ") "; 00130 C->getNext() = 0; 00131 if (tail) { 00132 tail->getNext() = C; 00133 tail = C; 00134 head.unlock(); 00135 } else { 00136 assert(!head.getValue()); 00137 tail = C; 00138 head.unlock_and_set(C); 00139 } 00140 } 00141 00142 T* pop() { 00143 //lock free Fast path empty case 00144 if (empty()) return 0; 00145 00146 head.lock(); 00147 T* C = head.getValue(); 00148 if (!C) { 00149 head.unlock(); 00150 return 0; 00151 } 00152 if (tail == C) { 00153 tail = 0; 00154 assert(!C->getNext()); 00155 head.unlock_and_clear(); 00156 } else { 00157 head.unlock_and_set(C->getNext()); 00158 C->getNext() = 0; 00159 } 00160 return C; 00161 } 00162 00164 typedef T value_type; 00165 typedef T& reference; 00166 typedef ConExtIterator<T> iterator; 00167 typedef ConExtIterator<const T> const_iterator; 00168 00169 iterator begin() { return iterator(head.getValue()); } 00170 iterator end() { return iterator(); } 00171 00172 const_iterator begin() const { return const_iterator(head.getValue()); } 00173 const_iterator end() const { return const_iterator(); } 00174 }; 00175 00176 template<typename T> 00177 struct DummyIndexer: public std::unary_function<const T&,unsigned> { 00178 unsigned operator()(const T& x) { return 0; } 00179 }; 00180 00181 } 00182 } // end namespace Galois 00183 00184 #endif
1.6.1