intrusive_stack.h

00001 ///\file
00002 
00003 /******************************************************************************
00004 The MIT License(MIT)
00005 
00006 Embedded Template Library.
00007 https://github.com/ETLCPP/etl
00008 http://www.etlcpp.com
00009 
00010 Copyright(c) 2016 jwellbelove
00011 
00012 Permission is hereby granted, free of charge, to any person obtaining a copy
00013 of this software and associated documentation files(the "Software"), to deal
00014 in the Software without restriction, including without limitation the rights
00015 to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
00016 copies of the Software, and to permit persons to whom the Software is
00017 furnished to do so, subject to the following conditions :
00018 
00019 The above copyright notice and this permission notice shall be included in all
00020 copies or substantial portions of the Software.
00021 
00022 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
00023 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
00024 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
00025 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
00026 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
00027 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
00028 SOFTWARE.
00029 ******************************************************************************/
00030 
00031 #ifndef __ETL_INTRUSIVE_STACK__
00032 #define __ETL_INTRUSIVE_STACK__
00033 
00034 #include <stddef.h>
00035 
00036 #include "platform.h "
00037 #include "type_traits.h "
00038 #include "error_handler.h "
00039 #include "intrusive_links.h "
00040 
00041 #define ETL_FILE "28"
00042 
00043 namespace etl
00044 {
00045   //***************************************************************************
00046   /// Exception base for intrusive stack
00047   ///\ingroup intrusive_stack
00048   //***************************************************************************
00049   class intrusive_stack_exception : public etl::exception
00050   {
00051   public:
00052 
00053     intrusive_stack_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
00054       : exception(reason_, file_name_, line_number_)
00055     {
00056     }
00057   };
00058 
00059   //***************************************************************************
00060   /// intrusive_stack empty exception.
00061   ///\ingroup intrusive_stack
00062   //***************************************************************************
00063   class intrusive_stack_empty : public intrusive_stack_exception
00064   {
00065   public:
00066 
00067     intrusive_stack_empty(string_type file_name_, numeric_type line_number_)
00068       : intrusive_stack_exception(ETL_ERROR_TEXT("intrusive_stack:empty", ETL_FILE"A"), file_name_, line_number_)
00069     {
00070     }
00071   };
00072 
00073   //***************************************************************************
00074   ///\ingroup stack
00075   /// Base for intrusive stack. Stores elements derived any type that supports an 'etl_next' pointer member.
00076   /// \tparam TLink  The link type that the value is derived from.
00077   //***************************************************************************
00078   template <typename TLink>
00079   class intrusive_stack_base
00080   {
00081   public:
00082 
00083     // Node typedef.
00084     typedef TLink  link_type;
00085 
00086     //*************************************************************************
00087     /// Adds a value to the stack.
00088     ///\param value The value to push to the stack.
00089     //*************************************************************************
00090     void push(link_type& value)
00091     {
00092       value.clear();
00093 
00094       if (p_top != std::nullptr)
00095       {
00096         etl::link(value, p_top);
00097       }
00098 
00099       p_top = &value;
00100 
00101       ++current_size;
00102     }
00103 
00104     //*************************************************************************
00105     /// Removes the oldest item from the top of the stack.
00106     /// Undefined behaviour if the stack is already empty.
00107     //*************************************************************************
00108     void pop()
00109     {
00110 #if defined(ETL_CHECK_PUSH_POP)
00111       ETL_ASSERT(!empty(), ETL_ERROR(intrusive_stack_empty));
00112 #endif
00113       link_type* p_next = p_top->etl_next;
00114       p_top = p_next;
00115       --current_size;
00116     }
00117 
00118     //*************************************************************************
00119     /// Removes the oldest item from the queue and pushes it to the destination.
00120     /// Undefined behaviour if the queue is already empty.
00121     /// NOTE: The destination must be an intrusize container that supports a push(TLink) member function.
00122     //*************************************************************************
00123     template <typename TContainer>
00124     void pop_into(TContainer& destination)
00125     {
00126       link_type* p_link = p_top;
00127       pop();
00128       destination.push(*p_link);
00129     }
00130 
00131     //*************************************************************************
00132     /// Reverses the stack order.
00133     //*************************************************************************
00134     void reverse()
00135     {
00136       link_type* previous = std::nullptr;
00137       link_type* current = p_top;
00138       link_type* next;
00139 
00140       while (current != std::nullptr)
00141       {
00142         next = current->etl_next;
00143         current->etl_next = previous;
00144         previous = current;
00145         current = next;
00146       }
00147 
00148       p_top = previous;
00149     }
00150 
00151     //*************************************************************************
00152     /// Clears the stack to the empty state.
00153     //*************************************************************************
00154     void clear()
00155     {
00156       while (!empty())
00157       {
00158         pop();
00159       }
00160 
00161       current_size = 0;
00162     }
00163 
00164     //*************************************************************************
00165     /// Checks if the stack is in the empty state.
00166     //*************************************************************************
00167     bool empty() const
00168     {
00169       return current_size == 0;
00170     }
00171 
00172     //*************************************************************************
00173     /// Returns the number of elements.
00174     //*************************************************************************
00175     size_t size() const
00176     {
00177       return current_size;
00178     }
00179 
00180   protected:
00181 
00182     //*************************************************************************
00183     /// Constructor
00184     //*************************************************************************
00185     intrusive_stack_base()
00186       : p_top(std::nullptr),
00187         current_size(0)
00188     {
00189     }
00190 
00191     link_type* p_top; ///< The current top of the stack.
00192 
00193     size_t current_size; ///< Counts the number of elements in the list.
00194   };
00195 
00196   //***************************************************************************
00197   ///\ingroup stack
00198   /// An intrusive stack. Stores elements derived from any type that supports an 'etl_next' pointer member.
00199   /// \warning This stack cannot be used for concurrent access from multiple threads.
00200   /// \tparam TValue The type of value that the stack holds.
00201   /// \tparam TLink  The link type that the value is derived from.
00202   //***************************************************************************
00203   template <typename TValue, typename TLink>
00204   class intrusive_stack : public etl::intrusive_stack_base<TLink>
00205   {
00206   public:
00207 
00208     // Node typedef.
00209     typedef typename etl::intrusive_stack_base<TLink>::link_type link_type;
00210 
00211     // STL style typedefs.
00212     typedef TValue            value_type;
00213     typedef value_type*       pointer;
00214     typedef const value_type* const_pointer;
00215     typedef value_type&       reference;
00216     typedef const value_type& const_reference;
00217     typedef size_t            size_type;
00218 
00219     //*************************************************************************
00220     /// Constructor
00221     //*************************************************************************
00222     intrusive_stack()
00223     : intrusive_stack_base<TLink>()
00224     {
00225     }
00226 
00227     //*************************************************************************
00228     /// Gets a reference to the value at the top of the stack.
00229     /// Undefined behaviour if the stack is empty.
00230     /// \return A reference to the value at the top of the stack.
00231     //*************************************************************************
00232     reference top()
00233     {
00234       return *static_cast<TValue*>(this->p_top);
00235     }
00236 
00237     //*************************************************************************
00238     /// Gets a const reference to the value at the top of the stack.<br>
00239     /// \return A const reference to the value at the top of the stack.
00240     //*************************************************************************
00241     const_reference top() const
00242     {
00243       return *static_cast<const TValue*>(this->p_top);
00244     }
00245 
00246   private:
00247 
00248     // Disable copy construction and assignment.
00249     intrusive_stack(const intrusive_stack&);
00250     intrusive_stack& operator = (const intrusive_stack& rhs);
00251   };
00252 }
00253 
00254 #undef ETL_FILE
00255 
00256 #endif
00257