| // Copyright 2019 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 "third_party/blink/renderer/core/svg/animation/priority_queue.h" |
| |
| #include "testing/gtest/include/gtest/gtest.h" |
| #include "third_party/blink/renderer/platform/heap/garbage_collected.h" |
| |
| namespace blink { |
| |
| namespace { |
| |
| class TestNode : public GarbageCollected<TestNode> { |
| public: |
| explicit TestNode() : handle_(kNotFound) {} |
| |
| wtf_size_t& PriorityQueueHandle() { return handle_; } |
| |
| void Trace(Visitor*) const {} |
| |
| private: |
| wtf_size_t handle_; |
| }; |
| |
| using TestPriorityQueue = PriorityQueue<int, TestNode>; |
| |
| void VerifyHeap(TestPriorityQueue& queue, int round = -1) { |
| for (wtf_size_t index = 0; index < queue.size(); ++index) { |
| const TestPriorityQueue::EntryType& entry = queue[index]; |
| |
| wtf_size_t left_child_index = index * 2 + 1; |
| if (left_child_index < queue.size()) |
| EXPECT_FALSE(queue[left_child_index].first < entry.first); |
| |
| wtf_size_t right_child_index = left_child_index + 1; |
| if (right_child_index < queue.size()) |
| EXPECT_FALSE(queue[right_child_index].first < entry.first); |
| |
| EXPECT_EQ(entry.second->PriorityQueueHandle(), index); |
| } |
| } |
| |
| } // namespace |
| |
| TEST(PriorityQueueTest, Insertion) { |
| TestPriorityQueue queue; |
| EXPECT_TRUE(queue.IsEmpty()); |
| queue.Insert(7, MakeGarbageCollected<TestNode>()); |
| EXPECT_FALSE(queue.IsEmpty()); |
| for (int n : {1, 2, 6, 4, 5, 3, 0}) |
| queue.Insert(n, MakeGarbageCollected<TestNode>()); |
| EXPECT_FALSE(queue.IsEmpty()); |
| EXPECT_EQ(queue.size(), 8u); |
| VerifyHeap(queue); |
| } |
| |
| TEST(PriorityQueueTest, InsertionDuplicates) { |
| TestPriorityQueue queue; |
| EXPECT_TRUE(queue.IsEmpty()); |
| for (int n : {7, 1, 5, 6, 5, 5, 1, 0}) |
| queue.Insert(n, MakeGarbageCollected<TestNode>()); |
| EXPECT_FALSE(queue.IsEmpty()); |
| EXPECT_EQ(queue.size(), 8u); |
| VerifyHeap(queue); |
| } |
| |
| TEST(PriorityQueueTest, RemovalMin) { |
| TestPriorityQueue queue; |
| EXPECT_TRUE(queue.IsEmpty()); |
| for (int n : {7, 1, 2, 6, 4, 5, 3, 0}) |
| queue.Insert(n, MakeGarbageCollected<TestNode>()); |
| EXPECT_FALSE(queue.IsEmpty()); |
| EXPECT_EQ(queue.size(), 8u); |
| VerifyHeap(queue); |
| for (int n = 0; n < 8; ++n) { |
| EXPECT_EQ(queue.Min(), n); |
| TestNode* node = queue.MinElement(); |
| wtf_size_t expected_size = static_cast<wtf_size_t>(8 - n); |
| EXPECT_EQ(queue.size(), expected_size); |
| queue.Remove(node); |
| EXPECT_EQ(queue.size(), expected_size - 1); |
| VerifyHeap(queue); |
| } |
| } |
| |
| TEST(PriorityQueueTest, RemovalFilledFromOtherSubtree) { |
| TestPriorityQueue queue; |
| using PairType = std::pair<int, Member<TestNode>>; |
| HeapVector<PairType> vector; |
| EXPECT_TRUE(queue.IsEmpty()); |
| // Build a heap/queue where the left subtree contains priority 3 and the right |
| // contains priority 4: |
| // |
| // /-{[6]=4} {[index]=priority} |
| // /-{[2]=4}-{[5]=4} |
| // {[0]=3} |
| // \-{[1]=3}-{[4]=3} |
| // \-{[3]=3} |
| // \-{[7]=3} |
| // |
| for (int n : {3, 3, 4, 3, 3, 4, 4, 3}) { |
| TestNode* node = MakeGarbageCollected<TestNode>(); |
| queue.Insert(n, node); |
| vector.push_back<PairType>({n, node}); |
| } |
| EXPECT_FALSE(queue.IsEmpty()); |
| EXPECT_EQ(queue.size(), 8u); |
| VerifyHeap(queue); |
| |
| queue.Remove(vector[6].second); |
| EXPECT_EQ(queue.size(), 7u); |
| VerifyHeap(queue); |
| } |
| |
| TEST(PriorityQueueTest, RemovalReverse) { |
| TestPriorityQueue queue; |
| using PairType = std::pair<int, Member<TestNode>>; |
| HeapVector<PairType> vector; |
| EXPECT_TRUE(queue.IsEmpty()); |
| for (int n : {7, 1, 2, 6, 4, 5, 3, 0}) { |
| TestNode* node = MakeGarbageCollected<TestNode>(); |
| queue.Insert(n, node); |
| vector.push_back<PairType>({n, node}); |
| } |
| EXPECT_FALSE(queue.IsEmpty()); |
| EXPECT_EQ(queue.size(), 8u); |
| VerifyHeap(queue); |
| std::sort( |
| vector.begin(), vector.end(), |
| [](const PairType& a, const PairType& b) { return a.first > b.first; }); |
| for (int n = 0; n < 8; ++n) { |
| EXPECT_EQ(vector[n].first, 8 - (n + 1)); |
| wtf_size_t expected_size = static_cast<wtf_size_t>(8 - n); |
| EXPECT_EQ(queue.size(), expected_size); |
| queue.Remove(vector[n].second); |
| EXPECT_EQ(queue.size(), expected_size - 1); |
| VerifyHeap(queue); |
| } |
| } |
| |
| TEST(PriorityQueueTest, RemovalRandom) { |
| TestPriorityQueue queue; |
| HeapVector<Member<TestNode>> vector; |
| EXPECT_TRUE(queue.IsEmpty()); |
| for (int n : {7, 1, 2, 6, 4, 0, 5, 3}) { |
| TestNode* node = MakeGarbageCollected<TestNode>(); |
| queue.Insert(n, node); |
| vector.push_back(node); |
| } |
| EXPECT_FALSE(queue.IsEmpty()); |
| EXPECT_EQ(queue.size(), 8u); |
| VerifyHeap(queue); |
| for (int n = 0; n < 8; ++n) { |
| wtf_size_t expected_size = static_cast<wtf_size_t>(8 - n); |
| EXPECT_EQ(queue.size(), expected_size); |
| queue.Remove(vector[n]); |
| EXPECT_EQ(queue.size(), expected_size - 1); |
| VerifyHeap(queue); |
| } |
| } |
| |
| TEST(PriorityQueueTest, Updates) { |
| TestPriorityQueue queue; |
| using PairType = std::pair<int, Member<TestNode>>; |
| HeapVector<PairType> vector; |
| EXPECT_TRUE(queue.IsEmpty()); |
| for (int n : {7, 1, 2, 6, 4, 0, 5, 3}) { |
| TestNode* node = MakeGarbageCollected<TestNode>(); |
| queue.Insert(n, node); |
| vector.push_back<PairType>({n, node}); |
| } |
| EXPECT_FALSE(queue.IsEmpty()); |
| EXPECT_EQ(queue.size(), 8u); |
| VerifyHeap(queue); |
| |
| // Increase/decrease priority for elements from even/odd slots in |vector|. |
| for (int n = 0; n < 8; ++n) { |
| int old_priority = vector[n].first; |
| int adjust = ((n % 2) - 1) * 4; |
| int new_priority = old_priority + adjust; |
| EXPECT_EQ(queue.size(), 8u); |
| queue.Update(new_priority, vector[n].second); |
| EXPECT_EQ(queue.size(), 8u); |
| VerifyHeap(queue, n); |
| } |
| |
| // Decrease priority for the root node. |
| TestNode* smallest = queue[0].second; |
| queue.Update(queue[0].first - 10, smallest); |
| EXPECT_EQ(smallest, queue[0].second); |
| VerifyHeap(queue); |
| |
| // Increase priority for the root node. |
| smallest = queue[0].second; |
| queue.Update(queue[7].first + 1, smallest); |
| EXPECT_EQ(smallest, queue[7].second); |
| VerifyHeap(queue); |
| |
| // No-op update. |
| TestNode* node = queue[3].second; |
| queue.Update(queue[3].first, node); |
| EXPECT_EQ(node, queue[3].second); |
| VerifyHeap(queue); |
| |
| // Decrease priority for a non-root node. |
| node = queue[3].second; |
| int parent_prio = queue[TestPriorityQueue::ParentIndex(3)].first; |
| queue.Update(parent_prio - 1, node); |
| VerifyHeap(queue); |
| |
| // Matching priority of parent doesn't move the node. |
| node = queue[3].second; |
| parent_prio = queue[TestPriorityQueue::ParentIndex(3)].first; |
| queue.Update(parent_prio, node); |
| EXPECT_EQ(node, queue[3].second); |
| VerifyHeap(queue); |
| |
| // Increase priority for a non-root node. |
| node = queue[3].second; |
| int left_child_prio = queue[TestPriorityQueue::LeftChildIndex(3)].first; |
| queue.Update(left_child_prio + 1, node); |
| VerifyHeap(queue); |
| |
| // Matching priority of smallest child doesn't move the node. |
| node = queue[1].second; |
| int left_child_index = TestPriorityQueue::LeftChildIndex(1); |
| left_child_prio = queue[left_child_index].first; |
| int right_child_prio = queue[left_child_index + 1].first; |
| queue.Update(std::min(left_child_prio, right_child_prio), node); |
| EXPECT_EQ(node, queue[1].second); |
| VerifyHeap(queue); |
| } |
| |
| } // namespace blink |