1 /*
2  * Copyright (C) 2016 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #ifndef CHRE_UTIL_ARRAY_QUEUE_H_
18 #define CHRE_UTIL_ARRAY_QUEUE_H_
19 
20 #include <cstddef>
21 #include <iterator>
22 #include <type_traits>
23 
24 #include "chre/util/non_copyable.h"
25 
26 namespace chre {
27 
28 /**
29  * A fixed-size FIFO queue for storing elements. When the FIFO is full, new
30  * element will not be able to be pushed in.
31  */
32 template<typename ElementType, size_t kCapacity>
33 class ArrayQueue : public NonCopyable {
34  public:
35   /**
36    * Calls the destructor of all the elements in the array queue.
37    */
38   ~ArrayQueue();
39 
40   /**
41    * Determines whether the array queue is empty or not.
42    *
43    * @return true if the array queue is empty.
44    */
45   bool empty() const;
46 
47   /**
48    * @return true if the array queue is full.
49    */
50   bool full() const;
51 
52   /**
53    * Obtains the number of elements currently stored in the array queue.
54    *
55    * @return The number of elements currently stored in the array queue.
56    */
57   size_t size() const;
58 
59   /**
60    * Obtains the front element of the array queue. It is illegal to access the
61    * front element when the array queue is empty. The user of the API must check
62    * the size() or empty() function prior to accessing the front element to
63    * ensure that they will not read out of bounds.
64    *
65    * @return The front element.
66    */
67   ElementType& front();
68   const ElementType& front() const;
69 
70   /**
71    * Obtains the last element in the queue. Illegal to call when empty() is
72    * true.
73    *
74    * @return The last element in the queue.
75    */
76   ElementType& back();
77   const ElementType& back() const;
78 
79   /**
80    * Obtains an element of the array queue given an index. It is illegal to
81    * index this array queue out of bounds and the user of the API must check the
82    * size() function prior to indexing this array queue to ensure that they will
83    * not read out of bounds.
84    *
85    * @param index Requested index in range [0,size()-1]
86    * @return The element.
87    */
88   ElementType& operator[](size_t index);
89 
90   /**
91    * Obtains an element of the array queue given an index. It is illegal to
92    * index this array queue out of bounds and the user of the API must check the
93    * size() function prior to indexing this array queue to ensure that they will
94    * not read out of bounds.
95    *
96    * @param index Requested index in range [0,size()-1]
97    * @return The element.
98    */
99   const ElementType& operator[](size_t index) const;
100 
101   /**
102    * Pushes an element onto the back of the array queue via copy or move
103    * construction. It returns false if the array queue is full already and there
104    * is no room for the elements. All iterators and references are unaffected.
105    *
106    * @param element The element to push onto the array queue.
107    * @return true if the element is pushed successfully.
108    */
109   bool push(const ElementType& element);
110   bool push(ElementType&& element);
111 
112   /**
113    * Pushes an element onto the back of the array queue via copy or move
114    * construction. If the array queue is full the front element is removed
115    * to make room for the new element.
116    *
117    * @param element The element to push onto the array queue.
118    */
119   void kick_push(const ElementType& element);
120   void kick_push(ElementType&& element);
121 
122   /**
123    * Removes the front element from the array queue if the array queue is not
124    * empty. Only iterators and references to the front of the queue are
125    * invalidated.
126    */
127   void pop();
128 
129   /**
130    * Removes the back element from the array queue if the array queue is not
131    * empty. Only iterators and references to the back of the queue are
132    * invalidated.
133    */
134   void pop_back();
135 
136   /**
137    * Removes an element from the array queue given an index. It returns false if
138    * the array queue contains fewer items than the index. All iterators and
139    * references to elements before the removed one are unaffected. Iterators
140    * and references to the removed element or any elements after it are
141    * invalidated.
142    *
143    * @param index Requested index in range [0,size()-1]
144    * @return true if the indexed element has been removed successfully.
145    */
146   bool remove(size_t index);
147 
148   /**
149    * Constructs an element onto the back of the array queue. All iterators and
150    * references are unaffected.
151    *
152    * @param The arguments to the constructor
153    * @return true if the element is constructed successfully.
154    */
155   template<typename... Args>
156   bool emplace(Args&&... args);
157 
158   /**
159    * Removes all the elements of the queue.
160    */
161   void clear();
162 
163   /**
164    * A template class that implements a forward iterator for the array queue.
165    */
166   template<typename ValueType>
167   class ArrayQueueIterator {
168    public:
169     typedef ValueType value_type;
170     typedef ValueType& reference;
171     typedef ValueType* pointer;
172     typedef std::ptrdiff_t difference_type;
173     typedef std::forward_iterator_tag iterator_category;
174 
175     ArrayQueueIterator() = default;
ArrayQueueIterator(ValueType * pointer,ValueType * base,size_t tail)176     ArrayQueueIterator(
177         ValueType *pointer, ValueType *base, size_t tail)
178         : mPointer(pointer), mBase(base), mTail(tail) {}
179 
180     bool operator==(const ArrayQueueIterator& right) const {
181       return (mPointer == right.mPointer);
182     }
183 
184     bool operator!=(const ArrayQueueIterator& right) const {
185       return (mPointer != right.mPointer);
186     }
187 
188     ValueType& operator*() {
189       return *mPointer;
190     }
191 
192     ValueType *operator->() {
193       return mPointer;
194     }
195 
196     ArrayQueueIterator& operator++() {
197       if (mPointer == (mBase + mTail)) {
198         // Jump to end() if at tail
199         mPointer = mBase + kCapacity;
200       } else if (mPointer == (mBase + kCapacity - 1)) {
201         // Wrap around in the memory
202         mPointer = mBase;
203       } else {
204         mPointer++;
205       }
206       return *this;
207     }
208 
209     ArrayQueueIterator operator++(int) {
210       ArrayQueueIterator it(*this);
211       operator++();
212       return it;
213     }
214 
215    private:
216     //! Pointer of the iterator.
217     ValueType *mPointer;
218 
219     //! The memory base address of this container.
220     ValueType *mBase;
221 
222     //! The tail offset relative to the memory base address.
223     size_t mTail;
224   };
225 
226   /**
227    * Forward iterator that points to some element in the container.
228    */
229   typedef ArrayQueueIterator<ElementType> iterator;
230   typedef ArrayQueueIterator<const ElementType> const_iterator;
231 
232   /**
233    * @return A forward iterator to the beginning.
234    */
235   typename ArrayQueue<ElementType, kCapacity>::iterator begin();
236   typename ArrayQueue<ElementType, kCapacity>::const_iterator begin() const;
237   typename ArrayQueue<ElementType, kCapacity>::const_iterator cbegin() const;
238 
239   /**
240    * @return A forward iterator to the end.
241    */
242   typename ArrayQueue<ElementType, kCapacity>::iterator end();
243   typename ArrayQueue<ElementType, kCapacity>::const_iterator end() const;
244   typename ArrayQueue<ElementType, kCapacity>::const_iterator cend() const;
245 
246  private:
247   /**
248    * Storage for array queue elements. To avoid static initialization of
249    * members, std::aligned_storage is used.
250    */
251   typename std::aligned_storage<sizeof(ElementType),
252                                 alignof(ElementType)>::type mData[kCapacity];
253 
254   /*
255    * Initialize mTail to be (kCapacity-1). When an element is pushed in,
256    * mHead and mTail will align. Also, this is consistent with
257    * mSize = (mTail - mHead)%kCapacity + 1 for mSize > 0.
258    */
259   //! Index of the front element
260   size_t mHead = 0;
261 
262   //! Index of the back element
263   size_t mTail = kCapacity - 1;
264 
265   //! Number of elements in the array queue
266   size_t mSize = 0;
267 
268   /**
269    * Obtains a pointer to the underlying storage for the vector.
270    *
271    * @return A pointer to the storage used for elements in this vector.
272    */
273   ElementType *data();
274 
275   /**
276    * Obtains a pointer to the underlying storage for the vector.
277    *
278    * @return A pointer to the storage used for elements in this vector.
279    */
280   const ElementType *data() const;
281 
282   /**
283    * Converts relative index with respect to mHead to absolute index in the
284    * storage array.
285    *
286    * @param index Relative index in range [0,size()-1]
287    * @return The index of the storage array in range [0,kCapacity-1]
288    */
289   size_t relativeIndexToAbsolute(size_t index) const;
290 
291   /*
292    * Pulls mHead to the next element in the array queue and decrements mSize
293    * accordingly. It is illegal to call this function on an empty array queue.
294    */
295   void pullHead();
296 
297   /*
298    * Pulls mTail to the previous element in the array queue and decrements mSize
299    * accordingly. It is illegal to call this function on an empty array queue.
300    */
301   void pullTail();
302 
303   /*
304    * Pushes mTail to the next available storage space and increments mSize
305    * accordingly.
306    *
307    * @return true if the array queue is not full.
308    */
309   bool pushTail();
310 };
311 
312 }  // namespace chre
313 
314 #include "chre/util/array_queue_impl.h"
315 
316 #endif  // CHRE_UTIL_ARRAY_QUEUE_H_
317