src/common/RingBuffer.h

/***************************************************************************
 *                                                                         *
 *   LinuxSampler - modular, streaming capable sampler                     *
 *                                                                         *
 *   Copyright (C) 2003, 2004 by Benno Senoner and Christian Schoenebeck   *
 *   Copyright (C) 2005 - 2008 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) {
            int power_of_two;

            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;

            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];
    };

    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;
            }

            /**
             * 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);

    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	persson	1790	* Copyright (C) 2005 - 2008 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			write_ptr(0), read_ptr(0) {
72	schoenebeck	53	int power_of_two;
73
74			this->wrap_elements = wrap_elements;
75
76	persson	1895	// the write-with-wrap functions need wrap_elements extra
77			// space in the buffer to be able to copy the wrap space
78			sz += wrap_elements;
79
80	schoenebeck	53	for (power_of_two = 1;
81			1<<power_of_two < sz;
82			power_of_two++);
83
84			size = 1<<power_of_two;
85			size_mask = size;
86			size_mask -= 1;
87			buf = new T[size + wrap_elements];
88			};
89
90			virtual ~RingBuffer() {
91			delete [] buf;
92			}
93
94			/**
95			* Sets all remaining write space elements to zero. The write pointer
96			* will currently not be incremented after, but that might change in
97			* future.
98	schoenebeck	970	*
99			* @e Caution: for @c T_DEEP_COPY=true you might probably @e NOT want
100			* to call this method at all, at least not in case type @c T allocates
101			* any additional data on the heap by itself.
102	schoenebeck	53	*/
103			inline void fill_write_space_with_null() {
104	persson	1790	int w = write_ptr.load(memory_order_relaxed),
105			r = read_ptr.load(memory_order_acquire);
106	senoner	1479	memset(get_write_ptr(), 0, sizeof(T)*write_space_to_end());
107	schoenebeck	53	if (r && w >= r) {
108	senoner	1479	memset(get_buffer_begin(), 0, sizeof(T)*(r - 1));
109	schoenebeck	53	}
110
111			// set the wrap space elements to null
112	senoner	1479	if (wrap_elements) memset(&buf[size], 0, sizeof(T)*wrap_elements);
113	schoenebeck	53	}
114
115			__inline int read (T *dest, int cnt);
116			__inline int write (T *src, int cnt);
117
118			inline int push(T* src) { return write(src,1); }
119			inline int pop(T* dst) { return read(dst,1); }
120
121			__inline T *get_buffer_begin();
122
123			__inline T *get_read_ptr(void) {
124	persson	1790	return(&buf[read_ptr.load(memory_order_relaxed)]);
125	schoenebeck	53	}
126
127			/**
128			* Returns a pointer to the element from the current read position,
129			* advanced by \a offset elements.
130			*/
131			/inline T get_read_ptr(int offset) {
132	persson	1790	int r = read_ptr.load(memory_order_relaxed);
133	schoenebeck	53	r += offset;
134			r &= size_mask;
135			return &buf[r];
136			}*/
137
138			__inline T *get_write_ptr();
139			__inline void increment_read_ptr(int cnt) {
140	persson	1790	read_ptr.store((read_ptr.load(memory_order_relaxed) + cnt) & size_mask, memory_order_release);
141	schoenebeck	53	}
142			__inline void set_read_ptr(int val) {
143	persson	1790	read_ptr.store(val, memory_order_release);
144	schoenebeck	53	}
145
146			__inline void increment_write_ptr(int cnt) {
147	persson	1790	write_ptr.store((write_ptr.load(memory_order_relaxed) + cnt) & size_mask, memory_order_release);
148	schoenebeck	53	}
149
150			/* this function increments the write_ptr by cnt, if the buffer wraps then
151			subtract size from the write_ptr value so that it stays within 0<write_ptr<size
152			use this function to increment the write ptr after you filled the buffer
153			with a number of elements given by write_space_to_end_with_wrap().
154			This ensures that the data that is written to the buffer fills up all
155			the wrap space that resides past the regular buffer. The wrap_space is needed for
156			interpolation. So that the audio thread sees the ringbuffer like a linear space
157			which allows us to use faster routines.
158			When the buffer wraps the wrap part is memcpy()ied to the beginning of the buffer
159			and the write ptr incremented accordingly.
160			*/
161			__inline void increment_write_ptr_with_wrap(int cnt) {
162	persson	1790	int w = write_ptr.load(memory_order_relaxed);
163	schoenebeck	53	w += cnt;
164			if(w >= size) {
165			w -= size;
166	schoenebeck	970	copy(&buf[0], &buf[size], w);
167	schoenebeck	53	//printf("DEBUG !!!! increment_write_ptr_with_wrap: buffer wrapped, elements wrapped = %d (wrap_elements %d)\n",w,wrap_elements);
168			}
169	persson	1790	write_ptr.store(w, memory_order_release);
170	schoenebeck	53	}
171
172			/* this function returns the available write space in the buffer
173			when the read_ptr > write_ptr it returns the space inbetween, otherwise
174			when the read_ptr < write_ptr it returns the space between write_ptr and
175			the buffer end, including the wrap_space.
176			There is an exception to it. When read_ptr <= wrap_elements. In that
177			case we return the write space to buffer end (-1) without the wrap_elements,
178			this is needed because a subsequent increment_write_ptr which copies the
179			data that resides into the wrap space to the beginning of the buffer and increments
180			the write_ptr would cause the write_ptr overstepping the read_ptr which would be an error.
181			So basically the if(r<=wrap_elements) we return the buffer space to end - 1 which
182			ensures that at the next call there will be one element free to write before the buffer wraps
183			and usually (except in EOF situations) the next write_space_to_end_with_wrap() will return
184			1 + wrap_elements which ensures that the wrap part gets fully filled with data
185			*/
186			__inline int write_space_to_end_with_wrap() {
187			int w, r;
188
189	persson	1790	w = write_ptr.load(memory_order_relaxed);
190			r = read_ptr.load(memory_order_acquire);
191	schoenebeck	53	//printf("write_space_to_end: w=%d r=%d\n",w,r);
192			if(r > w) {
193			//printf("DEBUG: write_space_to_end_with_wrap: r>w r=%d w=%d val=%d\n",r,w,r - w - 1);
194			return(r - w - 1);
195			}
196			if(r <= wrap_elements) {
197			//printf("DEBUG: write_space_to_end_with_wrap: ATTENTION r <= wrap_elements: r=%d w=%d val=%d\n",r,w,size - w -1);
198			return(size - w -1);
199			}
200			if(r) {
201			//printf("DEBUG: write_space_to_end_with_wrap: r=%d w=%d val=%d\n",r,w,size - w + wrap_elements);
202			return(size - w + wrap_elements);
203			}
204			//printf("DEBUG: write_space_to_end_with_wrap: r=0 w=%d val=%d\n",w,size - w - 1 + wrap_elements);
205			return(size - w - 1 + wrap_elements);
206			}
207
208			/* this function adjusts the number of elements to write into the ringbuffer
209			in a way that the size boundary is avoided and that the wrap space always gets
210			entirely filled.
211			cnt contains the write_space_to_end_with_wrap() amount while
212			capped_cnt contains a capped amount of samples to read.
213			normally capped_cnt == cnt but in some cases eg when the disk thread needs
214			to refill tracks with smaller blocks because lots of streams require immediate
215			refill because lots of notes were started simultaneously.
216			In that case we set for example capped_cnt to a fixed amount (< cnt, eg 64k),
217			which helps to reduce the buffer refill latencies that occur between streams.
218			the first if() checks if the current write_ptr + capped_cnt resides within
219			the wrap area but is < size+wrap_elements. in that case we cannot return
220			capped_cnt because it would lead to a write_ptr wrapping and only a partial fill
221			of wrap space which would lead to errors. So we simply return cnt which ensures
222			that the the entire wrap space will get filled correctly.
223			In all other cases (which are not problematic because no write_ptr wrapping
224			occurs) we simply return capped_cnt.
225			*/
226			__inline int adjust_write_space_to_avoid_boundary(int cnt, int capped_cnt) {
227			int w;
228	persson	1790	w = write_ptr.load(memory_order_relaxed);
229	schoenebeck	53	if((w+capped_cnt) >= size && (w+capped_cnt) < (size+wrap_elements)) {
230			//printf("adjust_write_space_to_avoid_boundary returning cnt = %d\n",cnt);
231			return(cnt);
232			}
233			//printf("adjust_write_space_to_avoid_boundary returning capped_cnt = %d\n",capped_cnt);
234			return(capped_cnt);
235			}
236
237			__inline int write_space_to_end() {
238			int w, r;
239
240	persson	1790	w = write_ptr.load(memory_order_relaxed);
241			r = read_ptr.load(memory_order_acquire);
242	schoenebeck	53	//printf("write_space_to_end: w=%d r=%d\n",w,r);
243			if(r > w) return(r - w - 1);
244			if(r) return(size - w);
245			return(size - w - 1);
246			}
247
248			__inline int read_space_to_end() {
249			int w, r;
250
251	persson	1790	w = write_ptr.load(memory_order_acquire);
252			r = read_ptr.load(memory_order_relaxed);
253	schoenebeck	53	if(w >= r) return(w - r);
254			return(size - r);
255			}
256			__inline void init() {
257	persson	1790	write_ptr.store(0, memory_order_relaxed);
258			read_ptr.store(0, memory_order_relaxed);
259	schoenebeck	53	// wrap=0;
260			}
261
262			int write_space () {
263			int w, r;
264
265	persson	1790	w = write_ptr.load(memory_order_relaxed);
266			r = read_ptr.load(memory_order_acquire);
267	schoenebeck	53
268			if (w > r) {
269			return ((r - w + size) & size_mask) - 1;
270			} else if (w < r) {
271			return (r - w) - 1;
272			} else {
273			return size - 1;
274			}
275			}
276
277			int read_space () {
278			int w, r;
279
280	persson	1790	w = write_ptr.load(memory_order_acquire);
281			r = read_ptr.load(memory_order_relaxed);
282	schoenebeck	53
283			if (w >= r) {
284			return w - r;
285			} else {
286			return (w - r + size) & size_mask;
287			}
288			}
289
290			int size;
291			int wrap_elements;
292
293	schoenebeck	243	/**
294			* Independent, random access reading from a RingBuffer. This class
295			* allows to read from a RingBuffer without being forced to free read
296			* data while reading / positioning.
297			*/
298	schoenebeck	970	template<class T1, bool T1_DEEP_COPY>
299	schoenebeck	243	class _NonVolatileReader {
300			public:
301			int read_space() {
302			int r = read_ptr;
303	persson	1790	int w = pBuf->write_ptr.load(memory_order_acquire);
304	schoenebeck	243	return (w >= r) ? w - r : (w - r + pBuf->size) & pBuf->size_mask;
305			}
306
307			/**
308	schoenebeck	294	* Prefix decrement operator, for reducing NonVolatileReader's
309			* read position by one.
310			*/
311			inline void operator--() {
312	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?
313	senoner	1479	read_ptr = (read_ptr-1) & pBuf->size_mask;
314	schoenebeck	294	}
315
316			/**
317			* Postfix decrement operator, for reducing NonVolatileReader's
318			* read position by one.
319			*/
320			inline void operator--(int) {
321			--*this;
322			}
323
324			/**
325			* Returns pointer to the RingBuffer data of current
326			* NonVolatileReader's read position and increments
327			* NonVolatileReader's read position by one.
328			*
329			* @returns pointer to element of current read position
330			*/
331			T* pop() {
332			if (!read_space()) return NULL;
333			T* pData = &pBuf->buf[read_ptr];
334			read_ptr++;
335			read_ptr &= pBuf->size_mask;
336			return pData;
337			}
338
339			/**
340	schoenebeck	243	* Reads one element from the NonVolatileReader's current read
341			* position and copies it to the variable pointed by \a dst and
342			* finally increments the NonVolatileReader's read position by
343			* one.
344			*
345			* @param dst - where the element is copied to
346			* @returns 1 on success, 0 otherwise
347			*/
348			int pop(T* dst) { return read(dst,1); }
349
350			/**
351			* Reads \a cnt elements from the NonVolatileReader's current
352			* read position and copies it to the buffer pointed by \a dest
353			* and finally increments the NonVolatileReader's read position
354			* by the number of read elements.
355			*
356			* @param dest - destination buffer
357			* @param cnt - number of elements to read
358			* @returns number of read elements
359			*/
360			int read(T* dest, int cnt) {
361			int free_cnt;
362			int cnt2;
363			int to_read;
364			int n1, n2;
365			int priv_read_ptr;
366
367			priv_read_ptr = read_ptr;
368
369			if ((free_cnt = read_space()) == 0) return 0;
370
371			to_read = cnt > free_cnt ? free_cnt : cnt;
372
373			cnt2 = priv_read_ptr + to_read;
374
375			if (cnt2 > pBuf->size) {
376			n1 = pBuf->size - priv_read_ptr;
377			n2 = cnt2 & pBuf->size_mask;
378			} else {
379			n1 = to_read;
380			n2 = 0;
381			}
382
383	schoenebeck	970	copy(dest, &pBuf->buf[priv_read_ptr], n1);
384	schoenebeck	243	priv_read_ptr = (priv_read_ptr + n1) & pBuf->size_mask;
385
386			if (n2) {
387	schoenebeck	970	copy(dest+n1, pBuf->buf, n2);
388	schoenebeck	243	priv_read_ptr = n2;
389			}
390
391			this->read_ptr = priv_read_ptr;
392			return to_read;
393			}
394	schoenebeck	294
395			/**
396			* Finally when the read data is not needed anymore, this method
397			* should be called to free the data in the RingBuffer up to the
398			* current read position of this NonVolatileReader.
399			*
400			* @see RingBuffer::increment_read_ptr()
401			*/
402			void free() {
403	persson	1790	pBuf->read_ptr.store(read_ptr, memory_order_release);
404	schoenebeck	294	}
405
406	schoenebeck	243	protected:
407	schoenebeck	970	_NonVolatileReader(RingBuffer<T1,T1_DEEP_COPY>* pBuf) {
408	schoenebeck	243	this->pBuf = pBuf;
409	persson	1790	this->read_ptr = pBuf->read_ptr.load(memory_order_relaxed);
410	schoenebeck	243	}
411
412	schoenebeck	970	RingBuffer<T1,T1_DEEP_COPY>* pBuf;
413	schoenebeck	243	int read_ptr;
414
415	schoenebeck	970	friend class RingBuffer<T1,T1_DEEP_COPY>;
416	schoenebeck	243	};
417
418	schoenebeck	970	typedef _NonVolatileReader<T,T_DEEP_COPY> NonVolatileReader;
419	schoenebeck	243
420			NonVolatileReader get_non_volatile_reader() { return NonVolatileReader(this); }
421
422	schoenebeck	53	protected:
423			T *buf;
424	persson	1790	atomic<int> write_ptr;
425			atomic<int> read_ptr;
426	schoenebeck	53	int size_mask;
427	schoenebeck	277
428	schoenebeck	970	/**
429			* Copies \a n amount of elements from the buffer given by
430			* \a pSrc to the buffer given by \a pDst.
431			*/
432			inline static void copy(T* pDst, T* pSrc, int n);
433
434			friend class _NonVolatileReader<T,T_DEEP_COPY>;
435	schoenebeck	53	};
436
437	schoenebeck	970	template<class T, bool T_DEEP_COPY>
438			T* RingBuffer<T,T_DEEP_COPY>::get_write_ptr (void) {
439	persson	1790	return(&buf[write_ptr.load(memory_order_relaxed)]);
440	schoenebeck	53	}
441
442	schoenebeck	970	template<class T, bool T_DEEP_COPY>
443			T* RingBuffer<T,T_DEEP_COPY>::get_buffer_begin (void) {
444	schoenebeck	53	return(buf);
445			}
446
447
448
449	schoenebeck	970	template<class T, bool T_DEEP_COPY>
450			int RingBuffer<T,T_DEEP_COPY>::read(T* dest, int cnt)
451	schoenebeck	53	{
452			int free_cnt;
453			int cnt2;
454			int to_read;
455			int n1, n2;
456			int priv_read_ptr;
457
458	persson	1790	priv_read_ptr = read_ptr.load(memory_order_relaxed);
459	schoenebeck	53
460			if ((free_cnt = read_space ()) == 0) {
461			return 0;
462			}
463
464			to_read = cnt > free_cnt ? free_cnt : cnt;
465
466			cnt2 = priv_read_ptr + to_read;
467
468			if (cnt2 > size) {
469			n1 = size - priv_read_ptr;
470			n2 = cnt2 & size_mask;
471			} else {
472			n1 = to_read;
473			n2 = 0;
474			}
475
476	schoenebeck	970	copy(dest, &buf[priv_read_ptr], n1);
477	schoenebeck	53	priv_read_ptr = (priv_read_ptr + n1) & size_mask;
478
479			if (n2) {
480	schoenebeck	970	copy(dest+n1, buf, n2);
481	schoenebeck	53	priv_read_ptr = n2;
482			}
483
484	persson	1790	read_ptr.store(priv_read_ptr, memory_order_release);
485	schoenebeck	53	return to_read;
486			}
487
488	schoenebeck	970	template<class T, bool T_DEEP_COPY>
489			int RingBuffer<T,T_DEEP_COPY>::write(T* src, int cnt)
490	schoenebeck	53	{
491			int free_cnt;
492			int cnt2;
493			int to_write;
494			int n1, n2;
495			int priv_write_ptr;
496
497	persson	1790	priv_write_ptr = write_ptr.load(memory_order_relaxed);
498	schoenebeck	53
499			if ((free_cnt = write_space ()) == 0) {
500			return 0;
501			}
502
503			to_write = cnt > free_cnt ? free_cnt : cnt;
504
505			cnt2 = priv_write_ptr + to_write;
506
507			if (cnt2 > size) {
508			n1 = size - priv_write_ptr;
509			n2 = cnt2 & size_mask;
510			} else {
511			n1 = to_write;
512			n2 = 0;
513			}
514
515	schoenebeck	970	copy(&buf[priv_write_ptr], src, n1);
516	schoenebeck	53	priv_write_ptr = (priv_write_ptr + n1) & size_mask;
517
518			if (n2) {
519	schoenebeck	970	copy(buf, src+n1, n2);
520	schoenebeck	53	priv_write_ptr = n2;
521			}
522	persson	1790	write_ptr.store(priv_write_ptr, memory_order_release);
523	schoenebeck	53	return to_write;
524			}
525
526	schoenebeck	970	template<class T, bool T_DEEP_COPY>
527			void RingBuffer<T,T_DEEP_COPY>::copy(T* pDst, T* pSrc, int n) {
528			if (T_DEEP_COPY) { // deep copy - won't work for data structures without assignment operator implementation
529			for (int i = 0; i < n; i++) pDst[i] = pSrc[i];
530			} else { // flat copy - won't work for complex data structures !
531			memcpy(pDst, pSrc, n * sizeof(T));
532			}
533			}
534	schoenebeck	53
535			#endif /* RINGBUFFER_H */