/builddir/build/BUILD/raul-0.4.0/raul/SRMWQueue.hpp

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

Generated on Wed Apr 9 08:14:41 2008 for RAUL by  doxygen 1.5.1