Chris@49: /* -*- c-basic-offset: 4 indent-tabs-mode: nil -*- vi:set ts=8 sts=4 sw=4: */ Chris@0: Chris@0: /* Chris@52: Sonic Visualiser Chris@52: An audio file viewer and annotation editor. Chris@52: Centre for Digital Music, Queen Mary, University of London. Chris@0: Chris@52: This program is free software; you can redistribute it and/or Chris@52: modify it under the terms of the GNU General Public License as Chris@52: published by the Free Software Foundation; either version 2 of the Chris@52: License, or (at your option) any later version. See the file Chris@52: COPYING included with this distribution for more information. Chris@0: */ Chris@0: Chris@0: /* Chris@0: This is a modified version of a source file from the Chris@0: Rosegarden MIDI and audio sequencer and notation editor. Chris@17: This file copyright 2000-2006 Chris Cannam. Chris@0: */ Chris@0: Chris@1553: #ifndef SV_RINGBUFFER_H Chris@1553: #define SV_RINGBUFFER_H Chris@0: Chris@0: #include Chris@0: Chris@150: #include "system/System.h" Chris@0: Chris@1553: #include Chris@1827: #include Chris@1553: Chris@1827: #include Chris@485: Chris@0: //#define DEBUG_RINGBUFFER 1 Chris@0: Chris@0: #ifdef DEBUG_RINGBUFFER Chris@0: #include Chris@0: #endif Chris@0: Chris@0: /** Chris@0: * RingBuffer implements a lock-free ring buffer for one writer and N Chris@0: * readers, that is to be used to store a sample type T. Chris@0: */ Chris@0: Chris@0: template Chris@0: class RingBuffer Chris@0: { Chris@0: public: Chris@0: /** Chris@0: * Create a ring buffer with room to write n samples. Chris@0: * Chris@0: * Note that the internal storage size will actually be n+1 Chris@0: * samples, as one element is unavailable for administrative Chris@0: * reasons. Since the ring buffer performs best if its size is a Chris@0: * power of two, this means n should ideally be some power of two Chris@0: * minus one. Chris@0: */ Chris@928: RingBuffer(int n); Chris@0: Chris@0: virtual ~RingBuffer(); Chris@0: Chris@0: /** Chris@0: * Return the total capacity of the ring buffer in samples. Chris@0: * (This is the argument n passed to the constructor.) Chris@0: */ Chris@928: int getSize() const; Chris@0: Chris@0: /** Chris@1827: * Return a new ring buffer of the given size, containing the same Chris@1827: * data as this one as perceived by reader 0 of this buffer. If Chris@1827: * another thread reads from or writes to this buffer during the Chris@1827: * call, the contents of the new buffer may be incomplete or Chris@835: * inconsistent. If this buffer's data will not fit in the new Chris@1827: * size, the contents are undetermined. Chris@0: */ Chris@1827: RingBuffer resized(int newSize) const; Chris@0: Chris@0: /** Chris@0: * Reset read and write pointers, thus emptying the buffer. Chris@0: * Should be called from the write thread. Chris@0: */ Chris@0: void reset(); Chris@0: Chris@0: /** Chris@0: * Return the amount of data available for reading by reader R, in Chris@0: * samples. Chris@0: */ Chris@928: int getReadSpace(int R = 0) const; Chris@0: Chris@0: /** Chris@0: * Return the amount of space available for writing, in samples. Chris@0: */ Chris@928: int getWriteSpace() const; Chris@0: Chris@0: /** Chris@0: * Read n samples from the buffer, for reader R. If fewer than n Chris@0: * are available, the remainder will be zeroed out. Returns the Chris@0: * number of samples actually read. Chris@0: */ Chris@928: int read(T *destination, int n, int R = 0); Chris@0: Chris@0: /** Chris@0: * Read n samples from the buffer, for reader R, adding them to Chris@0: * the destination. If fewer than n are available, the remainder Chris@0: * will be left alone. Returns the number of samples actually Chris@0: * read. Chris@0: */ Chris@928: int readAdding(T *destination, int n, int R = 0); Chris@0: Chris@0: /** Chris@0: * Read one sample from the buffer, for reader R. If no sample is Chris@0: * available, this will silently return zero. Calling this Chris@0: * repeatedly is obviously slower than calling read once, but it Chris@0: * may be good enough if you don't want to allocate a buffer to Chris@0: * read into. Chris@0: */ Chris@0: T readOne(int R = 0); Chris@0: Chris@0: /** Chris@0: * Read n samples from the buffer, if available, for reader R, Chris@0: * without advancing the read pointer -- i.e. a subsequent read() Chris@0: * or skip() will be necessary to empty the buffer. If fewer than Chris@0: * n are available, the remainder will be zeroed out. Returns the Chris@0: * number of samples actually read. Chris@0: */ Chris@928: int peek(T *destination, int n, int R = 0) const; Chris@0: Chris@0: /** Chris@0: * Read one sample from the buffer, if available, without Chris@0: * advancing the read pointer -- i.e. a subsequent read() or Chris@0: * skip() will be necessary to empty the buffer. Returns zero if Chris@0: * no sample was available. Chris@0: */ Chris@0: T peekOne(int R = 0) const; Chris@0: Chris@0: /** Chris@0: * Pretend to read n samples from the buffer, for reader R, Chris@0: * without actually returning them (i.e. discard the next n Chris@0: * samples). Returns the number of samples actually available for Chris@0: * discarding. Chris@0: */ Chris@928: int skip(int n, int R = 0); Chris@0: Chris@0: /** Chris@0: * Write n samples to the buffer. If insufficient space is Chris@0: * available, not all samples may actually be written. Returns Chris@0: * the number of samples actually written. Chris@0: */ Chris@928: int write(const T *source, int n); Chris@0: Chris@0: /** Chris@0: * Write n zero-value samples to the buffer. If insufficient Chris@0: * space is available, not all zeros may actually be written. Chris@0: * Returns the number of zeroes actually written. Chris@0: */ Chris@928: int zero(int n); Chris@0: Chris@1827: RingBuffer(const RingBuffer &) =default; Chris@1827: RingBuffer &operator=(const RingBuffer &) =default; Chris@1827: Chris@0: protected: Chris@1829: std::vector> m_buffer; Chris@1827: int m_writer; Chris@1827: std::vector m_readers; Chris@1827: int m_size; Chris@0: }; Chris@0: Chris@0: template Chris@928: RingBuffer::RingBuffer(int n) : Chris@1827: m_buffer(n + 1, T()), Chris@0: m_writer(0), Chris@1827: m_readers(N, 0), Chris@574: m_size(n + 1) Chris@0: { Chris@0: #ifdef DEBUG_RINGBUFFER Chris@0: std::cerr << "RingBuffer[" << this << "]::RingBuffer(" << n << ")" << std::endl; Chris@0: #endif Chris@0: } Chris@0: Chris@0: template Chris@0: RingBuffer::~RingBuffer() Chris@0: { Chris@0: #ifdef DEBUG_RINGBUFFER Chris@0: std::cerr << "RingBuffer[" << this << "]::~RingBuffer" << std::endl; Chris@0: #endif Chris@0: } Chris@0: Chris@0: template Chris@928: int Chris@0: RingBuffer::getSize() const Chris@0: { Chris@0: #ifdef DEBUG_RINGBUFFER Chris@0: std::cerr << "RingBuffer[" << this << "]::getSize(): " << m_size-1 << std::endl; Chris@0: #endif Chris@0: Chris@0: return m_size - 1; Chris@0: } Chris@0: Chris@0: template Chris@1827: RingBuffer Chris@928: RingBuffer::resized(int newSize) const Chris@0: { Chris@0: #ifdef DEBUG_RINGBUFFER Chris@835: std::cerr << "RingBuffer[" << this << "]::resized(" << newSize << ")" << std::endl; Chris@0: #endif Chris@0: Chris@1827: RingBuffer newBuffer(newSize); Chris@0: Chris@835: int w = m_writer; Chris@835: int r = m_readers[0]; Chris@835: Chris@835: while (r != w) { Chris@835: T value = m_buffer[r]; Chris@835: newBuffer->write(&value, 1); Chris@835: if (++r == m_size) r = 0; Chris@0: } Chris@0: Chris@835: return newBuffer; Chris@0: } Chris@0: Chris@0: template Chris@0: void Chris@0: RingBuffer::reset() Chris@0: { Chris@0: #ifdef DEBUG_RINGBUFFER Chris@0: std::cerr << "RingBuffer[" << this << "]::reset" << std::endl; Chris@0: #endif Chris@0: Chris@0: m_writer = 0; Chris@1827: for (int i = 0; i < N; ++i) { Chris@1827: m_readers[i] = 0; Chris@1827: } Chris@0: } Chris@0: Chris@0: template Chris@928: int Chris@0: RingBuffer::getReadSpace(int R) const Chris@0: { Chris@928: int writer = m_writer; Chris@928: int reader = m_readers[R]; Chris@928: int space = 0; Chris@0: Chris@0: if (writer > reader) space = writer - reader; Chris@0: else space = ((writer + m_size) - reader) % m_size; Chris@0: Chris@0: #ifdef DEBUG_RINGBUFFER Chris@0: std::cerr << "RingBuffer[" << this << "]::getReadSpace(" << R << "): " << space << std::endl; Chris@0: #endif Chris@0: Chris@0: return space; Chris@0: } Chris@0: Chris@0: template Chris@928: int Chris@0: RingBuffer::getWriteSpace() const Chris@0: { Chris@928: int space = 0; Chris@0: for (int i = 0; i < N; ++i) { Chris@1429: int here = (m_readers[i] + m_size - m_writer - 1) % m_size; Chris@1429: if (i == 0 || here < space) space = here; Chris@0: } Chris@0: Chris@0: #ifdef DEBUG_RINGBUFFER Chris@928: int rs(getReadSpace()), rp(m_readers[0]); Chris@0: Chris@0: std::cerr << "RingBuffer: write space " << space << ", read space " Chris@1429: << rs << ", total " << (space + rs) << ", m_size " << m_size << std::endl; Chris@0: std::cerr << "RingBuffer: reader " << rp << ", writer " << m_writer << std::endl; Chris@0: #endif Chris@0: Chris@0: #ifdef DEBUG_RINGBUFFER Chris@0: std::cerr << "RingBuffer[" << this << "]::getWriteSpace(): " << space << std::endl; Chris@0: #endif Chris@0: Chris@0: return space; Chris@0: } Chris@0: Chris@0: template Chris@928: int Chris@928: RingBuffer::read(T *destination, int n, int R) Chris@0: { Chris@0: #ifdef DEBUG_RINGBUFFER Chris@0: std::cerr << "RingBuffer[" << this << "]::read(dest, " << n << ", " << R << ")" << std::endl; Chris@0: #endif Chris@0: Chris@928: int available = getReadSpace(R); Chris@0: if (n > available) { Chris@0: #ifdef DEBUG_RINGBUFFER Chris@1429: std::cerr << "WARNING: Only " << available << " samples available" Chris@1429: << std::endl; Chris@0: #endif Chris@1827: breakfastquay::v_zero(destination + available, n - available); Chris@1429: n = available; Chris@0: } Chris@0: if (n == 0) return n; Chris@0: Chris@928: int here = m_size - m_readers[R]; Chris@0: if (here >= n) { Chris@1827: breakfastquay::v_copy(destination, m_buffer.data() + m_readers[R], n); Chris@0: } else { Chris@1827: breakfastquay::v_copy(destination, m_buffer.data() + m_readers[R], here); Chris@1827: breakfastquay::v_copy(destination + here, m_buffer.data(), n - here); Chris@0: } Chris@0: Chris@1553: BQ_MBARRIER(); Chris@0: m_readers[R] = (m_readers[R] + n) % m_size; Chris@0: Chris@0: #ifdef DEBUG_RINGBUFFER Chris@0: std::cerr << "RingBuffer[" << this << "]::read: read " << n << ", reader now " << m_readers[R] << std::endl; Chris@0: #endif Chris@0: Chris@0: return n; Chris@0: } Chris@0: Chris@0: template Chris@928: int Chris@928: RingBuffer::readAdding(T *destination, int n, int R) Chris@0: { Chris@0: #ifdef DEBUG_RINGBUFFER Chris@0: std::cerr << "RingBuffer[" << this << "]::readAdding(dest, " << n << ", " << R << ")" << std::endl; Chris@0: #endif Chris@0: Chris@928: int available = getReadSpace(R); Chris@0: if (n > available) { Chris@0: #ifdef DEBUG_RINGBUFFER Chris@1429: std::cerr << "WARNING: Only " << available << " samples available" Chris@1429: << std::endl; Chris@0: #endif Chris@1429: n = available; Chris@0: } Chris@0: if (n == 0) return n; Chris@0: Chris@928: int here = m_size - m_readers[R]; Chris@0: Chris@0: if (here >= n) { Chris@1429: for (int i = 0; i < n; ++i) { Chris@1827: destination[i] += (m_buffer.data() + m_readers[R])[i]; Chris@1429: } Chris@0: } else { Chris@1429: for (int i = 0; i < here; ++i) { Chris@1827: destination[i] += (m_buffer.data() + m_readers[R])[i]; Chris@1429: } Chris@1429: for (int i = 0; i < (n - here); ++i) { Chris@1429: destination[i + here] += m_buffer[i]; Chris@1429: } Chris@0: } Chris@0: Chris@1553: BQ_MBARRIER(); Chris@0: m_readers[R] = (m_readers[R] + n) % m_size; Chris@0: return n; Chris@0: } Chris@0: Chris@0: template Chris@0: T Chris@0: RingBuffer::readOne(int R) Chris@0: { Chris@0: #ifdef DEBUG_RINGBUFFER Chris@0: std::cerr << "RingBuffer[" << this << "]::readOne(" << R << ")" << std::endl; Chris@0: #endif Chris@0: Chris@0: if (m_writer == m_readers[R]) { Chris@0: #ifdef DEBUG_RINGBUFFER Chris@1429: std::cerr << "WARNING: No sample available" Chris@1429: << std::endl; Chris@0: #endif Chris@1827: return T(); Chris@0: } Chris@0: T value = m_buffer[m_readers[R]]; Chris@1553: BQ_MBARRIER(); Chris@0: if (++m_readers[R] == m_size) m_readers[R] = 0; Chris@0: return value; Chris@0: } Chris@0: Chris@0: template Chris@928: int Chris@928: RingBuffer::peek(T *destination, int n, int R) const Chris@0: { Chris@0: #ifdef DEBUG_RINGBUFFER Chris@0: std::cerr << "RingBuffer[" << this << "]::peek(dest, " << n << ", " << R << ")" << std::endl; Chris@0: #endif Chris@0: Chris@928: int available = getReadSpace(R); Chris@0: if (n > available) { Chris@0: #ifdef DEBUG_RINGBUFFER Chris@1429: std::cerr << "WARNING: Only " << available << " samples available" Chris@1429: << std::endl; Chris@0: #endif Chris@1827: breakfastquay::v_zero(destination + available, n - available); Chris@1429: n = available; Chris@0: } Chris@0: if (n == 0) return n; Chris@0: Chris@928: int here = m_size - m_readers[R]; Chris@0: if (here >= n) { Chris@1827: breakfastquay::v_copy(destination, m_buffer.data() + m_readers[R], n); Chris@0: } else { Chris@1827: breakfastquay::v_copy(destination, m_buffer.data() + m_readers[R], here); Chris@1827: breakfastquay::v_copy(destination + here, m_buffer.data(), n - here); Chris@0: } Chris@0: Chris@0: #ifdef DEBUG_RINGBUFFER Chris@0: std::cerr << "RingBuffer[" << this << "]::peek: read " << n << std::endl; Chris@0: #endif Chris@0: Chris@0: return n; Chris@0: } Chris@0: Chris@0: template Chris@0: T Chris@0: RingBuffer::peekOne(int R) const Chris@0: { Chris@0: #ifdef DEBUG_RINGBUFFER Chris@0: std::cerr << "RingBuffer[" << this << "]::peek(" << R << ")" << std::endl; Chris@0: #endif Chris@0: Chris@0: if (m_writer == m_readers[R]) { Chris@0: #ifdef DEBUG_RINGBUFFER Chris@1429: std::cerr << "WARNING: No sample available" Chris@1429: << std::endl; Chris@0: #endif Chris@1827: return T(); Chris@0: } Chris@0: T value = m_buffer[m_readers[R]]; Chris@0: return value; Chris@0: } Chris@0: Chris@0: template Chris@928: int Chris@928: RingBuffer::skip(int n, int R) Chris@0: { Chris@0: #ifdef DEBUG_RINGBUFFER Chris@0: std::cerr << "RingBuffer[" << this << "]::skip(" << n << ", " << R << ")" << std::endl; Chris@0: #endif Chris@0: Chris@928: int available = getReadSpace(R); Chris@0: if (n > available) { Chris@0: #ifdef DEBUG_RINGBUFFER Chris@1429: std::cerr << "WARNING: Only " << available << " samples available" Chris@1429: << std::endl; Chris@0: #endif Chris@1429: n = available; Chris@0: } Chris@0: if (n == 0) return n; Chris@0: m_readers[R] = (m_readers[R] + n) % m_size; Chris@0: return n; Chris@0: } Chris@0: Chris@0: template Chris@928: int Chris@928: RingBuffer::write(const T *source, int n) Chris@0: { Chris@0: #ifdef DEBUG_RINGBUFFER Chris@0: std::cerr << "RingBuffer[" << this << "]::write(" << n << ")" << std::endl; Chris@0: #endif Chris@0: Chris@928: int available = getWriteSpace(); Chris@0: if (n > available) { Chris@0: #ifdef DEBUG_RINGBUFFER Chris@1429: std::cerr << "WARNING: Only room for " << available << " samples" Chris@1429: << std::endl; Chris@0: #endif Chris@1429: n = available; Chris@0: } Chris@0: if (n == 0) return n; Chris@0: Chris@928: int here = m_size - m_writer; Chris@0: if (here >= n) { Chris@1827: breakfastquay::v_copy(m_buffer.data() + m_writer, source, n); Chris@0: } else { Chris@1827: breakfastquay::v_copy(m_buffer.data() + m_writer, source, here); Chris@1827: breakfastquay::v_copy(m_buffer.data(), source + here, n - here); Chris@0: } Chris@0: Chris@1553: BQ_MBARRIER(); Chris@0: m_writer = (m_writer + n) % m_size; Chris@0: Chris@0: #ifdef DEBUG_RINGBUFFER Chris@0: std::cerr << "RingBuffer[" << this << "]::write: wrote " << n << ", writer now " << m_writer << std::endl; Chris@0: #endif Chris@0: Chris@0: return n; Chris@0: } Chris@0: Chris@0: template Chris@928: int Chris@928: RingBuffer::zero(int n) Chris@0: { Chris@0: #ifdef DEBUG_RINGBUFFER Chris@0: std::cerr << "RingBuffer[" << this << "]::zero(" << n << ")" << std::endl; Chris@0: #endif Chris@0: Chris@928: int available = getWriteSpace(); Chris@0: if (n > available) { Chris@0: #ifdef DEBUG_RINGBUFFER Chris@1429: std::cerr << "WARNING: Only room for " << available << " samples" Chris@1429: << std::endl; Chris@0: #endif Chris@1429: n = available; Chris@0: } Chris@0: if (n == 0) return n; Chris@0: Chris@928: int here = m_size - m_writer; Chris@0: if (here >= n) { Chris@1827: breakfastquay::v_zero(m_buffer.data() + m_writer, n); Chris@0: } else { Chris@1827: breakfastquay::v_zero(m_buffer.data() + m_writer, here); Chris@1827: breakfastquay::v_zero(m_buffer.data(), n - here); Chris@0: } Chris@835: Chris@1553: BQ_MBARRIER(); Chris@0: m_writer = (m_writer + n) % m_size; Chris@0: return n; Chris@0: } Chris@0: Chris@0: #endif // _RINGBUFFER_H_