1 /*
2 * Copyright (C) 2016 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/array_queue.h"
18 #include "gtest/gtest.h"
19
20 #include <algorithm>
21 #include <memory>
22 #include <type_traits>
23 #include <utility>
24 #include <vector>
25
26 using chre::ArrayQueue;
27 using chre::ArrayQueueExt;
28
29 namespace {
30 constexpr int kMaxTestCapacity = 10;
31 int destructor_count[kMaxTestCapacity];
32 int constructor_count;
33 int total_destructor_count;
34
35 class FakeElement {
36 public:
FakeElement()37 FakeElement() {
38 constructor_count++;
39 }
40
FakeElement(int i)41 FakeElement(int i) {
42 val_ = i;
43 constructor_count++;
44 }
45
~FakeElement()46 ~FakeElement() {
47 total_destructor_count++;
48 if (val_ >= 0 && val_ < kMaxTestCapacity) {
49 destructor_count[val_]++;
50 }
51 }
52
setValue(int i)53 void setValue(int i) {
54 val_ = i;
55 }
56
57 private:
58 int val_ = kMaxTestCapacity - 1;
59 };
60 } // namespace
61
TEST(ArrayQueueTest,IsEmptyInitially)62 TEST(ArrayQueueTest, IsEmptyInitially) {
63 ArrayQueue<int, 4> q;
64 EXPECT_TRUE(q.empty());
65 EXPECT_EQ(0, q.size());
66 }
67
TEST(ArrayQueueTest,SimplePushPop)68 TEST(ArrayQueueTest, SimplePushPop) {
69 ArrayQueue<int, 3> q;
70 EXPECT_TRUE(q.push(1));
71 EXPECT_TRUE(q.push(2));
72 q.pop();
73 EXPECT_TRUE(q.push(3));
74 }
75
TEST(ArrayQueueTest,SimplePushPopBackPush)76 TEST(ArrayQueueTest, SimplePushPopBackPush) {
77 ArrayQueue<int, 3> q;
78 EXPECT_TRUE(q.push(0));
79 EXPECT_TRUE(q.push(1));
80 EXPECT_TRUE(q.push(2));
81 q.pop_back();
82 EXPECT_EQ(2, q.size());
83 EXPECT_EQ(0, q[0]);
84 EXPECT_EQ(1, q[1]);
85
86 EXPECT_TRUE(q.push(3));
87 EXPECT_EQ(3, q.size());
88 EXPECT_EQ(0, q[0]);
89 EXPECT_EQ(1, q[1]);
90 EXPECT_EQ(3, q[2]);
91
92 q.pop_back();
93 q.pop_back();
94 q.pop_back();
95
96 EXPECT_EQ(0, q.size());
97 EXPECT_TRUE(q.push(4));
98 EXPECT_TRUE(q.push(5));
99 EXPECT_TRUE(q.push(6));
100 EXPECT_EQ(3, q.size());
101 EXPECT_EQ(4, q[0]);
102 EXPECT_EQ(5, q[1]);
103 EXPECT_EQ(6, q[2]);
104
105 q.pop();
106
107 EXPECT_TRUE(q.push(7));
108 EXPECT_EQ(5, q[0]);
109 EXPECT_EQ(6, q[1]);
110 EXPECT_EQ(7, q[2]);
111
112 q.pop_back();
113
114 EXPECT_EQ(5, q[0]);
115 EXPECT_EQ(6, q[1]);
116
117 q.pop();
118
119 EXPECT_EQ(6, q[0]);
120 }
121
TEST(ArrayQueueTest,TestSize)122 TEST(ArrayQueueTest, TestSize) {
123 ArrayQueue<int, 2> q;
124 q.push(1);
125 EXPECT_EQ(1, q.size());
126 q.push(2);
127 EXPECT_EQ(2, q.size());
128 q.pop();
129 EXPECT_EQ(1, q.size());
130 q.pop();
131 }
132
TEST(ArrayQueueTest,TestEmpty)133 TEST(ArrayQueueTest, TestEmpty) {
134 ArrayQueue<int, 2> q;
135 q.push(1);
136 EXPECT_FALSE(q.empty());
137 q.push(2);
138 EXPECT_FALSE(q.empty());
139 q.pop();
140 EXPECT_FALSE(q.empty());
141 q.pop();
142 EXPECT_TRUE(q.empty());
143 }
144
TEST(ArrayQueueTest,KickPushWhenNotFull)145 TEST(ArrayQueueTest, KickPushWhenNotFull) {
146 ArrayQueue<int, 2> q;
147 q.kick_push(1);
148 EXPECT_EQ(1, q.size());
149 EXPECT_EQ(1, q[0]);
150 q.kick_push(2);
151 EXPECT_EQ(2, q.size());
152 EXPECT_EQ(2, q[1]);
153 }
154
TEST(ArrayQueueTest,KickPushWhenFull)155 TEST(ArrayQueueTest, KickPushWhenFull) {
156 ArrayQueue<int, 2> q;
157 q.kick_push(1);
158 q.push(2);
159 EXPECT_EQ(2, q.size());
160 q.kick_push(3);
161 EXPECT_EQ(2, q.size());
162 EXPECT_EQ(2, q[0]);
163 EXPECT_EQ(3, q[1]);
164 }
165
TEST(ArrayQueueTest,PopWhenEmpty)166 TEST(ArrayQueueTest, PopWhenEmpty) {
167 ArrayQueue<int, 4> q;
168 q.pop();
169 EXPECT_EQ(0, q.size());
170 }
171
TEST(ArrayQueueTest,PopBackWhenEmpty)172 TEST(ArrayQueueTest, PopBackWhenEmpty) {
173 ArrayQueue<int, 4> q;
174 q.pop_back();
175 EXPECT_EQ(0, q.size());
176 }
177
TEST(ArrayQueueTest,PushWhenFull)178 TEST(ArrayQueueTest, PushWhenFull) {
179 ArrayQueue<int, 2> q;
180 q.push(1);
181 q.push(2);
182 EXPECT_FALSE(q.push(3));
183 }
184
TEST(ArrayQueueDeathTest,FrontWhenEmpty)185 TEST(ArrayQueueDeathTest, FrontWhenEmpty) {
186 ArrayQueue<int, 4> q;
187 EXPECT_DEATH(q.front(), "");
188 }
189
TEST(ArrayQueueDeathTest,BackWhenEmpty)190 TEST(ArrayQueueDeathTest, BackWhenEmpty) {
191 ArrayQueue<int, 4> q;
192 EXPECT_DEATH(q.back(), "");
193 }
194
TEST(ArrayQueueTest,TestFront)195 TEST(ArrayQueueTest, TestFront) {
196 ArrayQueue<int, 3> q;
197 q.push(1);
198 EXPECT_EQ(1, q.front());
199 q.pop();
200 q.push(2);
201 EXPECT_EQ(2, q.front());
202 q.push(3);
203 EXPECT_EQ(2, q.front());
204 }
205
TEST(ArrayQueueTest,TestBack)206 TEST(ArrayQueueTest, TestBack) {
207 ArrayQueue<int, 3> q;
208 q.push(1);
209 EXPECT_EQ(1, q.back()); // 1 x x
210 q.push(2);
211 EXPECT_EQ(2, q.back()); // 1 2 x
212 q.pop();
213 EXPECT_EQ(2, q.back()); // x 2 x
214 q.push(3);
215 EXPECT_EQ(3, q.back()); // x 2 3
216 q.push(4);
217 EXPECT_EQ(4, q.back()); // 4 2 3 (forward wrap-around)
218 q.pop_back();
219 EXPECT_EQ(3, q.back()); // x 2 3 (backwards wrap-around)
220 q.pop();
221 EXPECT_EQ(3, q.back()); // x x 3
222 }
223
TEST(ArrayQueueDeathTest,InvalidSubscript)224 TEST(ArrayQueueDeathTest, InvalidSubscript) {
225 ArrayQueue<int, 2> q;
226 EXPECT_DEATH(q[0], "");
227 }
228
TEST(ArrayQueueTest,Subscript)229 TEST(ArrayQueueTest, Subscript) {
230 ArrayQueue<int, 2> q;
231 q.push(1);
232 q.push(2);
233 EXPECT_EQ(1, q[0]);
234 EXPECT_EQ(2, q[1]);
235 q.pop();
236 EXPECT_EQ(2, q[0]);
237 }
238
TEST(ArrayQueueTest,RemoveWithInvalidIndex)239 TEST(ArrayQueueTest, RemoveWithInvalidIndex) {
240 ArrayQueue<int, 3> q;
241 EXPECT_FALSE(q.remove(0));
242 }
243
TEST(ArrayQueueTest,RemoveWithIndex)244 TEST(ArrayQueueTest, RemoveWithIndex) {
245 ArrayQueue<int, 5> q;
246 q.push(1);
247 q.push(2);
248 q.remove(0);
249 EXPECT_EQ(2, q.front());
250 EXPECT_EQ(1, q.size());
251 q.push(3);
252 q.push(4);
253 q.push(5);
254 q.remove(3);
255 int sampleArray[] = {2, 3, 5};
256 EXPECT_EQ(3, q.size());
257 for (size_t i = 0; i < q.size(); ++i) {
258 EXPECT_EQ(sampleArray[i], q.front());
259 q.remove(0);
260 }
261 }
262
TEST(ArrayQueueTest,DestructorCalledOnPop)263 TEST(ArrayQueueTest, DestructorCalledOnPop) {
264 for (size_t i = 0; i < kMaxTestCapacity; ++i) {
265 destructor_count[i] = 0;
266 }
267
268 ArrayQueue<FakeElement, 3> q;
269 FakeElement e;
270 q.push(e);
271 q.push(e);
272
273 q.front().setValue(0);
274 q.pop();
275 EXPECT_EQ(1, destructor_count[0]);
276
277 q.front().setValue(1);
278 q.pop();
279 EXPECT_EQ(1, destructor_count[1]);
280 }
281
TEST(ArrayQueueTest,ElementsDestructedWhenQueueDestructed)282 TEST(ArrayQueueTest, ElementsDestructedWhenQueueDestructed) {
283 for (size_t i = 0; i < kMaxTestCapacity; ++i) {
284 destructor_count[i] = 0;
285 }
286
287 // Put q and e in the scope so their destructor will be called going
288 // out of scope.
289 {
290 ArrayQueue<FakeElement, 4> q;
291 FakeElement e;
292
293 for (size_t i = 0; i < 3; ++i) {
294 q.push(e);
295 q[i].setValue(i);
296 }
297 }
298
299 // q should now be destroyed - check destructor count.
300 for (size_t i = 0; i < 3; ++i) {
301 EXPECT_EQ(1, destructor_count[i]);
302 }
303 EXPECT_EQ(0, destructor_count[3]);
304 EXPECT_EQ(1, destructor_count[kMaxTestCapacity - 1]);
305 }
306
TEST(ArrayQueueTest,EmplaceTest)307 TEST(ArrayQueueTest, EmplaceTest) {
308 constructor_count = 0;
309 ArrayQueue<FakeElement, 2> q;
310
311 EXPECT_TRUE(q.emplace(0));
312 EXPECT_EQ(1, constructor_count);
313 EXPECT_EQ(1, q.size());
314
315 EXPECT_TRUE(q.emplace(1));
316 EXPECT_EQ(2, constructor_count);
317 EXPECT_EQ(2, q.size());
318
319 EXPECT_FALSE(q.emplace(2));
320 EXPECT_EQ(2, constructor_count);
321 EXPECT_EQ(2, q.size());
322 }
323
TEST(ArrayQueueTest,EmptyQueueIterator)324 TEST(ArrayQueueTest, EmptyQueueIterator) {
325 ArrayQueue<int, 4> q;
326
327 ArrayQueue<int, 4>::iterator it = q.begin();
328 EXPECT_TRUE(it == q.end());
329 EXPECT_FALSE(it != q.end());
330 }
331
TEST(ArrayQueueTest,SimpleIterator)332 TEST(ArrayQueueTest, SimpleIterator) {
333 ArrayQueue<int, 4> q;
334 for (size_t i = 0; i < 3; ++i) {
335 q.push(i);
336 }
337 EXPECT_NE(q.begin(), q.end());
338
339 size_t index = 0;
340 for (ArrayQueue<int, 4>::iterator it = q.begin(); it != q.end(); ++it) {
341 EXPECT_EQ(q[index++], *it);
342 }
343 index = 0;
344 for (ArrayQueue<int, 4>::iterator it = q.begin(); it != q.end(); it++) {
345 EXPECT_EQ(q[index++], *it);
346 }
347
348 index = 0;
349 ArrayQueue<int, 4>::iterator it = q.begin();
350 while (it != q.end()) {
351 EXPECT_EQ(q[index++], *it++);
352 }
353
354 for (size_t i = 0; i < 3; ++i) {
355 q.pop();
356 q.push(i + 3);
357 }
358
359 index = 0;
360 it = q.begin();
361 while (it != q.end()) {
362 EXPECT_EQ(q[index++], *it++);
363 }
364
365 // Iterator concept checks: default constructible, copy assignable, copy
366 // constructible
367 ArrayQueue<int, 4>::iterator it2;
368 it2 = it;
369 EXPECT_EQ(it, it2);
370
371 ArrayQueue<int, 4>::iterator it3(it);
372 EXPECT_EQ(it, it3);
373 }
374
TEST(ArrayQueueTest,IteratorSwap)375 TEST(ArrayQueueTest, IteratorSwap) {
376 ArrayQueue<int, 2> q;
377 q.push(1);
378 q.push(2);
379
380 auto it1 = q.begin(), it2 = q.end();
381 std::swap(it1, it2);
382 EXPECT_EQ(it1, q.end());
383 EXPECT_EQ(it2, q.begin());
384 }
385
TEST(ArrayQueueTest,IteratorAndPush)386 TEST(ArrayQueueTest, IteratorAndPush) {
387 ArrayQueue<int, 4> q;
388 for (size_t i = 0; i < 2; ++i) {
389 q.push(i);
390 }
391
392 ArrayQueue<int, 4>::iterator it_b = q.begin();
393 ArrayQueue<int, 4>::iterator it_e = q.end();
394 q.push(3);
395
396 size_t index = 0;
397 while (it_b != it_e) {
398 EXPECT_EQ(q[index++], *it_b++);
399 }
400 }
401
TEST(ArrayQueueTest,IteratorAndPop)402 TEST(ArrayQueueTest, IteratorAndPop) {
403 ArrayQueue<int, 4> q;
404 for (size_t i = 0; i < 3; ++i) {
405 q.push(i);
406 }
407
408 ArrayQueue<int, 4>::iterator it_b = q.begin();
409 q.pop();
410 it_b++;
411
412 for (size_t i = 0; i < 2; ++i) {
413 EXPECT_EQ(q[i], *it_b++);
414 }
415 }
416
TEST(ArrayQueueTest,IteratorAndRemove)417 TEST(ArrayQueueTest, IteratorAndRemove) {
418 ArrayQueue<int, 4> q;
419 for (size_t i = 0; i < 2; ++i) {
420 q.push(i);
421 }
422
423 ArrayQueue<int, 4>::iterator it_b = q.begin();
424 q.remove(1);
425
426 EXPECT_EQ(q[0], *it_b);
427 }
428
TEST(ArrayQueueTest,IteratorAndEmplace)429 TEST(ArrayQueueTest, IteratorAndEmplace) {
430 ArrayQueue<int, 4> q;
431 for (size_t i = 0; i < 2; ++i) {
432 q.push(i);
433 }
434
435 ArrayQueue<int, 4>::iterator it_b = q.begin();
436 ArrayQueue<int, 4>::iterator it_e = q.end();
437 q.emplace(3);
438
439 size_t index = 0;
440 while (it_b != it_e) {
441 EXPECT_EQ(q[index++], *it_b++);
442 }
443 }
444
TEST(ArrayQueueTest,SimpleConstIterator)445 TEST(ArrayQueueTest, SimpleConstIterator) {
446 ArrayQueue<int, 4> q;
447 for (size_t i = 0; i < 3; ++i) {
448 q.push(i);
449 }
450
451 size_t index = 0;
452 for (ArrayQueue<int, 4>::const_iterator cit = q.cbegin(); cit != q.cend();
453 ++cit) {
454 EXPECT_EQ(q[index++], *cit);
455 }
456
457 index = 0;
458 ArrayQueue<int, 4>::const_iterator cit = q.cbegin();
459 while (cit != q.cend()) {
460 EXPECT_EQ(q[index++], *cit++);
461 }
462
463 for (size_t i = 0; i < 3; ++i) {
464 q.pop();
465 q.push(i + 3);
466 }
467
468 index = 0;
469 cit = q.cbegin();
470 while (cit != q.cend()) {
471 EXPECT_EQ(q[index++], *cit++);
472 }
473 }
474
TEST(ArrayQueueTest,Full)475 TEST(ArrayQueueTest, Full) {
476 ArrayQueue<size_t, 4> q;
477 for (size_t i = 0; i < 4; i++) {
478 EXPECT_FALSE(q.full());
479 q.push(i);
480 }
481
482 EXPECT_TRUE(q.full());
483 }
484
TEST(ArrayQueueTest,ArrayCopy)485 TEST(ArrayQueueTest, ArrayCopy) {
486 constexpr size_t kSize = 8;
487 ArrayQueue<size_t, kSize> q;
488 std::vector<size_t> v;
489 v.resize(kSize);
490
491 for (size_t i = 0; i < kSize; i++) {
492 q.push(i);
493
494 v.assign(kSize, 0xdeadbeef);
495 std::copy(q.begin(), q.end(), v.begin());
496
497 for (size_t j = 0; j < i; j++) {
498 EXPECT_EQ(q[j], v[j]);
499 EXPECT_EQ(*std::next(q.begin(), j), v[j]);
500 }
501 }
502 }
503
TEST(ArrayQueueTest,IteratorTraits)504 TEST(ArrayQueueTest, IteratorTraits) {
505 ArrayQueue<int, 2> q;
506 q.push(1234);
507 q.push(5678);
508
509 using traits = std::iterator_traits<decltype(q)::iterator>;
510 typename traits::difference_type diff = std::distance(q.begin(), q.end());
511 EXPECT_EQ(diff, q.size());
512
513 typename traits::value_type v = *q.begin();
514 EXPECT_EQ(v, q[0]);
515
516 typename traits::reference r = *q.begin();
517 r = 999;
518 EXPECT_EQ(r, q[0]);
519
520 typename traits::pointer p = &r;
521 EXPECT_EQ(*p, q[0]);
522
523 // Note: if the implementation is upgraded to another category like random
524 // access, then this static assert should be updated. It exists primarily to
525 // confirm that we are declaring an iterator_category
526 static_assert(
527 std::is_same<traits::iterator_category, std::forward_iterator_tag>::value,
528 "ArrayQueueIterator should be a forward iterator");
529 }
530
TEST(ArrayQueueTest,ArrayClear)531 TEST(ArrayQueueTest, ArrayClear) {
532 ArrayQueue<size_t, 4> q;
533
534 q.clear();
535 EXPECT_TRUE(q.empty());
536
537 for (size_t i = 0; i < 4; i++) {
538 q.push(i);
539 }
540
541 q.clear();
542 EXPECT_TRUE(q.empty());
543
544 // Make sure that insertion/access still work after a clear.
545 for (size_t i = 0; i < 4; i++) {
546 q.push(i);
547 }
548 for (size_t i = 0; i < 4; i++) {
549 EXPECT_EQ(q[i], i);
550 }
551 }
552
TEST(ArrayQueueTest,ElementsDestructedArrayClear)553 TEST(ArrayQueueTest, ElementsDestructedArrayClear) {
554 for (size_t i = 0; i < kMaxTestCapacity; ++i) {
555 destructor_count[i] = 0;
556 }
557 total_destructor_count = 0;
558
559 ArrayQueue<FakeElement, 4> q;
560 for (size_t i = 0; i < 3; ++i) {
561 q.emplace(i);
562 }
563
564 q.clear();
565
566 for (size_t i = 0; i < 3; ++i) {
567 EXPECT_EQ(1, destructor_count[i]);
568 }
569 EXPECT_EQ(3, total_destructor_count);
570 }
571
TEST(ArrayQueueExtTest,BasicTest)572 TEST(ArrayQueueExtTest, BasicTest) {
573 constexpr size_t kNumElements = 32;
574 int32_t array[kNumElements];
575 ArrayQueueExt<int32_t> q(array, kNumElements);
576
577 ASSERT_EQ(q.data(), array);
578 EXPECT_EQ(q.capacity(), kNumElements);
579
580 for (int i = 0; i < kNumElements; i++) {
581 q.push(i);
582 }
583
584 for (int i = 0; i < kNumElements; i++) {
585 EXPECT_EQ(array[i], q[i]);
586 }
587 }
588
TEST(ArrayQueueTest,KickPushNonCopyable)589 TEST(ArrayQueueTest, KickPushNonCopyable) {
590 ArrayQueue<std::unique_ptr<int>, 2> q;
591 auto p1 = std::make_unique<int>(42);
592 auto p2 = std::make_unique<int>(43);
593 auto p3 = std::make_unique<int>(44);
594
595 q.kick_push(std::move(p1));
596 EXPECT_EQ(q.size(), 1);
597 EXPECT_EQ(*q.front(), 42);
598 EXPECT_EQ(*q.back(), 42);
599
600 q.kick_push(std::move(p2));
601 EXPECT_EQ(q.size(), 2);
602 EXPECT_EQ(*q.front(), 42);
603 EXPECT_EQ(*q.back(), 43);
604
605 q.kick_push(std::move(p3));
606 EXPECT_EQ(q.size(), 2);
607 EXPECT_EQ(*q.front(), 43);
608 EXPECT_EQ(*q.back(), 44);
609 }
610