[Reland] Optimize blink scheduler with an intrusive heap

third_party/WebKit/Source/platform/scheduler/base/intrusive_heap_unittest.cc

Index: third_party/WebKit/Source/platform/scheduler/base/intrusive_heap_unittest.cc
diff --git a/third_party/WebKit/Source/platform/scheduler/base/intrusive_heap_unittest.cc b/third_party/WebKit/Source/platform/scheduler/base/intrusive_heap_unittest.cc
new file mode 100644
index 0000000000000000000000000000000000000000..1f7bb6f6a716dcbd59954c45b354a14268d2b36c
--- /dev/null
+++ b/third_party/WebKit/Source/platform/scheduler/base/intrusive_heap_unittest.cc
@@ -0,0 +1,359 @@
+// Copyright 2016 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "platform/scheduler/base/intrusive_heap.h"
+#include "testing/gmock/include/gmock/gmock.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace blink {
+namespace scheduler {
+namespace {
+
+struct TestElement {
+  int key;
+  HeapHandle* handle;
+
+  bool operator<=(const TestElement& other) const { return key <= other.key; }
+
+  void SetHeapHandle(HeapHandle h) {
+    if (handle)
+      *handle = h;
+  }
+
+  void ClearHeapHandle() {
+    if (handle)
+      *handle = HeapHandle();
+  }
+};
+
+}  // namespace
+
+using IntrusiveHeapTest = ::testing::Test;
+
+TEST(IntrusiveHeapTest, Basic) {
+  IntrusiveHeap<TestElement> heap;
+
+  EXPECT_TRUE(heap.empty());
+  EXPECT_EQ(0u, heap.size());
+}
+
+TEST(IntrusiveHeapTest, Clear) {
+  IntrusiveHeap<TestElement> heap;
+  HeapHandle index1;
+
+  heap.insert({11, &index1});
+  EXPECT_EQ(1u, heap.size());
+  EXPECT_TRUE(index1.IsValid());
+
+  heap.clear();
+  EXPECT_EQ(0u, heap.size());
+  EXPECT_FALSE(index1.IsValid());
+}
+
+TEST(IntrusiveHeapTest, Destructor) {
+  HeapHandle index1;
+
+  {
+    IntrusiveHeap<TestElement> heap;
+
+    heap.insert({11, &index1});
+    EXPECT_EQ(1u, heap.size());
+    EXPECT_TRUE(index1.IsValid());
+  }
+
+  EXPECT_FALSE(index1.IsValid());
+}
+
+TEST(IntrusiveHeapTest, Min) {
+  IntrusiveHeap<TestElement> heap;
+
+  heap.insert({9, nullptr});
+  heap.insert({10, nullptr});
+  heap.insert({8, nullptr});
+  heap.insert({2, nullptr});
+  heap.insert({7, nullptr});
+  heap.insert({15, nullptr});
+  heap.insert({22, nullptr});
+  heap.insert({3, nullptr});
+
+  EXPECT_FALSE(heap.empty());
+  EXPECT_EQ(8u, heap.size());
+  EXPECT_EQ(2, heap.min().key);
+}
+
+TEST(IntrusiveHeapTest, InsertAscending) {
+  IntrusiveHeap<TestElement> heap;
+  HeapHandle index1;
+
+  for (int i = 0; i < 50; i++)
+    heap.insert({i, nullptr});
+
+  EXPECT_EQ(0, heap.min().key);
+  EXPECT_EQ(50u, heap.size());
+}
+
+TEST(IntrusiveHeapTest, InsertDescending) {
+  IntrusiveHeap<TestElement> heap;
+
+  for (int i = 0; i < 50; i++)
+    heap.insert({50 - i, nullptr});
+
+  EXPECT_EQ(1, heap.min().key);
+  EXPECT_EQ(50u, heap.size());
+}
+
+TEST(IntrusiveHeapTest, HeapIndex) {
+  IntrusiveHeap<TestElement> heap;
+  HeapHandle index5;
+  HeapHandle index4;
+  HeapHandle index3;
+  HeapHandle index2;
+  HeapHandle index1;
+
+  EXPECT_FALSE(index1.IsValid());
+  EXPECT_FALSE(index2.IsValid());
+  EXPECT_FALSE(index3.IsValid());
+  EXPECT_FALSE(index4.IsValid());
+  EXPECT_FALSE(index5.IsValid());
+
+  heap.insert({15, &index5});
+  heap.insert({14, &index4});
+  heap.insert({13, &index3});
+  heap.insert({12, &index2});
+  heap.insert({11, &index1});
+
+  EXPECT_TRUE(index1.IsValid());
+  EXPECT_TRUE(index2.IsValid());
+  EXPECT_TRUE(index3.IsValid());
+  EXPECT_TRUE(index4.IsValid());
+  EXPECT_TRUE(index5.IsValid());
+
+  EXPECT_FALSE(heap.empty());
+}
+
+TEST(IntrusiveHeapTest, Pop) {
+  IntrusiveHeap<TestElement> heap;
+  HeapHandle index1;
+  HeapHandle index2;
+
+  heap.insert({11, &index1});
+  heap.insert({12, &index2});
+  EXPECT_EQ(2u, heap.size());
+  EXPECT_TRUE(index1.IsValid());
+  EXPECT_TRUE(index2.IsValid());
+
+  heap.pop();
+  EXPECT_EQ(1u, heap.size());
+  EXPECT_FALSE(index1.IsValid());
+  EXPECT_TRUE(index2.IsValid());
+
+  heap.pop();
+  EXPECT_EQ(0u, heap.size());
+  EXPECT_FALSE(index1.IsValid());
+  EXPECT_FALSE(index2.IsValid());
+}
+
+TEST(IntrusiveHeapTest, PopMany) {
+  IntrusiveHeap<TestElement> heap;
+
+  for (int i = 0; i < 500; i++)
+    heap.insert({i, nullptr});
+
+  EXPECT_FALSE(heap.empty());
+  EXPECT_EQ(500u, heap.size());
+  for (int i = 0; i < 500; i++) {
+    EXPECT_EQ(i, heap.min().key);
+    heap.pop();
+  }
+  EXPECT_TRUE(heap.empty());
+}
+
+TEST(IntrusiveHeapTest, Erase) {
+  IntrusiveHeap<TestElement> heap;
+
+  HeapHandle index12;
+
+  heap.insert({15, nullptr});
+  heap.insert({14, nullptr});
+  heap.insert({13, nullptr});
+  heap.insert({12, &index12});
+  heap.insert({11, nullptr});
+
+  EXPECT_EQ(5u, heap.size());
+  EXPECT_TRUE(index12.IsValid());
+  heap.erase(index12);
+  EXPECT_EQ(4u, heap.size());
+  EXPECT_FALSE(index12.IsValid());
+
+  EXPECT_EQ(11, heap.min().key);
+  heap.pop();
+  EXPECT_EQ(13, heap.min().key);
+  heap.pop();
+  EXPECT_EQ(14, heap.min().key);
+  heap.pop();
+  EXPECT_EQ(15, heap.min().key);
+  heap.pop();
+  EXPECT_TRUE(heap.empty());
+}
+
+TEST(IntrusiveHeapTest, ReplaceMin) {
+  IntrusiveHeap<TestElement> heap;
+
+  for (int i = 0; i < 500; i++)
+    heap.insert({500 - i, nullptr});
+
+  EXPECT_EQ(1, heap.min().key);
+
+  for (int i = 0; i < 500; i++)
+    heap.ReplaceMin({1000 + i, nullptr});
+
+  EXPECT_EQ(1000, heap.min().key);
+}
+
+TEST(IntrusiveHeapTest, ReplaceMinWithNonLeafNode) {
+  IntrusiveHeap<TestElement> heap;
+
+  for (int i = 0; i < 50; i++) {
+    heap.insert({i, nullptr});
+    heap.insert({200 + i, nullptr});
+  }
+
+  EXPECT_EQ(0, heap.min().key);
+
+  for (int i = 0; i < 50; i++)
+    heap.ReplaceMin({100 + i, nullptr});
+
+  for (int i = 0; i < 50; i++) {
+    EXPECT_EQ((100 + i), heap.min().key);
+    heap.pop();
+  }
+  for (int i = 0; i < 50; i++) {
+    EXPECT_EQ((200 + i), heap.min().key);
+    heap.pop();
+  }
+  EXPECT_TRUE(heap.empty());
+}
+
+TEST(IntrusiveHeapTest, ReplaceMinCheckAllFinalPositions) {
+  HeapHandle index[100];
+
+  for (int j = -1; j <= 201; j += 2) {
+    IntrusiveHeap<TestElement> heap;
+    for (size_t i = 0; i < 100; i++) {
+      heap.insert({static_cast<int>(i) * 2, &index[i]});
+    }
+
+    heap.ReplaceMin({j, &index[40]});
+
+    int prev = -2;
+    while (!heap.empty()) {
+      DCHECK_GT(heap.min().key, prev);
+      DCHECK(heap.min().key == j || (heap.min().key % 2) == 0);
+      DCHECK_NE(heap.min().key, 0);
+      prev = heap.min().key;
+      heap.pop();
+    }
+  }
+}
+
+TEST(IntrusiveHeapTest, ChangeKeyUp) {
+  IntrusiveHeap<TestElement> heap;
+  HeapHandle index[10];
+
+  for (size_t i = 0; i < 10; i++) {
+    heap.insert({static_cast<int>(i) * 2, &index[i]});
+  }
+
+  heap.ChangeKey(index[5], {17, &index[5]});
+
+  std::vector<int> results;
+  while (!heap.empty()) {
+    results.push_back(heap.min().key);
+    heap.pop();
+  }
+
+  EXPECT_THAT(results, testing::ElementsAre(0, 2, 4, 6, 8, 12, 14, 16, 17, 18));
+}
+
+TEST(IntrusiveHeapTest, ChangeKeyUpButDoesntMove) {
+  IntrusiveHeap<TestElement> heap;
+  HeapHandle index[10];
+
+  for (size_t i = 0; i < 10; i++) {
+    heap.insert({static_cast<int>(i) * 2, &index[i]});
+  }
+
+  heap.ChangeKey(index[5], {11, &index[5]});
+
+  std::vector<int> results;
+  while (!heap.empty()) {
+    results.push_back(heap.min().key);
+    heap.pop();
+  }
+
+  EXPECT_THAT(results, testing::ElementsAre(0, 2, 4, 6, 8, 11, 12, 14, 16, 18));
+}
+
+TEST(IntrusiveHeapTest, ChangeKeyDown) {
+  IntrusiveHeap<TestElement> heap;
+  HeapHandle index[10];
+
+  for (size_t i = 0; i < 10; i++) {
+    heap.insert({static_cast<int>(i) * 2, &index[i]});
+  }
+
+  heap.ChangeKey(index[5], {1, &index[5]});
+
+  std::vector<int> results;
+  while (!heap.empty()) {
+    results.push_back(heap.min().key);
+    heap.pop();
+  }
+
+  EXPECT_THAT(results, testing::ElementsAre(0, 1, 2, 4, 6, 8, 12, 14, 16, 18));
+}
+
+TEST(IntrusiveHeapTest, ChangeKeyDownButDoesntMove) {
+  IntrusiveHeap<TestElement> heap;
+  HeapHandle index[10];
+
+  for (size_t i = 0; i < 10; i++) {
+    heap.insert({static_cast<int>(i) * 2, &index[i]});
+  }
+
+  heap.ChangeKey(index[5], {9, &index[5]});
+
+  std::vector<int> results;
+  while (!heap.empty()) {
+    results.push_back(heap.min().key);
+    heap.pop();
+  }
+
+  EXPECT_THAT(results, testing::ElementsAre(0, 2, 4, 6, 8, 9, 12, 14, 16, 18));
+}
+
+TEST(IntrusiveHeapTest, ChangeKeyCheckAllFinalPositions) {
+  HeapHandle index[100];
+
+  for (int j = -1; j <= 201; j += 2) {
+    IntrusiveHeap<TestElement> heap;
+    for (size_t i = 0; i < 100; i++) {
+      heap.insert({static_cast<int>(i) * 2, &index[i]});
+    }
+
+    heap.ChangeKey(index[40], {j, &index[40]});
+
+    int prev = -2;
+    while (!heap.empty()) {
+      DCHECK_GT(heap.min().key, prev);
+      DCHECK(heap.min().key == j || (heap.min().key % 2) == 0);
+      DCHECK_NE(heap.min().key, 80);
+      prev = heap.min().key;
+      heap.pop();
+    }
+  }
+}
+
+}  // namespace scheduler
+}  // namespace blink