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