1 /* 2 * Copyright (C) 2022 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_SEGMENTED_QUEUE_H_ 18 #define CHRE_UTIL_SEGMENTED_QUEUE_H_ 19 20 #include <type_traits> 21 #include <utility> 22 23 #include "chre/util/dynamic_vector.h" 24 #include "chre/util/non_copyable.h" 25 #include "chre/util/raw_storage.h" 26 #include "chre/util/unique_ptr.h" 27 28 namespace chre { 29 /** 30 * Data structure that is similar to chre::ArrayQueue but with the ability to 31 * expand dynamically. Also has segmented data storage to prevent heap 32 * fragmentation. 33 * 34 * Note that this data structure allocates storage dynamically and might need 35 * to move elements around during push_back(). It is important for ElementType 36 * to have a efficient move operator 37 * 38 * @tparam ElementType: The type of element for this SegmentedQueue to store. 39 * @tparam kBlockSize: The size of one block. 40 */ 41 template <typename ElementType, size_t kBlockSize> 42 class SegmentedQueue : public NonCopyable { 43 using Block = ::chre::RawStorage<ElementType, kBlockSize>; 44 using BlockPtr = UniquePtr<Block>; 45 static_assert(kBlockSize > 0); 46 47 public: 48 /** 49 * Construct a new Segmented Queue object. 50 * 51 * @param maxBlockCount: The maximum number of block that this queue can hold. 52 * @param staticBlockCount the number of blocks that will be allocate in the 53 * constructor and will only be deallocate by the destructor. Needs to be 54 * bigger than zero to avoid thrashing 55 */ 56 SegmentedQueue(size_t maxBlockCount, size_t staticBlockCount = 1); 57 58 ~SegmentedQueue(); 59 60 /** 61 * @return size_t: Number of elements that this segmented queue holds. 62 */ size()63 size_t size() { 64 return mSize; 65 } 66 67 /** 68 * @return size_t: How many blocks does this segmented queue contains. 69 */ block_count()70 size_t block_count() { 71 return mRawStoragePtrs.size(); 72 } 73 74 /** 75 * @return size_t: Number of items that this queue can store without pushing 76 * new blocks. 77 */ capacity()78 size_t capacity() { 79 return mRawStoragePtrs.size() * kBlockSize; 80 } 81 82 /** 83 * @return true: Return true if the segmented queue cannot accept new element. 84 */ full()85 bool full() { 86 return mSize == kMaxBlockCount * kBlockSize; 87 } 88 89 /** 90 * @return true: Return true if this segmented queue does not have any element 91 * stored. 92 */ empty()93 bool empty() const { 94 return mSize == 0; 95 } 96 97 /** 98 * Push a element to the end of the segmented queue. 99 * 100 * @param element: The element that will be push to the back of the queue. 101 * @return false: Return false if the queue is full. 102 */ 103 bool push_back(const ElementType &element); 104 bool push_back(ElementType &&element); 105 106 /** 107 * Provide the same push API like std::queue/chre::ArrayQueue that do 108 * push_back(). 109 * 110 * @param element: The element that will be push to the back of the queue. 111 * @return false: Return false if the queue is full. 112 */ 113 bool push(const ElementType &element); 114 bool push(ElementType &&element); 115 116 /** 117 * Constructs an element onto the back of the segmented queue. 118 * 119 * @param Arguments to the constructor of ElementType. 120 * @return: Return true if the element is constructed successfully. 121 */ 122 template <typename... Args> 123 bool emplace_back(Args &&...args); 124 125 /** 126 * Obtains an element of the queue by its index. 127 * It is illegal to use a index that is bigger or equal to the size of the 128 * queue. 129 * 130 * @param index: Requested index in range [0, size()-1]. 131 * @return ElementType&: Reference to the element. 132 */ 133 ElementType &operator[](size_t index); 134 const ElementType &operator[](size_t index) const; 135 136 /** 137 * Obtain the last element in the queue. 138 * It is illegal to call this function when empty() == true. 139 * 140 * @return ElementType&: Reference to the last element. 141 */ 142 ElementType &back(); 143 const ElementType &back() const; 144 145 /** 146 * Obtain the first element in the queue. 147 * It is illegal to call this function when empty() == true. 148 * 149 * @return ElementType&: Reference to the first element. 150 */ 151 ElementType &front(); 152 const ElementType &front() const; 153 154 /** 155 * Remove the first element from the queue. 156 * It is illegal to call this function when empty() == true. 157 */ 158 void pop_front(); 159 160 /** 161 * Provide the same pop API like std::queue/chre::ArrayQueue that do 162 * pop_front(). It is illegal to call this function when empty() == true. 163 */ 164 void pop(); 165 166 /** 167 * Removes an element from the queue by given index. 168 * 169 * @param index: Index of the item that will be removed. 170 * @return false: Returns false if index >= size(). 171 */ 172 bool remove(size_t index); 173 174 /** 175 * Function used to decide if an element in the queue matches a certain 176 * condition. 177 * 178 * @see removeMatchesFromBack and searchMatches. 179 */ 180 using MatchingFunction = 181 typename std::conditional<std::is_pointer<ElementType>::value || 182 std::is_fundamental<ElementType>::value, 183 bool(ElementType, void *, void *), 184 bool(ElementType &, void *, void *)>::type; 185 186 using FreeFunction = 187 typename std::conditional<std::is_pointer<ElementType>::value || 188 std::is_fundamental<ElementType>::value, 189 void(ElementType, void *), 190 void(ElementType &, void *)>::type; 191 /** 192 * Removes maxNumOfElementsRemoved of elements that satisfies matchFunc. 193 * 194 * If the queue has fewer items that matches the condition than 195 * maxNumOfElementsRemoved, it will remove all matching items and return the 196 * number of items that it actually removed. 197 * 198 * @param matchFunc Function used to decide if an item should 199 * be removed. Should return true if this 200 * item needs to be removed. 201 * @param data The data to be passed to the matchFunc. 202 * @param extraData The extra data to be passed to the 203 * matchFunc. 204 * @param maxNumOfElementsRemoved Number of elements to remove, also the 205 * size of removedElements. It is not 206 * guaranteed that the actual number of items 207 * removed will equal to this parameter since 208 * it will depend on the number of items that 209 * matches the condition. 210 * @param freeFunction Function to execute before the matched item 211 * is removed. If not supplied, the destructor 212 * of the element will be invoked. 213 * @param extraDataForFreeFunction Additional data that freeFunction will 214 * need. 215 * 216 * @return The number of pointers that is passed 217 * out. Returns SIZE_MAX if removedElement is 218 * a nullptr as error. 219 */ 220 size_t removeMatchedFromBack(MatchingFunction *matchFunction, void *data, 221 void *extraData, size_t maxNumOfElementsRemoved, 222 FreeFunction *freeFunction = nullptr, 223 void *extraDataForFreeFunction = nullptr); 224 225 private: 226 /** 227 * Push a new block to the end of storage to add storage space. 228 * The total block count after push cannot exceed kMaxBlockCount. 229 * 230 * @return true: Return true if a new block can be added. 231 */ 232 bool pushOneBlock(); 233 234 /** 235 * Insert one block to the underlying storage. 236 * The total block count after push cannot exceed kMaxBlockCount. 237 * 238 * @param blockIndex: The index to insert a block at. 239 * @return true: Return true if a new block can be added. 240 */ 241 bool insertBlock(size_t blockIndex); 242 243 /** 244 * Move count number of elements from srcIndex to destIndex. 245 * Note that index here refers to absolute index that starts from the head of 246 * the DynamicVector. 247 * 248 * @param srcIndex: The index of the first element to be moved. 249 * @param destIndex: The index of the destination to place the first moved 250 * element, absoluteIndexToRelative(srcIndex) needs to be bigger than 251 * absoluteIndexToRelative(destIndex). 252 * @param count: Number of element to move, it is illegal to call with count > 253 * size. 254 */ 255 256 void moveElements(size_t srcIndex, size_t destIndex, size_t count); 257 258 /** 259 * Clear the element in gapIndex, pull all elements behind forward 260 * to fill the gap and update mTail accordingly. 261 * 262 * @param gapIndex relative index of the gap. 263 */ 264 void pullForward(size_t gapIndex); 265 266 /** 267 * Clear the element in gapIndex, pull all elements before backward 268 * to fill the gap and update mHead accordingly. 269 * 270 * @param gapIndex relative index of the gap. 271 */ 272 void pullBackward(size_t gapIndex); 273 274 /** 275 * Move a movable item from srcIndex to destIndex. Note that index here refers 276 * to absolute index that starts from the head of the DynamicVector. 277 * 278 * @param srcIndex: Index to the block that has the source element. 279 * @param destIndex: Index to the start of the destination block. 280 */ 281 void doMove(size_t srcIndex, size_t destIndex, std::true_type); 282 283 /** 284 * Move a non-movable item from srcIndex to destIndex. Note that index here 285 * refers to absolute index that starts from the head of the DynamicVector. 286 * 287 * @param srcIndex: Index to the block that has the source element. 288 * @param destIndex: Index to the start of the destination block. 289 */ 290 void doMove(size_t srcIndex, size_t destIndex, std::false_type); 291 292 /** 293 * Calculate the index with respect to mHead to absolute index with respect to 294 * the start of the storage dynamic vector. 295 * 296 * @param index: Relative index in the range [0, mSize - 1]. 297 * @return size_t: The offset index in range [0, capacity() - 1]. 298 */ 299 size_t relativeIndexToAbsolute(size_t index); 300 301 /** 302 * Prepare push by pushing new blocks if needed and update mTail to point at 303 * the right index. 304 * 305 * @return false: Return false if the queue is already full. 306 */ 307 bool prepareForPush(); 308 309 /** 310 * Add 1 to the index if index is not at the end of the data storage. If so, 311 * wraps around to 0. 312 * 313 * @param index: Original index. 314 * @return size_t: New index after calculation. 315 */ 316 size_t advanceOrWrapAround(size_t index); 317 318 /** 319 * Subtract k steps to the index and wrap around if needed. 320 * 321 * @param index Original index. 322 * @param steps Number of steps that it needs to be subtracted. 323 * @return New index after calculation. 324 */ 325 size_t subtractOrWrapAround(size_t index, size_t steps); 326 327 /** 328 * Locate the data reference by absolute index. 329 * Note that this function does not check if the address belongs to 330 * this queue. 331 * 332 * @param index: The absolute index to find that data. 333 * @return ElementType&: Reference to the data. 334 */ 335 ElementType &locateDataAddress(size_t index); 336 337 /** 338 * Removes all the elements of the queue. 339 */ 340 void clear(); 341 342 /** 343 * Remove and destroy an object by the given index. 344 * Note that this function does not change any pointer nor fill the gap 345 * after removing. 346 * 347 * @param index: The absolute index for the item that will be removed. 348 */ 349 void doRemove(size_t index); 350 351 /** 352 * Calculate the index with respect to the start of the storage to relevant 353 * index with respect to mHead. 354 * 355 * @param index: Absolute index in the range [0, capacity() - 1]. 356 * @return size_t: Relative index in the range [0, mSize - 1]. 357 */ 358 size_t absoluteIndexToRelative(size_t index); 359 360 /** 361 * Resets the current queue to its initial state if the queue is empty. 362 * It is illegal to call this function if the queue is not empty. 363 */ 364 void resetEmptyQueue(); 365 366 /** 367 * Search the queue backwards to find foundIndicesLen of elements that matches 368 * a certain condition and return them by foundIndices. If the queue does not 369 * have enough elements, foundIndices will only be filled with the number that 370 * matches the condition. 371 * 372 * @param matchFunc Function used to decide if an item should be 373 * returned. Should return true if this item need 374 * to be returned. 375 * @param data The data to be passed to the matchFunc. 376 * @param extraData The extra data to be passed to the matchFunc. 377 * @param foundIndicesLen Length of foundIndices indicating how many index 378 * is targeted. 379 * @param foundIndices Indices that contains the element that matches 380 * the condition. Note that the index is 381 * returned in reversed order, i.e. the first 382 * element will contain the index closest to the 383 * end. 384 * @return the number of element that matches. 385 */ 386 size_t searchMatches(MatchingFunction *matchFunc, void *data, void *extraData, 387 size_t foundIndicesLen, size_t foundIndices[]); 388 389 /** 390 * Move elements in this queue to fill the gaps. 391 * 392 * @param gapCount Number of holes. 393 * @param gapIndices Indices that are empty. Need to be reverse order (first 394 * index is closest to the end of the queue). 395 */ 396 void fillGaps(size_t gapCount, const size_t gapIndices[]); 397 398 // TODO(b/258771255): See if we can change the container to 399 // ArrayQueue<UniquePtr<Block>> to minimize block moving during push_back. 400 //! The data storage of this segmented queue. 401 DynamicVector<UniquePtr<Block>> mRawStoragePtrs; 402 403 //! Records how many items are in this queue. 404 size_t mSize = 0; 405 406 //! The maximum block count this queue can hold. 407 const size_t kMaxBlockCount; 408 409 //! How many blocks allocated in constructor. 410 const size_t kStaticBlockCount; 411 412 //! The offset of the first element of the queue starting from the start of 413 //! the DynamicVector. 414 size_t mHead = 0; 415 416 // TODO(b/258828257): Modify initialization logic to make it work when 417 // kStaticBlockCount = 0 418 //! The offset of the last element of the queue starting from the start of the 419 //! DynamicVector. Initialize it to the end of container for a easier 420 //! implementation of push_back(). 421 size_t mTail = kBlockSize * kStaticBlockCount - 1; 422 }; 423 424 } // namespace chre 425 426 #include "chre/util/segmented_queue_impl.h" 427 428 #endif // CHRE_UTIL_SEGMENTED_QUEUE_H_ 429