1 // Copyright (c) 2019 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 // Tests QuicheLinkedHashMap.
6
7 #include "quiche/common/quiche_linked_hash_map.h"
8
9 #include <memory>
10 #include <utility>
11
12 #include "quiche/common/platform/api/quiche_test.h"
13
14 using testing::Pair;
15 using testing::Pointee;
16 using testing::UnorderedElementsAre;
17
18 namespace quiche {
19 namespace test {
20
21 // Tests that move constructor works.
TEST(LinkedHashMapTest,Move)22 TEST(LinkedHashMapTest, Move) {
23 // Use unique_ptr as an example of a non-copyable type.
24 QuicheLinkedHashMap<int, std::unique_ptr<int>> m;
25 m[2] = std::make_unique<int>(12);
26 m[3] = std::make_unique<int>(13);
27 QuicheLinkedHashMap<int, std::unique_ptr<int>> n = std::move(m);
28 EXPECT_THAT(n,
29 UnorderedElementsAre(Pair(2, Pointee(12)), Pair(3, Pointee(13))));
30 }
31
TEST(LinkedHashMapTest,CanEmplaceMoveOnly)32 TEST(LinkedHashMapTest, CanEmplaceMoveOnly) {
33 QuicheLinkedHashMap<int, std::unique_ptr<int>> m;
34 struct Data {
35 int k, v;
36 };
37 const Data data[] = {{1, 123}, {3, 345}, {2, 234}, {4, 456}};
38 for (const auto& kv : data) {
39 m.emplace(std::piecewise_construct, std::make_tuple(kv.k),
40 std::make_tuple(new int{kv.v}));
41 }
42 EXPECT_TRUE(m.contains(2));
43 auto found = m.find(2);
44 ASSERT_TRUE(found != m.end());
45 EXPECT_EQ(234, *found->second);
46 }
47
48 struct NoCopy {
NoCopyquiche::test::NoCopy49 explicit NoCopy(int x) : x(x) {}
50 NoCopy(const NoCopy&) = delete;
51 NoCopy& operator=(const NoCopy&) = delete;
52 NoCopy(NoCopy&&) = delete;
53 NoCopy& operator=(NoCopy&&) = delete;
54 int x;
55 };
56
TEST(LinkedHashMapTest,CanEmplaceNoMoveNoCopy)57 TEST(LinkedHashMapTest, CanEmplaceNoMoveNoCopy) {
58 QuicheLinkedHashMap<int, NoCopy> m;
59 struct Data {
60 int k, v;
61 };
62 const Data data[] = {{1, 123}, {3, 345}, {2, 234}, {4, 456}};
63 for (const auto& kv : data) {
64 m.emplace(std::piecewise_construct, std::make_tuple(kv.k),
65 std::make_tuple(kv.v));
66 }
67 EXPECT_TRUE(m.contains(2));
68 auto found = m.find(2);
69 ASSERT_TRUE(found != m.end());
70 EXPECT_EQ(234, found->second.x);
71 }
72
TEST(LinkedHashMapTest,ConstKeys)73 TEST(LinkedHashMapTest, ConstKeys) {
74 QuicheLinkedHashMap<int, int> m;
75 m.insert(std::make_pair(1, 2));
76 // Test that keys are const in iteration.
77 std::pair<int, int>& p = *m.begin();
78 EXPECT_EQ(1, p.first);
79 }
80
81 // Tests that iteration from begin() to end() works
TEST(LinkedHashMapTest,Iteration)82 TEST(LinkedHashMapTest, Iteration) {
83 QuicheLinkedHashMap<int, int> m;
84 EXPECT_TRUE(m.begin() == m.end());
85
86 m.insert(std::make_pair(2, 12));
87 m.insert(std::make_pair(1, 11));
88 m.insert(std::make_pair(3, 13));
89
90 QuicheLinkedHashMap<int, int>::iterator i = m.begin();
91 ASSERT_TRUE(m.begin() == i);
92 ASSERT_TRUE(m.end() != i);
93 EXPECT_EQ(2, i->first);
94 EXPECT_EQ(12, i->second);
95
96 ++i;
97 ASSERT_TRUE(m.end() != i);
98 EXPECT_EQ(1, i->first);
99 EXPECT_EQ(11, i->second);
100
101 ++i;
102 ASSERT_TRUE(m.end() != i);
103 EXPECT_EQ(3, i->first);
104 EXPECT_EQ(13, i->second);
105
106 ++i; // Should be the end of the line.
107 ASSERT_TRUE(m.end() == i);
108 }
109
110 // Tests that reverse iteration from rbegin() to rend() works
TEST(LinkedHashMapTest,ReverseIteration)111 TEST(LinkedHashMapTest, ReverseIteration) {
112 QuicheLinkedHashMap<int, int> m;
113 EXPECT_TRUE(m.rbegin() == m.rend());
114
115 m.insert(std::make_pair(2, 12));
116 m.insert(std::make_pair(1, 11));
117 m.insert(std::make_pair(3, 13));
118
119 QuicheLinkedHashMap<int, int>::reverse_iterator i = m.rbegin();
120 ASSERT_TRUE(m.rbegin() == i);
121 ASSERT_TRUE(m.rend() != i);
122 EXPECT_EQ(3, i->first);
123 EXPECT_EQ(13, i->second);
124
125 ++i;
126 ASSERT_TRUE(m.rend() != i);
127 EXPECT_EQ(1, i->first);
128 EXPECT_EQ(11, i->second);
129
130 ++i;
131 ASSERT_TRUE(m.rend() != i);
132 EXPECT_EQ(2, i->first);
133 EXPECT_EQ(12, i->second);
134
135 ++i; // Should be the end of the line.
136 ASSERT_TRUE(m.rend() == i);
137 }
138
139 // Tests that clear() works
TEST(LinkedHashMapTest,Clear)140 TEST(LinkedHashMapTest, Clear) {
141 QuicheLinkedHashMap<int, int> m;
142 m.insert(std::make_pair(2, 12));
143 m.insert(std::make_pair(1, 11));
144 m.insert(std::make_pair(3, 13));
145
146 ASSERT_EQ(3u, m.size());
147
148 m.clear();
149
150 EXPECT_EQ(0u, m.size());
151
152 m.clear(); // Make sure we can call it on an empty map.
153
154 EXPECT_EQ(0u, m.size());
155 }
156
157 // Tests that size() works.
TEST(LinkedHashMapTest,Size)158 TEST(LinkedHashMapTest, Size) {
159 QuicheLinkedHashMap<int, int> m;
160 EXPECT_EQ(0u, m.size());
161 m.insert(std::make_pair(2, 12));
162 EXPECT_EQ(1u, m.size());
163 m.insert(std::make_pair(1, 11));
164 EXPECT_EQ(2u, m.size());
165 m.insert(std::make_pair(3, 13));
166 EXPECT_EQ(3u, m.size());
167 m.clear();
168 EXPECT_EQ(0u, m.size());
169 }
170
171 // Tests empty()
TEST(LinkedHashMapTest,Empty)172 TEST(LinkedHashMapTest, Empty) {
173 QuicheLinkedHashMap<int, int> m;
174 ASSERT_TRUE(m.empty());
175 m.insert(std::make_pair(2, 12));
176 ASSERT_FALSE(m.empty());
177 m.clear();
178 ASSERT_TRUE(m.empty());
179 }
180
TEST(LinkedHashMapTest,Erase)181 TEST(LinkedHashMapTest, Erase) {
182 QuicheLinkedHashMap<int, int> m;
183 ASSERT_EQ(0u, m.size());
184 EXPECT_EQ(0u, m.erase(2)); // Nothing to erase yet
185
186 m.insert(std::make_pair(2, 12));
187 ASSERT_EQ(1u, m.size());
188 EXPECT_EQ(1u, m.erase(2));
189 EXPECT_EQ(0u, m.size());
190
191 EXPECT_EQ(0u, m.erase(2)); // Make sure nothing bad happens if we repeat.
192 EXPECT_EQ(0u, m.size());
193 }
194
TEST(LinkedHashMapTest,Erase2)195 TEST(LinkedHashMapTest, Erase2) {
196 QuicheLinkedHashMap<int, int> m;
197 ASSERT_EQ(0u, m.size());
198 EXPECT_EQ(0u, m.erase(2)); // Nothing to erase yet
199
200 m.insert(std::make_pair(2, 12));
201 m.insert(std::make_pair(1, 11));
202 m.insert(std::make_pair(3, 13));
203 m.insert(std::make_pair(4, 14));
204 ASSERT_EQ(4u, m.size());
205
206 // Erase middle two
207 EXPECT_EQ(1u, m.erase(1));
208 EXPECT_EQ(1u, m.erase(3));
209
210 EXPECT_EQ(2u, m.size());
211
212 // Make sure we can still iterate over everything that's left.
213 QuicheLinkedHashMap<int, int>::iterator it = m.begin();
214 ASSERT_TRUE(it != m.end());
215 EXPECT_EQ(12, it->second);
216 ++it;
217 ASSERT_TRUE(it != m.end());
218 EXPECT_EQ(14, it->second);
219 ++it;
220 ASSERT_TRUE(it == m.end());
221
222 EXPECT_EQ(0u, m.erase(1)); // Make sure nothing bad happens if we repeat.
223 ASSERT_EQ(2u, m.size());
224
225 EXPECT_EQ(1u, m.erase(2));
226 EXPECT_EQ(1u, m.erase(4));
227 ASSERT_EQ(0u, m.size());
228
229 EXPECT_EQ(0u, m.erase(1)); // Make sure nothing bad happens if we repeat.
230 ASSERT_EQ(0u, m.size());
231 }
232
233 // Test that erase(iter,iter) and erase(iter) compile and work.
TEST(LinkedHashMapTest,Erase3)234 TEST(LinkedHashMapTest, Erase3) {
235 QuicheLinkedHashMap<int, int> m;
236
237 m.insert(std::make_pair(1, 11));
238 m.insert(std::make_pair(2, 12));
239 m.insert(std::make_pair(3, 13));
240 m.insert(std::make_pair(4, 14));
241
242 // Erase middle two
243 QuicheLinkedHashMap<int, int>::iterator it2 = m.find(2);
244 QuicheLinkedHashMap<int, int>::iterator it4 = m.find(4);
245 EXPECT_EQ(m.erase(it2, it4), m.find(4));
246 EXPECT_EQ(2u, m.size());
247
248 // Make sure we can still iterate over everything that's left.
249 QuicheLinkedHashMap<int, int>::iterator it = m.begin();
250 ASSERT_TRUE(it != m.end());
251 EXPECT_EQ(11, it->second);
252 ++it;
253 ASSERT_TRUE(it != m.end());
254 EXPECT_EQ(14, it->second);
255 ++it;
256 ASSERT_TRUE(it == m.end());
257
258 // Erase first one using an iterator.
259 EXPECT_EQ(m.erase(m.begin()), m.find(4));
260
261 // Only the last element should be left.
262 it = m.begin();
263 ASSERT_TRUE(it != m.end());
264 EXPECT_EQ(14, it->second);
265 ++it;
266 ASSERT_TRUE(it == m.end());
267 }
268
TEST(LinkedHashMapTest,Insertion)269 TEST(LinkedHashMapTest, Insertion) {
270 QuicheLinkedHashMap<int, int> m;
271 ASSERT_EQ(0u, m.size());
272 std::pair<QuicheLinkedHashMap<int, int>::iterator, bool> result;
273
274 result = m.insert(std::make_pair(2, 12));
275 ASSERT_EQ(1u, m.size());
276 EXPECT_TRUE(result.second);
277 EXPECT_EQ(2, result.first->first);
278 EXPECT_EQ(12, result.first->second);
279
280 result = m.insert(std::make_pair(1, 11));
281 ASSERT_EQ(2u, m.size());
282 EXPECT_TRUE(result.second);
283 EXPECT_EQ(1, result.first->first);
284 EXPECT_EQ(11, result.first->second);
285
286 result = m.insert(std::make_pair(3, 13));
287 QuicheLinkedHashMap<int, int>::iterator result_iterator = result.first;
288 ASSERT_EQ(3u, m.size());
289 EXPECT_TRUE(result.second);
290 EXPECT_EQ(3, result.first->first);
291 EXPECT_EQ(13, result.first->second);
292
293 result = m.insert(std::make_pair(3, 13));
294 EXPECT_EQ(3u, m.size());
295 EXPECT_FALSE(result.second) << "No insertion should have occurred.";
296 EXPECT_TRUE(result_iterator == result.first)
297 << "Duplicate insertion should have given us the original iterator.";
298 }
299
Pair(int i,int j)300 static std::pair<int, int> Pair(int i, int j) { return {i, j}; }
301
302 // Test front accessors.
TEST(LinkedHashMapTest,Front)303 TEST(LinkedHashMapTest, Front) {
304 QuicheLinkedHashMap<int, int> m;
305
306 m.insert(std::make_pair(2, 12));
307 m.insert(std::make_pair(1, 11));
308 m.insert(std::make_pair(3, 13));
309
310 EXPECT_EQ(3u, m.size());
311 EXPECT_EQ(Pair(2, 12), m.front());
312 m.pop_front();
313 EXPECT_EQ(2u, m.size());
314 EXPECT_EQ(Pair(1, 11), m.front());
315 m.pop_front();
316 EXPECT_EQ(1u, m.size());
317 EXPECT_EQ(Pair(3, 13), m.front());
318 m.pop_front();
319 EXPECT_TRUE(m.empty());
320 }
321
TEST(LinkedHashMapTest,Find)322 TEST(LinkedHashMapTest, Find) {
323 QuicheLinkedHashMap<int, int> m;
324
325 EXPECT_TRUE(m.end() == m.find(1))
326 << "We shouldn't find anything in an empty map.";
327
328 m.insert(std::make_pair(2, 12));
329 EXPECT_TRUE(m.end() == m.find(1))
330 << "We shouldn't find an element that doesn't exist in the map.";
331
332 std::pair<QuicheLinkedHashMap<int, int>::iterator, bool> result =
333 m.insert(std::make_pair(1, 11));
334 ASSERT_TRUE(result.second);
335 ASSERT_TRUE(m.end() != result.first);
336 EXPECT_TRUE(result.first == m.find(1))
337 << "We should have found an element we know exists in the map.";
338 EXPECT_EQ(11, result.first->second);
339
340 // Check that a follow-up insertion doesn't affect our original
341 m.insert(std::make_pair(3, 13));
342 QuicheLinkedHashMap<int, int>::iterator it = m.find(1);
343 ASSERT_TRUE(m.end() != it);
344 EXPECT_EQ(11, it->second);
345
346 m.clear();
347 EXPECT_TRUE(m.end() == m.find(1))
348 << "We shouldn't find anything in a map that we've cleared.";
349 }
350
TEST(LinkedHashMapTest,Contains)351 TEST(LinkedHashMapTest, Contains) {
352 QuicheLinkedHashMap<int, int> m;
353
354 EXPECT_FALSE(m.contains(1)) << "An empty map shouldn't contain anything.";
355
356 m.insert(std::make_pair(2, 12));
357 EXPECT_FALSE(m.contains(1))
358 << "The map shouldn't contain an element that doesn't exist.";
359
360 m.insert(std::make_pair(1, 11));
361 EXPECT_TRUE(m.contains(1))
362 << "The map should contain an element that we know exists.";
363
364 m.clear();
365 EXPECT_FALSE(m.contains(1))
366 << "A map that we've cleared shouldn't contain anything.";
367 }
368
TEST(LinkedHashMapTest,Swap)369 TEST(LinkedHashMapTest, Swap) {
370 QuicheLinkedHashMap<int, int> m1;
371 QuicheLinkedHashMap<int, int> m2;
372 m1.insert(std::make_pair(1, 1));
373 m1.insert(std::make_pair(2, 2));
374 m2.insert(std::make_pair(3, 3));
375 ASSERT_EQ(2u, m1.size());
376 ASSERT_EQ(1u, m2.size());
377 m1.swap(m2);
378 ASSERT_EQ(1u, m1.size());
379 ASSERT_EQ(2u, m2.size());
380 }
381
TEST(LinkedHashMapTest,CustomHashAndEquality)382 TEST(LinkedHashMapTest, CustomHashAndEquality) {
383 struct CustomIntHash {
384 size_t operator()(int x) const { return x; }
385 };
386 QuicheLinkedHashMap<int, int, CustomIntHash> m;
387 m.insert(std::make_pair(1, 1));
388 EXPECT_TRUE(m.contains(1));
389 EXPECT_EQ(1, m[1]);
390 }
391
392 } // namespace test
393 } // namespace quiche
394