1 #include "gtest/gtest.h"
2 #include "chre/util/array_queue.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 DummyElement {
17 public:
DummyElement()18 DummyElement() {
19 constructor_count++;
20 };
DummyElement(int i)21 DummyElement(int i) {
22 val_ = i;
23 constructor_count++;
24 };
~DummyElement()25 ~DummyElement() {
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 }
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<DummyElement, 3> q;
225 DummyElement 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 { ArrayQueue<DummyElement, 4> q;
246 DummyElement e;
247
248 for (size_t i = 0; i < 3; ++i) {
249 q.push(e);
250 q[i].setValue(i);
251 }
252
253 q.~ArrayQueue();
254
255 for (size_t i = 0; i < 3; ++i) {
256 EXPECT_EQ(1, destructor_count[i]);
257 }
258 }
259
260 // Check destructor count.
261 for (size_t i = 0; i < 3; ++i) {
262 EXPECT_EQ(1, destructor_count[i]);
263 }
264 EXPECT_EQ(0, destructor_count[3]);
265 EXPECT_EQ(1, destructor_count[kMaxTestCapacity - 1]);
266 }
267
TEST(ArrayQueueTest,EmplaceTest)268 TEST(ArrayQueueTest, EmplaceTest) {
269 constructor_count = 0;
270 ArrayQueue<DummyElement, 2> q;
271
272 EXPECT_TRUE(q.emplace(0));
273 EXPECT_EQ(1, constructor_count);
274 EXPECT_EQ(1, q.size());
275
276 EXPECT_TRUE(q.emplace(1));
277 EXPECT_EQ(2, constructor_count);
278 EXPECT_EQ(2, q.size());
279
280 EXPECT_FALSE(q.emplace(2));
281 EXPECT_EQ(2, constructor_count);
282 EXPECT_EQ(2, q.size());
283 }
284
TEST(ArrayQueueTest,EmptyQueueIterator)285 TEST(ArrayQueueTest, EmptyQueueIterator) {
286 ArrayQueue<int, 4> q;
287
288 ArrayQueue<int, 4>::iterator it = q.begin();
289 EXPECT_TRUE(it == q.end());
290 EXPECT_FALSE(it != q.end());
291 }
292
TEST(ArrayQueueTest,SimpleIterator)293 TEST(ArrayQueueTest, SimpleIterator) {
294 ArrayQueue<int, 4> q;
295 for (size_t i = 0; i < 3; ++i) {
296 q.push(i);
297 }
298 EXPECT_NE(q.begin(), q.end());
299
300 size_t index = 0;
301 for (ArrayQueue<int, 4>::iterator it = q.begin(); it != q.end(); ++it) {
302 EXPECT_EQ(q[index++], *it);
303 }
304 index = 0;
305 for (ArrayQueue<int, 4>::iterator it = q.begin(); it != q.end(); it++) {
306 EXPECT_EQ(q[index++], *it);
307 }
308
309 index = 0;
310 ArrayQueue<int, 4>::iterator it = q.begin();
311 while (it != q.end()) {
312 EXPECT_EQ(q[index++], *it++);
313 }
314
315 for (size_t i = 0; i < 3; ++i) {
316 q.pop();
317 q.push(i + 3);
318 }
319
320 index = 0;
321 it = q.begin();
322 while (it != q.end()) {
323 EXPECT_EQ(q[index++], *it++);
324 }
325
326 // Iterator concept checks: default constructible, copy assignable, copy
327 // constructible
328 ArrayQueue<int, 4>::iterator it2;
329 it2 = it;
330 EXPECT_EQ(it, it2);
331
332 ArrayQueue<int, 4>::iterator it3(it);
333 EXPECT_EQ(it, it3);
334 }
335
TEST(ArrayQueueTest,IteratorSwap)336 TEST(ArrayQueueTest, IteratorSwap) {
337 ArrayQueue<int, 2> q;
338 q.push(1);
339 q.push(2);
340
341 auto it1 = q.begin(), it2 = q.end();
342 std::swap(it1, it2);
343 EXPECT_EQ(it1, q.end());
344 EXPECT_EQ(it2, q.begin());
345 }
346
TEST(ArrayQueueTest,IteratorAndPush)347 TEST(ArrayQueueTest, IteratorAndPush) {
348 ArrayQueue<int, 4> q;
349 for (size_t i = 0; i < 2; ++i) {
350 q.push(i);
351 }
352
353 ArrayQueue<int, 4>::iterator it_b = q.begin();
354 ArrayQueue<int, 4>::iterator it_e = q.end();
355 q.push(3);
356
357 size_t index = 0;
358 while (it_b != it_e) {
359 EXPECT_EQ(q[index++], *it_b++);
360 }
361 }
362
TEST(ArrayQueueTest,IteratorAndPop)363 TEST(ArrayQueueTest, IteratorAndPop) {
364 ArrayQueue<int, 4> q;
365 for (size_t i = 0; i < 3; ++i) {
366 q.push(i);
367 }
368
369 ArrayQueue<int, 4>::iterator it_b = q.begin();
370 q.pop();
371 it_b++;
372
373 for (size_t i = 0; i < 2; ++i) {
374 EXPECT_EQ(q[i], *it_b++);
375 }
376 }
377
TEST(ArrayQueueTest,IteratorAndRemove)378 TEST(ArrayQueueTest, IteratorAndRemove) {
379 ArrayQueue<int, 4> q;
380 for (size_t i = 0; i < 2; ++i) {
381 q.push(i);
382 }
383
384 ArrayQueue<int, 4>::iterator it_b = q.begin();
385 q.remove(1);
386
387 EXPECT_EQ(q[0], *it_b);
388 }
389
TEST(ArrayQueueTest,IteratorAndEmplace)390 TEST(ArrayQueueTest, IteratorAndEmplace) {
391 ArrayQueue<int, 4> q;
392 for (size_t i = 0; i < 2; ++i) {
393 q.push(i);
394 }
395
396 ArrayQueue<int, 4>::iterator it_b = q.begin();
397 ArrayQueue<int, 4>::iterator it_e = q.end();
398 q.emplace(3);
399
400 size_t index = 0;
401 while (it_b != it_e) {
402 EXPECT_EQ(q[index++], *it_b++);
403 }
404 }
405
TEST(ArrayQueueTest,SimpleConstIterator)406 TEST(ArrayQueueTest, SimpleConstIterator) {
407 ArrayQueue<int, 4> q;
408 for (size_t i = 0; i < 3; ++i) {
409 q.push(i);
410 }
411
412 size_t index = 0;
413 for (ArrayQueue<int, 4>::const_iterator cit = q.cbegin();
414 cit != q.cend(); ++cit) {
415 EXPECT_EQ(q[index++], *cit);
416 }
417
418 index = 0;
419 ArrayQueue<int, 4>::const_iterator cit = q.cbegin();
420 while (cit != q.cend()) {
421 EXPECT_EQ(q[index++], *cit++);
422 }
423
424 for (size_t i = 0; i < 3; ++i) {
425 q.pop();
426 q.push(i + 3);
427 }
428
429 index = 0;
430 cit = q.cbegin();
431 while (cit != q.cend()) {
432 EXPECT_EQ(q[index++], *cit++);
433 }
434 }
435
TEST(ArrayQueueTest,Full)436 TEST(ArrayQueueTest, Full) {
437 ArrayQueue<size_t, 4> q;
438 for (size_t i = 0; i < 4; i++) {
439 EXPECT_FALSE(q.full());
440 q.push(i);
441 }
442
443 EXPECT_TRUE(q.full());
444 }
445
TEST(ArrayQueueTest,ArrayCopy)446 TEST(ArrayQueueTest, ArrayCopy) {
447 constexpr size_t kSize = 8;
448 ArrayQueue<size_t, kSize> q;
449 std::vector<size_t> v;
450 v.resize(kSize);
451
452 for (size_t i = 0; i < kSize; i++) {
453 q.push(i);
454
455 v.assign(kSize, 0xdeadbeef);
456 std::copy(q.begin(), q.end(), v.begin());
457
458 for (size_t j = 0; j < i; j++) {
459 EXPECT_EQ(q[j], v[j]);
460 EXPECT_EQ(*std::next(q.begin(), j), v[j]);
461 }
462 }
463 }
464
TEST(ArrayQueueTest,IteratorTraits)465 TEST(ArrayQueueTest, IteratorTraits) {
466 ArrayQueue<int, 2> q;
467 q.push(1234);
468 q.push(5678);
469
470 using traits = std::iterator_traits<decltype(q)::iterator>;
471 typename traits::difference_type diff = std::distance(q.begin(), q.end());
472 EXPECT_EQ(diff, q.size());
473
474 typename traits::value_type v = *q.begin();
475 EXPECT_EQ(v, q[0]);
476
477 typename traits::reference r = *q.begin();
478 r = 999;
479 EXPECT_EQ(r, q[0]);
480
481 typename traits::pointer p = &r;
482 EXPECT_EQ(*p, q[0]);
483
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<DummyElement, 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