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