Embedded Template Library 1.0
Loading...
Searching...
No Matches
stack.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_STACK_INCLUDED
32#define ETL_STACK_INCLUDED
33
34#include "platform.h"
35#include "algorithm.h"
36#include "utility.h"
37#include "iterator.h"
38#include "alignment.h"
39#include "array.h"
40#include "exception.h"
41#include "error_handler.h"
42#include "debug_count.h"
43#include "type_traits.h"
44#include "placement_new.h"
45
46#include <stddef.h>
47#include <stdint.h>
48
49//*****************************************************************************
54//*****************************************************************************
55
56namespace etl
57{
58 //***************************************************************************
61 //***************************************************************************
71
72 //***************************************************************************
75 //***************************************************************************
77 {
78 public:
79
81 : stack_exception(ETL_ERROR_TEXT("stack:full", ETL_STACK_FILE_ID"A"), file_name_, line_number_)
82 {
83 }
84 };
85
86 //***************************************************************************
89 //***************************************************************************
91 {
92 public:
93
95 : stack_exception(ETL_ERROR_TEXT("stack:empty", ETL_STACK_FILE_ID"B"), file_name_, line_number_)
96 {
97 }
98 };
99
100 //***************************************************************************
104 //***************************************************************************
106 {
107 public:
108
109 typedef size_t size_type;
110
111 //*************************************************************************
114 //*************************************************************************
115 bool empty() const
116 {
117 return current_size == 0;
118 }
119
120 //*************************************************************************
123 //*************************************************************************
124 bool full() const
125 {
126 return current_size == CAPACITY;
127 }
128
129 //*************************************************************************
131 //*************************************************************************
133 {
134 return current_size;
135 }
136
137 //*************************************************************************
139 //*************************************************************************
141 {
142 return CAPACITY;
143 }
144
145 //*************************************************************************
148 //*************************************************************************
149 size_t available() const
150 {
151 return max_size() - size();
152 }
153
154 protected:
155
156 //*************************************************************************
158 //*************************************************************************
165
166 //*************************************************************************
168 //*************************************************************************
170 {
171 }
172
173 //*************************************************************************
175 //*************************************************************************
176 void add_in()
177 {
179 ETL_INCREMENT_DEBUG_COUNT;
180 }
181
182 //*************************************************************************
184 //*************************************************************************
185 void del_out()
186 {
187 --top_index;
188 --current_size;
189 ETL_DECREMENT_DEBUG_COUNT;
190 }
191
192 //*************************************************************************
194 //*************************************************************************
196 {
197 top_index = 0;
198 current_size = 0;
199 ETL_RESET_DEBUG_COUNT;
200 }
201
206 };
207
208 //***************************************************************************
218 //***************************************************************************
219 template <typename T>
220 class istack : public etl::stack_base
221 {
222 public:
223
224 typedef T value_type;
225 typedef T& reference;
226 typedef const T& const_reference;
227#if ETL_USING_CPP11
228 typedef T&& rvalue_reference;
229#endif
230 typedef T* pointer;
231 typedef const T* const_pointer;
233
234 private:
235
236 typedef typename etl::stack_base base_t;
237
238 public:
239
240 //*************************************************************************
243 //*************************************************************************
245 {
246 return p_buffer[top_index];
247 }
248
249 //*************************************************************************
253 //*************************************************************************
255 {
256#if defined(ETL_CHECK_PUSH_POP)
257 ETL_ASSERT(!full(), ETL_ERROR(stack_full));
258#endif
260 ::new (&p_buffer[top_index]) T(value);
261 }
262
263#if ETL_USING_CPP11
264 //*************************************************************************
268 //*************************************************************************
269 void push(rvalue_reference value)
270 {
271#if defined(ETL_CHECK_PUSH_POP)
272 ETL_ASSERT(!full(), ETL_ERROR(stack_full));
273#endif
275 ::new (&p_buffer[top_index]) T(etl::move(value));
276 }
277#endif
278
279#if ETL_USING_CPP11 && ETL_NOT_USING_STLPORT
280 //*************************************************************************
284 //*************************************************************************
285 template <typename ... Args>
286 reference emplace(Args && ... args)
287 {
288#if defined(ETL_CHECK_PUSH_POP)
289 ETL_ASSERT(!full(), ETL_ERROR(stack_full));
290#endif
292 ::new (&p_buffer[top_index]) T(etl::forward<Args>(args)...);
293
294 return p_buffer[top_index];
295 }
296#else
297 //*************************************************************************
301 //*************************************************************************
303 {
304#if defined(ETL_CHECK_PUSH_POP)
305 ETL_ASSERT(!full(), ETL_ERROR(stack_full));
306#endif
308 ::new (&p_buffer[top_index]) T();
309
310 return p_buffer[top_index];
311 }
312
313 //*************************************************************************
317 //*************************************************************************
318 template <typename T1>
319 reference emplace(const T1& value1)
320 {
321#if defined(ETL_CHECK_PUSH_POP)
322 ETL_ASSERT(!full(), ETL_ERROR(stack_full));
323#endif
325 ::new (&p_buffer[top_index]) T(value1);
326
327 return p_buffer[top_index];
328 }
329
330 //*************************************************************************
334 //*************************************************************************
335 template <typename T1, typename T2>
336 reference emplace(const T1& value1, const T2& value2)
337 {
338#if defined(ETL_CHECK_PUSH_POP)
339 ETL_ASSERT(!full(), ETL_ERROR(stack_full));
340#endif
342 ::new (&p_buffer[top_index]) T(value1, value2);
343
344 return p_buffer[top_index];
345 }
346
347 //*************************************************************************
351 //*************************************************************************
352 template <typename T1, typename T2, typename T3>
353 reference emplace(const T1& value1, const T2& value2, const T3& value3)
354 {
355#if defined(ETL_CHECK_PUSH_POP)
356 ETL_ASSERT(!full(), ETL_ERROR(stack_full));
357#endif
359 ::new (&p_buffer[top_index]) T(value1, value2, value3);
360
361 return p_buffer[top_index];
362 }
363
364 //*************************************************************************
368 //*************************************************************************
369 template <typename T1, typename T2, typename T3, typename T4>
370 reference emplace(const T1& value1, const T2& value2, const T3& value3, const T4& value4)
371 {
372#if defined(ETL_CHECK_PUSH_POP)
373 ETL_ASSERT(!full(), ETL_ERROR(stack_full));
374#endif
376 ::new (&p_buffer[top_index]) T(value1, value2, value3, value4);
377
378 return p_buffer[top_index];
379 }
380#endif
381
382 //*************************************************************************
385 //*************************************************************************
387 {
388 return p_buffer[top_index];
389 }
390
391 //*************************************************************************
393 //*************************************************************************
394 void clear()
395 {
397 {
399 }
400 else
401 {
402 while (current_size > 0)
403 {
404 p_buffer[top_index].~T();
406 }
407 }
408 }
409
410 //*************************************************************************
412 //*************************************************************************
413 void pop()
414 {
415#if defined(ETL_CHECK_PUSH_POP)
416 ETL_ASSERT_OR_RETURN(!empty(), ETL_ERROR(stack_empty));
417#endif
418 p_buffer[top_index].~T();
420 }
421
422 //*************************************************************************
424 //*************************************************************************
426 {
427 destination = ETL_MOVE(top());
428 pop();
429 }
430
431 //*************************************************************************
435 //*************************************************************************
436 template <typename TContainer>
438 {
439 destination.push(ETL_MOVE(top()));
440 pop();
441 }
442
443 //*************************************************************************
445 //*************************************************************************
446 void reverse()
447 {
448 etl::reverse(p_buffer, p_buffer + current_size);
449 }
450
451 //*************************************************************************
453 //*************************************************************************
455 {
456 if (&rhs != this)
457 {
458 clear();
459 clone(rhs);
460 }
461
462 return *this;
463 }
464
465#if ETL_USING_CPP11
466 //*************************************************************************
468 //*************************************************************************
470 {
471 if (&rhs != this)
472 {
473 clone(etl::move(rhs));
474 }
475
476 return *this;
477 }
478#endif
479
480 protected:
481
482 //*************************************************************************
484 //*************************************************************************
485 void clone(const istack& other)
486 {
487 clear();
488
489 size_t index = 0UL;
490
491 for (size_t i = 0UL; i < other.size(); ++i)
492 {
493 push(other.p_buffer[index++]);
494 }
495 }
496
497#if ETL_USING_CPP11
498 //*************************************************************************
500 //*************************************************************************
501 void clone(istack&& other)
502 {
503 clear();
504
505 size_t index = 0UL;
506
507 for (size_t i = 0UL; i < other.size(); ++i)
508 {
509 push(etl::move(other.p_buffer[index++]));
510 }
511 }
512#endif
513
514 //*************************************************************************
516 //*************************************************************************
519 p_buffer(p_buffer_)
520 {
521 }
522
523 private:
524
525 // Disable copy construction.
526 istack(const istack&);
527
528 T* p_buffer;
529
530 //*************************************************************************
532 //*************************************************************************
533#if defined(ETL_POLYMORPHIC_STACK) || defined(ETL_POLYMORPHIC_CONTAINERS)
534 public:
535 virtual ~istack()
536 {
537 }
538#else
539 protected:
541 {
542 }
543#endif
544 };
545
546 //***************************************************************************
552 //***************************************************************************
553 template <typename T, const size_t SIZE>
554 class stack : public etl::istack<T>
555 {
556 public:
557 typedef typename etl::aligned_storage<sizeof(T), etl::alignment_of<T>::value>::type container_type;
558
559 static ETL_CONSTANT size_t MAX_SIZE = SIZE;
560
561 //*************************************************************************
563 //*************************************************************************
565 : etl::istack<T>(reinterpret_cast<T*>(&buffer[0]), SIZE)
566 {
567 }
568
569 //*************************************************************************
571 //*************************************************************************
573 : etl::istack<T>(reinterpret_cast<T*>(&buffer[0]), SIZE)
574 {
576 }
577
578#if ETL_USING_CPP11
579 //*************************************************************************
581 //*************************************************************************
582 stack(stack&& rhs)
583 : etl::istack<T>(reinterpret_cast<T*>(&buffer[0]), SIZE)
584 {
585 etl::istack<T>::clone(etl::move(rhs));
586 }
587#endif
588
589 //*************************************************************************
591 //*************************************************************************
593 {
595 }
596
597 //*************************************************************************
599 //*************************************************************************
601 {
602 if (&rhs != this)
603 {
605 }
606
607 return *this;
608 }
609
610#if ETL_USING_CPP11
611 //*************************************************************************
613 //*************************************************************************
615 {
616 if (&rhs != this)
617 {
618 etl::istack<T>::clone(etl::move(rhs));
619 }
620
621 return *this;
622 }
623#endif
624
625 private:
626
628 container_type buffer[SIZE];
629 };
630
631 template <typename T, const size_t SIZE>
632 ETL_CONSTANT size_t stack<T, SIZE>::MAX_SIZE;
633}
634
635#endif
Definition alignment.h:231
#define ETL_ASSERT(b, e)
Definition error_handler.h:356
Definition exception.h:47
ETL_DECLARE_DEBUG_COUNT
For internal debugging purposes.
Definition stack.h:205
void del_out()
Decrements the indexes value to record a queue deletion.
Definition stack.h:185
stack & operator=(const stack &rhs)
Assignment operator.
Definition stack.h:600
reference top()
Definition stack.h:244
bool empty() const
Definition stack.h:115
~stack_base()
Destructor.
Definition stack.h:169
stack()
Default constructor.
Definition stack.h:564
stack_base(size_type max_size_)
The constructor that is called from derived classes.
Definition stack.h:159
bool full() const
Definition stack.h:124
const T * const_pointer
A const pointer to the type used in the stack.
Definition stack.h:231
const size_type CAPACITY
The maximum number of items in the stack.
Definition stack.h:204
void index_clear()
Clears all of the indexes.
Definition stack.h:195
size_type size() const
Returns the current number of items top the stack.
Definition stack.h:132
reference emplace(const T1 &value1, const T2 &value2)
Definition stack.h:336
reference emplace(const T1 &value1)
Definition stack.h:319
istack(T *p_buffer_, size_type max_size_)
The constructor that is called from derived classes.
Definition stack.h:517
size_type max_size() const
Returns the maximum number of items that can be stacked.
Definition stack.h:140
size_type current_size
The number of items in the stack.
Definition stack.h:203
reference emplace()
Definition stack.h:302
size_t available() const
Definition stack.h:149
void push(const_reference value)
Definition stack.h:254
void pop()
Removes the oldest item from the top of the stack.
Definition stack.h:413
istack & operator=(const istack &rhs)
Assignment operator.
Definition stack.h:454
size_type top_index
The index of the top of the stack.
Definition stack.h:202
size_t size_type
The type used for determining the size of stack.
Definition stack.h:109
reference emplace(const T1 &value1, const T2 &value2, const T3 &value3, const T4 &value4)
Definition stack.h:370
T & reference
A reference to the type used in the stack.
Definition stack.h:225
reference emplace(const T1 &value1, const T2 &value2, const T3 &value3)
Definition stack.h:353
T * pointer
A pointer to the type used in the stack.
Definition stack.h:230
~stack()
Destructor.
Definition stack.h:592
stack(const stack &rhs)
Copy constructor.
Definition stack.h:572
void pop_into(TContainer &destination)
Definition stack.h:437
void clone(const istack &other)
Make this a clone of the supplied stack.
Definition stack.h:485
~istack()
Destructor.
Definition stack.h:540
void pop_into(reference destination)
Removes the oldest item from the top of the stack and puts it in the destination.
Definition stack.h:425
const T & const_reference
A const reference to the type used in the stack.
Definition stack.h:226
void add_in()
Increments the indexes value to record a stack addition.
Definition stack.h:176
void clear()
Clears the stack to the empty state.
Definition stack.h:394
stack_base::size_type size_type
The type used for determining the size of the stack.
Definition stack.h:232
T value_type
The type stored in the stack.
Definition stack.h:224
void reverse()
Reverses the stack.
Definition stack.h:446
const_reference top() const
Definition stack.h:386
This is the base for all stacks that contain a particular type.
Definition stack.h:221
Definition stack.h:555
Definition stack.h:106
Definition stack.h:91
Definition stack.h:63
Definition stack.h:77
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