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

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