Fix incorrect usage of std::is_heap in blink::scheduler::IntrusiveHeap.

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

 // 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 {
@@ skipping 11 matching lines @@
   }
 
   void ClearHeapHandle() {
     if (handle)
       *handle = HeapHandle();
   }
 };
 
 }  // namespace
 
-using IntrusiveHeapTest = ::testing::Test;
+class IntrusiveHeapTest : public ::testing::Test {
+ protected:
+  static bool CompareNodes(const TestElement& a, const TestElement& b) {
+    return IntrusiveHeap<TestElement>::CompareNodes(a, b);
+  }
+};
 
-TEST(IntrusiveHeapTest, Basic) {
+TEST_F(IntrusiveHeapTest, Basic) {
   IntrusiveHeap<TestElement> heap;
 
   EXPECT_TRUE(heap.empty());
   EXPECT_EQ(0u, heap.size());
 }
 
-TEST(IntrusiveHeapTest, Clear) {
+TEST_F(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) {
+TEST_F(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) {
+TEST_F(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) {
+TEST_F(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) {
+TEST_F(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) {
+TEST_F(IntrusiveHeapTest, HeapIndex) {
   HeapHandle index5;
   HeapHandle index4;
   HeapHandle index3;
   HeapHandle index2;
   HeapHandle index1;
   IntrusiveHeap<TestElement> heap;
 
   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) {
+TEST_F(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) {
+TEST_F(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) {
+TEST_F(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) {
+TEST_F(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) {
+TEST_F(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) {
+TEST_F(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) {
+TEST_F(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) {
+TEST_F(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) {
+TEST_F(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) {
+TEST_F(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) {
+TEST_F(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();
     }
   }
 }
 
+TEST_F(IntrusiveHeapTest, CompareNodes) {
+  TestElement five{5, nullptr}, six{6, nullptr};
+
+  // This is the stdlibc++ assertion that fails in http://crbug.com/661080
+  EXPECT_FALSE(IntrusiveHeapTest::CompareNodes(six, six));
+
+  EXPECT_FALSE(IntrusiveHeapTest::CompareNodes(five, six));
+  EXPECT_TRUE(IntrusiveHeapTest::CompareNodes(six, five));
+}
+
 }  // namespace scheduler
 }  // namespace blink