/[svn]/linuxsampler/trunk/src/common/RingBuffer.h
ViewVC logotype

Diff of /linuxsampler/trunk/src/common/RingBuffer.h

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 56 by schoenebeck, Tue Apr 27 09:21:58 2004 UTC revision 1790 by persson, Sun Nov 2 12:05:00 2008 UTC
# Line 3  Line 3 
3   *   LinuxSampler - modular, streaming capable sampler                     *   *   LinuxSampler - modular, streaming capable sampler                     *
4   *                                                                         *   *                                                                         *
5   *   Copyright (C) 2003, 2004 by Benno Senoner and Christian Schoenebeck   *   *   Copyright (C) 2003, 2004 by Benno Senoner and Christian Schoenebeck   *
6     *   Copyright (C) 2005 - 2008 Christian Schoenebeck                       *
7   *                                                                         *   *                                                                         *
8   *   This program is free software; you can redistribute it and/or modify  *   *   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  *   *   it under the terms of the GNU General Public License as published by  *
# Line 23  Line 24 
24  #ifndef RINGBUFFER_H  #ifndef RINGBUFFER_H
25  #define RINGBUFFER_H  #define RINGBUFFER_H
26    
27  #define DEFAULT_WRAP_ELEMENTS 1024  #define DEFAULT_WRAP_ELEMENTS 0
28    
29  #include <string.h>  #include <string.h>
30    
31  #include "atomic.h"  #include "lsatomic.h"
32    
33  template<class T>  using LinuxSampler::atomic;
34    using LinuxSampler::memory_order_relaxed;
35    using LinuxSampler::memory_order_acquire;
36    using LinuxSampler::memory_order_release;
37    
38    
39    /** @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  class RingBuffer  class RingBuffer
68  {  {
69  public:  public:
70      RingBuffer (int sz, int wrap_elements = DEFAULT_WRAP_ELEMENTS) {      RingBuffer (int sz, int wrap_elements = DEFAULT_WRAP_ELEMENTS) :
71            write_ptr(0), read_ptr(0) {
72              int power_of_two;              int power_of_two;
73    
74              this->wrap_elements = wrap_elements;              this->wrap_elements = wrap_elements;
# Line 45  public: Line 80  public:
80              size = 1<<power_of_two;              size = 1<<power_of_two;
81              size_mask = size;              size_mask = size;
82              size_mask -= 1;              size_mask -= 1;
             atomic_set(&write_ptr, 0);  
             atomic_set(&read_ptr, 0);  
83              buf = new T[size + wrap_elements];              buf = new T[size + wrap_elements];
84      };      };
85    
# Line 58  public: Line 91  public:
91       * Sets all remaining write space elements to zero. The write pointer       * Sets all remaining write space elements to zero. The write pointer
92       * will currently not be incremented after, but that might change in       * will currently not be incremented after, but that might change in
93       * future.       * future.
94         *
95         * @e Caution: for @c T_DEEP_COPY=true you might probably @e NOT want
96         * to call this method at all, at least not in case type @c T allocates
97         * any additional data on the heap by itself.
98       */       */
99      inline void fill_write_space_with_null() {      inline void fill_write_space_with_null() {
100               int w = atomic_read(&write_ptr),               int w = write_ptr.load(memory_order_relaxed),
101                   r = atomic_read(&read_ptr);                   r = read_ptr.load(memory_order_acquire);
102               memset(get_write_ptr(), 0, write_space_to_end());               memset(get_write_ptr(), 0, sizeof(T)*write_space_to_end());
103               if (r && w >= r) {               if (r && w >= r) {
104                 memset(get_buffer_begin(), 0, r - 1);                 memset(get_buffer_begin(), 0, sizeof(T)*(r - 1));
105               }               }
106    
107               // set the wrap space elements to null               // set the wrap space elements to null
108               if (wrap_elements) memset(&buf[size], 0, wrap_elements);               if (wrap_elements) memset(&buf[size], 0, sizeof(T)*wrap_elements);
109             }             }
110    
111      __inline int  read (T *dest, int cnt);      __inline int  read (T *dest, int cnt);
# Line 80  public: Line 117  public:
117      __inline T *get_buffer_begin();      __inline T *get_buffer_begin();
118    
119      __inline T *get_read_ptr(void) {      __inline T *get_read_ptr(void) {
120        return(&buf[atomic_read(&read_ptr)]);        return(&buf[read_ptr.load(memory_order_relaxed)]);
121      }      }
122    
123      /**      /**
# Line 88  public: Line 125  public:
125       * advanced by \a offset elements.       * advanced by \a offset elements.
126       */       */
127      /*inline T* get_read_ptr(int offset) {      /*inline T* get_read_ptr(int offset) {
128          int r = atomic_read(&read_ptr);          int r = read_ptr.load(memory_order_relaxed);
129          r += offset;          r += offset;
130          r &= size_mask;          r &= size_mask;
131          return &buf[r];          return &buf[r];
# Line 96  public: Line 133  public:
133    
134      __inline T *get_write_ptr();      __inline T *get_write_ptr();
135      __inline void increment_read_ptr(int cnt) {      __inline void increment_read_ptr(int cnt) {
136                 atomic_set(&read_ptr , (atomic_read(&read_ptr) + cnt) & size_mask);                 read_ptr.store((read_ptr.load(memory_order_relaxed) + cnt) & size_mask, memory_order_release);
137               }               }
138      __inline void set_read_ptr(int val) {      __inline void set_read_ptr(int val) {
139                 atomic_set(&read_ptr , val);                 read_ptr.store(val, memory_order_release);
140               }               }
141    
142      __inline void increment_write_ptr(int cnt) {      __inline void increment_write_ptr(int cnt) {
143                 atomic_set(&write_ptr,  (atomic_read(&write_ptr) + cnt) & size_mask);                 write_ptr.store((write_ptr.load(memory_order_relaxed) + cnt) & size_mask, memory_order_release);
144               }               }
145    
146      /* this function increments the write_ptr by cnt, if the buffer wraps then      /* this function increments the write_ptr by cnt, if the buffer wraps then
# Line 118  public: Line 155  public:
155         and the write ptr incremented accordingly.         and the write ptr incremented accordingly.
156      */      */
157      __inline void increment_write_ptr_with_wrap(int cnt) {      __inline void increment_write_ptr_with_wrap(int cnt) {
158                 int w=atomic_read(&write_ptr);                 int w = write_ptr.load(memory_order_relaxed);
159                 w += cnt;                 w += cnt;
160                 if(w >= size) {                 if(w >= size) {
161                   w -= size;                   w -= size;
162                   memcpy(&buf[0], &buf[size], w*sizeof(T));                   copy(&buf[0], &buf[size], w);
163  //printf("DEBUG !!!! increment_write_ptr_with_wrap: buffer wrapped, elements wrapped = %d (wrap_elements %d)\n",w,wrap_elements);  //printf("DEBUG !!!! increment_write_ptr_with_wrap: buffer wrapped, elements wrapped = %d (wrap_elements %d)\n",w,wrap_elements);
164                 }                 }
165                 atomic_set(&write_ptr, w);                 write_ptr.store(w, memory_order_release);
166               }               }
167    
168      /* this function returns the available write space in the buffer      /* this function returns the available write space in the buffer
# Line 145  public: Line 182  public:
182      __inline int write_space_to_end_with_wrap() {      __inline int write_space_to_end_with_wrap() {
183                int w, r;                int w, r;
184    
185                w = atomic_read(&write_ptr);                w = write_ptr.load(memory_order_relaxed);
186                r = atomic_read(&read_ptr);                r = read_ptr.load(memory_order_acquire);
187  //printf("write_space_to_end: w=%d r=%d\n",w,r);  //printf("write_space_to_end: w=%d r=%d\n",w,r);
188                if(r > w) {                if(r > w) {
189                  //printf("DEBUG: write_space_to_end_with_wrap: r>w r=%d w=%d val=%d\n",r,w,r - w - 1);                  //printf("DEBUG: write_space_to_end_with_wrap: r>w r=%d w=%d val=%d\n",r,w,r - w - 1);
# Line 184  public: Line 221  public:
221             */             */
222      __inline int adjust_write_space_to_avoid_boundary(int cnt, int capped_cnt) {      __inline int adjust_write_space_to_avoid_boundary(int cnt, int capped_cnt) {
223                 int w;                 int w;
224                 w = atomic_read(&write_ptr);                 w = write_ptr.load(memory_order_relaxed);
225                 if((w+capped_cnt) >= size && (w+capped_cnt) < (size+wrap_elements)) {                 if((w+capped_cnt) >= size && (w+capped_cnt) < (size+wrap_elements)) {
226  //printf("adjust_write_space_to_avoid_boundary returning cnt = %d\n",cnt);  //printf("adjust_write_space_to_avoid_boundary returning cnt = %d\n",cnt);
227                   return(cnt);                   return(cnt);
# Line 196  public: Line 233  public:
233      __inline int write_space_to_end() {      __inline int write_space_to_end() {
234                int w, r;                int w, r;
235    
236                w = atomic_read(&write_ptr);                w = write_ptr.load(memory_order_relaxed);
237                r = atomic_read(&read_ptr);                r = read_ptr.load(memory_order_acquire);
238  //printf("write_space_to_end: w=%d r=%d\n",w,r);  //printf("write_space_to_end: w=%d r=%d\n",w,r);
239                if(r > w) return(r - w - 1);                if(r > w) return(r - w - 1);
240                if(r) return(size - w);                if(r) return(size - w);
# Line 207  public: Line 244  public:
244      __inline int read_space_to_end() {      __inline int read_space_to_end() {
245                int w, r;                int w, r;
246    
247                w = atomic_read(&write_ptr);                w = write_ptr.load(memory_order_acquire);
248                r = atomic_read(&read_ptr);                r = read_ptr.load(memory_order_relaxed);
249                if(w >= r) return(w - r);                if(w >= r) return(w - r);
250                return(size - r);                return(size - r);
251              }              }
252      __inline void init() {      __inline void init() {
253                     atomic_set(&write_ptr, 0);                     write_ptr.store(0, memory_order_relaxed);
254                     atomic_set(&read_ptr, 0);                     read_ptr.store(0, memory_order_relaxed);
255                   //  wrap=0;                   //  wrap=0;
256              }              }
257    
258      int write_space () {      int write_space () {
259              int w, r;              int w, r;
260    
261              w = atomic_read(&write_ptr);              w = write_ptr.load(memory_order_relaxed);
262              r = atomic_read(&read_ptr);              r = read_ptr.load(memory_order_acquire);
263    
264              if (w > r) {              if (w > r) {
265                      return ((r - w + size) & size_mask) - 1;                      return ((r - w + size) & size_mask) - 1;
# Line 236  public: Line 273  public:
273      int read_space () {      int read_space () {
274              int w, r;              int w, r;
275    
276              w = atomic_read(&write_ptr);              w = write_ptr.load(memory_order_acquire);
277              r = atomic_read(&read_ptr);              r = read_ptr.load(memory_order_relaxed);
278    
279              if (w >= r) {              if (w >= r) {
280                      return w - r;                      return w - r;
# Line 249  public: Line 286  public:
286      int size;      int size;
287      int wrap_elements;      int wrap_elements;
288    
289        /**
290         * Independent, random access reading from a RingBuffer. This class
291         * allows to read from a RingBuffer without being forced to free read
292         * data while reading / positioning.
293         */
294        template<class T1, bool T1_DEEP_COPY>
295        class _NonVolatileReader {
296            public:
297                int read_space() {
298                    int r = read_ptr;
299                    int w = pBuf->write_ptr.load(memory_order_acquire);
300                    return (w >= r) ? w - r : (w - r + pBuf->size) & pBuf->size_mask;
301                }
302    
303                /**
304                 * Prefix decrement operator, for reducing NonVolatileReader's
305                 * read position by one.
306                 */
307                inline void operator--() {
308                    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?
309                    read_ptr = (read_ptr-1) & pBuf->size_mask;
310                }
311    
312                /**
313                 * Postfix decrement operator, for reducing NonVolatileReader's
314                 * read position by one.
315                 */
316                inline void operator--(int) {
317                    --*this;
318                }
319    
320                /**
321                 * Returns pointer to the RingBuffer data of current
322                 * NonVolatileReader's read position and increments
323                 * NonVolatileReader's read position by one.
324                 *
325                 * @returns pointer to element of current read position
326                 */
327                T* pop() {
328                    if (!read_space()) return NULL;
329                    T* pData = &pBuf->buf[read_ptr];
330                    read_ptr++;
331                    read_ptr &= pBuf->size_mask;
332                    return pData;
333                }
334    
335                /**
336                 * Reads one element from the NonVolatileReader's current read
337                 * position and copies it to the variable pointed by \a dst and
338                 * finally increments the NonVolatileReader's read position by
339                 * one.
340                 *
341                 * @param dst - where the element is copied to
342                 * @returns 1 on success, 0 otherwise
343                 */
344                int pop(T* dst) { return read(dst,1); }
345    
346                /**
347                 * Reads \a cnt elements from the NonVolatileReader's current
348                 * read position and copies it to the buffer pointed by \a dest
349                 * and finally increments the NonVolatileReader's read position
350                 * by the number of read elements.
351                 *
352                 * @param dest - destination buffer
353                 * @param cnt  - number of elements to read
354                 * @returns number of read elements
355                 */
356                int read(T* dest, int cnt) {
357                    int free_cnt;
358                    int cnt2;
359                    int to_read;
360                    int n1, n2;
361                    int priv_read_ptr;
362    
363                    priv_read_ptr = read_ptr;
364    
365                    if ((free_cnt = read_space()) == 0) return 0;
366    
367                    to_read = cnt > free_cnt ? free_cnt : cnt;
368    
369                    cnt2 = priv_read_ptr + to_read;
370    
371                    if (cnt2 > pBuf->size) {
372                        n1 = pBuf->size - priv_read_ptr;
373                        n2 = cnt2 & pBuf->size_mask;
374                    } else {
375                        n1 = to_read;
376                        n2 = 0;
377                    }
378    
379                    copy(dest, &pBuf->buf[priv_read_ptr], n1);
380                    priv_read_ptr = (priv_read_ptr + n1) & pBuf->size_mask;
381    
382                    if (n2) {
383                        copy(dest+n1, pBuf->buf, n2);
384                        priv_read_ptr = n2;
385                    }
386    
387                    this->read_ptr = priv_read_ptr;
388                    return to_read;
389                }
390    
391                /**
392                 * Finally when the read data is not needed anymore, this method
393                 * should be called to free the data in the RingBuffer up to the
394                 * current read position of this NonVolatileReader.
395                 *
396                 * @see RingBuffer::increment_read_ptr()
397                 */
398                void free() {
399                    pBuf->read_ptr.store(read_ptr, memory_order_release);
400                }
401    
402            protected:
403                _NonVolatileReader(RingBuffer<T1,T1_DEEP_COPY>* pBuf) {
404                    this->pBuf     = pBuf;
405                    this->read_ptr = pBuf->read_ptr.load(memory_order_relaxed);
406                }
407    
408                RingBuffer<T1,T1_DEEP_COPY>* pBuf;
409                int read_ptr;
410    
411                friend class RingBuffer<T1,T1_DEEP_COPY>;
412        };
413    
414        typedef _NonVolatileReader<T,T_DEEP_COPY> NonVolatileReader;
415    
416        NonVolatileReader get_non_volatile_reader() { return NonVolatileReader(this); }
417    
418    protected:    protected:
419      T *buf;      T *buf;
420      atomic_t write_ptr;      atomic<int> write_ptr;
421      atomic_t read_ptr;      atomic<int> read_ptr;
422      int size_mask;      int size_mask;
423    
424        /**
425         * Copies \a n amount of elements from the buffer given by
426         * \a pSrc to the buffer given by \a pDst.
427         */
428        inline static void copy(T* pDst, T* pSrc, int n);
429    
430        friend class _NonVolatileReader<T,T_DEEP_COPY>;
431  };  };
432    
433  template<class T> T *  template<class T, bool T_DEEP_COPY>
434  RingBuffer<T>::get_write_ptr (void) {  T* RingBuffer<T,T_DEEP_COPY>::get_write_ptr (void) {
435    return(&buf[atomic_read(&write_ptr)]);    return(&buf[write_ptr.load(memory_order_relaxed)]);
436  }  }
437    
438  template<class T> T *  template<class T, bool T_DEEP_COPY>
439  RingBuffer<T>::get_buffer_begin (void) {  T* RingBuffer<T,T_DEEP_COPY>::get_buffer_begin (void) {
440    return(buf);    return(buf);
441  }  }
442    
443    
444    
445  template<class T> int  template<class T, bool T_DEEP_COPY>
446  RingBuffer<T>::read (T *dest, int cnt)  int RingBuffer<T,T_DEEP_COPY>::read(T* dest, int cnt)
   
447  {  {
448          int free_cnt;          int free_cnt;
449          int cnt2;          int cnt2;
# Line 278  RingBuffer<T>::read (T *dest, int cnt) Line 451  RingBuffer<T>::read (T *dest, int cnt)
451          int n1, n2;          int n1, n2;
452          int priv_read_ptr;          int priv_read_ptr;
453    
454          priv_read_ptr=atomic_read(&read_ptr);          priv_read_ptr = read_ptr.load(memory_order_relaxed);
455    
456          if ((free_cnt = read_space ()) == 0) {          if ((free_cnt = read_space ()) == 0) {
457                  return 0;                  return 0;
# Line 296  RingBuffer<T>::read (T *dest, int cnt) Line 469  RingBuffer<T>::read (T *dest, int cnt)
469                  n2 = 0;                  n2 = 0;
470          }          }
471    
472          memcpy (dest, &buf[priv_read_ptr], n1 * sizeof (T));          copy(dest, &buf[priv_read_ptr], n1);
473          priv_read_ptr = (priv_read_ptr + n1) & size_mask;          priv_read_ptr = (priv_read_ptr + n1) & size_mask;
474    
475          if (n2) {          if (n2) {
476                  memcpy (dest+n1, buf, n2 * sizeof (T));                  copy(dest+n1, buf, n2);
477                  priv_read_ptr = n2;                  priv_read_ptr = n2;
478          }          }
479    
480          atomic_set(&read_ptr, priv_read_ptr);          read_ptr.store(priv_read_ptr, memory_order_release);
481          return to_read;          return to_read;
482  }  }
483    
484  template<class T> int  template<class T, bool T_DEEP_COPY>
485  RingBuffer<T>::write (T *src, int cnt)  int RingBuffer<T,T_DEEP_COPY>::write(T* src, int cnt)
   
486  {  {
487          int free_cnt;          int free_cnt;
488          int cnt2;          int cnt2;
# Line 318  RingBuffer<T>::write (T *src, int cnt) Line 490  RingBuffer<T>::write (T *src, int cnt)
490          int n1, n2;          int n1, n2;
491          int priv_write_ptr;          int priv_write_ptr;
492    
493          priv_write_ptr=atomic_read(&write_ptr);          priv_write_ptr = write_ptr.load(memory_order_relaxed);
494    
495          if ((free_cnt = write_space ()) == 0) {          if ((free_cnt = write_space ()) == 0) {
496                  return 0;                  return 0;
# Line 336  RingBuffer<T>::write (T *src, int cnt) Line 508  RingBuffer<T>::write (T *src, int cnt)
508                  n2 = 0;                  n2 = 0;
509          }          }
510    
511          memcpy (&buf[priv_write_ptr], src, n1 * sizeof (T));          copy(&buf[priv_write_ptr], src, n1);
512          priv_write_ptr = (priv_write_ptr + n1) & size_mask;          priv_write_ptr = (priv_write_ptr + n1) & size_mask;
513    
514          if (n2) {          if (n2) {
515                  memcpy (buf, src+n1, n2 * sizeof (T));                  copy(buf, src+n1, n2);
516                  priv_write_ptr = n2;                  priv_write_ptr = n2;
517          }          }
518          atomic_set(&write_ptr, priv_write_ptr);          write_ptr.store(priv_write_ptr, memory_order_release);
519          return to_write;          return to_write;
520  }  }
521    
522    template<class T, bool T_DEEP_COPY>
523    void RingBuffer<T,T_DEEP_COPY>::copy(T* pDst, T* pSrc, int n) {
524        if (T_DEEP_COPY) { // deep copy - won't work for data structures without assignment operator implementation
525            for (int i = 0; i < n; i++) pDst[i] = pSrc[i];
526        } else { // flat copy - won't work for complex data structures !
527            memcpy(pDst, pSrc, n * sizeof(T));
528        }
529    }
530    
531  #endif /* RINGBUFFER_H */  #endif /* RINGBUFFER_H */
Legend:
Removed from v.56  
changed lines
  Added in v.1790
  ViewVC Help
Powered by ViewVC