Line data Source code
1 : ///\file
2 :
3 : /******************************************************************************
4 : The MIT License(MIT)
5 :
6 : Embedded Template Library.
7 : https://github.com/ETLCPP/etl
8 : https://www.etlcpp.com
9 :
10 : Copyright(c) 2014 John Wellbelove, Mark Kitson
11 :
12 : Permission is hereby granted, free of charge, to any person obtaining a copy
13 : of this software and associated documentation files(the "Software"), to deal
14 : in the Software without restriction, including without limitation the rights
15 : to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
16 : copies of the Software, and to permit persons to whom the Software is
17 : furnished to do so, subject to the following conditions :
18 :
19 : The above copyright notice and this permission notice shall be included in all
20 : copies or substantial portions of the Software.
21 :
22 : THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
23 : IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
24 : FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
25 : AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
26 : LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
27 : OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
28 : SOFTWARE.
29 : ******************************************************************************/
30 :
31 : #ifndef ETL_QUEUE_INCLUDED
32 : #define ETL_QUEUE_INCLUDED
33 :
34 : #include "platform.h"
35 : #include "alignment.h"
36 : #include "exception.h"
37 : #include "error_handler.h"
38 : #include "debug_count.h"
39 : #include "type_traits.h"
40 : #include "parameter_type.h"
41 : #include "memory_model.h"
42 : #include "integral_limits.h"
43 : #include "utility.h"
44 : #include "placement_new.h"
45 :
46 : #include <stddef.h>
47 : #include <stdint.h>
48 :
49 : //*****************************************************************************
50 : ///\defgroup queue queue
51 : /// A First-in / first-out queue with the capacity defined at compile time,
52 : /// written in the STL style.
53 : ///\ingroup containers
54 : //*****************************************************************************
55 :
56 : namespace etl
57 : {
58 : //***************************************************************************
59 : /// The base class for queue exceptions.
60 : ///\ingroup queue
61 : //***************************************************************************
62 : class queue_exception : public exception
63 : {
64 : public:
65 :
66 : queue_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
67 : : exception(reason_, file_name_, line_number_)
68 : {
69 : }
70 : };
71 :
72 : //***************************************************************************
73 : /// The exception thrown when the queue is full.
74 : ///\ingroup queue
75 : //***************************************************************************
76 : class queue_full : public queue_exception
77 : {
78 : public:
79 :
80 : queue_full(string_type file_name_, numeric_type line_number_)
81 : : queue_exception(ETL_ERROR_TEXT("queue:full", ETL_QUEUE_FILE_ID"A"), file_name_, line_number_)
82 : {
83 : }
84 : };
85 :
86 : //***************************************************************************
87 : /// The exception thrown when the queue is empty.
88 : ///\ingroup queue
89 : //***************************************************************************
90 : class queue_empty : public queue_exception
91 : {
92 : public:
93 :
94 : queue_empty(string_type file_name_, numeric_type line_number_)
95 : : queue_exception(ETL_ERROR_TEXT("queue:empty", ETL_QUEUE_FILE_ID"B"), file_name_, line_number_)
96 : {
97 : }
98 : };
99 :
100 : //***************************************************************************
101 : /// The base class for all queues.
102 : ///\ingroup queue
103 : //***************************************************************************
104 : template <size_t MEMORY_MODEL = etl::memory_model::MEMORY_MODEL_LARGE>
105 : class queue_base
106 : {
107 : public:
108 :
109 : /// The type used for determining the size of queue.
110 : typedef typename etl::size_type_lookup<MEMORY_MODEL>::type size_type;
111 :
112 : //*************************************************************************
113 : /// Returns the current number of items in the queue.
114 : //*************************************************************************
115 : size_type size() const
116 : {
117 : return current_size;
118 : }
119 :
120 : //*************************************************************************
121 : /// Returns the maximum number of items that can be queued.
122 : //*************************************************************************
123 : size_type max_size() const
124 : {
125 : return CAPACITY;
126 : }
127 :
128 : //*************************************************************************
129 : /// Returns the maximum number of items that can be queued.
130 : //*************************************************************************
131 : size_type capacity() const
132 : {
133 : return CAPACITY;
134 : }
135 :
136 : //*************************************************************************
137 : /// Checks to see if the queue is empty.
138 : /// \return <b>true</b> if the queue is empty, otherwise <b>false</b>
139 : //*************************************************************************
140 31 : bool empty() const
141 : {
142 31 : return current_size == 0;
143 : }
144 :
145 : //*************************************************************************
146 : /// Checks to see if the queue is full.
147 : /// \return <b>true</b> if the queue is full, otherwise <b>false</b>
148 : //*************************************************************************
149 7 : bool full() const
150 : {
151 7 : return current_size == CAPACITY;
152 : }
153 :
154 : //*************************************************************************
155 : /// Returns the remaining capacity.
156 : ///\return The remaining capacity.
157 : //*************************************************************************
158 : size_type available() const
159 : {
160 : return max_size() - size();
161 : }
162 :
163 : protected:
164 :
165 : //*************************************************************************
166 : /// The constructor that is called from derived classes.
167 : //*************************************************************************
168 91 : queue_base(size_type max_size_)
169 91 : : in(0),
170 91 : out(0),
171 91 : current_size(0),
172 91 : CAPACITY(max_size_)
173 : {
174 91 : }
175 :
176 : //*************************************************************************
177 : /// Destructor.
178 : //*************************************************************************
179 91 : ~queue_base()
180 : {
181 91 : }
182 :
183 : //*************************************************************************
184 : /// Increments (and wraps) the 'in' index value to record a queue addition.
185 : //*************************************************************************
186 15 : void add_in()
187 : {
188 15 : if (++in == CAPACITY) ETL_UNLIKELY
189 : {
190 15 : in = 0;
191 : }
192 :
193 15 : ++current_size;
194 : ETL_INCREMENT_DEBUG_COUNT;
195 15 : }
196 :
197 : //*************************************************************************
198 : /// Increments (and wraps) the 'out' index value to record a queue deletion.
199 : //*************************************************************************
200 15 : void del_out()
201 : {
202 15 : if (++out == CAPACITY) ETL_UNLIKELY
203 : {
204 15 : out = 0;
205 : }
206 15 : --current_size;
207 : ETL_DECREMENT_DEBUG_COUNT;
208 15 : }
209 :
210 : //*************************************************************************
211 : /// Clears the indexes.
212 : //*************************************************************************
213 : void index_clear()
214 : {
215 : in = 0;
216 : out = 0;
217 : current_size = 0;
218 : ETL_RESET_DEBUG_COUNT;
219 : }
220 :
221 : size_type in; ///< Where to input new data.
222 : size_type out; ///< Where to get the oldest data.
223 : size_type current_size; ///< The number of items in the queue.
224 : const size_type CAPACITY; ///< The maximum number of items in the queue.
225 : ETL_DECLARE_DEBUG_COUNT; ///< For internal debugging purposes.
226 :
227 : };
228 :
229 : //***************************************************************************
230 : ///\ingroup queue
231 : ///\brief This is the base for all queues that contain a particular type.
232 : ///\details Normally a reference to this type will be taken from a derived queue.
233 : ///\code
234 : /// etl::queue<int, 10> myQueue;
235 : /// etl::iqueue<int>& iQueue = myQueue;
236 : ///\endcode
237 : /// \warning This queue cannot be used for concurrent access from multiple threads.
238 : /// \tparam T The type of value that the queue holds.
239 : //***************************************************************************
240 : template <typename T, const size_t MEMORY_MODEL = etl::memory_model::MEMORY_MODEL_LARGE>
241 : class iqueue : public etl::queue_base<MEMORY_MODEL>
242 : {
243 : private:
244 :
245 : typedef typename etl::queue_base<MEMORY_MODEL> base_t;
246 :
247 : public:
248 :
249 : typedef T value_type; ///< The type stored in the queue.
250 : typedef T& reference; ///< A reference to the type used in the queue.
251 : typedef const T& const_reference; ///< A const reference to the type used in the queue.
252 : #if ETL_USING_CPP11
253 : typedef T&& rvalue_reference;///< An rvalue reference to the type used in the queue.
254 : #endif
255 : typedef T* pointer; ///< A pointer to the type used in the queue.
256 : typedef const T* const_pointer; ///< A const pointer to the type used in the queue.
257 : typedef typename base_t::size_type size_type; ///< The type used for determining the size of the queue.
258 :
259 : using base_t::in;
260 : using base_t::out;
261 : using base_t::CAPACITY;
262 : using base_t::current_size;
263 : using base_t::full;
264 : using base_t::empty;
265 : using base_t::add_in;
266 : using base_t::del_out;
267 :
268 : //*************************************************************************
269 : /// Gets a reference to the value at the front of the queue.<br>
270 : /// \return A reference to the value at the front of the queue.
271 : //*************************************************************************
272 11 : reference front()
273 : {
274 11 : return p_buffer[out];
275 : }
276 :
277 : //*************************************************************************
278 : /// Gets a const reference to the value at the front of the queue.<br>
279 : /// \return A const reference to the value at the front of the queue.
280 : //*************************************************************************
281 : const_reference front() const
282 : {
283 : return p_buffer[out];
284 : }
285 :
286 : //*************************************************************************
287 : /// Gets a reference to the value at the back of the queue.<br>
288 : /// \return A reference to the value at the back of the queue.
289 : //*************************************************************************
290 6 : reference back()
291 : {
292 6 : return p_buffer[in == 0 ? CAPACITY - 1 : in - 1];
293 : }
294 :
295 : //*************************************************************************
296 : /// Gets a const reference to the value at the back of the queue.<br>
297 : /// \return A const reference to the value at the back of the queue.
298 : //*************************************************************************
299 : const_reference back() const
300 : {
301 : return p_buffer[in == 0 ? CAPACITY - 1 : in - 1];
302 : }
303 :
304 : //*************************************************************************
305 : /// Adds a value to the queue.
306 : /// If asserts or exceptions are enabled, throws an etl::queue_full if the queue if already full.
307 : ///\param value The value to push to the queue.
308 : //*************************************************************************
309 : void push(const_reference value)
310 : {
311 : #if defined(ETL_CHECK_PUSH_POP)
312 : ETL_ASSERT(!full(), ETL_ERROR(queue_full));
313 : #endif
314 : ::new (&p_buffer[in]) T(value);
315 : add_in();
316 : }
317 :
318 : #if ETL_USING_CPP11
319 : //*************************************************************************
320 : /// Adds a value to the queue.
321 : /// If asserts or exceptions are enabled, throws an etl::queue_full if the queue if already full.
322 : ///\param value The value to push to the queue.
323 : //*************************************************************************
324 : void push(rvalue_reference value)
325 : {
326 : #if defined(ETL_CHECK_PUSH_POP)
327 : ETL_ASSERT(!full(), ETL_ERROR(queue_full));
328 : #endif
329 : ::new (&p_buffer[in]) T(etl::move(value));
330 : add_in();
331 : }
332 : #endif
333 :
334 : #if ETL_USING_CPP11 && ETL_NOT_USING_STLPORT && !defined(ETL_QUEUE_FORCE_CPP03_IMPLEMENTATION)
335 : //*************************************************************************
336 : /// Constructs a value in the queue 'in place'.
337 : /// If asserts or exceptions are enabled, throws an etl::queue_full if the queue if already full.
338 : ///\param args The arguments to the constructor for the new item to push to the queue.
339 : //*************************************************************************
340 : template <typename ... Args>
341 15 : reference emplace(Args && ... args)
342 : {
343 : #if defined(ETL_CHECK_PUSH_POP)
344 : ETL_ASSERT(!full(), ETL_ERROR(queue_full));
345 : #endif
346 15 : reference value = p_buffer[in];
347 15 : ::new (&value) T(etl::forward<Args>(args)...);
348 15 : add_in();
349 15 : return value;
350 : }
351 : #else
352 : //*************************************************************************
353 : /// Constructs a default constructed value in the queue 'in place'.
354 : /// If asserts or exceptions are enabled, throws an etl::queue_full if the queue if already full.
355 : //*************************************************************************
356 : reference emplace()
357 : {
358 : #if defined(ETL_CHECK_PUSH_POP)
359 : ETL_ASSERT(!full(), ETL_ERROR(queue_full));
360 : #endif
361 : reference value = p_buffer[in];
362 : ::new (&value) T();
363 : add_in();
364 : return value;
365 : }
366 :
367 : //*************************************************************************
368 : /// Constructs a value in the queue 'in place'.
369 : /// If asserts or exceptions are enabled, throws an etl::queue_full if the queue if already full.
370 : ///\param value1 The argument to use to construct the item to push to the queue.
371 : //*************************************************************************
372 : template <typename T1>
373 : reference emplace(const T1& value1)
374 : {
375 : #if defined(ETL_CHECK_PUSH_POP)
376 : ETL_ASSERT(!full(), ETL_ERROR(queue_full));
377 : #endif
378 : reference value = p_buffer[in];
379 : ::new (&value) T(value1);
380 : add_in();
381 : return value;
382 : }
383 :
384 : //*************************************************************************
385 : /// Constructs a value in the queue 'in place'.
386 : /// If asserts or exceptions are enabled, throws an etl::queue_full if the queue if already full.
387 : ///\param value1 The first argument to use to construct the item to push to the queue.
388 : ///\param value2 The second argument to use to construct the item to push to the queue.
389 : //*************************************************************************
390 : template <typename T1, typename T2>
391 : reference emplace(const T1& value1, const T2& value2)
392 : {
393 : #if defined(ETL_CHECK_PUSH_POP)
394 : ETL_ASSERT(!full(), ETL_ERROR(queue_full));
395 : #endif
396 : reference value = p_buffer[in];
397 : ::new (&value) T(value1, value2);
398 : add_in();
399 : return value;
400 : }
401 :
402 : //*************************************************************************
403 : /// Constructs a value in the queue 'in place'.
404 : /// If asserts or exceptions are enabled, throws an etl::queue_full if the queue if already full.
405 : ///\param value1 The first argument to use to construct the item to push to the queue.
406 : ///\param value2 The second argument to use to construct the item to push to the queue.
407 : ///\param value3 The third argument to use to construct the item to push to the queue.
408 : //*************************************************************************
409 : template <typename T1, typename T2, typename T3>
410 : reference emplace(const T1& value1, const T2& value2, const T3& value3)
411 : {
412 : #if defined(ETL_CHECK_PUSH_POP)
413 : ETL_ASSERT(!full(), ETL_ERROR(queue_full));
414 : #endif
415 : reference value = p_buffer[in];
416 : ::new (&value) T(value1, value2, value3);
417 : add_in();
418 : return value;
419 : }
420 :
421 : //*************************************************************************
422 : /// Constructs a value in the queue 'in place'.
423 : /// If asserts or exceptions are enabled, throws an etl::queue_full if the queue if already full.
424 : ///\param value1 The first argument to use to construct the item to push to the queue.
425 : ///\param value2 The second argument to use to construct the item to push to the queue.
426 : ///\param value3 The third argument to use to construct the item to push to the queue.
427 : ///\param value4 The fourth argument to use to construct the item to push to the queue.
428 : //*************************************************************************
429 : template <typename T1, typename T2, typename T3, typename T4>
430 : reference emplace(const T1& value1, const T2& value2, const T3& value3, const T4& value4)
431 : {
432 : #if defined(ETL_CHECK_PUSH_POP)
433 : ETL_ASSERT(!full(), ETL_ERROR(queue_full));
434 : #endif
435 : reference value = p_buffer[in];
436 : ::new (&value) T(value1, value2, value3, value4);
437 : add_in();
438 : return value;
439 : }
440 : #endif
441 :
442 : //*************************************************************************
443 : /// Clears the queue to the empty state.
444 : //*************************************************************************
445 91 : void clear()
446 : {
447 : if ETL_IF_CONSTEXPR(etl::is_trivially_destructible<T>::value)
448 : {
449 : base_t::index_clear();
450 : }
451 : else
452 : {
453 95 : while (current_size > 0)
454 : {
455 4 : p_buffer[out].~T();
456 4 : del_out();
457 : }
458 :
459 91 : in = 0;
460 91 : out = 0;
461 : }
462 91 : }
463 :
464 : //*************************************************************************
465 : /// Removes the oldest value from the back of the queue.
466 : /// Does nothing if the queue is already empty.
467 : /// If asserts or exceptions are enabled, throws an etl::queue_empty if the queue is empty.
468 : //*************************************************************************
469 11 : void pop()
470 : {
471 : #if defined(ETL_CHECK_PUSH_POP)
472 : ETL_ASSERT_OR_RETURN(!empty(), ETL_ERROR(queue_empty));
473 : #endif
474 11 : p_buffer[out].~T();
475 11 : del_out();
476 11 : }
477 :
478 : //*************************************************************************
479 : /// Gets the oldest value and removes it from the front of the queue.
480 : /// If asserts or exceptions are enabled, throws an etl::queue_empty if the queue is empty.
481 : //*************************************************************************
482 : void pop_into(reference destination)
483 : {
484 : destination = ETL_MOVE(front());
485 : pop();
486 : }
487 :
488 : //*************************************************************************
489 : /// Gets the oldest value and removes it from the front of the queue and
490 : /// pushes it to the destination container.
491 : /// If asserts or exceptions are enabled, throws an etl::queue_empty if the queue is empty.
492 : /// NOTE: The destination must support a push(T) member function.
493 : //*************************************************************************
494 : template <typename TContainer>
495 : void pop_into(TContainer& destination)
496 : {
497 : destination.push(ETL_MOVE(front()));
498 : pop();
499 : }
500 :
501 : //*************************************************************************
502 : /// Assignment operator.
503 : //*************************************************************************
504 : iqueue& operator = (const iqueue& rhs)
505 : {
506 : if (&rhs != this)
507 : {
508 : clear();
509 : clone(rhs);
510 : }
511 :
512 : return *this;
513 : }
514 :
515 : #if ETL_USING_CPP11
516 : //*************************************************************************
517 : /// Assignment operator.
518 : //*************************************************************************
519 : iqueue& operator = (iqueue&& rhs)
520 : {
521 : if (&rhs != this)
522 : {
523 : clear();
524 : move_clone(rhs);
525 : }
526 :
527 : return *this;
528 : }
529 : #endif
530 :
531 : protected:
532 :
533 : //*************************************************************************
534 : /// Make this a clone of the supplied queue
535 : //*************************************************************************
536 : void clone(const iqueue& other)
537 : {
538 : clear();
539 :
540 : size_type index = other.out;
541 :
542 : for (size_type i = 0; i < other.size(); ++i)
543 : {
544 : push(other.p_buffer[index]);
545 : index = (index == (CAPACITY - 1)) ? 0 : index + 1;
546 : }
547 : }
548 :
549 : #if ETL_USING_CPP11
550 : //*************************************************************************
551 : /// Make this a moved clone of the supplied queue
552 : //*************************************************************************
553 : void move_clone(iqueue&& other)
554 : {
555 : clear();
556 :
557 : size_type index = other.out;
558 :
559 : for (size_type i = 0; i < other.size(); ++i)
560 : {
561 : push(etl::move(other.p_buffer[index]));
562 : index = (index == (CAPACITY - 1)) ? 0 : index + 1;
563 : }
564 : }
565 : #endif
566 :
567 : //*************************************************************************
568 : /// The constructor that is called from derived classes.
569 : //*************************************************************************
570 91 : iqueue(T* p_buffer_, size_type max_size_)
571 : : base_t(max_size_),
572 91 : p_buffer(p_buffer_)
573 : {
574 91 : }
575 :
576 : private:
577 :
578 : // Disable copy construction.
579 : iqueue(const iqueue&);
580 :
581 : T* p_buffer; ///< The internal buffer.
582 :
583 : //*************************************************************************
584 : /// Destructor.
585 : //*************************************************************************
586 : #if defined(ETL_POLYMORPHIC_QUEUE) || defined(ETL_POLYMORPHIC_CONTAINERS)
587 : public:
588 : virtual ~iqueue()
589 : {
590 : }
591 : #else
592 : protected:
593 91 : ~iqueue()
594 : {
595 91 : }
596 : #endif
597 : };
598 :
599 : //***************************************************************************
600 : ///\ingroup queue
601 : /// A fixed capacity queue.
602 : /// This queue does not support concurrent access by different threads.
603 : /// \tparam T The type this queue should support.
604 : /// \tparam SIZE The maximum capacity of the queue.
605 : /// \tparam MEMORY_MODEL The memory model for the queue. Determines the type of the internal counter variables.
606 : //***************************************************************************
607 : template <typename T, const size_t SIZE, const size_t MEMORY_MODEL = etl::memory_model::MEMORY_MODEL_LARGE>
608 : class queue : public etl::iqueue<T, MEMORY_MODEL>
609 : {
610 : private:
611 :
612 : typedef etl::iqueue<T, MEMORY_MODEL> base_t;
613 :
614 : public:
615 :
616 : typedef typename base_t::size_type size_type;
617 : typedef typename etl::aligned_storage<sizeof(T), etl::alignment_of<T>::value>::type container_type;
618 :
619 : ETL_STATIC_ASSERT((SIZE <= etl::integral_limits<size_type>::max), "Size too large for memory model");
620 :
621 : static ETL_CONSTANT size_type MAX_SIZE = size_type(SIZE);
622 :
623 : //*************************************************************************
624 : /// Default constructor.
625 : //*************************************************************************
626 91 : queue()
627 91 : : base_t(reinterpret_cast<T*>(&buffer[0]), SIZE)
628 : {
629 91 : }
630 :
631 : //*************************************************************************
632 : /// Copy constructor
633 : //*************************************************************************
634 : queue(const queue& rhs)
635 : : base_t(reinterpret_cast<T*>(&buffer[0]), SIZE)
636 : {
637 : base_t::clone(rhs);
638 : }
639 :
640 : #if ETL_USING_CPP11
641 : //*************************************************************************
642 : /// Copy constructor
643 : //*************************************************************************
644 : queue(queue&& rhs)
645 : : base_t(reinterpret_cast<T*>(&buffer[0]), SIZE)
646 : {
647 : base_t::move_clone(etl::move(rhs));
648 : }
649 : #endif
650 :
651 : //*************************************************************************
652 : /// Destructor.
653 : //*************************************************************************
654 91 : ~queue()
655 : {
656 91 : base_t::clear();
657 91 : }
658 :
659 : //*************************************************************************
660 : /// Assignment operator.
661 : //*************************************************************************
662 : queue& operator = (const queue& rhs)
663 : {
664 : if (&rhs != this)
665 : {
666 : base_t::clone(rhs);
667 : }
668 :
669 : return *this;
670 : }
671 :
672 : #if ETL_USING_CPP11
673 : //*************************************************************************
674 : /// Move assignment operator.
675 : //*************************************************************************
676 : queue& operator = (queue&& rhs)
677 : {
678 : if (&rhs != this)
679 : {
680 : base_t::move_clone(etl::move(rhs));
681 : }
682 :
683 : return *this;
684 : }
685 : #endif
686 :
687 : private:
688 :
689 : /// The uninitialised buffer of T used in the queue.
690 : container_type buffer[SIZE];
691 : };
692 :
693 : template <typename T, const size_t SIZE, const size_t MEMORY_MODEL>
694 : ETL_CONSTANT typename queue<T, SIZE, MEMORY_MODEL>::size_type queue<T, SIZE, MEMORY_MODEL>::MAX_SIZE;
695 : }
696 :
697 : #endif
|
