Embedded Template Library 1.0
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 //***************************************************************************
63 {
64 public:
65
66 stack_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
67 : exception(reason_, file_name_, line_number_)
68 {
69 }
70 };
71
72 //***************************************************************************
75 //***************************************************************************
77 {
78 public:
79
80 stack_full(string_type file_name_, numeric_type line_number_)
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
94 stack_empty(string_type file_name_, numeric_type line_number_)
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 //*************************************************************************
160 : top_index(0),
161 current_size(0),
162 CAPACITY(max_size_)
163 {
164 }
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
205 ETL_DECLARE_DEBUG_COUNT
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 void 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#else
295 //*************************************************************************
299 //*************************************************************************
300 template <typename T1>
301 void emplace(const T1& value1)
302 {
303#if defined(ETL_CHECK_PUSH_POP)
304 ETL_ASSERT(!full(), ETL_ERROR(stack_full));
305#endif
307 ::new (&p_buffer[top_index]) T(value1);
308 }
309
310 //*************************************************************************
314 //*************************************************************************
315 template <typename T1, typename T2>
316 void emplace(const T1& value1, const T2& value2)
317 {
318#if defined(ETL_CHECK_PUSH_POP)
319 ETL_ASSERT(!full(), ETL_ERROR(stack_full));
320#endif
322 ::new (&p_buffer[top_index]) T(value1, value2);
323 }
324
325 //*************************************************************************
329 //*************************************************************************
330 template <typename T1, typename T2, typename T3>
331 void emplace(const T1& value1, const T2& value2, const T3& value3)
332 {
333#if defined(ETL_CHECK_PUSH_POP)
334 ETL_ASSERT(!full(), ETL_ERROR(stack_full));
335#endif
337 ::new (&p_buffer[top_index]) T(value1, value2, value3);
338 }
339
340 //*************************************************************************
344 //*************************************************************************
345 template <typename T1, typename T2, typename T3, typename T4>
346 void emplace(const T1& value1, const T2& value2, const T3& value3, const T4& value4)
347 {
348#if defined(ETL_CHECK_PUSH_POP)
349 ETL_ASSERT(!full(), ETL_ERROR(stack_full));
350#endif
352 ::new (&p_buffer[top_index]) T(value1, value2, value3, value4);
353 }
354#endif
355
356 //*************************************************************************
359 //*************************************************************************
361 {
362 return p_buffer[top_index];
363 }
364
365 //*************************************************************************
367 //*************************************************************************
368 void clear()
369 {
371 {
373 }
374 else
375 {
376 while (current_size > 0)
377 {
378 p_buffer[top_index].~T();
380 }
381 }
382 }
383
384 //*************************************************************************
386 //*************************************************************************
387 void pop()
388 {
389#if defined(ETL_CHECK_PUSH_POP)
390 ETL_ASSERT(!empty(), ETL_ERROR(stack_empty));
391#endif
392 p_buffer[top_index].~T();
394 }
395
396 //*************************************************************************
398 //*************************************************************************
399 void pop_into(reference destination)
400 {
401 destination = ETL_MOVE(top());
402 pop();
403 }
404
405 //*************************************************************************
409 //*************************************************************************
410 template <typename TContainer>
411 void pop_into(TContainer& destination)
412 {
413 destination.push(ETL_MOVE(top()));
414 pop();
415 }
416
417 //*************************************************************************
419 //*************************************************************************
420 void reverse()
421 {
422 etl::reverse(p_buffer, p_buffer + current_size);
423 }
424
425 //*************************************************************************
427 //*************************************************************************
429 {
430 if (&rhs != this)
431 {
432 clear();
433 clone(rhs);
434 }
435
436 return *this;
437 }
438
439#if ETL_USING_CPP11
440 //*************************************************************************
442 //*************************************************************************
444 {
445 if (&rhs != this)
446 {
447 clone(etl::move(rhs));
448 }
449
450 return *this;
451 }
452#endif
453
454 protected:
455
456 //*************************************************************************
458 //*************************************************************************
459 void clone(const istack& other)
460 {
461 clear();
462
463 size_t index = 0UL;
464
465 for (size_t i = 0UL; i < other.size(); ++i)
466 {
467 push(other.p_buffer[index++]);
468 }
469 }
470
471#if ETL_USING_CPP11
472 //*************************************************************************
474 //*************************************************************************
475 void clone(istack&& other)
476 {
477 clear();
478
479 size_t index = 0UL;
480
481 for (size_t i = 0UL; i < other.size(); ++i)
482 {
483 push(etl::move(other.p_buffer[index++]));
484 }
485 }
486#endif
487
488 //*************************************************************************
490 //*************************************************************************
491 istack(T* p_buffer_, size_type max_size_)
492 : stack_base(max_size_),
493 p_buffer(p_buffer_)
494 {
495 }
496
497 private:
498
499 // Disable copy construction.
500 istack(const istack&);
501
502 T* p_buffer;
503
504 //*************************************************************************
506 //*************************************************************************
507#if defined(ETL_POLYMORPHIC_STACK) || defined(ETL_POLYMORPHIC_CONTAINERS)
508 public:
509 virtual ~istack()
510 {
511 }
512#else
513 protected:
515 {
516 }
517#endif
518 };
519
520 //***************************************************************************
526 //***************************************************************************
527 template <typename T, const size_t SIZE>
528 class stack : public etl::istack<T>
529 {
530 public:
531 typedef typename etl::aligned_storage<sizeof(T), etl::alignment_of<T>::value>::type container_type;
532
533 static ETL_CONSTANT size_t MAX_SIZE = SIZE;
534
535 //*************************************************************************
537 //*************************************************************************
539 : etl::istack<T>(reinterpret_cast<T*>(&buffer[0]), SIZE)
540 {
541 }
542
543 //*************************************************************************
545 //*************************************************************************
546 stack(const stack& rhs)
547 : etl::istack<T>(reinterpret_cast<T*>(&buffer[0]), SIZE)
548 {
550 }
551
552#if ETL_USING_CPP11
553 //*************************************************************************
555 //*************************************************************************
556 stack(stack&& rhs)
557 : etl::istack<T>(reinterpret_cast<T*>(&buffer[0]), SIZE)
558 {
559 etl::istack<T>::clone(etl::move(rhs));
560 }
561#endif
562
563 //*************************************************************************
565 //*************************************************************************
567 {
569 }
570
571 //*************************************************************************
573 //*************************************************************************
575 {
576 if (&rhs != this)
577 {
579 }
580
581 return *this;
582 }
583
584#if ETL_USING_CPP11
585 //*************************************************************************
587 //*************************************************************************
588 stack& operator = (stack&& rhs)
589 {
590 if (&rhs != this)
591 {
592 etl::istack<T>::clone(etl::move(rhs));
593 }
594
595 return *this;
596 }
597#endif
598
599 private:
600
602 container_type buffer[SIZE];
603 };
604
605 template <typename T, const size_t SIZE>
606 ETL_CONSTANT size_t stack<T, SIZE>::MAX_SIZE;
607}
608
609#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
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:574
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:538
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 emplace(const T1 &value1, const T2 &value2, const T3 &value3, const T4 &value4)
Definition: stack.h:346
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
istack(T *p_buffer_, size_type max_size_)
The constructor that is called from derived classes.
Definition: stack.h:491
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
void emplace(const T1 &value1)
Definition: stack.h:301
void emplace(const T1 &value1, const T2 &value2)
Definition: stack.h:316
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:387
istack & operator=(const istack &rhs)
Assignment operator.
Definition: stack.h:428
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
T & reference
A reference to the type used in the stack.
Definition: stack.h:225
void emplace(const T1 &value1, const T2 &value2, const T3 &value3)
Definition: stack.h:331
T * pointer
A pointer to the type used in the stack.
Definition: stack.h:230
~stack()
Destructor.
Definition: stack.h:566
stack(const stack &rhs)
Copy constructor.
Definition: stack.h:546
void pop_into(TContainer &destination)
Definition: stack.h:411
void clone(const istack &other)
Make this a clone of the supplied stack.
Definition: stack.h:459
~istack()
Destructor.
Definition: stack.h:514
void pop_into(reference destination)
Removes the oldest item from the top of the stack and puts it in the destination.
Definition: stack.h:399
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:368
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:420
const_reference top() const
Definition: stack.h:360
This is the base for all stacks that contain a particular type.
Definition: stack.h:221
Definition: stack.h:529
Definition: stack.h:106
Definition: stack.h:91
Definition: stack.h:63
Definition: stack.h:77
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