1 // Copyright 2018 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/task/sequence_manager/lazily_deallocated_deque.h"
6
7 #include "base/test/scoped_mock_clock_override.h"
8 #include "testing/gmock/include/gmock/gmock.h"
9
10 namespace base {
11 namespace sequence_manager {
12 namespace internal {
13
14 class LazilyDeallocatedDequeTest : public testing::Test {};
15
TEST_F(LazilyDeallocatedDequeTest,InitiallyEmpty)16 TEST_F(LazilyDeallocatedDequeTest, InitiallyEmpty) {
17 LazilyDeallocatedDeque<int> d;
18
19 EXPECT_TRUE(d.empty());
20 EXPECT_EQ(0u, d.size());
21 }
22
TEST_F(LazilyDeallocatedDequeTest,PushBackAndPopFront1)23 TEST_F(LazilyDeallocatedDequeTest, PushBackAndPopFront1) {
24 LazilyDeallocatedDeque<int> d;
25
26 d.push_back(123);
27
28 EXPECT_FALSE(d.empty());
29 EXPECT_EQ(1u, d.size());
30
31 EXPECT_EQ(123, d.front());
32
33 d.pop_front();
34 EXPECT_TRUE(d.empty());
35 EXPECT_EQ(0u, d.size());
36 }
37
TEST_F(LazilyDeallocatedDequeTest,PushBackAndPopFront1000)38 TEST_F(LazilyDeallocatedDequeTest, PushBackAndPopFront1000) {
39 LazilyDeallocatedDeque<int> d;
40
41 for (int i = 0; i < 1000; i++) {
42 d.push_back(i);
43 }
44
45 EXPECT_EQ(0, d.front());
46 EXPECT_EQ(999, d.back());
47 EXPECT_EQ(1000u, d.size());
48
49 for (int i = 0; i < 1000; i++) {
50 EXPECT_EQ(i, d.front());
51 d.pop_front();
52 }
53
54 EXPECT_EQ(0u, d.size());
55 }
56
TEST_F(LazilyDeallocatedDequeTest,PushFrontBackAndPopFront1)57 TEST_F(LazilyDeallocatedDequeTest, PushFrontBackAndPopFront1) {
58 LazilyDeallocatedDeque<int> d;
59
60 d.push_front(123);
61
62 EXPECT_FALSE(d.empty());
63 EXPECT_EQ(1u, d.size());
64
65 EXPECT_EQ(123, d.front());
66
67 d.pop_front();
68 EXPECT_TRUE(d.empty());
69 EXPECT_EQ(0u, d.size());
70 }
71
TEST_F(LazilyDeallocatedDequeTest,PushFrontAndPopFront1000)72 TEST_F(LazilyDeallocatedDequeTest, PushFrontAndPopFront1000) {
73 LazilyDeallocatedDeque<int> d;
74
75 for (int i = 0; i < 1000; i++) {
76 d.push_front(i);
77 }
78
79 EXPECT_EQ(999, d.front());
80 EXPECT_EQ(0, d.back());
81 EXPECT_EQ(1000u, d.size());
82
83 for (int i = 0; i < 1000; i++) {
84 EXPECT_EQ(999 - i, d.front());
85 d.pop_front();
86 }
87
88 EXPECT_EQ(0u, d.size());
89 }
90
TEST_F(LazilyDeallocatedDequeTest,MaybeShrinkQueueWithLargeSizeDrop)91 TEST_F(LazilyDeallocatedDequeTest, MaybeShrinkQueueWithLargeSizeDrop) {
92 LazilyDeallocatedDeque<int> d;
93
94 for (int i = 0; i < 1000; i++) {
95 d.push_back(i);
96 }
97 EXPECT_EQ(1000u, d.size());
98 EXPECT_EQ(1305u, d.capacity());
99 EXPECT_EQ(1000u, d.max_size());
100
101 // Drop most elements.
102 for (int i = 0; i < 990; i++) {
103 d.pop_front();
104 }
105 EXPECT_EQ(10u, d.size());
106 EXPECT_EQ(450u, d.capacity());
107 EXPECT_EQ(1000u, d.max_size());
108
109 // This won't do anything since the max size is greater than the current
110 // capacity.
111 d.MaybeShrinkQueue();
112 EXPECT_EQ(450u, d.capacity());
113 EXPECT_EQ(10u, d.max_size());
114
115 // This will shrink because the max size is now much less than the current
116 // capacity.
117 d.MaybeShrinkQueue();
118 EXPECT_EQ(11u, d.capacity());
119 }
120
TEST_F(LazilyDeallocatedDequeTest,MaybeShrinkQueueWithSmallSizeDrop)121 TEST_F(LazilyDeallocatedDequeTest, MaybeShrinkQueueWithSmallSizeDrop) {
122 LazilyDeallocatedDeque<int> d;
123
124 for (int i = 0; i < 1010; i++) {
125 d.push_back(i);
126 }
127 EXPECT_EQ(1010u, d.size());
128 EXPECT_EQ(1305u, d.capacity());
129 EXPECT_EQ(1010u, d.max_size());
130
131 // Drop a couple of elements.
132 d.pop_front();
133 d.pop_front();
134 EXPECT_EQ(1008u, d.size());
135 EXPECT_EQ(1305u, d.capacity());
136 EXPECT_EQ(1010u, d.max_size());
137
138 // This won't do anything since the max size is only slightly lower than the
139 // capacity.
140 EXPECT_EQ(1305u, d.capacity());
141 EXPECT_EQ(1010u, d.max_size());
142
143 // Ditto. Nothing changed so no point shrinking.
144 d.MaybeShrinkQueue();
145 EXPECT_EQ(1008u, d.max_size());
146 EXPECT_EQ(1011u, d.capacity());
147 }
148
TEST_F(LazilyDeallocatedDequeTest,MaybeShrinkQueueToEmpty)149 TEST_F(LazilyDeallocatedDequeTest, MaybeShrinkQueueToEmpty) {
150 LazilyDeallocatedDeque<int> d;
151
152 for (int i = 0; i < 1000; i++) {
153 d.push_front(i);
154 }
155
156 for (int i = 0; i < 1000; i++) {
157 d.pop_front();
158 }
159
160 d.MaybeShrinkQueue();
161 EXPECT_EQ(0u, d.max_size());
162 EXPECT_EQ(LazilyDeallocatedDeque<int>::kMinimumRingSize, d.capacity());
163 }
164
TEST_F(LazilyDeallocatedDequeTest,MaybeShrinkQueueRateLimiting)165 TEST_F(LazilyDeallocatedDequeTest, MaybeShrinkQueueRateLimiting) {
166 ScopedMockClockOverride clock;
167 LazilyDeallocatedDeque<int> d;
168
169 for (int i = 0; i < 1000; i++) {
170 d.push_back(i);
171 }
172 EXPECT_EQ(1000u, d.size());
173 EXPECT_EQ(1305u, d.capacity());
174 EXPECT_EQ(1000u, d.max_size());
175
176 // Drop some elements.
177 for (int i = 0; i < 400; i++) {
178 d.pop_front();
179 }
180 EXPECT_EQ(600u, d.size());
181 EXPECT_EQ(947u, d.capacity());
182 EXPECT_EQ(1000u, d.max_size());
183
184 // This won't do anything since the max size is greater than the current
185 // capacity.
186 d.MaybeShrinkQueue();
187 EXPECT_EQ(947u, d.capacity());
188 EXPECT_EQ(600u, d.max_size());
189
190 // This will shrink to fit.
191 d.MaybeShrinkQueue();
192 EXPECT_EQ(601u, d.capacity());
193 EXPECT_EQ(600u, d.max_size());
194
195 // Drop some more elements.
196 for (int i = 0; i < 100; i++) {
197 d.pop_front();
198 }
199 EXPECT_EQ(500u, d.size());
200 EXPECT_EQ(601u, d.capacity());
201 EXPECT_EQ(600u, d.max_size());
202
203 // Not enough time has passed so max_size is untouched and not shrunk.
204 d.MaybeShrinkQueue();
205 EXPECT_EQ(601u, d.capacity());
206 EXPECT_EQ(600u, d.max_size());
207
208 // After time passes we re-sample max_size.
209 clock.Advance(
210 Seconds(LazilyDeallocatedDeque<int>::kMinimumShrinkIntervalInSeconds));
211 d.MaybeShrinkQueue();
212 EXPECT_EQ(601u, d.capacity());
213 EXPECT_EQ(500u, d.max_size());
214
215 // And The next call to MaybeShrinkQueue actually shrinks the queue.
216 d.MaybeShrinkQueue();
217 EXPECT_EQ(501u, d.capacity());
218 EXPECT_EQ(500u, d.max_size());
219 }
220
TEST_F(LazilyDeallocatedDequeTest,Iterators)221 TEST_F(LazilyDeallocatedDequeTest, Iterators) {
222 LazilyDeallocatedDeque<int> d;
223
224 d.push_back(1);
225 d.push_back(2);
226 d.push_back(3);
227
228 auto iter = d.begin();
229 EXPECT_EQ(1, *iter);
230 EXPECT_NE(++iter, d.end());
231
232 EXPECT_EQ(2, *iter);
233 EXPECT_NE(++iter, d.end());
234
235 EXPECT_EQ(3, *iter);
236 EXPECT_EQ(++iter, d.end());
237 }
238
TEST_F(LazilyDeallocatedDequeTest,PushBackAndFront)239 TEST_F(LazilyDeallocatedDequeTest, PushBackAndFront) {
240 LazilyDeallocatedDeque<int> d;
241
242 int j = 1;
243 for (int i = 0; i < 1000; i++) {
244 d.push_back(j++);
245 d.push_back(j++);
246 d.push_back(j++);
247 d.push_back(j++);
248 d.push_front(-i);
249 }
250
251 for (int i = -999; i < 4000; i++) {
252 EXPECT_EQ(d.front(), i);
253 d.pop_front();
254 }
255 }
256
TEST_F(LazilyDeallocatedDequeTest,PushBackThenSetCapacity)257 TEST_F(LazilyDeallocatedDequeTest, PushBackThenSetCapacity) {
258 LazilyDeallocatedDeque<int> d;
259 for (int i = 0; i < 1000; i++) {
260 d.push_back(i);
261 }
262
263 EXPECT_EQ(1305u, d.capacity());
264
265 // We need 1 more spot than the size due to the way the Ring works.
266 d.SetCapacity(1001);
267
268 EXPECT_EQ(1000u, d.size());
269 EXPECT_EQ(0, d.front());
270 EXPECT_EQ(999, d.back());
271
272 for (int i = 0; i < 1000; i++) {
273 EXPECT_EQ(d.front(), i);
274 d.pop_front();
275 }
276 }
277
TEST_F(LazilyDeallocatedDequeTest,PushFrontThenSetCapacity)278 TEST_F(LazilyDeallocatedDequeTest, PushFrontThenSetCapacity) {
279 LazilyDeallocatedDeque<int> d;
280 for (int i = 0; i < 1000; i++) {
281 d.push_front(i);
282 }
283
284 EXPECT_EQ(1336u, d.capacity());
285
286 // We need 1 more spot than the size due to the way the Ring works.
287 d.SetCapacity(1001);
288
289 EXPECT_EQ(1000u, d.size());
290 EXPECT_EQ(999, d.front());
291 EXPECT_EQ(0, d.back());
292
293 for (int i = 0; i < 1000; i++) {
294 EXPECT_EQ(d.front(), 999 - i);
295 d.pop_front();
296 }
297 }
298
TEST_F(LazilyDeallocatedDequeTest,PushFrontThenSetCapacity2)299 TEST_F(LazilyDeallocatedDequeTest, PushFrontThenSetCapacity2) {
300 LazilyDeallocatedDeque<std::unique_ptr<int>> d;
301 for (int i = 0; i < 1000; i++) {
302 d.push_front(std::make_unique<int>(i));
303 }
304
305 EXPECT_EQ(1336u, d.capacity());
306
307 // We need 1 more spot than the size due to the way the Ring works.
308 d.SetCapacity(1001);
309
310 EXPECT_EQ(1000u, d.size());
311 EXPECT_EQ(999, *d.front());
312 EXPECT_EQ(0, *d.back());
313
314 for (int i = 0; i < 1000; i++) {
315 EXPECT_EQ(*d.front(), 999 - i);
316 d.pop_front();
317 }
318 }
319
TEST_F(LazilyDeallocatedDequeTest,PushBackAndFrontThenSetCapacity)320 TEST_F(LazilyDeallocatedDequeTest, PushBackAndFrontThenSetCapacity) {
321 LazilyDeallocatedDeque<int> d;
322
323 int j = 1;
324 for (int i = 0; i < 1000; i++) {
325 d.push_back(j++);
326 d.push_back(j++);
327 d.push_back(j++);
328 d.push_back(j++);
329 d.push_front(-i);
330 }
331
332 d.SetCapacity(5001);
333
334 EXPECT_EQ(5000u, d.size());
335 EXPECT_EQ(-999, d.front());
336 EXPECT_EQ(4000, d.back());
337
338 for (int i = -999; i < 4000; i++) {
339 EXPECT_EQ(d.front(), i);
340 d.pop_front();
341 }
342 }
343
TEST_F(LazilyDeallocatedDequeTest,RingPushFront)344 TEST_F(LazilyDeallocatedDequeTest, RingPushFront) {
345 LazilyDeallocatedDeque<int>::Ring r(4);
346
347 r.push_front(1);
348 r.push_front(2);
349 r.push_front(3);
350
351 EXPECT_EQ(3, r.front());
352 EXPECT_EQ(1, r.back());
353 }
354
TEST_F(LazilyDeallocatedDequeTest,RingPushBack)355 TEST_F(LazilyDeallocatedDequeTest, RingPushBack) {
356 LazilyDeallocatedDeque<int>::Ring r(4);
357
358 r.push_back(1);
359 r.push_back(2);
360 r.push_back(3);
361
362 EXPECT_EQ(1, r.front());
363 EXPECT_EQ(3, r.back());
364 }
365
TEST_F(LazilyDeallocatedDequeTest,RingCanPush)366 TEST_F(LazilyDeallocatedDequeTest, RingCanPush) {
367 LazilyDeallocatedDeque<int>::Ring r1(4);
368 LazilyDeallocatedDeque<int>::Ring r2(4);
369
370 for (int i = 0; i < 3; i++) {
371 EXPECT_TRUE(r1.CanPush());
372 r1.push_back(0);
373
374 EXPECT_TRUE(r2.CanPush());
375 r2.push_back(0);
376 }
377
378 EXPECT_FALSE(r1.CanPush());
379 EXPECT_FALSE(r2.CanPush());
380 }
381
TEST_F(LazilyDeallocatedDequeTest,RingPushPopPushPop)382 TEST_F(LazilyDeallocatedDequeTest, RingPushPopPushPop) {
383 LazilyDeallocatedDeque<int>::Ring r(4);
384
385 EXPECT_TRUE(r.empty());
386 EXPECT_TRUE(r.CanPush());
387 r.push_back(1);
388 EXPECT_FALSE(r.empty());
389 EXPECT_TRUE(r.CanPush());
390 r.push_back(2);
391 EXPECT_TRUE(r.CanPush());
392 r.push_back(3);
393 EXPECT_FALSE(r.CanPush());
394
395 EXPECT_FALSE(r.empty());
396 EXPECT_EQ(1, r.front());
397 r.pop_front();
398 EXPECT_FALSE(r.empty());
399 EXPECT_EQ(2, r.front());
400 r.pop_front();
401 EXPECT_FALSE(r.empty());
402 EXPECT_EQ(3, r.front());
403 r.pop_front();
404 EXPECT_TRUE(r.empty());
405
406 EXPECT_TRUE(r.CanPush());
407 r.push_back(10);
408 EXPECT_TRUE(r.CanPush());
409 r.push_back(20);
410 EXPECT_TRUE(r.CanPush());
411 r.push_back(30);
412 EXPECT_FALSE(r.CanPush());
413
414 EXPECT_FALSE(r.empty());
415 EXPECT_EQ(10, r.front());
416 r.pop_front();
417 EXPECT_FALSE(r.empty());
418 EXPECT_EQ(20, r.front());
419 r.pop_front();
420 EXPECT_FALSE(r.empty());
421 EXPECT_EQ(30, r.front());
422 r.pop_front();
423
424 EXPECT_TRUE(r.empty());
425 }
426
TEST_F(LazilyDeallocatedDequeTest,PushAndIterate)427 TEST_F(LazilyDeallocatedDequeTest, PushAndIterate) {
428 LazilyDeallocatedDeque<int> d;
429
430 for (int i = 0; i < 1000; i++) {
431 d.push_front(i);
432 }
433
434 int expected = 999;
435 for (int value : d) {
436 EXPECT_EQ(expected, value);
437 expected--;
438 }
439 }
440
TEST_F(LazilyDeallocatedDequeTest,Swap)441 TEST_F(LazilyDeallocatedDequeTest, Swap) {
442 LazilyDeallocatedDeque<int> a;
443 LazilyDeallocatedDeque<int> b;
444
445 a.push_back(1);
446 a.push_back(2);
447
448 for (int i = 0; i < 1000; i++) {
449 b.push_back(i);
450 }
451
452 EXPECT_EQ(2u, a.size());
453 EXPECT_EQ(1, a.front());
454 EXPECT_EQ(2, a.back());
455 EXPECT_EQ(1000u, b.size());
456 EXPECT_EQ(0, b.front());
457 EXPECT_EQ(999, b.back());
458
459 a.swap(b);
460
461 EXPECT_EQ(1000u, a.size());
462 EXPECT_EQ(0, a.front());
463 EXPECT_EQ(999, a.back());
464 EXPECT_EQ(2u, b.size());
465 EXPECT_EQ(1, b.front());
466 EXPECT_EQ(2, b.back());
467 }
468
469 class DestructorTestItem {
470 public:
DestructorTestItem()471 DestructorTestItem() : v_(-1) {}
472
DestructorTestItem(int v)473 DestructorTestItem(int v) : v_(v) {}
474
~DestructorTestItem()475 ~DestructorTestItem() { destructor_count_++; }
476
477 int v_;
478 static int destructor_count_;
479 };
480
481 int DestructorTestItem::destructor_count_ = 0;
482
TEST_F(LazilyDeallocatedDequeTest,PopFrontCallsDestructor)483 TEST_F(LazilyDeallocatedDequeTest, PopFrontCallsDestructor) {
484 LazilyDeallocatedDeque<DestructorTestItem> a;
485
486 a.push_front(DestructorTestItem(123));
487
488 DestructorTestItem::destructor_count_ = 0;
489 a.pop_front();
490 EXPECT_EQ(1, DestructorTestItem::destructor_count_);
491 }
492
TEST_F(LazilyDeallocatedDequeTest,ExpectedNumberOfDestructorsCalled)493 TEST_F(LazilyDeallocatedDequeTest, ExpectedNumberOfDestructorsCalled) {
494 {
495 LazilyDeallocatedDeque<DestructorTestItem> a;
496
497 for (int i = 0; i < 100; i++) {
498 a.push_front(DestructorTestItem(i));
499 }
500
501 DestructorTestItem::destructor_count_ = 0;
502 }
503
504 EXPECT_EQ(100, DestructorTestItem::destructor_count_);
505 }
506
507 } // namespace internal
508 } // namespace sequence_manager
509 } // namespace base
510