Embedded Template Library 1.0
queue.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) 2014 John Wellbelove, Mark Kitson
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_QUEUE_INCLUDED
32#define ETL_QUEUE_INCLUDED
33
34#include "platform.h"
35#include "iterator.h"
36#include "alignment.h"
37#include "array.h"
38#include "exception.h"
39#include "error_handler.h"
40#include "debug_count.h"
41#include "type_traits.h"
42#include "parameter_type.h"
43#include "memory_model.h"
44#include "integral_limits.h"
45#include "utility.h"
46#include "placement_new.h"
47
48#include <stddef.h>
49#include <stdint.h>
50
51//*****************************************************************************
56//*****************************************************************************
57
58namespace etl
59{
60 //***************************************************************************
63 //***************************************************************************
65 {
66 public:
67
68 queue_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
69 : exception(reason_, file_name_, line_number_)
70 {
71 }
72 };
73
74 //***************************************************************************
77 //***************************************************************************
79 {
80 public:
81
82 queue_full(string_type file_name_, numeric_type line_number_)
83 : queue_exception(ETL_ERROR_TEXT("queue:full", ETL_QUEUE_FILE_ID"A"), file_name_, line_number_)
84 {
85 }
86 };
87
88 //***************************************************************************
91 //***************************************************************************
93 {
94 public:
95
96 queue_empty(string_type file_name_, numeric_type line_number_)
97 : queue_exception(ETL_ERROR_TEXT("queue:empty", ETL_QUEUE_FILE_ID"B"), file_name_, line_number_)
98 {
99 }
100 };
101
102 //***************************************************************************
105 //***************************************************************************
106 template <size_t MEMORY_MODEL = etl::memory_model::MEMORY_MODEL_LARGE>
108 {
109 public:
110
113
114 //*************************************************************************
116 //*************************************************************************
118 {
119 return current_size;
120 }
121
122 //*************************************************************************
124 //*************************************************************************
126 {
127 return CAPACITY;
128 }
129
130 //*************************************************************************
132 //*************************************************************************
134 {
135 return CAPACITY;
136 }
137
138 //*************************************************************************
141 //*************************************************************************
142 bool empty() const
143 {
144 return current_size == 0;
145 }
146
147 //*************************************************************************
150 //*************************************************************************
151 bool full() const
152 {
153 return current_size == CAPACITY;
154 }
155
156 //*************************************************************************
159 //*************************************************************************
161 {
162 return max_size() - size();
163 }
164
165 protected:
166
167 //*************************************************************************
169 //*************************************************************************
171 : in(0),
172 out(0),
173 current_size(0),
174 CAPACITY(max_size_)
175 {
176 }
177
178 //*************************************************************************
180 //*************************************************************************
182 {
183 }
184
185 //*************************************************************************
187 //*************************************************************************
188 void add_in()
189 {
190 if (++in == CAPACITY) ETL_UNLIKELY
191 {
192 in = 0;
193 }
194
195 ++current_size;
196 ETL_INCREMENT_DEBUG_COUNT
197 }
198
199 //*************************************************************************
201 //*************************************************************************
202 void del_out()
203 {
204 if (++out == CAPACITY) ETL_UNLIKELY
205 {
206 out = 0;
207 }
208 --current_size;
209 ETL_DECREMENT_DEBUG_COUNT
210 }
211
212 //*************************************************************************
214 //*************************************************************************
216 {
217 in = 0;
218 out = 0;
219 current_size = 0;
220 ETL_RESET_DEBUG_COUNT
221 }
222
227 ETL_DECLARE_DEBUG_COUNT
228
229 };
230
231 //***************************************************************************
241 //***************************************************************************
242 template <typename T, const size_t MEMORY_MODEL = etl::memory_model::MEMORY_MODEL_LARGE>
243 class iqueue : public etl::queue_base<MEMORY_MODEL>
244 {
245 private:
246
247 typedef typename etl::queue_base<MEMORY_MODEL> base_t;
248
249 public:
250
251 typedef T value_type;
252 typedef T& reference;
253 typedef const T& const_reference;
254#if ETL_USING_CPP11
255 typedef T&& rvalue_reference;
256#endif
257 typedef T* pointer;
258 typedef const T* const_pointer;
259 typedef typename base_t::size_type size_type;
260
261 using base_t::in;
262 using base_t::out;
263 using base_t::CAPACITY;
265 using base_t::full;
266 using base_t::empty;
267 using base_t::add_in;
268 using base_t::del_out;
269
270 //*************************************************************************
273 //*************************************************************************
275 {
276 return p_buffer[out];
277 }
278
279 //*************************************************************************
282 //*************************************************************************
284 {
285 return p_buffer[out];
286 }
287
288 //*************************************************************************
291 //*************************************************************************
293 {
294 return p_buffer[in == 0 ? CAPACITY - 1 : in - 1];
295 }
296
297 //*************************************************************************
300 //*************************************************************************
302 {
303 return p_buffer[in == 0 ? CAPACITY - 1 : in - 1];
304 }
305
306 //*************************************************************************
310 //*************************************************************************
312 {
313#if defined(ETL_CHECK_PUSH_POP)
314 ETL_ASSERT(!full(), ETL_ERROR(queue_full));
315#endif
316 ::new (&p_buffer[in]) T(value);
317 add_in();
318 }
319
320#if ETL_USING_CPP11
321 //*************************************************************************
325 //*************************************************************************
326 void push(rvalue_reference value)
327 {
328#if defined(ETL_CHECK_PUSH_POP)
329 ETL_ASSERT(!full(), ETL_ERROR(queue_full));
330#endif
331 ::new (&p_buffer[in]) T(etl::move(value));
332 add_in();
333 }
334#endif
335
336#if ETL_USING_CPP11 && ETL_NOT_USING_STLPORT && !defined(ETL_QUEUE_FORCE_CPP03_IMPLEMENTATION)
337 //*************************************************************************
341 //*************************************************************************
342 template <typename ... Args>
343 void emplace(Args && ... args)
344 {
345#if defined(ETL_CHECK_PUSH_POP)
346 ETL_ASSERT(!full(), ETL_ERROR(queue_full));
347#endif
348 ::new (&p_buffer[in]) T(etl::forward<Args>(args)...);
349 add_in();
350 }
351#else
352 //*************************************************************************
356 //*************************************************************************
357 template <typename T1>
358 void emplace(const T1& value1)
359 {
360#if defined(ETL_CHECK_PUSH_POP)
361 ETL_ASSERT(!full(), ETL_ERROR(queue_full));
362#endif
363 ::new (&p_buffer[in]) T(value1);
364 add_in();
365 }
366
367 //*************************************************************************
371 //*************************************************************************
372 template <typename T1, typename T2>
373 void emplace(const T1& value1, const T2& value2)
374 {
375#if defined(ETL_CHECK_PUSH_POP)
376 ETL_ASSERT(!full(), ETL_ERROR(queue_full));
377#endif
378 ::new (&p_buffer[in]) T(value1, value2);
379 add_in();
380 }
381
382 //*************************************************************************
386 //*************************************************************************
387 template <typename T1, typename T2, typename T3>
388 void emplace(const T1& value1, const T2& value2, const T3& value3)
389 {
390#if defined(ETL_CHECK_PUSH_POP)
391 ETL_ASSERT(!full(), ETL_ERROR(queue_full));
392#endif
393 ::new (&p_buffer[in]) T(value1, value2, value3);
394 add_in();
395 }
396
397 //*************************************************************************
401 //*************************************************************************
402 template <typename T1, typename T2, typename T3, typename T4>
403 void emplace(const T1& value1, const T2& value2, const T3& value3, const T4& value4)
404 {
405#if defined(ETL_CHECK_PUSH_POP)
406 ETL_ASSERT(!full(), ETL_ERROR(queue_full));
407#endif
408 ::new (&p_buffer[in]) T(value1, value2, value3, value4);
409 add_in();
410 }
411#endif
412
413 //*************************************************************************
415 //*************************************************************************
416 void clear()
417 {
419 {
421 }
422 else
423 {
424 while (current_size > 0)
425 {
426 p_buffer[out].~T();
427 del_out();
428 }
429
430 in = 0;
431 out = 0;
432 }
433 }
434
435 //*************************************************************************
439 //*************************************************************************
440 void pop()
441 {
442#if defined(ETL_CHECK_PUSH_POP)
443 ETL_ASSERT(!empty(), ETL_ERROR(queue_empty));
444#endif
445 p_buffer[out].~T();
446 del_out();
447 }
448
449 //*************************************************************************
452 //*************************************************************************
453 void pop_into(reference destination)
454 {
455 destination = ETL_MOVE(front());
456 pop();
457 }
458
459 //*************************************************************************
464 //*************************************************************************
465 template <typename TContainer>
466 void pop_into(TContainer& destination)
467 {
468 destination.push(ETL_MOVE(front()));
469 pop();
470 }
471
472 //*************************************************************************
474 //*************************************************************************
476 {
477 if (&rhs != this)
478 {
479 clear();
480 clone(rhs);
481 }
482
483 return *this;
484 }
485
486#if ETL_USING_CPP11
487 //*************************************************************************
489 //*************************************************************************
491 {
492 if (&rhs != this)
493 {
494 clear();
495 move_clone(rhs);
496 }
497
498 return *this;
499 }
500#endif
501
502 protected:
503
504 //*************************************************************************
506 //*************************************************************************
507 void clone(const iqueue& other)
508 {
509 clear();
510
511 size_type index = other.out;
512
513 for (size_type i = 0; i < other.size(); ++i)
514 {
515 push(other.p_buffer[index]);
516 index = (index == (CAPACITY - 1)) ? 0 : index + 1;
517 }
518 }
519
520#if ETL_USING_CPP11
521 //*************************************************************************
523 //*************************************************************************
524 void move_clone(iqueue&& other)
525 {
526 clear();
527
528 size_type index = other.out;
529
530 for (size_type i = 0; i < other.size(); ++i)
531 {
532 push(etl::move(other.p_buffer[index]));
533 index = (index == (CAPACITY - 1)) ? 0 : index + 1;
534 }
535 }
536#endif
537
538 //*************************************************************************
540 //*************************************************************************
541 iqueue(T* p_buffer_, size_type max_size_)
542 : base_t(max_size_),
543 p_buffer(p_buffer_)
544 {
545 }
546
547 private:
548
549 // Disable copy construction.
550 iqueue(const iqueue&);
551
552 T* p_buffer;
553
554 //*************************************************************************
556 //*************************************************************************
557#if defined(ETL_POLYMORPHIC_QUEUE) || defined(ETL_POLYMORPHIC_CONTAINERS)
558 public:
559 virtual ~iqueue()
560 {
561 }
562#else
563 protected:
565 {
566 }
567#endif
568 };
569
570 //***************************************************************************
577 //***************************************************************************
578 template <typename T, const size_t SIZE, const size_t MEMORY_MODEL = etl::memory_model::MEMORY_MODEL_LARGE>
579 class queue : public etl::iqueue<T, MEMORY_MODEL>
580 {
581 private:
582
584
585 public:
586
587 typedef typename base_t::size_type size_type;
588 typedef typename etl::aligned_storage<sizeof(T), etl::alignment_of<T>::value>::type container_type;
589
590 ETL_STATIC_ASSERT((SIZE <= etl::integral_limits<size_type>::max), "Size too large for memory model");
591
592 static ETL_CONSTANT size_type MAX_SIZE = size_type(SIZE);
593
594 //*************************************************************************
596 //*************************************************************************
598 : base_t(reinterpret_cast<T*>(&buffer[0]), SIZE)
599 {
600 }
601
602 //*************************************************************************
604 //*************************************************************************
605 queue(const queue& rhs)
606 : base_t(reinterpret_cast<T*>(&buffer[0]), SIZE)
607 {
608 base_t::clone(rhs);
609 }
610
611#if ETL_USING_CPP11
612 //*************************************************************************
614 //*************************************************************************
615 queue(queue&& rhs)
616 : base_t(reinterpret_cast<T*>(&buffer[0]), SIZE)
617 {
618 base_t::move_clone(etl::move(rhs));
619 }
620#endif
621
622 //*************************************************************************
624 //*************************************************************************
626 {
628 }
629
630 //*************************************************************************
632 //*************************************************************************
634 {
635 if (&rhs != this)
636 {
637 base_t::clone(rhs);
638 }
639
640 return *this;
641 }
642
643#if ETL_USING_CPP11
644 //*************************************************************************
646 //*************************************************************************
647 queue& operator = (queue&& rhs)
648 {
649 if (&rhs != this)
650 {
651 base_t::move_clone(rhs);
652 }
653
654 return *this;
655 }
656#endif
657
658 private:
659
661 container_type buffer[SIZE];
662 };
663
664 template <typename T, const size_t SIZE, const size_t MEMORY_MODEL>
665 ETL_CONSTANT typename queue<T, SIZE, MEMORY_MODEL>::size_type queue<T, SIZE, MEMORY_MODEL>::MAX_SIZE;
666}
667
668#endif
Definition: alignment.h:221
#define ETL_ASSERT(b, e)
Definition: error_handler.h:316
ETL_CONSTEXPR exception(string_type reason_, string_type, numeric_type line_)
Constructor.
Definition: exception.h:69
Definition: exception.h:47
Definition: integral_limits.h:468
~queue()
Destructor.
Definition: queue.h:625
size_type in
Where to input new data.
Definition: queue.h:223
queue & operator=(const queue &rhs)
Assignment operator.
Definition: queue.h:633
void emplace(const T1 &value1, const T2 &value2, const T3 &value3)
Definition: queue.h:388
const_reference front() const
Definition: queue.h:283
const T * const_pointer
A const pointer to the type used in the queue.
Definition: queue.h:258
void push(const_reference value)
Definition: queue.h:311
const_reference back() const
Definition: queue.h:301
void emplace(const T1 &value1)
Definition: queue.h:358
reference front()
Definition: queue.h:274
size_type current_size
The number of items in the queue.
Definition: queue.h:225
queue()
Default constructor.
Definition: queue.h:597
void pop_into(reference destination)
Definition: queue.h:453
etl::size_type_lookup< MEMORY_MODEL >::type size_type
The type used for determining the size of queue.
Definition: queue.h:112
iqueue & operator=(const iqueue &rhs)
Assignment operator.
Definition: queue.h:475
T value_type
The type stored in the queue.
Definition: queue.h:251
void pop()
Definition: queue.h:440
void index_clear()
Clears the indexes.
Definition: queue.h:215
size_type out
Where to get the oldest data.
Definition: queue.h:224
~queue_base()
Destructor.
Definition: queue.h:181
bool full() const
Definition: queue.h:151
reference back()
Definition: queue.h:292
size_type available() const
Definition: queue.h:160
void del_out()
Increments (and wraps) the 'out' index value to record a queue deletion.
Definition: queue.h:202
void add_in()
Increments (and wraps) the 'in' index value to record a queue addition.
Definition: queue.h:188
~iqueue()
Destructor.
Definition: queue.h:564
const size_type CAPACITY
The maximum number of items in the queue.
Definition: queue.h:226
base_t::size_type size_type
The type used for determining the size of the queue.
Definition: queue.h:259
iqueue(T *p_buffer_, size_type max_size_)
The constructor that is called from derived classes.
Definition: queue.h:541
queue_base(size_type max_size_)
The constructor that is called from derived classes.
Definition: queue.h:170
void clone(const iqueue &other)
Make this a clone of the supplied queue.
Definition: queue.h:507
queue(const queue &rhs)
Copy constructor.
Definition: queue.h:605
size_type size() const
Returns the current number of items in the queue.
Definition: queue.h:117
const T & const_reference
A const reference to the type used in the queue.
Definition: queue.h:253
void pop_into(TContainer &destination)
Definition: queue.h:466
size_type capacity() const
Returns the maximum number of items that can be queued.
Definition: queue.h:133
T & reference
A reference to the type used in the queue.
Definition: queue.h:252
size_type max_size() const
Returns the maximum number of items that can be queued.
Definition: queue.h:125
bool empty() const
Definition: queue.h:142
T * pointer
A pointer to the type used in the queue.
Definition: queue.h:257
void emplace(const T1 &value1, const T2 &value2)
Definition: queue.h:373
void clear()
Clears the queue to the empty state.
Definition: queue.h:416
void emplace(const T1 &value1, const T2 &value2, const T3 &value3, const T4 &value4)
Definition: queue.h:403
This is the base for all queues that contain a particular type.
Definition: queue.h:244
Definition: queue.h:580
Definition: queue.h:108
Definition: queue.h:93
Definition: queue.h:65
Definition: queue.h:79
add_rvalue_reference
Definition: type_traits_generator.h:1327
bitset_ext
Definition: absolute.h:38
Definition: alignment.h:223
Definition: type_traits_generator.h:2055
Definition: memory_model.h:50