RAUL  0.5.1
SRMWQueue.hpp
1 /* This file is part of Raul.
2  * Copyright (C) 2007 Dave Robillard <http://drobilla.net>
3  *
4  * Raul is free software; you can redistribute it and/or modify it under the
5  * terms of the GNU General Public License as published by the Free Software
6  * Foundation; either version 2 of the License, or (at your option) any later
7  * version.
8  *
9  * Raul is distributed in the hope that it will be useful, but WITHOUT ANY
10  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
11  * FOR A PARTICULAR PURPOSE. See the GNU General Public License for details.
12  *
13  * You should have received a copy of the GNU General Public License along
14  * with this program; if not, write to the Free Software Foundation, Inc.,
15  * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
16  */
17 
18 #ifndef RAUL_SRMW_QUEUE_HPP
19 #define RAUL_SRMW_QUEUE_HPP
20 
21 #include <cassert>
22 #include <cstdlib>
23 #include <cmath>
24 #include <boost/utility.hpp>
25 #include <raul/AtomicInt.hpp>
26 
27 #include <iostream>
28 using namespace std;
29 
30 namespace Raul {
31 
32 
54 template <typename T>
55 class SRMWQueue : boost::noncopyable
56 {
57 public:
58  SRMWQueue(size_t size);
59  ~SRMWQueue();
60 
61 
62  // Any thread:
63 
64  inline size_t capacity() const { return _size-1; }
65 
66 
67  // Write thread(s):
68 
69  inline bool full() const;
70  inline bool push(const T& obj);
71 
72 
73  // Read thread:
74 
75  inline bool empty() const;
76  inline T& front() const;
77  inline void pop();
78 
79 private:
80 
81  // Note that _front doesn't need to be an AtomicInt since it's only accessed
82  // by the (single) reader thread
83 
84  unsigned _front;
85  AtomicInt _back;
86  AtomicInt _write_space;
87  const unsigned _size;
88 
89  T* const _objects;
90  AtomicInt* const _valid;
91 };
92 
93 
94 template<typename T>
95 SRMWQueue<T>::SRMWQueue(size_t size)
96  : _front(0)
97  , _back(0)
98  , _write_space(size)
99  , _size(size+1)
100  , _objects((T*)calloc(_size, sizeof(T)))
101  , _valid((AtomicInt*)calloc(_size, sizeof(AtomicInt)))
102 {
103  assert(log2(size) - (int)log2(size) == 0);
104  assert(size > 1);
105  assert(_size-1 == (unsigned)_write_space.get());
106 
107  for (unsigned i=0; i < _size; ++i) {
108  assert(_valid[i].get() == 0);
109  }
110 }
111 
112 
113 template <typename T>
114 SRMWQueue<T>::~SRMWQueue()
115 {
116  free(_objects);
117 }
118 
119 
124 template <typename T>
125 inline bool
127 {
128  return (_write_space.get() <= 0);
129 }
130 
131 
139 template <typename T>
140 inline bool
141 SRMWQueue<T>::push(const T& elem)
142 {
143  const int old_write_space = _write_space.exchange_and_add(-1);
144  const bool already_full = ( old_write_space <= 0 );
145 
146  /* Technically right here pop could be called in the reader thread and
147  * make space available, but no harm in failing anyway - this queue
148  * really isn't designed to be filled... */
149 
150  if (already_full) {
151 
152  /* if multiple threads simultaneously get here, _write_space may be 0
153  * or negative. The next call to pop() will set _write_space back to
154  * a sane value. Note that _write_space is not exposed, so this is okay
155  * (... assuming this code is correct) */
156 
157  return false;
158 
159  } else {
160 
161  // Note: _size must be a power of 2 for this to not explode when _back overflows
162  const unsigned write_index = (unsigned)_back.exchange_and_add(1) % _size;
163 
164  assert(_valid[write_index] == 0);
165  _objects[write_index] = elem;
166  ++(_valid[write_index]);
167 
168  return true;
169 
170  }
171 }
172 
173 
178 template <typename T>
179 inline bool
181 {
182  return (_valid[_front].get() == 0);
183 }
184 
185 
191 template <typename T>
192 inline T&
194 {
195  return _objects[_front];
196 }
197 
198 
206 template <typename T>
207 inline void
209 {
210  assert(_valid[_front] == 1);
211  --(_valid[_front]);
212 
213  _front = (_front + 1) % (_size);
214 
215  if (_write_space.get() < 0)
216  _write_space = 1;
217  else
218  ++_write_space;
219 }
220 
221 
222 } // namespace Raul
223 
224 #endif // RAUL_SRMW_QUEUE_HPP
Realtime-safe single-reader multi-writer queue (aka lock-free ringbuffer)
Definition: SRMWQueue.hpp:55
bool push(const T &obj)
Push an item onto the back of the SRMWQueue - realtime-safe, not thread-safe.
Definition: SRMWQueue.hpp:141
bool empty() const
Return whether the queue is empty.
Definition: SRMWQueue.hpp:180
void pop()
Pop an item off the front of the queue - realtime-safe, NOT thread-safe.
Definition: SRMWQueue.hpp:208
Definition: Array.hpp:26
T & front() const
Return the element at the front of the queue without removing it.
Definition: SRMWQueue.hpp:193
bool full() const
Return whether the queue is full.
Definition: SRMWQueue.hpp:126