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 #include "chre/util/segmented_queue.h"
18
19 #include <cstdlib>
20 #include <deque>
21 #include <vector>
22
23 #include "chre/util/enum.h"
24 #include "chre/util/non_copyable.h"
25 #include "gtest/gtest.h"
26
27 using chre::SegmentedQueue;
28 using std::deque;
29 using std::vector;
30
31 namespace {
32
33 class ConstructorCount {
34 public:
35 ConstructorCount() = default;
ConstructorCount(int value_,ssize_t * constructedCount)36 ConstructorCount(int value_, ssize_t *constructedCount)
37 : sConstructedCounter(constructedCount), value(value_) {
38 (*sConstructedCounter)++;
39 }
~ConstructorCount()40 ~ConstructorCount() {
41 (*sConstructedCounter)--;
42 }
getValue()43 int getValue() {
44 return value;
45 }
46
47 ssize_t *sConstructedCounter;
48
49 private:
50 int value;
51 };
52
53 constexpr int kConstructedMagic = 0xdeadbeef;
54 class CopyableButNonMovable {
55 public:
CopyableButNonMovable(int value)56 CopyableButNonMovable(int value) : mValue(value) {}
57
CopyableButNonMovable(const CopyableButNonMovable & other)58 CopyableButNonMovable(const CopyableButNonMovable &other) {
59 mValue = other.mValue;
60 }
61
operator =(const CopyableButNonMovable & other)62 CopyableButNonMovable &operator=(const CopyableButNonMovable &other) {
63 CHRE_ASSERT(mMagic == kConstructedMagic);
64 mValue = other.mValue;
65 return *this;
66 }
67
68 CopyableButNonMovable(CopyableButNonMovable &&other) = delete;
69 CopyableButNonMovable &operator=(CopyableButNonMovable &&other) = delete;
70
getValue() const71 int getValue() const {
72 return mValue;
73 }
74
75 private:
76 int mMagic = kConstructedMagic;
77 int mValue;
78 };
79
80 class MovableButNonCopyable : public chre::NonCopyable {
81 public:
MovableButNonCopyable(int value)82 MovableButNonCopyable(int value) : mValue(value) {}
83
MovableButNonCopyable(MovableButNonCopyable && other)84 MovableButNonCopyable(MovableButNonCopyable &&other) {
85 mValue = other.mValue;
86 other.mValue = -1;
87 }
88
operator =(MovableButNonCopyable && other)89 MovableButNonCopyable &operator=(MovableButNonCopyable &&other) {
90 CHRE_ASSERT(mMagic == kConstructedMagic);
91 mValue = other.mValue;
92 other.mValue = -1;
93 return *this;
94 }
95
getValue() const96 int getValue() const {
97 return mValue;
98 }
99
100 private:
101 int mMagic = kConstructedMagic;
102 int mValue;
103 };
104
105 enum class OperationType : uint8_t {
106 EMPLACE_BACK = 0,
107 PUSH_BACK,
108 POP_FRONT,
109 REMOVE,
110 BATCH_REMOVE,
111
112 OPERATION_TYPE_COUNT, // Must be at the end.
113 };
114
115 } // namespace
116
TEST(SegmentedQueue,InitialzedState)117 TEST(SegmentedQueue, InitialzedState) {
118 constexpr uint8_t blockSize = 5;
119 constexpr uint8_t maxBlockCount = 3;
120 constexpr uint8_t staticBlockCount = 2;
121 SegmentedQueue<int, blockSize> segmentedQueue(maxBlockCount,
122 staticBlockCount);
123
124 EXPECT_EQ(segmentedQueue.block_count(), staticBlockCount);
125 EXPECT_EQ(segmentedQueue.capacity(), staticBlockCount * blockSize);
126 EXPECT_EQ(segmentedQueue.size(), 0);
127 }
128
TEST(SegmentedQueue,PushAndRead)129 TEST(SegmentedQueue, PushAndRead) {
130 constexpr uint8_t blockSize = 5;
131 constexpr uint8_t maxBlockCount = 3;
132 SegmentedQueue<int, blockSize> segmentedQueue(maxBlockCount);
133
134 for (uint32_t queueSize = 0; queueSize < blockSize * maxBlockCount;
135 queueSize++) {
136 EXPECT_TRUE(segmentedQueue.push_back(queueSize));
137 EXPECT_EQ(segmentedQueue.size(), queueSize + 1);
138 EXPECT_EQ(segmentedQueue[queueSize], queueSize);
139 EXPECT_EQ(segmentedQueue.back(), queueSize);
140 }
141
142 EXPECT_FALSE(segmentedQueue.push_back(10000));
143 EXPECT_EQ(segmentedQueue.size(), maxBlockCount * blockSize);
144 EXPECT_TRUE(segmentedQueue.full());
145 }
146
TEST(SegmentedQueue,EmplaceAndRead)147 TEST(SegmentedQueue, EmplaceAndRead) {
148 constexpr uint8_t blockSize = 5;
149 constexpr uint8_t maxBlockCount = 3;
150 ssize_t constructorCount = 0;
151 SegmentedQueue<ConstructorCount, blockSize> segmentedQueue(maxBlockCount);
152
153 for (uint32_t queueSize = 0; queueSize < blockSize * maxBlockCount;
154 queueSize++) {
155 ssize_t oldConstructedCounter = constructorCount;
156 EXPECT_TRUE(segmentedQueue.emplace_back(queueSize, &constructorCount));
157 EXPECT_EQ(segmentedQueue.size(), queueSize + 1);
158 EXPECT_EQ(segmentedQueue[queueSize].getValue(), queueSize);
159 EXPECT_EQ(segmentedQueue.back().getValue(), queueSize);
160 EXPECT_EQ(constructorCount, oldConstructedCounter + 1);
161 }
162
163 EXPECT_FALSE(segmentedQueue.emplace_back(10000, &constructorCount));
164 EXPECT_EQ(segmentedQueue.size(), maxBlockCount * blockSize);
165 EXPECT_TRUE(segmentedQueue.full());
166 }
167
TEST(SegmentedQueue,PushAndReadCopyableButNonMovable)168 TEST(SegmentedQueue, PushAndReadCopyableButNonMovable) {
169 constexpr uint8_t blockSize = 5;
170 constexpr uint8_t maxBlockCount = 3;
171 SegmentedQueue<CopyableButNonMovable, blockSize> segmentedQueue(
172 maxBlockCount);
173
174 for (uint32_t queueSize = 0; queueSize < blockSize * maxBlockCount;
175 queueSize++) {
176 CopyableButNonMovable cbnm(queueSize);
177 EXPECT_TRUE(segmentedQueue.push_back(cbnm));
178 EXPECT_EQ(segmentedQueue.size(), queueSize + 1);
179 EXPECT_EQ(segmentedQueue[queueSize].getValue(), queueSize);
180 EXPECT_EQ(segmentedQueue.back().getValue(), queueSize);
181 }
182 }
183
TEST(SegmentedQueue,PushAndReadMovableButNonCopyable)184 TEST(SegmentedQueue, PushAndReadMovableButNonCopyable) {
185 constexpr uint8_t blockSize = 5;
186 constexpr uint8_t maxBlockCount = 3;
187 SegmentedQueue<MovableButNonCopyable, blockSize> segmentedQueue(
188 maxBlockCount);
189
190 for (uint8_t blockIndex = 0; blockIndex < maxBlockCount; blockIndex++) {
191 for (uint8_t index = 0; index < blockSize; index++) {
192 int value = segmentedQueue.size();
193 EXPECT_TRUE(segmentedQueue.emplace_back(value));
194 EXPECT_EQ(segmentedQueue.size(), value + 1);
195 EXPECT_EQ(segmentedQueue[value].getValue(), value);
196 EXPECT_EQ(segmentedQueue.back().getValue(), value);
197 }
198 }
199 }
200
TEST(SegmentedQueue,ReadAndPop)201 TEST(SegmentedQueue, ReadAndPop) {
202 constexpr uint8_t blockSize = 5;
203 constexpr uint8_t maxBlockCount = 3;
204 SegmentedQueue<ConstructorCount, blockSize> segmentedQueue(maxBlockCount);
205 ssize_t constructedCounter = 0;
206
207 for (uint32_t index = 0; index < blockSize * maxBlockCount; index++) {
208 EXPECT_TRUE(segmentedQueue.emplace_back(index, &constructedCounter));
209 }
210
211 uint8_t originalQueueSize = segmentedQueue.size();
212 for (uint8_t index = 0; index < originalQueueSize; index++) {
213 EXPECT_EQ(segmentedQueue[index].getValue(), index);
214 }
215
216 size_t capacityBeforePop = segmentedQueue.capacity();
217 while (!segmentedQueue.empty()) {
218 ASSERT_EQ(segmentedQueue.front().getValue(),
219 originalQueueSize - segmentedQueue.size());
220 ssize_t oldConstructedCounter = constructedCounter;
221 segmentedQueue.pop_front();
222 EXPECT_EQ(oldConstructedCounter - 1, constructedCounter);
223 }
224
225 EXPECT_EQ(segmentedQueue.size(), 0);
226 EXPECT_TRUE(segmentedQueue.empty());
227 EXPECT_LT(segmentedQueue.capacity(), capacityBeforePop);
228 EXPECT_GT(segmentedQueue.capacity(), 0);
229 }
230
TEST(SegmentedQueue,RemoveTest)231 TEST(SegmentedQueue, RemoveTest) {
232 constexpr uint8_t blockSize = 2;
233 constexpr uint8_t maxBlockCount = 3;
234 SegmentedQueue<int, blockSize> segmentedQueue(maxBlockCount);
235
236 for (uint32_t index = 0; index < blockSize * maxBlockCount; index++) {
237 EXPECT_TRUE(segmentedQueue.push_back(index));
238 }
239
240 // segmentedQueue = [[0, 1], [2, 3], [4, 5]]
241 EXPECT_FALSE(segmentedQueue.remove(segmentedQueue.size()));
242
243 EXPECT_TRUE(segmentedQueue.remove(4));
244 EXPECT_EQ(segmentedQueue[4], 5);
245 EXPECT_EQ(segmentedQueue[3], 3);
246 EXPECT_EQ(segmentedQueue.size(), 5);
247
248 EXPECT_TRUE(segmentedQueue.remove(1));
249 EXPECT_EQ(segmentedQueue[3], 5);
250 EXPECT_EQ(segmentedQueue[1], 2);
251 EXPECT_EQ(segmentedQueue[0], 0);
252 EXPECT_EQ(segmentedQueue.size(), 4);
253
254 size_t currentSize = segmentedQueue.size();
255 size_t capacityBeforeRemove = segmentedQueue.capacity();
256 while (currentSize--) {
257 EXPECT_TRUE(segmentedQueue.remove(0));
258 }
259
260 EXPECT_EQ(segmentedQueue.size(), 0);
261 EXPECT_TRUE(segmentedQueue.empty());
262 EXPECT_LT(segmentedQueue.capacity(), capacityBeforeRemove);
263 EXPECT_GT(segmentedQueue.capacity(), 0);
264 }
265
TEST(SegmentedQueue,MiddleBlockTest)266 TEST(SegmentedQueue, MiddleBlockTest) {
267 // This test tests that the SegmentedQueue will behave correctly when
268 // the reference of front() and back() are not aligned to the head/back
269 // of a block.
270
271 constexpr uint8_t blockSize = 3;
272 constexpr uint8_t maxBlockCount = 3;
273 SegmentedQueue<int, blockSize> segmentedQueue(maxBlockCount);
274
275 for (uint32_t index = 0; index < blockSize * (maxBlockCount - 1); index++) {
276 EXPECT_TRUE(segmentedQueue.push_back(index));
277 }
278
279 segmentedQueue.pop_front();
280 segmentedQueue.pop_front();
281 EXPECT_TRUE(segmentedQueue.push_back(6));
282 EXPECT_TRUE(segmentedQueue.push_back(7));
283
284 // segmentedQueue = [[6, 7, 2], [3, 4, 5], [X]]
285 EXPECT_EQ(segmentedQueue.front(), 2);
286 EXPECT_EQ(segmentedQueue.back(), 7);
287
288 EXPECT_TRUE(segmentedQueue.push_back(8));
289 EXPECT_EQ(segmentedQueue.back(), 8);
290
291 // segmentedQueue = [[x, x, 2], [3, 4, 5], [6, 7, 8]]
292 EXPECT_TRUE(segmentedQueue.push_back(9));
293 EXPECT_TRUE(segmentedQueue.push_back(10));
294
295 for (int i = 0; i < segmentedQueue.size(); i++) {
296 EXPECT_EQ(segmentedQueue[i], i + 2);
297 }
298 }
299
TEST(SegmentedQueue,RemoveMatchesEnoughItem)300 TEST(SegmentedQueue, RemoveMatchesEnoughItem) {
301 constexpr uint8_t blockSize = 3;
302 constexpr uint8_t maxBlockCount = 2;
303 ssize_t constCounter = 0;
304 SegmentedQueue<ConstructorCount, blockSize> segmentedQueue(maxBlockCount);
305
306 for (uint32_t index = 0; index < blockSize * maxBlockCount; index++) {
307 EXPECT_TRUE(segmentedQueue.emplace_back(index, &constCounter));
308 }
309
310 EXPECT_EQ(
311 3, segmentedQueue.removeMatchedFromBack(
312 [](ConstructorCount &element) { return element.getValue() <= 4; },
313 3));
314
315 EXPECT_EQ(segmentedQueue[0].getValue(), 0);
316 EXPECT_EQ(segmentedQueue[1].getValue(), 1);
317 EXPECT_EQ(segmentedQueue[2].getValue(), 5);
318 EXPECT_EQ(segmentedQueue.size(), blockSize * maxBlockCount - 3);
319 EXPECT_EQ(segmentedQueue.front().getValue(), 0);
320 EXPECT_EQ(segmentedQueue.back().getValue(), 5);
321 EXPECT_EQ(constCounter, 3);
322 }
323
TEST(SegmentedQueue,RemoveMatchesEmptyQueue)324 TEST(SegmentedQueue, RemoveMatchesEmptyQueue) {
325 constexpr uint8_t blockSize = 5;
326 constexpr uint8_t maxBlockCount = 2;
327 SegmentedQueue<int, blockSize> segmentedQueue(maxBlockCount);
328
329 EXPECT_EQ(0, segmentedQueue.removeMatchedFromBack(
330 [](int element) { return element >= 5; }, 3));
331 EXPECT_EQ(segmentedQueue.size(), 0);
332 }
333
TEST(SegmentedQueue,RemoveMatchesSingleElementQueue)334 TEST(SegmentedQueue, RemoveMatchesSingleElementQueue) {
335 constexpr uint8_t blockSize = 5;
336 constexpr uint8_t maxBlockCount = 2;
337 SegmentedQueue<int, blockSize> segmentedQueue(maxBlockCount);
338
339 EXPECT_TRUE(segmentedQueue.push_back(1));
340
341 EXPECT_EQ(1, segmentedQueue.removeMatchedFromBack(
342 [](int element) { return element == 1; }, 3));
343 EXPECT_EQ(segmentedQueue.size(), 0);
344 }
345
TEST(SegmentedQueue,RemoveMatchesTemp)346 TEST(SegmentedQueue, RemoveMatchesTemp) {
347 constexpr uint8_t blockSize = 5;
348 constexpr uint8_t maxBlockCount = 2;
349 SegmentedQueue<int, blockSize> segmentedQueue(maxBlockCount);
350
351 EXPECT_TRUE(segmentedQueue.push_back(1));
352
353 EXPECT_EQ(1, segmentedQueue.removeMatchedFromBack(
354 [](int element) { return element == 1; }, 3));
355 EXPECT_EQ(segmentedQueue.size(), 0);
356 }
357
TEST(SegmentedQueue,RemoveMatchesTailInMiddle)358 TEST(SegmentedQueue, RemoveMatchesTailInMiddle) {
359 constexpr uint8_t blockSize = 5;
360 constexpr uint8_t maxBlockCount = 2;
361 SegmentedQueue<int, blockSize> segmentedQueue(maxBlockCount);
362
363 for (uint32_t index = 0; index < blockSize * maxBlockCount; index++) {
364 EXPECT_TRUE(segmentedQueue.emplace_back(index));
365 }
366
367 segmentedQueue.pop();
368 segmentedQueue.pop();
369 segmentedQueue.push_back(blockSize * maxBlockCount);
370 segmentedQueue.push_back(blockSize * maxBlockCount + 1);
371
372 EXPECT_EQ(5, segmentedQueue.removeMatchedFromBack(
373 [](int item) { return item % 2 == 0; }, 10));
374 EXPECT_EQ(segmentedQueue.size(), 5);
375
376 EXPECT_EQ(segmentedQueue[0], 3);
377 EXPECT_EQ(segmentedQueue[1], 5);
378 EXPECT_EQ(segmentedQueue[2], 7);
379 EXPECT_EQ(segmentedQueue[3], 9);
380 EXPECT_EQ(segmentedQueue[4], 11);
381
382 EXPECT_EQ(segmentedQueue.front(), 3);
383 EXPECT_EQ(segmentedQueue.back(), 11);
384 }
385
TEST(SegmentedQueue,RemoveMatchesWithFreeCallback)386 TEST(SegmentedQueue, RemoveMatchesWithFreeCallback) {
387 constexpr uint8_t blockSize = 3;
388 constexpr uint8_t maxBlockCount = 2;
389 int8_t counter = 0;
390 SegmentedQueue<uint8_t, blockSize> segmentedQueue(maxBlockCount);
391
392 for (uint8_t index = 0; index < blockSize * maxBlockCount; ++index) {
393 EXPECT_TRUE(segmentedQueue.push_back(index));
394 }
395
396 EXPECT_EQ(3, segmentedQueue.removeMatchedFromBack(
397 [](uint8_t item) { return item % 2 == 0; }, 3,
398 [](uint8_t item, void *counter) {
399 *static_cast<int8_t *>(counter) -= item;
400 },
401 &counter));
402
403 EXPECT_EQ(counter, -6); // item 0, 2, 4 is removed.
404 EXPECT_EQ(segmentedQueue.size(), 3);
405 EXPECT_EQ(segmentedQueue.back(), 5);
406 EXPECT_EQ(segmentedQueue.front(), 1);
407 }
408
TEST(SegmentedQueue,PseudoRandomStressTest)409 TEST(SegmentedQueue, PseudoRandomStressTest) {
410 // This test uses std::deque as reference implementation to make sure
411 // that chre::SegmentedQueue is functioning correctly.
412
413 constexpr uint32_t maxIteration = 200;
414
415 constexpr uint32_t totalSize = 1024;
416 constexpr uint32_t blockSize = 16;
417
418 ssize_t referenceQueueConstructedCounter = 0;
419 ssize_t segmentedQueueConstructedCounter = 0;
420
421 std::srand(0xbeef);
422
423 deque<ConstructorCount> referenceDeque;
424 SegmentedQueue<ConstructorCount, blockSize> testSegmentedQueue(totalSize /
425 blockSize);
426
427 for (uint32_t currentIteration = 0; currentIteration < maxIteration;
428 currentIteration++) {
429 OperationType operationType = static_cast<OperationType>(
430 std::rand() % chre::asBaseType(OperationType::OPERATION_TYPE_COUNT));
431 int temp = std::rand();
432 switch (operationType) {
433 case OperationType::PUSH_BACK:
434 if (referenceDeque.size() < totalSize) {
435 ASSERT_TRUE(testSegmentedQueue.push_back(
436 ConstructorCount(temp, &segmentedQueueConstructedCounter)));
437 referenceDeque.push_back(
438 ConstructorCount(temp, &referenceQueueConstructedCounter));
439 } else {
440 ASSERT_FALSE(testSegmentedQueue.push_back(
441 ConstructorCount(temp, &segmentedQueueConstructedCounter)));
442 }
443 break;
444
445 case OperationType::EMPLACE_BACK:
446 if (referenceDeque.size() < totalSize) {
447 ASSERT_TRUE(testSegmentedQueue.emplace_back(
448 temp, &segmentedQueueConstructedCounter));
449 referenceDeque.emplace_back(temp, &referenceQueueConstructedCounter);
450 } else {
451 ASSERT_FALSE(testSegmentedQueue.emplace_back(
452 temp, &segmentedQueueConstructedCounter));
453 }
454 break;
455
456 case OperationType::POP_FRONT:
457 ASSERT_EQ(testSegmentedQueue.empty(), referenceDeque.empty());
458 if (!testSegmentedQueue.empty()) {
459 testSegmentedQueue.pop_front();
460 referenceDeque.pop_front();
461 }
462 break;
463
464 case OperationType::REMOVE: {
465 ASSERT_EQ(testSegmentedQueue.size(), referenceDeque.size());
466 if (!testSegmentedQueue.empty()) {
467 // Creates 50% chance for removing index that is out of bound
468 size_t index = std::rand() % (testSegmentedQueue.size() * 2);
469 if (index >= referenceDeque.size()) {
470 ASSERT_FALSE(testSegmentedQueue.remove(index));
471 } else {
472 ASSERT_TRUE(testSegmentedQueue.remove(index));
473 referenceDeque.erase(referenceDeque.begin() + index);
474 }
475 }
476 } break;
477
478 case OperationType::BATCH_REMOVE: {
479 ASSERT_EQ(testSegmentedQueue.size(), referenceDeque.size());
480 // Always try to remove a quarter of elements
481 size_t targetRemoveElement = referenceDeque.size() * 0.25;
482 vector<size_t> removedIndex;
483 for (int i = referenceDeque.size() - 1; i >= 0; i--) {
484 if (removedIndex.size() == targetRemoveElement) {
485 break;
486 } else if (referenceDeque[i].getValue() % 2 == 0) {
487 removedIndex.push_back(i);
488 }
489 }
490 for (auto idx : removedIndex) {
491 referenceDeque.erase(referenceDeque.begin() + idx);
492 }
493
494 ASSERT_EQ(removedIndex.size(), testSegmentedQueue.removeMatchedFromBack(
495 [](ConstructorCount &item) {
496 return item.getValue() % 2 == 0;
497 },
498 targetRemoveElement));
499 } break;
500
501 case OperationType::OPERATION_TYPE_COUNT:
502 // Should not be here, create this to prevent compiler error from
503 // -Wswitch.
504 FAIL();
505 break;
506 }
507
508 // Complete check
509 ASSERT_EQ(segmentedQueueConstructedCounter,
510 referenceQueueConstructedCounter);
511 ASSERT_EQ(testSegmentedQueue.size(), referenceDeque.size());
512 ASSERT_EQ(testSegmentedQueue.empty(), referenceDeque.empty());
513 if (!testSegmentedQueue.empty()) {
514 ASSERT_EQ(testSegmentedQueue.back().getValue(),
515 referenceDeque.back().getValue());
516 ASSERT_EQ(testSegmentedQueue.front().getValue(),
517 referenceDeque.front().getValue());
518 }
519 for (size_t idx = 0; idx < testSegmentedQueue.size(); idx++) {
520 ASSERT_EQ(testSegmentedQueue[idx].getValue(),
521 referenceDeque[idx].getValue());
522 }
523 }
524 }