RAUL
0.7.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 #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 // Any thread: 00060 00061 inline size_t capacity() const { return _size-1; } 00062 00063 00064 // Write thread(s): 00065 00066 inline bool full() const; 00067 inline bool push(const T& obj); 00068 00069 00070 // Read thread: 00071 00072 inline bool empty() const; 00073 inline T& front() const; 00074 inline void pop(); 00075 00076 private: 00077 00078 // Note that _front doesn't need to be an AtomicInt since it's only accessed 00079 // by the (single) reader thread 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 /* Technically right here pop could be called in the reader thread and 00144 * make space available, but no harm in failing anyway - this queue 00145 * really isn't designed to be filled... */ 00146 00147 if (already_full) { 00148 00149 /* if multiple threads simultaneously get here, _write_space may be 0 00150 * or negative. The next call to pop() will set _write_space back to 00151 * a sane value. Note that _write_space is not exposed, so this is okay 00152 * (... assuming this code is correct) */ 00153 00154 return false; 00155 00156 } else { 00157 00158 // Note: _size must be a power of 2 for this to not explode when _back overflows 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 } // namespace Raul 00220 00221 #endif // RAUL_SRMW_QUEUE_HPP