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
00025 #include <boost/utility.hpp>
00026
00027 #include "raul/AtomicInt.hpp"
00028
00029 namespace Raul {
00030
00031
00053 template <typename T>
00054 class SRMWQueue : boost::noncopyable
00055 {
00056 public:
00057 explicit SRMWQueue(size_t size);
00058 ~SRMWQueue();
00059
00060
00061
00062
00063 inline size_t capacity() const { return _size-1; }
00064
00065
00066
00067
00068 inline bool full() const;
00069 inline bool push(const T& obj);
00070
00071
00072
00073
00074 inline bool empty() const;
00075 inline T& front() const;
00076 inline void pop();
00077
00078 private:
00079
00080
00081
00082
00083 unsigned _front;
00084 AtomicInt _back;
00085 AtomicInt _write_space;
00086 const unsigned _size;
00087
00088 T* const _objects;
00089 AtomicInt* const _valid;
00090 };
00091
00092
00093 template<typename T>
00094 SRMWQueue<T>::SRMWQueue(size_t size)
00095 : _front(0)
00096 , _back(0)
00097 , _write_space(size)
00098 , _size(size+1)
00099 , _objects((T*)calloc(_size, sizeof(T)))
00100 , _valid((AtomicInt*)calloc(_size, sizeof(AtomicInt)))
00101 {
00102 assert(log2(size) - (int)log2(size) == 0);
00103 assert(size > 1);
00104 assert(_size-1 == (unsigned)_write_space.get());
00105
00106 for (unsigned i=0; i < _size; ++i) {
00107 assert(_valid[i].get() == 0);
00108 }
00109 }
00110
00111
00112 template <typename T>
00113 SRMWQueue<T>::~SRMWQueue()
00114 {
00115 free(_objects);
00116 }
00117
00118
00123 template <typename T>
00124 inline bool
00125 SRMWQueue<T>::full() const
00126 {
00127 return (_write_space.get() <= 0);
00128 }
00129
00130
00138 template <typename T>
00139 inline bool
00140 SRMWQueue<T>::push(const T& elem)
00141 {
00142 const int old_write_space = _write_space.exchange_and_add(-1);
00143 const bool already_full = ( old_write_space <= 0 );
00144
00145
00146
00147
00148
00149 if (already_full) {
00150
00151
00152
00153
00154
00155
00156 return false;
00157
00158 } else {
00159
00160
00161 const unsigned write_index = (unsigned)_back.exchange_and_add(1) % _size;
00162
00163 assert(_valid[write_index] == 0);
00164 _objects[write_index] = elem;
00165 ++(_valid[write_index]);
00166
00167 return true;
00168
00169 }
00170 }
00171
00172
00177 template <typename T>
00178 inline bool
00179 SRMWQueue<T>::empty() const
00180 {
00181 return (_valid[_front].get() == 0);
00182 }
00183
00184
00190 template <typename T>
00191 inline T&
00192 SRMWQueue<T>::front() const
00193 {
00194 return _objects[_front];
00195 }
00196
00197
00205 template <typename T>
00206 inline void
00207 SRMWQueue<T>::pop()
00208 {
00209 assert(_valid[_front] == 1);
00210 --(_valid[_front]);
00211
00212 _front = (_front + 1) % (_size);
00213
00214 if (_write_space.get() < 0)
00215 _write_space = 1;
00216 else
00217 ++_write_space;
00218 }
00219
00220
00221 }
00222
00223 #endif // RAUL_SRMW_QUEUE_HPP