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 DummyElement {
17  public:
18   DummyElement() {
19     constructor_count++;
20   };
21   DummyElement(int i) {
22     val_ = i;
23     constructor_count++;
24   };
25   ~DummyElement() {
26     total_destructor_count++;
27     if (val_ >= 0 && val_ < kMaxTestCapacity) {
28       destructor_count[val_]++;
29     }
30   };
31   void setValue(int i) {
32     val_ = i;
33   }
34 
35  private:
36   int val_ = kMaxTestCapacity - 1;
37 };
38 }  // namespace
39 
40 TEST(ArrayQueueTest, IsEmptyInitially) {
41   ArrayQueue<int, 4> q;
42   EXPECT_TRUE(q.empty());
43   EXPECT_EQ(0, q.size());
44 }
45 
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 
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 
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 
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 
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 
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 
135 TEST(ArrayQueueTest, PopWhenEmpty) {
136   ArrayQueue<int, 4> q;
137   q.pop();
138   EXPECT_EQ(0, q.size());
139 }
140 
141 TEST(ArrayQueueTest, PopBackWhenEmpty) {
142   ArrayQueue<int, 4> q;
143   q.pop_back();
144   EXPECT_EQ(0, q.size());
145 }
146 
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 
154 TEST(ArrayQueueDeathTest, FrontWhenEmpty) {
155   ArrayQueue<int, 4> q;
156   EXPECT_DEATH(q.front(), "");
157 }
158 
159 TEST(ArrayQueueDeathTest, BackWhenEmpty) {
160   ArrayQueue<int, 4> q;
161   EXPECT_DEATH(q.back(), "");
162 }
163 
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 
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 
186 TEST(ArrayQueueDeathTest, InvalidSubscript) {
187   ArrayQueue<int, 2> q;
188   EXPECT_DEATH(q[0], "");
189 }
190 
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 
201 TEST(ArrayQueueTest, RemoveWithInvalidIndex) {
202   ArrayQueue<int, 3> q;
203   EXPECT_FALSE(q.remove(0));
204 }
205 
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 
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 
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<DummyElement, 4> q;
247     DummyElement 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 
269 TEST(ArrayQueueTest, EmplaceTest) {
270   constructor_count = 0;
271   ArrayQueue<DummyElement, 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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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