OLD | NEW |
1 // Copyright 2016 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "platform/scheduler/base/intrusive_heap.h" | 5 #include "platform/scheduler/base/intrusive_heap.h" |
6 #include "testing/gmock/include/gmock/gmock.h" | 6 #include "testing/gmock/include/gmock/gmock.h" |
7 #include "testing/gtest/include/gtest/gtest.h" | 7 #include "testing/gtest/include/gtest/gtest.h" |
8 | 8 |
9 namespace blink { | 9 namespace blink { |
10 namespace scheduler { | 10 namespace scheduler { |
(...skipping 260 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
271 } | 271 } |
272 | 272 |
273 heap.ChangeKey(index[5], {17, &index[5]}); | 273 heap.ChangeKey(index[5], {17, &index[5]}); |
274 | 274 |
275 std::vector<int> results; | 275 std::vector<int> results; |
276 while (!heap.empty()) { | 276 while (!heap.empty()) { |
277 results.push_back(heap.Min().key); | 277 results.push_back(heap.Min().key); |
278 heap.Pop(); | 278 heap.Pop(); |
279 } | 279 } |
280 | 280 |
281 EXPECT_THAT(results, testing::ElementsAre(0, 2, 4, 6, 8, 12, 14, 16, 17, 18)); | 281 EXPECT_THAT(results, |
| 282 ::testing::ElementsAre(0, 2, 4, 6, 8, 12, 14, 16, 17, 18)); |
282 } | 283 } |
283 | 284 |
284 TEST_F(IntrusiveHeapTest, ChangeKeyUpButDoesntMove) { | 285 TEST_F(IntrusiveHeapTest, ChangeKeyUpButDoesntMove) { |
285 IntrusiveHeap<TestElement> heap; | 286 IntrusiveHeap<TestElement> heap; |
286 HeapHandle index[10]; | 287 HeapHandle index[10]; |
287 | 288 |
288 for (size_t i = 0; i < 10; i++) { | 289 for (size_t i = 0; i < 10; i++) { |
289 heap.insert({static_cast<int>(i) * 2, &index[i]}); | 290 heap.insert({static_cast<int>(i) * 2, &index[i]}); |
290 } | 291 } |
291 | 292 |
292 heap.ChangeKey(index[5], {11, &index[5]}); | 293 heap.ChangeKey(index[5], {11, &index[5]}); |
293 | 294 |
294 std::vector<int> results; | 295 std::vector<int> results; |
295 while (!heap.empty()) { | 296 while (!heap.empty()) { |
296 results.push_back(heap.Min().key); | 297 results.push_back(heap.Min().key); |
297 heap.Pop(); | 298 heap.Pop(); |
298 } | 299 } |
299 | 300 |
300 EXPECT_THAT(results, testing::ElementsAre(0, 2, 4, 6, 8, 11, 12, 14, 16, 18)); | 301 EXPECT_THAT(results, |
| 302 ::testing::ElementsAre(0, 2, 4, 6, 8, 11, 12, 14, 16, 18)); |
301 } | 303 } |
302 | 304 |
303 TEST_F(IntrusiveHeapTest, ChangeKeyDown) { | 305 TEST_F(IntrusiveHeapTest, ChangeKeyDown) { |
304 IntrusiveHeap<TestElement> heap; | 306 IntrusiveHeap<TestElement> heap; |
305 HeapHandle index[10]; | 307 HeapHandle index[10]; |
306 | 308 |
307 for (size_t i = 0; i < 10; i++) { | 309 for (size_t i = 0; i < 10; i++) { |
308 heap.insert({static_cast<int>(i) * 2, &index[i]}); | 310 heap.insert({static_cast<int>(i) * 2, &index[i]}); |
309 } | 311 } |
310 | 312 |
311 heap.ChangeKey(index[5], {1, &index[5]}); | 313 heap.ChangeKey(index[5], {1, &index[5]}); |
312 | 314 |
313 std::vector<int> results; | 315 std::vector<int> results; |
314 while (!heap.empty()) { | 316 while (!heap.empty()) { |
315 results.push_back(heap.Min().key); | 317 results.push_back(heap.Min().key); |
316 heap.Pop(); | 318 heap.Pop(); |
317 } | 319 } |
318 | 320 |
319 EXPECT_THAT(results, testing::ElementsAre(0, 1, 2, 4, 6, 8, 12, 14, 16, 18)); | 321 EXPECT_THAT(results, |
| 322 ::testing::ElementsAre(0, 1, 2, 4, 6, 8, 12, 14, 16, 18)); |
320 } | 323 } |
321 | 324 |
322 TEST_F(IntrusiveHeapTest, ChangeKeyDownButDoesntMove) { | 325 TEST_F(IntrusiveHeapTest, ChangeKeyDownButDoesntMove) { |
323 IntrusiveHeap<TestElement> heap; | 326 IntrusiveHeap<TestElement> heap; |
324 HeapHandle index[10]; | 327 HeapHandle index[10]; |
325 | 328 |
326 for (size_t i = 0; i < 10; i++) { | 329 for (size_t i = 0; i < 10; i++) { |
327 heap.insert({static_cast<int>(i) * 2, &index[i]}); | 330 heap.insert({static_cast<int>(i) * 2, &index[i]}); |
328 } | 331 } |
329 | 332 |
330 heap.ChangeKey(index[5], {9, &index[5]}); | 333 heap.ChangeKey(index[5], {9, &index[5]}); |
331 | 334 |
332 std::vector<int> results; | 335 std::vector<int> results; |
333 while (!heap.empty()) { | 336 while (!heap.empty()) { |
334 results.push_back(heap.Min().key); | 337 results.push_back(heap.Min().key); |
335 heap.Pop(); | 338 heap.Pop(); |
336 } | 339 } |
337 | 340 |
338 EXPECT_THAT(results, testing::ElementsAre(0, 2, 4, 6, 8, 9, 12, 14, 16, 18)); | 341 EXPECT_THAT(results, |
| 342 ::testing::ElementsAre(0, 2, 4, 6, 8, 9, 12, 14, 16, 18)); |
339 } | 343 } |
340 | 344 |
341 TEST_F(IntrusiveHeapTest, ChangeKeyCheckAllFinalPositions) { | 345 TEST_F(IntrusiveHeapTest, ChangeKeyCheckAllFinalPositions) { |
342 HeapHandle index[100]; | 346 HeapHandle index[100]; |
343 | 347 |
344 for (int j = -1; j <= 201; j += 2) { | 348 for (int j = -1; j <= 201; j += 2) { |
345 IntrusiveHeap<TestElement> heap; | 349 IntrusiveHeap<TestElement> heap; |
346 for (size_t i = 0; i < 100; i++) { | 350 for (size_t i = 0; i < 100; i++) { |
347 heap.insert({static_cast<int>(i) * 2, &index[i]}); | 351 heap.insert({static_cast<int>(i) * 2, &index[i]}); |
348 } | 352 } |
(...skipping 16 matching lines...) Expand all Loading... |
365 | 369 |
366 // This is the stdlibc++ assertion that fails in http://crbug.com/661080 | 370 // This is the stdlibc++ assertion that fails in http://crbug.com/661080 |
367 EXPECT_FALSE(IntrusiveHeapTest::CompareNodes(six, six)); | 371 EXPECT_FALSE(IntrusiveHeapTest::CompareNodes(six, six)); |
368 | 372 |
369 EXPECT_FALSE(IntrusiveHeapTest::CompareNodes(five, six)); | 373 EXPECT_FALSE(IntrusiveHeapTest::CompareNodes(five, six)); |
370 EXPECT_TRUE(IntrusiveHeapTest::CompareNodes(six, five)); | 374 EXPECT_TRUE(IntrusiveHeapTest::CompareNodes(six, five)); |
371 } | 375 } |
372 | 376 |
373 } // namespace scheduler | 377 } // namespace scheduler |
374 } // namespace blink | 378 } // namespace blink |
OLD | NEW |