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