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