| OLD | NEW |
|---|
| (Empty) |
| 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 "platform/scheduler/base/intrusive_heap.h" | |
| 6 #include "testing/gtest/include/gtest/gtest.h" | |
| 7 | |
| 8 namespace blink { | |
| 9 namespace scheduler { | |
| 10 namespace { | |
| 11 | |
| 12 struct TestElement { | |
| 13 int key; | |
| 14 HeapHandle* handle; | |
| 15 | |
| 16 bool operator<=(const TestElement& other) const { return key <= other.key; } | |
| 17 | |
| 18 void SetHeapHandle(HeapHandle h) { | |
| 19 if (handle) | |
| 20 *handle = h; | |
| 21 } | |
| 22 }; | |
| 23 | |
| 24 } // namespace | |
| 25 | |
| 26 using IntrusiveHeapTest = ::testing::Test; | |
| 27 | |
| 28 TEST(IntrusiveHeapTest, Basic) { | |
| 29 IntrusiveHeap<TestElement> heap; | |
| 30 | |
| 31 EXPECT_TRUE(heap.empty()); | |
| 32 EXPECT_EQ(0u, heap.size()); | |
| 33 } | |
| 34 | |
| 35 TEST(IntrusiveHeapTest, Min) { | |
| 36 IntrusiveHeap<TestElement> heap; | |
| 37 | |
| 38 heap.insert({9, nullptr}); | |
| 39 heap.insert({10, nullptr}); | |
| 40 heap.insert({8, nullptr}); | |
| 41 heap.insert({2, nullptr}); | |
| 42 heap.insert({7, nullptr}); | |
| 43 heap.insert({15, nullptr}); | |
| 44 heap.insert({22, nullptr}); | |
| 45 heap.insert({3, nullptr}); | |
| 46 | |
| 47 EXPECT_FALSE(heap.empty()); | |
| 48 EXPECT_EQ(8u, heap.size()); | |
| 49 EXPECT_EQ(2, heap.min().key); | |
| 50 } | |
| 51 | |
| 52 TEST(IntrusiveHeapTest, InsertAscending) { | |
| 53 IntrusiveHeap<TestElement> heap; | |
| 54 | |
| 55 for (int i = 0; i < 50; i++) | |
| 56 heap.insert({i, nullptr}); | |
| 57 | |
| 58 EXPECT_EQ(0, heap.min().key); | |
| 59 EXPECT_EQ(50u, heap.size()); | |
| 60 } | |
| 61 | |
| 62 TEST(IntrusiveHeapTest, InsertDescending) { | |
| 63 IntrusiveHeap<TestElement> heap; | |
| 64 | |
| 65 for (int i = 0; i < 50; i++) | |
| 66 heap.insert({50 - i, nullptr}); | |
| 67 | |
| 68 EXPECT_EQ(1, heap.min().key); | |
| 69 EXPECT_EQ(50u, heap.size()); | |
| 70 } | |
| 71 | |
| 72 TEST(IntrusiveHeapTest, HeapIndex) { | |
| 73 IntrusiveHeap<TestElement> heap; | |
| 74 HeapHandle index5; | |
| 75 HeapHandle index4; | |
| 76 HeapHandle index3; | |
| 77 HeapHandle index2; | |
| 78 HeapHandle index1; | |
| 79 | |
| 80 EXPECT_FALSE(index1.IsValid()); | |
| 81 EXPECT_FALSE(index2.IsValid()); | |
| 82 EXPECT_FALSE(index3.IsValid()); | |
| 83 EXPECT_FALSE(index4.IsValid()); | |
| 84 EXPECT_FALSE(index5.IsValid()); | |
| 85 | |
| 86 heap.insert({15, &index5}); | |
| 87 heap.insert({14, &index4}); | |
| 88 heap.insert({13, &index3}); | |
| 89 heap.insert({12, &index2}); | |
| 90 heap.insert({11, &index1}); | |
| 91 | |
| 92 EXPECT_TRUE(index1.IsValid()); | |
| 93 EXPECT_TRUE(index2.IsValid()); | |
| 94 EXPECT_TRUE(index3.IsValid()); | |
| 95 EXPECT_TRUE(index4.IsValid()); | |
| 96 EXPECT_TRUE(index5.IsValid()); | |
| 97 | |
| 98 EXPECT_FALSE(heap.empty()); | |
| 99 } | |
| 100 | |
| 101 TEST(IntrusiveHeapTest, Pop) { | |
| 102 IntrusiveHeap<TestElement> heap; | |
| 103 | |
| 104 for (int i = 0; i < 500; i++) | |
| 105 heap.insert({i, nullptr}); | |
| 106 | |
| 107 EXPECT_FALSE(heap.empty()); | |
| 108 EXPECT_EQ(500u, heap.size()); | |
| 109 for (int i = 0; i < 500; i++) { | |
| 110 EXPECT_EQ(i, heap.min().key); | |
| 111 heap.pop(); | |
| 112 } | |
| 113 EXPECT_TRUE(heap.empty()); | |
| 114 } | |
| 115 | |
| 116 TEST(IntrusiveHeapTest, Erase) { | |
| 117 IntrusiveHeap<TestElement> heap; | |
| 118 | |
| 119 HeapHandle index12; | |
| 120 | |
| 121 heap.insert({15, nullptr}); | |
| 122 heap.insert({14, nullptr}); | |
| 123 heap.insert({13, nullptr}); | |
| 124 heap.insert({12, &index12}); | |
| 125 heap.insert({11, nullptr}); | |
| 126 | |
| 127 EXPECT_EQ(5u, heap.size()); | |
| 128 heap.erase(index12); | |
| 129 EXPECT_EQ(4u, heap.size()); | |
| 130 | |
| 131 EXPECT_EQ(11, heap.min().key); | |
| 132 heap.pop(); | |
| 133 EXPECT_EQ(13, heap.min().key); | |
| 134 heap.pop(); | |
| 135 EXPECT_EQ(14, heap.min().key); | |
| 136 heap.pop(); | |
| 137 EXPECT_EQ(15, heap.min().key); | |
| 138 heap.pop(); | |
| 139 EXPECT_TRUE(heap.empty()); | |
| 140 } | |
| 141 | |
| 142 TEST(IntrusiveHeapTest, ReplaceMin) { | |
| 143 IntrusiveHeap<TestElement> heap; | |
| 144 | |
| 145 for (int i = 0; i < 500; i++) | |
| 146 heap.insert({500 - i, nullptr}); | |
| 147 | |
| 148 EXPECT_EQ(1, heap.min().key); | |
| 149 | |
| 150 for (int i = 0; i < 500; i++) | |
| 151 heap.ReplaceMin({1000 + i, nullptr}); | |
| 152 | |
| 153 EXPECT_EQ(1000, heap.min().key); | |
| 154 } | |
| 155 | |
| 156 TEST(IntrusiveHeapTest, ReplaceMinWithNonLeafNode) { | |
| 157 IntrusiveHeap<TestElement> heap; | |
| 158 | |
| 159 for (int i = 0; i < 50; i++) { | |
| 160 heap.insert({i, nullptr}); | |
| 161 heap.insert({200 + i, nullptr}); | |
| 162 } | |
| 163 | |
| 164 EXPECT_EQ(0, heap.min().key); | |
| 165 | |
| 166 for (int i = 0; i < 50; i++) | |
| 167 heap.ReplaceMin({100 + i, nullptr}); | |
| 168 | |
| 169 for (int i = 0; i < 50; i++) { | |
| 170 EXPECT_EQ((100 + i), heap.min().key); | |
| 171 heap.pop(); | |
| 172 } | |
| 173 for (int i = 0; i < 50; i++) { | |
| 174 EXPECT_EQ((200 + i), heap.min().key); | |
| 175 heap.pop(); | |
| 176 } | |
| 177 EXPECT_TRUE(heap.empty()); | |
| 178 } | |
| 179 | |
| 180 } // namespace scheduler | |
| 181 } // namespace blink | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2428073002:
Revert of [Reland] Optimize blink scheduler with an intrusive heap (Closed)
