RAUL 0.8.0

- Main Page
- Modules
- Namespaces
- Classes
- Files

- File List

SRMWQueue.hpp

    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