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 #include "chre/util/raw_storage.h" 26 27 /** 28 * @file 29 * ArrayQueue is a templated fixed-size FIFO queue implemented around a 30 * contiguous array. Two variations on how the 31 * 32 * 1) ArrayQueue<ElementType, kCapacity> allocates the underlying array within 33 * the ArrayQueue object itself. 34 * 2) ArrayQueueExt<ElementType> accepts a pointer to the storage at 35 * construction time. Since this variation maintains the capacity of the array 36 * as a member variable rather than template parameter, it can be useful in 37 * situations where it'd be inconvenient to include the array capacity in the 38 * type specification, for example when processing multiple array queues with 39 * different capacities in a loop or similar construct. 40 * 41 * This variability is accomplished through a base class which provides the 42 * underlying storage, which is attached to the array queue implementation in 43 * ArrayQueueCore via a template parameter, then the two storage options are 44 * composed into public APIs as ArrayQueue and ArrayQueueExt. Users of this 45 * container are not expected to reference ArrayQueueCore or ArrayQueue*Storage 46 * directly, but developers should refer to ArrayQueueCore for API 47 * documentation. 48 */ 49 50 namespace chre { 51 52 // Forward declaration to support declarations in ArrayQueueCore 53 template <typename ValueType> 54 class ArrayQueueIterator; 55 56 namespace internal { 57 58 /** 59 * The core implementation of an array queue, from which the public interfaces 60 * (ArrayQueue and ArrayQueueExt) are derived. 61 * 62 * The StorageType template parameter must be a class supplying data() and 63 * capacity() methods used to access the underlying array storage. 64 */ 65 template <typename ElementType, class StorageType> 66 class ArrayQueueCore : public StorageType { 67 public: 68 // Inherit constructors from StorageType 69 using StorageType::StorageType; 70 71 /** 72 * Calls the destructor of all the elements in the array queue. 73 */ 74 ~ArrayQueueCore(); 75 76 // data() and capacity() functions are inherited from StorageType 77 78 /** 79 * @return true if the array queue is empty. 80 */ 81 bool empty() const; 82 83 /** 84 * @return true if the array queue is full. 85 */ 86 bool full() const; 87 88 /** 89 * @return The number of elements currently stored in the array queue. 90 */ 91 size_t size() const; 92 93 /** 94 * Obtains the front element of the array queue. It is illegal to access the 95 * front element when the array queue is empty. The user of the API must check 96 * the size() or empty() function prior to accessing the front element to 97 * ensure that they will not read out of bounds. 98 * 99 * @return The front element. 100 */ 101 ElementType &front(); 102 const ElementType &front() const; 103 104 /** 105 * Obtains the last element in the queue. Illegal to call when empty() is 106 * true. 107 * 108 * @return The last element in the queue. 109 */ 110 ElementType &back(); 111 const ElementType &back() const; 112 113 /** 114 * Obtains an element of the array queue given an index. It is illegal to 115 * index this array queue out of bounds and the user of the API must check the 116 * size() function prior to indexing this array queue to ensure that they will 117 * not read out of bounds. 118 * 119 * @param index Requested index in range [0,size()-1] 120 * @return The element. 121 */ 122 ElementType &operator[](size_t index); 123 124 /** 125 * Obtains an element of the array queue given an index. It is illegal to 126 * index this array queue out of bounds and the user of the API must check the 127 * size() function prior to indexing this array queue to ensure that they will 128 * not read out of bounds. 129 * 130 * @param index Requested index in range [0,size()-1] 131 * @return The element. 132 */ 133 const ElementType &operator[](size_t index) const; 134 135 /** 136 * Pushes an element onto the back of the array queue via copy or move 137 * construction. It returns false if the array queue is full already and there 138 * is no room for the elements. All iterators and references are unaffected. 139 * 140 * @param element The element to push onto the array queue. 141 * @return true if the element is pushed successfully. 142 */ 143 bool push(const ElementType &element); 144 bool push(ElementType &&element); 145 146 /** 147 * Pushes an element onto the back of the array queue via copy or move 148 * construction. If the array queue is full the front element is removed 149 * to make room for the new element. 150 * 151 * @param element The element to push onto the array queue. 152 */ 153 void kick_push(const ElementType &element); 154 void kick_push(ElementType &&element); 155 156 /** 157 * Removes the front element from the array queue if the array queue is not 158 * empty. Only iterators and references to the front of the queue are 159 * invalidated. 160 */ 161 void pop(); 162 163 /** 164 * Removes the back element from the array queue if the array queue is not 165 * empty. Only iterators and references to the back of the queue are 166 * invalidated. 167 */ 168 void pop_back(); 169 170 /** 171 * Removes an element from the array queue given an index. It returns false if 172 * the array queue contains fewer items than the index. All iterators and 173 * references to elements before the removed one are unaffected. Iterators 174 * and references to the removed element or any elements after it are 175 * invalidated. 176 * 177 * @param index Requested index in range [0,size()-1] 178 * @return true if the indexed element has been removed successfully. 179 */ 180 bool remove(size_t index); 181 182 /** 183 * Constructs an element onto the back of the array queue. All iterators and 184 * references are unaffected. 185 * 186 * @param The arguments to the constructor 187 * @return true if the element is constructed successfully. 188 */ 189 template <typename... Args> 190 bool emplace(Args &&... args); 191 192 /** 193 * Removes all the elements of the queue. 194 */ 195 void clear(); 196 197 /** 198 * Forward iterator that points to some element in the container. 199 */ 200 typedef ArrayQueueIterator<ElementType> iterator; 201 typedef ArrayQueueIterator<const ElementType> const_iterator; 202 203 /** 204 * @return A forward iterator to the beginning. 205 */ 206 iterator begin(); 207 const_iterator begin() const; 208 const_iterator cbegin() const; 209 210 /** 211 * @return A forward iterator to the end. 212 */ 213 iterator end(); 214 const_iterator end() const; 215 const_iterator cend() const; 216 217 private: 218 /* 219 * Initialize mTail to be (capacity-1). When an element is pushed in, 220 * mHead and mTail will align. Also, this is consistent with 221 * mSize = (mTail - mHead)%capacity + 1 for mSize > 0. 222 */ 223 //! Index of the front element 224 size_t mHead = 0; 225 226 //! Index of the back element 227 size_t mTail = StorageType::capacity() - 1; 228 229 //! Number of elements in the array queue 230 size_t mSize = 0; 231 232 /** 233 * Converts relative index with respect to mHead to absolute index in the 234 * storage array. 235 * 236 * @param index Relative index in range [0,size()-1] 237 * @return The index of the storage array in range [0,kCapacity-1] 238 */ 239 size_t relativeIndexToAbsolute(size_t index) const; 240 241 /* 242 * Pulls mHead to the next element in the array queue and decrements mSize 243 * accordingly. It is illegal to call this function on an empty array queue. 244 */ 245 void pullHead(); 246 247 /* 248 * Pulls mTail to the previous element in the array queue and decrements mSize 249 * accordingly. It is illegal to call this function on an empty array queue. 250 */ 251 void pullTail(); 252 253 /* 254 * Pushes mTail to the next available storage space and increments mSize 255 * accordingly. 256 * 257 * @return true if the array queue is not full. 258 */ 259 bool pushTail(); 260 }; 261 262 /** 263 * Storage for ArrayQueue based on a pointer to an array allocated elsewhere. 264 */ 265 template <typename ElementType> 266 class ArrayQueueExternalStorage : public NonCopyable { 267 public: ArrayQueueExternalStorage(ElementType * storage,size_t capacity)268 ArrayQueueExternalStorage(ElementType *storage, size_t capacity) 269 : mData(storage), kCapacity(capacity) {} 270 data()271 ElementType *data() { 272 return mData; 273 } 274 data()275 const ElementType *data() const { 276 return mData; 277 } 278 capacity()279 size_t capacity() const { 280 return kCapacity; 281 } 282 283 private: 284 ElementType *mData; 285 const size_t kCapacity; 286 }; 287 288 } // namespace internal 289 290 /** 291 * Alias to the array queue implementation with storage allocated inside the 292 * object. This is the interface that most code is expected to use. 293 */ 294 template <typename ElementType, size_t kCapacity> 295 class ArrayQueue 296 : public internal::ArrayQueueCore<ElementType, 297 RawStorage<ElementType, kCapacity>> { 298 public: 299 typedef ElementType value_type; 300 }; 301 302 /** 303 * Wrapper for the array queue implementation with storage allocated elsewhere. 304 * This is useful in instances where it's inconvenient to have the array's 305 * capacity form part of the type specification. 306 */ 307 template <typename ElementType> 308 class ArrayQueueExt 309 : public internal::ArrayQueueCore< 310 ElementType, internal::ArrayQueueExternalStorage<ElementType>> { 311 public: ArrayQueueExt(ElementType * storage,size_t capacity)312 ArrayQueueExt(ElementType *storage, size_t capacity) 313 : internal::ArrayQueueCore< 314 ElementType, internal::ArrayQueueExternalStorage<ElementType>>( 315 storage, capacity) {} 316 }; 317 318 /** 319 * A template class that implements a forward iterator for the array queue. 320 */ 321 template <typename ValueType> 322 class ArrayQueueIterator { 323 public: 324 typedef ValueType value_type; 325 typedef ValueType &reference; 326 typedef ValueType *pointer; 327 typedef std::ptrdiff_t difference_type; 328 typedef std::forward_iterator_tag iterator_category; 329 330 ArrayQueueIterator() = default; ArrayQueueIterator(ValueType * start,ValueType * base,size_t tail,size_t capacity)331 ArrayQueueIterator(ValueType *start, ValueType *base, size_t tail, 332 size_t capacity) 333 : mPointer(start), mBase(base), mTail(tail), mCapacity(capacity) {} 334 335 bool operator==(const ArrayQueueIterator &right) const { 336 return (mPointer == right.mPointer); 337 } 338 339 bool operator!=(const ArrayQueueIterator &right) const { 340 return (mPointer != right.mPointer); 341 } 342 343 ValueType &operator*() { 344 return *mPointer; 345 } 346 347 ValueType *operator->() { 348 return mPointer; 349 } 350 351 ArrayQueueIterator &operator++() { 352 if (mPointer == (mBase + mTail)) { 353 // Jump to end() if at tail 354 mPointer = mBase + mCapacity; 355 } else if (mPointer == (mBase + mCapacity - 1)) { 356 // Wrap around in the memory 357 mPointer = mBase; 358 } else { 359 mPointer++; 360 } 361 return *this; 362 } 363 364 ArrayQueueIterator operator++(int) { 365 ArrayQueueIterator it(*this); 366 operator++(); 367 return it; 368 } 369 370 private: 371 //! Pointer of the iterator. 372 ValueType *mPointer; 373 374 //! The memory base address of this container. 375 ValueType *mBase; 376 377 //! The tail offset relative to the memory base address. 378 size_t mTail; 379 380 //! Number of elements the underlying ArrayQueue can hold 381 size_t mCapacity; 382 }; 383 384 } // namespace chre 385 386 #include "chre/util/array_queue_impl.h" 387 388 #endif // CHRE_UTIL_ARRAY_QUEUE_H_ 389