1 #ifndef DALI_CIRCULAR_QUEUE_H
2 #define DALI_CIRCULAR_QUEUE_H
5 * Copyright (c) 2020 Samsung Electronics Co., Ltd.
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
11 * http://www.apache.org/licenses/LICENSE-2.0
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.
19 #include <dali/public-api/common/dali-vector.h>
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.
28 template<typename ElementType>
32 typedef Dali::Vector<ElementType> Queue;
36 * @param[in] maximumSize The maximum number of elements that the queue can contain
38 CircularQueue(int maximumSize)
39 : mMaximumSize(maximumSize),
44 mQueue.Reserve(maximumSize);
48 * @brief Index operator.
50 * @param[in] index The index to lookup.
52 * @warning This method asserts if the user attempts to read outside the
55 ElementType& operator[](unsigned int index)
57 unsigned int actualIndex = (mStartMarker + index) % mMaximumSize;
58 DALI_ASSERT_ALWAYS(actualIndex < mQueue.Count() && "Reading outside queue boundary");
59 return mQueue[actualIndex];
62 const ElementType& operator[](unsigned int index) const
64 unsigned int actualIndex = (mStartMarker + index) % mMaximumSize;
65 DALI_ASSERT_ALWAYS(actualIndex < mQueue.Count() && "Reading outside queue boundary");
66 return mQueue[actualIndex];
70 * @brief Push back an element into the queue.
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
76 void PushBack(const ElementType& element)
78 DALI_ASSERT_ALWAYS(!IsFull() && "Adding to full queue");
80 // Push back if we need to increase the vector count
81 if(mQueue.Count() == 0 || (mQueue.Count() < mMaximumSize && !IsEmpty()))
83 mQueue.PushBack(element);
92 // Don't advance the end marker or increase the vector count
93 mQueue[mEndMarker] = element;
98 // vector is at max and there is space: advance end marker
100 mEndMarker %= mMaximumSize;
101 mQueue[mEndMarker] = element;
107 * @brief Pops an element off the front of the queue
109 * @return A copy of the element at the front of the queue
110 * @warning This method asserts if the queue is empty
112 ElementType PopFront()
114 DALI_ASSERT_ALWAYS(!IsEmpty() && "Reading from empty queue");
117 if(mNumberOfElements == 1)
119 element = mQueue[mStartMarker];
120 mNumberOfElements = 0;
122 else if(mNumberOfElements > 1)
124 element = mQueue[mStartMarker];
126 mStartMarker %= mMaximumSize;
135 DALI_ASSERT_ALWAYS(!IsEmpty() && "Reading from empty queue");
136 return mQueue[mStartMarker];
139 const ElementType& Front() const
141 DALI_ASSERT_ALWAYS(!IsEmpty() && "Reading from empty queue");
142 return mQueue[mStartMarker];
147 DALI_ASSERT_ALWAYS(!IsEmpty() && "Reading from empty queue");
148 return mQueue[mEndMarker];
151 const ElementType& Back() const
153 DALI_ASSERT_ALWAYS(!IsEmpty() && "Reading from empty queue");
154 return mQueue[mEndMarker];
158 * @brief Predicate to determine if the queue is empty
160 * @return true if the queue is empty
164 return mNumberOfElements == 0;
168 * @brief Predicate to determine if the queue is full
170 * @return true if the queue is full
174 return (mQueue.Count() == mMaximumSize &&
175 mNumberOfElements > 0 &&
176 (mEndMarker + 1) % mMaximumSize == mStartMarker);
180 * @brief Get a count of the elements in the queue
182 * @return the number of elements in the queue.
184 std::size_t Count() const
186 return mNumberOfElements;
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
199 #endif // DALI_CIRCULAR_QUEUE_H