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 <type_traits>
21 
22 #include "chre/util/non_copyable.h"
23 
24 namespace chre {
25 
26 /**
27  * A fixed-size FIFO queue for storing elements. When the FIFO is full, new
28  * element will not be able to be pushed in.
29  */
30 template<typename ElementType, size_t kCapacity>
31 class ArrayQueue : public NonCopyable {
32  public:
33   /**
34    * Calls the destructor of all the elements in the array queue.
35    */
36   ~ArrayQueue();
37 
38   /**
39    * Determines whether the array queue is empty or not.
40    *
41    * @return true if the array queue is empty.
42    */
43   bool empty() const;
44 
45   /**
46    * @return true if the array queue is full.
47    */
48   bool full() const;
49 
50   /**
51    * Obtains the number of elements currently stored in the array queue.
52    *
53    * @return The number of elements currently stored in the array queue.
54    */
55   size_t size() const;
56 
57   /**
58    * Obtains the front element of the array queue. It is illegal to access the
59    * front element when the array queue is empty. The user of the API must check
60    * the size() or empty() function prior to accessing the front element to
61    * ensure that they will not read out of bounds.
62    *
63    * @return The front element.
64    */
65   ElementType& front();
66 
67   /**
68    * Obtains the front element of the array queue. It is illegal to access the
69    * front element when the array queue is empty. The user of the API must check
70    * the size() or empty() function prior to accessing the front element to
71    * ensure that they will not read out of bounds.
72    *
73    * @return The front element.
74    */
75   const ElementType& front() const;
76 
77   /**
78    * Obtains an element of the array queue given an index. It is illegal to
79    * index this array queue out of bounds and the user of the API must check the
80    * size() function prior to indexing this array queue to ensure that they will
81    * not read out of bounds.
82    *
83    * @param index Requested index in range [0,size()-1]
84    * @return The element.
85    */
86   ElementType& operator[](size_t index);
87 
88   /**
89    * Obtains an element of the array queue given an index. It is illegal to
90    * index this array queue out of bounds and the user of the API must check the
91    * size() function prior to indexing this array queue to ensure that they will
92    * not read out of bounds.
93    *
94    * @param index Requested index in range [0,size()-1]
95    * @return The element.
96    */
97   const ElementType& operator[](size_t index) const;
98 
99   /**
100    * Pushes an element onto the back of the array queue via copy or move
101    * construction. It returns false if the array queue is full already and there
102    * is no room for the elements. All iterators and references are unaffected.
103    *
104    * @param element The element to push onto the array queue.
105    * @return true if the element is pushed successfully.
106    */
107   bool push(const ElementType& element);
108   bool push(ElementType&& element);
109 
110   /**
111    * Removes the front element from the array queue if the array queue is not
112    * empty. Only iterators and references to the front of the queue are
113    * invalidated.
114    */
115   void pop();
116 
117   /**
118    * Removes an element from the array queue given an index. It returns false if
119    * the array queue contains fewer items than the index. All iterators and
120    * references to elements before the removed one are unaffected. Iterators
121    * and references to the removed element or any elements after it are
122    * invalidated.
123    *
124    * @param index Requested index in range [0,size()-1]
125    * @return true if the indexed element has been removed successfully.
126    */
127   bool remove(size_t index);
128 
129   /**
130    * Constructs an element onto the back of the array queue. All iterators and
131    * references are unaffected.
132    *
133    * @param The arguments to the constructor
134    * @return true if the element is constructed successfully.
135    */
136   template<typename... Args>
137   bool emplace(Args&&... args);
138 
139   /**
140    * A template class that implements a forward iterator for the array queue.
141    */
142   template<typename ValueType>
143   class ArrayQueueIterator {
144    public:
ArrayQueueIterator(ValueType * pointer,ValueType * base,size_t tail)145     ArrayQueueIterator(
146         ValueType *pointer, ValueType *base, size_t tail)
147         : mPointer(pointer), mBase(base), mTail(tail) {}
148 
149     bool operator==(const ArrayQueueIterator& right) {
150       return (mPointer == right.mPointer);
151     }
152 
153     bool operator!=(const ArrayQueueIterator& right) {
154       return (mPointer != right.mPointer);
155     }
156 
157     ValueType& operator*() {
158       return *mPointer;
159     }
160 
161     ValueType *operator->() {
162       return mPointer;
163     }
164 
165     ArrayQueueIterator& operator++() {
166       if (mPointer == (mBase + mTail)) {
167         // Jump to end() if at tail
168         mPointer = mBase + kCapacity;
169       } else if (mPointer == (mBase + kCapacity - 1)) {
170         // Wrap around in the memory
171         mPointer = mBase;
172       } else {
173         mPointer++;
174       }
175       return *this;
176     }
177 
178     ArrayQueueIterator operator++(int) {
179       ArrayQueueIterator it(*this);
180       operator++();
181       return it;
182     }
183 
184    private:
185     //! Pointer of the iterator.
186     ValueType *mPointer;
187 
188     //! The memory base address of this container.
189     ValueType *mBase;
190 
191     //! The tail offset relative to the memory base address.
192     size_t mTail;
193   };
194 
195   /**
196    * Forward iterator that points to some element in the container.
197    */
198   typedef ArrayQueueIterator<ElementType> iterator;
199   typedef ArrayQueueIterator<const ElementType> const_iterator;
200 
201   /**
202    * @return A forward iterator to the beginning.
203    */
204   typename ArrayQueue<ElementType, kCapacity>::iterator begin();
205   typename ArrayQueue<ElementType, kCapacity>::const_iterator begin() const;
206   typename ArrayQueue<ElementType, kCapacity>::const_iterator cbegin() const;
207 
208   /**
209    * @return A forward iterator to the end.
210    */
211   typename ArrayQueue<ElementType, kCapacity>::iterator end();
212   typename ArrayQueue<ElementType, kCapacity>::const_iterator end() const;
213   typename ArrayQueue<ElementType, kCapacity>::const_iterator cend() const;
214 
215  private:
216   /**
217    * Storage for array queue elements. To avoid static initialization of
218    * members, std::aligned_storage is used.
219    */
220   typename std::aligned_storage<sizeof(ElementType),
221                                 alignof(ElementType)>::type mData[kCapacity];
222 
223   /*
224    * Initialize mTail to be (kCapacity-1). When an element is pushed in,
225    * mHead and mTail will align. Also, this is consistent with
226    * mSize = (mTail - mHead)%kCapacity + 1 for mSize > 0.
227    */
228   //! Index of the front element
229   size_t mHead = 0;
230 
231   //! Index of the back element
232   size_t mTail = kCapacity - 1;
233 
234   //! Number of elements in the array queue
235   size_t mSize = 0;
236 
237   /**
238    * Obtains a pointer to the underlying storage for the vector.
239    *
240    * @return A pointer to the storage used for elements in this vector.
241    */
242   ElementType *data();
243 
244   /**
245    * Obtains a pointer to the underlying storage for the vector.
246    *
247    * @return A pointer to the storage used for elements in this vector.
248    */
249   const ElementType *data() const;
250 
251   /**
252    * Converts relative index with respect to mHead to absolute index in the
253    * storage array.
254    *
255    * @param index Relative index in range [0,size()-1]
256    * @return The index of the storage array in range [0,kCapacity-1]
257    */
258   size_t relativeIndexToAbsolute(size_t index) const;
259 
260   /*
261    * Pulls mHead to the next element in the array queue and decrements mSize
262    * accordingly. It is illegal to call this function on an empty array queue.
263    */
264   void pullHead();
265 
266   /*
267    * Pushes mTail to the next available storage space and increments mSize
268    * accordingly.
269    *
270    * @return true if the array queue is not full.
271    */
272   bool pushTail();
273 };
274 
275 }  // namespace chre
276 
277 #include "chre/util/array_queue_impl.h"
278 
279 #endif  // CHRE_UTIL_ARRAY_QUEUE_H_
280