Embedded Template Library 1.0
Loading...
Searching...
No Matches
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 //***************************************************************************
73
74 //***************************************************************************
77 //***************************************************************************
79 {
80 public:
81
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
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),
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
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 void emplace()
358 {
359#if defined(ETL_CHECK_PUSH_POP)
360 ETL_ASSERT(!full(), ETL_ERROR(queue_full));
361#endif
362 ::new (&p_buffer[in]) T();
363 add_in();
364 }
365
366 //*************************************************************************
370 //*************************************************************************
371 template <typename T1>
372 void emplace(const T1& value1)
373 {
374#if defined(ETL_CHECK_PUSH_POP)
375 ETL_ASSERT(!full(), ETL_ERROR(queue_full));
376#endif
377 ::new (&p_buffer[in]) T(value1);
378 add_in();
379 }
380
381 //*************************************************************************
385 //*************************************************************************
386 template <typename T1, typename T2>
387 void emplace(const T1& value1, const T2& value2)
388 {
389#if defined(ETL_CHECK_PUSH_POP)
390 ETL_ASSERT(!full(), ETL_ERROR(queue_full));
391#endif
392 ::new (&p_buffer[in]) T(value1, value2);
393 add_in();
394 }
395
396 //*************************************************************************
400 //*************************************************************************
401 template <typename T1, typename T2, typename T3>
402 void emplace(const T1& value1, const T2& value2, const T3& value3)
403 {
404#if defined(ETL_CHECK_PUSH_POP)
405 ETL_ASSERT(!full(), ETL_ERROR(queue_full));
406#endif
407 ::new (&p_buffer[in]) T(value1, value2, value3);
408 add_in();
409 }
410
411 //*************************************************************************
415 //*************************************************************************
416 template <typename T1, typename T2, typename T3, typename T4>
417 void emplace(const T1& value1, const T2& value2, const T3& value3, const T4& value4)
418 {
419#if defined(ETL_CHECK_PUSH_POP)
420 ETL_ASSERT(!full(), ETL_ERROR(queue_full));
421#endif
422 ::new (&p_buffer[in]) T(value1, value2, value3, value4);
423 add_in();
424 }
425#endif
426
427 //*************************************************************************
429 //*************************************************************************
430 void clear()
431 {
433 {
435 }
436 else
437 {
438 while (current_size > 0)
439 {
440 p_buffer[out].~T();
441 del_out();
442 }
443
444 in = 0;
445 out = 0;
446 }
447 }
448
449 //*************************************************************************
453 //*************************************************************************
454 void pop()
455 {
456#if defined(ETL_CHECK_PUSH_POP)
457 ETL_ASSERT_OR_RETURN(!empty(), ETL_ERROR(queue_empty));
458#endif
459 p_buffer[out].~T();
460 del_out();
461 }
462
463 //*************************************************************************
466 //*************************************************************************
468 {
469 destination = ETL_MOVE(front());
470 pop();
471 }
472
473 //*************************************************************************
478 //*************************************************************************
479 template <typename TContainer>
481 {
482 destination.push(ETL_MOVE(front()));
483 pop();
484 }
485
486 //*************************************************************************
488 //*************************************************************************
490 {
491 if (&rhs != this)
492 {
493 clear();
494 clone(rhs);
495 }
496
497 return *this;
498 }
499
500#if ETL_USING_CPP11
501 //*************************************************************************
503 //*************************************************************************
505 {
506 if (&rhs != this)
507 {
508 clear();
510 }
511
512 return *this;
513 }
514#endif
515
516 protected:
517
518 //*************************************************************************
520 //*************************************************************************
521 void clone(const iqueue& other)
522 {
523 clear();
524
525 size_type index = other.out;
526
527 for (size_type i = 0; i < other.size(); ++i)
528 {
529 push(other.p_buffer[index]);
530 index = (index == (CAPACITY - 1)) ? 0 : index + 1;
531 }
532 }
533
534#if ETL_USING_CPP11
535 //*************************************************************************
537 //*************************************************************************
538 void move_clone(iqueue&& other)
539 {
540 clear();
541
542 size_type index = other.out;
543
544 for (size_type i = 0; i < other.size(); ++i)
545 {
546 push(etl::move(other.p_buffer[index]));
547 index = (index == (CAPACITY - 1)) ? 0 : index + 1;
548 }
549 }
550#endif
551
552 //*************************************************************************
554 //*************************************************************************
556 : base_t(max_size_),
557 p_buffer(p_buffer_)
558 {
559 }
560
561 private:
562
563 // Disable copy construction.
564 iqueue(const iqueue&);
565
566 T* p_buffer;
567
568 //*************************************************************************
570 //*************************************************************************
571#if defined(ETL_POLYMORPHIC_QUEUE) || defined(ETL_POLYMORPHIC_CONTAINERS)
572 public:
573 virtual ~iqueue()
574 {
575 }
576#else
577 protected:
579 {
580 }
581#endif
582 };
583
584 //***************************************************************************
591 //***************************************************************************
592 template <typename T, const size_t SIZE, const size_t MEMORY_MODEL = etl::memory_model::MEMORY_MODEL_LARGE>
593 class queue : public etl::iqueue<T, MEMORY_MODEL>
594 {
595 private:
596
598
599 public:
600
601 typedef typename base_t::size_type size_type;
602 typedef typename etl::aligned_storage<sizeof(T), etl::alignment_of<T>::value>::type container_type;
603
604 ETL_STATIC_ASSERT((SIZE <= etl::integral_limits<size_type>::max), "Size too large for memory model");
605
606 static ETL_CONSTANT size_type MAX_SIZE = size_type(SIZE);
607
608 //*************************************************************************
610 //*************************************************************************
612 : base_t(reinterpret_cast<T*>(&buffer[0]), SIZE)
613 {
614 }
615
616 //*************************************************************************
618 //*************************************************************************
620 : base_t(reinterpret_cast<T*>(&buffer[0]), SIZE)
621 {
622 base_t::clone(rhs);
623 }
624
625#if ETL_USING_CPP11
626 //*************************************************************************
628 //*************************************************************************
629 queue(queue&& rhs)
630 : base_t(reinterpret_cast<T*>(&buffer[0]), SIZE)
631 {
632 base_t::move_clone(etl::move(rhs));
633 }
634#endif
635
636 //*************************************************************************
638 //*************************************************************************
640 {
641 base_t::clear();
642 }
643
644 //*************************************************************************
646 //*************************************************************************
648 {
649 if (&rhs != this)
650 {
651 base_t::clone(rhs);
652 }
653
654 return *this;
655 }
656
657#if ETL_USING_CPP11
658 //*************************************************************************
660 //*************************************************************************
662 {
663 if (&rhs != this)
664 {
665 base_t::move_clone(etl::move(rhs));
666 }
667
668 return *this;
669 }
670#endif
671
672 private:
673
675 container_type buffer[SIZE];
676 };
677
678 template <typename T, const size_t SIZE, const size_t MEMORY_MODEL>
679 ETL_CONSTANT typename queue<T, SIZE, MEMORY_MODEL>::size_type queue<T, SIZE, MEMORY_MODEL>::MAX_SIZE;
680}
681
682#endif
Definition alignment.h:231
#define ETL_ASSERT(b, e)
Definition error_handler.h:316
Definition exception.h:47
Definition integral_limits.h:516
~queue()
Destructor.
Definition queue.h:639
size_type in
Where to input new data.
Definition queue.h:223
queue & operator=(const queue &rhs)
Assignment operator.
Definition queue.h:647
void emplace(const T1 &value1, const T2 &value2, const T3 &value3)
Definition queue.h:402
const_reference front() const
Definition queue.h:283
ETL_DECLARE_DEBUG_COUNT
For internal debugging purposes.
Definition queue.h:227
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:372
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:611
void pop_into(reference destination)
Definition queue.h:467
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:489
T value_type
The type stored in the queue.
Definition queue.h:251
void pop()
Definition queue.h:454
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:578
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:555
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:521
queue(const queue &rhs)
Copy constructor.
Definition queue.h:619
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:480
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
void emplace()
Definition queue.h:357
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:387
void clear()
Clears the queue to the empty state.
Definition queue.h:430
void emplace(const T1 &value1, const T2 &value2, const T3 &value3, const T4 &value4)
Definition queue.h:417
This is the base for all queues that contain a particular type.
Definition queue.h:244
Definition queue.h:594
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:233
Definition type_traits_generator.h:2101
pair holds two objects of arbitrary type
Definition utility.h:164
ETL_CONSTEXPR pair()
Default constructor.
Definition utility.h:176
Definition memory_model.h:50