SRMWQueue.hpp
/* This file is part of Raul.
* Copyright (C) 2007-2009 David Robillard <http://drobilla.net>
*
* Raul is free software; you can redistribute it and/or modify it under the
* terms of the GNU General Public License as published by the Free Software
* Foundation; either version 2 of the License, or (at your option) any later
* version.
*
* Raul is distributed in the hope that it will be useful, but WITHOUT ANY
* WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
* FOR A PARTICULAR PURPOSE. See the GNU General Public License for details.
*
* You should have received a copy of the GNU General Public License along
* with this program; if not, write to the Free Software Foundation, Inc.,
* 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
*/
#ifndef RAUL_SRMW_QUEUE_HPP
#define RAUL_SRMW_QUEUE_HPP
#include <cassert>
#include <cstdlib>
#include <cmath>
#include <boost/utility.hpp>
#include "raul/AtomicInt.hpp"
namespace Raul {
template <typename T>
class SRMWQueue : boost::noncopyable
{
public:
explicit SRMWQueue(size_t size);
~SRMWQueue();
// Any thread:
inline size_t capacity() const { return _size-1; }
// Write thread(s):
inline bool full() const;
inline bool push(const T& obj);
// Read thread:
inline bool empty() const;
inline T& front() const;
inline void pop();
private:
// Note that _front doesn't need to be an AtomicInt since it's only accessed
// by the (single) reader thread
unsigned _front;
AtomicInt _back;
AtomicInt _write_space;
const unsigned _size;
T* const _objects;
AtomicInt* const _valid;
};
template<typename T>
SRMWQueue<T>::SRMWQueue(size_t size)
: _front(0)
, _back(0)
, _write_space(size)
, _size(size+1)
, _objects((T*)calloc(_size, sizeof(T)))
, _valid((AtomicInt*)calloc(_size, sizeof(AtomicInt)))
{
assert(log2(size) - (int)log2(size) == 0);
assert(size > 1);
assert(_size-1 == (unsigned)_write_space.get());
for (unsigned i=0; i < _size; ++i) {
assert(_valid[i].get() == 0);
}
}
template <typename T>
SRMWQueue<T>::~SRMWQueue()
{
free(_objects);
}
template <typename T>
inline bool
SRMWQueue<T>::full() const
{
return (_write_space.get() <= 0);
}
template <typename T>
inline bool
SRMWQueue<T>::push(const T& elem)
{
const int old_write_space = _write_space.exchange_and_add(-1);
const bool already_full = ( old_write_space <= 0 );
/* Technically right here pop could be called in the reader thread and
* make space available, but no harm in failing anyway - this queue
* really isn't designed to be filled... */
if (already_full) {
/* if multiple threads simultaneously get here, _write_space may be 0
* or negative. The next call to pop() will set _write_space back to
* a sane value. Note that _write_space is not exposed, so this is okay
* (... assuming this code is correct) */
return false;
} else {
// Note: _size must be a power of 2 for this to not explode when _back overflows
const unsigned write_index = (unsigned)_back.exchange_and_add(1) % _size;
assert(_valid[write_index] == 0);
_objects[write_index] = elem;
++(_valid[write_index]);
return true;
}
}
template <typename T>
inline bool
SRMWQueue<T>::empty() const
{
return (_valid[_front].get() == 0);
}
template <typename T>
inline T&
SRMWQueue<T>::front() const
{
return _objects[_front];
}
template <typename T>
inline void
SRMWQueue<T>::pop()
{
assert(_valid[_front] == 1);
--(_valid[_front]);
_front = (_front + 1) % (_size);
if (_write_space.get() < 0)
_write_space = 1;
else
++_write_space;
}
} // namespace Raul
#endif // RAUL_SRMW_QUEUE_HPP
Raul::SRMWQueue
Realtime-safe single-reader multi-writer queue (aka lock-free ringbuffer)
Definition: SRMWQueue.hpp:54
Raul::SRMWQueue::push
bool push(const T &obj)
Push an item onto the back of the SRMWQueue - realtime-safe, not thread-safe.
Definition: SRMWQueue.hpp:140
Raul::SRMWQueue::empty
bool empty() const
Return whether the queue is empty.
Definition: SRMWQueue.hpp:179
Raul::SRMWQueue::pop
void pop()
Pop an item off the front of the queue - realtime-safe, NOT thread-safe.
Definition: SRMWQueue.hpp:207
Raul
Definition: Array.hpp:26
Raul::SRMWQueue::front
T & front() const
Return the element at the front of the queue without removing it.
Definition: SRMWQueue.hpp:192
Raul::AtomicInt
Atomic integer.
Definition: AtomicInt.hpp:29
Raul::SRMWQueue::full
bool full() const
Return whether the queue is full.
Definition: SRMWQueue.hpp:125