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