1 /*
2 * Copyright (c) 2021 The WebRTC project authors. All Rights Reserved.
3 *
4 * Use of this source code is governed by a BSD-style license
5 * that can be found in the LICENSE file in the root of the source
6 * tree. An additional intellectual property rights grant can be found
7 * in the file PATENTS. All contributing project authors may
8 * be found in the AUTHORS file in the root of the source tree.
9 */
10
11 // This implementation is borrowed from Chromium.
12
13 #include "rtc_base/containers/flat_map.h"
14
15 #include <algorithm>
16 #include <string>
17 #include <type_traits>
18 #include <vector>
19
20 #include "rtc_base/containers/move_only_int.h"
21 #include "test/gmock.h"
22 #include "test/gtest.h"
23
24 // A flat_map is basically a interface to flat_tree. So several basic
25 // operations are tested to make sure things are set up properly, but the bulk
26 // of the tests are in flat_tree_unittests.cc.
27
28 using ::testing::ElementsAre;
29
30 namespace webrtc {
31
32 namespace {
33
34 struct Unsortable {
35 int value;
36 };
37
operator ==(const Unsortable & lhs,const Unsortable & rhs)38 bool operator==(const Unsortable& lhs, const Unsortable& rhs) {
39 return lhs.value == rhs.value;
40 }
41
42 bool operator<(const Unsortable& lhs, const Unsortable& rhs) = delete;
43 bool operator<=(const Unsortable& lhs, const Unsortable& rhs) = delete;
44 bool operator>(const Unsortable& lhs, const Unsortable& rhs) = delete;
45 bool operator>=(const Unsortable& lhs, const Unsortable& rhs) = delete;
46
TEST(FlatMap,IncompleteType)47 TEST(FlatMap, IncompleteType) {
48 struct A {
49 using Map = flat_map<A, A>;
50 int data;
51 Map set_with_incomplete_type;
52 Map::iterator it;
53 Map::const_iterator cit;
54
55 // We do not declare operator< because clang complains that it's unused.
56 };
57
58 A a;
59 }
60
TEST(FlatMap,RangeConstructor)61 TEST(FlatMap, RangeConstructor) {
62 flat_map<int, int>::value_type input_vals[] = {
63 {1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3, 2}, {3, 3}};
64
65 flat_map<int, int> first(std::begin(input_vals), std::end(input_vals));
66 EXPECT_THAT(first, ElementsAre(std::make_pair(1, 1), std::make_pair(2, 1),
67 std::make_pair(3, 1)));
68 }
69
TEST(FlatMap,MoveConstructor)70 TEST(FlatMap, MoveConstructor) {
71 using pair = std::pair<MoveOnlyInt, MoveOnlyInt>;
72
73 flat_map<MoveOnlyInt, MoveOnlyInt> original;
74 original.insert(pair(MoveOnlyInt(1), MoveOnlyInt(1)));
75 original.insert(pair(MoveOnlyInt(2), MoveOnlyInt(2)));
76 original.insert(pair(MoveOnlyInt(3), MoveOnlyInt(3)));
77 original.insert(pair(MoveOnlyInt(4), MoveOnlyInt(4)));
78
79 flat_map<MoveOnlyInt, MoveOnlyInt> moved(std::move(original));
80
81 EXPECT_EQ(1U, moved.count(MoveOnlyInt(1)));
82 EXPECT_EQ(1U, moved.count(MoveOnlyInt(2)));
83 EXPECT_EQ(1U, moved.count(MoveOnlyInt(3)));
84 EXPECT_EQ(1U, moved.count(MoveOnlyInt(4)));
85 }
86
TEST(FlatMap,VectorConstructor)87 TEST(FlatMap, VectorConstructor) {
88 using IntPair = std::pair<int, int>;
89 using IntMap = flat_map<int, int>;
90 std::vector<IntPair> vect{{1, 1}, {1, 2}, {2, 1}};
91 IntMap map(std::move(vect));
92 EXPECT_THAT(map, ElementsAre(IntPair(1, 1), IntPair(2, 1)));
93 }
94
TEST(FlatMap,InitializerListConstructor)95 TEST(FlatMap, InitializerListConstructor) {
96 flat_map<int, int> cont(
97 {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {1, 2}, {10, 10}, {8, 8}});
98 EXPECT_THAT(cont, ElementsAre(std::make_pair(1, 1), std::make_pair(2, 2),
99 std::make_pair(3, 3), std::make_pair(4, 4),
100 std::make_pair(5, 5), std::make_pair(8, 8),
101 std::make_pair(10, 10)));
102 }
103
TEST(FlatMap,SortedRangeConstructor)104 TEST(FlatMap, SortedRangeConstructor) {
105 using PairType = std::pair<int, Unsortable>;
106 using MapType = flat_map<int, Unsortable>;
107 MapType::value_type input_vals[] = {{1, {1}}, {2, {1}}, {3, {1}}};
108 MapType map(sorted_unique, std::begin(input_vals), std::end(input_vals));
109 EXPECT_THAT(
110 map, ElementsAre(PairType(1, {1}), PairType(2, {1}), PairType(3, {1})));
111 }
112
TEST(FlatMap,SortedCopyFromVectorConstructor)113 TEST(FlatMap, SortedCopyFromVectorConstructor) {
114 using PairType = std::pair<int, Unsortable>;
115 using MapType = flat_map<int, Unsortable>;
116 std::vector<PairType> vect{{1, {1}}, {2, {1}}};
117 MapType map(sorted_unique, vect);
118 EXPECT_THAT(map, ElementsAre(PairType(1, {1}), PairType(2, {1})));
119 }
120
TEST(FlatMap,SortedMoveFromVectorConstructor)121 TEST(FlatMap, SortedMoveFromVectorConstructor) {
122 using PairType = std::pair<int, Unsortable>;
123 using MapType = flat_map<int, Unsortable>;
124 std::vector<PairType> vect{{1, {1}}, {2, {1}}};
125 MapType map(sorted_unique, std::move(vect));
126 EXPECT_THAT(map, ElementsAre(PairType(1, {1}), PairType(2, {1})));
127 }
128
TEST(FlatMap,SortedInitializerListConstructor)129 TEST(FlatMap, SortedInitializerListConstructor) {
130 using PairType = std::pair<int, Unsortable>;
131 flat_map<int, Unsortable> map(
132 sorted_unique,
133 {{1, {1}}, {2, {2}}, {3, {3}}, {4, {4}}, {5, {5}}, {8, {8}}, {10, {10}}});
134 EXPECT_THAT(map,
135 ElementsAre(PairType(1, {1}), PairType(2, {2}), PairType(3, {3}),
136 PairType(4, {4}), PairType(5, {5}), PairType(8, {8}),
137 PairType(10, {10})));
138 }
139
TEST(FlatMap,InitializerListAssignment)140 TEST(FlatMap, InitializerListAssignment) {
141 flat_map<int, int> cont;
142 cont = {{1, 1}, {2, 2}};
143 EXPECT_THAT(cont, ElementsAre(std::make_pair(1, 1), std::make_pair(2, 2)));
144 }
145
TEST(FlatMap,InsertFindSize)146 TEST(FlatMap, InsertFindSize) {
147 flat_map<int, int> s;
148 s.insert(std::make_pair(1, 1));
149 s.insert(std::make_pair(1, 1));
150 s.insert(std::make_pair(2, 2));
151
152 EXPECT_EQ(2u, s.size());
153 EXPECT_EQ(std::make_pair(1, 1), *s.find(1));
154 EXPECT_EQ(std::make_pair(2, 2), *s.find(2));
155 EXPECT_EQ(s.end(), s.find(7));
156 }
157
TEST(FlatMap,CopySwap)158 TEST(FlatMap, CopySwap) {
159 flat_map<int, int> original;
160 original.insert({1, 1});
161 original.insert({2, 2});
162 EXPECT_THAT(original,
163 ElementsAre(std::make_pair(1, 1), std::make_pair(2, 2)));
164
165 flat_map<int, int> copy(original);
166 EXPECT_THAT(copy, ElementsAre(std::make_pair(1, 1), std::make_pair(2, 2)));
167
168 copy.erase(copy.begin());
169 copy.insert({10, 10});
170 EXPECT_THAT(copy, ElementsAre(std::make_pair(2, 2), std::make_pair(10, 10)));
171
172 original.swap(copy);
173 EXPECT_THAT(original,
174 ElementsAre(std::make_pair(2, 2), std::make_pair(10, 10)));
175 EXPECT_THAT(copy, ElementsAre(std::make_pair(1, 1), std::make_pair(2, 2)));
176 }
177
178 // operator[](const Key&)
TEST(FlatMap,SubscriptConstKey)179 TEST(FlatMap, SubscriptConstKey) {
180 flat_map<std::string, int> m;
181
182 // Default construct elements that don't exist yet.
183 int& s = m["a"];
184 EXPECT_EQ(0, s);
185 EXPECT_EQ(1u, m.size());
186
187 // The returned mapped reference should refer into the map.
188 s = 22;
189 EXPECT_EQ(22, m["a"]);
190
191 // Overwrite existing elements.
192 m["a"] = 44;
193 EXPECT_EQ(44, m["a"]);
194 }
195
196 // operator[](Key&&)
TEST(FlatMap,SubscriptMoveOnlyKey)197 TEST(FlatMap, SubscriptMoveOnlyKey) {
198 flat_map<MoveOnlyInt, int> m;
199
200 // Default construct elements that don't exist yet.
201 int& s = m[MoveOnlyInt(1)];
202 EXPECT_EQ(0, s);
203 EXPECT_EQ(1u, m.size());
204
205 // The returned mapped reference should refer into the map.
206 s = 22;
207 EXPECT_EQ(22, m[MoveOnlyInt(1)]);
208
209 // Overwrite existing elements.
210 m[MoveOnlyInt(1)] = 44;
211 EXPECT_EQ(44, m[MoveOnlyInt(1)]);
212 }
213
214 // Mapped& at(const Key&)
215 // const Mapped& at(const Key&) const
TEST(FlatMap,AtFunction)216 TEST(FlatMap, AtFunction) {
217 flat_map<int, std::string> m = {{1, "a"}, {2, "b"}};
218
219 // Basic Usage.
220 EXPECT_EQ("a", m.at(1));
221 EXPECT_EQ("b", m.at(2));
222
223 // Const reference works.
224 const std::string& const_ref = std::as_const(m).at(1);
225 EXPECT_EQ("a", const_ref);
226
227 // Reference works, can operate on the string.
228 m.at(1)[0] = 'x';
229 EXPECT_EQ("x", m.at(1));
230
231 // Out-of-bounds will CHECK.
232 EXPECT_DEATH_IF_SUPPORTED(m.at(-1), "");
233 EXPECT_DEATH_IF_SUPPORTED({ m.at(-1)[0] = 'z'; }, "");
234
235 // Heterogeneous look-up works.
236 flat_map<std::string, int> m2 = {{"a", 1}, {"b", 2}};
237 EXPECT_EQ(1, m2.at(absl::string_view("a")));
238 EXPECT_EQ(2, std::as_const(m2).at(absl::string_view("b")));
239 }
240
241 // insert_or_assign(K&&, M&&)
TEST(FlatMap,InsertOrAssignMoveOnlyKey)242 TEST(FlatMap, InsertOrAssignMoveOnlyKey) {
243 flat_map<MoveOnlyInt, MoveOnlyInt> m;
244
245 // Initial insertion should return an iterator to the element and set the
246 // second pair member to `true`. The inserted key and value should be moved
247 // from.
248 MoveOnlyInt key(1);
249 MoveOnlyInt val(22);
250 auto result = m.insert_or_assign(std::move(key), std::move(val));
251 EXPECT_EQ(1, result.first->first.data());
252 EXPECT_EQ(22, result.first->second.data());
253 EXPECT_TRUE(result.second);
254 EXPECT_EQ(1u, m.size());
255 EXPECT_EQ(0, key.data()); // moved from
256 EXPECT_EQ(0, val.data()); // moved from
257
258 // Second call with same key should result in an assignment, overwriting the
259 // old value. Assignment should be indicated by setting the second pair member
260 // to `false`. Only the inserted value should be moved from, the key should be
261 // left intact.
262 key = MoveOnlyInt(1);
263 val = MoveOnlyInt(44);
264 result = m.insert_or_assign(std::move(key), std::move(val));
265 EXPECT_EQ(1, result.first->first.data());
266 EXPECT_EQ(44, result.first->second.data());
267 EXPECT_FALSE(result.second);
268 EXPECT_EQ(1u, m.size());
269 EXPECT_EQ(1, key.data()); // not moved from
270 EXPECT_EQ(0, val.data()); // moved from
271
272 // Check that random insertion results in sorted range.
273 flat_map<MoveOnlyInt, int> map;
274 for (int i : {3, 1, 5, 6, 8, 7, 0, 9, 4, 2}) {
275 map.insert_or_assign(MoveOnlyInt(i), i);
276 EXPECT_TRUE(absl::c_is_sorted(map));
277 }
278 }
279
280 // insert_or_assign(const_iterator hint, K&&, M&&)
TEST(FlatMap,InsertOrAssignMoveOnlyKeyWithHint)281 TEST(FlatMap, InsertOrAssignMoveOnlyKeyWithHint) {
282 flat_map<MoveOnlyInt, MoveOnlyInt> m;
283
284 // Initial insertion should return an iterator to the element. The inserted
285 // key and value should be moved from.
286 MoveOnlyInt key(1);
287 MoveOnlyInt val(22);
288 auto result = m.insert_or_assign(m.end(), std::move(key), std::move(val));
289 EXPECT_EQ(1, result->first.data());
290 EXPECT_EQ(22, result->second.data());
291 EXPECT_EQ(1u, m.size());
292 EXPECT_EQ(0, key.data()); // moved from
293 EXPECT_EQ(0, val.data()); // moved from
294
295 // Second call with same key should result in an assignment, overwriting the
296 // old value. Only the inserted value should be moved from, the key should be
297 // left intact.
298 key = MoveOnlyInt(1);
299 val = MoveOnlyInt(44);
300 result = m.insert_or_assign(m.end(), std::move(key), std::move(val));
301 EXPECT_EQ(1, result->first.data());
302 EXPECT_EQ(44, result->second.data());
303 EXPECT_EQ(1u, m.size());
304 EXPECT_EQ(1, key.data()); // not moved from
305 EXPECT_EQ(0, val.data()); // moved from
306
307 // Check that random insertion results in sorted range.
308 flat_map<MoveOnlyInt, int> map;
309 for (int i : {3, 1, 5, 6, 8, 7, 0, 9, 4, 2}) {
310 map.insert_or_assign(map.end(), MoveOnlyInt(i), i);
311 EXPECT_TRUE(absl::c_is_sorted(map));
312 }
313 }
314
315 // try_emplace(K&&, Args&&...)
TEST(FlatMap,TryEmplaceMoveOnlyKey)316 TEST(FlatMap, TryEmplaceMoveOnlyKey) {
317 flat_map<MoveOnlyInt, std::pair<MoveOnlyInt, MoveOnlyInt>> m;
318
319 // Trying to emplace into an empty map should succeed. Insertion should return
320 // an iterator to the element and set the second pair member to `true`. The
321 // inserted key and value should be moved from.
322 MoveOnlyInt key(1);
323 MoveOnlyInt val1(22);
324 MoveOnlyInt val2(44);
325 // Test piecewise construction of mapped_type.
326 auto result = m.try_emplace(std::move(key), std::move(val1), std::move(val2));
327 EXPECT_EQ(1, result.first->first.data());
328 EXPECT_EQ(22, result.first->second.first.data());
329 EXPECT_EQ(44, result.first->second.second.data());
330 EXPECT_TRUE(result.second);
331 EXPECT_EQ(1u, m.size());
332 EXPECT_EQ(0, key.data()); // moved from
333 EXPECT_EQ(0, val1.data()); // moved from
334 EXPECT_EQ(0, val2.data()); // moved from
335
336 // Second call with same key should result in a no-op, returning an iterator
337 // to the existing element and returning false as the second pair member.
338 // Key and values that were attempted to be inserted should be left intact.
339 key = MoveOnlyInt(1);
340 auto paired_val = std::make_pair(MoveOnlyInt(33), MoveOnlyInt(55));
341 // Test construction of mapped_type from pair.
342 result = m.try_emplace(std::move(key), std::move(paired_val));
343 EXPECT_EQ(1, result.first->first.data());
344 EXPECT_EQ(22, result.first->second.first.data());
345 EXPECT_EQ(44, result.first->second.second.data());
346 EXPECT_FALSE(result.second);
347 EXPECT_EQ(1u, m.size());
348 EXPECT_EQ(1, key.data()); // not moved from
349 EXPECT_EQ(33, paired_val.first.data()); // not moved from
350 EXPECT_EQ(55, paired_val.second.data()); // not moved from
351
352 // Check that random insertion results in sorted range.
353 flat_map<MoveOnlyInt, int> map;
354 for (int i : {3, 1, 5, 6, 8, 7, 0, 9, 4, 2}) {
355 map.try_emplace(MoveOnlyInt(i), i);
356 EXPECT_TRUE(absl::c_is_sorted(map));
357 }
358 }
359
360 // try_emplace(const_iterator hint, K&&, Args&&...)
TEST(FlatMap,TryEmplaceMoveOnlyKeyWithHint)361 TEST(FlatMap, TryEmplaceMoveOnlyKeyWithHint) {
362 flat_map<MoveOnlyInt, std::pair<MoveOnlyInt, MoveOnlyInt>> m;
363
364 // Trying to emplace into an empty map should succeed. Insertion should return
365 // an iterator to the element. The inserted key and value should be moved
366 // from.
367 MoveOnlyInt key(1);
368 MoveOnlyInt val1(22);
369 MoveOnlyInt val2(44);
370 // Test piecewise construction of mapped_type.
371 auto result =
372 m.try_emplace(m.end(), std::move(key), std::move(val1), std::move(val2));
373 EXPECT_EQ(1, result->first.data());
374 EXPECT_EQ(22, result->second.first.data());
375 EXPECT_EQ(44, result->second.second.data());
376 EXPECT_EQ(1u, m.size());
377 EXPECT_EQ(0, key.data()); // moved from
378 EXPECT_EQ(0, val1.data()); // moved from
379 EXPECT_EQ(0, val2.data()); // moved from
380
381 // Second call with same key should result in a no-op, returning an iterator
382 // to the existing element. Key and values that were attempted to be inserted
383 // should be left intact.
384 key = MoveOnlyInt(1);
385 val1 = MoveOnlyInt(33);
386 val2 = MoveOnlyInt(55);
387 auto paired_val = std::make_pair(MoveOnlyInt(33), MoveOnlyInt(55));
388 // Test construction of mapped_type from pair.
389 result = m.try_emplace(m.end(), std::move(key), std::move(paired_val));
390 EXPECT_EQ(1, result->first.data());
391 EXPECT_EQ(22, result->second.first.data());
392 EXPECT_EQ(44, result->second.second.data());
393 EXPECT_EQ(1u, m.size());
394 EXPECT_EQ(1, key.data()); // not moved from
395 EXPECT_EQ(33, paired_val.first.data()); // not moved from
396 EXPECT_EQ(55, paired_val.second.data()); // not moved from
397
398 // Check that random insertion results in sorted range.
399 flat_map<MoveOnlyInt, int> map;
400 for (int i : {3, 1, 5, 6, 8, 7, 0, 9, 4, 2}) {
401 map.try_emplace(map.end(), MoveOnlyInt(i), i);
402 EXPECT_TRUE(absl::c_is_sorted(map));
403 }
404 }
405
TEST(FlatMap,UsingTransparentCompare)406 TEST(FlatMap, UsingTransparentCompare) {
407 using ExplicitInt = MoveOnlyInt;
408 flat_map<ExplicitInt, int> m;
409 const auto& m1 = m;
410 int x = 0;
411
412 // Check if we can use lookup functions without converting to key_type.
413 // Correctness is checked in flat_tree tests.
414 m.count(x);
415 m1.count(x);
416 m.find(x);
417 m1.find(x);
418 m.equal_range(x);
419 m1.equal_range(x);
420 m.lower_bound(x);
421 m1.lower_bound(x);
422 m.upper_bound(x);
423 m1.upper_bound(x);
424 m.erase(x);
425
426 // Check if we broke overload resolution.
427 m.emplace(ExplicitInt(0), 0);
428 m.emplace(ExplicitInt(1), 0);
429 m.erase(m.begin());
430 m.erase(m.cbegin());
431 }
432
TEST(FlatMap,SupportsEraseIf)433 TEST(FlatMap, SupportsEraseIf) {
434 flat_map<MoveOnlyInt, MoveOnlyInt> m;
435 m.insert(std::make_pair(MoveOnlyInt(1), MoveOnlyInt(1)));
436 m.insert(std::make_pair(MoveOnlyInt(2), MoveOnlyInt(2)));
437 m.insert(std::make_pair(MoveOnlyInt(3), MoveOnlyInt(3)));
438 m.insert(std::make_pair(MoveOnlyInt(4), MoveOnlyInt(4)));
439 m.insert(std::make_pair(MoveOnlyInt(5), MoveOnlyInt(5)));
440
441 EraseIf(m, [to_be_removed = MoveOnlyInt(2)](
442 const std::pair<MoveOnlyInt, MoveOnlyInt>& e) {
443 return e.first == to_be_removed;
444 });
445
446 EXPECT_EQ(m.size(), 4u);
447 ASSERT_TRUE(m.find(MoveOnlyInt(1)) != m.end());
448 ASSERT_FALSE(m.find(MoveOnlyInt(2)) != m.end());
449 ASSERT_TRUE(m.find(MoveOnlyInt(3)) != m.end());
450 ASSERT_TRUE(m.find(MoveOnlyInt(4)) != m.end());
451 ASSERT_TRUE(m.find(MoveOnlyInt(5)) != m.end());
452 }
453
454 } // namespace
455 } // namespace webrtc
456