1 // Copyright 2017 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "base/containers/circular_deque.h"
6
7 #include "base/test/copy_only_int.h"
8 #include "base/test/move_only_int.h"
9 #include "testing/gtest/include/gtest/gtest.h"
10
11 using base::internal::VectorBuffer;
12
13 namespace base {
14
15 namespace {
16
MakeSequence(size_t max)17 circular_deque<int> MakeSequence(size_t max) {
18 circular_deque<int> ret;
19 for (size_t i = 0; i < max; i++)
20 ret.push_back(i);
21 return ret;
22 }
23
24 // Cycles through the queue, popping items from the back and pushing items
25 // at the front to validate behavior across different configurations of the
26 // queue in relation to the underlying buffer. The tester closure is run for
27 // each cycle.
28 template <class QueueT, class Tester>
CycleTest(circular_deque<QueueT> & queue,const Tester & tester)29 void CycleTest(circular_deque<QueueT>& queue, const Tester& tester) {
30 size_t steps = queue.size() * 2;
31 for (size_t i = 0; i < steps; i++) {
32 tester(queue, i);
33 queue.pop_back();
34 queue.push_front(QueueT());
35 }
36 }
37
38 class DestructorCounter {
39 public:
DestructorCounter(int * counter)40 DestructorCounter(int* counter) : counter_(counter) {}
~DestructorCounter()41 ~DestructorCounter() { ++(*counter_); }
42
43 private:
44 int* counter_;
45 };
46
47 } // namespace
48
TEST(CircularDeque,FillConstructor)49 TEST(CircularDeque, FillConstructor) {
50 constexpr size_t num_elts = 9;
51
52 std::vector<int> foo(15);
53 EXPECT_EQ(15u, foo.size());
54
55 // Fill with default constructor.
56 {
57 circular_deque<int> buf(num_elts);
58
59 EXPECT_EQ(num_elts, buf.size());
60 EXPECT_EQ(num_elts, static_cast<size_t>(buf.end() - buf.begin()));
61
62 for (size_t i = 0; i < num_elts; i++)
63 EXPECT_EQ(0, buf[i]);
64 }
65
66 // Fill with explicit value.
67 {
68 int value = 199;
69 circular_deque<int> buf(num_elts, value);
70
71 EXPECT_EQ(num_elts, buf.size());
72 EXPECT_EQ(num_elts, static_cast<size_t>(buf.end() - buf.begin()));
73
74 for (size_t i = 0; i < num_elts; i++)
75 EXPECT_EQ(value, buf[i]);
76 }
77 }
78
TEST(CircularDeque,CopyAndRangeConstructor)79 TEST(CircularDeque, CopyAndRangeConstructor) {
80 int values[] = {1, 2, 3, 4, 5, 6};
81 circular_deque<CopyOnlyInt> first(std::begin(values), std::end(values));
82
83 circular_deque<CopyOnlyInt> second(first);
84 EXPECT_EQ(6u, second.size());
85 for (int i = 0; i < 6; i++)
86 EXPECT_EQ(i + 1, second[i].data());
87 }
88
TEST(CircularDeque,MoveConstructor)89 TEST(CircularDeque, MoveConstructor) {
90 int values[] = {1, 2, 3, 4, 5, 6};
91 circular_deque<MoveOnlyInt> first(std::begin(values), std::end(values));
92
93 circular_deque<MoveOnlyInt> second(std::move(first));
94 EXPECT_TRUE(first.empty());
95 EXPECT_EQ(6u, second.size());
96 for (int i = 0; i < 6; i++)
97 EXPECT_EQ(i + 1, second[i].data());
98 }
99
TEST(CircularDeque,InitializerListConstructor)100 TEST(CircularDeque, InitializerListConstructor) {
101 circular_deque<int> empty({});
102 ASSERT_TRUE(empty.empty());
103
104 circular_deque<int> first({1, 2, 3, 4, 5, 6});
105 EXPECT_EQ(6u, first.size());
106 for (int i = 0; i < 6; i++)
107 EXPECT_EQ(i + 1, first[i]);
108 }
109
TEST(CircularDeque,Destructor)110 TEST(CircularDeque, Destructor) {
111 int destruct_count = 0;
112
113 // Contiguous buffer.
114 {
115 circular_deque<DestructorCounter> q;
116 q.resize(5, DestructorCounter(&destruct_count));
117
118 EXPECT_EQ(1, destruct_count); // The temporary in the call to resize().
119 destruct_count = 0;
120 }
121 EXPECT_EQ(5, destruct_count); // One call for each.
122
123 // Force a wraparound buffer.
124 {
125 circular_deque<DestructorCounter> q;
126 q.reserve(7);
127 q.resize(5, DestructorCounter(&destruct_count));
128
129 // Cycle throught some elements in our buffer to force a wraparound.
130 destruct_count = 0;
131 for (int i = 0; i < 4; i++) {
132 q.emplace_back(&destruct_count);
133 q.pop_front();
134 }
135 EXPECT_EQ(4, destruct_count); // One for each cycle.
136 destruct_count = 0;
137 }
138 EXPECT_EQ(5, destruct_count); // One call for each.
139 }
140
TEST(CircularDeque,EqualsCopy)141 TEST(CircularDeque, EqualsCopy) {
142 circular_deque<int> first = {1, 2, 3, 4, 5, 6};
143 circular_deque<int> copy;
144 EXPECT_TRUE(copy.empty());
145 copy = first;
146 EXPECT_EQ(6u, copy.size());
147 for (int i = 0; i < 6; i++) {
148 EXPECT_EQ(i + 1, first[i]);
149 EXPECT_EQ(i + 1, copy[i]);
150 EXPECT_NE(&first[i], ©[i]);
151 }
152 }
153
TEST(CircularDeque,EqualsMove)154 TEST(CircularDeque, EqualsMove) {
155 circular_deque<int> first = {1, 2, 3, 4, 5, 6};
156 circular_deque<int> move;
157 EXPECT_TRUE(move.empty());
158 move = std::move(first);
159 EXPECT_TRUE(first.empty());
160 EXPECT_EQ(6u, move.size());
161 for (int i = 0; i < 6; i++)
162 EXPECT_EQ(i + 1, move[i]);
163 }
164
165 // Tests that self-assignment is a no-op.
TEST(CircularDeque,EqualsSelf)166 TEST(CircularDeque, EqualsSelf) {
167 circular_deque<int> q = {1, 2, 3, 4, 5, 6};
168 q = *&q; // The *& defeats Clang's -Wself-assign warning.
169 EXPECT_EQ(6u, q.size());
170 for (int i = 0; i < 6; i++)
171 EXPECT_EQ(i + 1, q[i]);
172 }
173
TEST(CircularDeque,EqualsInitializerList)174 TEST(CircularDeque, EqualsInitializerList) {
175 circular_deque<int> q;
176 EXPECT_TRUE(q.empty());
177 q = {1, 2, 3, 4, 5, 6};
178 EXPECT_EQ(6u, q.size());
179 for (int i = 0; i < 6; i++)
180 EXPECT_EQ(i + 1, q[i]);
181 }
182
TEST(CircularDeque,AssignCountValue)183 TEST(CircularDeque, AssignCountValue) {
184 circular_deque<int> empty;
185 empty.assign(0, 52);
186 EXPECT_EQ(0u, empty.size());
187
188 circular_deque<int> full;
189 size_t count = 13;
190 int value = 12345;
191 full.assign(count, value);
192 EXPECT_EQ(count, full.size());
193
194 for (size_t i = 0; i < count; i++)
195 EXPECT_EQ(value, full[i]);
196 }
197
TEST(CircularDeque,AssignIterator)198 TEST(CircularDeque, AssignIterator) {
199 int range[8] = {11, 12, 13, 14, 15, 16, 17, 18};
200
201 circular_deque<int> empty;
202 empty.assign(std::begin(range), std::begin(range));
203 EXPECT_TRUE(empty.empty());
204
205 circular_deque<int> full;
206 full.assign(std::begin(range), std::end(range));
207 EXPECT_EQ(8u, full.size());
208 for (size_t i = 0; i < 8; i++)
209 EXPECT_EQ(range[i], full[i]);
210 }
211
TEST(CircularDeque,AssignInitializerList)212 TEST(CircularDeque, AssignInitializerList) {
213 circular_deque<int> empty;
214 empty.assign({});
215 EXPECT_TRUE(empty.empty());
216
217 circular_deque<int> full;
218 full.assign({11, 12, 13, 14, 15, 16, 17, 18});
219 EXPECT_EQ(8u, full.size());
220 for (int i = 0; i < 8; i++)
221 EXPECT_EQ(11 + i, full[i]);
222 }
223
224 // Tests [] and .at().
TEST(CircularDeque,At)225 TEST(CircularDeque, At) {
226 circular_deque<int> q = MakeSequence(10);
227 CycleTest(q, [](const circular_deque<int>& q, size_t cycle) {
228 size_t expected_size = 10;
229 EXPECT_EQ(expected_size, q.size());
230
231 // A sequence of 0's.
232 size_t index = 0;
233 size_t num_zeros = std::min(expected_size, cycle);
234 for (size_t i = 0; i < num_zeros; i++, index++) {
235 EXPECT_EQ(0, q[index]);
236 EXPECT_EQ(0, q.at(index));
237 }
238
239 // Followed by a sequence of increasing ints.
240 size_t num_ints = expected_size - num_zeros;
241 for (int i = 0; i < static_cast<int>(num_ints); i++, index++) {
242 EXPECT_EQ(i, q[index]);
243 EXPECT_EQ(i, q.at(index));
244 }
245 });
246 }
247
248 // This also tests the copy constructor with lots of different types of
249 // input configurations.
TEST(CircularDeque,FrontBackPushPop)250 TEST(CircularDeque, FrontBackPushPop) {
251 circular_deque<int> q = MakeSequence(10);
252
253 int expected_front = 0;
254 int expected_back = 9;
255
256 // Go in one direction.
257 for (int i = 0; i < 100; i++) {
258 const circular_deque<int> const_q(q);
259
260 EXPECT_EQ(expected_front, q.front());
261 EXPECT_EQ(expected_back, q.back());
262 EXPECT_EQ(expected_front, const_q.front());
263 EXPECT_EQ(expected_back, const_q.back());
264
265 expected_front++;
266 expected_back++;
267
268 q.pop_front();
269 q.push_back(expected_back);
270 }
271
272 // Go back in reverse.
273 for (int i = 0; i < 100; i++) {
274 const circular_deque<int> const_q(q);
275
276 EXPECT_EQ(expected_front, q.front());
277 EXPECT_EQ(expected_back, q.back());
278 EXPECT_EQ(expected_front, const_q.front());
279 EXPECT_EQ(expected_back, const_q.back());
280
281 expected_front--;
282 expected_back--;
283
284 q.pop_back();
285 q.push_front(expected_front);
286 }
287 }
288
TEST(CircularDeque,ReallocateWithSplitBuffer)289 TEST(CircularDeque, ReallocateWithSplitBuffer) {
290 // Tests reallocating a deque with an internal buffer that looks like this:
291 // 4 5 x x 0 1 2 3
292 // end-^ ^-begin
293 circular_deque<int> q;
294 q.reserve(7); // Internal buffer is always 1 larger than requested.
295 q.push_back(-1);
296 q.push_back(-1);
297 q.push_back(-1);
298 q.push_back(-1);
299 q.push_back(0);
300 q.pop_front();
301 q.pop_front();
302 q.pop_front();
303 q.pop_front();
304 q.push_back(1);
305 q.push_back(2);
306 q.push_back(3);
307 q.push_back(4);
308 q.push_back(5);
309
310 q.shrink_to_fit();
311 EXPECT_EQ(6u, q.size());
312
313 EXPECT_EQ(0, q[0]);
314 EXPECT_EQ(1, q[1]);
315 EXPECT_EQ(2, q[2]);
316 EXPECT_EQ(3, q[3]);
317 EXPECT_EQ(4, q[4]);
318 EXPECT_EQ(5, q[5]);
319 }
320
TEST(CircularDeque,Swap)321 TEST(CircularDeque, Swap) {
322 circular_deque<int> a = MakeSequence(10);
323 circular_deque<int> b = MakeSequence(100);
324
325 a.swap(b);
326 EXPECT_EQ(100u, a.size());
327 for (int i = 0; i < 100; i++)
328 EXPECT_EQ(i, a[i]);
329
330 EXPECT_EQ(10u, b.size());
331 for (int i = 0; i < 10; i++)
332 EXPECT_EQ(i, b[i]);
333 }
334
TEST(CircularDeque,Iteration)335 TEST(CircularDeque, Iteration) {
336 circular_deque<int> q = MakeSequence(10);
337
338 int expected_front = 0;
339 int expected_back = 9;
340
341 // This loop causes various combinations of begin and end to be tested.
342 for (int i = 0; i < 30; i++) {
343 // Range-based for loop going forward.
344 int current_expected = expected_front;
345 for (int cur : q) {
346 EXPECT_EQ(current_expected, cur);
347 current_expected++;
348 }
349
350 // Manually test reverse iterators.
351 current_expected = expected_back;
352 for (auto cur = q.crbegin(); cur < q.crend(); cur++) {
353 EXPECT_EQ(current_expected, *cur);
354 current_expected--;
355 }
356
357 expected_front++;
358 expected_back++;
359
360 q.pop_front();
361 q.push_back(expected_back);
362 }
363
364 // Go back in reverse.
365 for (int i = 0; i < 100; i++) {
366 const circular_deque<int> const_q(q);
367
368 EXPECT_EQ(expected_front, q.front());
369 EXPECT_EQ(expected_back, q.back());
370 EXPECT_EQ(expected_front, const_q.front());
371 EXPECT_EQ(expected_back, const_q.back());
372
373 expected_front--;
374 expected_back--;
375
376 q.pop_back();
377 q.push_front(expected_front);
378 }
379 }
380
TEST(CircularDeque,IteratorComparisons)381 TEST(CircularDeque, IteratorComparisons) {
382 circular_deque<int> q = MakeSequence(10);
383
384 // This loop causes various combinations of begin and end to be tested.
385 for (int i = 0; i < 30; i++) {
386 EXPECT_LT(q.begin(), q.end());
387 EXPECT_LE(q.begin(), q.end());
388 EXPECT_LE(q.begin(), q.begin());
389
390 EXPECT_GT(q.end(), q.begin());
391 EXPECT_GE(q.end(), q.begin());
392 EXPECT_GE(q.end(), q.end());
393
394 EXPECT_EQ(q.begin(), q.begin());
395 EXPECT_NE(q.begin(), q.end());
396
397 q.push_front(10);
398 q.pop_back();
399 }
400 }
401
TEST(CircularDeque,IteratorIncDec)402 TEST(CircularDeque, IteratorIncDec) {
403 circular_deque<int> q;
404
405 // No-op offset computations with no capacity.
406 EXPECT_EQ(q.end(), q.end() + 0);
407 EXPECT_EQ(q.end(), q.end() - 0);
408
409 q = MakeSequence(10);
410
411 // Mutable preincrement, predecrement.
412 {
413 circular_deque<int>::iterator it = q.begin();
414 circular_deque<int>::iterator op_result = ++it;
415 EXPECT_EQ(1, *op_result);
416 EXPECT_EQ(1, *it);
417
418 op_result = --it;
419 EXPECT_EQ(0, *op_result);
420 EXPECT_EQ(0, *it);
421 }
422
423 // Const preincrement, predecrement.
424 {
425 circular_deque<int>::const_iterator it = q.begin();
426 circular_deque<int>::const_iterator op_result = ++it;
427 EXPECT_EQ(1, *op_result);
428 EXPECT_EQ(1, *it);
429
430 op_result = --it;
431 EXPECT_EQ(0, *op_result);
432 EXPECT_EQ(0, *it);
433 }
434
435 // Mutable postincrement, postdecrement.
436 {
437 circular_deque<int>::iterator it = q.begin();
438 circular_deque<int>::iterator op_result = it++;
439 EXPECT_EQ(0, *op_result);
440 EXPECT_EQ(1, *it);
441
442 op_result = it--;
443 EXPECT_EQ(1, *op_result);
444 EXPECT_EQ(0, *it);
445 }
446
447 // Const postincrement, postdecrement.
448 {
449 circular_deque<int>::const_iterator it = q.begin();
450 circular_deque<int>::const_iterator op_result = it++;
451 EXPECT_EQ(0, *op_result);
452 EXPECT_EQ(1, *it);
453
454 op_result = it--;
455 EXPECT_EQ(1, *op_result);
456 EXPECT_EQ(0, *it);
457 }
458 }
459
TEST(CircularDeque,IteratorIntegerOps)460 TEST(CircularDeque, IteratorIntegerOps) {
461 circular_deque<int> q = MakeSequence(10);
462
463 int expected_front = 0;
464 int expected_back = 9;
465
466 for (int i = 0; i < 30; i++) {
467 EXPECT_EQ(0, q.begin() - q.begin());
468 EXPECT_EQ(0, q.end() - q.end());
469 EXPECT_EQ(q.size(), static_cast<size_t>(q.end() - q.begin()));
470
471 // +=
472 circular_deque<int>::iterator eight = q.begin();
473 eight += 8;
474 EXPECT_EQ(8, eight - q.begin());
475 EXPECT_EQ(expected_front + 8, *eight);
476
477 // -=
478 eight -= 8;
479 EXPECT_EQ(q.begin(), eight);
480
481 // +
482 eight = eight + 8;
483 EXPECT_EQ(8, eight - q.begin());
484
485 // -
486 eight = eight - 8;
487 EXPECT_EQ(q.begin(), eight);
488
489 expected_front++;
490 expected_back++;
491
492 q.pop_front();
493 q.push_back(expected_back);
494 }
495 }
496
TEST(CircularDeque,IteratorArrayAccess)497 TEST(CircularDeque, IteratorArrayAccess) {
498 circular_deque<int> q = MakeSequence(10);
499
500 circular_deque<int>::iterator begin = q.begin();
501 EXPECT_EQ(0, begin[0]);
502 EXPECT_EQ(9, begin[9]);
503
504 circular_deque<int>::iterator end = q.end();
505 EXPECT_EQ(0, end[-10]);
506 EXPECT_EQ(9, end[-1]);
507
508 begin[0] = 100;
509 EXPECT_EQ(100, end[-10]);
510 }
511
TEST(CircularDeque,ReverseIterator)512 TEST(CircularDeque, ReverseIterator) {
513 circular_deque<int> q;
514 q.push_back(4);
515 q.push_back(3);
516 q.push_back(2);
517 q.push_back(1);
518
519 circular_deque<int>::reverse_iterator iter = q.rbegin();
520 EXPECT_EQ(1, *iter);
521 iter++;
522 EXPECT_EQ(2, *iter);
523 ++iter;
524 EXPECT_EQ(3, *iter);
525 iter++;
526 EXPECT_EQ(4, *iter);
527 ++iter;
528 EXPECT_EQ(q.rend(), iter);
529 }
530
TEST(CircularDeque,CapacityReserveShrink)531 TEST(CircularDeque, CapacityReserveShrink) {
532 circular_deque<int> q;
533
534 // A default constructed queue should have no capacity since it should waste
535 // no space.
536 EXPECT_TRUE(q.empty());
537 EXPECT_EQ(0u, q.size());
538 EXPECT_EQ(0u, q.capacity());
539
540 size_t new_capacity = 100;
541 q.reserve(new_capacity);
542 EXPECT_EQ(new_capacity, q.capacity());
543
544 // Adding that many items should not cause a resize.
545 for (size_t i = 0; i < new_capacity; i++)
546 q.push_back(i);
547 EXPECT_EQ(new_capacity, q.size());
548 EXPECT_EQ(new_capacity, q.capacity());
549
550 // Shrink to fit to a smaller size.
551 size_t capacity_2 = new_capacity / 2;
552 q.resize(capacity_2);
553 q.shrink_to_fit();
554 EXPECT_EQ(capacity_2, q.size());
555 EXPECT_EQ(capacity_2, q.capacity());
556 }
557
TEST(CircularDeque,CapacityAutoShrink)558 TEST(CircularDeque, CapacityAutoShrink) {
559 size_t big_size = 1000u;
560 circular_deque<int> q;
561 q.resize(big_size);
562
563 size_t big_capacity = q.capacity();
564
565 // Delete 3/4 of the items.
566 for (size_t i = 0; i < big_size / 4 * 3; i++)
567 q.pop_back();
568
569 // The capacity should have shrunk by deleting that many items.
570 size_t medium_capacity = q.capacity();
571 EXPECT_GT(big_capacity, medium_capacity);
572
573 // Using resize to shrink should keep some extra capacity.
574 q.resize(1);
575 EXPECT_LT(1u, q.capacity());
576
577 q.resize(0);
578 EXPECT_LT(0u, q.capacity());
579
580 // Using clear() should delete everything.
581 q.clear();
582 EXPECT_EQ(0u, q.capacity());
583 }
584
TEST(CircularDeque,ClearAndEmpty)585 TEST(CircularDeque, ClearAndEmpty) {
586 circular_deque<int> q;
587 EXPECT_TRUE(q.empty());
588
589 q.resize(10);
590 EXPECT_EQ(10u, q.size());
591 EXPECT_FALSE(q.empty());
592
593 q.clear();
594 EXPECT_EQ(0u, q.size());
595 EXPECT_TRUE(q.empty());
596
597 // clear() also should reset the capacity.
598 EXPECT_EQ(0u, q.capacity());
599 }
600
TEST(CircularDeque,Resize)601 TEST(CircularDeque, Resize) {
602 circular_deque<int> q;
603
604 // Resize with default constructor.
605 size_t first_size = 10;
606 q.resize(first_size);
607 EXPECT_EQ(first_size, q.size());
608 for (size_t i = 0; i < first_size; i++)
609 EXPECT_EQ(0, q[i]);
610
611 // Resize with different value.
612 size_t second_expand = 10;
613 q.resize(first_size + second_expand, 3);
614 EXPECT_EQ(first_size + second_expand, q.size());
615 for (size_t i = 0; i < first_size; i++)
616 EXPECT_EQ(0, q[i]);
617 for (size_t i = 0; i < second_expand; i++)
618 EXPECT_EQ(3, q[i + first_size]);
619
620 // Erase from the end and add to the beginning so resize is forced to cross
621 // a circular buffer wrap boundary.
622 q.shrink_to_fit();
623 for (int i = 0; i < 5; i++) {
624 q.pop_back();
625 q.push_front(6);
626 }
627 q.resize(10);
628
629 EXPECT_EQ(6, q[0]);
630 EXPECT_EQ(6, q[1]);
631 EXPECT_EQ(6, q[2]);
632 EXPECT_EQ(6, q[3]);
633 EXPECT_EQ(6, q[4]);
634 EXPECT_EQ(0, q[5]);
635 EXPECT_EQ(0, q[6]);
636 EXPECT_EQ(0, q[7]);
637 EXPECT_EQ(0, q[8]);
638 EXPECT_EQ(0, q[9]);
639 }
640
641 // Tests destructor behavior of resize.
TEST(CircularDeque,ResizeDelete)642 TEST(CircularDeque, ResizeDelete) {
643 int counter = 0;
644 circular_deque<DestructorCounter> q;
645 q.resize(10, DestructorCounter(&counter));
646 // The one temporary when calling resize() should be deleted, that's it.
647 EXPECT_EQ(1, counter);
648
649 // The loops below assume the capacity will be set by resize().
650 EXPECT_EQ(10u, q.capacity());
651
652 // Delete some via resize(). This is done so that the wasted items are
653 // still greater than the size() so that auto-shrinking is not triggered
654 // (which will mess up our destructor counting).
655 counter = 0;
656 q.resize(8, DestructorCounter(&counter));
657 // 2 deleted ones + the one temporary in the resize() call.
658 EXPECT_EQ(3, counter);
659
660 // Cycle through some items so two items will cross the boundary in the
661 // 11-item buffer (one more than the capacity).
662 // Before: x x x x x x x x . . .
663 // After: x . . . x x x x x x x
664 counter = 0;
665 for (int i = 0; i < 4; i++) {
666 q.emplace_back(&counter);
667 q.pop_front();
668 }
669 EXPECT_EQ(4, counter); // Loop should have deleted 7 items.
670
671 // Delete two items with resize, these should be on either side of the
672 // buffer wrap point.
673 counter = 0;
674 q.resize(6, DestructorCounter(&counter));
675 // 2 deleted ones + the one temporary in the resize() call.
676 EXPECT_EQ(3, counter);
677 }
678
TEST(CircularDeque,InsertEraseSingle)679 TEST(CircularDeque, InsertEraseSingle) {
680 circular_deque<int> q;
681 q.push_back(1);
682 q.push_back(2);
683
684 // Insert at the beginning.
685 auto result = q.insert(q.begin(), 0);
686 EXPECT_EQ(q.begin(), result);
687 EXPECT_EQ(3u, q.size());
688 EXPECT_EQ(0, q[0]);
689 EXPECT_EQ(1, q[1]);
690 EXPECT_EQ(2, q[2]);
691
692 // Erase at the beginning.
693 result = q.erase(q.begin());
694 EXPECT_EQ(q.begin(), result);
695 EXPECT_EQ(2u, q.size());
696 EXPECT_EQ(1, q[0]);
697 EXPECT_EQ(2, q[1]);
698
699 // Insert at the end.
700 result = q.insert(q.end(), 3);
701 EXPECT_EQ(q.end() - 1, result);
702 EXPECT_EQ(1, q[0]);
703 EXPECT_EQ(2, q[1]);
704 EXPECT_EQ(3, q[2]);
705
706 // Erase at the end.
707 result = q.erase(q.end() - 1);
708 EXPECT_EQ(q.end(), result);
709 EXPECT_EQ(1, q[0]);
710 EXPECT_EQ(2, q[1]);
711
712 // Insert in the middle.
713 result = q.insert(q.begin() + 1, 10);
714 EXPECT_EQ(q.begin() + 1, result);
715 EXPECT_EQ(1, q[0]);
716 EXPECT_EQ(10, q[1]);
717 EXPECT_EQ(2, q[2]);
718
719 // Erase in the middle.
720 result = q.erase(q.begin() + 1);
721 EXPECT_EQ(q.begin() + 1, result);
722 EXPECT_EQ(1, q[0]);
723 EXPECT_EQ(2, q[1]);
724 }
725
TEST(CircularDeque,InsertFill)726 TEST(CircularDeque, InsertFill) {
727 circular_deque<int> q;
728
729 // Fill when empty.
730 q.insert(q.begin(), 2, 1);
731
732 // 0's at the beginning.
733 q.insert(q.begin(), 2, 0);
734
735 // 50's in the middle (now at offset 3).
736 q.insert(q.begin() + 3, 2, 50);
737
738 // 200's at the end.
739 q.insert(q.end(), 2, 200);
740
741 ASSERT_EQ(8u, q.size());
742 EXPECT_EQ(0, q[0]);
743 EXPECT_EQ(0, q[1]);
744 EXPECT_EQ(1, q[2]);
745 EXPECT_EQ(50, q[3]);
746 EXPECT_EQ(50, q[4]);
747 EXPECT_EQ(1, q[5]);
748 EXPECT_EQ(200, q[6]);
749 EXPECT_EQ(200, q[7]);
750 }
751
TEST(CircularDeque,InsertEraseRange)752 TEST(CircularDeque, InsertEraseRange) {
753 circular_deque<int> q;
754
755 // Erase nothing from an empty deque should work.
756 q.erase(q.begin(), q.end());
757
758 // Loop index used below to shift the used items in the buffer.
759 for (int i = 0; i < 10; i++) {
760 circular_deque<int> source;
761
762 // Fill empty range.
763 q.insert(q.begin(), source.begin(), source.end());
764
765 // Have some stuff to insert.
766 source.push_back(1);
767 source.push_back(2);
768
769 q.insert(q.begin(), source.begin(), source.end());
770
771 // Shift the used items in the buffer by i which will place the two used
772 // elements in different places in the buffer each time through this loop.
773 for (int shift_i = 0; shift_i < i; shift_i++) {
774 q.push_back(0);
775 q.pop_front();
776 }
777
778 // Set the two items to notable values so we can check for them later.
779 ASSERT_EQ(2u, q.size());
780 q[0] = 100;
781 q[1] = 101;
782
783 // Insert at the beginning, middle (now at offset 3), and end.
784 q.insert(q.begin(), source.begin(), source.end());
785 q.insert(q.begin() + 3, source.begin(), source.end());
786 q.insert(q.end(), source.begin(), source.end());
787
788 ASSERT_EQ(8u, q.size());
789 EXPECT_EQ(1, q[0]);
790 EXPECT_EQ(2, q[1]);
791 EXPECT_EQ(100, q[2]); // First inserted one.
792 EXPECT_EQ(1, q[3]);
793 EXPECT_EQ(2, q[4]);
794 EXPECT_EQ(101, q[5]); // First inserted second one.
795 EXPECT_EQ(1, q[6]);
796 EXPECT_EQ(2, q[7]);
797
798 // Now erase the inserted ranges. Try each subsection also with no items
799 // being erased, which should be a no-op.
800 auto result = q.erase(q.begin(), q.begin()); // No-op.
801 EXPECT_EQ(q.begin(), result);
802 result = q.erase(q.begin(), q.begin() + 2);
803 EXPECT_EQ(q.begin(), result);
804
805 result = q.erase(q.begin() + 1, q.begin() + 1); // No-op.
806 EXPECT_EQ(q.begin() + 1, result);
807 result = q.erase(q.begin() + 1, q.begin() + 3);
808 EXPECT_EQ(q.begin() + 1, result);
809
810 result = q.erase(q.end() - 2, q.end() - 2); // No-op.
811 EXPECT_EQ(q.end() - 2, result);
812 result = q.erase(q.end() - 2, q.end());
813 EXPECT_EQ(q.end(), result);
814
815 ASSERT_EQ(2u, q.size());
816 EXPECT_EQ(100, q[0]);
817 EXPECT_EQ(101, q[1]);
818
819 // Erase everything.
820 result = q.erase(q.begin(), q.end());
821 EXPECT_EQ(q.end(), result);
822 EXPECT_TRUE(q.empty());
823 }
824 }
825
TEST(CircularDeque,EmplaceMoveOnly)826 TEST(CircularDeque, EmplaceMoveOnly) {
827 int values[] = {1, 3};
828 circular_deque<MoveOnlyInt> q(std::begin(values), std::end(values));
829
830 q.emplace(q.begin(), MoveOnlyInt(0));
831 q.emplace(q.begin() + 2, MoveOnlyInt(2));
832 q.emplace(q.end(), MoveOnlyInt(4));
833
834 ASSERT_EQ(5u, q.size());
835 EXPECT_EQ(0, q[0].data());
836 EXPECT_EQ(1, q[1].data());
837 EXPECT_EQ(2, q[2].data());
838 EXPECT_EQ(3, q[3].data());
839 EXPECT_EQ(4, q[4].data());
840 }
841
TEST(CircularDeque,EmplaceFrontBackReturnsReference)842 TEST(CircularDeque, EmplaceFrontBackReturnsReference) {
843 circular_deque<int> q;
844 q.reserve(2);
845
846 int& front = q.emplace_front(1);
847 int& back = q.emplace_back(2);
848 ASSERT_EQ(2u, q.size());
849 EXPECT_EQ(1, q[0]);
850 EXPECT_EQ(2, q[1]);
851
852 EXPECT_EQ(&front, &q.front());
853 EXPECT_EQ(&back, &q.back());
854
855 front = 3;
856 back = 4;
857
858 ASSERT_EQ(2u, q.size());
859 EXPECT_EQ(3, q[0]);
860 EXPECT_EQ(4, q[1]);
861
862 EXPECT_EQ(&front, &q.front());
863 EXPECT_EQ(&back, &q.back());
864 }
865
866 /*
867 This test should assert in a debug build. It tries to dereference an iterator
868 after mutating the container. Uncomment to double-check that this works.
869 TEST(CircularDeque, UseIteratorAfterMutate) {
870 circular_deque<int> q;
871 q.push_back(0);
872
873 auto old_begin = q.begin();
874 EXPECT_EQ(0, *old_begin);
875
876 q.push_back(1);
877 EXPECT_EQ(0, *old_begin); // Should DCHECK.
878 }
879 */
880
881 } // namespace base
882