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