1 /*
2 * Copyright 2020 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include <ftl/small_map.h>
18 #include <gtest/gtest.h>
19
20 #include <cctype>
21 #include <string>
22
23 using namespace std::string_literals;
24
25 namespace android::test {
26
27 using ftl::SmallMap;
28
29 // Keep in sync with example usage in header file.
TEST(SmallMap,Example)30 TEST(SmallMap, Example) {
31 ftl::SmallMap<int, std::string, 3> map;
32 EXPECT_TRUE(map.empty());
33 EXPECT_FALSE(map.dynamic());
34
35 map = ftl::init::map<int, std::string>(123, "abc")(-1)(42, 3u, '?');
36 EXPECT_EQ(map.size(), 3u);
37 EXPECT_FALSE(map.dynamic());
38
39 EXPECT_TRUE(map.contains(123));
40
41 EXPECT_EQ(map.get(42, [](const std::string& s) { return s.size(); }), 3u);
42
43 const auto opt = map.get(-1);
44 ASSERT_TRUE(opt);
45
46 std::string& ref = *opt;
47 EXPECT_TRUE(ref.empty());
48 ref = "xyz";
49
50 map.emplace_or_replace(0, "vanilla", 2u, 3u);
51 EXPECT_TRUE(map.dynamic());
52
53 EXPECT_EQ(map, SmallMap(ftl::init::map(-1, "xyz")(0, "nil")(42, "???")(123, "abc")));
54 }
55
TEST(SmallMap,Construct)56 TEST(SmallMap, Construct) {
57 {
58 // Default constructor.
59 SmallMap<int, std::string, 2> map;
60
61 EXPECT_TRUE(map.empty());
62 EXPECT_FALSE(map.dynamic());
63 }
64 {
65 // In-place constructor with same types.
66 SmallMap<int, std::string, 5> map =
67 ftl::init::map<int, std::string>(123, "abc")(456, "def")(789, "ghi");
68
69 EXPECT_EQ(map.size(), 3u);
70 EXPECT_EQ(map.max_size(), 5u);
71 EXPECT_FALSE(map.dynamic());
72
73 EXPECT_EQ(map, SmallMap(ftl::init::map(123, "abc")(456, "def")(789, "ghi")));
74 }
75 {
76 // In-place constructor with different types.
77 SmallMap<int, std::string, 5> map =
78 ftl::init::map<int, std::string>(123, "abc")(-1)(42, 3u, '?');
79
80 EXPECT_EQ(map.size(), 3u);
81 EXPECT_EQ(map.max_size(), 5u);
82 EXPECT_FALSE(map.dynamic());
83
84 EXPECT_EQ(map, SmallMap(ftl::init::map(42, "???")(123, "abc")(-1, "\0\0\0")));
85 }
86 {
87 // In-place constructor with implicit size.
88 SmallMap map = ftl::init::map<int, std::string>(123, "abc")(-1)(42, 3u, '?');
89
90 static_assert(std::is_same_v<decltype(map), SmallMap<int, std::string, 3>>);
91 EXPECT_EQ(map.size(), 3u);
92 EXPECT_EQ(map.max_size(), 3u);
93 EXPECT_FALSE(map.dynamic());
94
95 EXPECT_EQ(map, SmallMap(ftl::init::map(-1, "\0\0\0")(42, "???")(123, "abc")));
96 }
97 }
98
TEST(SmallMap,Assign)99 TEST(SmallMap, Assign) {
100 {
101 // Same types; smaller capacity.
102 SmallMap map1 = ftl::init::map<char, std::string>('k', "kilo")('M', "mega")('G', "giga");
103 const SmallMap map2 = ftl::init::map('T', "tera"s)('P', "peta"s);
104
105 map1 = map2;
106 EXPECT_EQ(map1, map2);
107 }
108 {
109 // Convertible types; same capacity.
110 SmallMap map1 = ftl::init::map<char, std::string>('M', "mega")('G', "giga");
111 const SmallMap map2 = ftl::init::map('T', "tera")('P', "peta");
112
113 map1 = map2;
114 EXPECT_EQ(map1, map2);
115 }
116 {
117 // Convertible types; zero capacity.
118 SmallMap<char, std::string, 0> map1 = ftl::init::map('M', "mega")('G', "giga");
119 const SmallMap<char, std::string, 0> map2 = ftl::init::map('T', "tera")('P', "peta");
120
121 map1 = map2;
122 EXPECT_EQ(map1, map2);
123 }
124 }
125
TEST(SmallMap,UniqueKeys)126 TEST(SmallMap, UniqueKeys) {
127 {
128 // Duplicate mappings are discarded.
129 const SmallMap map = ftl::init::map<int, float>(1)(2)(3)(2)(3)(1)(3)(2)(1);
130
131 EXPECT_EQ(map.size(), 3u);
132 EXPECT_EQ(map.max_size(), 9u);
133
134 using Map = decltype(map);
135 EXPECT_EQ(map, Map(ftl::init::map(1, 0.f)(2, 0.f)(3, 0.f)));
136 }
137 {
138 // Duplicate mappings may be reordered.
139 const SmallMap map = ftl::init::map('a', 'A')(
140 'b', 'B')('b')('b')('c', 'C')('a')('d')('c')('e', 'E')('d', 'D')('a')('f', 'F');
141
142 EXPECT_EQ(map.size(), 6u);
143 EXPECT_EQ(map.max_size(), 12u);
144
145 using Map = decltype(map);
146 EXPECT_EQ(map, Map(ftl::init::map('a', 'A')('b', 'B')('c', 'C')('d', 'D')('e', 'E')('f', 'F')));
147 }
148 }
149
TEST(SmallMap,Find)150 TEST(SmallMap, Find) {
151 {
152 // Constant reference.
153 const SmallMap map = ftl::init::map('a', 'A')('b', 'B')('c', 'C');
154
155 const auto opt = map.get('b');
156 EXPECT_EQ(opt, 'B');
157
158 const char d = 'D';
159 const auto ref = map.get('d').value_or(std::cref(d));
160 EXPECT_EQ(ref.get(), 'D');
161 }
162 {
163 // Mutable reference.
164 SmallMap map = ftl::init::map('a', 'A')('b', 'B')('c', 'C');
165
166 const auto opt = map.get('c');
167 EXPECT_EQ(opt, 'C');
168
169 char d = 'd';
170 const auto ref = map.get('d').value_or(std::ref(d));
171 ref.get() = 'D';
172 EXPECT_EQ(d, 'D');
173 }
174 {
175 // Constant unary operation.
176 const SmallMap map = ftl::init::map('a', 'x')('b', 'y')('c', 'z');
177 EXPECT_EQ(map.get('c', [](char c) { return std::toupper(c); }), 'Z');
178 }
179 {
180 // Mutable unary operation.
181 SmallMap map = ftl::init::map('a', 'x')('b', 'y')('c', 'z');
182 EXPECT_TRUE(map.get('c', [](char& c) { c = std::toupper(c); }));
183
184 EXPECT_EQ(map, SmallMap(ftl::init::map('c', 'Z')('b', 'y')('a', 'x')));
185 }
186 }
187
TEST(SmallMap,TryEmplace)188 TEST(SmallMap, TryEmplace) {
189 SmallMap<int, std::string, 3> map;
190 using Pair = decltype(map)::value_type;
191
192 {
193 const auto [it, ok] = map.try_emplace(123, "abc");
194 ASSERT_TRUE(ok);
195 EXPECT_EQ(*it, Pair(123, "abc"s));
196 }
197 {
198 const auto [it, ok] = map.try_emplace(42, 3u, '?');
199 ASSERT_TRUE(ok);
200 EXPECT_EQ(*it, Pair(42, "???"s));
201 }
202 {
203 const auto [it, ok] = map.try_emplace(-1);
204 ASSERT_TRUE(ok);
205 EXPECT_EQ(*it, Pair(-1, std::string()));
206 EXPECT_FALSE(map.dynamic());
207 }
208 {
209 // Insertion fails if mapping exists.
210 const auto [it, ok] = map.try_emplace(42, "!!!");
211 EXPECT_FALSE(ok);
212 EXPECT_EQ(*it, Pair(42, "???"));
213 EXPECT_FALSE(map.dynamic());
214 }
215 {
216 // Insertion at capacity promotes the map.
217 const auto [it, ok] = map.try_emplace(999, "xyz");
218 ASSERT_TRUE(ok);
219 EXPECT_EQ(*it, Pair(999, "xyz"));
220 EXPECT_TRUE(map.dynamic());
221 }
222
223 EXPECT_EQ(map, SmallMap(ftl::init::map(-1, ""s)(42, "???"s)(123, "abc"s)(999, "xyz"s)));
224 }
225
226 namespace {
227
228 // The mapped type does not require a copy/move assignment operator.
229 struct String {
230 template <typename... Args>
Stringandroid::test::__anone2f4cf050411::String231 String(Args... args) : str(args...) {}
232 const std::string str;
233
operator ==android::test::__anone2f4cf050411::String234 bool operator==(const String& other) const { return other.str == str; }
235 };
236
237 } // namespace
238
TEST(SmallMap,TryReplace)239 TEST(SmallMap, TryReplace) {
240 SmallMap<int, String, 3> map = ftl::init::map(1, "a")(2, "B");
241 using Pair = decltype(map)::value_type;
242
243 {
244 // Replacing fails unless mapping exists.
245 const auto it = map.try_replace(3, "c");
246 EXPECT_EQ(it, map.end());
247 }
248 {
249 // Replacement arguments can refer to the replaced mapping.
250 const auto ref = map.get(2, [](const auto& s) { return s.str[0]; });
251 ASSERT_TRUE(ref);
252
253 // Construct std::string from one character.
254 const auto it = map.try_replace(2, 1u, static_cast<char>(std::tolower(*ref)));
255 ASSERT_NE(it, map.end());
256 EXPECT_EQ(*it, Pair(2, "b"));
257 }
258
259 EXPECT_FALSE(map.dynamic());
260 EXPECT_TRUE(map.try_emplace(3, "abc").second);
261 EXPECT_TRUE(map.try_emplace(4, "d").second);
262 EXPECT_TRUE(map.dynamic());
263
264 {
265 // Replacing fails unless mapping exists.
266 const auto it = map.try_replace(5, "e");
267 EXPECT_EQ(it, map.end());
268 }
269 {
270 // Replacement arguments can refer to the replaced mapping.
271 const auto ref = map.get(3);
272 ASSERT_TRUE(ref);
273
274 // Construct std::string from substring.
275 const auto it = map.try_replace(3, ref->get().str, 2u, 1u);
276 ASSERT_NE(it, map.end());
277 EXPECT_EQ(*it, Pair(3, "c"));
278 }
279
280 EXPECT_EQ(map, SmallMap(ftl::init::map(4, "d"s)(3, "c"s)(2, "b"s)(1, "a"s)));
281 }
282
TEST(SmallMap,EmplaceOrReplace)283 TEST(SmallMap, EmplaceOrReplace) {
284 SmallMap<int, String, 3> map = ftl::init::map(1, "a")(2, "B");
285 using Pair = decltype(map)::value_type;
286
287 {
288 // New mapping is emplaced.
289 const auto [it, emplace] = map.emplace_or_replace(3, "c");
290 EXPECT_TRUE(emplace);
291 EXPECT_EQ(*it, Pair(3, "c"));
292 }
293 {
294 // Replacement arguments can refer to the replaced mapping.
295 const auto ref = map.get(2, [](const auto& s) { return s.str[0]; });
296 ASSERT_TRUE(ref);
297
298 // Construct std::string from one character.
299 const auto [it, emplace] = map.emplace_or_replace(2, 1u, static_cast<char>(std::tolower(*ref)));
300 EXPECT_FALSE(emplace);
301 EXPECT_EQ(*it, Pair(2, "b"));
302 }
303
304 EXPECT_FALSE(map.dynamic());
305 EXPECT_FALSE(map.emplace_or_replace(3, "abc").second); // Replace.
306 EXPECT_TRUE(map.emplace_or_replace(4, "d").second); // Emplace.
307 EXPECT_TRUE(map.dynamic());
308
309 {
310 // New mapping is emplaced.
311 const auto [it, emplace] = map.emplace_or_replace(5, "e");
312 EXPECT_TRUE(emplace);
313 EXPECT_EQ(*it, Pair(5, "e"));
314 }
315 {
316 // Replacement arguments can refer to the replaced mapping.
317 const auto ref = map.get(3);
318 ASSERT_TRUE(ref);
319
320 // Construct std::string from substring.
321 const auto [it, emplace] = map.emplace_or_replace(3, ref->get().str, 2u, 1u);
322 EXPECT_FALSE(emplace);
323 EXPECT_EQ(*it, Pair(3, "c"));
324 }
325
326 EXPECT_EQ(map, SmallMap(ftl::init::map(5, "e"s)(4, "d"s)(3, "c"s)(2, "b"s)(1, "a"s)));
327 }
328
TEST(SmallMap,Erase)329 TEST(SmallMap, Erase) {
330 {
331 SmallMap map = ftl::init::map(1, '1')(2, '2')(3, '3')(4, '4');
332 EXPECT_FALSE(map.dynamic());
333
334 EXPECT_FALSE(map.erase(0)); // Key not found.
335
336 EXPECT_TRUE(map.erase(2));
337 EXPECT_EQ(map, SmallMap(ftl::init::map(1, '1')(3, '3')(4, '4')));
338
339 EXPECT_TRUE(map.erase(1));
340 EXPECT_EQ(map, SmallMap(ftl::init::map(3, '3')(4, '4')));
341
342 EXPECT_TRUE(map.erase(4));
343 EXPECT_EQ(map, SmallMap(ftl::init::map(3, '3')));
344
345 EXPECT_TRUE(map.erase(3));
346 EXPECT_FALSE(map.erase(3)); // Key not found.
347
348 EXPECT_TRUE(map.empty());
349 EXPECT_FALSE(map.dynamic());
350 }
351 {
352 SmallMap map = ftl::init::map(1, '1')(2, '2')(3, '3');
353 map.try_emplace(4, '4');
354 EXPECT_TRUE(map.dynamic());
355
356 EXPECT_FALSE(map.erase(0)); // Key not found.
357
358 EXPECT_TRUE(map.erase(2));
359 EXPECT_EQ(map, SmallMap(ftl::init::map(1, '1')(3, '3')(4, '4')));
360
361 EXPECT_TRUE(map.erase(1));
362 EXPECT_EQ(map, SmallMap(ftl::init::map(3, '3')(4, '4')));
363
364 EXPECT_TRUE(map.erase(4));
365 EXPECT_EQ(map, SmallMap(ftl::init::map(3, '3')));
366
367 EXPECT_TRUE(map.erase(3));
368 EXPECT_FALSE(map.erase(3)); // Key not found.
369
370 EXPECT_TRUE(map.empty());
371 EXPECT_TRUE(map.dynamic());
372 }
373 }
374
TEST(SmallMap,Clear)375 TEST(SmallMap, Clear) {
376 SmallMap map = ftl::init::map(1, '1')(2, '2')(3, '3');
377
378 map.clear();
379
380 EXPECT_TRUE(map.empty());
381 EXPECT_FALSE(map.dynamic());
382
383 map = ftl::init::map(1, '1')(2, '2')(3, '3');
384 map.try_emplace(4, '4');
385
386 map.clear();
387
388 EXPECT_TRUE(map.empty());
389 EXPECT_TRUE(map.dynamic());
390 }
391
TEST(SmallMap,KeyEqual)392 TEST(SmallMap, KeyEqual) {
393 struct KeyEqual {
394 bool operator()(int lhs, int rhs) const { return lhs % 10 == rhs % 10; }
395 };
396
397 SmallMap<int, char, 1, KeyEqual> map;
398
399 EXPECT_TRUE(map.try_emplace(3, '3').second);
400 EXPECT_FALSE(map.try_emplace(13, '3').second);
401
402 EXPECT_TRUE(map.try_emplace(22, '2').second);
403 EXPECT_TRUE(map.contains(42));
404
405 EXPECT_TRUE(map.try_emplace(111, '1').second);
406 EXPECT_EQ(map.get(321), '1');
407
408 map.erase(123);
409 EXPECT_EQ(map, SmallMap(ftl::init::map<int, char, KeyEqual>(1, '1')(2, '2')));
410 }
411
412 } // namespace android::test
413