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

5 files changed, 196 insertions, 307 deletions

diff --git a/raul/EventRingBuffer.hpp b/raul/EventRingBuffer.hpp
deleted file mode 100644
index 803df11..0000000
--- a/raul/EventRingBuffer.hpp
+++ /dev/null
@@ -1,83 +0,0 @@
-/* This file is part of Raul.
- * Copyright 2007-2011 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_EVENT_RING_BUFFER_HPP
-#define RAUL_EVENT_RING_BUFFER_HPP
-
-#include <cassert>
-#include <algorithm>
-#include "raul/RingBuffer.hpp"
-#include "raul/TimeStamp.hpp"
-
-namespace Raul {
-
-
-/** A RingBuffer of events (generic time-stamped binary "blobs").
- *
- * This packs a timestamp, size, and size bytes of data flat into the buffer.
- * Useful for MIDI events, OSC messages, etc.
- * \ingroup raul
- */
-class EventRingBuffer : private Raul::RingBuffer {
-public:
-
-	/** @param capacity Ringbuffer capacity in bytes.
-	 */
-	explicit EventRingBuffer(size_t capacity)
-		: RingBuffer(capacity)
-	{}
-
-	size_t capacity() const { return _size; }
-
-	size_t write(TimeStamp time, size_t size, const uint8_t* buf);
-	bool   read(TimeStamp* time, size_t* size, uint8_t* buf);
-};
-
-
-inline bool
-EventRingBuffer::read(TimeStamp* time, size_t* size, uint8_t* buf)
-{
-	bool success = RingBuffer::full_read(sizeof(TimeStamp), (uint8_t*)time);
-	if (success)
-		success = RingBuffer::full_read(sizeof(size_t), (uint8_t*)size);
-	if (success)
-		success = RingBuffer::full_read(*size, buf);
-
-	return success;
-}
-
-
-inline size_t
-EventRingBuffer::write(TimeStamp time, size_t size, const uint8_t* buf)
-{
-	assert(size > 0);
-
-	if (write_space() < (sizeof(TimeStamp) + sizeof(size_t) + size)) {
-		return 0;
-	} else {
-		RingBuffer::write(sizeof(TimeStamp), (uint8_t*)&time);
-		RingBuffer::write(sizeof(size_t), (uint8_t*)&size);
-		RingBuffer::write(size, buf);
-		return size;
-	}
-}
-
-
-} // namespace Raul
-
-#endif // RAUL_EVENT_RING_BUFFER_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 <assert.h>
 #include <stdint.h>
-
-#include <cassert>
-#include <cstdlib>
-#include <cstring>
-#include <iostream>
+#include <stdlib.h>
+#include <string.h>
 
 #include <glib.h>
 
-#include "raul/log.hpp"
+#include <boost/utility.hpp>
 
 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<char*>(malloc(size)))
-		, _size(size)
+		: _size(next_power_of_two(size))
+		, _size_mask(_size - 1)
+		, _buf(static_cast<char*>(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
-
diff --git a/test/midi_ringbuffer_test.cpp b/test/midi_ringbuffer_test.cpp
deleted file mode 100644
index fed3ca0..0000000
--- a/test/midi_ringbuffer_test.cpp
+++ /dev/null
@@ -1,48 +0,0 @@
-#include <iostream>
-#include <cstring>
-#include <cstdio>
-#include <stdio.h>
-#include "raul/TimeStamp.hpp"
-#include "raul/EventRingBuffer.hpp"
-#include "raul/midi_names.h"
-
-using namespace std;
-using namespace Raul;
-
-int
-read_write_test(EventRingBuffer& rb, unsigned offset)
-{
-	TimeStamp     t(TimeUnit(TimeUnit::FRAMES, 48000), 0, 0);
-	size_t        size;
-	unsigned char write_buf[5];
-	unsigned char read_buf[5];
-
-	snprintf(reinterpret_cast<char*>(write_buf), 5, "%d", offset);
-	size = strlen(reinterpret_cast<const char*>(write_buf));
-
-#ifndef NDEBUG
-	const size_t written = rb.write(t, size, write_buf);
-	assert(written == size);
-#endif
-
-	rb.read(&t, &size, read_buf);
-
-	return strncmp(
-			reinterpret_cast<const char*>(write_buf),
-			reinterpret_cast<const char*>(read_buf),
-			size);
-}
-
-
-int
-main()
-{
-	EventRingBuffer rb(32);
-
-	for (size_t i = 0; i < 100000; ++i)
-		if (read_write_test(rb, i))
-			return 1;
-
-	return 0;
-}
-
diff --git a/test/ringbuffer_test.cpp b/test/ringbuffer_test.cpp
index 3a36bb8..ea1088c 100644
--- a/test/ringbuffer_test.cpp
+++ b/test/ringbuffer_test.cpp
@@ -1,47 +1,74 @@
 #include <iostream>
 #include <cstring>
+#include <cstdlib>
+
+#include "raul/log.hpp"
 #include "raul/RingBuffer.hpp"
 
 using namespace std;
 using namespace Raul;
 
-void
-print_buf(size_t size, char* buf)
-{
-	cout << "{ ";
-	for (size_t i=0; i < size; ++i) {
-		cout << buf[i];
-		if (i < size-1)
-			cout << ", ";
-	}
-
-	cout << " }" << endl;
-}
-
-
 int
 main()
 {
-	RingBuffer rb(5);
+	static const int n_tests = 32;
+	for (int i = 0; i < n_tests; ++i) {
+		const int size = (rand() % 2000) + 8;
+		RingBuffer rb(size);
 
-	char ev[] = { 'a', 'b', 'c' };
+		for (int j = 0; j < size * 32; ++j) {
+			char ev1[] = { 'a', 'b', 'c' };
+			rb.write(3, ev1);
 
-	rb.write(3, ev);
+			char buf[3];
+			uint32_t read = rb.read(3, buf);
+			if (read != 3 || strncmp(buf, "abc", 3)) {
+				error << "Corrupt event " << i << ".1: "
+				      << buf[0] << buf[1] << buf[2] << endl;
+				return 1;
+			}
+	
+			char ev2[] = { 'd', 'e', 'f' };
+			if (!rb.write(3, ev2)) {
+				error << "Failed write " << i << ".2" << endl;
+				return 1;
+			}
 
-	char buf[3];
-	rb.read(3, buf);
-	print_buf(3, buf);
+			char ev3[] = { 'g', 'h' };
+			if (!rb.write(2, ev3)) {
+				error << "Failed write " << i << ".3" << endl;
+				return 1;
+			}
 
-	char ev2[] = { 'd', 'e', 'f' };
-	rb.write(3, ev2);
+			if (rb.skip(1) != 1) {
+				error << "Failed skip " << i << endl;
+				return 1;
+			}
 
+			uint32_t n_read = rb.read(2, buf);
+			if (n_read != 2 || strncmp(buf, "ef", 2)) {
+				error << "Corrupt event " << i << ".4: "
+				      << buf[0] << buf[1] << buf[2] << endl;
+				return 1;
+			}
 
-	size_t read = rb.read(3, buf);
-	if (read < 3)
-		rb.read(3 - read, buf + read);
+			n_read = rb.peek(2, buf);
+			if (n_read != 2 || strncmp(buf, "gh", 2)) {
+				error << "Corrupt peek event " << i << ".5: "
+				      << buf[0] << buf[1] << endl;
+				return 1;
+			}
 
-	print_buf(3, buf);
+			n_read = rb.read(2, buf);
+			if (n_read != 2 || strncmp(buf, "gh", 2)) {
+				error << "Corrupt event " << i << ".6: "
+				      << buf[0] << buf[1] << endl;
+				return 1;
+			}
+		}
+	}
 
+	info << "Successfully ran " << n_tests << " tests." << endl;
 	return 0;
 }
 
diff --git a/wscript b/wscript
index 652d11e..f6d9585 100644
--- a/wscript
+++ b/wscript
@@ -77,7 +77,6 @@ tests = '''
         test/atom_test
         test/atomic_test
         test/list_test
-        test/midi_ringbuffer_test
         test/path_test
         test/quantize_test
         test/queue_test