RAUL
0.8.0
|
00001 /* This file is part of Raul. 00002 * Copyright (C) 2007-2009 David Robillard <http://drobilla.net> 00003 * 00004 * Raul is free software; you can redistribute it and/or modify it under the 00005 * terms of the GNU General Public License as published by the Free Software 00006 * Foundation; either version 2 of the License, or (at your option) any later 00007 * version. 00008 * 00009 * Raul is distributed in the hope that it will be useful, but WITHOUT ANY 00010 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 00011 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for details. 00012 * 00013 * You should have received a copy of the GNU General Public License along 00014 * with this program; if not, write to the Free Software Foundation, Inc., 00015 * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 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 // Any thread: 00062 00063 inline size_t capacity() const { return _size-1; } 00064 00065 00066 // Write thread(s): 00067 00068 inline bool full() const; 00069 inline bool push(const T& obj); 00070 00071 00072 // Read thread: 00073 00074 inline bool empty() const; 00075 inline T& front() const; 00076 inline void pop(); 00077 00078 private: 00079 00080 // Note that _front doesn't need to be an AtomicInt since it's only accessed 00081 // by the (single) reader thread 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 /* Technically right here pop could be called in the reader thread and 00146 * make space available, but no harm in failing anyway - this queue 00147 * really isn't designed to be filled... */ 00148 00149 if (already_full) { 00150 00151 /* if multiple threads simultaneously get here, _write_space may be 0 00152 * or negative. The next call to pop() will set _write_space back to 00153 * a sane value. Note that _write_space is not exposed, so this is okay 00154 * (... assuming this code is correct) */ 00155 00156 return false; 00157 00158 } else { 00159 00160 // Note: _size must be a power of 2 for this to not explode when _back overflows 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 } // namespace Raul 00222 00223 #endif // RAUL_SRMW_QUEUE_HPP