1 // Copyright 2012 The Chromium Authors
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 "net/base/priority_queue.h"
6
7 #include <cstddef>
8
9 #include "base/functional/bind.h"
10 #include "testing/gtest/include/gtest/gtest.h"
11
12 namespace net {
13
14 namespace {
15
16 typedef PriorityQueue<int>::Priority Priority;
17 // Queue 0 has empty lists for first and last priorities.
18 // Queue 1 has multiple empty lists in a row, and occupied first and last
19 // priorities.
20 // Queue 2 has multiple empty lists in a row at the first and last priorities.
21 // Queue 0 Queue 1 Queue 2
22 // Priority 0: {} {3, 7} {}
23 // Priority 1: {2, 3, 7} {2} {}
24 // Priority 2: {1, 5} {1, 5} {1, 2, 3, 5, 7}
25 // Priority 3: {0} {} {0, 4, 6}
26 // Priority 4: {} {} {}
27 // Priority 5: {4, 6} {6} {}
28 // Priority 6: {} {0, 4} {}
29 constexpr Priority kNumPriorities = 7;
30 constexpr size_t kNumElements = 8;
31 constexpr size_t kNumQueues = 3;
32 constexpr Priority kPriorities[kNumQueues][kNumElements] = {
33 {3, 2, 1, 1, 5, 2, 5, 1},
34 {6, 2, 1, 0, 6, 2, 5, 0},
35 {3, 2, 2, 2, 3, 2, 3, 2}};
36 constexpr int kFirstMinOrder[kNumQueues][kNumElements] = {
37 {2, 3, 7, 1, 5, 0, 4, 6},
38 {3, 7, 2, 1, 5, 6, 0, 4},
39 {1, 2, 3, 5, 7, 0, 4, 6}};
40 constexpr int kLastMaxOrderErase[kNumQueues][kNumElements] = {
41 {6, 4, 0, 5, 1, 7, 3, 2},
42 {4, 0, 6, 5, 1, 2, 7, 3},
43 {6, 4, 0, 7, 5, 3, 2, 1}};
44 constexpr int kFirstMaxOrder[kNumQueues][kNumElements] = {
45 {4, 6, 0, 1, 5, 2, 3, 7},
46 {0, 4, 6, 1, 5, 2, 3, 7},
47 {0, 4, 6, 1, 2, 3, 5, 7}};
48 constexpr int kLastMinOrder[kNumQueues][kNumElements] = {
49 {7, 3, 2, 5, 1, 0, 6, 4},
50 {7, 3, 2, 5, 1, 6, 4, 0},
51 {7, 5, 3, 2, 1, 6, 4, 0}};
52
53 class PriorityQueueTest : public testing::TestWithParam<size_t> {
54 public:
PriorityQueueTest()55 PriorityQueueTest() : queue_(kNumPriorities) {}
56
SetUp()57 void SetUp() override {
58 CheckEmpty();
59 for (size_t i = 0; i < kNumElements; ++i) {
60 EXPECT_EQ(i, queue_.size());
61 pointers_[i] =
62 queue_.Insert(static_cast<int>(i), kPriorities[GetParam()][i]);
63 EXPECT_FALSE(queue_.empty());
64 }
65 EXPECT_EQ(kNumElements, queue_.size());
66 }
67
CheckEmpty()68 void CheckEmpty() {
69 EXPECT_TRUE(queue_.empty());
70 EXPECT_EQ(0u, queue_.size());
71 EXPECT_TRUE(queue_.FirstMin().is_null());
72 EXPECT_TRUE(queue_.LastMin().is_null());
73 EXPECT_TRUE(queue_.FirstMax().is_null());
74 EXPECT_TRUE(queue_.LastMax().is_null());
75 }
76
77 protected:
78 PriorityQueue<int> queue_;
79 PriorityQueue<int>::Pointer pointers_[kNumElements];
80 };
81
TEST_P(PriorityQueueTest,AddAndClear)82 TEST_P(PriorityQueueTest, AddAndClear) {
83 for (size_t i = 0; i < kNumElements; ++i) {
84 EXPECT_EQ(kPriorities[GetParam()][i], pointers_[i].priority());
85 EXPECT_EQ(static_cast<int>(i), pointers_[i].value());
86 }
87 queue_.Clear();
88 CheckEmpty();
89 }
90
TEST_P(PriorityQueueTest,PointerComparison)91 TEST_P(PriorityQueueTest, PointerComparison) {
92 for (PriorityQueue<int>::Pointer p = queue_.FirstMax();
93 !p.Equals(queue_.LastMin()); p = queue_.GetNextTowardsLastMin(p)) {
94 for (PriorityQueue<int>::Pointer q = queue_.GetNextTowardsLastMin(p);
95 !q.is_null(); q = queue_.GetNextTowardsLastMin(q)) {
96 EXPECT_TRUE(queue_.IsCloserToFirstMaxThan(p, q));
97 EXPECT_FALSE(queue_.IsCloserToFirstMaxThan(q, p));
98 EXPECT_FALSE(queue_.IsCloserToLastMinThan(p, q));
99 EXPECT_TRUE(queue_.IsCloserToLastMinThan(q, p));
100 EXPECT_FALSE(p.Equals(q));
101 }
102 }
103
104 for (PriorityQueue<int>::Pointer p = queue_.LastMin();
105 !p.Equals(queue_.FirstMax()); p = queue_.GetPreviousTowardsFirstMax(p)) {
106 for (PriorityQueue<int>::Pointer q = queue_.GetPreviousTowardsFirstMax(p);
107 !q.is_null(); q = queue_.GetPreviousTowardsFirstMax(q)) {
108 EXPECT_FALSE(queue_.IsCloserToFirstMaxThan(p, q));
109 EXPECT_TRUE(queue_.IsCloserToFirstMaxThan(q, p));
110 EXPECT_TRUE(queue_.IsCloserToLastMinThan(p, q));
111 EXPECT_FALSE(queue_.IsCloserToLastMinThan(q, p));
112 EXPECT_FALSE(p.Equals(q));
113 }
114 }
115 }
116
TEST_P(PriorityQueueTest,FirstMinOrder)117 TEST_P(PriorityQueueTest, FirstMinOrder) {
118 for (size_t i = 0; i < kNumElements; ++i) {
119 EXPECT_EQ(kNumElements - i, queue_.size());
120 // Also check Equals.
121 EXPECT_TRUE(
122 queue_.FirstMin().Equals(pointers_[kFirstMinOrder[GetParam()][i]]));
123 EXPECT_EQ(kFirstMinOrder[GetParam()][i], queue_.FirstMin().value());
124 queue_.Erase(queue_.FirstMin());
125 }
126 CheckEmpty();
127 }
128
TEST_P(PriorityQueueTest,LastMinOrder)129 TEST_P(PriorityQueueTest, LastMinOrder) {
130 for (size_t i = 0; i < kNumElements; ++i) {
131 EXPECT_EQ(kLastMinOrder[GetParam()][i], queue_.LastMin().value());
132 queue_.Erase(queue_.LastMin());
133 }
134 CheckEmpty();
135 }
136
TEST_P(PriorityQueueTest,FirstMaxOrder)137 TEST_P(PriorityQueueTest, FirstMaxOrder) {
138 PriorityQueue<int>::Pointer p = queue_.FirstMax();
139 size_t i = 0;
140 for (; !p.is_null() && i < kNumElements;
141 p = queue_.GetNextTowardsLastMin(p), ++i) {
142 EXPECT_EQ(kFirstMaxOrder[GetParam()][i], p.value());
143 }
144 EXPECT_TRUE(p.is_null());
145 EXPECT_EQ(kNumElements, i);
146 queue_.Clear();
147 CheckEmpty();
148 }
149
TEST_P(PriorityQueueTest,GetNextTowardsLastMinAndErase)150 TEST_P(PriorityQueueTest, GetNextTowardsLastMinAndErase) {
151 PriorityQueue<int>::Pointer current = queue_.FirstMax();
152 for (size_t i = 0; i < kNumElements; ++i) {
153 EXPECT_FALSE(current.is_null());
154 EXPECT_EQ(kFirstMaxOrder[GetParam()][i], current.value());
155 PriorityQueue<int>::Pointer next = queue_.GetNextTowardsLastMin(current);
156 queue_.Erase(current);
157 current = next;
158 }
159 EXPECT_TRUE(current.is_null());
160 CheckEmpty();
161 }
162
TEST_P(PriorityQueueTest,GetPreviousTowardsFirstMaxAndErase)163 TEST_P(PriorityQueueTest, GetPreviousTowardsFirstMaxAndErase) {
164 PriorityQueue<int>::Pointer current = queue_.LastMin();
165 for (size_t i = 0; i < kNumElements; ++i) {
166 EXPECT_FALSE(current.is_null());
167 EXPECT_EQ(kLastMinOrder[GetParam()][i], current.value());
168 PriorityQueue<int>::Pointer next =
169 queue_.GetPreviousTowardsFirstMax(current);
170 queue_.Erase(current);
171 current = next;
172 }
173 EXPECT_TRUE(current.is_null());
174 CheckEmpty();
175 }
176
TEST_P(PriorityQueueTest,FirstMaxOrderErase)177 TEST_P(PriorityQueueTest, FirstMaxOrderErase) {
178 for (size_t i = 0; i < kNumElements; ++i) {
179 EXPECT_EQ(kFirstMaxOrder[GetParam()][i], queue_.FirstMax().value());
180 queue_.Erase(queue_.FirstMax());
181 }
182 CheckEmpty();
183 }
184
TEST_P(PriorityQueueTest,LastMaxOrderErase)185 TEST_P(PriorityQueueTest, LastMaxOrderErase) {
186 for (size_t i = 0; i < kNumElements; ++i) {
187 EXPECT_EQ(kLastMaxOrderErase[GetParam()][i], queue_.LastMax().value());
188 queue_.Erase(queue_.LastMax());
189 }
190 CheckEmpty();
191 }
192
TEST_P(PriorityQueueTest,EraseFromMiddle)193 TEST_P(PriorityQueueTest, EraseFromMiddle) {
194 queue_.Erase(pointers_[2]);
195 queue_.Erase(pointers_[0]);
196
197 const int expected_order[kNumQueues][kNumElements - 2] = {
198 {3, 7, 1, 5, 4, 6}, {3, 7, 1, 5, 6, 4}, {1, 3, 5, 7, 4, 6}};
199
200 for (const auto& value : expected_order[GetParam()]) {
201 EXPECT_EQ(value, queue_.FirstMin().value());
202 queue_.Erase(queue_.FirstMin());
203 }
204 CheckEmpty();
205 }
206
TEST_P(PriorityQueueTest,InsertAtFront)207 TEST_P(PriorityQueueTest, InsertAtFront) {
208 queue_.InsertAtFront(8, 6);
209 queue_.InsertAtFront(9, 2);
210 queue_.InsertAtFront(10, 0);
211 queue_.InsertAtFront(11, 1);
212 queue_.InsertAtFront(12, 1);
213
214 const int expected_order[kNumQueues][kNumElements + 5] = {
215 {10, 12, 11, 2, 3, 7, 9, 1, 5, 0, 4, 6, 8},
216 {10, 3, 7, 12, 11, 2, 9, 1, 5, 6, 8, 0, 4},
217 {10, 12, 11, 9, 1, 2, 3, 5, 7, 0, 4, 6, 8}};
218
219 for (const auto& value : expected_order[GetParam()]) {
220 EXPECT_EQ(value, queue_.FirstMin().value());
221 queue_.Erase(queue_.FirstMin());
222 }
223 CheckEmpty();
224 }
225
TEST_P(PriorityQueueTest,FindIf)226 TEST_P(PriorityQueueTest, FindIf) {
227 auto pred = [](size_t i, int value) -> bool {
228 return value == static_cast<int>(i);
229 };
230 for (size_t i = 0; i < kNumElements; ++i) {
231 PriorityQueue<int>::Pointer pointer =
232 queue_.FindIf(base::BindRepeating(pred, i));
233 EXPECT_FALSE(pointer.is_null());
234 EXPECT_EQ(static_cast<int>(i), pointer.value());
235 queue_.Erase(pointer);
236 pointer = queue_.FindIf(base::BindRepeating(pred, i));
237 EXPECT_TRUE(pointer.is_null());
238 }
239 }
240
241 INSTANTIATE_TEST_SUITE_P(PriorityQueues,
242 PriorityQueueTest,
243 testing::Range(static_cast<size_t>(0), kNumQueues));
244
245 } // namespace
246
247 } // namespace net
248