Add a generic ring buffer implementation

This piece of code is from the JACK Audio Connection Kit
(trimmed down a bit for better readability).

The vector functions now reuse the common iovec struct used by
writev/readv instead of reinventing an identical but
differently-named struct.

From the comments:
> ISO/POSIX C version of Paul Davis's lock free ringbuffer C++ code.
> This is safe for the case of one read thread and one write thread.

License is LGPL 2.1 or later

git-svn-id: https://svn.musicpd.org/mpd/trunk@7386 09075e82-0dd4-0310-85a5-a0d7c8717e4f

3 files changed, 503 insertions, 0 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index 6d709c38a..9e053ef3e 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -66,6 +66,7 @@ mpd_headers = \
 	playerData.h \
 	playlist.h \
 	replayGain.h \
+	ringbuf.h \
 	signal_check.h \
 	sig_handlers.h \
 	sllist.h \
@@ -122,6 +123,7 @@ mpd_SOURCES = \
 	playerData.c \
 	playlist.c \
 	replayGain.c \
+	ringbuf.c \
 	sig_handlers.c \
 	signal_check.c \
 	sllist.c \
diff --git a/src/ringbuf.c b/src/ringbuf.c
new file mode 100644
index 000000000..517a4c216
--- /dev/null
+++ b/src/ringbuf.c
@@ -0,0 +1,296 @@
+/*
+ * This file is originally from JACK Audio Connection Kit
+ *
+ * Copyright (C) 2000 Paul Davis
+ * Copyright (C) 2003 Rohan Drape
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or
+ * (at your option) any later version.
+ *
+ * This program 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 Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ *
+ * ISO/POSIX C version of Paul Davis's lock free ringbuffer C++ code.
+ * This is safe for the case of one read thread and one write thread.
+ */
+
+#include "ringbuf.h"
+#include "utils.h"
+
+#define advance_ptr(ptr,cnt,mask)  ptr = (ptr + cnt) & mask
+
+/*
+ * Create a new ringbuffer to hold at least `sz' bytes of data. The
+ * actual buffer size is rounded up to the next power of two.
+ */
+struct ringbuf *ringbuf_create(size_t sz)
+{
+	struct ringbuf *rb = xmalloc(sizeof(struct ringbuf));
+	size_t power_of_two;
+
+	for (power_of_two = 1; 1 << power_of_two < sz; power_of_two++)
+		/* next power_of_two... */;
+
+	rb->size = 1 << power_of_two;
+	rb->size_mask = rb->size;
+	rb->size_mask -= 1;
+	rb->buf = xmalloc(rb->size);
+	ringbuf_reset(rb);
+
+	return rb;
+}
+
+/* Free all data associated with the ringbuffer `rb'. */
+void ringbuf_free(struct ringbuf * rb)
+{
+	free(rb->buf);
+	free(rb);
+}
+
+/* Reset the read and write pointers to zero. This is not thread safe. */
+void ringbuf_reset(struct ringbuf * rb)
+{
+	rb->read_ptr = 0;
+	rb->write_ptr = 0;
+}
+
+/*
+ * Return the number of bytes available for reading.  This is the
+ * number of bytes in front of the read pointer and behind the write
+ * pointer.
+ */
+size_t ringbuf_read_space(const struct ringbuf * rb)
+{
+	size_t w = rb->write_ptr;
+	size_t r = rb->read_ptr;
+
+	if (w > r)
+		return w - r;
+	else
+		return (w - r + rb->size) & rb->size_mask;
+}
+
+/*
+ * Return the number of bytes available for writing.  This is the
+ * number of bytes in front of the write pointer and behind the read
+ * pointer.
+ */
+size_t ringbuf_write_space(const struct ringbuf * rb)
+{
+	size_t w = rb->write_ptr;
+	size_t r = rb->read_ptr;
+
+	if (w > r)
+		return ((r - w + rb->size) & rb->size_mask) - 1;
+	else if (w < r)
+		return (r - w) - 1;
+	else
+		return rb->size - 1;
+}
+
+/*
+ * The copying data reader.  Copy at most `cnt' bytes from `rb' to
+ * `dest'.  Returns the actual number of bytes copied.
+ */
+size_t ringbuf_read(struct ringbuf * rb, void *dest, size_t cnt)
+{
+	size_t free_cnt;
+	size_t cnt2;
+	size_t to_read;
+	size_t n1, n2;
+
+	if ((free_cnt = ringbuf_read_space(rb)) == 0)
+		return 0;
+
+	to_read = cnt > free_cnt ? free_cnt : cnt;
+	cnt2 = rb->read_ptr + to_read;
+
+	if (cnt2 > rb->size) {
+		n1 = rb->size - rb->read_ptr;
+		n2 = cnt2 & rb->size_mask;
+	} else {
+		n1 = to_read;
+		n2 = 0;
+	}
+
+	memcpy(dest, rb->buf + rb->read_ptr, n1);
+	ringbuf_read_advance(rb, n1);
+
+	if (n2) {
+		memcpy(dest + n1, rb->buf + rb->read_ptr, n2);
+		ringbuf_read_advance(rb, n2);
+	}
+
+	return to_read;
+}
+
+/*
+ * The copying data reader w/o read pointer advance.  Copy at most
+ * `cnt' bytes from `rb' to `dest'.  Returns the actual number of bytes
+ * copied.
+ */
+size_t ringbuf_peek(struct ringbuf * rb, void *dest, size_t cnt)
+{
+	size_t free_cnt;
+	size_t cnt2;
+	size_t to_read;
+	size_t n1, n2;
+	size_t tmp_read_ptr = rb->read_ptr;
+
+	if ((free_cnt = ringbuf_read_space(rb)) == 0)
+		return 0;
+
+	to_read = cnt > free_cnt ? free_cnt : cnt;
+	cnt2 = tmp_read_ptr + to_read;
+
+	if (cnt2 > rb->size) {
+		n1 = rb->size - tmp_read_ptr;
+		n2 = cnt2 & rb->size_mask;
+	} else {
+		n1 = to_read;
+		n2 = 0;
+	}
+
+	memcpy(dest, rb->buf + tmp_read_ptr, n1);
+	advance_ptr(tmp_read_ptr, n1, rb->size_mask);
+
+	if (n2) {
+		memcpy(dest + n1, rb->buf + tmp_read_ptr, n2);
+		advance_ptr(tmp_read_ptr, n2, rb->size_mask);
+	}
+
+	return to_read;
+}
+
+/*
+ * The copying data writer.  Copy at most `cnt' bytes to `rb' from
+ * `src'.  Returns the actual number of bytes copied.
+ */
+size_t ringbuf_write(struct ringbuf * rb, const void *src, size_t cnt)
+{
+	size_t free_cnt;
+	size_t cnt2;
+	size_t to_write;
+	size_t n1, n2;
+
+	if ((free_cnt = ringbuf_write_space(rb)) == 0)
+		return 0;
+
+	to_write = cnt > free_cnt ? free_cnt : cnt;
+	cnt2 = rb->write_ptr + to_write;
+
+	if (cnt2 > rb->size) {
+		n1 = rb->size - rb->write_ptr;
+		n2 = cnt2 & rb->size_mask;
+	} else {
+		n1 = to_write;
+		n2 = 0;
+	}
+
+	memcpy(rb->buf + rb->write_ptr, src, n1);
+	ringbuf_write_advance(rb, n1);
+
+	if (n2) {
+		memcpy(rb->buf + rb->write_ptr, src + n1, n2);
+		ringbuf_write_advance(rb, n2);
+	}
+
+	return to_write;
+}
+
+/* Advance the read pointer `cnt' places. */
+void ringbuf_read_advance(struct ringbuf * rb, size_t cnt)
+{
+	advance_ptr(rb->read_ptr, cnt, rb->size_mask);
+}
+
+/* Advance the write pointer `cnt' places. */
+void ringbuf_write_advance(struct ringbuf * rb, size_t cnt)
+{
+	advance_ptr(rb->write_ptr, cnt, rb->size_mask);
+}
+
+/*
+ * The non-copying data reader.  `vec' is an array of two places.  Set
+ * the values at `vec' to hold the current readable data at `rb'.  If
+ * the readable data is in one segment the second segment has zero
+ * length.
+ */
+void ringbuf_get_read_vector(const struct ringbuf * rb, struct iovec * vec)
+{
+	size_t free_cnt;
+	size_t cnt2;
+	size_t w = rb->write_ptr;
+	size_t r = rb->read_ptr;
+
+	if (w > r)
+		free_cnt = w - r;
+	else
+		free_cnt = (w - r + rb->size) & rb->size_mask;
+
+	cnt2 = r + free_cnt;
+
+	if (cnt2 > rb->size) {
+		/*
+		 * Two part vector: the rest of the buffer after the current
+		 * write ptr, plus some from the start of the buffer.
+		 */
+		vec[0].iov_base = rb->buf + r;
+		vec[0].iov_len = rb->size - r;
+		vec[1].iov_base = rb->buf;
+		vec[1].iov_len = cnt2 & rb->size_mask;
+
+	} else {
+		/* Single part vector: just the rest of the buffer */
+		vec[0].iov_base = rb->buf + r;
+		vec[0].iov_len = free_cnt;
+		vec[1].iov_len = 0;
+	}
+}
+
+/*
+ * The non-copying data writer.  `vec' is an array of two places.  Set
+ * the values at `vec' to hold the current writeable data at `rb'.  If
+ * the writeable data is in one segment the second segment has zero
+ * length.
+ */
+void ringbuf_get_write_vector(const struct ringbuf * rb, struct iovec * vec)
+{
+	size_t free_cnt;
+	size_t cnt2;
+	size_t w = rb->write_ptr;
+	size_t r = rb->read_ptr;
+
+	if (w > r)
+		free_cnt = ((r - w + rb->size) & rb->size_mask) - 1;
+	else if (w < r)
+		free_cnt = (r - w) - 1;
+	else
+		free_cnt = rb->size - 1;
+
+	cnt2 = w + free_cnt;
+
+	if (cnt2 > rb->size) {
+		/*
+		 * Two part vector: the rest of the buffer after the current
+		 * write ptr, plus some from the start of the buffer.
+		 */
+		vec[0].iov_base = rb->buf + w;
+		vec[0].iov_len = rb->size - w;
+		vec[1].iov_base = rb->buf;
+		vec[1].iov_len = cnt2 & rb->size_mask;
+	} else {
+		vec[0].iov_base = rb->buf + w;
+		vec[0].iov_len = free_cnt;
+		vec[1].iov_len = 0;
+	}
+}
+
diff --git a/src/ringbuf.h b/src/ringbuf.h
new file mode 100644
index 000000000..dc3509363
--- /dev/null
+++ b/src/ringbuf.h
@@ -0,0 +1,205 @@
+/*
+ * This file is originally from JACK Audio Connection Kit
+ *
+ * Copyright (C) 2000 Paul Davis
+ * Copyright (C) 2003 Rohan Drape
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or
+ * (at your option) any later version.
+ *
+ * This program 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 Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ */
+
+#ifndef RINGBUF_H
+#define RINGBUF_H
+
+#include "os_compat.h"
+
+/** @file ringbuf.h
+ *
+ * A set of library functions to make lock-free ringbuffers available
+ * to JACK clients.  The `capture_client.c' (in the example_clients
+ * directory) is a fully functioning user of this API.
+ *
+ * The key attribute of a ringbuffer is that it can be safely accessed
+ * by two threads simultaneously -- one reading from the buffer and
+ * the other writing to it -- without using any synchronization or
+ * mutual exclusion primitives.  For this to work correctly, there can
+ * only be a single reader and a single writer thread.  Their
+ * identities cannot be interchanged.
+ */
+
+struct ringbuf {
+	void *buf;
+	size_t write_ptr;
+	size_t read_ptr;
+	size_t size;
+	size_t size_mask;
+};
+
+/**
+ * Allocates a ringbuffer data structure of a specified size. The
+ * caller must arrange for a call to ringbuf_free() to release
+ * the memory associated with the ringbuffer.
+ *
+ * @param sz the ringbuffer size in bytes.
+ *
+ * @return a pointer to a new struct ringbuf, if successful; NULL
+ * otherwise.
+ */
+struct ringbuf *ringbuf_create(size_t sz);
+
+/**
+ * Frees the ringbuffer data structure allocated by an earlier call to
+ * ringbuf_create().
+ *
+ * @param rb a pointer to the ringbuffer structure.
+ */
+void ringbuf_free(struct ringbuf * rb);
+
+/**
+ * Fill a data structure with a description of the current readable
+ * data held in the ringbuffer.  This description is returned in a two
+ * element array of struct iovec.  Two elements are needed
+ * because the data to be read may be split across the end of the
+ * ringbuffer.
+ *
+ * The first element will always contain a valid @a len field, which
+ * may be zero or greater.  If the @a len field is non-zero, then data
+ * can be read in a contiguous fashion using the address given in the
+ * corresponding @a buf field.
+ *
+ * If the second element has a non-zero @a len field, then a second
+ * contiguous stretch of data can be read from the address given in
+ * its corresponding @a buf field.
+ *
+ * @param rb a pointer to the ringbuffer structure.
+ * @param vec a pointer to a 2 element array of struct iovec.
+ *
+ */
+void ringbuf_get_read_vector(const struct ringbuf * rb, struct iovec * vec);
+
+/**
+ * Fill a data structure with a description of the current writable
+ * space in the ringbuffer.  The description is returned in a two
+ * element array of struct iovec.  Two elements are needed
+ * because the space available for writing may be split across the end
+ * of the ringbuffer.
+ *
+ * The first element will always contain a valid @a len field, which
+ * may be zero or greater.  If the @a len field is non-zero, then data
+ * can be written in a contiguous fashion using the address given in
+ * the corresponding @a buf field.
+ *
+ * If the second element has a non-zero @a len field, then a second
+ * contiguous stretch of data can be written to the address given in
+ * the corresponding @a buf field.
+ *
+ * @param rb a pointer to the ringbuffer structure.
+ * @param vec a pointer to a 2 element array of struct iovec.
+ */
+void ringbuf_get_write_vector(const struct ringbuf * rb, struct iovec * vec);
+
+/**
+ * Read data from the ringbuffer.
+ *
+ * @param rb a pointer to the ringbuffer structure.
+ * @param dest a pointer to a buffer where data read from the
+ * ringbuffer will go.
+ * @param cnt the number of bytes to read.
+ *
+ * @return the number of bytes read, which may range from 0 to cnt.
+ */
+size_t ringbuf_read(struct ringbuf * rb, void *dest, size_t cnt);
+
+/**
+ * Read data from the ringbuffer. Opposed to ringbuf_read()
+ * this function does not move the read pointer. Thus it's
+ * a convenient way to inspect data in the ringbuffer in a
+ * continous fashion. The price is that the data is copied
+ * into a user provided buffer. For "raw" non-copy inspection
+ * of the data in the ringbuffer use ringbuf_get_read_vector().
+ *
+ * @param rb a pointer to the ringbuffer structure.
+ * @param dest a pointer to a buffer where data read from the
+ * ringbuffer will go.
+ * @param cnt the number of bytes to read.
+ *
+ * @return the number of bytes read, which may range from 0 to cnt.
+ */
+size_t ringbuf_peek(struct ringbuf * rb, void *dest, size_t cnt);
+
+/**
+ * Advance the read pointer.
+ *
+ * After data have been read from the ringbuffer using the pointers
+ * returned by ringbuf_get_read_vector(), use this function to
+ * advance the buffer pointers, making that space available for future
+ * write operations.
+ *
+ * @param rb a pointer to the ringbuffer structure.
+ * @param cnt the number of bytes read.
+ */
+void ringbuf_read_advance(struct ringbuf * rb, size_t cnt);
+
+/**
+ * Return the number of bytes available for reading.
+ *
+ * @param rb a pointer to the ringbuffer structure.
+ *
+ * @return the number of bytes available to read.
+ */
+size_t ringbuf_read_space(const struct ringbuf * rb);
+
+/**
+ * Reset the read and write pointers, making an empty buffer.
+ *
+ * This is not thread safe.
+ *
+ * @param rb a pointer to the ringbuffer structure.
+ */
+void ringbuf_reset(struct ringbuf * rb);
+
+/**
+ * Write data into the ringbuffer.
+ *
+ * @param rb a pointer to the ringbuffer structure.
+ * @param src a pointer to the data to be written to the ringbuffer.
+ * @param cnt the number of bytes to write.
+ *
+ * @return the number of bytes write, which may range from 0 to cnt
+ */
+size_t ringbuf_write(struct ringbuf * rb, const void *src, size_t cnt);
+
+/**
+ * Advance the write pointer.
+ *
+ * After data have been written the ringbuffer using the pointers
+ * returned by ringbuf_get_write_vector(), use this function
+ * to advance the buffer pointer, making the data available for future
+ * read operations.
+ *
+ * @param rb a pointer to the ringbuffer structure.
+ * @param cnt the number of bytes written.
+ */
+void ringbuf_write_advance(struct ringbuf * rb, size_t cnt);
+
+/**
+ * Return the number of bytes available for writing.
+ *
+ * @param rb a pointer to the ringbuffer structure.
+ *
+ * @return the amount of free space (in bytes) available for writing.
+ */
+size_t ringbuf_write_space(const struct ringbuf * rb);
+
+#endif /* RINGBUF_H */