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