blob: 0c0d3ca9f2429c3d4aa0dc52688a32c385dd70d7 [file] [log] [blame]
 // Copyright (c) 2012 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 "net/base/priority_queue.h" #include #include "base/stl_util.h" #include "testing/gtest/include/gtest/gtest.h" namespace net { namespace { typedef PriorityQueue::Priority Priority; // Queue 0 has empty lists for first and last priorities. // Queue 1 has multiple empty lists in a row, and occupied first and last // priorities. // Queue 2 has multiple empty lists in a row at the first and last priorities. // Queue 0 Queue 1 Queue 2 // Priority 0: {} {3, 7} {} // Priority 1: {2, 3, 7} {2} {} // Priority 2: {1, 5} {1, 5} {1, 2, 3, 5, 7} // Priority 3: {0} {} {0, 4, 6} // Priority 4: {} {} {} // Priority 5: {4, 6} {6} {} // Priority 6: {} {0, 4} {} constexpr Priority kNumPriorities = 7; constexpr size_t kNumElements = 8; constexpr size_t kNumQueues = 3; constexpr Priority kPriorities[kNumQueues][kNumElements] = { {3, 2, 1, 1, 5, 2, 5, 1}, {6, 2, 1, 0, 6, 2, 5, 0}, {3, 2, 2, 2, 3, 2, 3, 2}}; constexpr int kFirstMinOrder[kNumQueues][kNumElements] = { {2, 3, 7, 1, 5, 0, 4, 6}, {3, 7, 2, 1, 5, 6, 0, 4}, {1, 2, 3, 5, 7, 0, 4, 6}}; constexpr int kLastMaxOrderErase[kNumQueues][kNumElements] = { {6, 4, 0, 5, 1, 7, 3, 2}, {4, 0, 6, 5, 1, 2, 7, 3}, {6, 4, 0, 7, 5, 3, 2, 1}}; constexpr int kFirstMaxOrder[kNumQueues][kNumElements] = { {4, 6, 0, 1, 5, 2, 3, 7}, {0, 4, 6, 1, 5, 2, 3, 7}, {0, 4, 6, 1, 2, 3, 5, 7}}; constexpr int kLastMinOrder[kNumQueues][kNumElements] = { {7, 3, 2, 5, 1, 0, 6, 4}, {7, 3, 2, 5, 1, 6, 4, 0}, {7, 5, 3, 2, 1, 6, 4, 0}}; class PriorityQueueTest : public testing::TestWithParam { public: PriorityQueueTest() : queue_(kNumPriorities) {} void SetUp() override { CheckEmpty(); for (size_t i = 0; i < kNumElements; ++i) { EXPECT_EQ(i, queue_.size()); pointers_[i] = queue_.Insert(static_cast(i), kPriorities[GetParam()][i]); EXPECT_FALSE(queue_.empty()); } EXPECT_EQ(kNumElements, queue_.size()); } void CheckEmpty() { EXPECT_TRUE(queue_.empty()); EXPECT_EQ(0u, queue_.size()); EXPECT_TRUE(queue_.FirstMin().is_null()); EXPECT_TRUE(queue_.LastMin().is_null()); EXPECT_TRUE(queue_.FirstMax().is_null()); EXPECT_TRUE(queue_.LastMax().is_null()); } protected: PriorityQueue queue_; PriorityQueue::Pointer pointers_[kNumElements]; }; TEST_P(PriorityQueueTest, AddAndClear) { for (size_t i = 0; i < kNumElements; ++i) { EXPECT_EQ(kPriorities[GetParam()][i], pointers_[i].priority()); EXPECT_EQ(static_cast(i), pointers_[i].value()); } queue_.Clear(); CheckEmpty(); } TEST_P(PriorityQueueTest, PointerComparison) { for (PriorityQueue::Pointer p = queue_.FirstMax(); !p.Equals(queue_.LastMin()); p = queue_.GetNextTowardsLastMin(p)) { for (PriorityQueue::Pointer q = queue_.GetNextTowardsLastMin(p); !q.is_null(); q = queue_.GetNextTowardsLastMin(q)) { EXPECT_TRUE(queue_.IsCloserToFirstMaxThan(p, q)); EXPECT_FALSE(queue_.IsCloserToFirstMaxThan(q, p)); EXPECT_FALSE(queue_.IsCloserToLastMinThan(p, q)); EXPECT_TRUE(queue_.IsCloserToLastMinThan(q, p)); EXPECT_FALSE(p.Equals(q)); } } for (PriorityQueue::Pointer p = queue_.LastMin(); !p.Equals(queue_.FirstMax()); p = queue_.GetPreviousTowardsFirstMax(p)) { for (PriorityQueue::Pointer q = queue_.GetPreviousTowardsFirstMax(p); !q.is_null(); q = queue_.GetPreviousTowardsFirstMax(q)) { EXPECT_FALSE(queue_.IsCloserToFirstMaxThan(p, q)); EXPECT_TRUE(queue_.IsCloserToFirstMaxThan(q, p)); EXPECT_TRUE(queue_.IsCloserToLastMinThan(p, q)); EXPECT_FALSE(queue_.IsCloserToLastMinThan(q, p)); EXPECT_FALSE(p.Equals(q)); } } } TEST_P(PriorityQueueTest, FirstMinOrder) { for (size_t i = 0; i < kNumElements; ++i) { EXPECT_EQ(kNumElements - i, queue_.size()); // Also check Equals. EXPECT_TRUE( queue_.FirstMin().Equals(pointers_[kFirstMinOrder[GetParam()][i]])); EXPECT_EQ(kFirstMinOrder[GetParam()][i], queue_.FirstMin().value()); queue_.Erase(queue_.FirstMin()); } CheckEmpty(); } TEST_P(PriorityQueueTest, LastMinOrder) { for (size_t i = 0; i < kNumElements; ++i) { EXPECT_EQ(kLastMinOrder[GetParam()][i], queue_.LastMin().value()); queue_.Erase(queue_.LastMin()); } CheckEmpty(); } TEST_P(PriorityQueueTest, FirstMaxOrder) { PriorityQueue::Pointer p = queue_.FirstMax(); size_t i = 0; for (; !p.is_null() && i < kNumElements; p = queue_.GetNextTowardsLastMin(p), ++i) { EXPECT_EQ(kFirstMaxOrder[GetParam()][i], p.value()); } EXPECT_TRUE(p.is_null()); EXPECT_EQ(kNumElements, i); queue_.Clear(); CheckEmpty(); } TEST_P(PriorityQueueTest, GetNextTowardsLastMinAndErase) { PriorityQueue::Pointer current = queue_.FirstMax(); for (size_t i = 0; i < kNumElements; ++i) { EXPECT_FALSE(current.is_null()); EXPECT_EQ(kFirstMaxOrder[GetParam()][i], current.value()); PriorityQueue::Pointer next = queue_.GetNextTowardsLastMin(current); queue_.Erase(current); current = next; } EXPECT_TRUE(current.is_null()); CheckEmpty(); } TEST_P(PriorityQueueTest, GetPreviousTowardsFirstMaxAndErase) { PriorityQueue::Pointer current = queue_.LastMin(); for (size_t i = 0; i < kNumElements; ++i) { EXPECT_FALSE(current.is_null()); EXPECT_EQ(kLastMinOrder[GetParam()][i], current.value()); PriorityQueue::Pointer next = queue_.GetPreviousTowardsFirstMax(current); queue_.Erase(current); current = next; } EXPECT_TRUE(current.is_null()); CheckEmpty(); } TEST_P(PriorityQueueTest, FirstMaxOrderErase) { for (size_t i = 0; i < kNumElements; ++i) { EXPECT_EQ(kFirstMaxOrder[GetParam()][i], queue_.FirstMax().value()); queue_.Erase(queue_.FirstMax()); } CheckEmpty(); } TEST_P(PriorityQueueTest, LastMaxOrderErase) { for (size_t i = 0; i < kNumElements; ++i) { EXPECT_EQ(kLastMaxOrderErase[GetParam()][i], queue_.LastMax().value()); queue_.Erase(queue_.LastMax()); } CheckEmpty(); } TEST_P(PriorityQueueTest, EraseFromMiddle) { queue_.Erase(pointers_[2]); queue_.Erase(pointers_[0]); const int expected_order[kNumQueues][kNumElements - 2] = { {3, 7, 1, 5, 4, 6}, {3, 7, 1, 5, 6, 4}, {1, 3, 5, 7, 4, 6}}; for (const auto& value : expected_order[GetParam()]) { EXPECT_EQ(value, queue_.FirstMin().value()); queue_.Erase(queue_.FirstMin()); } CheckEmpty(); } TEST_P(PriorityQueueTest, InsertAtFront) { queue_.InsertAtFront(8, 6); queue_.InsertAtFront(9, 2); queue_.InsertAtFront(10, 0); queue_.InsertAtFront(11, 1); queue_.InsertAtFront(12, 1); const int expected_order[kNumQueues][kNumElements + 5] = { {10, 12, 11, 2, 3, 7, 9, 1, 5, 0, 4, 6, 8}, {10, 3, 7, 12, 11, 2, 9, 1, 5, 6, 8, 0, 4}, {10, 12, 11, 9, 1, 2, 3, 5, 7, 0, 4, 6, 8}}; for (const auto& value : expected_order[GetParam()]) { EXPECT_EQ(value, queue_.FirstMin().value()); queue_.Erase(queue_.FirstMin()); } CheckEmpty(); } TEST_P(PriorityQueueTest, FindIf) { auto pred = [](size_t i, int value) -> bool { return value == static_cast(i); }; for (size_t i = 0; i < kNumElements; ++i) { PriorityQueue::Pointer pointer = queue_.FindIf(base::BindRepeating(pred, i)); EXPECT_FALSE(pointer.is_null()); EXPECT_EQ(static_cast(i), pointer.value()); queue_.Erase(pointer); pointer = queue_.FindIf(base::BindRepeating(pred, i)); EXPECT_TRUE(pointer.is_null()); } } INSTANTIATE_TEST_CASE_P(PriorityQueues, PriorityQueueTest, testing::Range(static_cast(0), kNumQueues)); } // namespace } // namespace net