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
24namespace 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 */
30template<typename ElementType, size_t kCapacity>
31class 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:
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