intrusive_queue.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_QUEUE__
00032 #define __ETL_INTRUSIVE_QUEUE__
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 "29"
00042 
00043 namespace etl
00044 {
00045   //***************************************************************************
00046   /// Exception base for intrusive queue
00047   ///\ingroup intrusive_queue
00048   //***************************************************************************
00049   class intrusive_queue_exception : public etl::exception
00050   {
00051   public:
00052 
00053     intrusive_queue_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_queue empty exception.
00061   ///\ingroup intrusive_queue
00062   //***************************************************************************
00063   class intrusive_queue_empty : public intrusive_queue_exception
00064   {
00065   public:
00066 
00067     intrusive_queue_empty(string_type file_name_, numeric_type line_number_)
00068       : intrusive_queue_exception(ETL_ERROR_TEXT("intrusive_queue:empty", ETL_FILE"A"), file_name_, line_number_)
00069     {
00070     }
00071   };
00072 
00073   //***************************************************************************
00074   ///\ingroup queue
00075   /// Base for intrusive queue. 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_queue_base
00080   {
00081   public:
00082 
00083     // Node typedef.
00084     typedef TLink link_type;
00085 
00086     //*************************************************************************
00087     /// Adds a value to the queue.
00088     ///\param value The value to push to the queue.
00089     //*************************************************************************
00090     void push(link_type& value)
00091     {
00092       value.clear();
00093 
00094       if (p_back != std::nullptr)
00095       {
00096         etl::link(p_back, value);
00097       }
00098       else
00099       {
00100         p_front = &value;
00101       }
00102 
00103       p_back = &value;
00104 
00105       ++current_size;
00106     }
00107 
00108     //*************************************************************************
00109     /// Removes the oldest item from the queue.
00110     /// Undefined behaviour if the queue is already empty.
00111     //*************************************************************************
00112     void pop()
00113     {
00114 #if defined(ETL_CHECK_PUSH_POP)
00115       ETL_ASSERT(!empty(), ETL_ERROR(intrusive_queue_empty));
00116 #endif
00117       link_type* p_next = p_front->etl_next;
00118 
00119       p_front = p_next;
00120 
00121       // Now empty?
00122       if (p_front == std::nullptr)
00123       {
00124         p_back = std::nullptr;
00125       }
00126 
00127       --current_size;
00128     }
00129 
00130     //*************************************************************************
00131     /// Removes the oldest item from the queue and pushes it to the destination.
00132     /// Undefined behaviour if the queue is already empty.
00133     /// NOTE: The destination must be an intrusize container that supports a push(TLink) member function.
00134     //*************************************************************************
00135     template <typename TContainer>
00136     void pop_into(TContainer& destination)
00137     {
00138       link_type* p_link = p_front;
00139       pop();
00140       destination.push(*p_link);
00141     }
00142 
00143     //*************************************************************************
00144     /// Clears the queue to the empty state.
00145     //*************************************************************************
00146     void clear()
00147     {
00148       while (!empty())
00149       {
00150         pop();
00151       }
00152 
00153       current_size = 0;
00154     }
00155 
00156     //*************************************************************************
00157     /// Checks if the queue is in the empty state.
00158     //*************************************************************************
00159     bool empty() const
00160     {
00161       return current_size == 0;
00162     }
00163 
00164     //*************************************************************************
00165     /// Returns the number of elements.
00166     //*************************************************************************
00167     size_t size() const
00168     {
00169       return current_size;
00170     }
00171 
00172   protected:
00173 
00174     //*************************************************************************
00175     /// Constructor
00176     //*************************************************************************
00177     intrusive_queue_base()
00178       : p_front(std::nullptr),
00179         p_back(std::nullptr),
00180         current_size(0)
00181     {
00182     }
00183 
00184     link_type* p_front; ///< The current front of the queue.
00185     link_type* p_back;  ///< The current back of the queue.
00186 
00187     size_t current_size; ///< Counts the number of elements in the list.
00188   };
00189 
00190   //***************************************************************************
00191   ///\ingroup queue
00192   /// An intrusive queue. Stores elements derived from any type that supports an 'etl_next' pointer member.
00193   /// \warning This queue cannot be used for concurrent access from multiple threads.
00194   /// \tparam TValue The type of value that the queue holds.
00195   /// \tparam TLink  The link type that the value is derived from.
00196   //***************************************************************************
00197   template <typename TValue, typename TLink>
00198   class intrusive_queue : public etl::intrusive_queue_base<TLink>
00199   {
00200   public:
00201 
00202     // Node typedef.
00203     typedef typename etl::intrusive_queue_base<TLink> link_type;
00204 
00205     // STL style typedefs.
00206     typedef TValue            value_type;
00207     typedef value_type*       pointer;
00208     typedef const value_type* const_pointer;
00209     typedef value_type&       reference;
00210     typedef const value_type& const_reference;
00211     typedef size_t            size_type;
00212 
00213     //*************************************************************************
00214     /// Constructor
00215     //*************************************************************************
00216     intrusive_queue()
00217       : intrusive_queue_base<TLink>()
00218     {
00219     }
00220 
00221     //*************************************************************************
00222     /// Gets a reference to the value at the front of the queue.
00223     /// Undefined behaviour if the queue is empty.
00224     /// \return A reference to the value at the front of the queue.
00225     //*************************************************************************
00226     reference front()
00227     {
00228       return *static_cast<TValue*>(this->p_front);
00229     }
00230 
00231     //*************************************************************************
00232     /// Gets a reference to the value at the back of the queue.
00233     /// Undefined behaviour if the queue is empty.
00234     /// \return A reference to the value at the back of the queue.
00235     //*************************************************************************
00236     reference back()
00237     {
00238       return *static_cast<TValue*>(this->p_back);
00239     }
00240 
00241     //*************************************************************************
00242     /// Gets a const reference to the value at the front of the queue.
00243     /// Undefined behaviour if the queue is empty.
00244     /// \return A const reference to the value at the front of the queue.
00245     //*************************************************************************
00246     const_reference front() const
00247     {
00248       return *static_cast<const TValue*>(this->p_front);
00249     }
00250 
00251     //*************************************************************************
00252     /// Gets a reference to the value at the back of the queue.
00253     /// Undefined behaviour if the queue is empty.
00254     /// \return A reference to the value at the back of the queue.
00255     //*************************************************************************
00256     const_reference back() const
00257     {
00258       return *static_cast<const TValue*>(this->p_back);
00259     }
00260 
00261   private:
00262 
00263     // Disable copy construction and assignment.
00264     intrusive_queue(const intrusive_queue&);
00265     intrusive_queue& operator = (const intrusive_queue& rhs);
00266   };
00267 }
00268 
00269 #undef ETL_FILE
00270 
00271 #endif
00272