RAUL  0.8.0
SRMWQueue.hpp
1 /* This file is part of Raul.
2  * Copyright (C) 2007-2009 David 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 
25 #include <boost/utility.hpp>
26 
27 #include "raul/AtomicInt.hpp"
28 
29 namespace Raul {
30 
31 
53 template <typename T>
54 class SRMWQueue : boost::noncopyable
55 {
56 public:
57  explicit SRMWQueue(size_t size);
58  ~SRMWQueue();
59 
60 
61  // Any thread:
62 
63  inline size_t capacity() const { return _size-1; }
64 
65 
66  // Write thread(s):
67 
68  inline bool full() const;
69  inline bool push(const T& obj);
70 
71 
72  // Read thread:
73 
74  inline bool empty() const;
75  inline T& front() const;
76  inline void pop();
77 
78 private:
79 
80  // Note that _front doesn't need to be an AtomicInt since it's only accessed
81  // by the (single) reader thread
82 
83  unsigned _front;
84  AtomicInt _back;
85  AtomicInt _write_space;
86  const unsigned _size;
87 
88  T* const _objects;
89  AtomicInt* const _valid;
90 };
91 
92 
93 template<typename T>
94 SRMWQueue<T>::SRMWQueue(size_t size)
95  : _front(0)
96  , _back(0)
97  , _write_space(size)
98  , _size(size+1)
99  , _objects((T*)calloc(_size, sizeof(T)))
100  , _valid((AtomicInt*)calloc(_size, sizeof(AtomicInt)))
101 {
102  assert(log2(size) - (int)log2(size) == 0);
103  assert(size > 1);
104  assert(_size-1 == (unsigned)_write_space.get());
105 
106  for (unsigned i=0; i < _size; ++i) {
107  assert(_valid[i].get() == 0);
108  }
109 }
110 
111 
112 template <typename T>
114 {
115  free(_objects);
116 }
117 
118 
123 template <typename T>
124 inline bool
126 {
127  return (_write_space.get() <= 0);
128 }
129 
130 
138 template <typename T>
139 inline bool
140 SRMWQueue<T>::push(const T& elem)
141 {
142  const int old_write_space = _write_space.exchange_and_add(-1);
143  const bool already_full = ( old_write_space <= 0 );
144 
145  /* Technically right here pop could be called in the reader thread and
146  * make space available, but no harm in failing anyway - this queue
147  * really isn't designed to be filled... */
148 
149  if (already_full) {
150 
151  /* if multiple threads simultaneously get here, _write_space may be 0
152  * or negative. The next call to pop() will set _write_space back to
153  * a sane value. Note that _write_space is not exposed, so this is okay
154  * (... assuming this code is correct) */
155 
156  return false;
157 
158  } else {
159 
160  // Note: _size must be a power of 2 for this to not explode when _back overflows
161  const unsigned write_index = (unsigned)_back.exchange_and_add(1) % _size;
162 
163  assert(_valid[write_index] == 0);
164  _objects[write_index] = elem;
165  ++(_valid[write_index]);
166 
167  return true;
168 
169  }
170 }
171 
172 
177 template <typename T>
178 inline bool
180 {
181  return (_valid[_front].get() == 0);
182 }
183 
184 
190 template <typename T>
191 inline T&
193 {
194  return _objects[_front];
195 }
196 
197 
205 template <typename T>
206 inline void
208 {
209  assert(_valid[_front] == 1);
210  --(_valid[_front]);
211 
212  _front = (_front + 1) % (_size);
213 
214  if (_write_space.get() < 0)
215  _write_space = 1;
216  else
217  ++_write_space;
218 }
219 
220 
221 } // namespace Raul
222 
223 #endif // RAUL_SRMW_QUEUE_HPP
Realtime-safe single-reader multi-writer queue (aka lock-free ringbuffer)
Definition: SRMWQueue.hpp:54
bool full() const
Return whether the queue is full.
Definition: SRMWQueue.hpp:125
bool empty() const
Return whether the queue is empty.
Definition: SRMWQueue.hpp:179
bool push(const T &obj)
Push an item onto the back of the SRMWQueue - realtime-safe, not thread-safe.
Definition: SRMWQueue.hpp:140
void pop()
Pop an item off the front of the queue - realtime-safe, NOT thread-safe.
Definition: SRMWQueue.hpp:207
T & front() const
Return the element at the front of the queue without removing it.
Definition: SRMWQueue.hpp:192
Definition: Array.hpp:26
Atomic integer.
Definition: AtomicInt.hpp:29
int exchange_and_add(int val)
Add val to value.
Definition: AtomicInt.hpp:70