1 // Copyright (c) 2019 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 "quiche/common/quiche_circular_deque.h"
6
7 #include <cstddef>
8 #include <cstdint>
9 #include <list>
10 #include <memory>
11 #include <type_traits>
12
13 #include "quiche/common/platform/api/quiche_logging.h"
14 #include "quiche/common/platform/api/quiche_test.h"
15
16 using testing::ElementsAre;
17
18 namespace quiche {
19 namespace test {
20 namespace {
21
22 template <typename T, template <typename> class BaseAllocator = std::allocator>
23 class CountingAllocator : public BaseAllocator<T> {
24 using BaseType = BaseAllocator<T>;
25
26 public:
27 using propagate_on_container_copy_assignment = std::true_type;
28 using propagate_on_container_move_assignment = std::true_type;
29 using propagate_on_container_swap = std::true_type;
30
allocate(std::size_t n)31 T* allocate(std::size_t n) {
32 ++shared_counts_->allocate_count;
33 return BaseType::allocate(n);
34 }
35
deallocate(T * ptr,std::size_t n)36 void deallocate(T* ptr, std::size_t n) {
37 ++shared_counts_->deallocate_count;
38 return BaseType::deallocate(ptr, n);
39 }
40
allocate_count() const41 size_t allocate_count() const { return shared_counts_->allocate_count; }
42
deallocate_count() const43 size_t deallocate_count() const { return shared_counts_->deallocate_count; }
44
operator ==(const CountingAllocator & lhs,const CountingAllocator & rhs)45 friend bool operator==(const CountingAllocator& lhs,
46 const CountingAllocator& rhs) {
47 return lhs.shared_counts_ == rhs.shared_counts_;
48 }
49
operator !=(const CountingAllocator & lhs,const CountingAllocator & rhs)50 friend bool operator!=(const CountingAllocator& lhs,
51 const CountingAllocator& rhs) {
52 return !(lhs == rhs);
53 }
54
55 private:
56 struct Counts {
57 size_t allocate_count = 0;
58 size_t deallocate_count = 0;
59 };
60
61 std::shared_ptr<Counts> shared_counts_ = std::make_shared<Counts>();
62 };
63
64 template <typename T, typename propagate_on_copy_assignment,
65 typename propagate_on_move_assignment, typename propagate_on_swap,
66 bool equality_result,
67 template <typename> class BaseAllocator = std::allocator>
68 struct ConfigurableAllocator : public BaseAllocator<T> {
69 using propagate_on_container_copy_assignment = propagate_on_copy_assignment;
70 using propagate_on_container_move_assignment = propagate_on_move_assignment;
71 using propagate_on_container_swap = propagate_on_swap;
72
operator ==(const ConfigurableAllocator &,const ConfigurableAllocator &)73 friend bool operator==(const ConfigurableAllocator& /*lhs*/,
74 const ConfigurableAllocator& /*rhs*/) {
75 return equality_result;
76 }
77
operator !=(const ConfigurableAllocator & lhs,const ConfigurableAllocator & rhs)78 friend bool operator!=(const ConfigurableAllocator& lhs,
79 const ConfigurableAllocator& rhs) {
80 return !(lhs == rhs);
81 }
82 };
83
84 // [1, 2, 3, 4] ==> [4, 1, 2, 3]
85 template <typename Deque>
ShiftRight(Deque * dq,bool emplace)86 void ShiftRight(Deque* dq, bool emplace) {
87 auto back = *(&dq->back());
88 dq->pop_back();
89 if (emplace) {
90 dq->emplace_front(back);
91 } else {
92 dq->push_front(back);
93 }
94 }
95
96 // [1, 2, 3, 4] ==> [2, 3, 4, 1]
97 template <typename Deque>
ShiftLeft(Deque * dq,bool emplace)98 void ShiftLeft(Deque* dq, bool emplace) {
99 auto front = *(&dq->front());
100 dq->pop_front();
101 if (emplace) {
102 dq->emplace_back(front);
103 } else {
104 dq->push_back(front);
105 }
106 }
107
108 class QuicheCircularDequeTest : public QuicheTest {};
109
TEST_F(QuicheCircularDequeTest,Empty)110 TEST_F(QuicheCircularDequeTest, Empty) {
111 QuicheCircularDeque<int> dq;
112 EXPECT_TRUE(dq.empty());
113 EXPECT_EQ(0u, dq.size());
114 dq.clear();
115 dq.push_back(10);
116 EXPECT_FALSE(dq.empty());
117 EXPECT_EQ(1u, dq.size());
118 EXPECT_EQ(10, dq.front());
119 EXPECT_EQ(10, dq.back());
120 dq.pop_front();
121 EXPECT_TRUE(dq.empty());
122 EXPECT_EQ(0u, dq.size());
123
124 EXPECT_QUICHE_DEBUG_DEATH(dq.front(), "");
125 EXPECT_QUICHE_DEBUG_DEATH(dq.back(), "");
126 EXPECT_QUICHE_DEBUG_DEATH(dq.at(0), "");
127 EXPECT_QUICHE_DEBUG_DEATH(dq[0], "");
128 }
129
TEST_F(QuicheCircularDequeTest,Constructor)130 TEST_F(QuicheCircularDequeTest, Constructor) {
131 QuicheCircularDeque<int> dq;
132 EXPECT_TRUE(dq.empty());
133
134 std::allocator<int> alloc;
135 QuicheCircularDeque<int> dq1(alloc);
136 EXPECT_TRUE(dq1.empty());
137
138 QuicheCircularDeque<int> dq2(8, 100, alloc);
139 EXPECT_THAT(dq2, ElementsAre(100, 100, 100, 100, 100, 100, 100, 100));
140
141 QuicheCircularDeque<int> dq3(5, alloc);
142 EXPECT_THAT(dq3, ElementsAre(0, 0, 0, 0, 0));
143
144 QuicheCircularDeque<int> dq4_rand_iter(dq3.begin(), dq3.end(), alloc);
145 EXPECT_THAT(dq4_rand_iter, ElementsAre(0, 0, 0, 0, 0));
146 EXPECT_EQ(dq4_rand_iter, dq3);
147
148 std::list<int> dq4_src = {4, 4, 4, 4};
149 QuicheCircularDeque<int> dq4_bidi_iter(dq4_src.begin(), dq4_src.end());
150 EXPECT_THAT(dq4_bidi_iter, ElementsAre(4, 4, 4, 4));
151
152 QuicheCircularDeque<int> dq5(dq4_bidi_iter);
153 EXPECT_THAT(dq5, ElementsAre(4, 4, 4, 4));
154 EXPECT_EQ(dq5, dq4_bidi_iter);
155
156 QuicheCircularDeque<int> dq6(dq5, alloc);
157 EXPECT_THAT(dq6, ElementsAre(4, 4, 4, 4));
158 EXPECT_EQ(dq6, dq5);
159
160 QuicheCircularDeque<int> dq7(std::move(*&dq6));
161 EXPECT_THAT(dq7, ElementsAre(4, 4, 4, 4));
162 EXPECT_TRUE(dq6.empty());
163
164 QuicheCircularDeque<int> dq8_equal_allocator(std::move(*&dq7), alloc);
165 EXPECT_THAT(dq8_equal_allocator, ElementsAre(4, 4, 4, 4));
166 EXPECT_TRUE(dq7.empty());
167
168 QuicheCircularDeque<int, 3, CountingAllocator<int>> dq8_temp = {5, 6, 7, 8,
169 9};
170 QuicheCircularDeque<int, 3, CountingAllocator<int>> dq8_unequal_allocator(
171 std::move(*&dq8_temp), CountingAllocator<int>());
172 EXPECT_THAT(dq8_unequal_allocator, ElementsAre(5, 6, 7, 8, 9));
173 EXPECT_TRUE(dq8_temp.empty());
174
175 QuicheCircularDeque<int> dq9({3, 4, 5, 6, 7}, alloc);
176 EXPECT_THAT(dq9, ElementsAre(3, 4, 5, 6, 7));
177 }
178
TEST_F(QuicheCircularDequeTest,Assign)179 TEST_F(QuicheCircularDequeTest, Assign) {
180 // assign()
181 QuicheCircularDeque<int, 3, CountingAllocator<int>> dq;
182 dq.assign(7, 1);
183 EXPECT_THAT(dq, ElementsAre(1, 1, 1, 1, 1, 1, 1));
184 EXPECT_EQ(1u, dq.get_allocator().allocate_count());
185
186 QuicheCircularDeque<int, 3, CountingAllocator<int>> dq2;
187 dq2.assign(dq.begin(), dq.end());
188 EXPECT_THAT(dq2, ElementsAre(1, 1, 1, 1, 1, 1, 1));
189 EXPECT_EQ(1u, dq2.get_allocator().allocate_count());
190 EXPECT_TRUE(std::equal(dq.begin(), dq.end(), dq2.begin(), dq2.end()));
191
192 dq2.assign({2, 2, 2, 2, 2, 2});
193 EXPECT_THAT(dq2, ElementsAre(2, 2, 2, 2, 2, 2));
194
195 // Assign from a non random access iterator.
196 std::list<int> dq3_src = {3, 3, 3, 3, 3};
197 QuicheCircularDeque<int, 3, CountingAllocator<int>> dq3;
198 dq3.assign(dq3_src.begin(), dq3_src.end());
199 EXPECT_THAT(dq3, ElementsAre(3, 3, 3, 3, 3));
200 EXPECT_LT(1u, dq3.get_allocator().allocate_count());
201
202 // Copy assignment
203 dq3 = *&dq3;
204 EXPECT_THAT(dq3, ElementsAre(3, 3, 3, 3, 3));
205
206 QuicheCircularDeque<
207 int, 3,
208 ConfigurableAllocator<int,
209 /*propagate_on_copy_assignment=*/std::true_type,
210 /*propagate_on_move_assignment=*/std::true_type,
211 /*propagate_on_swap=*/std::true_type,
212 /*equality_result=*/false>>
213 dq4, dq5;
214 dq4.assign(dq3.begin(), dq3.end());
215 dq5 = dq4;
216 EXPECT_THAT(dq5, ElementsAre(3, 3, 3, 3, 3));
217
218 QuicheCircularDeque<
219 int, 3,
220 ConfigurableAllocator<int,
221 /*propagate_on_copy_assignment=*/std::false_type,
222 /*propagate_on_move_assignment=*/std::true_type,
223 /*propagate_on_swap=*/std::true_type,
224 /*equality_result=*/true>>
225 dq6, dq7;
226 dq6.assign(dq3.begin(), dq3.end());
227 dq7 = dq6;
228 EXPECT_THAT(dq7, ElementsAre(3, 3, 3, 3, 3));
229
230 // Move assignment
231 dq3 = std::move(*&dq3);
232 EXPECT_THAT(dq3, ElementsAre(3, 3, 3, 3, 3));
233
234 ASSERT_TRUE(decltype(dq3.get_allocator())::
235 propagate_on_container_move_assignment::value);
236 decltype(dq3) dq8;
237 dq8 = std::move(*&dq3);
238 EXPECT_THAT(dq8, ElementsAre(3, 3, 3, 3, 3));
239 EXPECT_TRUE(dq3.empty());
240
241 QuicheCircularDeque<
242 int, 3,
243 ConfigurableAllocator<int,
244 /*propagate_on_copy_assignment=*/std::true_type,
245 /*propagate_on_move_assignment=*/std::false_type,
246 /*propagate_on_swap=*/std::true_type,
247 /*equality_result=*/true>>
248 dq9, dq10;
249 dq9.assign(dq8.begin(), dq8.end());
250 dq10.assign(dq2.begin(), dq2.end());
251 dq9 = std::move(*&dq10);
252 EXPECT_THAT(dq9, ElementsAre(2, 2, 2, 2, 2, 2));
253 EXPECT_TRUE(dq10.empty());
254
255 QuicheCircularDeque<
256 int, 3,
257 ConfigurableAllocator<int,
258 /*propagate_on_copy_assignment=*/std::true_type,
259 /*propagate_on_move_assignment=*/std::false_type,
260 /*propagate_on_swap=*/std::true_type,
261 /*equality_result=*/false>>
262 dq11, dq12;
263 dq11.assign(dq8.begin(), dq8.end());
264 dq12.assign(dq2.begin(), dq2.end());
265 dq11 = std::move(*&dq12);
266 EXPECT_THAT(dq11, ElementsAre(2, 2, 2, 2, 2, 2));
267 EXPECT_TRUE(dq12.empty());
268 }
269
TEST_F(QuicheCircularDequeTest,Access)270 TEST_F(QuicheCircularDequeTest, Access) {
271 // at()
272 // operator[]
273 // front()
274 // back()
275
276 QuicheCircularDeque<int, 3, CountingAllocator<int>> dq;
277 dq.push_back(10);
278 EXPECT_EQ(dq.front(), 10);
279 EXPECT_EQ(dq.back(), 10);
280 EXPECT_EQ(dq.at(0), 10);
281 EXPECT_EQ(dq[0], 10);
282 dq.front() = 12;
283 EXPECT_EQ(dq.front(), 12);
284 EXPECT_EQ(dq.back(), 12);
285 EXPECT_EQ(dq.at(0), 12);
286 EXPECT_EQ(dq[0], 12);
287
288 const auto& dqref = dq;
289 EXPECT_EQ(dqref.front(), 12);
290 EXPECT_EQ(dqref.back(), 12);
291 EXPECT_EQ(dqref.at(0), 12);
292 EXPECT_EQ(dqref[0], 12);
293
294 dq.pop_front();
295 EXPECT_TRUE(dqref.empty());
296
297 // Push to capacity.
298 dq.push_back(15);
299 dq.push_front(5);
300 dq.push_back(25);
301 EXPECT_EQ(dq.size(), dq.capacity());
302 EXPECT_THAT(dq, ElementsAre(5, 15, 25));
303 EXPECT_LT(&dq.front(), &dq.back());
304 EXPECT_EQ(dq.front(), 5);
305 EXPECT_EQ(dq.back(), 25);
306 EXPECT_EQ(dq.at(0), 5);
307 EXPECT_EQ(dq.at(1), 15);
308 EXPECT_EQ(dq.at(2), 25);
309 EXPECT_EQ(dq[0], 5);
310 EXPECT_EQ(dq[1], 15);
311 EXPECT_EQ(dq[2], 25);
312
313 // Shift right such that begin=1 and end=0. Data is still not wrapped.
314 dq.pop_front();
315 dq.push_back(35);
316 EXPECT_THAT(dq, ElementsAre(15, 25, 35));
317 EXPECT_LT(&dq.front(), &dq.back());
318 EXPECT_EQ(dq.front(), 15);
319 EXPECT_EQ(dq.back(), 35);
320 EXPECT_EQ(dq.at(0), 15);
321 EXPECT_EQ(dq.at(1), 25);
322 EXPECT_EQ(dq.at(2), 35);
323 EXPECT_EQ(dq[0], 15);
324 EXPECT_EQ(dq[1], 25);
325 EXPECT_EQ(dq[2], 35);
326
327 // Shift right such that data is wrapped.
328 dq.pop_front();
329 dq.push_back(45);
330 EXPECT_THAT(dq, ElementsAre(25, 35, 45));
331 EXPECT_GT(&dq.front(), &dq.back());
332 EXPECT_EQ(dq.front(), 25);
333 EXPECT_EQ(dq.back(), 45);
334 EXPECT_EQ(dq.at(0), 25);
335 EXPECT_EQ(dq.at(1), 35);
336 EXPECT_EQ(dq.at(2), 45);
337 EXPECT_EQ(dq[0], 25);
338 EXPECT_EQ(dq[1], 35);
339 EXPECT_EQ(dq[2], 45);
340
341 // Shift right again, data is still wrapped.
342 dq.pop_front();
343 dq.push_back(55);
344 EXPECT_THAT(dq, ElementsAre(35, 45, 55));
345 EXPECT_GT(&dq.front(), &dq.back());
346 EXPECT_EQ(dq.front(), 35);
347 EXPECT_EQ(dq.back(), 55);
348 EXPECT_EQ(dq.at(0), 35);
349 EXPECT_EQ(dq.at(1), 45);
350 EXPECT_EQ(dq.at(2), 55);
351 EXPECT_EQ(dq[0], 35);
352 EXPECT_EQ(dq[1], 45);
353 EXPECT_EQ(dq[2], 55);
354
355 // Shift right one last time. begin returns to 0. Data is no longer wrapped.
356 dq.pop_front();
357 dq.push_back(65);
358 EXPECT_THAT(dq, ElementsAre(45, 55, 65));
359 EXPECT_LT(&dq.front(), &dq.back());
360 EXPECT_EQ(dq.front(), 45);
361 EXPECT_EQ(dq.back(), 65);
362 EXPECT_EQ(dq.at(0), 45);
363 EXPECT_EQ(dq.at(1), 55);
364 EXPECT_EQ(dq.at(2), 65);
365 EXPECT_EQ(dq[0], 45);
366 EXPECT_EQ(dq[1], 55);
367 EXPECT_EQ(dq[2], 65);
368
369 EXPECT_EQ(1u, dq.get_allocator().allocate_count());
370 }
371
TEST_F(QuicheCircularDequeTest,Iterate)372 TEST_F(QuicheCircularDequeTest, Iterate) {
373 QuicheCircularDeque<int> dq;
374 EXPECT_EQ(dq.begin(), dq.end());
375 EXPECT_EQ(dq.cbegin(), dq.cend());
376 EXPECT_EQ(dq.rbegin(), dq.rend());
377 EXPECT_EQ(dq.crbegin(), dq.crend());
378
379 dq.emplace_back(2);
380 QuicheCircularDeque<int>::const_iterator citer = dq.begin();
381 EXPECT_NE(citer, dq.end());
382 EXPECT_EQ(*citer, 2);
383 ++citer;
384 EXPECT_EQ(citer, dq.end());
385
386 EXPECT_EQ(*dq.begin(), 2);
387 EXPECT_EQ(*dq.cbegin(), 2);
388 EXPECT_EQ(*dq.rbegin(), 2);
389 EXPECT_EQ(*dq.crbegin(), 2);
390
391 dq.emplace_front(1);
392 QuicheCircularDeque<int>::const_reverse_iterator criter = dq.rbegin();
393 EXPECT_NE(criter, dq.rend());
394 EXPECT_EQ(*criter, 2);
395 ++criter;
396 EXPECT_NE(criter, dq.rend());
397 EXPECT_EQ(*criter, 1);
398 ++criter;
399 EXPECT_EQ(criter, dq.rend());
400
401 EXPECT_EQ(*dq.begin(), 1);
402 EXPECT_EQ(*dq.cbegin(), 1);
403 EXPECT_EQ(*dq.rbegin(), 2);
404 EXPECT_EQ(*dq.crbegin(), 2);
405
406 dq.push_back(3);
407
408 // Forward iterate.
409 int expected_value = 1;
410 for (QuicheCircularDeque<int>::iterator it = dq.begin(); it != dq.end();
411 ++it) {
412 EXPECT_EQ(expected_value++, *it);
413 }
414
415 expected_value = 1;
416 for (QuicheCircularDeque<int>::const_iterator it = dq.cbegin();
417 it != dq.cend(); ++it) {
418 EXPECT_EQ(expected_value++, *it);
419 }
420
421 // Reverse iterate.
422 expected_value = 3;
423 for (QuicheCircularDeque<int>::reverse_iterator it = dq.rbegin();
424 it != dq.rend(); ++it) {
425 EXPECT_EQ(expected_value--, *it);
426 }
427
428 expected_value = 3;
429 for (QuicheCircularDeque<int>::const_reverse_iterator it = dq.crbegin();
430 it != dq.crend(); ++it) {
431 EXPECT_EQ(expected_value--, *it);
432 }
433 }
434
TEST_F(QuicheCircularDequeTest,Iterator)435 TEST_F(QuicheCircularDequeTest, Iterator) {
436 // Default constructed iterators of the same type compare equal.
437 EXPECT_EQ(QuicheCircularDeque<int>::iterator(),
438 QuicheCircularDeque<int>::iterator());
439 EXPECT_EQ(QuicheCircularDeque<int>::const_iterator(),
440 QuicheCircularDeque<int>::const_iterator());
441 EXPECT_EQ(QuicheCircularDeque<int>::reverse_iterator(),
442 QuicheCircularDeque<int>::reverse_iterator());
443 EXPECT_EQ(QuicheCircularDeque<int>::const_reverse_iterator(),
444 QuicheCircularDeque<int>::const_reverse_iterator());
445
446 QuicheCircularDeque<QuicheCircularDeque<int>, 3> dqdq = {
447 {1, 2}, {10, 20, 30}, {100, 200, 300, 400}};
448
449 // iter points to {1, 2}
450 decltype(dqdq)::iterator iter = dqdq.begin();
451 EXPECT_EQ(iter->size(), 2u);
452 EXPECT_THAT(*iter, ElementsAre(1, 2));
453
454 // citer points to {10, 20, 30}
455 decltype(dqdq)::const_iterator citer = dqdq.cbegin() + 1;
456 EXPECT_NE(*iter, *citer);
457 EXPECT_EQ(citer->size(), 3u);
458 int x = 10;
459 for (auto it = citer->begin(); it != citer->end(); ++it) {
460 EXPECT_EQ(*it, x);
461 x += 10;
462 }
463
464 EXPECT_LT(iter, citer);
465 EXPECT_LE(iter, iter);
466 EXPECT_GT(citer, iter);
467 EXPECT_GE(citer, citer);
468
469 // iter points to {100, 200, 300, 400}
470 iter += 2;
471 EXPECT_NE(*iter, *citer);
472 EXPECT_EQ(iter->size(), 4u);
473 for (int i = 1; i <= 4; ++i) {
474 EXPECT_EQ(iter->begin()[i - 1], i * 100);
475 }
476
477 EXPECT_LT(citer, iter);
478 EXPECT_LE(iter, iter);
479 EXPECT_GT(iter, citer);
480 EXPECT_GE(citer, citer);
481
482 // iter points to {10, 20, 30}. (same as citer)
483 iter -= 1;
484 EXPECT_EQ(*iter, *citer);
485 EXPECT_EQ(iter->size(), 3u);
486 x = 10;
487 for (auto it = iter->begin(); it != iter->end();) {
488 EXPECT_EQ(*(it++), x);
489 x += 10;
490 }
491 x = 30;
492 for (auto it = iter->begin() + 2; it != iter->begin();) {
493 EXPECT_EQ(*(it--), x);
494 x -= 10;
495 }
496 }
497
TEST_F(QuicheCircularDequeTest,Resize)498 TEST_F(QuicheCircularDequeTest, Resize) {
499 QuicheCircularDeque<int, 3, CountingAllocator<int>> dq;
500 dq.resize(8);
501 EXPECT_THAT(dq, ElementsAre(0, 0, 0, 0, 0, 0, 0, 0));
502 EXPECT_EQ(1u, dq.get_allocator().allocate_count());
503
504 dq.resize(10, 5);
505 EXPECT_THAT(dq, ElementsAre(0, 0, 0, 0, 0, 0, 0, 0, 5, 5));
506
507 QuicheCircularDeque<int, 3, CountingAllocator<int>> dq2 = dq;
508
509 for (size_t new_size = dq.size(); new_size != 0; --new_size) {
510 dq.resize(new_size);
511 EXPECT_TRUE(
512 std::equal(dq.begin(), dq.end(), dq2.begin(), dq2.begin() + new_size));
513 }
514
515 dq.resize(0);
516 EXPECT_TRUE(dq.empty());
517
518 // Resize when data is wrapped.
519 ASSERT_EQ(dq2.size(), dq2.capacity());
520 while (dq2.size() < dq2.capacity()) {
521 dq2.push_back(5);
522 }
523
524 // Shift left once such that data is wrapped.
525 ASSERT_LT(&dq2.front(), &dq2.back());
526 dq2.pop_back();
527 dq2.push_front(-5);
528 ASSERT_GT(&dq2.front(), &dq2.back());
529
530 EXPECT_EQ(-5, dq2.front());
531 EXPECT_EQ(5, dq2.back());
532 dq2.resize(dq2.size() + 1, 10);
533
534 // Data should be unwrapped after the resize.
535 ASSERT_LT(&dq2.front(), &dq2.back());
536 EXPECT_EQ(-5, dq2.front());
537 EXPECT_EQ(10, dq2.back());
538 EXPECT_EQ(5, *(dq2.rbegin() + 1));
539 }
540
541 namespace {
542 class Foo {
543 public:
Foo()544 Foo() : Foo(0xF00) {}
545
Foo(int i)546 explicit Foo(int i) : i_(new int(i)) {}
547
~Foo()548 ~Foo() {
549 if (i_ != nullptr) {
550 delete i_;
551 // Do not set i_ to nullptr such that if the container calls destructor
552 // multiple times, asan can detect it.
553 }
554 }
555
Foo(const Foo & other)556 Foo(const Foo& other) : i_(new int(*other.i_)) {}
557
558 Foo(Foo&& other) = delete;
559
Set(int i)560 void Set(int i) { *i_ = i; }
561
i() const562 int i() const { return *i_; }
563
operator ==(const Foo & lhs,const Foo & rhs)564 friend bool operator==(const Foo& lhs, const Foo& rhs) {
565 return lhs.i() == rhs.i();
566 }
567
operator <<(std::ostream & os,const Foo & foo)568 friend std::ostream& operator<<(std::ostream& os, const Foo& foo) {
569 return os << "Foo(" << foo.i() << ")";
570 }
571
572 private:
573 // By pointing i_ to a dynamically allocated integer, a memory leak will be
574 // reported if the container forget to properly destruct this object.
575 int* i_ = nullptr;
576 };
577 } // namespace
578
TEST_F(QuicheCircularDequeTest,RelocateNonTriviallyCopyable)579 TEST_F(QuicheCircularDequeTest, RelocateNonTriviallyCopyable) {
580 // When relocating non-trivially-copyable objects:
581 // - Move constructor is preferred, if available.
582 // - Copy constructor is used otherwise.
583
584 {
585 // Move construct in Relocate.
586 using MoveConstructible = std::unique_ptr<Foo>;
587 ASSERT_FALSE(std::is_trivially_copyable<MoveConstructible>::value);
588 ASSERT_TRUE(std::is_move_constructible<MoveConstructible>::value);
589 QuicheCircularDeque<MoveConstructible, 3,
590 CountingAllocator<MoveConstructible>>
591 dq1;
592 dq1.resize(3);
593 EXPECT_EQ(dq1.size(), dq1.capacity());
594 EXPECT_EQ(1u, dq1.get_allocator().allocate_count());
595
596 dq1.emplace_back(new Foo(0xF1)); // Cause existing elements to relocate.
597 EXPECT_EQ(4u, dq1.size());
598 EXPECT_EQ(2u, dq1.get_allocator().allocate_count());
599 EXPECT_EQ(dq1[0], nullptr);
600 EXPECT_EQ(dq1[1], nullptr);
601 EXPECT_EQ(dq1[2], nullptr);
602 EXPECT_EQ(dq1[3]->i(), 0xF1);
603 }
604
605 {
606 // Copy construct in Relocate.
607 using NonMoveConstructible = Foo;
608 ASSERT_FALSE(std::is_trivially_copyable<NonMoveConstructible>::value);
609 ASSERT_FALSE(std::is_move_constructible<NonMoveConstructible>::value);
610 QuicheCircularDeque<NonMoveConstructible, 3,
611 CountingAllocator<NonMoveConstructible>>
612 dq2;
613 dq2.resize(3);
614 EXPECT_EQ(dq2.size(), dq2.capacity());
615 EXPECT_EQ(1u, dq2.get_allocator().allocate_count());
616
617 dq2.emplace_back(0xF1); // Cause existing elements to relocate.
618 EXPECT_EQ(4u, dq2.size());
619 EXPECT_EQ(2u, dq2.get_allocator().allocate_count());
620 EXPECT_EQ(dq2[0].i(), 0xF00);
621 EXPECT_EQ(dq2[1].i(), 0xF00);
622 EXPECT_EQ(dq2[2].i(), 0xF00);
623 EXPECT_EQ(dq2[3].i(), 0xF1);
624 }
625 }
626
TEST_F(QuicheCircularDequeTest,PushPop)627 TEST_F(QuicheCircularDequeTest, PushPop) {
628 // (push|pop|emplace)_(back|front)
629
630 {
631 QuicheCircularDeque<Foo, 4, CountingAllocator<Foo>> dq(4);
632 for (size_t i = 0; i < dq.size(); ++i) {
633 dq[i].Set(i + 1);
634 }
635 QUICHE_LOG(INFO) << "dq initialized to " << dq;
636 EXPECT_THAT(dq, ElementsAre(Foo(1), Foo(2), Foo(3), Foo(4)));
637
638 ShiftLeft(&dq, false);
639 QUICHE_LOG(INFO) << "shift left once : " << dq;
640 EXPECT_THAT(dq, ElementsAre(Foo(2), Foo(3), Foo(4), Foo(1)));
641
642 ShiftLeft(&dq, true);
643 QUICHE_LOG(INFO) << "shift left twice: " << dq;
644 EXPECT_THAT(dq, ElementsAre(Foo(3), Foo(4), Foo(1), Foo(2)));
645 ASSERT_GT(&dq.front(), &dq.back());
646 // dq destructs with wrapped data.
647 }
648
649 {
650 QuicheCircularDeque<Foo, 4, CountingAllocator<Foo>> dq1(4);
651 for (size_t i = 0; i < dq1.size(); ++i) {
652 dq1[i].Set(i + 1);
653 }
654 QUICHE_LOG(INFO) << "dq1 initialized to " << dq1;
655 EXPECT_THAT(dq1, ElementsAre(Foo(1), Foo(2), Foo(3), Foo(4)));
656
657 ShiftRight(&dq1, false);
658 QUICHE_LOG(INFO) << "shift right once : " << dq1;
659 EXPECT_THAT(dq1, ElementsAre(Foo(4), Foo(1), Foo(2), Foo(3)));
660
661 ShiftRight(&dq1, true);
662 QUICHE_LOG(INFO) << "shift right twice: " << dq1;
663 EXPECT_THAT(dq1, ElementsAre(Foo(3), Foo(4), Foo(1), Foo(2)));
664 ASSERT_GT(&dq1.front(), &dq1.back());
665 // dq1 destructs with wrapped data.
666 }
667
668 { // Pop n elements from front.
669 QuicheCircularDeque<Foo, 4, CountingAllocator<Foo>> dq2(5);
670 for (size_t i = 0; i < dq2.size(); ++i) {
671 dq2[i].Set(i + 1);
672 }
673 EXPECT_THAT(dq2, ElementsAre(Foo(1), Foo(2), Foo(3), Foo(4), Foo(5)));
674
675 EXPECT_EQ(2u, dq2.pop_front_n(2));
676 EXPECT_THAT(dq2, ElementsAre(Foo(3), Foo(4), Foo(5)));
677
678 EXPECT_EQ(3u, dq2.pop_front_n(100));
679 EXPECT_TRUE(dq2.empty());
680 }
681
682 { // Pop n elements from back.
683 QuicheCircularDeque<Foo, 4, CountingAllocator<Foo>> dq3(6);
684 for (size_t i = 0; i < dq3.size(); ++i) {
685 dq3[i].Set(i + 1);
686 }
687 EXPECT_THAT(dq3,
688 ElementsAre(Foo(1), Foo(2), Foo(3), Foo(4), Foo(5), Foo(6)));
689
690 ShiftRight(&dq3, true);
691 ShiftRight(&dq3, true);
692 ShiftRight(&dq3, true);
693 EXPECT_THAT(dq3,
694 ElementsAre(Foo(4), Foo(5), Foo(6), Foo(1), Foo(2), Foo(3)));
695
696 EXPECT_EQ(2u, dq3.pop_back_n(2));
697 EXPECT_THAT(dq3, ElementsAre(Foo(4), Foo(5), Foo(6), Foo(1)));
698
699 EXPECT_EQ(2u, dq3.pop_back_n(2));
700 EXPECT_THAT(dq3, ElementsAre(Foo(4), Foo(5)));
701 }
702 }
703
TEST_F(QuicheCircularDequeTest,Allocation)704 TEST_F(QuicheCircularDequeTest, Allocation) {
705 CountingAllocator<int> alloc;
706
707 {
708 QuicheCircularDeque<int, 3, CountingAllocator<int>> dq(alloc);
709 EXPECT_EQ(alloc, dq.get_allocator());
710 EXPECT_EQ(0u, dq.size());
711 EXPECT_EQ(0u, dq.capacity());
712 EXPECT_EQ(0u, alloc.allocate_count());
713 EXPECT_EQ(0u, alloc.deallocate_count());
714
715 for (int i = 1; i <= 18; ++i) {
716 SCOPED_TRACE(testing::Message()
717 << "i=" << i << ", capacity_b4_push=" << dq.capacity());
718 dq.push_back(i);
719 EXPECT_EQ(i, static_cast<int>(dq.size()));
720
721 const size_t capacity = 3 + (i - 1) / 3 * 3;
722 EXPECT_EQ(capacity, dq.capacity());
723 EXPECT_EQ(capacity / 3, alloc.allocate_count());
724 EXPECT_EQ(capacity / 3 - 1, alloc.deallocate_count());
725 }
726
727 dq.push_back(19);
728 EXPECT_EQ(22u, dq.capacity()); // 18 + 18 / 4
729 EXPECT_EQ(7u, alloc.allocate_count());
730 EXPECT_EQ(6u, alloc.deallocate_count());
731 }
732
733 EXPECT_EQ(7u, alloc.deallocate_count());
734 }
735
736 } // namespace
737 } // namespace test
738 } // namespace quiche
739
740 // Use a non-quiche namespace to make sure swap can be used via ADL.
741 namespace {
742
743 template <typename T>
744 using SwappableAllocator = quiche::test::ConfigurableAllocator<
745 T,
746 /*propagate_on_copy_assignment=*/std::true_type,
747 /*propagate_on_move_assignment=*/std::true_type,
748 /*propagate_on_swap=*/std::true_type,
749 /*equality_result=*/true>;
750
751 template <typename T>
752 using UnswappableEqualAllocator = quiche::test::ConfigurableAllocator<
753 T,
754 /*propagate_on_copy_assignment=*/std::true_type,
755 /*propagate_on_move_assignment=*/std::true_type,
756 /*propagate_on_swap=*/std::false_type,
757 /*equality_result=*/true>;
758
759 template <typename T>
760 using UnswappableUnequalAllocator = quiche::test::ConfigurableAllocator<
761 T,
762 /*propagate_on_copy_assignment=*/std::true_type,
763 /*propagate_on_move_assignment=*/std::true_type,
764 /*propagate_on_swap=*/std::false_type,
765 /*equality_result=*/false>;
766
767 using quiche::test::QuicheCircularDequeTest;
768
TEST_F(QuicheCircularDequeTest,Swap)769 TEST_F(QuicheCircularDequeTest, Swap) {
770 using std::swap;
771
772 quiche::QuicheCircularDeque<int64_t, 3, SwappableAllocator<int64_t>> dq1, dq2;
773 dq1.push_back(10);
774 dq1.push_back(11);
775 dq2.push_back(20);
776 swap(dq1, dq2);
777 EXPECT_THAT(dq1, ElementsAre(20));
778 EXPECT_THAT(dq2, ElementsAre(10, 11));
779
780 quiche::QuicheCircularDeque<char, 3, UnswappableEqualAllocator<char>> dq3,
781 dq4;
782 dq3 = {1, 2, 3, 4, 5};
783 dq4 = {6, 7, 8, 9, 0};
784 swap(dq3, dq4);
785 EXPECT_THAT(dq3, ElementsAre(6, 7, 8, 9, 0));
786 EXPECT_THAT(dq4, ElementsAre(1, 2, 3, 4, 5));
787
788 quiche::QuicheCircularDeque<int, 3, UnswappableUnequalAllocator<int>> dq5,
789 dq6;
790 dq6.push_front(4);
791
792 // Using UnswappableUnequalAllocator is ok as long as swap is not called.
793 dq5.assign(dq6.begin(), dq6.end());
794 EXPECT_THAT(dq5, ElementsAre(4));
795
796 // Undefined behavior to swap between two containers with unequal allocators.
797 EXPECT_QUICHE_DEBUG_DEATH(swap(dq5, dq6), "Undefined swap behavior");
798 }
799 } // namespace
800