| 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 |