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