From 0d229deb0d6059e997d69207e152343ef811da80 Mon Sep 17 00:00:00 2001 From: David Robillard Date: Thu, 28 Apr 2011 18:19:28 +0000 Subject: Improve RingBuffer implementation. Previous implementation was broken when written to full capacity, and this version is significantly faster as well. git-svn-id: http://svn.drobilla.net/lad/trunk/raul@3213 a436a847-0d15-0410-975c-d299462d15a1 --- raul/RingBuffer.hpp | 292 +++++++++++++++++++++++++--------------------------- 1 file changed, 143 insertions(+), 149 deletions(-) (limited to 'raul/RingBuffer.hpp') diff --git a/raul/RingBuffer.hpp b/raul/RingBuffer.hpp index 32ca54d..bc17b02 100644 --- a/raul/RingBuffer.hpp +++ b/raul/RingBuffer.hpp @@ -18,208 +18,202 @@ #ifndef RAUL_RING_BUFFER_HPP #define RAUL_RING_BUFFER_HPP +#include #include - -#include -#include -#include -#include +#include +#include #include -#include "raul/log.hpp" +#include namespace Raul { +/** + A lock-free RingBuffer. -/** A lock-free RingBuffer. - * Read/Write realtime safe. - * Single-reader Single-writer thread safe. - * \ingroup raul - */ -class RingBuffer { + Thread-safe with a single reader and single writer, and realtime safe + on both ends. + + @ingroup raul +*/ +class RingBuffer : public boost::noncopyable { public: - /** @param size Size in bytes. + /** + Create a new RingBuffer. + @param size Size in bytes (note this may be rounded up). */ explicit RingBuffer(uint32_t size) - : _buf(static_cast(malloc(size))) - , _size(size) + : _size(next_power_of_two(size)) + , _size_mask(_size - 1) + , _buf(static_cast(malloc(_size))) { reset(); assert(read_space() == 0); - assert(write_space() == size - 1); + assert(write_space() == _size - 1); } - virtual ~RingBuffer() { + /** + Destroy a RingBuffer. + */ + inline ~RingBuffer() { free(_buf); } - /** Reset(empty) the ringbuffer. - * NOT thread safe. - */ - void reset() { + /** + Reset (empty) the RingBuffer. + + This method is NOT thread-safe, it may only be called when there are no + readers or writers. + */ + inline void reset() { g_atomic_int_set(&_write_ptr, 0); g_atomic_int_set(&_read_ptr, 0); } - uint32_t write_space() const { - const uint32_t w = g_atomic_int_get(&_write_ptr); + /** + Return the number of bytes of space available for reading. + */ + inline uint32_t read_space() const { const uint32_t r = g_atomic_int_get(&_read_ptr); + const uint32_t w = g_atomic_int_get(&_write_ptr); + return read_space_internal(r, w); + } - if (w > r) { - return ((r - w + _size) % _size) - 1; - } else if (w < r) { - return (r - w) - 1; - } else { - return _size - 1; - } + /** + Return the number of bytes of space available for writing. + */ + inline uint32_t write_space() const { + const uint32_t r = g_atomic_int_get(&_read_ptr); + const uint32_t w = g_atomic_int_get(&_write_ptr); + return write_space_internal(r, w); } - uint32_t read_space() const { + /** + Return the capacity (i.e. total write space when empty). + */ + inline uint32_t capacity() const { return _size - 1; } + + /** + Read from the RingBuffer without advancing the read head. + */ + inline uint32_t peek(uint32_t size, void* dst) { + const uint32_t r = g_atomic_int_get(&_read_ptr); const uint32_t w = g_atomic_int_get(&_write_ptr); + return peek_internal(r, w, size, dst); + } + + /** + Read from the RingBuffer and advance the read head. + */ + inline uint32_t read(uint32_t size, void* dst) { const uint32_t r = g_atomic_int_get(&_read_ptr); + const uint32_t w = g_atomic_int_get(&_write_ptr); - if (w > r) { - return w - r; + if (peek_internal(r, w, size, dst)) { + g_atomic_int_set(&_read_ptr, (r + size) & _size_mask); + return size; } else { - return (w - r + _size) % _size; + return 0; } } - uint32_t capacity() const { return _size; } - - uint32_t peek(uint32_t size, void* dst); - bool full_peek(uint32_t size, void* dst); - - uint32_t read(uint32_t size, void* dst); - bool full_read(uint32_t size, void* dst); - - bool skip(uint32_t size); - - void write(uint32_t size, const void* src); - -protected: - mutable uint32_t _write_ptr; - mutable uint32_t _read_ptr; - - char* const _buf; ///< Contents - const uint32_t _size; ///< Size (capacity) in bytes -}; - - -/** Peek at the ringbuffer (read w/o advancing read pointer). - * - * Note that a full read may not be done if the data wraps around. - * Caller must check return value and call again if necessary, or use the - * full_peek method which does this automatically. - */ -inline uint32_t -RingBuffer::peek(uint32_t size, void* dst) -{ - const uint32_t priv_read_ptr = g_atomic_int_get(&_read_ptr); - - const uint32_t read_size = (priv_read_ptr + size < _size) - ? size - : _size - priv_read_ptr; + /** + Skip data in the RingBuffer (advance read head without reading). + */ + inline uint32_t skip(uint32_t size) { + const uint32_t r = g_atomic_int_get(&_read_ptr); + const uint32_t w = g_atomic_int_get(&_write_ptr); + if (read_space_internal(r, w) < size) { + return 0; + } - memcpy(dst, &_buf[priv_read_ptr], read_size); + g_atomic_int_set(&_read_ptr, (r + size) & _size_mask); + return size; + } - return read_size; -} + /** + Write data to the RingBuffer. + */ + inline uint32_t write(uint32_t size, const void* src) { + const uint32_t r = g_atomic_int_get(&_read_ptr); + const uint32_t w = g_atomic_int_get(&_write_ptr); + if (write_space_internal(r, w) < size) { + return 0; + } + if (w + size <= _size) { + memcpy(&_buf[w], src, size); + g_atomic_int_set(&_write_ptr, (w + size) & _size_mask); + } else { + const uint32_t this_size = _size - w; + assert(this_size < size); + assert(w + this_size <= _size); + memcpy(&_buf[w], src, this_size); + memcpy(&_buf[0], (char*)src + this_size, size - this_size); + g_atomic_int_set(&_write_ptr, size - this_size); + } -inline bool -RingBuffer::full_peek(uint32_t size, void* dst) -{ - if (read_space() < size) { - return false; + return size; } - const uint32_t read_size = peek(size, dst); - - if (read_size < size) { - peek(size - read_size, (char*)dst + read_size); +private: + static inline uint32_t next_power_of_two(uint32_t size) { + // http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 + size--; + size |= size >> 1; + size |= size >> 2; + size |= size >> 4; + size |= size >> 8; + size |= size >> 16; + size++; + return size; } - return true; -} - - -/** Read from the ringbuffer. - * - * Note that a full read may not be done if the data wraps around. - * Caller must check return value and call again if necessary, or use the - * full_read method which does this automatically. - */ -inline uint32_t -RingBuffer::read(uint32_t size, void* dst) -{ - const uint32_t priv_read_ptr = g_atomic_int_get(&_read_ptr); - - const uint32_t read_size = (priv_read_ptr + size < _size) - ? size - : _size - priv_read_ptr; - - memcpy(dst, &_buf[priv_read_ptr], read_size); - - g_atomic_int_set(&_read_ptr, (priv_read_ptr + read_size) % _size); - - return read_size; -} - - -inline bool -RingBuffer::full_read(uint32_t size, void* dst) -{ - if (read_space() < size) { - return false; + inline uint32_t write_space_internal(uint32_t r, uint32_t w) const { + if (w > r) { + return ((r - w + _size) & _size_mask) - 1; + } else if (w < r) { + return (r - w) - 1; + } else { + return _size - 1; + } } - const uint32_t read_size = read(size, dst); - - if (read_size < size) { - read(size - read_size, (char*)dst + read_size); + inline uint32_t read_space_internal(uint32_t r, uint32_t w) const { + if (w > r) { + return w - r; + } else { + return (w - r + _size) & _size_mask; + } } - return true; -} + inline uint32_t peek_internal(uint32_t r, uint32_t w, + uint32_t size, void* dst) const { + if (read_space_internal(r, w) < size) { + return 0; + } + if (r + size < _size) { + memcpy(dst, &_buf[r], size); + } else { + const uint32_t first_size = _size - r; + memcpy(dst, &_buf[r], first_size); + memcpy(dst, &_buf[0], size - first_size); + } -inline bool -RingBuffer::skip(uint32_t size) -{ - if (read_space() < size) { - warn << "Attempt to skip past end of RingBuffer" << std::endl; - return false; + return size; } - const uint32_t priv_read_ptr = g_atomic_int_get(&_read_ptr); - g_atomic_int_set(&_read_ptr, (priv_read_ptr + size) % _size); - - return true; -} - + mutable uint32_t _write_ptr; ///< Read index into _buf + mutable uint32_t _read_ptr; ///< Write index into _buf -inline void -RingBuffer::write(uint32_t size, const void* src) -{ - const uint32_t priv_write_ptr = g_atomic_int_get(&_write_ptr); - - if (priv_write_ptr + size <= _size) { - memcpy(&_buf[priv_write_ptr], src, size); - g_atomic_int_set(&_write_ptr, (priv_write_ptr + size) % _size); - } else { - const uint32_t this_size = _size - priv_write_ptr; - assert(this_size < size); - assert(priv_write_ptr + this_size <= _size); - memcpy(&_buf[priv_write_ptr], src, this_size); - memcpy(&_buf[0], (char*)src + this_size, size - this_size); - g_atomic_int_set(&_write_ptr, size - this_size); - } -} + const uint32_t _size; ///< Size (capacity) in bytes + const uint32_t _size_mask; ///< Mask for fast modulo + char* const _buf; ///< Contents +}; } // namespace Raul #endif // RAUL_RING_BUFFER_HPP - -- cgit v1.2.1