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_deque.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(InlineDeque,Construct_Sized)34 TEST(InlineDeque, Construct_Sized) {
35 InlineDeque<int, 3> deque;
36 EXPECT_TRUE(deque.empty());
37 EXPECT_EQ(deque.size(), 0u);
38 EXPECT_EQ(deque.max_size(), 3u);
39 }
40
TEST(InlineDeque,Construct_GenericSized)41 TEST(InlineDeque, Construct_GenericSized) {
42 InlineDeque<int, 3> sized_deque;
43 InlineDeque<int>& deque(sized_deque);
44 EXPECT_TRUE(deque.empty());
45 EXPECT_EQ(deque.size(), 0u);
46 EXPECT_EQ(deque.max_size(), 3u);
47 }
48
TEST(InlineDeque,Construct_CopySameCapacity)49 TEST(InlineDeque, Construct_CopySameCapacity) {
50 InlineDeque<CopyOnly, 4> deque(4, CopyOnly(123));
51 const auto& deque_ref = deque;
52 InlineDeque<CopyOnly, 4> copied(deque_ref);
53
54 ASSERT_EQ(4u, deque.size());
55 EXPECT_EQ(123, deque[3].value);
56
57 ASSERT_EQ(4u, copied.size());
58 EXPECT_EQ(123, copied[3].value);
59 }
60
TEST(InlineDeque,Construct_MoveSameCapacity)61 TEST(InlineDeque, Construct_MoveSameCapacity) {
62 InlineDeque<MoveOnly, 4> deque;
63 deque.emplace_back(MoveOnly(1));
64 deque.emplace_back(MoveOnly(2));
65 deque.emplace_back(MoveOnly(3));
66 deque.emplace_back(MoveOnly(4));
67 InlineDeque<MoveOnly, 4> moved(std::move(deque));
68
69 // NOLINTNEXTLINE(bugprone-use-after-move)
70 EXPECT_EQ(0u, deque.size());
71
72 ASSERT_EQ(4u, moved.size());
73 EXPECT_EQ(4, moved[3].value);
74 }
75
TEST(InlineDeque,Construct_CopyLargerCapacity)76 TEST(InlineDeque, Construct_CopyLargerCapacity) {
77 InlineDeque<CopyOnly, 4> deque(4, CopyOnly(123));
78 InlineDeque<CopyOnly, 5> copied(deque);
79
80 ASSERT_EQ(4u, deque.size());
81 EXPECT_EQ(123, deque[3].value);
82
83 ASSERT_EQ(4u, copied.size());
84 EXPECT_EQ(123, copied[3].value);
85 }
86
TEST(InlineDeque,Construct_MoveLargerCapacity)87 TEST(InlineDeque, Construct_MoveLargerCapacity) {
88 InlineDeque<MoveOnly, 4> deque;
89 deque.emplace_back(MoveOnly(1));
90 deque.emplace_back(MoveOnly(2));
91 deque.emplace_back(MoveOnly(3));
92 deque.emplace_back(MoveOnly(4));
93 InlineDeque<MoveOnly, 5> moved(std::move(deque));
94
95 // NOLINTNEXTLINE(bugprone-use-after-move)
96 EXPECT_EQ(0u, deque.size());
97
98 ASSERT_EQ(4u, moved.size());
99 EXPECT_EQ(4, moved[3].value);
100 }
101
TEST(InlineDeque,Construct_CopySmallerCapacity)102 TEST(InlineDeque, Construct_CopySmallerCapacity) {
103 InlineDeque<CopyOnly, 4> deque(3, CopyOnly(123));
104 InlineDeque<CopyOnly, 3> copied(deque);
105
106 ASSERT_EQ(3u, deque.size());
107 EXPECT_EQ(123, deque[2].value);
108
109 ASSERT_EQ(3u, copied.size());
110 EXPECT_EQ(123, copied[2].value);
111 }
112
TEST(InlineDeque,Destruct_ZeroLength)113 TEST(InlineDeque, Destruct_ZeroLength) {
114 Counter::Reset();
115 {
116 InlineDeque<Counter, 0> deque;
117 EXPECT_EQ(deque.size(), 0u);
118 }
119 EXPECT_EQ(Counter::created, 0);
120 EXPECT_EQ(Counter::destroyed, 0);
121 }
122
TEST(InlineDeque,Destruct_Empty)123 TEST(InlineDeque, Destruct_Empty) {
124 Counter::Reset();
125
126 {
127 InlineDeque<Counter, 3> deque;
128 EXPECT_EQ(deque.size(), 0u);
129 }
130 EXPECT_EQ(Counter::created, 0);
131 EXPECT_EQ(Counter::destroyed, 0);
132 }
133
TEST(InlineDeque,Destruct_MultipleEntries)134 TEST(InlineDeque, Destruct_MultipleEntries) {
135 Counter value;
136 Counter::Reset();
137
138 {
139 InlineDeque<Counter, 128> deque(100, value);
140 }
141
142 EXPECT_EQ(Counter::created, 100);
143 EXPECT_EQ(Counter::destroyed, 100);
144 }
145
TEST(InlineDeque,Assign_InitializerList)146 TEST(InlineDeque, Assign_InitializerList) {
147 InlineDeque<int, 4> deque = {1, 3, 5, 7};
148
149 ASSERT_EQ(4u, deque.size());
150
151 EXPECT_EQ(1, deque[0]);
152 EXPECT_EQ(3, deque[1]);
153 EXPECT_EQ(5, deque[2]);
154 EXPECT_EQ(7, deque[3]);
155 }
156
TEST(InlineDeque,Assign_CopySameCapacity)157 TEST(InlineDeque, Assign_CopySameCapacity) {
158 InlineDeque<CopyOnly, 4> deque(4, CopyOnly(123));
159 InlineDeque<CopyOnly, 4> copied = deque;
160
161 ASSERT_EQ(4u, deque.size());
162 EXPECT_EQ(123, deque[3].value);
163
164 ASSERT_EQ(4u, copied.size());
165 EXPECT_EQ(123, copied[3].value);
166 }
167
TEST(InlineDeque,Assign_CopyLargerCapacity)168 TEST(InlineDeque, Assign_CopyLargerCapacity) {
169 InlineDeque<CopyOnly, 4> deque(4, CopyOnly(123));
170 InlineDeque<CopyOnly, 5> copied = deque;
171
172 ASSERT_EQ(4u, deque.size());
173 EXPECT_EQ(123, deque[3].value);
174
175 ASSERT_EQ(4u, copied.size());
176 EXPECT_EQ(123, copied[3].value);
177 }
178
TEST(InlineDeque,Assign_CopySmallerCapacity)179 TEST(InlineDeque, Assign_CopySmallerCapacity) {
180 InlineDeque<CopyOnly, 4> deque(3, CopyOnly(123));
181 InlineDeque<CopyOnly, 3> copied = deque;
182
183 ASSERT_EQ(3u, deque.size());
184 EXPECT_EQ(123, deque[2].value);
185
186 ASSERT_EQ(3u, copied.size());
187 EXPECT_EQ(123, copied[2].value);
188 }
189
TEST(InlineDeque,Assign_MoveSameCapacity)190 TEST(InlineDeque, Assign_MoveSameCapacity) {
191 InlineDeque<MoveOnly, 4> deque;
192 deque.emplace_back(MoveOnly(1));
193 deque.emplace_back(MoveOnly(2));
194 deque.emplace_back(MoveOnly(3));
195 deque.emplace_back(MoveOnly(4));
196 InlineDeque<MoveOnly, 4> moved = std::move(deque);
197
198 // NOLINTNEXTLINE(bugprone-use-after-move)
199 EXPECT_EQ(0u, deque.size());
200
201 ASSERT_EQ(4u, moved.size());
202 EXPECT_EQ(4, moved[3].value);
203 }
204
TEST(InlineDeque,Assign_MoveLargerCapacity)205 TEST(InlineDeque, Assign_MoveLargerCapacity) {
206 InlineDeque<MoveOnly, 4> deque;
207 deque.emplace_back(MoveOnly(1));
208 deque.emplace_back(MoveOnly(2));
209 deque.emplace_back(MoveOnly(3));
210 deque.emplace_back(MoveOnly(4));
211 InlineDeque<MoveOnly, 5> moved = std::move(deque);
212
213 // NOLINTNEXTLINE(bugprone-use-after-move)
214 EXPECT_EQ(0u, deque.size());
215
216 ASSERT_EQ(4u, moved.size());
217 EXPECT_EQ(4, moved[3].value);
218 }
219
TEST(InlineDeque,Assign_MoveSmallerCapacity)220 TEST(InlineDeque, Assign_MoveSmallerCapacity) {
221 InlineDeque<MoveOnly, 4> deque;
222 deque.emplace_back(MoveOnly(1));
223 deque.emplace_back(MoveOnly(2));
224 deque.emplace_back(MoveOnly(3));
225 InlineDeque<MoveOnly, 3> moved = std::move(deque);
226
227 // NOLINTNEXTLINE(bugprone-use-after-move)
228 EXPECT_EQ(0u, deque.size());
229
230 ASSERT_EQ(3u, moved.size());
231 EXPECT_EQ(3, moved[2].value);
232 }
233
TEST(InlineDeque,Access_Iterator)234 TEST(InlineDeque, Access_Iterator) {
235 InlineDeque<Counter, 2> deque(2);
236 for (Counter& item : deque) {
237 EXPECT_EQ(item.value, 0);
238 }
239 for (const Counter& item : deque) {
240 EXPECT_EQ(item.value, 0);
241 }
242 }
243
TEST(InlineDeque,Access_ConstIterator)244 TEST(InlineDeque, Access_ConstIterator) {
245 const InlineDeque<Counter, 2> deque(2);
246 for (const Counter& item : deque) {
247 EXPECT_EQ(item.value, 0);
248 }
249 }
250
TEST(InlineDeque,Access_ZeroLength)251 TEST(InlineDeque, Access_ZeroLength) {
252 InlineDeque<Counter, 0> deque;
253
254 EXPECT_EQ(0u, deque.size());
255 EXPECT_EQ(0u, deque.max_size());
256 EXPECT_TRUE(deque.empty());
257 EXPECT_TRUE(deque.full());
258
259 for (Counter& item : deque) {
260 (void)item;
261 FAIL();
262 }
263 }
264
TEST(InlineDeque,Access_ContiguousData)265 TEST(InlineDeque, Access_ContiguousData) {
266 // Content = {}, Storage = [x, x]
267 InlineDeque<int, 2> deque;
268
269 {
270 auto [first, second] = deque.contiguous_data();
271 EXPECT_EQ(first.size(), 0u);
272 EXPECT_EQ(second.size(), 0u);
273 }
274
275 // Content = {1}, Storage = [1, x]
276 deque.push_back(1);
277 {
278 auto [first, second] = deque.contiguous_data();
279 EXPECT_TRUE(Equal(first, std::array<int, 1>{1}));
280 EXPECT_TRUE(Equal(second, std::array<int, 0>{}));
281 }
282
283 // Content = {1, 2}, Storage = [1, 2]
284 deque.push_back(2);
285 EXPECT_TRUE(deque.full());
286 {
287 auto [first, second] = deque.contiguous_data();
288 EXPECT_TRUE(Equal(first, std::array<int, 2>{1, 2}));
289 EXPECT_TRUE(Equal(second, std::array<int, 0>{}));
290 }
291
292 // Content = {2}, Storage = [x, 2]
293 deque.pop_front();
294 {
295 auto [first, second] = deque.contiguous_data();
296 EXPECT_TRUE(Equal(first, std::array<int, 1>{2}));
297 EXPECT_TRUE(Equal(second, std::array<int, 0>{}));
298 }
299
300 // Content = {2, 1}, Storage = [1, 2]
301 deque.push_back(1);
302 {
303 auto [first, second] = deque.contiguous_data();
304 EXPECT_TRUE(Equal(first, std::array<int, 1>{2}));
305 EXPECT_TRUE(Equal(second, std::array<int, 1>{1}));
306 }
307
308 // Content = {1}, Storage = [1, x]
309 deque.pop_front();
310 {
311 auto [first, second] = deque.contiguous_data();
312 EXPECT_TRUE(Equal(first, std::array<int, 1>{1}));
313 EXPECT_TRUE(Equal(second, std::array<int, 0>{}));
314 }
315
316 // Content = {1, 2}, Storage = [1, 2]
317 deque.push_back(2);
318 {
319 auto [first, second] = deque.contiguous_data();
320 EXPECT_TRUE(Equal(first, std::array<int, 2>{1, 2}));
321 EXPECT_TRUE(Equal(second, std::array<int, 0>{}));
322 }
323 }
324
TEST(InlineDeque,Access_ConstContiguousData)325 TEST(InlineDeque, Access_ConstContiguousData) {
326 // Content = {1, 2}, Storage = [1, 2]
327 const InlineDeque<int, 2> deque = {1, 2};
328
329 {
330 auto [first, second] = deque.contiguous_data();
331 EXPECT_EQ(first.size(), 2u);
332 EXPECT_EQ(second.size(), 0u);
333 }
334 }
335
TEST(InlineDeque,Modify_Clear)336 TEST(InlineDeque, Modify_Clear) {
337 Counter::Reset();
338
339 InlineDeque<Counter, 100> deque;
340 deque.emplace_back();
341 deque.emplace_back();
342 deque.emplace_back();
343
344 deque.clear();
345
346 EXPECT_EQ(3, Counter::created);
347 EXPECT_EQ(3, Counter::destroyed);
348 }
349
TEST(InlineDeque,Modify_PushBack_Copy)350 TEST(InlineDeque, Modify_PushBack_Copy) {
351 Counter value(99);
352 Counter::Reset();
353
354 {
355 InlineDeque<Counter, 10> deque;
356 deque.push_back(value);
357
358 ASSERT_EQ(deque.size(), 1u);
359 EXPECT_EQ(deque.front().value, 99);
360 }
361
362 EXPECT_EQ(Counter::created, 1);
363 EXPECT_EQ(Counter::destroyed, 1);
364 }
365
TEST(InlineDeque,Modify_PushBack_Move)366 TEST(InlineDeque, Modify_PushBack_Move) {
367 Counter::Reset();
368
369 {
370 Counter value(99);
371 InlineDeque<Counter, 10> deque;
372 deque.push_back(std::move(value));
373
374 EXPECT_EQ(deque.size(), 1u);
375 EXPECT_EQ(deque.front().value, 99);
376 // NOLINTNEXTLINE(bugprone-use-after-move)
377 EXPECT_EQ(value.value, 0);
378 }
379
380 EXPECT_EQ(Counter::created, 1);
381 EXPECT_EQ(Counter::destroyed, 2);
382 EXPECT_EQ(Counter::moved, 1);
383 }
384
TEST(InlineDeque,Modify_EmplaceBack)385 TEST(InlineDeque, Modify_EmplaceBack) {
386 Counter::Reset();
387
388 {
389 InlineDeque<Counter, 10> deque;
390 deque.emplace_back(314);
391
392 ASSERT_EQ(deque.size(), 1u);
393 EXPECT_EQ(deque.front().value, 314);
394 }
395
396 EXPECT_EQ(Counter::created, 1);
397 EXPECT_EQ(Counter::destroyed, 1);
398 }
399
TEST(InlineDeque,Modify_WrapForwards)400 TEST(InlineDeque, Modify_WrapForwards) {
401 Counter::Reset();
402
403 {
404 InlineDeque<Counter, 3> deque;
405 deque.emplace_back(1);
406 deque.emplace_back(2);
407 deque.emplace_back(3);
408
409 ASSERT_EQ(deque.size(), 3u);
410 EXPECT_EQ(deque[0].value, 1);
411 EXPECT_EQ(deque.front().value, 1);
412 EXPECT_EQ(deque[1].value, 2);
413 EXPECT_EQ(deque[2].value, 3);
414 EXPECT_EQ(deque.back().value, 3);
415
416 deque.pop_front();
417 deque.emplace_back(4);
418
419 ASSERT_EQ(deque.size(), 3u);
420 EXPECT_EQ(deque[0].value, 2);
421 EXPECT_EQ(deque.front().value, 2);
422 EXPECT_EQ(deque[1].value, 3);
423 EXPECT_EQ(deque[2].value, 4);
424 EXPECT_EQ(deque.back().value, 4);
425 }
426
427 EXPECT_EQ(Counter::created, 4);
428 EXPECT_EQ(Counter::destroyed, 4);
429 }
430
TEST(InlineDeque,Modify_WrapBackwards)431 TEST(InlineDeque, Modify_WrapBackwards) {
432 Counter::Reset();
433
434 {
435 InlineDeque<Counter, 3> deque;
436 deque.emplace_front(1);
437 deque.emplace_front(2);
438 deque.emplace_front(3);
439
440 ASSERT_EQ(deque.size(), 3u);
441 EXPECT_EQ(deque[0].value, 3);
442 EXPECT_EQ(deque.front().value, 3);
443 EXPECT_EQ(deque[1].value, 2);
444 EXPECT_EQ(deque[2].value, 1);
445 EXPECT_EQ(deque.back().value, 1);
446
447 deque.pop_back();
448 deque.emplace_front(4);
449
450 ASSERT_EQ(deque.size(), 3u);
451 EXPECT_EQ(deque[0].value, 4);
452 EXPECT_EQ(deque.front().value, 4);
453 EXPECT_EQ(deque[1].value, 3);
454 EXPECT_EQ(deque[2].value, 2);
455 EXPECT_EQ(deque.back().value, 2);
456 }
457
458 EXPECT_EQ(Counter::created, 4);
459 EXPECT_EQ(Counter::destroyed, 4);
460 }
461
TEST(InlineDeque,Modify_PushFront_Copy)462 TEST(InlineDeque, Modify_PushFront_Copy) {
463 Counter value(99);
464 Counter::Reset();
465
466 {
467 InlineDeque<Counter, 10> deque;
468 deque.push_front(value);
469
470 EXPECT_EQ(deque.size(), 1u);
471 EXPECT_EQ(deque.front().value, 99);
472 }
473
474 EXPECT_EQ(Counter::created, 1);
475 EXPECT_EQ(Counter::destroyed, 1);
476 }
477
TEST(InlineDeque,Modify_PushFront_Move)478 TEST(InlineDeque, Modify_PushFront_Move) {
479 Counter::Reset();
480
481 {
482 Counter value(99);
483 InlineDeque<Counter, 10> deque;
484 deque.push_front(std::move(value));
485
486 EXPECT_EQ(deque.size(), 1u);
487 EXPECT_EQ(deque.front().value, 99);
488 // NOLINTNEXTLINE(bugprone-use-after-move)
489 EXPECT_EQ(value.value, 0);
490 }
491
492 EXPECT_EQ(Counter::created, 1);
493 EXPECT_EQ(Counter::destroyed, 2);
494 EXPECT_EQ(Counter::moved, 1);
495 }
496
TEST(InlineDeque,Modify_EmplaceFront)497 TEST(InlineDeque, Modify_EmplaceFront) {
498 Counter::Reset();
499
500 {
501 InlineDeque<Counter, 10> deque;
502 deque.emplace_front(314);
503
504 EXPECT_EQ(deque.size(), 1u);
505 EXPECT_EQ(deque.front().value, 314);
506 }
507
508 EXPECT_EQ(Counter::created, 1);
509 EXPECT_EQ(Counter::destroyed, 1);
510 }
511
TEST(InlineDeque,Modify_PopBack)512 TEST(InlineDeque, Modify_PopBack) {
513 Counter::Reset();
514
515 InlineDeque<Counter, 3> deque;
516 deque.emplace_front(1); // This wraps to the other end.
517 deque.emplace_back(2); // This is the first entry in storage.
518 deque.emplace_back(3);
519 // Content = {1, 2, 3}, Storage = [2, 3, 1]
520
521 ASSERT_EQ(deque.size(), 3u);
522 EXPECT_EQ(deque[0].value, 1);
523 EXPECT_EQ(deque[1].value, 2);
524 EXPECT_EQ(deque[2].value, 3);
525
526 deque.pop_back();
527 // Content = {1, 2}, Storage = [2, x, 1]
528 ASSERT_EQ(deque.size(), 2u);
529 EXPECT_EQ(deque[0].value, 1);
530 EXPECT_EQ(deque[1].value, 2);
531
532 // This wraps around.
533 deque.pop_back();
534 // Content = {1}, Storage = [x, x, 1]
535
536 ASSERT_EQ(deque.size(), 1u);
537 EXPECT_EQ(deque[0].value, 1);
538
539 EXPECT_EQ(Counter::created, 3);
540 EXPECT_EQ(Counter::destroyed, 2);
541 }
542
TEST(InlineDeque,Modify_PopFront)543 TEST(InlineDeque, Modify_PopFront) {
544 Counter::Reset();
545
546 InlineDeque<Counter, 3> deque;
547 deque.emplace_front(1); // This wraps to the other end.
548 deque.emplace_back(2); // This is the first entry in storage.
549 deque.emplace_back(3);
550 // Content = {1, 2, 3}, Storage = [2, 3, 1]
551
552 ASSERT_EQ(deque.size(), 3u);
553 EXPECT_EQ(deque[0].value, 1);
554 EXPECT_EQ(deque[1].value, 2);
555 EXPECT_EQ(deque[2].value, 3);
556
557 // This wraps around
558 deque.pop_front();
559 // Content = {2, 3}, Storage = [2, 3, x]
560
561 EXPECT_EQ(deque.size(), 2u);
562 EXPECT_EQ(deque[0].value, 2);
563 EXPECT_EQ(deque[1].value, 3);
564
565 deque.pop_front();
566 // Content = {3}, Storage = [x, 3, x]
567 ASSERT_EQ(deque.size(), 1u);
568 EXPECT_EQ(deque[0].value, 3);
569
570 EXPECT_EQ(Counter::created, 3);
571 EXPECT_EQ(Counter::destroyed, 2);
572 }
573
TEST(InlineDeque,Modify_Resize_Larger)574 TEST(InlineDeque, Modify_Resize_Larger) {
575 InlineDeque<CopyOnly, 10> deque(1, CopyOnly(123));
576 deque.resize(3, CopyOnly(123));
577
578 EXPECT_EQ(deque.size(), 3u);
579 for (auto& i : deque) {
580 EXPECT_EQ(i.value, 123);
581 }
582 }
583
TEST(InlineDeque,Modify_Resize_LargerThanMax)584 TEST(InlineDeque, Modify_Resize_LargerThanMax) {
585 InlineDeque<CopyOnly, 10> deque;
586 deque.resize(1000, CopyOnly(123));
587
588 EXPECT_EQ(deque.size(), 10u);
589 for (auto& i : deque) {
590 EXPECT_EQ(i.value, 123);
591 }
592 }
593
TEST(InlineDeque,Modify_Resize_Smaller)594 TEST(InlineDeque, Modify_Resize_Smaller) {
595 InlineDeque<CopyOnly, 10> deque(9, CopyOnly(123));
596 deque.resize(3, CopyOnly(123));
597
598 EXPECT_EQ(deque.size(), 3u);
599 for (auto& i : deque) {
600 EXPECT_EQ(i.value, 123);
601 }
602 }
603
TEST(InlineDeque,Modify_Resize_Zero)604 TEST(InlineDeque, Modify_Resize_Zero) {
605 InlineDeque<CopyOnly, 10> deque(10, CopyOnly(123));
606 deque.resize(0, CopyOnly(123));
607
608 EXPECT_EQ(deque.size(), 0u);
609 }
610
TEST(InlineDeque,Generic)611 TEST(InlineDeque, Generic) {
612 InlineDeque<int, 10> deque;
613 InlineDeque<int>& generic_deque(deque);
614 generic_deque = {1, 2, 3, 4, 5};
615
616 EXPECT_EQ(generic_deque.size(), deque.size());
617 EXPECT_EQ(generic_deque.max_size(), deque.max_size());
618
619 unsigned short i = 0;
620 for (int value : deque) {
621 EXPECT_EQ(value, generic_deque[i]);
622 i += 1;
623 }
624
625 i = 0;
626 for (int value : generic_deque) {
627 EXPECT_EQ(deque[i], value);
628 i += 1;
629 }
630 }
631
TEST(InlineDeque,ConstexprMaxSize)632 TEST(InlineDeque, ConstexprMaxSize) {
633 InlineDeque<int, 10> deque;
634 constexpr size_t kMaxSize = deque.max_size();
635 EXPECT_EQ(deque.max_size(), kMaxSize);
636
637 // Ensure the generic sized container does not have a constexpr max_size().
638 [[maybe_unused]] InlineDeque<int>& generic_deque(deque);
639 #if PW_NC_TEST(InlineDeque_GenericMaxSize_NotConstexpr)
640 PW_NC_EXPECT_CLANG(
641 "kGenericMaxSize.* must be initialized by a constant expression");
642 PW_NC_EXPECT_GCC("call to non-'constexpr' function .*InlineDeque.*max_size");
643 [[maybe_unused]] constexpr size_t kGenericMaxSize = generic_deque.max_size();
644 #endif // PW_NC_TEST
645 }
646
TEST(InlineDeque,StdMaxElement)647 TEST(InlineDeque, StdMaxElement) {
648 // Content = {1, 2, 3, 4}, Storage = [1, 2, 3, 4]
649 InlineDeque<int, 4> deque = {1, 2, 3, 4};
650
651 auto max_element_it = std::max_element(deque.begin(), deque.end());
652 ASSERT_NE(max_element_it, deque.end());
653 EXPECT_EQ(*max_element_it, 4);
654
655 // Content = {2, 3, 4}, Storage = [x, 2, 3, 4]
656 deque.pop_front();
657
658 max_element_it = std::max_element(deque.begin(), deque.end());
659 ASSERT_NE(max_element_it, deque.end());
660 EXPECT_EQ(*max_element_it, 4);
661
662 // Content = {2, 3, 4, 5}, Storage = [5, 2, 3, 4]
663 deque.push_back(5);
664 max_element_it = std::max_element(deque.begin(), deque.end());
665 ASSERT_NE(max_element_it, deque.end());
666 EXPECT_EQ(*max_element_it, 5);
667
668 // Content = {}, Storage = [x, x, x, x]
669 deque.clear();
670
671 max_element_it = std::max_element(deque.begin(), deque.end());
672 ASSERT_EQ(max_element_it, deque.end());
673 }
674
TEST(InlineDeque,StdMaxElementConst)675 TEST(InlineDeque, StdMaxElementConst) {
676 // Content = {1, 2, 3, 4}, Storage = [1, 2, 3, 4]
677 InlineDeque<int, 4> deque = {1, 2, 3, 4};
678
679 auto max_element_it = std::max_element(deque.cbegin(), deque.cend());
680 ASSERT_NE(max_element_it, deque.cend());
681 EXPECT_EQ(*max_element_it, 4);
682
683 // Content = {2, 3, 4}, Storage = [x, 2, 3, 4]
684 deque.pop_front();
685
686 max_element_it = std::max_element(deque.cbegin(), deque.cend());
687 ASSERT_NE(max_element_it, deque.cend());
688 EXPECT_EQ(*max_element_it, 4);
689
690 // Content = {2, 3, 4, 5}, Storage = [5, 2, 3, 4]
691 deque.push_back(5);
692 max_element_it = std::max_element(deque.cbegin(), deque.cend());
693 ASSERT_NE(max_element_it, deque.cend());
694 EXPECT_EQ(*max_element_it, 5);
695
696 // Content = {}, Storage = [x, x, x, x]
697 deque.clear();
698
699 max_element_it = std::max_element(deque.cbegin(), deque.cend());
700 ASSERT_EQ(max_element_it, deque.cend());
701 }
702
TEST(InlineDeque,OperatorPlus)703 TEST(InlineDeque, OperatorPlus) {
704 // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
705 InlineDeque<int, 4> deque = {0, 0, 1, 2};
706 // Content = {0, 1, 2}, Storage = [x, 0, 1, 2]
707 deque.pop_front();
708 // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
709 deque.push_back(3);
710 // Content = {1, 2, 3}, Storage = [3, x, 1, 2]
711 deque.pop_front();
712 // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
713 deque.push_back(4);
714
715 for (int i = 0; i < 4; i++) {
716 ASSERT_EQ(*(deque.begin() + i), static_cast<int>(i + 1));
717 ASSERT_EQ(*(i + deque.begin()), static_cast<int>(i + 1));
718 }
719
720 ASSERT_EQ(deque.begin() + deque.size(), deque.end());
721 }
722
TEST(InlineDeque,OperatorPlusPlus)723 TEST(InlineDeque, OperatorPlusPlus) {
724 // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
725 InlineDeque<int, 4> deque = {0, 0, 1, 2};
726 // Content = {0, 1, 2}, Storage = [x, 0, 1, 2]
727 deque.pop_front();
728 // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
729 deque.push_back(3);
730 // Content = {1, 2, 3}, Storage = [3, x, 1, 2]
731 deque.pop_front();
732 // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
733 deque.push_back(4);
734
735 auto it = deque.begin();
736
737 ASSERT_EQ(*it, 1);
738 it++;
739 ASSERT_EQ(*it, 2);
740 it++;
741 ASSERT_EQ(*it, 3);
742 it++;
743 ASSERT_EQ(*it, 4);
744 it++;
745
746 ASSERT_EQ(it, deque.end());
747 }
748
TEST(InlineDeque,OperatorPlusEquals)749 TEST(InlineDeque, OperatorPlusEquals) {
750 // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
751 InlineDeque<int, 4> deque = {0, 0, 1, 2};
752 // Content = {0, 1, 2}, Storage = [x, 0, 1, 2]
753 deque.pop_front();
754 // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
755 deque.push_back(3);
756 // Content = {1, 2, 3}, Storage = [3, x, 1, 2]
757 deque.pop_front();
758 // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
759 deque.push_back(4);
760
761 auto it = deque.begin();
762
763 ASSERT_EQ(*it, 1);
764 it += 1;
765 ASSERT_EQ(*it, 2);
766 it += 1;
767 ASSERT_EQ(*it, 3);
768 it += 1;
769 ASSERT_EQ(*it, 4);
770 it += 1;
771 ASSERT_EQ(it, deque.end());
772
773 it = deque.begin();
774 ASSERT_EQ(*it, 1);
775 it += 2;
776 ASSERT_EQ(*it, 3);
777 it += 2;
778 ASSERT_EQ(it, deque.end());
779
780 it = deque.begin();
781 it += deque.size();
782
783 ASSERT_EQ(it, deque.end());
784 }
785
TEST(InlineDeque,OpeartorMinus)786 TEST(InlineDeque, OpeartorMinus) {
787 // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
788 InlineDeque<int, 4> deque = {0, 0, 1, 2};
789 // Content = {0, 1, 2}, Storage = [x, 0, 1, 2]
790 deque.pop_front();
791 // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
792 deque.push_back(3);
793 // Content = {1, 2, 3}, Storage = [3, x, 1, 2]
794 deque.pop_front();
795 // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
796 deque.push_back(4);
797
798 for (int i = 1; i <= 4; i++) {
799 ASSERT_EQ(*(deque.end() - i), static_cast<int>(5 - i));
800 }
801
802 ASSERT_EQ(deque.end() - deque.size(), deque.begin());
803 }
TEST(InlineDeque,OperatorMinusMinus)804 TEST(InlineDeque, OperatorMinusMinus) {
805 // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
806 InlineDeque<int, 4> deque = {0, 0, 1, 2};
807 // Content = {0, 1, 2}, Storage = [x, 0, 1, 2]
808 deque.pop_front();
809 // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
810 deque.push_back(3);
811 // Content = {1, 2, 3}, Storage = [3, x, 1, 2]
812 deque.pop_front();
813 // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
814 deque.push_back(4);
815
816 auto it = deque.end();
817
818 it--;
819 ASSERT_EQ(*it, 4);
820 it--;
821 ASSERT_EQ(*it, 3);
822 it--;
823 ASSERT_EQ(*it, 2);
824 it--;
825 ASSERT_EQ(*it, 1);
826
827 ASSERT_EQ(it, deque.begin());
828 }
829
TEST(InlineDeque,OperatorMinusEquals)830 TEST(InlineDeque, OperatorMinusEquals) {
831 // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
832 InlineDeque<int, 4> deque = {0, 0, 1, 2};
833 // Content = {0, 1, 2}, Storage = [x, 0, 1, 2]
834 deque.pop_front();
835 // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
836 deque.push_back(3);
837 // Content = {1, 2, 3}, Storage = [3, x, 1, 2]
838 deque.pop_front();
839 // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
840 deque.push_back(4);
841
842 auto it = deque.end();
843
844 it -= 1;
845 ASSERT_EQ(*it, 4);
846 it -= 1;
847 ASSERT_EQ(*it, 3);
848 it -= 1;
849 ASSERT_EQ(*it, 2);
850 it -= 1;
851 ASSERT_EQ(*it, 1);
852
853 ASSERT_EQ(it, deque.begin());
854
855 it = deque.end();
856
857 it -= 2;
858 ASSERT_EQ(*it, 3);
859 it -= 2;
860 ASSERT_EQ(*it, 1);
861
862 ASSERT_EQ(it, deque.begin());
863
864 it = deque.end();
865 it -= deque.size();
866
867 ASSERT_EQ(it, deque.begin());
868 }
869
TEST(InlineDeque,OperatorSquareBracket)870 TEST(InlineDeque, OperatorSquareBracket) {
871 // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
872 InlineDeque<int, 4> deque = {0, 0, 1, 2};
873 // Content = {0, 1, 2}, Storage = [x, 0, 1, 2]
874 deque.pop_front();
875 // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
876 deque.push_back(3);
877 // Content = {1, 2, 3}, Storage = [3, x, 1, 2]
878 deque.pop_front();
879 // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
880 deque.push_back(4);
881
882 for (unsigned short i = 0; i < deque.size(); i++) {
883 ASSERT_EQ(deque.begin()[i], static_cast<int>(i + 1));
884 }
885 }
886
TEST(InlineDeque,OperatorLessThan)887 TEST(InlineDeque, OperatorLessThan) {
888 // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
889 InlineDeque<int, 4> deque = {0, 0, 1, 2};
890 // Content = {0, 1, 2}, Storage = [x, 0, 1, 2]
891 deque.pop_front();
892 // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
893 deque.push_back(3);
894 // Content = {1, 2, 3}, Storage = [3, x, 1, 2]
895 deque.pop_front();
896 // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
897 deque.push_back(4);
898
899 for (int i = 0; i < deque.size(); i++) {
900 for (int j = 0; j < i; j++) {
901 ASSERT_TRUE((deque.begin() + j) < (deque.begin() + i));
902 }
903
904 ASSERT_TRUE((deque.begin() + i) < deque.end());
905 }
906 }
907
TEST(InlineDeque,OperatorLessThanEqual)908 TEST(InlineDeque, OperatorLessThanEqual) {
909 // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
910 InlineDeque<int, 4> deque = {0, 0, 1, 2};
911 // Content = {0, 1, 2}, Storage = [x, 0, 1, 2]
912 deque.pop_front();
913 // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
914 deque.push_back(3);
915 // Content = {1, 2, 3}, Storage = [3, x, 1, 2]
916 deque.pop_front();
917 // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
918 deque.push_back(4);
919
920 for (int i = 0; i < deque.size(); i++) {
921 for (int j = 0; j <= i; j++) {
922 ASSERT_TRUE((deque.begin() + j) <= (deque.begin() + i));
923 }
924
925 ASSERT_TRUE((deque.begin() + i) <= deque.end());
926 }
927 }
928
TEST(InlineDeque,OperatorGreater)929 TEST(InlineDeque, OperatorGreater) {
930 // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
931 InlineDeque<int, 4> deque = {0, 0, 1, 2};
932 // Content = {0, 1, 2}, Storage = [x, 0, 1, 2]
933 deque.pop_front();
934 // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
935 deque.push_back(3);
936 // Content = {1, 2, 3}, Storage = [3, x, 1, 2]
937 deque.pop_front();
938 // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
939 deque.push_back(4);
940
941 for (int i = 0; i < deque.size(); i++) {
942 for (int j = i + 1; j < deque.size(); j++) {
943 ASSERT_TRUE((deque.begin() + j) > (deque.begin() + i));
944 }
945
946 ASSERT_TRUE(deque.end() > (deque.begin() + i));
947 }
948 }
949
TEST(InlineDeque,OperatorGreaterThanEqual)950 TEST(InlineDeque, OperatorGreaterThanEqual) {
951 // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
952 InlineDeque<int, 4> deque = {0, 0, 1, 2};
953 // Content = {0, 1, 2}, Storage = [x, 0, 1, 2]
954 deque.pop_front();
955 // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
956 deque.push_back(3);
957 // Content = {1, 2, 3}, Storage = [3, x, 1, 2]
958 deque.pop_front();
959 // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
960 deque.push_back(4);
961
962 for (int i = 0; i < deque.size(); i++) {
963 for (int j = i; j < deque.size(); j++) {
964 ASSERT_TRUE((deque.begin() + j) >= (deque.begin() + i));
965 }
966
967 ASSERT_TRUE(deque.end() >= (deque.begin() + i));
968 }
969 }
970
TEST(InlineDeque,DereferenceOperator)971 TEST(InlineDeque, DereferenceOperator) {
972 // Content = {0, 0, 1, 2}, Storage = [0, 0, 1, 2]
973 InlineDeque<int, 4> deque = {0, 0, 1, 2};
974 // Content = {0, 1, 2}, Storage = [x, 0, 1, 2]
975 deque.pop_front();
976 // Content = {0, 1, 2, 3}, Storage = [3, 0, 1, 2]
977 deque.push_back(3);
978 // Content = {1, 2, 3}, Storage = [3, x, 1, 2]
979 deque.pop_front();
980 // Content = {1, 2, 3, 4}, Storage = [3, 4, 1, 2]
981 deque.push_back(4);
982
983 for (int i = 0; i < deque.size(); i++) {
984 const auto it = deque.begin() + i;
985 ASSERT_EQ(*(it.operator->()), static_cast<int>(i + 1));
986 }
987 }
988
989 // Test that InlineDeque<T> is trivially destructible when its type is.
990 static_assert(std::is_trivially_destructible_v<InlineDeque<int, 4>>);
991
992 static_assert(std::is_trivially_destructible_v<MoveOnly>);
993 static_assert(std::is_trivially_destructible_v<InlineDeque<MoveOnly, 1>>);
994
995 static_assert(std::is_trivially_destructible_v<CopyOnly>);
996 static_assert(std::is_trivially_destructible_v<InlineDeque<CopyOnly, 99>>);
997
998 static_assert(!std::is_trivially_destructible_v<Counter>);
999 static_assert(!std::is_trivially_destructible_v<InlineDeque<Counter, 99>>);
1000
1001 // Generic-capacity deques cannot be constructed or destructed.
1002 static_assert(!std::is_constructible_v<InlineDeque<int>>);
1003 static_assert(!std::is_destructible_v<InlineDeque<int>>);
1004
1005 // Tests that InlineDeque<T> does not have any extra padding.
1006 static_assert(sizeof(InlineDeque<uint8_t, 1>) ==
1007 sizeof(InlineDeque<uint8_t>::size_type) * 4 +
1008 std::max(sizeof(InlineDeque<uint8_t>::size_type),
1009 sizeof(uint8_t)));
1010 static_assert(sizeof(InlineDeque<uint8_t, 2>) ==
1011 sizeof(InlineDeque<uint8_t>::size_type) * 4 +
1012 2 * sizeof(uint8_t));
1013 static_assert(sizeof(InlineDeque<uint16_t, 1>) ==
1014 sizeof(InlineDeque<uint16_t>::size_type) * 4 + sizeof(uint16_t));
1015 static_assert(sizeof(InlineDeque<uint32_t, 1>) ==
1016 sizeof(InlineDeque<uint32_t>::size_type) * 4 + sizeof(uint32_t));
1017 static_assert(sizeof(InlineDeque<uint64_t, 1>) ==
1018 sizeof(InlineDeque<uint64_t>::size_type) * 4 + sizeof(uint64_t));
1019
1020 // Test that InlineDeque<T> is copy constructible
1021 static_assert(std::is_copy_constructible_v<InlineDeque<int, 4>::iterator>);
1022
1023 // Test that InlineDeque<T> is move constructible
1024 static_assert(std::is_move_constructible_v<InlineDeque<MoveOnly, 4>::iterator>);
1025
1026 // Test that InlineDeque<T> is copy assignable
1027 static_assert(std::is_copy_assignable_v<InlineDeque<int>::iterator>);
1028 static_assert(std::is_copy_assignable_v<InlineDeque<int, 4>::iterator>);
1029
1030 // Test that InlineDeque<T> is move assignable
1031 static_assert(std::is_move_assignable_v<InlineDeque<MoveOnly>>);
1032 static_assert(std::is_move_assignable_v<InlineDeque<MoveOnly, 4>>);
1033
1034 // Test that InlineDeque<T>::iterator can be converted to a const_iterator
1035 static_assert(std::is_convertible<InlineDeque<int>::iterator,
1036 InlineDeque<int>::const_iterator>::value);
1037 static_assert(std::is_convertible<InlineDeque<int, 4>::iterator,
1038 InlineDeque<int, 4>::const_iterator>::value);
1039
1040 // Test that InlineDeque<T>::const_iterator can NOT be converted to a iterator
1041 static_assert(!std::is_convertible<InlineDeque<int>::const_iterator,
1042 InlineDeque<int>::iterator>::value);
1043 static_assert(!std::is_convertible<InlineDeque<int, 4>::const_iterator,
1044 InlineDeque<int, 4>::iterator>::value);
1045
1046 } // namespace
1047 } // namespace pw::containers
1048