dali/devel-api/common/circular-queue.h

   1 #ifndef DALI_CIRCULAR_QUEUE_H
   2 #define DALI_CIRCULAR_QUEUE_H
   3
   4 /*
   5  * Copyright (c) 2017 Samsung Electronics Co., Ltd.
   6  *
   7  * Licensed under the Apache License, Version 2.0 (the "License");
   8  * you may not use this file except in compliance with the License.
   9  * You may obtain a copy of the License at
  10  *
  11  * http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS,
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  * See the License for the specific language governing permissions and
  17  * limitations under the License.
  18  */
  19 #include <dali/public-api/common/dali-vector.h>
  20
  21 namespace Dali
  22 {
  23
  24 /**
  25  * Class to provide a circular growable queue on top of Dali::Vector
  26  * It is designed to occupy a fixed block of memory. It does not allow
  27  * addition of elements past the start; i.e. it doesn't overwrite.
  28  */
  29 template <typename ElementType>
  30 class CircularQueue
  31 {
  32 public:
  33   typedef Dali::Vector<ElementType> Queue;
  34
  35   /**
  36    * Constructor
  37    * @param[in] maximumSize The maximum number of elements that the queue can contain
  38    */
  39   CircularQueue( int maximumSize )
  40   : mMaximumSize(maximumSize),
  41     mStartMarker(0),
  42     mEndMarker(0),
  43     mNumberOfElements(0)
  44   {
  45     mQueue.Reserve(maximumSize);
  46   }
  47
  48   /**
  49    * @brief Index operator.
  50    *
  51    * @param[in] index The index to lookup.
  52    *
  53    * @warning This method asserts if the user attempts to read outside the
  54    * range of elements.
  55    */
  56   ElementType& operator[](unsigned int index)
  57   {
  58     unsigned int actualIndex = (mStartMarker + index) % mMaximumSize;
  59     DALI_ASSERT_ALWAYS( actualIndex<mQueue.Count() && "Reading outside queue boundary");
  60     return mQueue[actualIndex];
  61   }
  62
  63   const ElementType& operator[](unsigned int index) const
  64   {
  65     unsigned int actualIndex = (mStartMarker + index) % mMaximumSize;
  66     DALI_ASSERT_ALWAYS( actualIndex<mQueue.Count() && "Reading outside queue boundary");
  67     return mQueue[actualIndex];
  68   }
  69
  70   /**
  71    * @brief Push back an element into the queue.
  72    *
  73    * @param[in] element The element to push to the back of the queue
  74    * @warning This method asserts if the user attempts to push more elements
  75    * than the maximum size specified in the constructor
  76    */
  77   void PushBack( const ElementType& element )
  78   {
  79     DALI_ASSERT_ALWAYS( !IsFull() && "Adding to full queue");
  80
  81     // Push back if we need to increase the vector count
  82     if( mQueue.Count() == 0 || ( mQueue.Count() < mMaximumSize && ! IsEmpty() ) )
  83     {
  84       mQueue.PushBack(element);
  85       if( !IsEmpty() )
  86       {
  87         ++mEndMarker;
  88       }
  89       ++mNumberOfElements;
  90     }
  91     else if( IsEmpty() )
  92     {
  93       // Don't advance the end marker or increase the vector count
  94       mQueue[mEndMarker] = element;
  95       ++mNumberOfElements;
  96     }
  97     else if( !IsFull() )
  98     {
  99       // vector is at max and there is space: advance end marker
 100       ++mEndMarker;
 101       mEndMarker %= mMaximumSize;
 102       mQueue[ mEndMarker ] = element;
 103       ++mNumberOfElements;
 104     }
 105   }
 106
 107   /**
 108    * @brief Pops an element off the front of the queue
 109    *
 110    * @return A copy of the element at the front of the queue
 111    * @warning This method asserts if the queue is empty
 112    */
 113   ElementType PopFront()
 114   {
 115     DALI_ASSERT_ALWAYS( !IsEmpty() && "Reading from empty queue" );
 116     ElementType element;
 117
 118     if( mNumberOfElements == 1 )
 119     {
 120       element = mQueue[mStartMarker];
 121       mNumberOfElements = 0;
 122     }
 123     else if( mNumberOfElements > 1 )
 124     {
 125       element = mQueue[mStartMarker];
 126       ++mStartMarker;
 127       mStartMarker %= mMaximumSize;
 128       --mNumberOfElements;
 129     }
 130
 131     return element;
 132   }
 133
 134   ElementType& Front()
 135   {
 136     DALI_ASSERT_ALWAYS( !IsEmpty() && "Reading from empty queue" );
 137     return mQueue[mStartMarker];
 138   }
 139
 140   const ElementType& Front() const
 141   {
 142     DALI_ASSERT_ALWAYS( !IsEmpty() && "Reading from empty queue" );
 143     return mQueue[mStartMarker];
 144   }
 145
 146   ElementType& Back()
 147   {
 148     DALI_ASSERT_ALWAYS( !IsEmpty() && "Reading from empty queue" );
 149     return mQueue[mEndMarker];
 150   }
 151
 152   const ElementType& Back() const
 153   {
 154     DALI_ASSERT_ALWAYS( !IsEmpty() && "Reading from empty queue" );
 155     return mQueue[mEndMarker];
 156   }
 157
 158   /**
 159    * @brief Predicate to determine if the queue is empty
 160    *
 161    * @return true if the queue is empty
 162    */
 163   bool IsEmpty() const
 164   {
 165     return mNumberOfElements == 0;
 166   }
 167
 168   /**
 169    * @brief Predicate to determine if the queue is full
 170    *
 171    * @return true if the queue is full
 172    */
 173   bool IsFull() const
 174   {
 175     return ( mQueue.Count() == mMaximumSize &&
 176              mNumberOfElements > 0 &&
 177              (mEndMarker + 1) % mMaximumSize == mStartMarker );
 178   }
 179
 180   /**
 181    * @brief Get a count of the elements in the queue
 182    *
 183    * @return the number of elements in the queue.
 184    */
 185   std::size_t Count() const
 186   {
 187     return mNumberOfElements;
 188   }
 189
 190 private:
 191   Queue       mQueue;            ///< The queue of elements
 192   std::size_t mMaximumSize;      ///< maximum size of queue
 193   std::size_t mStartMarker;      ///< Index of the first element in the queue
 194   std::size_t mEndMarker;        ///< Index of the last element in the queue
 195   int         mNumberOfElements; ///< Number of valid elements in the queue
 196 };
 197
 198 } // Dali
 199
 200 #endif //  DALI_CIRCULAR_QUEUE_H