• 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 #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

Generated on Sun Sep 12 2010 for RAUL by  doxygen 1.7.1