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