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 reference emplace(Args && ... args)
344 {
345#if defined(ETL_CHECK_PUSH_POP)
346 ETL_ASSERT(!full(), ETL_ERROR(queue_full));
347#endif
348 reference value = p_buffer[in];
349 ::new (&value) T(etl::forward<Args>(args)...);
350 add_in();
351 return value;
352 }
353#else
354 //*************************************************************************
357 //*************************************************************************
359 {
360#if defined(ETL_CHECK_PUSH_POP)
361 ETL_ASSERT(!full(), ETL_ERROR(queue_full));
362#endif
363 reference value = p_buffer[in];
364 ::new (&value) T();
365 add_in();
366 return value;
367 }
368
369 //*************************************************************************
373 //*************************************************************************
374 template <typename T1>
375 reference emplace(const T1& value1)
376 {
377#if defined(ETL_CHECK_PUSH_POP)
378 ETL_ASSERT(!full(), ETL_ERROR(queue_full));
379#endif
380 reference value = p_buffer[in];
381 ::new (&value) T(value1);
382 add_in();
383 return value;
384 }
385
386 //*************************************************************************
391 //*************************************************************************
392 template <typename T1, typename T2>
393 reference emplace(const T1& value1, const T2& value2)
394 {
395#if defined(ETL_CHECK_PUSH_POP)
396 ETL_ASSERT(!full(), ETL_ERROR(queue_full));
397#endif
398 reference value = p_buffer[in];
399 ::new (&value) T(value1, value2);
400 add_in();
401 return value;
402 }
403
404 //*************************************************************************
410 //*************************************************************************
411 template <typename T1, typename T2, typename T3>
412 reference emplace(const T1& value1, const T2& value2, const T3& value3)
413 {
414#if defined(ETL_CHECK_PUSH_POP)
415 ETL_ASSERT(!full(), ETL_ERROR(queue_full));
416#endif
417 reference value = p_buffer[in];
418 ::new (&value) T(value1, value2, value3);
419 add_in();
420 return value;
421 }
422
423 //*************************************************************************
430 //*************************************************************************
431 template <typename T1, typename T2, typename T3, typename T4>
432 reference emplace(const T1& value1, const T2& value2, const T3& value3, const T4& value4)
433 {
434#if defined(ETL_CHECK_PUSH_POP)
435 ETL_ASSERT(!full(), ETL_ERROR(queue_full));
436#endif
437 reference value = p_buffer[in];
438 ::new (&value) T(value1, value2, value3, value4);
439 add_in();
440 return value;
441 }
442#endif
443
444 //*************************************************************************
446 //*************************************************************************
447 void clear()
448 {
450 {
452 }
453 else
454 {
455 while (current_size > 0)
456 {
457 p_buffer[out].~T();
458 del_out();
459 }
460
461 in = 0;
462 out = 0;
463 }
464 }
465
466 //*************************************************************************
470 //*************************************************************************
471 void pop()
472 {
473#if defined(ETL_CHECK_PUSH_POP)
474 ETL_ASSERT_OR_RETURN(!empty(), ETL_ERROR(queue_empty));
475#endif
476 p_buffer[out].~T();
477 del_out();
478 }
479
480 //*************************************************************************
483 //*************************************************************************
485 {
486 destination = ETL_MOVE(front());
487 pop();
488 }
489
490 //*************************************************************************
495 //*************************************************************************
496 template <typename TContainer>
498 {
499 destination.push(ETL_MOVE(front()));
500 pop();
501 }
502
503 //*************************************************************************
505 //*************************************************************************
507 {
508 if (&rhs != this)
509 {
510 clear();
511 clone(rhs);
512 }
513
514 return *this;
515 }
516
517#if ETL_USING_CPP11
518 //*************************************************************************
520 //*************************************************************************
522 {
523 if (&rhs != this)
524 {
525 clear();
527 }
528
529 return *this;
530 }
531#endif
532
533 protected:
534
535 //*************************************************************************
537 //*************************************************************************
538 void clone(const 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(other.p_buffer[index]);
547 index = (index == (CAPACITY - 1)) ? 0 : index + 1;
548 }
549 }
550
551#if ETL_USING_CPP11
552 //*************************************************************************
554 //*************************************************************************
555 void move_clone(iqueue&& other)
556 {
557 clear();
558
559 size_type index = other.out;
560
561 for (size_type i = 0; i < other.size(); ++i)
562 {
563 push(etl::move(other.p_buffer[index]));
564 index = (index == (CAPACITY - 1)) ? 0 : index + 1;
565 }
566 }
567#endif
568
569 //*************************************************************************
571 //*************************************************************************
573 : base_t(max_size_),
574 p_buffer(p_buffer_)
575 {
576 }
577
578 private:
579
580 // Disable copy construction.
581 iqueue(const iqueue&);
582
583 T* p_buffer;
584
585 //*************************************************************************
587 //*************************************************************************
588#if defined(ETL_POLYMORPHIC_QUEUE) || defined(ETL_POLYMORPHIC_CONTAINERS)
589 public:
590 virtual ~iqueue()
591 {
592 }
593#else
594 protected:
596 {
597 }
598#endif
599 };
600
601 //***************************************************************************
608 //***************************************************************************
609 template <typename T, const size_t SIZE, const size_t MEMORY_MODEL = etl::memory_model::MEMORY_MODEL_LARGE>
610 class queue : public etl::iqueue<T, MEMORY_MODEL>
611 {
612 private:
613
615
616 public:
617
618 typedef typename base_t::size_type size_type;
619 typedef typename etl::aligned_storage<sizeof(T), etl::alignment_of<T>::value>::type container_type;
620
621 ETL_STATIC_ASSERT((SIZE <= etl::integral_limits<size_type>::max), "Size too large for memory model");
622
623 static ETL_CONSTANT size_type MAX_SIZE = size_type(SIZE);
624
625 //*************************************************************************
627 //*************************************************************************
629 : base_t(reinterpret_cast<T*>(&buffer[0]), SIZE)
630 {
631 }
632
633 //*************************************************************************
635 //*************************************************************************
637 : base_t(reinterpret_cast<T*>(&buffer[0]), SIZE)
638 {
639 base_t::clone(rhs);
640 }
641
642#if ETL_USING_CPP11
643 //*************************************************************************
645 //*************************************************************************
646 queue(queue&& rhs)
647 : base_t(reinterpret_cast<T*>(&buffer[0]), SIZE)
648 {
649 base_t::move_clone(etl::move(rhs));
650 }
651#endif
652
653 //*************************************************************************
655 //*************************************************************************
657 {
658 base_t::clear();
659 }
660
661 //*************************************************************************
663 //*************************************************************************
665 {
666 if (&rhs != this)
667 {
668 base_t::clone(rhs);
669 }
670
671 return *this;
672 }
673
674#if ETL_USING_CPP11
675 //*************************************************************************
677 //*************************************************************************
679 {
680 if (&rhs != this)
681 {
682 base_t::move_clone(etl::move(rhs));
683 }
684
685 return *this;
686 }
687#endif
688
689 private:
690
692 container_type buffer[SIZE];
693 };
694
695 template <typename T, const size_t SIZE, const size_t MEMORY_MODEL>
696 ETL_CONSTANT typename queue<T, SIZE, MEMORY_MODEL>::size_type queue<T, SIZE, MEMORY_MODEL>::MAX_SIZE;
697}
698
699#endif
Definition alignment.h:231
#define ETL_ASSERT(b, e)
Definition error_handler.h:356
Definition exception.h:47
Definition integral_limits.h:516
~queue()
Destructor.
Definition queue.h:656
size_type in
Where to input new data.
Definition queue.h:223
reference emplace(const T1 &value1, const T2 &value2)
Definition queue.h:393
queue & operator=(const queue &rhs)
Assignment operator.
Definition queue.h:664
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
reference emplace(const T1 &value1, const T2 &value2, const T3 &value3)
Definition queue.h:412
const_reference back() const
Definition queue.h:301
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:628
void pop_into(reference destination)
Definition queue.h:484
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:506
reference emplace(const T1 &value1, const T2 &value2, const T3 &value3, const T4 &value4)
Definition queue.h:432
T value_type
The type stored in the queue.
Definition queue.h:251
void pop()
Definition queue.h:471
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:595
const size_type CAPACITY
The maximum number of items in the queue.
Definition queue.h:226
reference emplace()
Definition queue.h:358
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:572
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:538
queue(const queue &rhs)
Copy constructor.
Definition queue.h:636
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:497
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
reference emplace(const T1 &value1)
Definition queue.h:375
bool empty() const
Definition queue.h:142
T * pointer
A pointer to the type used in the queue.
Definition queue.h:257
void clear()
Clears the queue to the empty state.
Definition queue.h:447
This is the base for all queues that contain a particular type.
Definition queue.h:244
Definition queue.h:611
Definition queue.h:108
Definition queue.h:93
Definition queue.h:65
Definition queue.h:79
add_rvalue_reference
Definition type_traits_generator.h:1322
bitset_ext
Definition absolute.h:38
Definition alignment.h:233
Definition type_traits_generator.h:2096
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