libs/rubberband/src/RingBuffer.h

   1 /* -*- c-basic-offset: 4 indent-tabs-mode: nil -*-  vi:set ts=8 sts=4 sw=4: */
   2
   3 /*
   4     Rubber Band
   5     An audio time-stretching and pitch-shifting library.
   6     Copyright 2007-2008 Chris Cannam.
   7
   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.
  13 */
  14
  15 #ifndef _RUBBERBAND_RINGBUFFER_H_
  16 #define _RUBBERBAND_RINGBUFFER_H_
  17
  18 #include <cstring>
  19 #include <sys/types.h>
  20
  21 #include <cstring>
  22
  23 #ifndef _WIN32
  24 #include <sys/mman.h>
  25 #endif
  26
  27 #include "Scavenger.h"
  28 #include "Profiler.h"
  29
  30
  31 //#define DEBUG_RINGBUFFER 1
  32
  33 #ifdef _WIN32
  34 #define MLOCK(a,b) 1
  35 #define MUNLOCK(a,b) 1
  36 #else
  37 #define MLOCK(a,b) ::mlock(a,b)
  38 #define MUNLOCK(a,b) ::munlock(a,b)
  39 #endif
  40
  41 #ifdef DEBUG_RINGBUFFER
  42 #include <iostream>
  43 #endif
  44
  45 namespace RubberBand {
  46
  47 /**
  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.
  50  */
  51
  52 template <typename T, int N = 1>
  53 class RingBuffer
  54 {
  55 public:
  56     /**
  57      * Create a ring buffer with room to write n samples.
  58      *
  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
  63      * minus one.
  64      */
  65     RingBuffer(int n);
  66
  67     virtual ~RingBuffer();
  68
  69     /**
  70      * Return the total capacity of the ring buffer in samples.
  71      * (This is the argument n passed to the constructor.)
  72      */
  73     int getSize() const;
  74
  75     /**
  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.
  80      */
  81     void resize(int newSize);
  82
  83     /**
  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.
  90      */
  91     RingBuffer<T, N> *resized(int newSize, int R = 0) const;
  92
  93     /**
  94      * Lock the ring buffer into physical memory.  Returns true
  95      * for success.
  96      */
  97     bool mlock();
  98
  99     /**
 100      * Reset read and write pointers, thus emptying the buffer.
 101      * Should be called from the write thread.
 102      */
 103     void reset();
 104
 105     /**
 106      * Return the amount of data available for reading by reader R, in
 107      * samples.
 108      */
 109     int getReadSpace(int R = 0) const;
 110
 111     /**
 112      * Return the amount of space available for writing, in samples.
 113      */
 114     int getWriteSpace() const;
 115
 116     /**
 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.
 120      */
 121     int read(T *R__ destination, int n, int R = 0);
 122
 123     /**
 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
 127      * read.
 128      */
 129     int readAdding(T *R__ destination, int n, int R = 0);
 130
 131     /**
 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
 136      * read into.
 137      */
 138     T readOne(int R = 0);
 139
 140     /**
 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.
 146      */
 147     int peek(T *R__ destination, int n, int R = 0) const;
 148
 149     /**
 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.
 154      */
 155     T peekOne(int R = 0) const;
 156
 157     /**
 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
 161      * discarding.
 162      */
 163     int skip(int n, int R = 0);
 164
 165     /**
 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.
 169      */
 170     int write(const T *source, int n);
 171
 172     /**
 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.
 176      */
 177     int zero(int n);
 178
 179 protected:
 180     T *R__      m_buffer;
 181     volatile int     m_writer;
 182     volatile int     m_readers[N];
 183     int              m_size;
 184     bool             m_mlocked;
 185
 186     static Scavenger<ScavengerArrayWrapper<T> > m_scavenger;
 187
 188 private:
 189     RingBuffer(const RingBuffer &); // not provided
 190     RingBuffer &operator=(const RingBuffer &); // not provided
 191 };
 192
 193 template <typename T, int N>
 194 Scavenger<ScavengerArrayWrapper<T> > RingBuffer<T, N>::m_scavenger;
 195
 196 template <typename T, int N>
 197 RingBuffer<T, N>::RingBuffer(int n) :
 198     m_buffer(new T[n + 1]),
 199     m_writer(0),
 200     m_size(n + 1),
 201     m_mlocked(false)
 202 {
 203 #ifdef DEBUG_RINGBUFFER
 204     std::cerr << "RingBuffer<T," << N << ">[" << this << "]::RingBuffer(" << n << ")" << std::endl;
 205 #endif
 206
 207     for (int i = 0; i < N; ++i) m_readers[i] = 0;
 208
 209     m_scavenger.scavenge();
 210 }
 211
 212 template <typename T, int N>
 213 RingBuffer<T, N>::~RingBuffer()
 214 {
 215 #ifdef DEBUG_RINGBUFFER
 216     std::cerr << "RingBuffer<T," << N << ">[" << this << "]::~RingBuffer" << std::endl;
 217 #endif
 218
 219     if (m_mlocked) {
 220         MUNLOCK((void *)m_buffer, m_size * sizeof(T));
 221     }
 222     delete[] m_buffer;
 223
 224     m_scavenger.scavenge();
 225 }
 226
 227 template <typename T, int N>
 228 int
 229 RingBuffer<T, N>::getSize() const
 230 {
 231 #ifdef DEBUG_RINGBUFFER
 232     std::cerr << "RingBuffer<T," << N << ">[" << this << "]::getSize(): " << m_size-1 << std::endl;
 233 #endif
 234
 235     return m_size - 1;
 236 }
 237
 238 template <typename T, int N>
 239 void
 240 RingBuffer<T, N>::resize(int newSize)
 241 {
 242 #ifdef DEBUG_RINGBUFFER
 243     std::cerr << "RingBuffer<T," << N << ">[" << this << "]::resize(" << newSize << ")" << std::endl;
 244 #endif
 245
 246     m_scavenger.scavenge();
 247
 248     if (m_mlocked) {
 249         MUNLOCK((void *)m_buffer, m_size * sizeof(T));
 250     }
 251
 252     m_scavenger.claim(new ScavengerArrayWrapper<T>(m_buffer));
 253
 254     reset();
 255     m_buffer = new T[newSize + 1];
 256     m_size = newSize + 1;
 257
 258     if (m_mlocked) {
 259         if (MLOCK((void *)m_buffer, m_size * sizeof(T))) {
 260             m_mlocked = false;
 261         }
 262     }
 263 }
 264
 265 template <typename T, int N>
 266 RingBuffer<T, N> *
 267 RingBuffer<T, N>::resized(int newSize, int R) const
 268 {
 269     RingBuffer<T, N> *newBuffer = new RingBuffer<T, N>(newSize);
 270
 271     int w = m_writer;
 272     int r = m_readers[R];
 273
 274     while (r != w) {
 275         T value = m_buffer[r];
 276         newBuffer->write(&value, 1);
 277         if (++r == m_size) r = 0;
 278     }
 279
 280     return newBuffer;
 281 }
 282
 283 template <typename T, int N>
 284 bool
 285 RingBuffer<T, N>::mlock()
 286 {
 287     if (MLOCK((void *)m_buffer, m_size * sizeof(T))) return false;
 288     m_mlocked = true;
 289     return true;
 290 }
 291
 292 template <typename T, int N>
 293 void
 294 RingBuffer<T, N>::reset()
 295 {
 296 #ifdef DEBUG_RINGBUFFER
 297     std::cerr << "RingBuffer<T," << N << ">[" << this << "]::reset" << std::endl;
 298 #endif
 299
 300     m_writer = 0;
 301     for (int i = 0; i < N; ++i) m_readers[i] = 0;
 302 }
 303
 304 template <typename T, int N>
 305 int
 306 RingBuffer<T, N>::getReadSpace(int R) const
 307 {
 308     int writer = m_writer;
 309     int reader = m_readers[R];
 310     int space;
 311
 312 #ifdef DEBUG_RINGBUFFER
 313     std::cerr << "RingBuffer<T," << N << ">[" << this << "]::getReadSpace(" << R << "): reader " << reader << ", writer " << writer << std::endl;
 314 #endif
 315
 316     if (writer > reader) space = writer - reader;
 317     else if (writer < reader) space = (writer + m_size) - reader;
 318     else space = 0;
 319
 320 #ifdef DEBUG_RINGBUFFER
 321     std::cerr << "RingBuffer<T," << N << ">[" << this << "]::getReadSpace(" << R << "): " << space << std::endl;
 322 #endif
 323
 324     return space;
 325 }
 326
 327 template <typename T, int N>
 328 int
 329 RingBuffer<T, N>::getWriteSpace() const
 330 {
 331     int space = 0;
 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;
 338     }
 339
 340 #ifdef DEBUG_RINGBUFFER
 341     int rs(getReadSpace()), rp(m_readers[0]);
 342
 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;
 346 #endif
 347
 348 #ifdef DEBUG_RINGBUFFER
 349     std::cerr << "RingBuffer<T," << N << ">[" << this << "]::getWriteSpace(): " << space << std::endl;
 350 #endif
 351
 352     return space;
 353 }
 354
 355 template <typename T, int N>
 356 int
 357 RingBuffer<T, N>::read(T *R__ destination, int n, int R)
 358 {
 359     Profiler profiler("RingBuffer::read");
 360
 361 #ifdef DEBUG_RINGBUFFER
 362     std::cerr << "RingBuffer<T," << N << ">[" << this << "]::read(dest, " << n << ", " << R << ")" << std::endl;
 363 #endif
 364
 365     int available = getReadSpace(R);
 366     if (n > available) {
 367 #ifdef DEBUG_RINGBUFFER
 368         std::cerr << "WARNING: Only " << available << " samples available"
 369                   << std::endl;
 370 #endif
 371         for (int i = available; i < n; ++i) {
 372             destination[i] = 0;
 373         }
 374         n = available;
 375     }
 376     if (n == 0) return n;
 377
 378     int reader = m_readers[R];
 379     int here = m_size - reader;
 380     T *const R__ bufbase = m_buffer + reader;
 381
 382     if (here >= n) {
 383         for (int i = 0; i < n; ++i) {
 384             destination[i] = bufbase[i];
 385         }
 386     } else {
 387         for (int i = 0; i < here; ++i) {
 388             destination[i] = bufbase[i];
 389         }
 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];
 394         }
 395     }
 396
 397     reader += n;
 398     while (reader >= m_size) reader -= m_size;
 399     m_readers[R] = reader;
 400
 401 #ifdef DEBUG_RINGBUFFER
 402     std::cerr << "RingBuffer<T," << N << ">[" << this << "]::read: read " << n << ", reader now " << m_readers[R] << std::endl;
 403 #endif
 404
 405     return n;
 406 }
 407
 408 template <typename T, int N>
 409 int
 410 RingBuffer<T, N>::readAdding(T *R__ destination, int n, int R)
 411 {
 412     Profiler profiler("RingBuffer::readAdding");
 413
 414 #ifdef DEBUG_RINGBUFFER
 415     std::cerr << "RingBuffer<T," << N << ">[" << this << "]::readAdding(dest, " << n << ", " << R << ")" << std::endl;
 416 #endif
 417
 418     int available = getReadSpace(R);
 419     if (n > available) {
 420 #ifdef DEBUG_RINGBUFFER
 421         std::cerr << "WARNING: Only " << available << " samples available"
 422                   << std::endl;
 423 #endif
 424         n = available;
 425     }
 426     if (n == 0) return n;
 427
 428     int reader = m_readers[R];
 429     int here = m_size - reader;
 430     const T *const R__ bufbase = m_buffer + reader;
 431
 432     if (here >= n) {
 433         for (int i = 0; i < n; ++i) {
 434             destination[i] += bufbase[i];
 435         }
 436     } else {
 437         for (int i = 0; i < here; ++i) {
 438             destination[i] += bufbase[i];
 439         }
 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];
 444         }
 445     }
 446
 447     reader += n;
 448     while (reader >= m_size) reader -= m_size;
 449     m_readers[R] = reader;
 450     return n;
 451 }
 452
 453 template <typename T, int N>
 454 T
 455 RingBuffer<T, N>::readOne(int R)
 456 {
 457 #ifdef DEBUG_RINGBUFFER
 458     std::cerr << "RingBuffer<T," << N << ">[" << this << "]::readOne(" << R << ")" << std::endl;
 459 #endif
 460
 461     if (m_writer == m_readers[R]) {
 462 #ifdef DEBUG_RINGBUFFER
 463         std::cerr << "WARNING: No sample available"
 464                   << std::endl;
 465 #endif
 466         return 0;
 467     }
 468     int reader = m_readers[R];
 469     T value = m_buffer[reader];
 470     if (++reader == m_size) reader = 0;
 471     m_readers[R] = reader;
 472     return value;
 473 }
 474
 475 template <typename T, int N>
 476 int
 477 RingBuffer<T, N>::peek(T *R__ destination, int n, int R) const
 478 {
 479     Profiler profiler("RingBuffer::peek");
 480
 481 #ifdef DEBUG_RINGBUFFER
 482     std::cerr << "RingBuffer<T," << N << ">[" << this << "]::peek(dest, " << n << ", " << R << ")" << std::endl;
 483 #endif
 484
 485     int available = getReadSpace(R);
 486     if (n > available) {
 487 #ifdef DEBUG_RINGBUFFER
 488         std::cerr << "WARNING: Only " << available << " samples available"
 489                   << std::endl;
 490 #endif
 491         memset(destination + available, 0, (n - available) * sizeof(T));
 492         n = available;
 493     }
 494     if (n == 0) return n;
 495
 496     int reader = m_readers[R];
 497     int here = m_size - reader;
 498     const T *const R__ bufbase = m_buffer + reader;
 499
 500     if (here >= n) {
 501         for (int i = 0; i < n; ++i) {
 502             destination[i] = bufbase[i];
 503         }
 504     } else {
 505         for (int i = 0; i < here; ++i) {
 506             destination[i] = bufbase[i];
 507         }
 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];
 512         }
 513     }
 514
 515 #ifdef DEBUG_RINGBUFFER
 516     std::cerr << "RingBuffer<T," << N << ">[" << this << "]::peek: read " << n << std::endl;
 517 #endif
 518
 519     return n;
 520 }
 521
 522 template <typename T, int N>
 523 T
 524 RingBuffer<T, N>::peekOne(int R) const
 525 {
 526 #ifdef DEBUG_RINGBUFFER
 527     std::cerr << "RingBuffer<T," << N << ">[" << this << "]::peek(" << R << ")" << std::endl;
 528 #endif
 529
 530     if (m_writer == m_readers[R]) {
 531 #ifdef DEBUG_RINGBUFFER
 532         std::cerr << "WARNING: No sample available"
 533                   << std::endl;
 534 #endif
 535         return 0;
 536     }
 537     T value = m_buffer[m_readers[R]];
 538     return value;
 539 }
 540
 541 template <typename T, int N>
 542 int
 543 RingBuffer<T, N>::skip(int n, int R)
 544 {
 545 #ifdef DEBUG_RINGBUFFER
 546     std::cerr << "RingBuffer<T," << N << ">[" << this << "]::skip(" << n << ", " << R << ")" << std::endl;
 547 #endif
 548
 549     int available = getReadSpace(R);
 550     if (n > available) {
 551 #ifdef DEBUG_RINGBUFFER
 552         std::cerr << "WARNING: Only " << available << " samples available"
 553                   << std::endl;
 554 #endif
 555         n = available;
 556     }
 557     if (n == 0) return n;
 558
 559     int reader = m_readers[R];
 560     reader += n;
 561     while (reader >= m_size) reader -= m_size;
 562     m_readers[R] = reader;
 563     return n;
 564 }
 565
 566 template <typename T, int N>
 567 int
 568 RingBuffer<T, N>::write(const T *source, int n)
 569 {
 570     Profiler profiler("RingBuffer::write");
 571
 572 #ifdef DEBUG_RINGBUFFER
 573     std::cerr << "RingBuffer<T," << N << ">[" << this << "]::write(" << n << ")" << std::endl;
 574 #endif
 575
 576     int available = getWriteSpace();
 577     if (n > available) {
 578 #ifdef DEBUG_RINGBUFFER
 579         std::cerr << "WARNING: Only room for " << available << " samples"
 580                   << std::endl;
 581 #endif
 582         n = available;
 583     }
 584     if (n == 0) return n;
 585
 586     int writer = m_writer;
 587     int here = m_size - writer;
 588     T *const R__ bufbase = m_buffer + writer;
 589
 590     if (here >= n) {
 591         for (int i = 0; i < n; ++i) {
 592             bufbase[i] = source[i];
 593         }
 594     } else {
 595         for (int i = 0; i < here; ++i) {
 596             bufbase[i] = source[i];
 597         }
 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) {
 602             buf[i] = srcbase[i];
 603         }
 604     }
 605
 606     writer += n;
 607     while (writer >= m_size) writer -= m_size;
 608     m_writer = writer;
 609
 610 #ifdef DEBUG_RINGBUFFER
 611     std::cerr << "RingBuffer<T," << N << ">[" << this << "]::write: wrote " << n << ", writer now " << m_writer << std::endl;
 612 #endif
 613
 614     return n;
 615 }
 616
 617 template <typename T, int N>
 618 int
 619 RingBuffer<T, N>::zero(int n)
 620 {
 621     Profiler profiler("RingBuffer::zero");
 622
 623 #ifdef DEBUG_RINGBUFFER
 624     std::cerr << "RingBuffer<T," << N << ">[" << this << "]::zero(" << n << ")" << std::endl;
 625 #endif
 626
 627     int available = getWriteSpace();
 628     if (n > available) {
 629 #ifdef DEBUG_RINGBUFFER
 630         std::cerr << "WARNING: Only room for " << available << " samples"
 631                   << std::endl;
 632 #endif
 633         n = available;
 634     }
 635     if (n == 0) return n;
 636
 637     int writer = m_writer;
 638     int here = m_size - writer;
 639     T *const R__ bufbase = m_buffer + writer;
 640
 641     if (here >= n) {
 642         for (int i = 0; i < n; ++i) {
 643             bufbase[i] = 0;
 644         }
 645     } else {
 646         for (int i = 0; i < here; ++i) {
 647             bufbase[i] = 0;
 648         }
 649         const int nh = n - here;
 650         for (int i = 0; i < nh; ++i) {
 651             m_buffer[i] = 0;
 652         }
 653     }
 654
 655     writer += n;
 656     while (writer >= m_size) writer -= m_size;
 657     m_writer = writer;
 658
 659 #ifdef DEBUG_RINGBUFFER
 660     std::cerr << "writer -> " << m_writer << std::endl;
 661 #endif
 662
 663     return n;
 664 }
 665
 666 }
 667
 668 //#include "RingBuffer.cpp"
 669
 670 #endif // _RINGBUFFER_H_