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