1 // Copyright 2018 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/task/sequence_manager/lazily_deallocated_deque.h"
6
7 #include "base/time/time_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(1020u, 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(512u, 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(512u, 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(1020u, 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(1020u, 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(1020u, 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(1020u, 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
165 namespace {
166 TimeTicks fake_now;
167 }
168
TEST_F(LazilyDeallocatedDequeTest,MaybeShrinkQueueRateLimiting)169 TEST_F(LazilyDeallocatedDequeTest, MaybeShrinkQueueRateLimiting) {
170 subtle::ScopedTimeClockOverrides time_overrides(
171 nullptr, []() { return fake_now; }, nullptr);
172 LazilyDeallocatedDeque<int> d;
173
174 for (int i = 0; i < 1000; i++) {
175 d.push_back(i);
176 }
177 EXPECT_EQ(1000u, d.size());
178 EXPECT_EQ(1020u, d.capacity());
179 EXPECT_EQ(1000u, d.max_size());
180
181 // Drop some elements.
182 for (int i = 0; i < 100; i++) {
183 d.pop_front();
184 }
185 EXPECT_EQ(900u, d.size());
186 EXPECT_EQ(960u, d.capacity());
187 EXPECT_EQ(1000u, d.max_size());
188
189 // This won't do anything since the max size is greater than the current
190 // capacity.
191 d.MaybeShrinkQueue();
192 EXPECT_EQ(960u, d.capacity());
193 EXPECT_EQ(900u, d.max_size());
194
195 // This will shrink to fit.
196 d.MaybeShrinkQueue();
197 EXPECT_EQ(901u, d.capacity());
198 EXPECT_EQ(900u, d.max_size());
199
200 // Drop some more elements.
201 for (int i = 0; i < 100; i++) {
202 d.pop_front();
203 }
204 EXPECT_EQ(800u, d.size());
205 EXPECT_EQ(901u, d.capacity());
206 EXPECT_EQ(900u, d.max_size());
207
208 // Not enough time has passed so max_size is untouched and not shrunk.
209 d.MaybeShrinkQueue();
210 EXPECT_EQ(900u, d.max_size());
211 EXPECT_EQ(901u, d.capacity());
212
213 // After time passes we re-sample max_size.
214 fake_now += TimeDelta::FromSeconds(
215 LazilyDeallocatedDeque<int>::kMinimumShrinkIntervalInSeconds);
216 d.MaybeShrinkQueue();
217 EXPECT_EQ(800u, d.max_size());
218 EXPECT_EQ(901u, d.capacity());
219
220 // And The next call to MaybeShrinkQueue actually shrinks the queue.
221 d.MaybeShrinkQueue();
222 EXPECT_EQ(800u, d.max_size());
223 EXPECT_EQ(801u, d.capacity());
224 }
225
TEST_F(LazilyDeallocatedDequeTest,Iterators)226 TEST_F(LazilyDeallocatedDequeTest, Iterators) {
227 LazilyDeallocatedDeque<int> d;
228
229 d.push_back(1);
230 d.push_back(2);
231 d.push_back(3);
232
233 auto iter = d.begin();
234 EXPECT_EQ(1, *iter);
235 EXPECT_NE(++iter, d.end());
236
237 EXPECT_EQ(2, *iter);
238 EXPECT_NE(++iter, d.end());
239
240 EXPECT_EQ(3, *iter);
241 EXPECT_EQ(++iter, d.end());
242 }
243
TEST_F(LazilyDeallocatedDequeTest,PushBackAndFront)244 TEST_F(LazilyDeallocatedDequeTest, PushBackAndFront) {
245 LazilyDeallocatedDeque<int> d;
246
247 int j = 1;
248 for (int i = 0; i < 1000; i++) {
249 d.push_back(j++);
250 d.push_back(j++);
251 d.push_back(j++);
252 d.push_back(j++);
253 d.push_front(-i);
254 }
255
256 for (int i = -999; i < 4000; i++) {
257 EXPECT_EQ(d.front(), i);
258 d.pop_front();
259 }
260 }
261
TEST_F(LazilyDeallocatedDequeTest,SetCapacity)262 TEST_F(LazilyDeallocatedDequeTest, SetCapacity) {
263 LazilyDeallocatedDeque<int> d;
264 for (int i = 0; i < 1000; i++) {
265 d.push_back(i);
266 }
267
268 EXPECT_EQ(1020u, d.capacity());
269
270 // We need 1 more spot than the size due to the way the Ring works.
271 d.SetCapacity(1001);
272
273 for (int i = 0; i < 1000; i++) {
274 EXPECT_EQ(d.front(), i);
275 d.pop_front();
276 }
277 }
278
TEST_F(LazilyDeallocatedDequeTest,RingPushFront)279 TEST_F(LazilyDeallocatedDequeTest, RingPushFront) {
280 LazilyDeallocatedDeque<int>::Ring r(4);
281
282 r.push_front(1);
283 r.push_front(2);
284 r.push_front(3);
285
286 EXPECT_EQ(3, r.front());
287 EXPECT_EQ(1, r.back());
288 }
289
TEST_F(LazilyDeallocatedDequeTest,RingPushBack)290 TEST_F(LazilyDeallocatedDequeTest, RingPushBack) {
291 LazilyDeallocatedDeque<int>::Ring r(4);
292
293 r.push_back(1);
294 r.push_back(2);
295 r.push_back(3);
296
297 EXPECT_EQ(1, r.front());
298 EXPECT_EQ(3, r.back());
299 }
300
TEST_F(LazilyDeallocatedDequeTest,RingCanPush)301 TEST_F(LazilyDeallocatedDequeTest, RingCanPush) {
302 LazilyDeallocatedDeque<int>::Ring r1(4);
303 LazilyDeallocatedDeque<int>::Ring r2(4);
304
305 for (int i = 0; i < 3; i++) {
306 EXPECT_TRUE(r1.CanPush());
307 r1.push_back(0);
308
309 EXPECT_TRUE(r2.CanPush());
310 r2.push_back(0);
311 }
312
313 EXPECT_FALSE(r1.CanPush());
314 EXPECT_FALSE(r2.CanPush());
315 }
316
TEST_F(LazilyDeallocatedDequeTest,RingPushPopPushPop)317 TEST_F(LazilyDeallocatedDequeTest, RingPushPopPushPop) {
318 LazilyDeallocatedDeque<int>::Ring r(4);
319
320 EXPECT_FALSE(r.CanPop());
321 EXPECT_TRUE(r.CanPush());
322 r.push_back(1);
323 EXPECT_TRUE(r.CanPop());
324 EXPECT_TRUE(r.CanPush());
325 r.push_back(2);
326 EXPECT_TRUE(r.CanPush());
327 r.push_back(3);
328 EXPECT_FALSE(r.CanPush());
329
330 EXPECT_TRUE(r.CanPop());
331 EXPECT_EQ(1, r.front());
332 r.pop_front();
333 EXPECT_TRUE(r.CanPop());
334 EXPECT_EQ(2, r.front());
335 r.pop_front();
336 EXPECT_TRUE(r.CanPop());
337 EXPECT_EQ(3, r.front());
338 r.pop_front();
339 EXPECT_FALSE(r.CanPop());
340
341 EXPECT_TRUE(r.CanPush());
342 r.push_back(10);
343 EXPECT_TRUE(r.CanPush());
344 r.push_back(20);
345 EXPECT_TRUE(r.CanPush());
346 r.push_back(30);
347 EXPECT_FALSE(r.CanPush());
348
349 EXPECT_TRUE(r.CanPop());
350 EXPECT_EQ(10, r.front());
351 r.pop_front();
352 EXPECT_TRUE(r.CanPop());
353 EXPECT_EQ(20, r.front());
354 r.pop_front();
355 EXPECT_TRUE(r.CanPop());
356 EXPECT_EQ(30, r.front());
357 r.pop_front();
358
359 EXPECT_FALSE(r.CanPop());
360 }
361
362 } // namespace internal
363 } // namespace sequence_manager
364 } // namespace base
365