1 // Copyright 2016 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/intrusive_heap.h"
6 #include "testing/gmock/include/gmock/gmock.h"
7 #include "testing/gtest/include/gtest/gtest.h"
8
9 namespace base {
10 namespace sequence_manager {
11 namespace internal {
12
13 namespace {
14
15 struct TestElement {
16 int key;
17 HeapHandle* handle;
18
operator <=base::sequence_manager::internal::__anon11586e920111::TestElement19 bool operator<=(const TestElement& other) const { return key <= other.key; }
20
SetHeapHandlebase::sequence_manager::internal::__anon11586e920111::TestElement21 void SetHeapHandle(HeapHandle h) {
22 if (handle)
23 *handle = h;
24 }
25
ClearHeapHandlebase::sequence_manager::internal::__anon11586e920111::TestElement26 void ClearHeapHandle() {
27 if (handle)
28 *handle = HeapHandle();
29 }
30 };
31
32 } // namespace
33
34 class IntrusiveHeapTest : public testing::Test {
35 protected:
CompareNodes(const TestElement & a,const TestElement & b)36 static bool CompareNodes(const TestElement& a, const TestElement& b) {
37 return IntrusiveHeap<TestElement>::CompareNodes(a, b);
38 }
39 };
40
TEST_F(IntrusiveHeapTest,Basic)41 TEST_F(IntrusiveHeapTest, Basic) {
42 IntrusiveHeap<TestElement> heap;
43
44 EXPECT_TRUE(heap.empty());
45 EXPECT_EQ(0u, heap.size());
46 }
47
TEST_F(IntrusiveHeapTest,Clear)48 TEST_F(IntrusiveHeapTest, Clear) {
49 IntrusiveHeap<TestElement> heap;
50 HeapHandle index1;
51
52 heap.insert({11, &index1});
53 EXPECT_EQ(1u, heap.size());
54 EXPECT_TRUE(index1.IsValid());
55
56 heap.Clear();
57 EXPECT_EQ(0u, heap.size());
58 EXPECT_FALSE(index1.IsValid());
59 }
60
TEST_F(IntrusiveHeapTest,Destructor)61 TEST_F(IntrusiveHeapTest, Destructor) {
62 HeapHandle index1;
63
64 {
65 IntrusiveHeap<TestElement> heap;
66
67 heap.insert({11, &index1});
68 EXPECT_EQ(1u, heap.size());
69 EXPECT_TRUE(index1.IsValid());
70 }
71
72 EXPECT_FALSE(index1.IsValid());
73 }
74
TEST_F(IntrusiveHeapTest,Min)75 TEST_F(IntrusiveHeapTest, Min) {
76 IntrusiveHeap<TestElement> heap;
77
78 heap.insert({9, nullptr});
79 heap.insert({10, nullptr});
80 heap.insert({8, nullptr});
81 heap.insert({2, nullptr});
82 heap.insert({7, nullptr});
83 heap.insert({15, nullptr});
84 heap.insert({22, nullptr});
85 heap.insert({3, nullptr});
86
87 EXPECT_FALSE(heap.empty());
88 EXPECT_EQ(8u, heap.size());
89 EXPECT_EQ(2, heap.Min().key);
90 }
91
TEST_F(IntrusiveHeapTest,InsertAscending)92 TEST_F(IntrusiveHeapTest, InsertAscending) {
93 IntrusiveHeap<TestElement> heap;
94 HeapHandle index1;
95
96 for (int i = 0; i < 50; i++)
97 heap.insert({i, nullptr});
98
99 EXPECT_EQ(0, heap.Min().key);
100 EXPECT_EQ(50u, heap.size());
101 }
102
TEST_F(IntrusiveHeapTest,InsertDescending)103 TEST_F(IntrusiveHeapTest, InsertDescending) {
104 IntrusiveHeap<TestElement> heap;
105
106 for (int i = 0; i < 50; i++)
107 heap.insert({50 - i, nullptr});
108
109 EXPECT_EQ(1, heap.Min().key);
110 EXPECT_EQ(50u, heap.size());
111 }
112
TEST_F(IntrusiveHeapTest,HeapIndex)113 TEST_F(IntrusiveHeapTest, HeapIndex) {
114 HeapHandle index5;
115 HeapHandle index4;
116 HeapHandle index3;
117 HeapHandle index2;
118 HeapHandle index1;
119 IntrusiveHeap<TestElement> heap;
120
121 EXPECT_FALSE(index1.IsValid());
122 EXPECT_FALSE(index2.IsValid());
123 EXPECT_FALSE(index3.IsValid());
124 EXPECT_FALSE(index4.IsValid());
125 EXPECT_FALSE(index5.IsValid());
126
127 heap.insert({15, &index5});
128 heap.insert({14, &index4});
129 heap.insert({13, &index3});
130 heap.insert({12, &index2});
131 heap.insert({11, &index1});
132
133 EXPECT_TRUE(index1.IsValid());
134 EXPECT_TRUE(index2.IsValid());
135 EXPECT_TRUE(index3.IsValid());
136 EXPECT_TRUE(index4.IsValid());
137 EXPECT_TRUE(index5.IsValid());
138
139 EXPECT_FALSE(heap.empty());
140 }
141
TEST_F(IntrusiveHeapTest,Pop)142 TEST_F(IntrusiveHeapTest, Pop) {
143 IntrusiveHeap<TestElement> heap;
144 HeapHandle index1;
145 HeapHandle index2;
146
147 heap.insert({11, &index1});
148 heap.insert({12, &index2});
149 EXPECT_EQ(2u, heap.size());
150 EXPECT_TRUE(index1.IsValid());
151 EXPECT_TRUE(index2.IsValid());
152
153 heap.Pop();
154 EXPECT_EQ(1u, heap.size());
155 EXPECT_FALSE(index1.IsValid());
156 EXPECT_TRUE(index2.IsValid());
157
158 heap.Pop();
159 EXPECT_EQ(0u, heap.size());
160 EXPECT_FALSE(index1.IsValid());
161 EXPECT_FALSE(index2.IsValid());
162 }
163
TEST_F(IntrusiveHeapTest,PopMany)164 TEST_F(IntrusiveHeapTest, PopMany) {
165 IntrusiveHeap<TestElement> heap;
166
167 for (int i = 0; i < 500; i++)
168 heap.insert({i, nullptr});
169
170 EXPECT_FALSE(heap.empty());
171 EXPECT_EQ(500u, heap.size());
172 for (int i = 0; i < 500; i++) {
173 EXPECT_EQ(i, heap.Min().key);
174 heap.Pop();
175 }
176 EXPECT_TRUE(heap.empty());
177 }
178
TEST_F(IntrusiveHeapTest,Erase)179 TEST_F(IntrusiveHeapTest, Erase) {
180 IntrusiveHeap<TestElement> heap;
181
182 HeapHandle index12;
183
184 heap.insert({15, nullptr});
185 heap.insert({14, nullptr});
186 heap.insert({13, nullptr});
187 heap.insert({12, &index12});
188 heap.insert({11, nullptr});
189
190 EXPECT_EQ(5u, heap.size());
191 EXPECT_TRUE(index12.IsValid());
192 heap.erase(index12);
193 EXPECT_EQ(4u, heap.size());
194 EXPECT_FALSE(index12.IsValid());
195
196 EXPECT_EQ(11, heap.Min().key);
197 heap.Pop();
198 EXPECT_EQ(13, heap.Min().key);
199 heap.Pop();
200 EXPECT_EQ(14, heap.Min().key);
201 heap.Pop();
202 EXPECT_EQ(15, heap.Min().key);
203 heap.Pop();
204 EXPECT_TRUE(heap.empty());
205 }
206
TEST_F(IntrusiveHeapTest,ReplaceMin)207 TEST_F(IntrusiveHeapTest, ReplaceMin) {
208 IntrusiveHeap<TestElement> heap;
209
210 for (int i = 0; i < 500; i++)
211 heap.insert({500 - i, nullptr});
212
213 EXPECT_EQ(1, heap.Min().key);
214
215 for (int i = 0; i < 500; i++)
216 heap.ReplaceMin({1000 + i, nullptr});
217
218 EXPECT_EQ(1000, heap.Min().key);
219 }
220
TEST_F(IntrusiveHeapTest,ReplaceMinWithNonLeafNode)221 TEST_F(IntrusiveHeapTest, ReplaceMinWithNonLeafNode) {
222 IntrusiveHeap<TestElement> heap;
223
224 for (int i = 0; i < 50; i++) {
225 heap.insert({i, nullptr});
226 heap.insert({200 + i, nullptr});
227 }
228
229 EXPECT_EQ(0, heap.Min().key);
230
231 for (int i = 0; i < 50; i++)
232 heap.ReplaceMin({100 + i, nullptr});
233
234 for (int i = 0; i < 50; i++) {
235 EXPECT_EQ((100 + i), heap.Min().key);
236 heap.Pop();
237 }
238 for (int i = 0; i < 50; i++) {
239 EXPECT_EQ((200 + i), heap.Min().key);
240 heap.Pop();
241 }
242 EXPECT_TRUE(heap.empty());
243 }
244
TEST_F(IntrusiveHeapTest,ReplaceMinCheckAllFinalPositions)245 TEST_F(IntrusiveHeapTest, ReplaceMinCheckAllFinalPositions) {
246 HeapHandle index[100];
247
248 for (int j = -1; j <= 201; j += 2) {
249 IntrusiveHeap<TestElement> heap;
250 for (size_t i = 0; i < 100; i++) {
251 heap.insert({static_cast<int>(i) * 2, &index[i]});
252 }
253
254 heap.ReplaceMin({j, &index[40]});
255
256 int prev = -2;
257 while (!heap.empty()) {
258 DCHECK_GT(heap.Min().key, prev);
259 DCHECK(heap.Min().key == j || (heap.Min().key % 2) == 0);
260 DCHECK_NE(heap.Min().key, 0);
261 prev = heap.Min().key;
262 heap.Pop();
263 }
264 }
265 }
266
TEST_F(IntrusiveHeapTest,ChangeKeyUp)267 TEST_F(IntrusiveHeapTest, ChangeKeyUp) {
268 IntrusiveHeap<TestElement> heap;
269 HeapHandle index[10];
270
271 for (size_t i = 0; i < 10; i++) {
272 heap.insert({static_cast<int>(i) * 2, &index[i]});
273 }
274
275 heap.ChangeKey(index[5], {17, &index[5]});
276
277 std::vector<int> results;
278 while (!heap.empty()) {
279 results.push_back(heap.Min().key);
280 heap.Pop();
281 }
282
283 EXPECT_THAT(results, testing::ElementsAre(0, 2, 4, 6, 8, 12, 14, 16, 17, 18));
284 }
285
TEST_F(IntrusiveHeapTest,ChangeKeyUpButDoesntMove)286 TEST_F(IntrusiveHeapTest, ChangeKeyUpButDoesntMove) {
287 IntrusiveHeap<TestElement> heap;
288 HeapHandle index[10];
289
290 for (size_t i = 0; i < 10; i++) {
291 heap.insert({static_cast<int>(i) * 2, &index[i]});
292 }
293
294 heap.ChangeKey(index[5], {11, &index[5]});
295
296 std::vector<int> results;
297 while (!heap.empty()) {
298 results.push_back(heap.Min().key);
299 heap.Pop();
300 }
301
302 EXPECT_THAT(results, testing::ElementsAre(0, 2, 4, 6, 8, 11, 12, 14, 16, 18));
303 }
304
TEST_F(IntrusiveHeapTest,ChangeKeyDown)305 TEST_F(IntrusiveHeapTest, ChangeKeyDown) {
306 IntrusiveHeap<TestElement> heap;
307 HeapHandle index[10];
308
309 for (size_t i = 0; i < 10; i++) {
310 heap.insert({static_cast<int>(i) * 2, &index[i]});
311 }
312
313 heap.ChangeKey(index[5], {1, &index[5]});
314
315 std::vector<int> results;
316 while (!heap.empty()) {
317 results.push_back(heap.Min().key);
318 heap.Pop();
319 }
320
321 EXPECT_THAT(results, testing::ElementsAre(0, 1, 2, 4, 6, 8, 12, 14, 16, 18));
322 }
323
TEST_F(IntrusiveHeapTest,ChangeKeyDownButDoesntMove)324 TEST_F(IntrusiveHeapTest, ChangeKeyDownButDoesntMove) {
325 IntrusiveHeap<TestElement> heap;
326 HeapHandle index[10];
327
328 for (size_t i = 0; i < 10; i++) {
329 heap.insert({static_cast<int>(i) * 2, &index[i]});
330 }
331
332 heap.ChangeKey(index[5], {9, &index[5]});
333
334 std::vector<int> results;
335 while (!heap.empty()) {
336 results.push_back(heap.Min().key);
337 heap.Pop();
338 }
339
340 EXPECT_THAT(results, testing::ElementsAre(0, 2, 4, 6, 8, 9, 12, 14, 16, 18));
341 }
342
TEST_F(IntrusiveHeapTest,ChangeKeyCheckAllFinalPositions)343 TEST_F(IntrusiveHeapTest, ChangeKeyCheckAllFinalPositions) {
344 HeapHandle index[100];
345
346 for (int j = -1; j <= 201; j += 2) {
347 IntrusiveHeap<TestElement> heap;
348 for (size_t i = 0; i < 100; i++) {
349 heap.insert({static_cast<int>(i) * 2, &index[i]});
350 }
351
352 heap.ChangeKey(index[40], {j, &index[40]});
353
354 int prev = -2;
355 while (!heap.empty()) {
356 DCHECK_GT(heap.Min().key, prev);
357 DCHECK(heap.Min().key == j || (heap.Min().key % 2) == 0);
358 DCHECK_NE(heap.Min().key, 80);
359 prev = heap.Min().key;
360 heap.Pop();
361 }
362 }
363 }
364
TEST_F(IntrusiveHeapTest,CompareNodes)365 TEST_F(IntrusiveHeapTest, CompareNodes) {
366 TestElement five{5, nullptr}, six{6, nullptr};
367
368 // Check that we have a strict comparator, otherwise std::is_heap()
369 // (used in DCHECK) may fail. See http://crbug.com/661080.
370 EXPECT_FALSE(IntrusiveHeapTest::CompareNodes(six, six));
371
372 EXPECT_FALSE(IntrusiveHeapTest::CompareNodes(five, six));
373 EXPECT_TRUE(IntrusiveHeapTest::CompareNodes(six, five));
374 }
375
376 } // namespace internal
377 } // namespace sequence_manager
378 } // namespace base
379