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