src/common/RingBuffer.h

/***************************************************************************
 *                                                                         *
 *   LinuxSampler - modular, streaming capable sampler                     *
 *                                                                         *
 *   Copyright (C) 2003, 2004 by Benno Senoner and Christian Schoenebeck   *
 *   Copyright (C) 2005 - 2012 Christian Schoenebeck                       *
 *                                                                         *
 *   This program 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.                                   *
 *                                                                         *
 *   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 General Public License for more 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., 59 Temple Place, Suite 330, Boston,                 *
 *   MA  02111-1307  USA                                                   *
 ***************************************************************************/

#ifndef RINGBUFFER_H
#define RINGBUFFER_H

#define DEFAULT_WRAP_ELEMENTS 0

#include <string.h>

#include "lsatomic.h"

using LinuxSampler::atomic;
using LinuxSampler::memory_order_relaxed;
using LinuxSampler::memory_order_acquire;
using LinuxSampler::memory_order_release;


/** @brief Real-time safe and type safe RingBuffer implementation.
 *
 * This constant size buffer can be used to send data from exactly one
 * sender / writing thread to exactly one receiver / reading thread. It is
 * real-time safe due to the fact that data is only allocated when this
 * RingBuffer is created and no system level mechanisms are used for
 * ensuring thread safety of this class.
 *
 * <b>Important:</b> There are two distinct behaviors of this RingBuffer
 * which has to be given as template argument @c T_DEEP_COPY, which is a
 * boolean flag:
 *
 * - @c true: The RingBuffer will copy elements of type @c T by using type
 *   @c T's assignment operator. This behavior is mandatory for all data
 *   structures (classes) which additionally allocate memory on the heap.
 *   Type @c T's needs to have an assignment operator implementation though,
 *   otherwise this will cause a compilation error. This behavior is more
 *   safe, but usually slower (except for very small buffer sizes, where it
 *   might be even faster).
 * - @c false: The RingBuffer will copy elements of type @c T by flatly
 *   copying their structural data ( i.e. with @c memcpy() ) in one piece.
 *   This will only work if class @c T (and all of its subelements) does not
 *   allocate any additional data on the heap by itself. So use this option
 *   with great care, because otherwise it will result in very ugly behavior
 *   and crashes! For larger buffer sizes, this behavior will most probably
 *   be faster.
 */
template<class T, bool T_DEEP_COPY>
class RingBuffer
{
public:
    RingBuffer (int sz, int wrap_elements = DEFAULT_WRAP_ELEMENTS) :
        write_ptr(0), read_ptr(0)
    {
        _allocBuffer(sz, wrap_elements);
    }
    
    /**
     * Resize this ring buffer to the given size. This operation
     * is not thread safe! Any operations using this RingBuffer
     * have to be stopped before calling this method.
     *
     * @param sz - new size (amount of elements)
     * @param wrap_elements - (optional) if supplied, the new amount
     *                        of wrap elements to be used beyond
     *                        official buffer end, if not provided
     *                        the amount wrap_elements remains as it was
     *                        before
     */
    void resize(int sz, int wrap_elements = -1) {
        if (wrap_elements == -1)
            wrap_elements = this->wrap_elements;
        
        delete [] buf;
        
        _allocBuffer(sz, wrap_elements);
    }

    virtual ~RingBuffer() {
            delete [] buf;
    }

    /**
     * Sets all remaining write space elements to zero. The write pointer
     * will currently not be incremented after, but that might change in
     * future.
     *
     * @e Caution: for @c T_DEEP_COPY=true you might probably @e NOT want
     * to call this method at all, at least not in case type @c T allocates
     * any additional data on the heap by itself.
     */
    inline void fill_write_space_with_null() {
             int w = write_ptr.load(memory_order_relaxed),
                 r = read_ptr.load(memory_order_acquire);
             memset(get_write_ptr(), 0, sizeof(T)*write_space_to_end());
             if (r && w >= r) {
               memset(get_buffer_begin(), 0, sizeof(T)*(r - 1));
             }

             // set the wrap space elements to null
             if (wrap_elements) memset(&buf[size], 0, sizeof(T)*wrap_elements);
           }

    __inline int  read (T *dest, int cnt);
    __inline int  write (T *src, int cnt);

    inline int push(T* src) { return write(src,1); }
    inline int pop(T* dst)  { return read(dst,1);  }

    __inline T *get_buffer_begin();

    __inline T *get_read_ptr(void) {
      return(&buf[read_ptr.load(memory_order_relaxed)]);
    }

    /**
     * Returns a pointer to the element from the current read position,
     * advanced by \a offset elements.
     */
    /*inline T* get_read_ptr(int offset) {
        int r = read_ptr.load(memory_order_relaxed);
        r += offset;
        r &= size_mask;
        return &buf[r];
    }*/

    __inline T *get_write_ptr();
    __inline void increment_read_ptr(int cnt) {
               read_ptr.store((read_ptr.load(memory_order_relaxed) + cnt) & size_mask, memory_order_release);
             }
    __inline void set_read_ptr(int val) {
               read_ptr.store(val, memory_order_release);
             }

    __inline void increment_write_ptr(int cnt) {
               write_ptr.store((write_ptr.load(memory_order_relaxed) + cnt) & size_mask, memory_order_release);
             }

    /* this function increments the write_ptr by cnt, if the buffer wraps then
       subtract size from the write_ptr value so that it stays within 0<write_ptr<size
       use this function to increment the write ptr after you filled the buffer
       with a number of elements given by write_space_to_end_with_wrap().
       This ensures that the data that is written to the buffer fills up all
       the wrap space that resides past the regular buffer. The wrap_space is needed for
       interpolation. So that the audio thread sees the ringbuffer like a linear space
       which allows us to use faster routines.
       When the buffer wraps the wrap part is memcpy()ied to the beginning of the buffer
       and the write ptr incremented accordingly.
    */
    __inline void increment_write_ptr_with_wrap(int cnt) {
               int w = write_ptr.load(memory_order_relaxed);
               w += cnt;
               if(w >= size) {
                 w -= size;
                 copy(&buf[0], &buf[size], w);
//printf("DEBUG !!!! increment_write_ptr_with_wrap: buffer wrapped, elements wrapped = %d (wrap_elements %d)\n",w,wrap_elements);
               }
               write_ptr.store(w, memory_order_release);
             }

    /* this function returns the available write space in the buffer
       when the read_ptr > write_ptr it returns the space inbetween, otherwise
       when the read_ptr < write_ptr it returns the space between write_ptr and
       the buffer end, including the wrap_space.
       There is an exception to it. When read_ptr <= wrap_elements. In that
       case we return the write space to buffer end (-1) without the wrap_elements,
       this is needed because a subsequent increment_write_ptr which copies the
       data that resides into the wrap space to the beginning of the buffer and increments
       the write_ptr would cause the write_ptr overstepping the read_ptr which would be an error.
       So basically the if(r<=wrap_elements) we return the buffer space to end - 1 which
       ensures that at the next call there will be one element free to write before the buffer wraps
       and usually (except in EOF situations) the next write_space_to_end_with_wrap() will return
       1 + wrap_elements which ensures that the wrap part gets fully filled with data
    */
    __inline int write_space_to_end_with_wrap() {
              int w, r;

              w = write_ptr.load(memory_order_relaxed);
              r = read_ptr.load(memory_order_acquire);
//printf("write_space_to_end: w=%d r=%d\n",w,r);
              if(r > w) {
                //printf("DEBUG: write_space_to_end_with_wrap: r>w r=%d w=%d val=%d\n",r,w,r - w - 1);
                return(r - w - 1);
              }
              if(r <= wrap_elements) {
                //printf("DEBUG: write_space_to_end_with_wrap: ATTENTION r <= wrap_elements: r=%d w=%d val=%d\n",r,w,size - w -1);
                return(size - w -1);
              }
              if(r) {
                //printf("DEBUG: write_space_to_end_with_wrap: r=%d w=%d val=%d\n",r,w,size - w + wrap_elements);
                return(size - w + wrap_elements);
              }
              //printf("DEBUG: write_space_to_end_with_wrap: r=0 w=%d val=%d\n",w,size - w - 1 + wrap_elements);
              return(size - w - 1 + wrap_elements);
            }

           /* this function adjusts the number of elements to write into the ringbuffer
              in a way that the size boundary is avoided and that the wrap space always gets
              entirely filled.
              cnt contains the write_space_to_end_with_wrap() amount while
              capped_cnt contains a capped amount of samples to read.
              normally capped_cnt == cnt but in some cases eg when the disk thread needs
              to refill tracks with smaller blocks because lots of streams require immediate
              refill because lots of notes were started simultaneously.
              In that case we set for example capped_cnt to a fixed amount (< cnt, eg 64k),
              which helps to reduce the buffer refill latencies that occur between streams.
              the first if() checks if the current write_ptr + capped_cnt resides within
              the wrap area but is < size+wrap_elements. in that case we cannot return
              capped_cnt because it would lead to a write_ptr wrapping and only a partial fill
              of wrap space which would lead to errors. So we simply return cnt which ensures
              that the the entire wrap space will get filled correctly.
              In all other cases (which are not problematic because no write_ptr wrapping
              occurs) we simply return capped_cnt.
           */
    __inline int adjust_write_space_to_avoid_boundary(int cnt, int capped_cnt) {
               int w;
               w = write_ptr.load(memory_order_relaxed);
               if((w+capped_cnt) >= size && (w+capped_cnt) < (size+wrap_elements)) {
//printf("adjust_write_space_to_avoid_boundary returning cnt = %d\n",cnt);
                 return(cnt);
               }
//printf("adjust_write_space_to_avoid_boundary returning capped_cnt = %d\n",capped_cnt);
               return(capped_cnt);
             }

    __inline int write_space_to_end() {
              int w, r;

              w = write_ptr.load(memory_order_relaxed);
              r = read_ptr.load(memory_order_acquire);
//printf("write_space_to_end: w=%d r=%d\n",w,r);
              if(r > w) return(r - w - 1);
              if(r) return(size - w);
              return(size - w - 1);
            }

    __inline int read_space_to_end() {
              int w, r;

              w = write_ptr.load(memory_order_acquire);
              r = read_ptr.load(memory_order_relaxed);
              if(w >= r) return(w - r);
              return(size - r);
            }
    __inline void init() {
                   write_ptr.store(0, memory_order_relaxed);
                   read_ptr.store(0, memory_order_relaxed);
                 //  wrap=0;
            }

    int write_space () {
            int w, r;

            w = write_ptr.load(memory_order_relaxed);
            r = read_ptr.load(memory_order_acquire);

            if (w > r) {
                    return ((r - w + size) & size_mask) - 1;
            } else if (w < r) {
                    return (r - w) - 1;
            } else {
                    return size - 1;
            }
    }

    int read_space () {
            int w, r;

            w = write_ptr.load(memory_order_acquire);
            r = read_ptr.load(memory_order_relaxed);

            if (w >= r) {
                    return w - r;
            } else {
                    return (w - r + size) & size_mask;
            }
    }

    int size;
    int wrap_elements;

    /**
     * Independent, random access reading from a RingBuffer. This class
     * allows to read from a RingBuffer without being forced to free read
     * data while reading / positioning.
     */
    template<class T1, bool T1_DEEP_COPY>
    class _NonVolatileReader {
        public:
            int read_space() {
                int r = read_ptr;
                int w = pBuf->write_ptr.load(memory_order_acquire);
                return (w >= r) ? w - r : (w - r + pBuf->size) & pBuf->size_mask;
            }

            /**
             * Prefix decrement operator, for reducing NonVolatileReader's
             * read position by one.
             */
            inline void operator--() {
                if (read_ptr == pBuf->read_ptr.load(memory_order_relaxed)) return; //TODO: or should we react oh this case (e.g. force segfault), as this is a very odd case?
                read_ptr = (read_ptr-1) & pBuf->size_mask;
            }

            /**
             * Postfix decrement operator, for reducing NonVolatileReader's
             * read position by one.
             */
            inline void operator--(int) {
                --*this;
            }
    
            /**
             * "Increment assign" operator, for advancing NonVolatileReader's
             * read position by @a n elements.
             *
             * @param n - amount of elements to advance read position
             */
            inline void operator+=(int n) {
                if (read_space() < n) return;
                read_ptr = (read_ptr+n) & pBuf->size_mask;
            }

            /**
             * Returns pointer to the RingBuffer data of current
             * NonVolatileReader's read position and increments
             * NonVolatileReader's read position by one.
             *
             * @returns pointer to element of current read position
             */
            T* pop() {
                if (!read_space()) return NULL;
                T* pData = &pBuf->buf[read_ptr];
                read_ptr++;
                read_ptr &= pBuf->size_mask;
                return pData;
            }

            /**
             * Reads one element from the NonVolatileReader's current read
             * position and copies it to the variable pointed by \a dst and
             * finally increments the NonVolatileReader's read position by
             * one.
             *
             * @param dst - where the element is copied to
             * @returns 1 on success, 0 otherwise
             */
            int pop(T* dst) { return read(dst,1); }

            /**
             * Reads \a cnt elements from the NonVolatileReader's current
             * read position and copies it to the buffer pointed by \a dest
             * and finally increments the NonVolatileReader's read position
             * by the number of read elements.
             *
             * @param dest - destination buffer
             * @param cnt  - number of elements to read
             * @returns number of read elements
             */
            int read(T* dest, int cnt) {
                int free_cnt;
                int cnt2;
                int to_read;
                int n1, n2;
                int priv_read_ptr;

                priv_read_ptr = read_ptr;

                if ((free_cnt = read_space()) == 0) return 0;

                to_read = cnt > free_cnt ? free_cnt : cnt;

                cnt2 = priv_read_ptr + to_read;

                if (cnt2 > pBuf->size) {
                    n1 = pBuf->size - priv_read_ptr;
                    n2 = cnt2 & pBuf->size_mask;
                } else {
                    n1 = to_read;
                    n2 = 0;
                }

                copy(dest, &pBuf->buf[priv_read_ptr], n1);
                priv_read_ptr = (priv_read_ptr + n1) & pBuf->size_mask;

                if (n2) {
                    copy(dest+n1, pBuf->buf, n2);
                    priv_read_ptr = n2;
                }

                this->read_ptr = priv_read_ptr;
                return to_read;
            }

            /**
             * Finally when the read data is not needed anymore, this method
             * should be called to free the data in the RingBuffer up to the
             * current read position of this NonVolatileReader.
             *
             * @see RingBuffer::increment_read_ptr()
             */
            void free() {
                pBuf->read_ptr.store(read_ptr, memory_order_release);
            }

        protected:
            _NonVolatileReader(RingBuffer<T1,T1_DEEP_COPY>* pBuf) {
                this->pBuf     = pBuf;
                this->read_ptr = pBuf->read_ptr.load(memory_order_relaxed);
            }

            RingBuffer<T1,T1_DEEP_COPY>* pBuf;
            int read_ptr;

            friend class RingBuffer<T1,T1_DEEP_COPY>;
    };

    typedef _NonVolatileReader<T,T_DEEP_COPY> NonVolatileReader;

    NonVolatileReader get_non_volatile_reader() { return NonVolatileReader(this); }

  protected:
    T *buf;
    atomic<int> write_ptr;
    atomic<int> read_ptr;
    int size_mask;

    /**
     * Copies \a n amount of elements from the buffer given by
     * \a pSrc to the buffer given by \a pDst.
     */
    inline static void copy(T* pDst, T* pSrc, int n);
    
    void _allocBuffer(int sz, int wrap_elements) {
        this->wrap_elements = wrap_elements;
            
        // the write-with-wrap functions need wrap_elements extra
        // space in the buffer to be able to copy the wrap space
        sz += wrap_elements;

        int power_of_two;
        for (power_of_two = 1;
             1<<power_of_two < sz;
             power_of_two++);

        size = 1<<power_of_two;
        size_mask = size;
        size_mask -= 1;
        buf = new T[size + wrap_elements];   
    }

    friend class _NonVolatileReader<T,T_DEEP_COPY>;
};

template<class T, bool T_DEEP_COPY>
T* RingBuffer<T,T_DEEP_COPY>::get_write_ptr (void) {
  return(&buf[write_ptr.load(memory_order_relaxed)]);
}

template<class T, bool T_DEEP_COPY>
T* RingBuffer<T,T_DEEP_COPY>::get_buffer_begin (void) {
  return(buf);
}


template<class T, bool T_DEEP_COPY>
int RingBuffer<T,T_DEEP_COPY>::read(T* dest, int cnt)
{
        int free_cnt;
        int cnt2;
        int to_read;
        int n1, n2;
        int priv_read_ptr;

        priv_read_ptr = read_ptr.load(memory_order_relaxed);

        if ((free_cnt = read_space ()) == 0) {
                return 0;
        }

        to_read = cnt > free_cnt ? free_cnt : cnt;

        cnt2 = priv_read_ptr + to_read;

        if (cnt2 > size) {
                n1 = size - priv_read_ptr;
                n2 = cnt2 & size_mask;
        } else {
                n1 = to_read;
                n2 = 0;
        }

        copy(dest, &buf[priv_read_ptr], n1);
        priv_read_ptr = (priv_read_ptr + n1) & size_mask;

        if (n2) {
                copy(dest+n1, buf, n2);
                priv_read_ptr = n2;
        }

        read_ptr.store(priv_read_ptr, memory_order_release);
        return to_read;
}

template<class T, bool T_DEEP_COPY>
int RingBuffer<T,T_DEEP_COPY>::write(T* src, int cnt)
{
        int free_cnt;
        int cnt2;
        int to_write;
        int n1, n2;
        int priv_write_ptr;

        priv_write_ptr = write_ptr.load(memory_order_relaxed);

        if ((free_cnt = write_space ()) == 0) {
                return 0;
        }

        to_write = cnt > free_cnt ? free_cnt : cnt;

        cnt2 = priv_write_ptr + to_write;

        if (cnt2 > size) {
                n1 = size - priv_write_ptr;
                n2 = cnt2 & size_mask;
        } else {
                n1 = to_write;
                n2 = 0;
        }

        copy(&buf[priv_write_ptr], src, n1);
        priv_write_ptr = (priv_write_ptr + n1) & size_mask;

        if (n2) {
                copy(buf, src+n1, n2);
                priv_write_ptr = n2;
        }
        write_ptr.store(priv_write_ptr, memory_order_release);
        return to_write;
}

template<class T, bool T_DEEP_COPY>
void RingBuffer<T,T_DEEP_COPY>::copy(T* pDst, T* pSrc, int n) {
    if (T_DEEP_COPY) { // deep copy - won't work for data structures without assignment operator implementation
        for (int i = 0; i < n; i++) pDst[i] = pSrc[i];
    } else { // flat copy - won't work for complex data structures !
        memcpy(pDst, pSrc, n * sizeof(T));
    }
}

#endif /* RINGBUFFER_H */
1	schoenebeck	53	/***************************************************************************
2			* *
3			* LinuxSampler - modular, streaming capable sampler *
4			* *
5	schoenebeck	56	* Copyright (C) 2003, 2004 by Benno Senoner and Christian Schoenebeck *
6	schoenebeck	2384	* Copyright (C) 2005 - 2012 Christian Schoenebeck *
7	schoenebeck	53	* *
8			* This program is free software; you can redistribute it and/or modify *
9			* it under the terms of the GNU General Public License as published by *
10			* the Free Software Foundation; either version 2 of the License, or *
11			* (at your option) any later version. *
12			* *
13			* This program is distributed in the hope that it will be useful, *
14			* but WITHOUT ANY WARRANTY; without even the implied warranty of *
15			* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
16			* GNU General Public License for more details. *
17			* *
18			* You should have received a copy of the GNU General Public License *
19			* along with this program; if not, write to the Free Software *
20			* Foundation, Inc., 59 Temple Place, Suite 330, Boston, *
21			* MA 02111-1307 USA *
22			***************************************************************************/
23
24			#ifndef RINGBUFFER_H
25			#define RINGBUFFER_H
26
27	senoner	1479	#define DEFAULT_WRAP_ELEMENTS 0
28	schoenebeck	53
29			#include <string.h>
30
31	persson	1790	#include "lsatomic.h"
32	schoenebeck	53
33	persson	1790	using LinuxSampler::atomic;
34			using LinuxSampler::memory_order_relaxed;
35			using LinuxSampler::memory_order_acquire;
36			using LinuxSampler::memory_order_release;
37
38
39	schoenebeck	970	/** @brief Real-time safe and type safe RingBuffer implementation.
40			*
41			* This constant size buffer can be used to send data from exactly one
42			* sender / writing thread to exactly one receiver / reading thread. It is
43			* real-time safe due to the fact that data is only allocated when this
44			* RingBuffer is created and no system level mechanisms are used for
45			* ensuring thread safety of this class.
46			*
47			* <b>Important:</b> There are two distinct behaviors of this RingBuffer
48			* which has to be given as template argument @c T_DEEP_COPY, which is a
49			* boolean flag:
50			*
51			* - @c true: The RingBuffer will copy elements of type @c T by using type
52			* @c T's assignment operator. This behavior is mandatory for all data
53			* structures (classes) which additionally allocate memory on the heap.
54			* Type @c T's needs to have an assignment operator implementation though,
55			* otherwise this will cause a compilation error. This behavior is more
56			* safe, but usually slower (except for very small buffer sizes, where it
57			* might be even faster).
58			* - @c false: The RingBuffer will copy elements of type @c T by flatly
59			* copying their structural data ( i.e. with @c memcpy() ) in one piece.
60			* This will only work if class @c T (and all of its subelements) does not
61			* allocate any additional data on the heap by itself. So use this option
62			* with great care, because otherwise it will result in very ugly behavior
63			* and crashes! For larger buffer sizes, this behavior will most probably
64			* be faster.
65			*/
66			template<class T, bool T_DEEP_COPY>
67	schoenebeck	53	class RingBuffer
68			{
69			public:
70	persson	1790	RingBuffer (int sz, int wrap_elements = DEFAULT_WRAP_ELEMENTS) :
71	schoenebeck	2384	write_ptr(0), read_ptr(0)
72			{
73			_allocBuffer(sz, wrap_elements);
74			}
75
76			/**
77			* Resize this ring buffer to the given size. This operation
78			* is not thread safe! Any operations using this RingBuffer
79			* have to be stopped before calling this method.
80			*
81			* @param sz - new size (amount of elements)
82			* @param wrap_elements - (optional) if supplied, the new amount
83			* of wrap elements to be used beyond
84			* official buffer end, if not provided
85			* the amount wrap_elements remains as it was
86			* before
87			*/
88			void resize(int sz, int wrap_elements = -1) {
89			if (wrap_elements == -1)
90			wrap_elements = this->wrap_elements;
91
92			delete [] buf;
93
94			_allocBuffer(sz, wrap_elements);
95			}
96	schoenebeck	53
97			virtual ~RingBuffer() {
98			delete [] buf;
99			}
100
101			/**
102			* Sets all remaining write space elements to zero. The write pointer
103			* will currently not be incremented after, but that might change in
104			* future.
105	schoenebeck	970	*
106			* @e Caution: for @c T_DEEP_COPY=true you might probably @e NOT want
107			* to call this method at all, at least not in case type @c T allocates
108			* any additional data on the heap by itself.
109	schoenebeck	53	*/
110			inline void fill_write_space_with_null() {
111	persson	1790	int w = write_ptr.load(memory_order_relaxed),
112			r = read_ptr.load(memory_order_acquire);
113	senoner	1479	memset(get_write_ptr(), 0, sizeof(T)*write_space_to_end());
114	schoenebeck	53	if (r && w >= r) {
115	senoner	1479	memset(get_buffer_begin(), 0, sizeof(T)*(r - 1));
116	schoenebeck	53	}
117
118			// set the wrap space elements to null
119	senoner	1479	if (wrap_elements) memset(&buf[size], 0, sizeof(T)*wrap_elements);
120	schoenebeck	53	}
121
122			__inline int read (T *dest, int cnt);
123			__inline int write (T *src, int cnt);
124
125			inline int push(T* src) { return write(src,1); }
126			inline int pop(T* dst) { return read(dst,1); }
127
128			__inline T *get_buffer_begin();
129
130			__inline T *get_read_ptr(void) {
131	persson	1790	return(&buf[read_ptr.load(memory_order_relaxed)]);
132	schoenebeck	53	}
133
134			/**
135			* Returns a pointer to the element from the current read position,
136			* advanced by \a offset elements.
137			*/
138			/inline T get_read_ptr(int offset) {
139	persson	1790	int r = read_ptr.load(memory_order_relaxed);
140	schoenebeck	53	r += offset;
141			r &= size_mask;
142			return &buf[r];
143			}*/
144
145			__inline T *get_write_ptr();
146			__inline void increment_read_ptr(int cnt) {
147	persson	1790	read_ptr.store((read_ptr.load(memory_order_relaxed) + cnt) & size_mask, memory_order_release);
148	schoenebeck	53	}
149			__inline void set_read_ptr(int val) {
150	persson	1790	read_ptr.store(val, memory_order_release);
151	schoenebeck	53	}
152
153			__inline void increment_write_ptr(int cnt) {
154	persson	1790	write_ptr.store((write_ptr.load(memory_order_relaxed) + cnt) & size_mask, memory_order_release);
155	schoenebeck	53	}
156
157			/* this function increments the write_ptr by cnt, if the buffer wraps then
158			subtract size from the write_ptr value so that it stays within 0<write_ptr<size
159			use this function to increment the write ptr after you filled the buffer
160			with a number of elements given by write_space_to_end_with_wrap().
161			This ensures that the data that is written to the buffer fills up all
162			the wrap space that resides past the regular buffer. The wrap_space is needed for
163			interpolation. So that the audio thread sees the ringbuffer like a linear space
164			which allows us to use faster routines.
165			When the buffer wraps the wrap part is memcpy()ied to the beginning of the buffer
166			and the write ptr incremented accordingly.
167			*/
168			__inline void increment_write_ptr_with_wrap(int cnt) {
169	persson	1790	int w = write_ptr.load(memory_order_relaxed);
170	schoenebeck	53	w += cnt;
171			if(w >= size) {
172			w -= size;
173	schoenebeck	970	copy(&buf[0], &buf[size], w);
174	schoenebeck	53	//printf("DEBUG !!!! increment_write_ptr_with_wrap: buffer wrapped, elements wrapped = %d (wrap_elements %d)\n",w,wrap_elements);
175			}
176	persson	1790	write_ptr.store(w, memory_order_release);
177	schoenebeck	53	}
178
179			/* this function returns the available write space in the buffer
180			when the read_ptr > write_ptr it returns the space inbetween, otherwise
181			when the read_ptr < write_ptr it returns the space between write_ptr and
182			the buffer end, including the wrap_space.
183			There is an exception to it. When read_ptr <= wrap_elements. In that
184			case we return the write space to buffer end (-1) without the wrap_elements,
185			this is needed because a subsequent increment_write_ptr which copies the
186			data that resides into the wrap space to the beginning of the buffer and increments
187			the write_ptr would cause the write_ptr overstepping the read_ptr which would be an error.
188			So basically the if(r<=wrap_elements) we return the buffer space to end - 1 which
189			ensures that at the next call there will be one element free to write before the buffer wraps
190			and usually (except in EOF situations) the next write_space_to_end_with_wrap() will return
191			1 + wrap_elements which ensures that the wrap part gets fully filled with data
192			*/
193			__inline int write_space_to_end_with_wrap() {
194			int w, r;
195
196	persson	1790	w = write_ptr.load(memory_order_relaxed);
197			r = read_ptr.load(memory_order_acquire);
198	schoenebeck	53	//printf("write_space_to_end: w=%d r=%d\n",w,r);
199			if(r > w) {
200			//printf("DEBUG: write_space_to_end_with_wrap: r>w r=%d w=%d val=%d\n",r,w,r - w - 1);
201			return(r - w - 1);
202			}
203			if(r <= wrap_elements) {
204			//printf("DEBUG: write_space_to_end_with_wrap: ATTENTION r <= wrap_elements: r=%d w=%d val=%d\n",r,w,size - w -1);
205			return(size - w -1);
206			}
207			if(r) {
208			//printf("DEBUG: write_space_to_end_with_wrap: r=%d w=%d val=%d\n",r,w,size - w + wrap_elements);
209			return(size - w + wrap_elements);
210			}
211			//printf("DEBUG: write_space_to_end_with_wrap: r=0 w=%d val=%d\n",w,size - w - 1 + wrap_elements);
212			return(size - w - 1 + wrap_elements);
213			}
214
215			/* this function adjusts the number of elements to write into the ringbuffer
216			in a way that the size boundary is avoided and that the wrap space always gets
217			entirely filled.
218			cnt contains the write_space_to_end_with_wrap() amount while
219			capped_cnt contains a capped amount of samples to read.
220			normally capped_cnt == cnt but in some cases eg when the disk thread needs
221			to refill tracks with smaller blocks because lots of streams require immediate
222			refill because lots of notes were started simultaneously.
223			In that case we set for example capped_cnt to a fixed amount (< cnt, eg 64k),
224			which helps to reduce the buffer refill latencies that occur between streams.
225			the first if() checks if the current write_ptr + capped_cnt resides within
226			the wrap area but is < size+wrap_elements. in that case we cannot return
227			capped_cnt because it would lead to a write_ptr wrapping and only a partial fill
228			of wrap space which would lead to errors. So we simply return cnt which ensures
229			that the the entire wrap space will get filled correctly.
230			In all other cases (which are not problematic because no write_ptr wrapping
231			occurs) we simply return capped_cnt.
232			*/
233			__inline int adjust_write_space_to_avoid_boundary(int cnt, int capped_cnt) {
234			int w;
235	persson	1790	w = write_ptr.load(memory_order_relaxed);
236	schoenebeck	53	if((w+capped_cnt) >= size && (w+capped_cnt) < (size+wrap_elements)) {
237			//printf("adjust_write_space_to_avoid_boundary returning cnt = %d\n",cnt);
238			return(cnt);
239			}
240			//printf("adjust_write_space_to_avoid_boundary returning capped_cnt = %d\n",capped_cnt);
241			return(capped_cnt);
242			}
243
244			__inline int write_space_to_end() {
245			int w, r;
246
247	persson	1790	w = write_ptr.load(memory_order_relaxed);
248			r = read_ptr.load(memory_order_acquire);
249	schoenebeck	53	//printf("write_space_to_end: w=%d r=%d\n",w,r);
250			if(r > w) return(r - w - 1);
251			if(r) return(size - w);
252			return(size - w - 1);
253			}
254
255			__inline int read_space_to_end() {
256			int w, r;
257
258	persson	1790	w = write_ptr.load(memory_order_acquire);
259			r = read_ptr.load(memory_order_relaxed);
260	schoenebeck	53	if(w >= r) return(w - r);
261			return(size - r);
262			}
263			__inline void init() {
264	persson	1790	write_ptr.store(0, memory_order_relaxed);
265			read_ptr.store(0, memory_order_relaxed);
266	schoenebeck	53	// wrap=0;
267			}
268
269			int write_space () {
270			int w, r;
271
272	persson	1790	w = write_ptr.load(memory_order_relaxed);
273			r = read_ptr.load(memory_order_acquire);
274	schoenebeck	53
275			if (w > r) {
276			return ((r - w + size) & size_mask) - 1;
277			} else if (w < r) {
278			return (r - w) - 1;
279			} else {
280			return size - 1;
281			}
282			}
283
284			int read_space () {
285			int w, r;
286
287	persson	1790	w = write_ptr.load(memory_order_acquire);
288			r = read_ptr.load(memory_order_relaxed);
289	schoenebeck	53
290			if (w >= r) {
291			return w - r;
292			} else {
293			return (w - r + size) & size_mask;
294			}
295			}
296
297			int size;
298			int wrap_elements;
299
300	schoenebeck	243	/**
301			* Independent, random access reading from a RingBuffer. This class
302			* allows to read from a RingBuffer without being forced to free read
303			* data while reading / positioning.
304			*/
305	schoenebeck	970	template<class T1, bool T1_DEEP_COPY>
306	schoenebeck	243	class _NonVolatileReader {
307			public:
308			int read_space() {
309			int r = read_ptr;
310	persson	1790	int w = pBuf->write_ptr.load(memory_order_acquire);
311	schoenebeck	243	return (w >= r) ? w - r : (w - r + pBuf->size) & pBuf->size_mask;
312			}
313
314			/**
315	schoenebeck	294	* Prefix decrement operator, for reducing NonVolatileReader's
316			* read position by one.
317			*/
318			inline void operator--() {
319	persson	1790	if (read_ptr == pBuf->read_ptr.load(memory_order_relaxed)) return; //TODO: or should we react oh this case (e.g. force segfault), as this is a very odd case?
320	senoner	1479	read_ptr = (read_ptr-1) & pBuf->size_mask;
321	schoenebeck	294	}
322
323			/**
324			* Postfix decrement operator, for reducing NonVolatileReader's
325			* read position by one.
326			*/
327			inline void operator--(int) {
328			--*this;
329			}
330	schoenebeck	2386
331			/**
332			* "Increment assign" operator, for advancing NonVolatileReader's
333			* read position by @a n elements.
334			*
335			* @param n - amount of elements to advance read position
336			*/
337			inline void operator+=(int n) {
338			if (read_space() < n) return;
339			read_ptr = (read_ptr+n) & pBuf->size_mask;
340			}
341	schoenebeck	294
342			/**
343			* Returns pointer to the RingBuffer data of current
344			* NonVolatileReader's read position and increments
345			* NonVolatileReader's read position by one.
346			*
347			* @returns pointer to element of current read position
348			*/
349			T* pop() {
350			if (!read_space()) return NULL;
351			T* pData = &pBuf->buf[read_ptr];
352			read_ptr++;
353			read_ptr &= pBuf->size_mask;
354			return pData;
355			}
356
357			/**
358	schoenebeck	243	* Reads one element from the NonVolatileReader's current read
359			* position and copies it to the variable pointed by \a dst and
360			* finally increments the NonVolatileReader's read position by
361			* one.
362			*
363			* @param dst - where the element is copied to
364			* @returns 1 on success, 0 otherwise
365			*/
366			int pop(T* dst) { return read(dst,1); }
367
368			/**
369			* Reads \a cnt elements from the NonVolatileReader's current
370			* read position and copies it to the buffer pointed by \a dest
371			* and finally increments the NonVolatileReader's read position
372			* by the number of read elements.
373			*
374			* @param dest - destination buffer
375			* @param cnt - number of elements to read
376			* @returns number of read elements
377			*/
378			int read(T* dest, int cnt) {
379			int free_cnt;
380			int cnt2;
381			int to_read;
382			int n1, n2;
383			int priv_read_ptr;
384
385			priv_read_ptr = read_ptr;
386
387			if ((free_cnt = read_space()) == 0) return 0;
388
389			to_read = cnt > free_cnt ? free_cnt : cnt;
390
391			cnt2 = priv_read_ptr + to_read;
392
393			if (cnt2 > pBuf->size) {
394			n1 = pBuf->size - priv_read_ptr;
395			n2 = cnt2 & pBuf->size_mask;
396			} else {
397			n1 = to_read;
398			n2 = 0;
399			}
400
401	schoenebeck	970	copy(dest, &pBuf->buf[priv_read_ptr], n1);
402	schoenebeck	243	priv_read_ptr = (priv_read_ptr + n1) & pBuf->size_mask;
403
404			if (n2) {
405	schoenebeck	970	copy(dest+n1, pBuf->buf, n2);
406	schoenebeck	243	priv_read_ptr = n2;
407			}
408
409			this->read_ptr = priv_read_ptr;
410			return to_read;
411			}
412	schoenebeck	294
413			/**
414			* Finally when the read data is not needed anymore, this method
415			* should be called to free the data in the RingBuffer up to the
416			* current read position of this NonVolatileReader.
417			*
418			* @see RingBuffer::increment_read_ptr()
419			*/
420			void free() {
421	persson	1790	pBuf->read_ptr.store(read_ptr, memory_order_release);
422	schoenebeck	294	}
423
424	schoenebeck	243	protected:
425	schoenebeck	970	_NonVolatileReader(RingBuffer<T1,T1_DEEP_COPY>* pBuf) {
426	schoenebeck	243	this->pBuf = pBuf;
427	persson	1790	this->read_ptr = pBuf->read_ptr.load(memory_order_relaxed);
428	schoenebeck	243	}
429
430	schoenebeck	970	RingBuffer<T1,T1_DEEP_COPY>* pBuf;
431	schoenebeck	243	int read_ptr;
432
433	schoenebeck	970	friend class RingBuffer<T1,T1_DEEP_COPY>;
434	schoenebeck	243	};
435
436	schoenebeck	970	typedef _NonVolatileReader<T,T_DEEP_COPY> NonVolatileReader;
437	schoenebeck	243
438			NonVolatileReader get_non_volatile_reader() { return NonVolatileReader(this); }
439
440	schoenebeck	53	protected:
441			T *buf;
442	persson	1790	atomic<int> write_ptr;
443			atomic<int> read_ptr;
444	schoenebeck	53	int size_mask;
445	schoenebeck	277
446	schoenebeck	970	/**
447			* Copies \a n amount of elements from the buffer given by
448			* \a pSrc to the buffer given by \a pDst.
449			*/
450			inline static void copy(T* pDst, T* pSrc, int n);
451	schoenebeck	2384
452			void _allocBuffer(int sz, int wrap_elements) {
453			this->wrap_elements = wrap_elements;
454
455			// the write-with-wrap functions need wrap_elements extra
456			// space in the buffer to be able to copy the wrap space
457			sz += wrap_elements;
458	schoenebeck	970
459	schoenebeck	2384	int power_of_two;
460			for (power_of_two = 1;
461			1<<power_of_two < sz;
462			power_of_two++);
463
464			size = 1<<power_of_two;
465			size_mask = size;
466			size_mask -= 1;
467			buf = new T[size + wrap_elements];
468			}
469
470	schoenebeck	970	friend class _NonVolatileReader<T,T_DEEP_COPY>;
471	schoenebeck	53	};
472
473	schoenebeck	970	template<class T, bool T_DEEP_COPY>
474			T* RingBuffer<T,T_DEEP_COPY>::get_write_ptr (void) {
475	persson	1790	return(&buf[write_ptr.load(memory_order_relaxed)]);
476	schoenebeck	53	}
477
478	schoenebeck	970	template<class T, bool T_DEEP_COPY>
479			T* RingBuffer<T,T_DEEP_COPY>::get_buffer_begin (void) {
480	schoenebeck	53	return(buf);
481			}
482
483
484
485	schoenebeck	970	template<class T, bool T_DEEP_COPY>
486			int RingBuffer<T,T_DEEP_COPY>::read(T* dest, int cnt)
487	schoenebeck	53	{
488			int free_cnt;
489			int cnt2;
490			int to_read;
491			int n1, n2;
492			int priv_read_ptr;
493
494	persson	1790	priv_read_ptr = read_ptr.load(memory_order_relaxed);
495	schoenebeck	53
496			if ((free_cnt = read_space ()) == 0) {
497			return 0;
498			}
499
500			to_read = cnt > free_cnt ? free_cnt : cnt;
501
502			cnt2 = priv_read_ptr + to_read;
503
504			if (cnt2 > size) {
505			n1 = size - priv_read_ptr;
506			n2 = cnt2 & size_mask;
507			} else {
508			n1 = to_read;
509			n2 = 0;
510			}
511
512	schoenebeck	970	copy(dest, &buf[priv_read_ptr], n1);
513	schoenebeck	53	priv_read_ptr = (priv_read_ptr + n1) & size_mask;
514
515			if (n2) {
516	schoenebeck	970	copy(dest+n1, buf, n2);
517	schoenebeck	53	priv_read_ptr = n2;
518			}
519
520	persson	1790	read_ptr.store(priv_read_ptr, memory_order_release);
521	schoenebeck	53	return to_read;
522			}
523
524	schoenebeck	970	template<class T, bool T_DEEP_COPY>
525			int RingBuffer<T,T_DEEP_COPY>::write(T* src, int cnt)
526	schoenebeck	53	{
527			int free_cnt;
528			int cnt2;
529			int to_write;
530			int n1, n2;
531			int priv_write_ptr;
532
533	persson	1790	priv_write_ptr = write_ptr.load(memory_order_relaxed);
534	schoenebeck	53
535			if ((free_cnt = write_space ()) == 0) {
536			return 0;
537			}
538
539			to_write = cnt > free_cnt ? free_cnt : cnt;
540
541			cnt2 = priv_write_ptr + to_write;
542
543			if (cnt2 > size) {
544			n1 = size - priv_write_ptr;
545			n2 = cnt2 & size_mask;
546			} else {
547			n1 = to_write;
548			n2 = 0;
549			}
550
551	schoenebeck	970	copy(&buf[priv_write_ptr], src, n1);
552	schoenebeck	53	priv_write_ptr = (priv_write_ptr + n1) & size_mask;
553
554			if (n2) {
555	schoenebeck	970	copy(buf, src+n1, n2);
556	schoenebeck	53	priv_write_ptr = n2;
557			}
558	persson	1790	write_ptr.store(priv_write_ptr, memory_order_release);
559	schoenebeck	53	return to_write;
560			}
561
562	schoenebeck	970	template<class T, bool T_DEEP_COPY>
563			void RingBuffer<T,T_DEEP_COPY>::copy(T* pDst, T* pSrc, int n) {
564			if (T_DEEP_COPY) { // deep copy - won't work for data structures without assignment operator implementation
565			for (int i = 0; i < n; i++) pDst[i] = pSrc[i];
566			} else { // flat copy - won't work for complex data structures !
567			memcpy(pDst, pSrc, n * sizeof(T));
568			}
569			}
570	schoenebeck	53
571			#endif /* RINGBUFFER_H */