Loading...
Searching...
No Matches
intrusive_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) 2016 John Wellbelove
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_INTRUSIVE_STACK_INCLUDED
#define ETL_INTRUSIVE_STACK_INCLUDED
#include "platform.h"
#include "error_handler.h"
#include "intrusive_links.h"
#include "type_traits.h"
#include <stddef.h>
namespace etl
{
//***************************************************************************
//***************************************************************************
class intrusive_stack_exception : public etl::exception
{
public:
intrusive_stack_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
: exception(reason_, file_name_, line_number_)
{
}
};
//***************************************************************************
//***************************************************************************
class intrusive_stack_empty : public intrusive_stack_exception
{
public:
intrusive_stack_empty(string_type file_name_, numeric_type line_number_)
: intrusive_stack_exception(ETL_ERROR_TEXT("intrusive_stack:empty", ETL_INTRUSIVE_STACK_FILE_ID"A"), file_name_, line_number_)
{
}
};
//***************************************************************************
//***************************************************************************
class intrusive_stack_value_is_already_linked : public intrusive_stack_exception
{
public:
intrusive_stack_value_is_already_linked(string_type file_name_, numeric_type line_number_)
: intrusive_stack_exception(ETL_ERROR_TEXT("intrusive_stack:value is already linked", ETL_INTRUSIVE_STACK_FILE_ID"B"), file_name_, line_number_)
{
}
};
//***************************************************************************
//***************************************************************************
template <typename TLink>
class intrusive_stack_base
{
public:
// Node typedef.
typedef TLink link_type;
//*************************************************************************
//*************************************************************************
void push(link_type& value)
{
ETL_ASSERT_OR_RETURN(!value.is_linked(), ETL_ERROR(intrusive_stack_value_is_already_linked));
value.etl_next = p_top;
p_top = &value;
++current_size;
}
//*************************************************************************
//*************************************************************************
void pop()
{
ETL_ASSERT_CHECK_PUSH_POP_OR_RETURN(!empty(), ETL_ERROR(intrusive_stack_empty));
link_type* p_next = p_top->etl_next;
p_top->clear();
p_top = p_next;
--current_size;
}
//*************************************************************************
//*************************************************************************
template <typename TContainer>
void pop_into(TContainer& destination)
{
link_type* p_link = p_top;
pop();
destination.push(*p_link);
}
//*************************************************************************
//*************************************************************************
void reverse()
{
link_type* previous = &terminator;
link_type* current = p_top;
link_type* next;
while (current != &terminator)
{
next = current->etl_next;
current->etl_next = previous;
previous = current;
current = next;
}
p_top = previous;
}
//*************************************************************************
//*************************************************************************
void clear()
{
while (!empty())
{
pop();
}
current_size = 0;
}
//*************************************************************************
//*************************************************************************
bool empty() const
{
return current_size == 0;
}
//*************************************************************************
//*************************************************************************
size_t size() const
{
return current_size;
}
protected:
//*************************************************************************
//*************************************************************************
intrusive_stack_base()
: p_top(&terminator)
, current_size(0)
{
}
//*************************************************************************
//*************************************************************************
~intrusive_stack_base() {}
link_type* p_top;
link_type terminator;
size_t current_size;
};
//***************************************************************************
//***************************************************************************
template <typename TValue, typename TLink>
class intrusive_stack : public etl::intrusive_stack_base<TLink>
{
public:
// Node typedef.
typedef typename etl::intrusive_stack_base<TLink>::link_type link_type;
// STL style typedefs.
typedef TValue value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef size_t size_type;
//*************************************************************************
//*************************************************************************
intrusive_stack()
: intrusive_stack_base<TLink>()
{
}
//*************************************************************************
//*************************************************************************
reference top()
{
ETL_ASSERT_CHECK_EXTRA(!this->empty(), ETL_ERROR(intrusive_stack_empty));
return *static_cast<TValue*>(this->p_top);
}
//*************************************************************************
//*************************************************************************
const_reference top() const
{
ETL_ASSERT_CHECK_EXTRA(!this->empty(), ETL_ERROR(intrusive_stack_empty));
return *static_cast<const TValue*>(this->p_top);
}
private:
// Disable copy construction and assignment.
intrusive_stack(const intrusive_stack&);
intrusive_stack& operator=(const intrusive_stack& rhs);
};
} // namespace etl
#endif
etl::intrusive_stack_empty
Definition intrusive_stack.h:62
etl::intrusive_stack_value_is_already_linked
Definition intrusive_stack.h:76
error_handler.h
etl::exception::exception
ETL_EXCEPTION_CONSTEXPR exception(string_type reason_, string_type, numeric_type)
Constructor.
Definition exception.h:81
etl::exception
Definition exception.h:59
etl::intrusive_stack_base::pop
void pop()
Definition intrusive_stack.h:117
etl::intrusive_stack_base::size
size_t size() const
Returns the number of elements.
Definition intrusive_stack.h:185
etl::intrusive_stack::top
reference top()
Definition intrusive_stack.h:250
etl::intrusive_stack_base::reverse
void reverse()
Reverses the stack order.
Definition intrusive_stack.h:144
etl::intrusive_stack_base::clear
void clear()
Clears the stack to the empty state.
Definition intrusive_stack.h:164
etl::intrusive_stack::top
const_reference top() const
Definition intrusive_stack.h:262
etl::intrusive_stack_base::~intrusive_stack_base
~intrusive_stack_base()
Destructor.
Definition intrusive_stack.h:204
etl::intrusive_stack_base::pop_into
void pop_into(TContainer &destination)
Definition intrusive_stack.h:134
etl::intrusive_stack::intrusive_stack
intrusive_stack()
Constructor.
Definition intrusive_stack.h:239
etl::link_type::current_size
size_t current_size
Definition intrusive_stack.h:209
etl::intrusive_stack_base::empty
bool empty() const
Checks if the stack is in the empty state.
Definition intrusive_stack.h:177
etl::link_type::p_top
link_type * p_top
Definition intrusive_stack.h:206
etl::link_type::terminator
link_type terminator
Definition intrusive_stack.h:207
etl::intrusive_stack_base::push
void push(link_type &value)
Definition intrusive_stack.h:103
etl::intrusive_stack_base::intrusive_stack_base
intrusive_stack_base()
Constructor.
Definition intrusive_stack.h:195
etl::intrusive_stack
Definition intrusive_stack.h:222
etl::intrusive_stack_base
Definition intrusive_stack.h:93
intrusive_links.h
etl
Definition absolute.h:40
platform.h
type_traits.h