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), bool(ElementType &)>::type; 184 185 using FreeFunction = 186 typename std::conditional<std::is_pointer<ElementType>::value || 187 std::is_fundamental<ElementType>::value, 188 void(ElementType, void *), 189 void(ElementType &, void *)>::type; 190 /** 191 * Removes maxNumOfElementsRemoved of elements that satisfies matchFunc. 192 * 193 * If the queue has fewer items that matches the condition than 194 * maxNumOfElementsRemoved, it will remove all matching items and return the 195 * number of items that it actually removed. 196 * 197 * @param matchFunc Function used to decide if an item should 198 * be removed. Should return true if this 199 * item needs to be removed. 200 * @param maxNumOfElementsRemoved Number of elements to remove, also the 201 * size of removedElements. It is not 202 * guaranteed that the actual number of items 203 * removed will equal to this parameter since 204 * it will depend on the number of items that 205 * matches the condition. 206 * @param removedElements Stores the pointers that has been 207 * removed. This cannot be a nullptr. 208 * @param freeFunction Function to execute before the matched item 209 * is removed. If not supplied, the destructor 210 * of the element will be invoked. 211 * @param extraDataForFreeFunction Additional data that freeFunction will 212 * need. 213 * 214 * @return The number of pointers that is passed 215 * out. Returns SIZE_MAX if removedElement is 216 * a nullptr as error. 217 */ 218 size_t removeMatchedFromBack(MatchingFunction *matchFunction, 219 size_t maxNumOfElementsRemoved, 220 FreeFunction *freeFunction = nullptr, 221 void *extraDataForFreeFunction = nullptr); 222 223 private: 224 /** 225 * Push a new block to the end of storage to add storage space. 226 * The total block count after push cannot exceed kMaxBlockCount. 227 * 228 * @return true: Return true if a new block can be added. 229 */ 230 bool pushOneBlock(); 231 232 /** 233 * Insert one block to the underlying storage. 234 * The total block count after push cannot exceed kMaxBlockCount. 235 * 236 * @param blockIndex: The index to insert a block at. 237 * @return true: Return true if a new block can be added. 238 */ 239 bool insertBlock(size_t blockIndex); 240 241 /** 242 * Move count number of elements from srcIndex to destIndex. 243 * Note that index here refers to absolute index that starts from the head of 244 * the DynamicVector. 245 * 246 * @param srcIndex: The index of the first element to be moved. 247 * @param destIndex: The index of the destination to place the first moved 248 * element. 249 * @param count: Number of element to move. 250 */ 251 252 void moveElements(size_t srcIndex, size_t destIndex, size_t count); 253 254 /** 255 * Move a movable item from srcIndex to destIndex. Note that index here refers 256 * to absolute index that starts from the head of the DynamicVector. 257 * 258 * @param srcIndex: Index to the block that has the source element. 259 * @param destIndex: Index to the start of the destination block. 260 */ 261 void doMove(size_t srcIndex, size_t destIndex, std::true_type); 262 263 /** 264 * Move a non-movable item from srcIndex to destIndex. Note that index here 265 * refers to absolute index that starts from the head of the DynamicVector. 266 * 267 * @param srcIndex: Index to the block that has the source element. 268 * @param destIndex: Index to the start of the destination block. 269 */ 270 void doMove(size_t srcIndex, size_t destIndex, std::false_type); 271 272 /** 273 * Calculate the index with respect to mHead to absolute index with respect to 274 * the start of the storage dynamic vector. 275 * 276 * @param index: Relative index in the range [0, mSize - 1]. 277 * @return size_t: The offset index in range [0, capacity() - 1]. 278 */ 279 size_t relativeIndexToAbsolute(size_t index); 280 281 /** 282 * Prepare push by pushing new blocks if needed and update mTail to point at 283 * the right index. 284 * 285 * @return false: Return false if the queue is already full. 286 */ 287 bool prepareForPush(); 288 289 /** 290 * Add 1 to the index if index is not at the end of the data storage. If so, 291 * wraps around to 0. 292 * 293 * @param index: Original index. 294 * @return size_t: New index after calculation. 295 */ 296 size_t advanceOrWrapAround(size_t index); 297 298 /** 299 * Subtract k steps to the index and wrap around if needed. 300 * 301 * @param index Original index. 302 * @param steps Number of steps that it needs to be subtracted. 303 * @return New index after calculation. 304 */ 305 size_t subtractOrWrapAround(size_t index, size_t steps); 306 307 /** 308 * Locate the data reference by absolute index. 309 * Note that this function does not check if the address belongs to 310 * this queue. 311 * 312 * @param index: The absolute index to find that data. 313 * @return ElementType&: Reference to the data. 314 */ 315 ElementType &locateDataAddress(size_t index); 316 317 /** 318 * Removes all the elements of the queue. 319 */ 320 void clear(); 321 322 /** 323 * Remove and destroy an object by the given index. 324 * Note that this function does not change any pointer nor fill the gap 325 * after removing. 326 * 327 * @param index: The absolute index for the item that will be removed. 328 */ 329 void doRemove(size_t index); 330 331 /** 332 * Calculate the index with respect to the start of the storage to relevant 333 * index with respect to mHead. 334 * 335 * @param index: Absolute index in the range [0, capacity() - 1]. 336 * @return size_t: Relative index in the range [0, mSize - 1]. 337 */ 338 size_t absoluteIndexToRelative(size_t index); 339 340 /** 341 * Resets the current queue to its initial state if the queue is empty. 342 * It is illegal to call this function if the queue is not empty. 343 */ 344 void resetEmptyQueue(); 345 346 /** 347 * Search the queue backwards to find foundIndicesLen of elements that matches 348 * a certain condition and return them by foundIndices. If the queue does not 349 * have enough elements, foundIndices will only be filled with the number that 350 * matches the condition. 351 * 352 * @param matchFunc Function used to decide if an item should be 353 * returned. Should return true if this item need 354 * to be returned. 355 * @param foundIndicesLen Length of foundIndices indicating how many index 356 * is targeted. 357 * @param foundIndices Indices that contains the element that matches 358 * the condition. Note that the index is 359 * returned in reversed order, i.e. the first 360 * element will contain the index closest to the 361 * end. 362 * @return the number of element that matches. 363 */ 364 size_t searchMatches(MatchingFunction *matchFunc, size_t foundIndicesLen, 365 size_t foundIndices[]); 366 367 /** 368 * Move elements in this queue to fill the gaps. 369 * 370 * @param gapCount Number of holes. 371 * @param gapIndices Indices that are empty. Need to be reverse order (first 372 * index is closest to the end of the queue). 373 */ 374 void fillGaps(size_t gapCount, const size_t gapIndices[]); 375 376 // TODO(b/258771255): See if we can change the container to 377 // ArrayQueue<UniquePtr<Block>> to minimize block moving during push_back. 378 //! The data storage of this segmented queue. 379 DynamicVector<UniquePtr<Block>> mRawStoragePtrs; 380 381 //! Records how many items are in this queue. 382 size_t mSize = 0; 383 384 //! The maximum block count this queue can hold. 385 const size_t kMaxBlockCount; 386 387 //! How many blocks allocated in constructor. 388 const size_t kStaticBlockCount; 389 390 //! The offset of the first element of the queue starting from the start of 391 //! the DynamicVector. 392 size_t mHead = 0; 393 394 // TODO(b/258828257): Modify initialization logic to make it work when 395 // kStaticBlockCount = 0 396 //! The offset of the last element of the queue starting from the start of the 397 //! DynamicVector. Initialize it to the end of container for a easier 398 //! implementation of push_back(). 399 size_t mTail = kBlockSize * kStaticBlockCount - 1; 400 }; 401 402 } // namespace chre 403 404 #include "chre/util/segmented_queue_impl.h" 405 406 #endif // CHRE_UTIL_SEGMENTED_QUEUE_H_