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 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 void emplace()
301 {
302#if defined(ETL_CHECK_PUSH_POP)
303 ETL_ASSERT(!full(), ETL_ERROR(stack_full));
304#endif
306 ::new (&p_buffer[top_index]) T();
307 }
308
309 //*************************************************************************
313 //*************************************************************************
314 template <typename T1>
315 void emplace(const T1& value1)
316 {
317#if defined(ETL_CHECK_PUSH_POP)
318 ETL_ASSERT(!full(), ETL_ERROR(stack_full));
319#endif
321 ::new (&p_buffer[top_index]) T(value1);
322 }
323
324 //*************************************************************************
328 //*************************************************************************
329 template <typename T1, typename T2>
330 void emplace(const T1& value1, const T2& value2)
331 {
332#if defined(ETL_CHECK_PUSH_POP)
333 ETL_ASSERT(!full(), ETL_ERROR(stack_full));
334#endif
336 ::new (&p_buffer[top_index]) T(value1, value2);
337 }
338
339 //*************************************************************************
343 //*************************************************************************
344 template <typename T1, typename T2, typename T3>
345 void emplace(const T1& value1, const T2& value2, const T3& value3)
346 {
347#if defined(ETL_CHECK_PUSH_POP)
348 ETL_ASSERT(!full(), ETL_ERROR(stack_full));
349#endif
351 ::new (&p_buffer[top_index]) T(value1, value2, value3);
352 }
353
354 //*************************************************************************
358 //*************************************************************************
359 template <typename T1, typename T2, typename T3, typename T4>
360 void emplace(const T1& value1, const T2& value2, const T3& value3, const T4& value4)
361 {
362#if defined(ETL_CHECK_PUSH_POP)
363 ETL_ASSERT(!full(), ETL_ERROR(stack_full));
364#endif
366 ::new (&p_buffer[top_index]) T(value1, value2, value3, value4);
367 }
368#endif
369
370 //*************************************************************************
373 //*************************************************************************
375 {
376 return p_buffer[top_index];
377 }
378
379 //*************************************************************************
381 //*************************************************************************
382 void clear()
383 {
385 {
387 }
388 else
389 {
390 while (current_size > 0)
391 {
392 p_buffer[top_index].~T();
394 }
395 }
396 }
397
398 //*************************************************************************
400 //*************************************************************************
401 void pop()
402 {
403#if defined(ETL_CHECK_PUSH_POP)
404 ETL_ASSERT_OR_RETURN(!empty(), ETL_ERROR(stack_empty));
405#endif
406 p_buffer[top_index].~T();
408 }
409
410 //*************************************************************************
412 //*************************************************************************
414 {
415 destination = ETL_MOVE(top());
416 pop();
417 }
418
419 //*************************************************************************
423 //*************************************************************************
424 template <typename TContainer>
426 {
427 destination.push(ETL_MOVE(top()));
428 pop();
429 }
430
431 //*************************************************************************
433 //*************************************************************************
434 void reverse()
435 {
436 etl::reverse(p_buffer, p_buffer + current_size);
437 }
438
439 //*************************************************************************
441 //*************************************************************************
443 {
444 if (&rhs != this)
445 {
446 clear();
447 clone(rhs);
448 }
449
450 return *this;
451 }
452
453#if ETL_USING_CPP11
454 //*************************************************************************
456 //*************************************************************************
458 {
459 if (&rhs != this)
460 {
461 clone(etl::move(rhs));
462 }
463
464 return *this;
465 }
466#endif
467
468 protected:
469
470 //*************************************************************************
472 //*************************************************************************
473 void clone(const istack& other)
474 {
475 clear();
476
477 size_t index = 0UL;
478
479 for (size_t i = 0UL; i < other.size(); ++i)
480 {
481 push(other.p_buffer[index++]);
482 }
483 }
484
485#if ETL_USING_CPP11
486 //*************************************************************************
488 //*************************************************************************
489 void clone(istack&& other)
490 {
491 clear();
492
493 size_t index = 0UL;
494
495 for (size_t i = 0UL; i < other.size(); ++i)
496 {
497 push(etl::move(other.p_buffer[index++]));
498 }
499 }
500#endif
501
502 //*************************************************************************
504 //*************************************************************************
507 p_buffer(p_buffer_)
508 {
509 }
510
511 private:
512
513 // Disable copy construction.
514 istack(const istack&);
515
516 T* p_buffer;
517
518 //*************************************************************************
520 //*************************************************************************
521#if defined(ETL_POLYMORPHIC_STACK) || defined(ETL_POLYMORPHIC_CONTAINERS)
522 public:
523 virtual ~istack()
524 {
525 }
526#else
527 protected:
529 {
530 }
531#endif
532 };
533
534 //***************************************************************************
540 //***************************************************************************
541 template <typename T, const size_t SIZE>
542 class stack : public etl::istack<T>
543 {
544 public:
545 typedef typename etl::aligned_storage<sizeof(T), etl::alignment_of<T>::value>::type container_type;
546
547 static ETL_CONSTANT size_t MAX_SIZE = SIZE;
548
549 //*************************************************************************
551 //*************************************************************************
553 : etl::istack<T>(reinterpret_cast<T*>(&buffer[0]), SIZE)
554 {
555 }
556
557 //*************************************************************************
559 //*************************************************************************
561 : etl::istack<T>(reinterpret_cast<T*>(&buffer[0]), SIZE)
562 {
564 }
565
566#if ETL_USING_CPP11
567 //*************************************************************************
569 //*************************************************************************
570 stack(stack&& rhs)
571 : etl::istack<T>(reinterpret_cast<T*>(&buffer[0]), SIZE)
572 {
573 etl::istack<T>::clone(etl::move(rhs));
574 }
575#endif
576
577 //*************************************************************************
579 //*************************************************************************
581 {
583 }
584
585 //*************************************************************************
587 //*************************************************************************
589 {
590 if (&rhs != this)
591 {
593 }
594
595 return *this;
596 }
597
598#if ETL_USING_CPP11
599 //*************************************************************************
601 //*************************************************************************
603 {
604 if (&rhs != this)
605 {
606 etl::istack<T>::clone(etl::move(rhs));
607 }
608
609 return *this;
610 }
611#endif
612
613 private:
614
616 container_type buffer[SIZE];
617 };
618
619 template <typename T, const size_t SIZE>
620 ETL_CONSTANT size_t stack<T, SIZE>::MAX_SIZE;
621}
622
623#endif
Definition alignment.h:231
#define ETL_ASSERT(b, e)
Definition error_handler.h:316
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:588
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:552
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:360
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:505
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()
Definition stack.h:300
void emplace(const T1 &value1)
Definition stack.h:315
void emplace(const T1 &value1, const T2 &value2)
Definition stack.h:330
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:401
istack & operator=(const istack &rhs)
Assignment operator.
Definition stack.h:442
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:345
T * pointer
A pointer to the type used in the stack.
Definition stack.h:230
~stack()
Destructor.
Definition stack.h:580
stack(const stack &rhs)
Copy constructor.
Definition stack.h:560
void pop_into(TContainer &destination)
Definition stack.h:425
void clone(const istack &other)
Make this a clone of the supplied stack.
Definition stack.h:473
~istack()
Destructor.
Definition stack.h:528
void pop_into(reference destination)
Removes the oldest item from the top of the stack and puts it in the destination.
Definition stack.h:413
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:382
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:434
const_reference top() const
Definition stack.h:374
This is the base for all stacks that contain a particular type.
Definition stack.h:221
Definition stack.h:543
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:233
Definition type_traits_generator.h:2101
pair holds two objects of arbitrary type
Definition utility.h:164