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) 2014 jwellbelove, Mark Kitson
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_QUEUE__
00032 #define __ETL_QUEUE__
00033 
00034 #include <stddef.h>
00035 #include <stdint.h>
00036 
00037 #include "platform.h "
00038 #include "container.h "
00039 #include "alignment.h "
00040 #include "array.h "
00041 #include "exception.h "
00042 #include "error_handler.h "
00043 #include "debug_count.h "
00044 #include "type_traits.h "
00045 #include "parameter_type.h "
00046 
00047 #undef ETL_FILE
00048 #define ETL_FILE "13"
00049 
00050 //*****************************************************************************
00051 ///\defgroup queue queue
00052 /// A First-in / first-out queue with the capacity defined at compile time,
00053 /// written in the STL style.
00054 ///\ingroup containers
00055 //*****************************************************************************
00056 
00057 namespace etl
00058 {
00059   //***************************************************************************
00060   /// The base class for queue exceptions.
00061   ///\ingroup queue
00062   //***************************************************************************
00063   class queue_exception : public exception
00064   {
00065   public:
00066 
00067     queue_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
00068       : exception(reason_, file_name_, line_number_)
00069     {
00070     }
00071   };
00072 
00073   //***************************************************************************
00074   /// The exception thrown when the queue is full.
00075   ///\ingroup queue
00076   //***************************************************************************
00077   class queue_full : public queue_exception
00078   {
00079   public:
00080 
00081     queue_full(string_type file_name_, numeric_type line_number_)
00082       : queue_exception(ETL_ERROR_TEXT("queue:full", ETL_FILE"A"), file_name_, line_number_)
00083     {
00084     }
00085   };
00086 
00087   //***************************************************************************
00088   /// The exception thrown when the queue is empty.
00089   ///\ingroup queue
00090   //***************************************************************************
00091   class queue_empty : public queue_exception
00092   {
00093   public:
00094 
00095     queue_empty(string_type file_name_, numeric_type line_number_)
00096       : queue_exception(ETL_ERROR_TEXT("queue:empty", ETL_FILE"B"), file_name_, line_number_)
00097     {
00098     }
00099   };
00100 
00101   //***************************************************************************
00102   /// The base class for all queues.
00103   ///\ingroup queue
00104   //***************************************************************************
00105   class queue_base
00106   {
00107   public:
00108 
00109     typedef size_t size_type; ///< The type used for determining the size of queue.
00110 
00111     //*************************************************************************
00112     /// Returns the current number of items in the queue.
00113     //*************************************************************************
00114     size_type size() const
00115     {
00116       return current_size;
00117     }
00118 
00119     //*************************************************************************
00120     /// Returns the maximum number of items that can be queued.
00121     //*************************************************************************
00122     size_type max_size() const
00123     {
00124       return CAPACITY;
00125     }
00126 
00127     //*************************************************************************
00128     /// Checks to see if the queue is empty.
00129     /// \return <b>true</b> if the queue is empty, otherwise <b>false</b>
00130     //*************************************************************************
00131     bool empty() const
00132     {
00133       return current_size == 0;
00134     }
00135 
00136     //*************************************************************************
00137     /// Checks to see if the queue is full.
00138     /// \return <b>true</b> if the queue is full, otherwise <b>false</b>
00139     //*************************************************************************
00140     bool full() const
00141     {
00142       return current_size == CAPACITY;
00143     }
00144 
00145     //*************************************************************************
00146     /// Returns the remaining capacity.
00147     ///\return The remaining capacity.
00148     //*************************************************************************
00149     size_t available() const
00150     {
00151       return max_size() - size();
00152     }
00153 
00154   protected:
00155 
00156     //*************************************************************************
00157     /// The constructor that is called from derived classes.
00158     //*************************************************************************
00159     queue_base(size_type max_size_)
00160       : in(0),
00161         out(0),
00162         current_size(0),
00163         CAPACITY(max_size_)
00164     {
00165     }
00166 
00167     //*************************************************************************
00168     /// Increments (and wraps) the 'in' index value to record a queue addition.
00169     //*************************************************************************
00170     void add_in()
00171     {
00172       if (++in == CAPACITY)
00173       {
00174         in = 0;
00175       }
00176 
00177       ++current_size;
00178       ++construct_count;
00179     }
00180 
00181     //*************************************************************************
00182     /// Decrements (and wraps) the 'out' index value to record a queue deletion.
00183     //*************************************************************************
00184     void del_out()
00185     {
00186       if (++out == CAPACITY)
00187       {
00188         out = 0;
00189       }
00190       --current_size;
00191       --construct_count;
00192     }
00193 
00194     size_type in;                     ///< Where to input new data.
00195     size_type out;                    ///< Where to get the oldest data.
00196     size_type current_size;           ///< The number of items in the queue.
00197     const size_type CAPACITY;         ///< The maximum number of items in the queue.
00198     etl::debug_count construct_count; ///< For internal debugging purposes.
00199   };
00200 
00201   //***************************************************************************
00202   ///\ingroup queue
00203   ///\brief This is the base for all queues that contain a particular type.
00204   ///\details Normally a reference to this type will be taken from a derived queue.
00205   ///\code
00206   /// etl::queue<int, 10> myQueue;
00207   /// etl::iqueue<int>& iQueue = myQueue;
00208   ///\endcode
00209   /// \warning This queue cannot be used for concurrent access from multiple threads.
00210   /// \tparam T The type of value that the queue holds.
00211   //***************************************************************************
00212   template <typename T>
00213   class iqueue : public etl::queue_base
00214   {
00215   public:
00216 
00217     typedef T                     value_type;      ///< The type stored in the queue.
00218     typedef T&                    reference;       ///< A reference to the type used in the queue.
00219     typedef const T&              const_reference; ///< A const reference to the type used in the queue.
00220     typedef T*                    pointer;         ///< A pointer to the type used in the queue.
00221     typedef const T*              const_pointer;   ///< A const pointer to the type used in the queue.
00222     typedef queue_base::size_type size_type;       ///< The type used for determining the size of the queue.
00223 
00224   private:
00225 
00226     typedef typename etl::parameter_type<T>::type parameter_t;
00227     typedef typename etl::queue_base              base_t;
00228 
00229   public:
00230 
00231     //*************************************************************************
00232     /// Gets a reference to the value at the front of the queue.<br>
00233     /// \return A reference to the value at the front of the queue.
00234     //*************************************************************************
00235     reference front()
00236     {
00237       return p_buffer[out];
00238     }
00239 
00240     //*************************************************************************
00241     /// Gets a const reference to the value at the front of the queue.<br>
00242     /// \return A const reference to the value at the front of the queue.
00243     //*************************************************************************
00244     const_reference front() const
00245     {
00246       return p_buffer[out];
00247     }
00248 
00249     //*************************************************************************
00250     /// Gets a reference to the value at the back of the queue.<br>
00251     /// \return A reference to the value at the back of the queue.
00252     //*************************************************************************
00253     reference back()
00254     {
00255       return p_buffer[in == 0 ? CAPACITY - 1 : in - 1];
00256     }
00257 
00258     //*************************************************************************
00259     /// Gets a const reference to the value at the back of the queue.<br>
00260     /// \return A const reference to the value at the back of the queue.
00261     //*************************************************************************
00262     const_reference back() const
00263     {
00264       return p_buffer[in == 0 ? CAPACITY - 1 : in - 1];
00265     }
00266 
00267     //*************************************************************************
00268     /// Adds a value to the queue.
00269     /// If asserts or exceptions are enabled, throws an etl::queue_full if the queue if already full.
00270     ///\param value The value to push to the queue.
00271     //*************************************************************************
00272     void push(parameter_t value)
00273     {
00274 #if defined(ETL_CHECK_PUSH_POP)
00275       ETL_ASSERT(!full(), ETL_ERROR(queue_full));
00276 #endif
00277       ::new (&p_buffer[in]) T(value);
00278       base_t::add_in();
00279     }
00280 
00281     //*************************************************************************
00282     /// Allows a possibly more efficient 'push' by moving to the next input value
00283     /// and returning a reference to it.
00284     /// This may eliminate a copy by allowing direct construction in-place.<br>
00285     /// If asserts or exceptions are enabled, throws an etl::queue_full is the queue is already full.
00286     /// \return A reference to the position to 'push' to.
00287     //*************************************************************************
00288     reference push()
00289     {
00290       const size_type next = in;
00291 
00292 #if defined(ETL_CHECK_PUSH_POP)
00293       ETL_ASSERT(!full(), ETL_ERROR(queue_full));
00294 #endif
00295       base_t::add_in();
00296 
00297       return p_buffer[next];
00298     }
00299 
00300     //*************************************************************************
00301     /// Constructs a value in the queue 'in place'.
00302     /// If asserts or exceptions are enabled, throws an etl::queue_full if the queue if already full.
00303     ///\param value The value to use to construct the item to push to the queue.
00304     //*************************************************************************
00305     template <typename T1>
00306     void emplace(const T1& value1)
00307     {
00308 #if defined(ETL_CHECK_PUSH_POP)
00309       ETL_ASSERT(!full(), ETL_ERROR(queue_full));
00310 #endif
00311       ::new (&p_buffer[in]) T(value1);
00312       base_t::add_in();
00313     }
00314 
00315     //*************************************************************************
00316     /// Constructs a value in the queue 'in place'.
00317     /// If asserts or exceptions are enabled, throws an etl::queue_full if the queue if already full.
00318     ///\param value The value to use to construct the item to push to the queue.
00319     //*************************************************************************
00320     template <typename T1, typename T2>
00321     void emplace(const T1& value1, const T2& value2)
00322     {
00323 #if defined(ETL_CHECK_PUSH_POP)
00324       ETL_ASSERT(!full(), ETL_ERROR(queue_full));
00325 #endif
00326       ::new (&p_buffer[in]) T(value1, value2);
00327       base_t::add_in();
00328     }
00329 
00330     //*************************************************************************
00331     /// Constructs a value in the queue 'in place'.
00332     /// If asserts or exceptions are enabled, throws an etl::queue_full if the queue if already full.
00333     ///\param value The value to use to construct the item to push to the queue.
00334     //*************************************************************************
00335     template <typename T1, typename T2, typename T3>
00336     void emplace(const T1& value1, const T2& value2, const T3& value3)
00337     {
00338 #if defined(ETL_CHECK_PUSH_POP)
00339       ETL_ASSERT(!full(), ETL_ERROR(queue_full));
00340 #endif
00341       ::new (&p_buffer[in]) T(value1, value2, value3);
00342       base_t::add_in();
00343     }
00344 
00345     //*************************************************************************
00346     /// Constructs a value in the queue 'in place'.
00347     /// If asserts or exceptions are enabled, throws an etl::queue_full if the queue if already full.
00348     ///\param value The value to use to construct the item to push to the queue.
00349     //*************************************************************************
00350     template <typename T1, typename T2, typename T3, typename T4>
00351     void emplace(const T1& value1, const T2& value2, const T3& value3, const T4& value4)
00352     {
00353 #if defined(ETL_CHECK_PUSH_POP)
00354       ETL_ASSERT(!full(), ETL_ERROR(queue_full));
00355 #endif
00356       ::new (&p_buffer[in]) T(value1, value2, value3, value4);
00357       base_t::add_in();
00358     }
00359 
00360     //*************************************************************************
00361     /// Clears the queue to the empty state.
00362     //*************************************************************************
00363     void clear()
00364     {
00365       while (current_size > 0)
00366       {
00367         p_buffer[out].~T();
00368         base_t::del_out();
00369       }
00370 
00371       in = 0;
00372       out = 0;
00373     }
00374 
00375     //*************************************************************************
00376     /// Removes the oldest value from the back of the queue.
00377     /// Does nothing if the queue is already empty.
00378     /// If asserts or exceptions are enabled, throws an etl::queue_empty if the queue is empty.
00379     //*************************************************************************
00380     void pop()
00381     {
00382 #if defined(ETL_CHECK_PUSH_POP)
00383       ETL_ASSERT(!empty(), ETL_ERROR(queue_empty));
00384 #endif
00385       p_buffer[out].~T();
00386       base_t::del_out();
00387     }
00388 
00389     //*************************************************************************
00390     /// Gets the oldest value and removes it from the front of the queue.
00391     /// If asserts or exceptions are enabled, throws an etl::queue_empty if the queue is empty.
00392     //*************************************************************************
00393     void pop_into(reference destination)
00394     {
00395       destination = front();
00396       pop();
00397     }
00398 
00399     //*************************************************************************
00400     /// Gets the oldest value and removes it from the front of the queue and
00401     /// pushes it to the destination container.
00402     /// If asserts or exceptions are enabled, throws an etl::queue_empty if the queue is empty.
00403     /// NOTE: The destination must support a push(T) member function.
00404     //*************************************************************************
00405     template <typename TContainer>
00406     void pop_into(TContainer& destination)
00407     {
00408       destination.push(front());
00409       pop();
00410     }
00411 
00412     //*************************************************************************
00413     /// Assignment operator.
00414     //*************************************************************************
00415     iqueue& operator = (const iqueue& rhs)
00416     {
00417       if (&rhs != this)
00418       {
00419         clear();
00420         clone(rhs);
00421       }
00422 
00423       return *this;
00424     }
00425 
00426   protected:
00427 
00428     //*************************************************************************
00429     /// Make this a clone of the supplied queue
00430     //*************************************************************************
00431     void clone(const iqueue& other)
00432     {
00433       clear();
00434 
00435       size_t index = other.out;
00436 
00437       for (size_t i = 0; i < other.size(); ++i)
00438       {
00439         push(other.p_buffer[index]);
00440         index = (index == (CAPACITY - 1)) ? 0 : index + 1;
00441       }
00442     }
00443 
00444     //*************************************************************************
00445     /// The constructor that is called from derived classes.
00446     //*************************************************************************
00447     iqueue(T* p_buffer_, size_type max_size_)
00448       : queue_base(max_size_),
00449         p_buffer(p_buffer_)
00450     {
00451     }
00452 
00453   private:
00454 
00455     // Disable copy construction.
00456     iqueue(const iqueue&);
00457 
00458     T* p_buffer; ///< The internal buffer.
00459   };
00460 
00461   //***************************************************************************
00462   ///\ingroup queue
00463   /// A fixed capacity queue.
00464   /// This queue does not support concurrent access by different threads.
00465   /// \tparam T    The type this queue should support.
00466   /// \tparam SIZE The maximum capacity of the queue.
00467   //***************************************************************************
00468   template <typename T, const size_t SIZE>
00469   class queue : public etl::iqueue<T>
00470   {
00471   public:
00472 
00473     static const size_t MAX_SIZE = SIZE;
00474 
00475     //*************************************************************************
00476     /// Default constructor.
00477     //*************************************************************************
00478     queue()
00479       : etl::iqueue<T>(reinterpret_cast<T*>(&buffer[0]), SIZE)
00480     {
00481     }
00482 
00483     //*************************************************************************
00484     /// Copy constructor
00485     //*************************************************************************
00486     queue(const queue& rhs)
00487       : etl::iqueue<T>(reinterpret_cast<T*>(&buffer[0]), SIZE)
00488     {
00489       etl::iqueue<T>::clone(rhs);
00490     }
00491 
00492     //*************************************************************************
00493     /// Destructor.
00494     //*************************************************************************
00495     ~queue()
00496     {
00497       etl::iqueue<T>::clear();
00498     }
00499 
00500     //*************************************************************************
00501     /// Assignment operator.
00502     //*************************************************************************
00503     queue& operator = (const queue& rhs)
00504     {
00505       if (&rhs != this)
00506       {
00507         etl::iqueue<T>::clone(rhs);
00508       }
00509 
00510       return *this;
00511     }
00512 
00513   private:
00514 
00515     /// The uninitialised buffer of T used in the stack.
00516     typename etl::aligned_storage<sizeof(T), etl::alignment_of<T>::value>::type buffer[SIZE];
00517   };
00518 }
00519 
00520 #undef ETL_FILE
00521 
00522 #endif
00523