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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2386 - (hide annotations) (download) (as text)
Tue Dec 18 18:29:55 2012 UTC (8 years, 3 months ago) by schoenebeck
File MIME type: text/x-c++hdr
File size: 21780 byte(s)
- "RingBuffer" class: implemented += operator for NonVolatileReader

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

  ViewVC Help
Powered by ViewVC