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