00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018 #ifndef RAUL_SRMW_QUEUE_HPP
00019 #define RAUL_SRMW_QUEUE_HPP
00020
00021 #include <cassert>
00022 #include <cstdlib>
00023 #include <cmath>
00024 #include <boost/utility.hpp>
00025 #include "raul/AtomicInt.hpp"
00026
00027 namespace Raul {
00028
00029
00051 template <typename T>
00052 class SRMWQueue : boost::noncopyable
00053 {
00054 public:
00055 SRMWQueue(size_t size);
00056 ~SRMWQueue();
00057
00058
00059
00060
00061 inline size_t capacity() const { return _size-1; }
00062
00063
00064
00065
00066 inline bool full() const;
00067 inline bool push(const T& obj);
00068
00069
00070
00071
00072 inline bool empty() const;
00073 inline T& front() const;
00074 inline void pop();
00075
00076 private:
00077
00078
00079
00080
00081 unsigned _front;
00082 AtomicInt _back;
00083 AtomicInt _write_space;
00084 const unsigned _size;
00085
00086 T* const _objects;
00087 AtomicInt* const _valid;
00088 };
00089
00090
00091 template<typename T>
00092 SRMWQueue<T>::SRMWQueue(size_t size)
00093 : _front(0)
00094 , _back(0)
00095 , _write_space(size)
00096 , _size(size+1)
00097 , _objects((T*)calloc(_size, sizeof(T)))
00098 , _valid((AtomicInt*)calloc(_size, sizeof(AtomicInt)))
00099 {
00100 assert(log2(size) - (int)log2(size) == 0);
00101 assert(size > 1);
00102 assert(_size-1 == (unsigned)_write_space.get());
00103
00104 for (unsigned i=0; i < _size; ++i) {
00105 assert(_valid[i].get() == 0);
00106 }
00107 }
00108
00109
00110 template <typename T>
00111 SRMWQueue<T>::~SRMWQueue()
00112 {
00113 free(_objects);
00114 }
00115
00116
00121 template <typename T>
00122 inline bool
00123 SRMWQueue<T>::full() const
00124 {
00125 return (_write_space.get() <= 0);
00126 }
00127
00128
00136 template <typename T>
00137 inline bool
00138 SRMWQueue<T>::push(const T& elem)
00139 {
00140 const int old_write_space = _write_space.exchange_and_add(-1);
00141 const bool already_full = ( old_write_space <= 0 );
00142
00143
00144
00145
00146
00147 if (already_full) {
00148
00149
00150
00151
00152
00153
00154 return false;
00155
00156 } else {
00157
00158
00159 const unsigned write_index = (unsigned)_back.exchange_and_add(1) % _size;
00160
00161 assert(_valid[write_index] == 0);
00162 _objects[write_index] = elem;
00163 ++(_valid[write_index]);
00164
00165 return true;
00166
00167 }
00168 }
00169
00170
00175 template <typename T>
00176 inline bool
00177 SRMWQueue<T>::empty() const
00178 {
00179 return (_valid[_front].get() == 0);
00180 }
00181
00182
00188 template <typename T>
00189 inline T&
00190 SRMWQueue<T>::front() const
00191 {
00192 return _objects[_front];
00193 }
00194
00195
00203 template <typename T>
00204 inline void
00205 SRMWQueue<T>::pop()
00206 {
00207 assert(_valid[_front] == 1);
00208 --(_valid[_front]);
00209
00210 _front = (_front + 1) % (_size);
00211
00212 if (_write_space.get() < 0)
00213 _write_space = 1;
00214 else
00215 ++_write_space;
00216 }
00217
00218
00219 }
00220
00221 #endif // RAUL_SRMW_QUEUE_HPP