Loading...
Searching...
No Matches
stack.h
Go to the documentation of this file.
/******************************************************************************
The MIT License(MIT)
Embedded Template Library.
https://github.com/ETLCPP/etl
https://www.etlcpp.com
Copyright(c) 2014 John Wellbelove, Mark Kitson
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files(the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions :
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
******************************************************************************/
#ifndef ETL_STACK_INCLUDED
#define ETL_STACK_INCLUDED
#include "platform.h"
#include "algorithm.h"
#include "alignment.h"
#include "array.h"
#include "debug_count.h"
#include "error_handler.h"
#include "exception.h"
#include "iterator.h"
#include "placement_new.h"
#include "type_traits.h"
#include "utility.h"
#include <stddef.h>
//*****************************************************************************
//*****************************************************************************
namespace etl
{
//***************************************************************************
//***************************************************************************
class stack_exception : public exception
{
public:
stack_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
: exception(reason_, file_name_, line_number_)
{
}
};
//***************************************************************************
//***************************************************************************
class stack_full : public stack_exception
{
public:
stack_full(string_type file_name_, numeric_type line_number_)
: stack_exception(ETL_ERROR_TEXT("stack:full", ETL_STACK_FILE_ID"A"), file_name_, line_number_)
{
}
};
//***************************************************************************
//***************************************************************************
class stack_empty : public stack_exception
{
public:
stack_empty(string_type file_name_, numeric_type line_number_)
: stack_exception(ETL_ERROR_TEXT("stack:empty", ETL_STACK_FILE_ID"B"), file_name_, line_number_)
{
}
};
//***************************************************************************
//***************************************************************************
class stack_base
{
public:
typedef size_t size_type;
//*************************************************************************
//*************************************************************************
bool empty() const
{
return current_size == 0;
}
//*************************************************************************
//*************************************************************************
bool full() const
{
return current_size == CAPACITY;
}
//*************************************************************************
//*************************************************************************
size_type size() const
{
return current_size;
}
//*************************************************************************
//*************************************************************************
size_type max_size() const
{
return CAPACITY;
}
//*************************************************************************
//*************************************************************************
size_t available() const
{
return max_size() - size();
}
protected:
//*************************************************************************
//*************************************************************************
stack_base(size_type max_size_)
: top_index(0)
, current_size(0)
, CAPACITY(max_size_)
{
}
//*************************************************************************
//*************************************************************************
~stack_base() {}
//*************************************************************************
//*************************************************************************
void add_in()
{
top_index = current_size++;
ETL_INCREMENT_DEBUG_COUNT;
}
//*************************************************************************
//*************************************************************************
void del_out()
{
--top_index;
--current_size;
ETL_DECREMENT_DEBUG_COUNT;
}
//*************************************************************************
//*************************************************************************
void index_clear()
{
top_index = 0;
current_size = 0;
ETL_RESET_DEBUG_COUNT;
}
size_type top_index;
size_type current_size;
const size_type CAPACITY;
ETL_DECLARE_DEBUG_COUNT;
};
//***************************************************************************
//***************************************************************************
template <typename T>
class istack : public etl::stack_base
{
public:
typedef T value_type;
typedef T& reference;
typedef const T& const_reference;
#if ETL_USING_CPP11
typedef T&& rvalue_reference;
#endif
typedef T* pointer;
typedef const T* const_pointer;
typedef stack_base::size_type size_type;
private:
typedef typename etl::stack_base base_t;
public:
//*************************************************************************
//*************************************************************************
reference top()
{
ETL_ASSERT_CHECK_EXTRA(!empty(), ETL_ERROR(stack_empty));
return p_buffer[top_index];
}
//*************************************************************************
//*************************************************************************
void push(const_reference value)
{
ETL_ASSERT_CHECK_PUSH_POP_OR_RETURN(!full(), ETL_ERROR(stack_full));
base_t::add_in();
::new (&p_buffer[top_index]) T(value);
}
#if ETL_USING_CPP11
//*************************************************************************
//*************************************************************************
void push(rvalue_reference value)
{
ETL_ASSERT_CHECK_PUSH_POP_OR_RETURN(!full(), ETL_ERROR(stack_full));
base_t::add_in();
::new (&p_buffer[top_index]) T(etl::move(value));
}
#endif
#if ETL_USING_CPP11 && ETL_NOT_USING_STLPORT
//*************************************************************************
//*************************************************************************
template <typename... Args>
reference emplace(Args&&... args)
{
ETL_ASSERT_CHECK_PUSH_POP(!full(), ETL_ERROR(stack_full));
base_t::add_in();
::new (&p_buffer[top_index]) T(etl::forward<Args>(args)...);
return p_buffer[top_index];
}
#else
//*************************************************************************
//*************************************************************************
reference emplace()
{
ETL_ASSERT_CHECK_PUSH_POP(!full(), ETL_ERROR(stack_full));
base_t::add_in();
::new (&p_buffer[top_index]) T();
return p_buffer[top_index];
}
//*************************************************************************
//*************************************************************************
template <typename T1>
reference emplace(const T1& value1)
{
ETL_ASSERT_CHECK_PUSH_POP(!full(), ETL_ERROR(stack_full));
base_t::add_in();
::new (&p_buffer[top_index]) T(value1);
return p_buffer[top_index];
}
//*************************************************************************
//*************************************************************************
template <typename T1, typename T2>
reference emplace(const T1& value1, const T2& value2)
{
ETL_ASSERT_CHECK_PUSH_POP(!full(), ETL_ERROR(stack_full));
base_t::add_in();
::new (&p_buffer[top_index]) T(value1, value2);
return p_buffer[top_index];
}
//*************************************************************************
//*************************************************************************
template <typename T1, typename T2, typename T3>
reference emplace(const T1& value1, const T2& value2, const T3& value3)
{
ETL_ASSERT_CHECK_PUSH_POP(!full(), ETL_ERROR(stack_full));
base_t::add_in();
::new (&p_buffer[top_index]) T(value1, value2, value3);
return p_buffer[top_index];
}
//*************************************************************************
//*************************************************************************
template <typename T1, typename T2, typename T3, typename T4>
reference emplace(const T1& value1, const T2& value2, const T3& value3, const T4& value4)
{
ETL_ASSERT_CHECK_PUSH_POP(!full(), ETL_ERROR(stack_full));
base_t::add_in();
::new (&p_buffer[top_index]) T(value1, value2, value3, value4);
return p_buffer[top_index];
}
#endif
//*************************************************************************
//*************************************************************************
const_reference top() const
{
ETL_ASSERT_CHECK_EXTRA(!empty(), ETL_ERROR(stack_empty));
return p_buffer[top_index];
}
//*************************************************************************
//*************************************************************************
void clear()
{
if ETL_IF_CONSTEXPR (etl::is_trivially_destructible<T>::value)
{
base_t::index_clear();
}
else
{
while (current_size > 0)
{
p_buffer[top_index].~T();
base_t::del_out();
}
}
}
//*************************************************************************
//*************************************************************************
void pop()
{
ETL_ASSERT_CHECK_PUSH_POP_OR_RETURN(!empty(), ETL_ERROR(stack_empty));
p_buffer[top_index].~T();
base_t::del_out();
}
//*************************************************************************
//*************************************************************************
void pop_into(reference destination)
{
destination = ETL_MOVE(top());
pop();
}
//*************************************************************************
//*************************************************************************
template <typename TContainer>
void pop_into(TContainer& destination)
{
destination.push(ETL_MOVE(top()));
pop();
}
//*************************************************************************
//*************************************************************************
void reverse()
{
etl::reverse(p_buffer, p_buffer + current_size);
}
//*************************************************************************
//*************************************************************************
istack& operator=(const istack& rhs)
{
if (&rhs != this)
{
clear();
clone(rhs);
}
return *this;
}
#if ETL_USING_CPP11
//*************************************************************************
//*************************************************************************
istack& operator=(istack&& rhs)
{
if (&rhs != this)
{
clone(etl::move(rhs));
}
return *this;
}
#endif
protected:
//*************************************************************************
//*************************************************************************
void clone(const istack& other)
{
clear();
size_t index = 0UL;
for (size_t i = 0UL; i < other.size(); ++i)
{
push(other.p_buffer[index++]);
}
}
#if ETL_USING_CPP11
//*************************************************************************
//*************************************************************************
void clone(istack&& other)
{
clear();
size_t index = 0UL;
for (size_t i = 0UL; i < other.size(); ++i)
{
push(etl::move(other.p_buffer[index++]));
}
}
#endif
//*************************************************************************
//*************************************************************************
istack(T* p_buffer_, size_type max_size_)
: stack_base(max_size_)
, p_buffer(p_buffer_)
{
}
private:
// Disable copy construction.
istack(const istack&);
T* p_buffer;
//*************************************************************************
//*************************************************************************
#if defined(ETL_POLYMORPHIC_STACK) || defined(ETL_POLYMORPHIC_CONTAINERS)
public:
virtual ~istack() {}
#else
protected:
~istack() {}
#endif
};
//***************************************************************************
//***************************************************************************
template <typename T, const size_t SIZE>
class stack : public etl::istack<T>
{
public:
typedef typename etl::aligned_storage< sizeof(T), etl::alignment_of<T>::value>::type container_type;
static ETL_CONSTANT size_t MAX_SIZE = SIZE;
//*************************************************************************
//*************************************************************************
stack()
: etl::istack<T>(reinterpret_cast<T*>(&buffer[0]), SIZE)
{
}
//*************************************************************************
//*************************************************************************
stack(const stack& rhs)
: etl::istack<T>(reinterpret_cast<T*>(&buffer[0]), SIZE)
{
etl::istack<T>::clone(rhs);
}
#if ETL_USING_CPP11
//*************************************************************************
//*************************************************************************
stack(stack&& rhs)
: etl::istack<T>(reinterpret_cast<T*>(&buffer[0]), SIZE)
{
etl::istack<T>::clone(etl::move(rhs));
}
#endif
//*************************************************************************
//*************************************************************************
~stack()
{
etl::istack<T>::clear();
}
//*************************************************************************
//*************************************************************************
stack& operator=(const stack& rhs)
{
if (&rhs != this)
{
etl::istack<T>::clone(rhs);
}
return *this;
}
#if ETL_USING_CPP11
//*************************************************************************
//*************************************************************************
stack& operator=(stack&& rhs)
{
if (&rhs != this)
{
etl::istack<T>::clone(etl::move(rhs));
}
return *this;
}
#endif
private:
container_type buffer[SIZE];
};
template <typename T, const size_t SIZE>
ETL_CONSTANT size_t stack<T, SIZE>::MAX_SIZE;
} // namespace etl
#endif
algorithm.h
alignment.h
array.h
debug_count.h
error_handler.h
exception.h
etl::aligned_storage
Definition alignment.h:251
etl::exception::exception
ETL_EXCEPTION_CONSTEXPR exception(string_type reason_, string_type, numeric_type)
Constructor.
Definition exception.h:81
etl::stack_base::ETL_DECLARE_DEBUG_COUNT
ETL_DECLARE_DEBUG_COUNT
For internal debugging purposes.
Definition stack.h:203
etl::stack_base::del_out
void del_out()
Decrements the indexes value to record a queue deletion.
Definition stack.h:183
etl::stack::operator=
stack & operator=(const stack &rhs)
Assignment operator.
Definition stack.h:605
etl::istack::top
reference top()
Definition stack.h:244
etl::stack_base::empty
bool empty() const
Definition stack.h:115
etl::stack_base::~stack_base
~stack_base()
Destructor.
Definition stack.h:169
etl::stack::stack
stack()
Default constructor.
Definition stack.h:569
etl::stack_base::stack_base
stack_base(size_type max_size_)
The constructor that is called from derived classes.
Definition stack.h:159
etl::stack_base::full
bool full() const
Definition stack.h:124
etl::istack::const_pointer
const T * const_pointer
A const pointer to the type used in the stack.
Definition stack.h:229
etl::stack_base::CAPACITY
const size_type CAPACITY
The maximum number of items in the stack.
Definition stack.h:202
etl::stack_base::index_clear
void index_clear()
Clears all of the indexes.
Definition stack.h:193
etl::stack_base::size
size_type size() const
Returns the current number of items top the stack.
Definition stack.h:132
etl::istack::emplace
reference emplace(const T1 &value1, const T2 &value2)
Definition stack.h:338
etl::istack::emplace
reference emplace(const T1 &value1)
Definition stack.h:321
etl::istack::istack
istack(T *p_buffer_, size_type max_size_)
The constructor that is called from derived classes.
Definition stack.h:521
etl::stack_base::max_size
size_type max_size() const
Returns the maximum number of items that can be stacked.
Definition stack.h:140
etl::stack_base::current_size
size_type current_size
The number of items in the stack.
Definition stack.h:201
etl::istack::emplace
reference emplace()
Definition stack.h:304
etl::stack_base::available
size_t available() const
Definition stack.h:149
etl::istack::push
void push(const_reference value)
Definition stack.h:256
etl::istack::pop
void pop()
Removes the oldest item from the top of the stack.
Definition stack.h:417
etl::istack::operator=
istack & operator=(const istack &rhs)
Assignment operator.
Definition stack.h:458
etl::stack_base::top_index
size_type top_index
The index of the top of the stack.
Definition stack.h:200
etl::stack_base::size_type
size_t size_type
The type used for determining the size of stack.
Definition stack.h:109
etl::istack::emplace
reference emplace(const T1 &value1, const T2 &value2, const T3 &value3, const T4 &value4)
Definition stack.h:372
etl::istack::reference
T & reference
A reference to the type used in the stack.
Definition stack.h:223
etl::istack::emplace
reference emplace(const T1 &value1, const T2 &value2, const T3 &value3)
Definition stack.h:355
etl::istack::pointer
T * pointer
A pointer to the type used in the stack.
Definition stack.h:228
etl::stack::~stack
~stack()
Destructor.
Definition stack.h:597
etl::stack::stack
stack(const stack &rhs)
Copy constructor.
Definition stack.h:577
etl::istack::pop_into
void pop_into(TContainer &destination)
Definition stack.h:441
etl::istack::clone
void clone(const istack &other)
Make this a clone of the supplied stack.
Definition stack.h:489
etl::istack::~istack
~istack()
Destructor.
Definition stack.h:546
etl::istack::pop_into
void pop_into(reference destination)
Definition stack.h:429
etl::istack::const_reference
const T & const_reference
A const reference to the type used in the stack.
Definition stack.h:224
etl::stack_base::add_in
void add_in()
Increments the indexes value to record a stack addition.
Definition stack.h:174
etl::istack::clear
void clear()
Clears the stack to the empty state.
Definition stack.h:398
etl::istack::size_type
stack_base::size_type size_type
The type used for determining the size of the stack.
Definition stack.h:230
etl::istack::value_type
T value_type
The type stored in the stack.
Definition stack.h:222
etl::istack::reverse
void reverse()
Reverses the stack.
Definition stack.h:450
etl::istack::top
const_reference top() const
Definition stack.h:389
etl::istack
This is the base for all stacks that contain a particular type.
Definition stack.h:219
etl::stack
Definition stack.h:559
etl::stack_base
Definition stack.h:106
etl::stack_empty
Definition stack.h:90
etl::stack_full
Definition stack.h:76
iterator.h
etl
Definition absolute.h:40
placement_new.h
platform.h
etl::type
type_traits.h
utility.h