1 // Copyright 2020 The Pigweed Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
4 // use this file except in compliance with the License. You may obtain a copy of
5 // the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
12 // License for the specific language governing permissions and limitations under
13 // the License.
14
15 #include "pw_containers/inline_queue.h"
16
17 #include <algorithm>
18 #include <array>
19 #include <cstddef>
20
21 #include "pw_compilation_testing/negative_compilation.h"
22 #include "pw_containers/algorithm.h"
23 #include "pw_containers_private/test_helpers.h"
24 #include "pw_unit_test/framework.h"
25
26 namespace pw::containers {
27 namespace {
28
29 using namespace std::literals::string_view_literals;
30 using test::CopyOnly;
31 using test::Counter;
32 using test::MoveOnly;
33
TEST(InlineQueue,Construct_Sized)34 TEST(InlineQueue, Construct_Sized) {
35 InlineQueue<int, 3> queue;
36 EXPECT_TRUE(queue.empty());
37 EXPECT_EQ(queue.size(), 0u);
38 EXPECT_EQ(queue.max_size(), 3u);
39 }
40
TEST(InlineQueue,Construct_GenericSized)41 TEST(InlineQueue, Construct_GenericSized) {
42 InlineQueue<int, 3> sized_queue;
43 InlineQueue<int>& queue(sized_queue);
44 EXPECT_TRUE(queue.empty());
45 EXPECT_EQ(queue.size(), 0u);
46 EXPECT_EQ(queue.max_size(), 3u);
47 }
48
TEST(InlineQueue,Construct_CopySameCapacity)49 TEST(InlineQueue, Construct_CopySameCapacity) {
50 InlineQueue<CopyOnly, 4> queue(4, CopyOnly(123));
51 InlineQueue<CopyOnly, 4> copied(queue);
52
53 EXPECT_EQ(4u, queue.size());
54 EXPECT_EQ(123, queue[3].value);
55
56 EXPECT_EQ(4u, copied.size());
57 EXPECT_EQ(123, copied[3].value);
58 }
59
TEST(InlineQueue,Construct_CopyLargerCapacity)60 TEST(InlineQueue, Construct_CopyLargerCapacity) {
61 InlineQueue<CopyOnly, 4> queue(4, CopyOnly(123));
62 InlineQueue<CopyOnly, 5> copied(queue);
63
64 EXPECT_EQ(4u, queue.size());
65 EXPECT_EQ(123, queue[3].value);
66
67 EXPECT_EQ(4u, copied.size());
68 EXPECT_EQ(123, copied[3].value);
69 }
70
TEST(InlineQueue,Construct_CopySmallerCapacity)71 TEST(InlineQueue, Construct_CopySmallerCapacity) {
72 InlineQueue<CopyOnly, 4> queue(3, CopyOnly(123));
73 InlineQueue<CopyOnly, 3> copied(queue);
74
75 EXPECT_EQ(3u, queue.size());
76 EXPECT_EQ(123, queue[2].value);
77
78 EXPECT_EQ(3u, copied.size());
79 EXPECT_EQ(123, copied[2].value);
80 }
81
TEST(InlineQueue,Construct_MoveSameCapacity)82 TEST(InlineQueue, Construct_MoveSameCapacity) {
83 InlineQueue<MoveOnly, 4> queue;
84 queue.emplace(MoveOnly(1));
85 queue.emplace(MoveOnly(2));
86 queue.emplace(MoveOnly(3));
87 queue.emplace(MoveOnly(4));
88 InlineQueue<MoveOnly, 4> moved(std::move(queue));
89
90 // NOLINTNEXTLINE(bugprone-use-after-move)
91 EXPECT_EQ(0u, queue.size());
92
93 ASSERT_EQ(4u, moved.size());
94 EXPECT_EQ(4, moved[3].value);
95 }
96
TEST(InlineQueue,Construct_MoveLargerCapacity)97 TEST(InlineQueue, Construct_MoveLargerCapacity) {
98 InlineQueue<MoveOnly, 4> queue;
99 queue.emplace(MoveOnly(1));
100 queue.emplace(MoveOnly(2));
101 queue.emplace(MoveOnly(3));
102 queue.emplace(MoveOnly(4));
103 InlineQueue<MoveOnly, 5> moved(std::move(queue));
104
105 // NOLINTNEXTLINE(bugprone-use-after-move)
106 EXPECT_EQ(0u, queue.size());
107
108 ASSERT_EQ(4u, moved.size());
109 EXPECT_EQ(4, moved[3].value);
110 }
111
TEST(InlineQueue,Construct_MoveSmallerCapacity)112 TEST(InlineQueue, Construct_MoveSmallerCapacity) {
113 InlineQueue<MoveOnly, 4> queue;
114 queue.emplace(MoveOnly(1));
115 queue.emplace(MoveOnly(2));
116 queue.emplace(MoveOnly(3));
117 InlineQueue<MoveOnly, 3> moved(std::move(queue));
118
119 // NOLINTNEXTLINE(bugprone-use-after-move)
120 EXPECT_EQ(0u, queue.size());
121
122 ASSERT_EQ(3u, moved.size());
123 EXPECT_EQ(3, moved[2].value);
124 }
125
TEST(InlineQueue,Destruct_ZeroLength)126 TEST(InlineQueue, Destruct_ZeroLength) {
127 Counter::Reset();
128 {
129 InlineQueue<Counter, 0> queue;
130 EXPECT_EQ(queue.size(), 0u);
131 }
132 EXPECT_EQ(Counter::created, 0);
133 EXPECT_EQ(Counter::destroyed, 0);
134 }
135
TEST(InlineQueue,Destruct_Empty)136 TEST(InlineQueue, Destruct_Empty) {
137 Counter::Reset();
138
139 {
140 InlineQueue<Counter, 3> queue;
141 EXPECT_EQ(queue.size(), 0u);
142 }
143 EXPECT_EQ(Counter::created, 0);
144 EXPECT_EQ(Counter::destroyed, 0);
145 }
146
TEST(InlineQueue,Destruct_MultipleEntries)147 TEST(InlineQueue, Destruct_MultipleEntries) {
148 Counter value;
149 Counter::Reset();
150
151 {
152 InlineQueue<Counter, 128> queue(100, value);
153 }
154
155 EXPECT_EQ(Counter::created, 100);
156 EXPECT_EQ(Counter::destroyed, 100);
157 }
158
TEST(InlineQueue,Assign_InitializerList)159 TEST(InlineQueue, Assign_InitializerList) {
160 InlineQueue<int, 4> queue = {1, 3, 5, 7};
161
162 EXPECT_EQ(4u, queue.size());
163
164 EXPECT_EQ(1, queue[0]);
165 EXPECT_EQ(3, queue[1]);
166 EXPECT_EQ(5, queue[2]);
167 EXPECT_EQ(7, queue[3]);
168 }
169
TEST(InlineQueue,Assign_CopySameCapacity)170 TEST(InlineQueue, Assign_CopySameCapacity) {
171 InlineQueue<CopyOnly, 4> queue(4, CopyOnly(123));
172 InlineQueue<CopyOnly, 4> copied = queue;
173
174 EXPECT_EQ(4u, queue.size());
175 EXPECT_EQ(123, queue[3].value);
176
177 EXPECT_EQ(4u, copied.size());
178 EXPECT_EQ(123, copied[3].value);
179 }
180
TEST(InlineQueue,Assign_CopyLargerCapacity)181 TEST(InlineQueue, Assign_CopyLargerCapacity) {
182 InlineQueue<CopyOnly, 4> queue(4, CopyOnly(123));
183 InlineQueue<CopyOnly, 5> copied = queue;
184
185 EXPECT_EQ(4u, queue.size());
186 EXPECT_EQ(123, queue[3].value);
187
188 EXPECT_EQ(4u, copied.size());
189 EXPECT_EQ(123, copied[3].value);
190 }
191
TEST(InlineQueue,Assign_CopySmallerCapacity)192 TEST(InlineQueue, Assign_CopySmallerCapacity) {
193 InlineQueue<CopyOnly, 4> queue(3, CopyOnly(123));
194 InlineQueue<CopyOnly, 3> copied = queue;
195
196 EXPECT_EQ(3u, queue.size());
197 EXPECT_EQ(123, queue[2].value);
198
199 EXPECT_EQ(3u, copied.size());
200 EXPECT_EQ(123, copied[2].value);
201 }
202
TEST(InlineQueue,Access_Iterator)203 TEST(InlineQueue, Access_Iterator) {
204 InlineQueue<Counter, 2> queue(2);
205 for (Counter& item : queue) {
206 EXPECT_EQ(item.value, 0);
207 }
208 for (const Counter& item : queue) {
209 EXPECT_EQ(item.value, 0);
210 }
211 }
212
TEST(InlineQueue,Access_ConstIterator)213 TEST(InlineQueue, Access_ConstIterator) {
214 const InlineQueue<Counter, 2> queue(2);
215 for (const Counter& item : queue) {
216 EXPECT_EQ(item.value, 0);
217 }
218 }
219
TEST(InlineQueue,Access_ZeroLength)220 TEST(InlineQueue, Access_ZeroLength) {
221 InlineQueue<Counter, 0> queue;
222
223 EXPECT_EQ(0u, queue.size());
224 EXPECT_EQ(0u, queue.max_size());
225 EXPECT_TRUE(queue.empty());
226 EXPECT_TRUE(queue.full());
227
228 for (Counter& item : queue) {
229 (void)item;
230 FAIL();
231 }
232 }
233
TEST(InlineQueue,Access_ContiguousData)234 TEST(InlineQueue, Access_ContiguousData) {
235 // Content = {}, Storage = [x, x]
236 InlineQueue<int, 2> queue;
237
238 {
239 auto [first, second] = queue.contiguous_data();
240 EXPECT_EQ(first.size(), 0u);
241 EXPECT_EQ(second.size(), 0u);
242 }
243
244 // Content = {1}, Storage = [1, x]
245 queue.push(1);
246 {
247 auto [first, second] = queue.contiguous_data();
248 EXPECT_TRUE(Equal(first, std::array<int, 1>{1}));
249 EXPECT_TRUE(Equal(second, std::array<int, 0>{}));
250 }
251
252 // Content = {1, 2}, Storage = [1, 2]
253 queue.push(2);
254 EXPECT_TRUE(queue.full());
255 {
256 auto [first, second] = queue.contiguous_data();
257 EXPECT_TRUE(Equal(first, std::array<int, 2>{1, 2}));
258 EXPECT_TRUE(Equal(second, std::array<int, 0>{}));
259 }
260
261 // Content = {2}, Storage = [x, 2]
262 queue.pop();
263 {
264 auto [first, second] = queue.contiguous_data();
265 EXPECT_TRUE(Equal(first, std::array<int, 1>{2}));
266 EXPECT_TRUE(Equal(second, std::array<int, 0>{}));
267 }
268
269 // Content = {2, 1}, Storage = [1, 2]
270 queue.push(1);
271 {
272 auto [first, second] = queue.contiguous_data();
273 EXPECT_TRUE(Equal(first, std::array<int, 1>{2}));
274 EXPECT_TRUE(Equal(second, std::array<int, 1>{1}));
275 }
276
277 // Content = {1}, Storage = [1, x]
278 queue.pop();
279 {
280 auto [first, second] = queue.contiguous_data();
281 EXPECT_TRUE(Equal(first, std::array<int, 1>{1}));
282 EXPECT_TRUE(Equal(second, std::array<int, 0>{}));
283 }
284
285 // Content = {1, 2}, Storage = [1, 2]
286 queue.push(2);
287 {
288 auto [first, second] = queue.contiguous_data();
289 EXPECT_TRUE(Equal(first, std::array<int, 2>{1, 2}));
290 EXPECT_TRUE(Equal(second, std::array<int, 0>{}));
291 }
292 }
293
TEST(InlineQueue,Access_ConstContiguousData)294 TEST(InlineQueue, Access_ConstContiguousData) {
295 // Content = {1, 2}, Storage = [1, 2]
296 const InlineQueue<int, 2> queue = {1, 2};
297
298 {
299 auto [first, second] = queue.contiguous_data();
300 EXPECT_EQ(first.size(), 2u);
301 EXPECT_EQ(second.size(), 0u);
302 }
303 }
304
TEST(InlineQueue,Modify_Clear)305 TEST(InlineQueue, Modify_Clear) {
306 Counter::Reset();
307
308 InlineQueue<Counter, 100> queue;
309 queue.emplace();
310 queue.emplace();
311 queue.emplace();
312
313 queue.clear();
314
315 EXPECT_EQ(3, Counter::created);
316 EXPECT_EQ(3, Counter::destroyed);
317 }
318
TEST(InlineQueue,Modify_Push_Copy)319 TEST(InlineQueue, Modify_Push_Copy) {
320 Counter value(99);
321 Counter::Reset();
322
323 {
324 InlineQueue<Counter, 10> queue;
325 queue.push(value);
326
327 EXPECT_EQ(queue.size(), 1u);
328 EXPECT_EQ(queue.front().value, 99);
329 }
330
331 EXPECT_EQ(Counter::created, 1);
332 EXPECT_EQ(Counter::destroyed, 1);
333 }
334
TEST(InlineQueue,Modify_Push_Move)335 TEST(InlineQueue, Modify_Push_Move) {
336 Counter::Reset();
337
338 {
339 Counter value(99);
340 InlineQueue<Counter, 10> queue;
341 queue.push(std::move(value));
342
343 EXPECT_EQ(queue.size(), 1u);
344 EXPECT_EQ(queue.front().value, 99);
345 // NOLINTNEXTLINE(bugprone-use-after-move)
346 EXPECT_EQ(value.value, 0);
347 }
348
349 EXPECT_EQ(Counter::created, 1);
350 EXPECT_EQ(Counter::destroyed, 2);
351 EXPECT_EQ(Counter::moved, 1);
352 }
353
TEST(InlineQueue,Modify_Emplace)354 TEST(InlineQueue, Modify_Emplace) {
355 Counter::Reset();
356
357 {
358 InlineQueue<Counter, 10> queue;
359 queue.emplace(314);
360
361 EXPECT_EQ(queue.size(), 1u);
362 EXPECT_EQ(queue.front().value, 314);
363 }
364
365 EXPECT_EQ(Counter::created, 1);
366 EXPECT_EQ(Counter::destroyed, 1);
367 }
368
TEST(InlineQueue,Modify_Overwrite)369 TEST(InlineQueue, Modify_Overwrite) {
370 Counter::Reset();
371 {
372 InlineQueue<Counter, 2> queue(2);
373 queue.push_overwrite(1);
374 queue.emplace_overwrite(2);
375
376 EXPECT_EQ(queue.size(), 2u);
377 EXPECT_EQ(queue.front().value, 1);
378 EXPECT_EQ(queue.back().value, 2);
379 }
380 }
381
TEST(InlineQueue,Modify_Wrap)382 TEST(InlineQueue, Modify_Wrap) {
383 Counter::Reset();
384
385 {
386 InlineQueue<Counter, 3> queue;
387 queue.emplace(1);
388 queue.emplace(2);
389 queue.emplace(3);
390
391 ASSERT_EQ(queue.size(), 3u);
392 EXPECT_EQ(queue[0].value, 1);
393 EXPECT_EQ(queue[1].value, 2);
394 EXPECT_EQ(queue[2].value, 3);
395
396 queue.pop();
397 queue.emplace(4);
398
399 ASSERT_EQ(queue.size(), 3u);
400 EXPECT_EQ(queue[0].value, 2);
401 EXPECT_EQ(queue[1].value, 3);
402 EXPECT_EQ(queue[2].value, 4);
403 }
404
405 EXPECT_EQ(Counter::created, 4);
406 EXPECT_EQ(Counter::destroyed, 4);
407 }
408
TEST(InlineQueue,Modify_Pop)409 TEST(InlineQueue, Modify_Pop) {
410 Counter::Reset();
411
412 InlineQueue<Counter, 3> queue;
413 queue.emplace(0);
414 queue.pop();
415 queue.emplace(0);
416 queue.pop();
417 queue.emplace(1); // This wraps to the other end.
418 queue.emplace(2); // This is the first entry in storage.
419 queue.emplace(3);
420 // Content = {1, 2, 3}, Storage = [2, 3, 1]
421
422 ASSERT_EQ(queue.size(), 3u);
423 EXPECT_EQ(queue[0].value, 1);
424 EXPECT_EQ(queue[1].value, 2);
425 EXPECT_EQ(queue[2].value, 3);
426
427 // This wraps around
428 queue.pop();
429 // Content = {2, 3}, Storage = [2, 3, x]
430
431 EXPECT_EQ(queue.size(), 2u);
432 EXPECT_EQ(queue[0].value, 2);
433 EXPECT_EQ(queue[1].value, 3);
434
435 queue.pop();
436 // Content = {3}, Storage = [x, 3, x]
437 ASSERT_EQ(queue.size(), 1u);
438 EXPECT_EQ(queue[0].value, 3);
439
440 EXPECT_EQ(Counter::created, 5);
441 EXPECT_EQ(Counter::destroyed, 4);
442 }
443
TEST(InlineQueue,Generic)444 TEST(InlineQueue, Generic) {
445 InlineQueue<int, 10> queue({1, 2, 3, 4, 5});
446 InlineQueue<int>& generic_queue(queue);
447
448 EXPECT_EQ(generic_queue.size(), queue.size());
449 EXPECT_EQ(generic_queue.max_size(), queue.max_size());
450
451 uint16_t i = 0;
452 for (int value : queue) {
453 EXPECT_EQ(value, generic_queue[i]);
454 i += 1;
455 }
456
457 i = 0;
458 for (int value : generic_queue) {
459 EXPECT_EQ(queue[i], value);
460 i += 1;
461 }
462 }
463
TEST(InlineQueue,ConstexprMaxSize)464 TEST(InlineQueue, ConstexprMaxSize) {
465 InlineQueue<int, 10> queue;
466 constexpr size_t kMaxSize = queue.max_size();
467 EXPECT_EQ(queue.max_size(), kMaxSize);
468
469 // Ensure the generic sized container does not have a constexpr max_size().
470 [[maybe_unused]] InlineQueue<int>& generic_queue(queue);
471 #if PW_NC_TEST(InlineQueue_GenericMaxSize_NotConstexpr)
472 PW_NC_EXPECT_CLANG(
473 "kGenericMaxSize.* must be initialized by a constant expression");
474 PW_NC_EXPECT_GCC("call to non-'constexpr' function .*InlineQueue.*max_size");
475 [[maybe_unused]] constexpr size_t kGenericMaxSize = generic_queue.max_size();
476 #endif // PW_NC_TEST
477 }
478
TEST(InlineQueue,StdMaxElement)479 TEST(InlineQueue, StdMaxElement) {
480 // Content = {1, 2, 3, 4}, Storage = [1, 2, 3, 4]
481 InlineQueue<int, 4> queue = {1, 2, 3, 4};
482
483 auto max_element_it = std::max_element(queue.begin(), queue.end());
484 ASSERT_NE(max_element_it, queue.end());
485 EXPECT_EQ(*max_element_it, 4);
486
487 // Content = {2, 3, 4, 5}, Storage = [5, 2, 3, 4]
488 queue.push_overwrite(5);
489
490 max_element_it = std::max_element(queue.begin(), queue.end());
491 ASSERT_NE(max_element_it, queue.end());
492 EXPECT_EQ(*max_element_it, 5);
493
494 // Content = {3, 4, 5}, Storage = [5, x, 3, 4]
495 queue.pop();
496
497 max_element_it = std::max_element(queue.begin(), queue.end());
498 ASSERT_NE(max_element_it, queue.end());
499 EXPECT_EQ(*max_element_it, 5);
500
501 // Content = {}, Storage = [x, x, x, x]
502 queue.clear();
503
504 max_element_it = std::max_element(queue.begin(), queue.end());
505 ASSERT_EQ(max_element_it, queue.end());
506 }
507
TEST(InlineQueue,StdMaxElementConst)508 TEST(InlineQueue, StdMaxElementConst) {
509 // Content = {1, 2, 3, 4}, Storage = [1, 2, 3, 4]
510 InlineQueue<int, 4> queue = {1, 2, 3, 4};
511
512 auto max_element_it = std::max_element(queue.cbegin(), queue.cend());
513 ASSERT_NE(max_element_it, queue.cend());
514 EXPECT_EQ(*max_element_it, 4);
515
516 // Content = {2, 3, 4, 5}, Storage = [5, 2, 3, 4]
517 queue.push_overwrite(5);
518
519 max_element_it = std::max_element(queue.cbegin(), queue.cend());
520 ASSERT_NE(max_element_it, queue.cend());
521 EXPECT_EQ(*max_element_it, 5);
522
523 // Content = {3, 4, 5}, Storage = [5, x, 3, 4]
524 queue.pop();
525
526 max_element_it = std::max_element(queue.cbegin(), queue.cend());
527 ASSERT_NE(max_element_it, queue.cend());
528 EXPECT_EQ(*max_element_it, 5);
529
530 // Content = {}, Storage = [x, x, x, x]
531 queue.clear();
532
533 max_element_it = std::max_element(queue.cbegin(), queue.cend());
534 ASSERT_EQ(max_element_it, queue.cend());
535 }
536
TEST(InlineQueue,OperatorPlus)537 TEST(InlineQueue, OperatorPlus) {
538 // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
539 InlineQueue<int, 4> queue = {0, 0, 1, 2};
540 // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
541 queue.push_overwrite(3);
542 // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
543 queue.push_overwrite(4);
544
545 for (int i = 0; i < 4; i++) {
546 ASSERT_EQ(*(queue.begin() + i), static_cast<int>(i + 1));
547 ASSERT_EQ(*(i + queue.begin()), static_cast<int>(i + 1));
548 }
549
550 ASSERT_EQ(queue.begin() + queue.size(), queue.end());
551 }
552
TEST(InlineQueue,OperatorPlusPlus)553 TEST(InlineQueue, OperatorPlusPlus) {
554 // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
555 InlineQueue<int, 4> queue = {0, 0, 1, 2};
556 // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
557 queue.push_overwrite(3);
558 // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
559 queue.push_overwrite(4);
560
561 auto it = queue.begin();
562
563 ASSERT_EQ(*it, 1);
564 it++;
565 ASSERT_EQ(*it, 2);
566 it++;
567 ASSERT_EQ(*it, 3);
568 it++;
569 ASSERT_EQ(*it, 4);
570 it++;
571
572 ASSERT_EQ(it, queue.end());
573 }
574
TEST(InlineQueue,OperatorPlusEquals)575 TEST(InlineQueue, OperatorPlusEquals) {
576 // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
577 InlineQueue<int, 4> queue = {0, 0, 1, 2};
578 // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
579 queue.push_overwrite(3);
580 // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
581 queue.push_overwrite(4);
582
583 auto it = queue.begin();
584
585 ASSERT_EQ(*it, 1);
586 it += 1;
587 ASSERT_EQ(*it, 2);
588 it += 1;
589 ASSERT_EQ(*it, 3);
590 it += 1;
591 ASSERT_EQ(*it, 4);
592 it += 1;
593 ASSERT_EQ(it, queue.end());
594
595 it = queue.begin();
596 ASSERT_EQ(*it, 1);
597 it += 2;
598 ASSERT_EQ(*it, 3);
599 it += 2;
600 ASSERT_EQ(it, queue.end());
601
602 it = queue.begin();
603 it += queue.size();
604
605 ASSERT_EQ(it, queue.end());
606 }
607
TEST(InlineQueue,OpeartorMinus)608 TEST(InlineQueue, OpeartorMinus) {
609 // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
610 InlineQueue<int, 4> queue = {0, 0, 1, 2};
611 // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
612 queue.push_overwrite(3);
613 // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
614 queue.push_overwrite(4);
615
616 for (int i = 1; i <= 4; i++) {
617 ASSERT_EQ(*(queue.end() - i), static_cast<int>(5 - i));
618 }
619
620 ASSERT_EQ(queue.end() - queue.size(), queue.begin());
621 }
TEST(InlineQueue,OperatorMinusMinus)622 TEST(InlineQueue, OperatorMinusMinus) {
623 // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
624 InlineQueue<int, 4> queue = {0, 0, 1, 2};
625 // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
626 queue.push_overwrite(3);
627 // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
628 queue.push_overwrite(4);
629
630 auto it = queue.end();
631
632 it--;
633 ASSERT_EQ(*it, 4);
634 it--;
635 ASSERT_EQ(*it, 3);
636 it--;
637 ASSERT_EQ(*it, 2);
638 it--;
639 ASSERT_EQ(*it, 1);
640
641 ASSERT_EQ(it, queue.begin());
642 }
643
TEST(InlineQueue,OperatorMinusEquals)644 TEST(InlineQueue, OperatorMinusEquals) {
645 // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
646 InlineQueue<int, 4> queue = {0, 0, 1, 2};
647 // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
648 queue.push_overwrite(3);
649 // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
650 queue.push_overwrite(4);
651
652 auto it = queue.end();
653
654 it -= 1;
655 ASSERT_EQ(*it, 4);
656 it -= 1;
657 ASSERT_EQ(*it, 3);
658 it -= 1;
659 ASSERT_EQ(*it, 2);
660 it -= 1;
661 ASSERT_EQ(*it, 1);
662
663 ASSERT_EQ(it, queue.begin());
664
665 it = queue.end();
666
667 it -= 2;
668 ASSERT_EQ(*it, 3);
669 it -= 2;
670 ASSERT_EQ(*it, 1);
671
672 ASSERT_EQ(it, queue.begin());
673
674 it = queue.end();
675 it -= queue.size();
676
677 ASSERT_EQ(it, queue.begin());
678 }
679
TEST(InlineQueue,OperatorSquareBracket)680 TEST(InlineQueue, OperatorSquareBracket) {
681 // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
682 InlineQueue<int, 4> queue = {0, 0, 1, 2};
683 // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
684 queue.push_overwrite(3);
685 // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
686 queue.push_overwrite(4);
687
688 for (unsigned short i = 0; i < queue.size(); i++) {
689 ASSERT_EQ(queue.begin()[i], static_cast<int>(i + 1));
690 }
691 }
692
TEST(InlineQueue,OperatorLessThan)693 TEST(InlineQueue, OperatorLessThan) {
694 // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
695 InlineQueue<int, 4> queue = {0, 0, 1, 2};
696 // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
697 queue.push_overwrite(3);
698 // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
699 queue.push_overwrite(4);
700
701 for (int i = 0; i < queue.size(); i++) {
702 for (int j = 0; j < i; j++) {
703 ASSERT_TRUE((queue.begin() + j) < (queue.begin() + i));
704 }
705
706 ASSERT_TRUE((queue.begin() + i) < queue.end());
707 }
708 }
709
TEST(InlineQueue,OperatorLessThanEqual)710 TEST(InlineQueue, OperatorLessThanEqual) {
711 // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
712 InlineQueue<int, 4> queue = {0, 0, 1, 2};
713 // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
714 queue.push_overwrite(3);
715 // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
716 queue.push_overwrite(4);
717
718 for (int i = 0; i < queue.size(); i++) {
719 for (int j = 0; j <= i; j++) {
720 ASSERT_TRUE((queue.begin() + j) <= (queue.begin() + i));
721 }
722
723 ASSERT_TRUE((queue.begin() + i) <= queue.end());
724 }
725 }
726
TEST(InlineQueue,OperatorGreater)727 TEST(InlineQueue, OperatorGreater) {
728 // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
729 InlineQueue<int, 4> queue = {0, 0, 1, 2};
730 // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
731 queue.push_overwrite(3);
732 // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
733 queue.push_overwrite(4);
734
735 for (int i = 0; i < queue.size(); i++) {
736 for (int j = i + 1; j < queue.size(); j++) {
737 ASSERT_TRUE((queue.begin() + j) > (queue.begin() + i));
738 }
739
740 ASSERT_TRUE(queue.end() > (queue.begin() + i));
741 }
742 }
743
TEST(InlineQueue,OperatorGreaterThanEqual)744 TEST(InlineQueue, OperatorGreaterThanEqual) {
745 // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
746 InlineQueue<int, 4> queue = {0, 0, 1, 2};
747 // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
748 queue.push_overwrite(3);
749 // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
750 queue.push_overwrite(4);
751
752 for (int i = 0; i < queue.size(); i++) {
753 for (int j = i; j < queue.size(); j++) {
754 ASSERT_TRUE((queue.begin() + j) >= (queue.begin() + i));
755 }
756
757 ASSERT_TRUE(queue.end() >= (queue.begin() + i));
758 }
759 }
760
TEST(InlineQueue,DereferenceOperator)761 TEST(InlineQueue, DereferenceOperator) {
762 // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
763 InlineQueue<int, 4> queue = {0, 0, 1, 2};
764 // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
765 queue.push_overwrite(3);
766 // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
767 queue.push_overwrite(4);
768
769 for (int i = 0; i < queue.size(); i++) {
770 const auto it = queue.begin() + i;
771 ASSERT_EQ(*(it.operator->()), static_cast<int>(i + 1));
772 }
773 }
774
775 // Test that InlineQueue<T> is trivially destructible when its type is.
776 static_assert(std::is_trivially_destructible_v<InlineQueue<int, 4>>);
777
778 static_assert(std::is_trivially_destructible_v<MoveOnly>);
779 static_assert(std::is_trivially_destructible_v<InlineQueue<MoveOnly, 1>>);
780
781 static_assert(std::is_trivially_destructible_v<CopyOnly>);
782 static_assert(std::is_trivially_destructible_v<InlineQueue<CopyOnly, 99>>);
783
784 static_assert(!std::is_trivially_destructible_v<Counter>);
785 static_assert(!std::is_trivially_destructible_v<InlineQueue<Counter, 99>>);
786
787 // Generic-capacity queues cannot be constructed or destructed.
788 static_assert(!std::is_constructible_v<InlineQueue<int>>);
789 static_assert(!std::is_destructible_v<InlineQueue<int>>);
790
791 // Tests that InlineQueue<T> does not have any extra padding.
792 static_assert(sizeof(InlineQueue<uint8_t, 1>) ==
793 sizeof(InlineQueue<uint8_t>::size_type) * 4 +
794 std::max(sizeof(InlineQueue<uint8_t>::size_type),
795 sizeof(uint8_t)));
796 static_assert(sizeof(InlineQueue<uint8_t, 2>) ==
797 sizeof(InlineQueue<uint8_t>::size_type) * 4 +
798 2 * sizeof(uint8_t));
799 static_assert(sizeof(InlineQueue<uint16_t, 1>) ==
800 sizeof(InlineQueue<uint16_t>::size_type) * 4 + sizeof(uint16_t));
801 static_assert(sizeof(InlineQueue<uint32_t, 1>) ==
802 sizeof(InlineQueue<uint32_t>::size_type) * 4 + sizeof(uint32_t));
803 static_assert(sizeof(InlineQueue<uint64_t, 1>) ==
804 sizeof(InlineQueue<uint64_t>::size_type) * 4 + sizeof(uint64_t));
805
806 // Test that InlineQueue<T> is copy assignable
807 static_assert(std::is_copy_assignable_v<InlineQueue<int>::iterator>);
808 static_assert(std::is_copy_assignable_v<InlineQueue<int, 4>::iterator>);
809
810 // Test that InlineQueue<T>::iterator can be converted to a const_iterator
811 static_assert(std::is_convertible<InlineQueue<int>::iterator,
812 InlineQueue<int>::const_iterator>::value);
813 static_assert(std::is_convertible<InlineQueue<int, 4>::iterator,
814 InlineQueue<int, 4>::const_iterator>::value);
815
816 // Test that InlineQueue<T>::const_iterator can NOT be converted to a iterator
817 static_assert(!std::is_convertible<InlineQueue<int>::const_iterator,
818 InlineQueue<int>::iterator>::value);
819 static_assert(!std::is_convertible<InlineQueue<int, 4>::const_iterator,
820 InlineQueue<int, 4>::iterator>::value);
821
822 } // namespace
823 } // namespace pw::containers
824