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_IMPL_H
18 #define CHRE_UTIL_SEGMENTED_QUEUE_IMPL_H
19
20 // IWYU pragma: private
21 #include <algorithm>
22 #include <type_traits>
23 #include <utility>
24
25 #include "chre/util/container_support.h"
26 #include "chre/util/segmented_queue.h"
27 #include "chre/util/unique_ptr.h"
28
29 namespace chre {
30
31 template <typename ElementType, size_t kBlockSize>
SegmentedQueue(size_t maxBlockCount,size_t staticBlockCount)32 SegmentedQueue<ElementType, kBlockSize>::SegmentedQueue(size_t maxBlockCount,
33 size_t staticBlockCount)
34 : kMaxBlockCount(maxBlockCount), kStaticBlockCount(staticBlockCount) {
35 CHRE_ASSERT(kMaxBlockCount >= kStaticBlockCount);
36 CHRE_ASSERT(kStaticBlockCount > 0);
37 CHRE_ASSERT(kMaxBlockCount * kBlockSize < SIZE_MAX);
38 mRawStoragePtrs.reserve(kMaxBlockCount);
39 for (size_t i = 0; i < kStaticBlockCount; i++) {
40 pushOneBlock();
41 }
42 }
43
44 template <typename ElementType, size_t kBlockSize>
~SegmentedQueue()45 SegmentedQueue<ElementType, kBlockSize>::~SegmentedQueue() {
46 clear();
47 }
48
49 template <typename ElementType, size_t kBlockSize>
push_back(const ElementType & element)50 bool SegmentedQueue<ElementType, kBlockSize>::push_back(
51 const ElementType &element) {
52 if (!prepareForPush()) {
53 return false;
54 }
55 new (&locateDataAddress(mTail)) ElementType(element);
56 mSize++;
57
58 return true;
59 }
60
61 template <typename ElementType, size_t kBlockSize>
push_back(ElementType && element)62 bool SegmentedQueue<ElementType, kBlockSize>::push_back(ElementType &&element) {
63 if (!prepareForPush()) {
64 return false;
65 }
66 new (&locateDataAddress(mTail)) ElementType(std::move(element));
67 mSize++;
68
69 return true;
70 }
71
72 template <typename ElementType, size_t kBlockSize>
push(const ElementType & element)73 bool SegmentedQueue<ElementType, kBlockSize>::push(const ElementType &element) {
74 return push_back(element);
75 }
76
77 template <typename ElementType, size_t kBlockSize>
push(ElementType && element)78 bool SegmentedQueue<ElementType, kBlockSize>::push(ElementType &&element) {
79 return push_back(std::move(element));
80 }
81
82 template <typename ElementType, size_t kBlockSize>
83 template <typename... Args>
emplace_back(Args &&...args)84 bool SegmentedQueue<ElementType, kBlockSize>::emplace_back(Args &&...args) {
85 if (!prepareForPush()) {
86 return false;
87 }
88 new (&locateDataAddress(mTail)) ElementType(std::forward<Args>(args)...);
89 mSize++;
90
91 return true;
92 }
93
94 template <typename ElementType, size_t kBlockSize>
95 ElementType &SegmentedQueue<ElementType, kBlockSize>::operator[](size_t index) {
96 CHRE_ASSERT(index < mSize);
97
98 return locateDataAddress(relativeIndexToAbsolute(index));
99 }
100
101 template <typename ElementType, size_t kBlockSize>
102 const ElementType &SegmentedQueue<ElementType, kBlockSize>::operator[](
103 size_t index) const {
104 CHRE_ASSERT(index < mSize);
105
106 return locateDataAddress(relativeIndexToAbsolute(index));
107 }
108
109 template <typename ElementType, size_t kBlockSize>
back()110 ElementType &SegmentedQueue<ElementType, kBlockSize>::back() {
111 CHRE_ASSERT(!empty());
112
113 return locateDataAddress(mTail);
114 }
115
116 template <typename ElementType, size_t kBlockSize>
back()117 const ElementType &SegmentedQueue<ElementType, kBlockSize>::back() const {
118 CHRE_ASSERT(!empty());
119
120 return locateDataAddress(mTail);
121 }
122
123 template <typename ElementType, size_t kBlockSize>
front()124 ElementType &SegmentedQueue<ElementType, kBlockSize>::front() {
125 CHRE_ASSERT(!empty());
126
127 return locateDataAddress(mHead);
128 }
129
130 template <typename ElementType, size_t kBlockSize>
front()131 const ElementType &SegmentedQueue<ElementType, kBlockSize>::front() const {
132 CHRE_ASSERT(!empty());
133
134 return locateDataAddress(mHead);
135 }
136
137 template <typename ElementType, size_t kBlockSize>
pop_front()138 void SegmentedQueue<ElementType, kBlockSize>::pop_front() {
139 CHRE_ASSERT(!empty());
140
141 doRemove(mHead);
142
143 if (mSize == 0) {
144 // TODO(b/258860898), Define a more proactive way to deallocate unused
145 // block.
146 resetEmptyQueue();
147 } else {
148 mHead = advanceOrWrapAround(mHead);
149 }
150 }
151
152 template <typename ElementType, size_t kBlockSize>
pop()153 void SegmentedQueue<ElementType, kBlockSize>::pop() {
154 pop_front();
155 }
156
157 template <typename ElementType, size_t kBlockSize>
remove(size_t index)158 bool SegmentedQueue<ElementType, kBlockSize>::remove(size_t index) {
159 if (index >= mSize) {
160 return false;
161 }
162
163 if (index < mSize / 2) {
164 pullBackward(index);
165 } else {
166 pullForward(index);
167 }
168
169 if (mSize == 0) {
170 resetEmptyQueue();
171 }
172 return true;
173 }
174
175 template <typename ElementType, size_t kBlockSize>
searchMatches(MatchingFunction * matchFunc,void * data,void * extraData,size_t foundIndicesLen,size_t foundIndices[])176 size_t SegmentedQueue<ElementType, kBlockSize>::searchMatches(
177 MatchingFunction *matchFunc, void *data, void *extraData,
178 size_t foundIndicesLen, size_t foundIndices[]) {
179 size_t foundCount = 0;
180 size_t searchIndex = advanceOrWrapAround(mTail);
181 bool firstRound = true;
182
183 if (size() == 0) {
184 return 0;
185 }
186
187 // firstRound need to be checked since if the queue is full, the index after
188 // mTail will be mHead, leading to the loop falsely terminate in the first
189 // round.
190 while ((searchIndex != mHead || firstRound) &&
191 foundCount != foundIndicesLen) {
192 searchIndex = subtractOrWrapAround(searchIndex, 1 /* steps */);
193 firstRound = false;
194 if (matchFunc(locateDataAddress(searchIndex), data, extraData)) {
195 foundIndices[foundCount] = searchIndex;
196 ++foundCount;
197 }
198 }
199 return foundCount;
200 }
201
202 template <typename ElementType, size_t kBlockSize>
fillGaps(size_t gapCount,const size_t gapIndices[])203 void SegmentedQueue<ElementType, kBlockSize>::fillGaps(
204 size_t gapCount, const size_t gapIndices[]) {
205 if (gapCount == 0) {
206 return;
207 }
208
209 // Move the elements between each gap indices section by section from the
210 // section that is closest to the head. The destination index = the gap index
211 // - how many gaps has been filled.
212 //
213 // For instance, assuming we have elements that we want to remove (gaps) at
214 // these indices = [8, 7, 5, 2] and the last element is at index 10.
215 //
216 // The first iteration will move the items at index 3, 4, which is the first
217 // section, to index 2, 3 and overwrite the original item at index 2, making
218 // the queue: [0, 1, 3, 4, x, 5, 6, ...., 10] where x means empty slot.
219 //
220 // The second iteration will do a similar thing, move item 6 to the empty
221 // slot, which could be calculated by using the index of the last gap and how
222 // many gaps has been filled. So the queue turns into:
223 // [0, 1, 3, 4, 6, x, x, 7, 8, 9, 10], note that there are now two empty slots
224 // since there are two gaps filled.
225 //
226 // The third iteration does not move anything since there are no items between
227 // 7 and 8.
228 //
229 // The final iteration is a special case to close the final gap. After the
230 // final iteration, the queue will become: [1, 3, 4, 6, 9, 10].
231
232 for (size_t i = gapCount - 1; i > 0; --i) {
233 moveElements(advanceOrWrapAround(gapIndices[i]),
234 subtractOrWrapAround(gapIndices[i], gapCount - 1 - i),
235 absoluteIndexToRelative(gapIndices[i - 1]) -
236 absoluteIndexToRelative(gapIndices[i]) - 1);
237 }
238
239 // Since mTail is not guaranteed to be a gap, we need to make a special case
240 // for moving the last section.
241 moveElements(
242 advanceOrWrapAround(gapIndices[0]),
243 subtractOrWrapAround(gapIndices[0], gapCount - 1),
244 absoluteIndexToRelative(mTail) - absoluteIndexToRelative(gapIndices[0]));
245 mTail = subtractOrWrapAround(mTail, gapCount);
246 }
247
248 template <typename ElementType, size_t kBlockSize>
removeMatchedFromBack(MatchingFunction * matchFunc,void * data,void * extraData,size_t maxNumOfElementsRemoved,FreeFunction * freeFunction,void * extraDataForFreeFunction)249 size_t SegmentedQueue<ElementType, kBlockSize>::removeMatchedFromBack(
250 MatchingFunction *matchFunc, void *data, void *extraData,
251 size_t maxNumOfElementsRemoved, FreeFunction *freeFunction,
252 void *extraDataForFreeFunction) {
253 constexpr size_t kRemoveItemInOneIter = 5;
254 size_t removeIndex[kRemoveItemInOneIter];
255 size_t currentRemoveCount =
256 std::min(maxNumOfElementsRemoved, kRemoveItemInOneIter);
257 size_t totalRemovedItemCount = 0;
258
259 while (currentRemoveCount != 0) {
260 // TODO(b/343282484): We will search the same elements multiple times, make sure we start
261 // from a unsearch index in the next iteration.
262 size_t removedItemCount = searchMatches(matchFunc, data, extraData,
263 currentRemoveCount, removeIndex);
264 totalRemovedItemCount += removedItemCount;
265
266 if (removedItemCount == 0) {
267 break;
268 }
269
270 for (size_t i = 0; i < removedItemCount; ++i) {
271 if (freeFunction == nullptr) {
272 doRemove(removeIndex[i]);
273 } else {
274 --mSize;
275 freeFunction(locateDataAddress(removeIndex[i]),
276 extraDataForFreeFunction);
277 }
278 }
279 if (mSize == 0) {
280 resetEmptyQueue();
281 } else {
282 fillGaps(removedItemCount, removeIndex);
283 }
284
285 maxNumOfElementsRemoved -= removedItemCount;
286 currentRemoveCount =
287 std::min(maxNumOfElementsRemoved, kRemoveItemInOneIter);
288 }
289
290 return totalRemovedItemCount;
291 }
292
293 template <typename ElementType, size_t kBlockSize>
pushOneBlock()294 bool SegmentedQueue<ElementType, kBlockSize>::pushOneBlock() {
295 return insertBlock(mRawStoragePtrs.size());
296 }
297
298 template <typename ElementType, size_t kBlockSize>
insertBlock(size_t blockIndex)299 bool SegmentedQueue<ElementType, kBlockSize>::insertBlock(size_t blockIndex) {
300 // Supporting inserting at any index since we started this data structure as
301 // std::deque and would like to support push_front() in the future. This
302 // function should not be needed once b/258771255 is implemented.
303 CHRE_ASSERT(mRawStoragePtrs.size() != kMaxBlockCount);
304 bool success = false;
305
306 Block *newBlockPtr = static_cast<Block *>(memoryAlloc(sizeof(Block)));
307 if (newBlockPtr != nullptr) {
308 success = mRawStoragePtrs.insert(blockIndex, UniquePtr(newBlockPtr));
309 if (success) {
310 if (!empty() && mHead >= blockIndex * kBlockSize) {
311 // If we are inserting a block before the current mHead, we need to
312 // increase the offset since we now have a new gap from mHead to the
313 // head of the container.
314 mHead += kBlockSize;
315 }
316
317 // If mTail is after the new block, we want to move mTail to make sure
318 // that the queue is continuous.
319 if (mTail >= blockIndex * kBlockSize) {
320 moveElements((blockIndex + 1) * kBlockSize, blockIndex * kBlockSize,
321 (mTail + 1) % kBlockSize);
322 }
323 }
324 }
325 return success;
326 }
327
328 template <typename ElementType, size_t kBlockSize>
moveElements(size_t srcIndex,size_t destIndex,size_t count)329 void SegmentedQueue<ElementType, kBlockSize>::moveElements(size_t srcIndex,
330 size_t destIndex,
331 size_t count) {
332 CHRE_ASSERT(count <= mSize);
333 CHRE_ASSERT(absoluteIndexToRelative(srcIndex) >
334 absoluteIndexToRelative(destIndex));
335
336 while (count--) {
337 doMove(srcIndex, destIndex,
338 typename std::is_move_constructible<ElementType>::type());
339 srcIndex = advanceOrWrapAround(srcIndex);
340 destIndex = advanceOrWrapAround(destIndex);
341 }
342 }
343
344 template <typename ElementType, size_t kBlockSize>
pullForward(size_t gapIndex)345 void SegmentedQueue<ElementType, kBlockSize>::pullForward(size_t gapIndex) {
346 CHRE_ASSERT(gapIndex < mSize);
347
348 size_t gapAbsolute = relativeIndexToAbsolute(gapIndex);
349 size_t tailSize = absoluteIndexToRelative(mTail) - gapIndex;
350 size_t nextAbsolute = advanceOrWrapAround(gapAbsolute);
351 doRemove(gapAbsolute);
352 for (size_t i = 0; i < tailSize; ++i) {
353 doMove(nextAbsolute, gapAbsolute,
354 typename std::is_move_constructible<ElementType>::type());
355 gapAbsolute = nextAbsolute;
356 nextAbsolute = advanceOrWrapAround(nextAbsolute);
357 }
358 mTail = subtractOrWrapAround(mTail, /* steps= */ 1);
359 }
360
361 template <typename ElementType, size_t kBlockSize>
pullBackward(size_t gapIndex)362 void SegmentedQueue<ElementType, kBlockSize>::pullBackward(size_t gapIndex) {
363 CHRE_ASSERT(gapIndex < mSize);
364
365 size_t headSize = gapIndex;
366 size_t gapAbsolute = relativeIndexToAbsolute(gapIndex);
367 size_t prevAbsolute = subtractOrWrapAround(gapAbsolute, /* steps= */ 1);
368 doRemove(gapAbsolute);
369 for (size_t i = 0; i < headSize; ++i) {
370 doMove(prevAbsolute, gapAbsolute,
371 typename std::is_move_constructible<ElementType>::type());
372 gapAbsolute = prevAbsolute;
373 prevAbsolute = subtractOrWrapAround(prevAbsolute, /* steps= */ 1);
374 }
375 mHead = advanceOrWrapAround(mHead);
376 }
377
378 template <typename ElementType, size_t kBlockSize>
doMove(size_t srcIndex,size_t destIndex,std::true_type)379 void SegmentedQueue<ElementType, kBlockSize>::doMove(size_t srcIndex,
380 size_t destIndex,
381 std::true_type) {
382 new (&locateDataAddress(destIndex))
383 ElementType(std::move(locateDataAddress(srcIndex)));
384 }
385
386 template <typename ElementType, size_t kBlockSize>
doMove(size_t srcIndex,size_t destIndex,std::false_type)387 void SegmentedQueue<ElementType, kBlockSize>::doMove(size_t srcIndex,
388 size_t destIndex,
389 std::false_type) {
390 new (&locateDataAddress(destIndex)) ElementType(locateDataAddress(srcIndex));
391 }
392
393 template <typename ElementType, size_t kBlockSize>
relativeIndexToAbsolute(size_t index)394 size_t SegmentedQueue<ElementType, kBlockSize>::relativeIndexToAbsolute(
395 size_t index) {
396 size_t absoluteIndex = mHead + index;
397 if (absoluteIndex >= capacity()) {
398 absoluteIndex -= capacity();
399 }
400 return absoluteIndex;
401 }
402
403 template <typename ElementType, size_t kBlockSize>
absoluteIndexToRelative(size_t index)404 size_t SegmentedQueue<ElementType, kBlockSize>::absoluteIndexToRelative(
405 size_t index) {
406 if (mHead > index) {
407 index += capacity();
408 }
409 return index - mHead;
410 }
411
412 template <typename ElementType, size_t kBlockSize>
prepareForPush()413 bool SegmentedQueue<ElementType, kBlockSize>::prepareForPush() {
414 bool success = false;
415 if (!full()) {
416 if (mSize == capacity()) {
417 // TODO(b/258771255): index-based insert block should go away when we
418 // have a ArrayQueue based container.
419 size_t insertBlockIndex = (mTail + 1) / kBlockSize;
420 success = insertBlock(insertBlockIndex);
421 } else {
422 success = true;
423 }
424 if (success) {
425 mTail = advanceOrWrapAround(mTail);
426 }
427 }
428
429 return success;
430 }
431
432 template <typename ElementType, size_t kBlockSize>
clear()433 void SegmentedQueue<ElementType, kBlockSize>::clear() {
434 if constexpr (!std::is_trivially_destructible<ElementType>::value) {
435 while (!empty()) {
436 pop_front();
437 }
438 } else {
439 mSize = 0;
440 mHead = 0;
441 mTail = capacity() - 1;
442 }
443 }
444
445 template <typename ElementType, size_t kBlockSize>
locateDataAddress(size_t index)446 ElementType &SegmentedQueue<ElementType, kBlockSize>::locateDataAddress(
447 size_t index) {
448 return mRawStoragePtrs[index / kBlockSize].get()->data()[index % kBlockSize];
449 }
450
451 template <typename ElementType, size_t kBlockSize>
advanceOrWrapAround(size_t index)452 size_t SegmentedQueue<ElementType, kBlockSize>::advanceOrWrapAround(
453 size_t index) {
454 return index >= capacity() - 1 ? 0 : index + 1;
455 }
456
457 template <typename ElementType, size_t kBlockSize>
subtractOrWrapAround(size_t index,size_t steps)458 size_t SegmentedQueue<ElementType, kBlockSize>::subtractOrWrapAround(
459 size_t index, size_t steps) {
460 return index < steps ? capacity() + index - steps : index - steps;
461 }
462
463 template <typename ElementType, size_t kBlockSize>
doRemove(size_t index)464 void SegmentedQueue<ElementType, kBlockSize>::doRemove(size_t index) {
465 mSize--;
466 locateDataAddress(index).~ElementType();
467 }
468
469 template <typename ElementType, size_t kBlockSize>
resetEmptyQueue()470 void SegmentedQueue<ElementType, kBlockSize>::resetEmptyQueue() {
471 CHRE_ASSERT(empty());
472
473 while (mRawStoragePtrs.size() != kStaticBlockCount) {
474 mRawStoragePtrs.pop_back();
475 }
476 mHead = 0;
477 mTail = capacity() - 1;
478 }
479
480 } // namespace chre
481
482 #endif // CHRE_UTIL_SEGMENTED_QUEUE_IMPL_H