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(ValueType *pointer, ValueType *base, size_t tail)
177         : mPointer(pointer), mBase(base), mTail(tail) {}
178 
179     bool operator==(const ArrayQueueIterator &right) const {
180       return (mPointer == right.mPointer);
181     }
182 
183     bool operator!=(const ArrayQueueIterator &right) const {
184       return (mPointer != right.mPointer);
185     }
186 
187     ValueType &operator*() {
188       return *mPointer;
189     }
190 
191     ValueType *operator->() {
192       return mPointer;
193     }
194 
195     ArrayQueueIterator &operator++() {
196       if (mPointer == (mBase + mTail)) {
197         // Jump to end() if at tail
198         mPointer = mBase + kCapacity;
199       } else if (mPointer == (mBase + kCapacity - 1)) {
200         // Wrap around in the memory
201         mPointer = mBase;
202       } else {
203         mPointer++;
204       }
205       return *this;
206     }
207 
208     ArrayQueueIterator operator++(int) {
209       ArrayQueueIterator it(*this);
210       operator++();
211       return it;
212     }
213 
214    private:
215     //! Pointer of the iterator.
216     ValueType *mPointer;
217 
218     //! The memory base address of this container.
219     ValueType *mBase;
220 
221     //! The tail offset relative to the memory base address.
222     size_t mTail;
223   };
224 
225   /**
226    * Forward iterator that points to some element in the container.
227    */
228   typedef ArrayQueueIterator<ElementType> iterator;
229   typedef ArrayQueueIterator<const ElementType> const_iterator;
230 
231   /**
232    * @return A forward iterator to the beginning.
233    */
234   typename ArrayQueue<ElementType, kCapacity>::iterator begin();
235   typename ArrayQueue<ElementType, kCapacity>::const_iterator begin() const;
236   typename ArrayQueue<ElementType, kCapacity>::const_iterator cbegin() const;
237 
238   /**
239    * @return A forward iterator to the end.
240    */
241   typename ArrayQueue<ElementType, kCapacity>::iterator end();
242   typename ArrayQueue<ElementType, kCapacity>::const_iterator end() const;
243   typename ArrayQueue<ElementType, kCapacity>::const_iterator cend() const;
244 
245  private:
246   /**
247    * Storage for array queue elements. To avoid static initialization of
248    * members, std::aligned_storage is used.
249    */
250   typename std::aligned_storage<sizeof(ElementType), alignof(ElementType)>::type
251       mData[kCapacity];
252 
253   /*
254    * Initialize mTail to be (kCapacity-1). When an element is pushed in,
255    * mHead and mTail will align. Also, this is consistent with
256    * mSize = (mTail - mHead)%kCapacity + 1 for mSize > 0.
257    */
258   //! Index of the front element
259   size_t mHead = 0;
260 
261   //! Index of the back element
262   size_t mTail = kCapacity - 1;
263 
264   //! Number of elements in the array queue
265   size_t mSize = 0;
266 
267   /**
268    * Obtains a pointer to the underlying storage for the vector.
269    *
270    * @return A pointer to the storage used for elements in this vector.
271    */
272   ElementType *data();
273 
274   /**
275    * Obtains a pointer to the underlying storage for the vector.
276    *
277    * @return A pointer to the storage used for elements in this vector.
278    */
279   const ElementType *data() const;
280 
281   /**
282    * Converts relative index with respect to mHead to absolute index in the
283    * storage array.
284    *
285    * @param index Relative index in range [0,size()-1]
286    * @return The index of the storage array in range [0,kCapacity-1]
287    */
288   size_t relativeIndexToAbsolute(size_t index) const;
289 
290   /*
291    * Pulls mHead to the next element in the array queue and decrements mSize
292    * accordingly. It is illegal to call this function on an empty array queue.
293    */
294   void pullHead();
295 
296   /*
297    * Pulls mTail to the previous element in the array queue and decrements mSize
298    * accordingly. It is illegal to call this function on an empty array queue.
299    */
300   void pullTail();
301 
302   /*
303    * Pushes mTail to the next available storage space and increments mSize
304    * accordingly.
305    *
306    * @return true if the array queue is not full.
307    */
308   bool pushTail();
309 };
310 
311 }  // namespace chre
312 
313 #include "chre/util/array_queue_impl.h"
314 
315 #endif  // CHRE_UTIL_ARRAY_QUEUE_H_
316