1 /* -*- c-basic-offset: 4 indent-tabs-mode: nil -*- vi:set ts=8 sts=4 sw=4: */
5 An audio time-stretching and pitch-shifting library.
6 Copyright 2007-2008 Chris Cannam.
8 This program is free software; you can redistribute it and/or
9 modify it under the terms of the GNU General Public License as
10 published by the Free Software Foundation; either version 2 of the
11 License, or (at your option) any later version. See the file
12 COPYING included with this distribution for more information.
15 #ifndef _RUBBERBAND_RINGBUFFER_H_
16 #define _RUBBERBAND_RINGBUFFER_H_
19 #include <sys/types.h>
23 #ifndef PLATFORM_WINDOWS
27 #include "Scavenger.h"
31 //#define DEBUG_RINGBUFFER 1
33 #ifdef PLATFORM_WINDOWS
35 #define MUNLOCK(a,b) 1
37 #define MLOCK(a,b) ::mlock(a,b)
38 #define MUNLOCK(a,b) ::munlock(a,b)
41 #ifdef DEBUG_RINGBUFFER
45 namespace RubberBand {
48 * RingBuffer implements a lock-free ring buffer for one writer and N
49 * readers, that is to be used to store a sample type T.
52 template <typename T, int N = 1>
57 * Create a ring buffer with room to write n samples.
59 * Note that the internal storage size will actually be n+1
60 * samples, as one element is unavailable for administrative
61 * reasons. Since the ring buffer performs best if its size is a
62 * power of two, this means n should ideally be some power of two
67 virtual ~RingBuffer();
70 * Return the total capacity of the ring buffer in samples.
71 * (This is the argument n passed to the constructor.)
76 * Resize the ring buffer. This also empties it; use resized()
77 * below if you do not want this to happen. Actually swaps in a
78 * new, larger buffer; the old buffer is scavenged after a seemly
79 * delay. Should be called from the write thread.
81 void resize(int newSize);
84 * Return a new ring buffer (allocated with "new" -- called must
85 * delete when no longer needed) of the given size, containing the
86 * same data as this one. If another thread reads from or writes
87 * to this buffer during the call, the results may be incomplete
88 * or inconsistent. If this buffer's data will not fit in the new
89 * size, the contents are undefined.
91 RingBuffer<T, N> *resized(int newSize, int R = 0) const;
94 * Lock the ring buffer into physical memory. Returns true
100 * Reset read and write pointers, thus emptying the buffer.
101 * Should be called from the write thread.
106 * Return the amount of data available for reading by reader R, in
109 int getReadSpace(int R = 0) const;
112 * Return the amount of space available for writing, in samples.
114 int getWriteSpace() const;
117 * Read n samples from the buffer, for reader R. If fewer than n
118 * are available, the remainder will be zeroed out. Returns the
119 * number of samples actually read.
121 int read(T *R__ destination, int n, int R = 0);
124 * Read n samples from the buffer, for reader R, adding them to
125 * the destination. If fewer than n are available, the remainder
126 * will be left alone. Returns the number of samples actually
129 int readAdding(T *R__ destination, int n, int R = 0);
132 * Read one sample from the buffer, for reader R. If no sample is
133 * available, this will silently return zero. Calling this
134 * repeatedly is obviously slower than calling read once, but it
135 * may be good enough if you don't want to allocate a buffer to
138 T readOne(int R = 0);
141 * Read n samples from the buffer, if available, for reader R,
142 * without advancing the read pointer -- i.e. a subsequent read()
143 * or skip() will be necessary to empty the buffer. If fewer than
144 * n are available, the remainder will be zeroed out. Returns the
145 * number of samples actually read.
147 int peek(T *R__ destination, int n, int R = 0) const;
150 * Read one sample from the buffer, if available, without
151 * advancing the read pointer -- i.e. a subsequent read() or
152 * skip() will be necessary to empty the buffer. Returns zero if
153 * no sample was available.
155 T peekOne(int R = 0) const;
158 * Pretend to read n samples from the buffer, for reader R,
159 * without actually returning them (i.e. discard the next n
160 * samples). Returns the number of samples actually available for
163 int skip(int n, int R = 0);
166 * Write n samples to the buffer. If insufficient space is
167 * available, not all samples may actually be written. Returns
168 * the number of samples actually written.
170 int write(const T *source, int n);
173 * Write n zero-value samples to the buffer. If insufficient
174 * space is available, not all zeros may actually be written.
175 * Returns the number of zeroes actually written.
181 volatile int m_writer;
182 volatile int m_readers[N];
186 static Scavenger<ScavengerArrayWrapper<T> > m_scavenger;
189 RingBuffer(const RingBuffer &); // not provided
190 RingBuffer &operator=(const RingBuffer &); // not provided
193 template <typename T, int N>
194 Scavenger<ScavengerArrayWrapper<T> > RingBuffer<T, N>::m_scavenger;
196 template <typename T, int N>
197 RingBuffer<T, N>::RingBuffer(int n) :
198 m_buffer(new T[n + 1]),
203 #ifdef DEBUG_RINGBUFFER
204 std::cerr << "RingBuffer<T," << N << ">[" << this << "]::RingBuffer(" << n << ")" << std::endl;
207 for (int i = 0; i < N; ++i) m_readers[i] = 0;
209 m_scavenger.scavenge();
212 template <typename T, int N>
213 RingBuffer<T, N>::~RingBuffer()
215 #ifdef DEBUG_RINGBUFFER
216 std::cerr << "RingBuffer<T," << N << ">[" << this << "]::~RingBuffer" << std::endl;
220 MUNLOCK((void *)m_buffer, m_size * sizeof(T));
224 m_scavenger.scavenge();
227 template <typename T, int N>
229 RingBuffer<T, N>::getSize() const
231 #ifdef DEBUG_RINGBUFFER
232 std::cerr << "RingBuffer<T," << N << ">[" << this << "]::getSize(): " << m_size-1 << std::endl;
238 template <typename T, int N>
240 RingBuffer<T, N>::resize(int newSize)
242 #ifdef DEBUG_RINGBUFFER
243 std::cerr << "RingBuffer<T," << N << ">[" << this << "]::resize(" << newSize << ")" << std::endl;
246 m_scavenger.scavenge();
249 MUNLOCK((void *)m_buffer, m_size * sizeof(T));
252 m_scavenger.claim(new ScavengerArrayWrapper<T>(m_buffer));
255 m_buffer = new T[newSize + 1];
256 m_size = newSize + 1;
259 if (MLOCK((void *)m_buffer, m_size * sizeof(T))) {
265 template <typename T, int N>
267 RingBuffer<T, N>::resized(int newSize, int R) const
269 RingBuffer<T, N> *newBuffer = new RingBuffer<T, N>(newSize);
272 int r = m_readers[R];
275 T value = m_buffer[r];
276 newBuffer->write(&value, 1);
277 if (++r == m_size) r = 0;
283 template <typename T, int N>
285 RingBuffer<T, N>::mlock()
287 if (MLOCK((void *)m_buffer, m_size * sizeof(T))) return false;
292 template <typename T, int N>
294 RingBuffer<T, N>::reset()
296 #ifdef DEBUG_RINGBUFFER
297 std::cerr << "RingBuffer<T," << N << ">[" << this << "]::reset" << std::endl;
301 for (int i = 0; i < N; ++i) m_readers[i] = 0;
304 template <typename T, int N>
306 RingBuffer<T, N>::getReadSpace(int R) const
308 int writer = m_writer;
309 int reader = m_readers[R];
312 #ifdef DEBUG_RINGBUFFER
313 std::cerr << "RingBuffer<T," << N << ">[" << this << "]::getReadSpace(" << R << "): reader " << reader << ", writer " << writer << std::endl;
316 if (writer > reader) space = writer - reader;
317 else if (writer < reader) space = (writer + m_size) - reader;
320 #ifdef DEBUG_RINGBUFFER
321 std::cerr << "RingBuffer<T," << N << ">[" << this << "]::getReadSpace(" << R << "): " << space << std::endl;
327 template <typename T, int N>
329 RingBuffer<T, N>::getWriteSpace() const
332 for (int i = 0; i < N; ++i) {
333 int writer = m_writer;
334 int reader = m_readers[i];
335 int here = (reader + m_size - writer - 1);
336 if (here >= m_size) here -= m_size;
337 if (i == 0 || here < space) space = here;
340 #ifdef DEBUG_RINGBUFFER
341 int rs(getReadSpace()), rp(m_readers[0]);
343 std::cerr << "RingBuffer: write space " << space << ", read space "
344 << rs << ", total " << (space + rs) << ", m_size " << m_size << std::endl;
345 std::cerr << "RingBuffer: reader " << rp << ", writer " << m_writer << std::endl;
348 #ifdef DEBUG_RINGBUFFER
349 std::cerr << "RingBuffer<T," << N << ">[" << this << "]::getWriteSpace(): " << space << std::endl;
355 template <typename T, int N>
357 RingBuffer<T, N>::read(T *R__ destination, int n, int R)
359 Profiler profiler("RingBuffer::read");
361 #ifdef DEBUG_RINGBUFFER
362 std::cerr << "RingBuffer<T," << N << ">[" << this << "]::read(dest, " << n << ", " << R << ")" << std::endl;
365 int available = getReadSpace(R);
367 #ifdef DEBUG_RINGBUFFER
368 std::cerr << "WARNING: Only " << available << " samples available"
371 for (int i = available; i < n; ++i) {
376 if (n == 0) return n;
378 int reader = m_readers[R];
379 int here = m_size - reader;
380 T *const R__ bufbase = m_buffer + reader;
383 for (int i = 0; i < n; ++i) {
384 destination[i] = bufbase[i];
387 for (int i = 0; i < here; ++i) {
388 destination[i] = bufbase[i];
390 T *const R__ destbase = destination + here;
391 const int nh = n - here;
392 for (int i = 0; i < nh; ++i) {
393 destbase[i] = m_buffer[i];
398 while (reader >= m_size) reader -= m_size;
399 m_readers[R] = reader;
401 #ifdef DEBUG_RINGBUFFER
402 std::cerr << "RingBuffer<T," << N << ">[" << this << "]::read: read " << n << ", reader now " << m_readers[R] << std::endl;
408 template <typename T, int N>
410 RingBuffer<T, N>::readAdding(T *R__ destination, int n, int R)
412 Profiler profiler("RingBuffer::readAdding");
414 #ifdef DEBUG_RINGBUFFER
415 std::cerr << "RingBuffer<T," << N << ">[" << this << "]::readAdding(dest, " << n << ", " << R << ")" << std::endl;
418 int available = getReadSpace(R);
420 #ifdef DEBUG_RINGBUFFER
421 std::cerr << "WARNING: Only " << available << " samples available"
426 if (n == 0) return n;
428 int reader = m_readers[R];
429 int here = m_size - reader;
430 const T *const R__ bufbase = m_buffer + reader;
433 for (int i = 0; i < n; ++i) {
434 destination[i] += bufbase[i];
437 for (int i = 0; i < here; ++i) {
438 destination[i] += bufbase[i];
440 T *const R__ destbase = destination + here;
441 const int nh = n - here;
442 for (int i = 0; i < nh; ++i) {
443 destbase[i] += m_buffer[i];
448 while (reader >= m_size) reader -= m_size;
449 m_readers[R] = reader;
453 template <typename T, int N>
455 RingBuffer<T, N>::readOne(int R)
457 #ifdef DEBUG_RINGBUFFER
458 std::cerr << "RingBuffer<T," << N << ">[" << this << "]::readOne(" << R << ")" << std::endl;
461 if (m_writer == m_readers[R]) {
462 #ifdef DEBUG_RINGBUFFER
463 std::cerr << "WARNING: No sample available"
468 int reader = m_readers[R];
469 T value = m_buffer[reader];
470 if (++reader == m_size) reader = 0;
471 m_readers[R] = reader;
475 template <typename T, int N>
477 RingBuffer<T, N>::peek(T *R__ destination, int n, int R) const
479 Profiler profiler("RingBuffer::peek");
481 #ifdef DEBUG_RINGBUFFER
482 std::cerr << "RingBuffer<T," << N << ">[" << this << "]::peek(dest, " << n << ", " << R << ")" << std::endl;
485 int available = getReadSpace(R);
487 #ifdef DEBUG_RINGBUFFER
488 std::cerr << "WARNING: Only " << available << " samples available"
491 memset(destination + available, 0, (n - available) * sizeof(T));
494 if (n == 0) return n;
496 int reader = m_readers[R];
497 int here = m_size - reader;
498 const T *const R__ bufbase = m_buffer + reader;
501 for (int i = 0; i < n; ++i) {
502 destination[i] = bufbase[i];
505 for (int i = 0; i < here; ++i) {
506 destination[i] = bufbase[i];
508 T *const R__ destbase = destination + here;
509 const int nh = n - here;
510 for (int i = 0; i < nh; ++i) {
511 destbase[i] = m_buffer[i];
515 #ifdef DEBUG_RINGBUFFER
516 std::cerr << "RingBuffer<T," << N << ">[" << this << "]::peek: read " << n << std::endl;
522 template <typename T, int N>
524 RingBuffer<T, N>::peekOne(int R) const
526 #ifdef DEBUG_RINGBUFFER
527 std::cerr << "RingBuffer<T," << N << ">[" << this << "]::peek(" << R << ")" << std::endl;
530 if (m_writer == m_readers[R]) {
531 #ifdef DEBUG_RINGBUFFER
532 std::cerr << "WARNING: No sample available"
537 T value = m_buffer[m_readers[R]];
541 template <typename T, int N>
543 RingBuffer<T, N>::skip(int n, int R)
545 #ifdef DEBUG_RINGBUFFER
546 std::cerr << "RingBuffer<T," << N << ">[" << this << "]::skip(" << n << ", " << R << ")" << std::endl;
549 int available = getReadSpace(R);
551 #ifdef DEBUG_RINGBUFFER
552 std::cerr << "WARNING: Only " << available << " samples available"
557 if (n == 0) return n;
559 int reader = m_readers[R];
561 while (reader >= m_size) reader -= m_size;
562 m_readers[R] = reader;
566 template <typename T, int N>
568 RingBuffer<T, N>::write(const T *source, int n)
570 Profiler profiler("RingBuffer::write");
572 #ifdef DEBUG_RINGBUFFER
573 std::cerr << "RingBuffer<T," << N << ">[" << this << "]::write(" << n << ")" << std::endl;
576 int available = getWriteSpace();
578 #ifdef DEBUG_RINGBUFFER
579 std::cerr << "WARNING: Only room for " << available << " samples"
584 if (n == 0) return n;
586 int writer = m_writer;
587 int here = m_size - writer;
588 T *const R__ bufbase = m_buffer + writer;
591 for (int i = 0; i < n; ++i) {
592 bufbase[i] = source[i];
595 for (int i = 0; i < here; ++i) {
596 bufbase[i] = source[i];
598 const int nh = n - here;
599 const T *const R__ srcbase = source + here;
600 T *const R__ buf = m_buffer;
601 for (int i = 0; i < nh; ++i) {
607 while (writer >= m_size) writer -= m_size;
610 #ifdef DEBUG_RINGBUFFER
611 std::cerr << "RingBuffer<T," << N << ">[" << this << "]::write: wrote " << n << ", writer now " << m_writer << std::endl;
617 template <typename T, int N>
619 RingBuffer<T, N>::zero(int n)
621 Profiler profiler("RingBuffer::zero");
623 #ifdef DEBUG_RINGBUFFER
624 std::cerr << "RingBuffer<T," << N << ">[" << this << "]::zero(" << n << ")" << std::endl;
627 int available = getWriteSpace();
629 #ifdef DEBUG_RINGBUFFER
630 std::cerr << "WARNING: Only room for " << available << " samples"
635 if (n == 0) return n;
637 int writer = m_writer;
638 int here = m_size - writer;
639 T *const R__ bufbase = m_buffer + writer;
642 for (int i = 0; i < n; ++i) {
646 for (int i = 0; i < here; ++i) {
649 const int nh = n - here;
650 for (int i = 0; i < nh; ++i) {
656 while (writer >= m_size) writer -= m_size;
659 #ifdef DEBUG_RINGBUFFER
660 std::cerr << "writer -> " << m_writer << std::endl;
668 //#include "RingBuffer.cpp"
670 #endif // _RINGBUFFER_H_