Embedded Template Library 1.0
queue_spsc_atomic.h
Go to the documentation of this file.
1
2
3/******************************************************************************
4The MIT License(MIT)
5
6Embedded Template Library.
7https://github.com/ETLCPP/etl
8https://www.etlcpp.com
9
10Copyright(c) 2018 John Wellbelove
11
12Permission is hereby granted, free of charge, to any person obtaining a copy
13of this software and associated documentation files(the "Software"), to deal
14in the Software without restriction, including without limitation the rights
15to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
16copies of the Software, and to permit persons to whom the Software is
17furnished to do so, subject to the following conditions :
18
19The above copyright notice and this permission notice shall be included in all
20copies or substantial portions of the Software.
21
22THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
23IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
24FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
25AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
26LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
27OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
28SOFTWARE.
29******************************************************************************/
30
31#ifndef ETL_SPSC_QUEUE_ATOMIC_INCLUDED
32#define ETL_SPSC_QUEUE_ATOMIC_INCLUDED
33
34#include "platform.h"
35#include "alignment.h"
36#include "parameter_type.h"
37#include "atomic.h"
38#include "memory_model.h"
39#include "integral_limits.h"
40#include "utility.h"
41#include "placement_new.h"
42
43#include <stddef.h>
44#include <stdint.h>
45
46#if ETL_HAS_ATOMIC
47
48namespace etl
49{
50 template <size_t MEMORY_MODEL = etl::memory_model::MEMORY_MODEL_LARGE>
51 class queue_spsc_atomic_base
52 {
53 public:
54
56 typedef typename etl::size_type_lookup<MEMORY_MODEL>::type size_type;
57
58 //*************************************************************************
62 //*************************************************************************
63 bool empty() const
64 {
65 return read.load(etl::memory_order_acquire) == write.load(etl::memory_order_acquire);
66 }
67
68 //*************************************************************************
72 //*************************************************************************
73 bool full() const
74 {
75 size_type next_index = get_next_index(write.load(etl::memory_order_acquire), RESERVED);
76
77 return (next_index == read.load(etl::memory_order_acquire));
78 }
79
80 //*************************************************************************
83 //*************************************************************************
84 size_type size() const
85 {
86 size_type write_index = write.load(etl::memory_order_acquire);
87 size_type read_index = read.load(etl::memory_order_acquire);
88
89 size_type n;
90
91 if (write_index >= read_index)
92 {
93 n = write_index - read_index;
94 }
95 else
96 {
97 n = RESERVED - read_index + write_index;
98 }
99
100 return n;
101 }
102
103 //*************************************************************************
106 //*************************************************************************
107 size_type available() const
108 {
109 return RESERVED - size() - 1;
110 }
111
112 //*************************************************************************
114 //*************************************************************************
115 size_type capacity() const
116 {
117 return RESERVED - 1;
118 }
119
120 //*************************************************************************
122 //*************************************************************************
123 size_type max_size() const
124 {
125 return RESERVED - 1;
126 }
127
128 protected:
129
130 queue_spsc_atomic_base(size_type reserved_)
131 : write(0),
132 read(0),
133 RESERVED(reserved_)
134 {
135 }
136
137 //*************************************************************************
139 //*************************************************************************
140 static size_type get_next_index(size_type index, size_type maximum)
141 {
142 ++index;
143
144 if (index == maximum) ETL_UNLIKELY
145 {
146 index = 0;
147 }
148
149 return index;
150 }
151
152 etl::atomic<size_type> write;
153 etl::atomic<size_type> read;
154 const size_type RESERVED;
155
156 private:
157
158 //*************************************************************************
160 //*************************************************************************
161#if defined(ETL_POLYMORPHIC_SPSC_QUEUE_ATOMIC) || defined(ETL_POLYMORPHIC_CONTAINERS)
162 public:
163 virtual ~queue_spsc_atomic_base()
164 {
165 }
166#else
167 protected:
168 ~queue_spsc_atomic_base()
169 {
170 }
171#endif
172 };
173
174 //***************************************************************************
184 //***************************************************************************
185 template <typename T, const size_t MEMORY_MODEL = etl::memory_model::MEMORY_MODEL_LARGE>
186 class iqueue_spsc_atomic : public queue_spsc_atomic_base<MEMORY_MODEL>
187 {
188 private:
189
190 typedef typename etl::queue_spsc_atomic_base<MEMORY_MODEL> base_t;
191
192 public:
193
194 typedef T value_type;
195 typedef T& reference;
196 typedef const T& const_reference;
197#if ETL_USING_CPP11
198 typedef T&& rvalue_reference;
199#endif
200 typedef typename base_t::size_type size_type;
201
202 using base_t::write;
203 using base_t::read;
204 using base_t::RESERVED;
205 using base_t::get_next_index;
206
207 //*************************************************************************
209 //*************************************************************************
210 bool push(const_reference value)
211 {
212 size_type write_index = write.load(etl::memory_order_relaxed);
213 size_type next_index = get_next_index(write_index, RESERVED);
214
215 if (next_index != read.load(etl::memory_order_acquire))
216 {
217 ::new (&p_buffer[write_index]) T(value);
218
219 write.store(next_index, etl::memory_order_release);
220
221 return true;
222 }
223
224 // Queue is full.
225 return false;
226 }
227
228#if ETL_USING_CPP11 && ETL_NOT_USING_STLPORT && !defined(ETL_QUEUE_ATOMIC_FORCE_CPP03_IMPLEMENTATION)
229 //*************************************************************************
231 //*************************************************************************
232 bool push(rvalue_reference value)
233 {
234 size_type write_index = write.load(etl::memory_order_relaxed);
235 size_type next_index = get_next_index(write_index, RESERVED);
236
237 if (next_index != read.load(etl::memory_order_acquire))
238 {
239 ::new (&p_buffer[write_index]) T(etl::move(value));
240
241 write.store(next_index, etl::memory_order_release);
242
243 return true;
244 }
245
246 // Queue is full.
247 return false;
248 }
249#endif
250
251#if ETL_USING_CPP11 && ETL_NOT_USING_STLPORT && !defined(ETL_QUEUE_ATOMIC_FORCE_CPP03_IMPLEMENTATION)
252 //*************************************************************************
255 //*************************************************************************
256 template <typename ... Args>
257 bool emplace(Args&&... args)
258 {
259 size_type write_index = write.load(etl::memory_order_relaxed);
260 size_type next_index = get_next_index(write_index, RESERVED);
261
262 if (next_index != read.load(etl::memory_order_acquire))
263 {
264 ::new (&p_buffer[write_index]) T(etl::forward<Args>(args)...);
265
266 write.store(next_index, etl::memory_order_release);
267
268 return true;
269 }
270
271 // Queue is full.
272 return false;
273 }
274#else
275 //*************************************************************************
278 //*************************************************************************
279 template <typename T1>
280 bool emplace(const T1& value1)
281 {
282 size_type write_index = write.load(etl::memory_order_relaxed);
283 size_type next_index = get_next_index(write_index, RESERVED);
284
285 if (next_index != read.load(etl::memory_order_acquire))
286 {
287 ::new (&p_buffer[write_index]) T(value1);
288
289 write.store(next_index, etl::memory_order_release);
290
291 return true;
292 }
293
294 // Queue is full.
295 return false;
296 }
297
298 //*************************************************************************
301 //*************************************************************************
302 template <typename T1, typename T2>
303 bool emplace(const T1& value1, const T2& value2)
304 {
305 size_type write_index = write.load(etl::memory_order_relaxed);
306 size_type next_index = get_next_index(write_index, RESERVED);
307
308 if (next_index != read.load(etl::memory_order_acquire))
309 {
310 ::new (&p_buffer[write_index]) T(value1, value2);
311
312 write.store(next_index, etl::memory_order_release);
313
314 return true;
315 }
316
317 // Queue is full.
318 return false;
319 }
320
321 //*************************************************************************
324 //*************************************************************************
325 template <typename T1, typename T2, typename T3>
326 bool emplace(const T1& value1, const T2& value2, const T3& value3)
327 {
328 size_type write_index = write.load(etl::memory_order_relaxed);
329 size_type next_index = get_next_index(write_index, RESERVED);
330
331 if (next_index != read.load(etl::memory_order_acquire))
332 {
333 ::new (&p_buffer[write_index]) T(value1, value2, value3);
334
335 write.store(next_index, etl::memory_order_release);
336
337 return true;
338 }
339
340 // Queue is full.
341 return false;
342 }
343
344 //*************************************************************************
347 //*************************************************************************
348 template <typename T1, typename T2, typename T3, typename T4>
349 bool emplace(const T1& value1, const T2& value2, const T3& value3, const T4& value4)
350 {
351 size_type write_index = write.load(etl::memory_order_relaxed);
352 size_type next_index = get_next_index(write_index, RESERVED);
353
354 if (next_index != read.load(etl::memory_order_acquire))
355 {
356 ::new (&p_buffer[write_index]) T(value1, value2, value3, value4);
357
358 write.store(next_index, etl::memory_order_release);
359
360 return true;
361 }
362
363 // Queue is full.
364 return false;
365 }
366#endif
367
368 //*************************************************************************
370 //*************************************************************************
371 bool front(reference value)
372 {
373 size_type read_index = read.load(etl::memory_order_relaxed);
374
375 if (read_index == write.load(etl::memory_order_acquire))
376 {
377 // Queue is empty
378 return false;
379 }
380
381 value = p_buffer[read_index];
382
383 return true;
384 }
385
386 //*************************************************************************
388 //*************************************************************************
389 bool pop(reference value)
390 {
391 size_type read_index = read.load(etl::memory_order_relaxed);
392
393 if (read_index == write.load(etl::memory_order_acquire))
394 {
395 // Queue is empty
396 return false;
397 }
398
399 size_type next_index = get_next_index(read_index, RESERVED);
400
401#if ETL_USING_CPP11 && ETL_NOT_USING_STLPORT && !defined(ETL_QUEUE_LOCKABLE_FORCE_CPP03_IMPLEMENTATION)
402 value = etl::move(p_buffer[read_index]);
403#else
404 value = p_buffer[read_index];
405#endif
406
407 p_buffer[read_index].~T();
408
409 read.store(next_index, etl::memory_order_release);
410
411 return true;
412 }
413
414 //*************************************************************************
416 //*************************************************************************
417 bool pop()
418 {
419 size_type read_index = read.load(etl::memory_order_relaxed);
420
421 if (read_index == write.load(etl::memory_order_acquire))
422 {
423 // Queue is empty
424 return false;
425 }
426
427 size_type next_index = get_next_index(read_index, RESERVED);
428
429 p_buffer[read_index].~T();
430
431 read.store(next_index, etl::memory_order_release);
432
433 return true;
434 }
435
436 //*************************************************************************
438 //*************************************************************************
439 reference front()
440 {
441 size_type read_index = read.load(etl::memory_order_relaxed);
442
443 return p_buffer[read_index];
444 }
445
446 //*************************************************************************
448 //*************************************************************************
449 const_reference front() const
450 {
451 size_type read_index = read.load(etl::memory_order_relaxed);
452
453 return p_buffer[read_index];
454 }
455
456 //*************************************************************************
460 //*************************************************************************
461 void clear()
462 {
463 while (pop())
464 {
465 // Do nothing.
466 }
467 }
468
469 protected:
470
471 //*************************************************************************
473 //*************************************************************************
474 iqueue_spsc_atomic(T* p_buffer_, size_type reserved_)
475 : base_t(reserved_),
476 p_buffer(p_buffer_)
477 {
478 }
479
480 private:
481
482 // Disable copy construction and assignment.
483 iqueue_spsc_atomic(const iqueue_spsc_atomic&) ETL_DELETE;
484 iqueue_spsc_atomic& operator =(const iqueue_spsc_atomic&) ETL_DELETE;
485
486#if ETL_USING_CPP11
487 iqueue_spsc_atomic(iqueue_spsc_atomic&&) = delete;
488 iqueue_spsc_atomic& operator =(iqueue_spsc_atomic&&) = delete;
489#endif
490
491 T* p_buffer;
492 };
493
494 //***************************************************************************
501 //***************************************************************************
502 template <typename T, size_t SIZE, const size_t MEMORY_MODEL = etl::memory_model::MEMORY_MODEL_LARGE>
503 class queue_spsc_atomic : public iqueue_spsc_atomic<T, MEMORY_MODEL>
504 {
505 private:
506
507 typedef typename etl::iqueue_spsc_atomic<T, MEMORY_MODEL> base_t;
508
509 public:
510
511 typedef typename base_t::size_type size_type;
512
513 private:
514
515 static ETL_CONSTANT size_type RESERVED_SIZE = size_type(SIZE + 1);
516
517 public:
518
519 ETL_STATIC_ASSERT((SIZE <= (etl::integral_limits<size_type>::max - 1)), "Size too large for memory model");
520
521 static ETL_CONSTANT size_type MAX_SIZE = size_type(SIZE);
522
523 //*************************************************************************
525 //*************************************************************************
526 queue_spsc_atomic()
527 : base_t(reinterpret_cast<T*>(&buffer[0]), RESERVED_SIZE)
528 {
529 }
530
531 //*************************************************************************
533 //*************************************************************************
534 ~queue_spsc_atomic()
535 {
536 base_t::clear();
537 }
538
539 private:
540
542 typename etl::aligned_storage<sizeof(T), etl::alignment_of<T>::value>::type buffer[RESERVED_SIZE];
543 };
544
545 template <typename T, size_t SIZE, const size_t MEMORY_MODEL>
546 ETL_CONSTANT typename queue_spsc_atomic<T, SIZE, MEMORY_MODEL>::size_type queue_spsc_atomic<T, SIZE, MEMORY_MODEL>::MAX_SIZE;
547}
548
549#endif
550
551#endif
Definition: alignment.h:221
Definition: integral_limits.h:468
add_rvalue_reference
Definition: type_traits_generator.h:1327
bitset_ext
Definition: absolute.h:38
size_t max_size() const
Returns the maximum number of items in the variant_pool.
Definition: variant_pool_generator.h:281
etl::optional< T > read(etl::bit_stream_reader &stream)
Read a checked type from a stream.
Definition: bit_stream.h:1348
bool write(etl::bit_stream_writer &stream, bool value)
Definition: bit_stream.h:992
Definition: memory_model.h:50