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 
192 template <typename Capacity>
193 struct SmallMapTest : testing::Test {
194   static constexpr std::size_t kCapacity = Capacity{}();
195 };
196 
197 template <std::size_t N>
198 using Capacity = std::integral_constant<std::size_t, N>;
199 
200 using Capacities = testing::Types<Capacity<3>, Capacity<0>>;
201 TYPED_TEST_SUITE(SmallMapTest, Capacities, );
202 
TYPED_TEST(SmallMapTest,TryEmplace)203 TYPED_TEST(SmallMapTest, TryEmplace) {
204   SmallMap<int, std::string, TestFixture::kCapacity> map;
205   using Pair = typename decltype(map)::value_type;
206 
207   {
208     const auto [it, ok] = map.try_emplace(123, "abc");
209     ASSERT_TRUE(ok);
210     EXPECT_EQ(*it, Pair(123, "abc"s));
211   }
212   {
213     const auto [it, ok] = map.try_emplace(42, 3u, '?');
214     ASSERT_TRUE(ok);
215     EXPECT_EQ(*it, Pair(42, "???"s));
216   }
217   {
218     const auto [it, ok] = map.try_emplace(-1);
219     ASSERT_TRUE(ok);
220     EXPECT_EQ(*it, Pair(-1, std::string()));
221     if constexpr (map.static_capacity() > 0) {
222       EXPECT_FALSE(map.dynamic());
223     } else {
224       EXPECT_TRUE(map.dynamic());
225     }
226   }
227   {
228     // Insertion fails if mapping exists.
229     const auto [it, ok] = map.try_emplace(42, "!!!");
230     EXPECT_FALSE(ok);
231     EXPECT_EQ(*it, Pair(42, "???"));
232     if constexpr (map.static_capacity() > 0) {
233       EXPECT_FALSE(map.dynamic());
234     } else {
235       EXPECT_TRUE(map.dynamic());
236     }
237   }
238   {
239     // Insertion at capacity promotes the map.
240     const auto [it, ok] = map.try_emplace(999, "xyz");
241     ASSERT_TRUE(ok);
242     EXPECT_EQ(*it, Pair(999, "xyz"));
243     EXPECT_TRUE(map.dynamic());
244   }
245 
246   EXPECT_EQ(map, SmallMap(ftl::init::map(-1, ""s)(42, "???"s)(123, "abc"s)(999, "xyz"s)));
247 }
248 
249 namespace {
250 
251 // The mapped type does not require a copy/move assignment operator.
252 struct String {
253   template <typename... Args>
Stringandroid::test::__anon7b907c590411::String254   String(Args... args) : str(args...) {}
255   const std::string str;
256 
operator ==android::test::__anon7b907c590411::String257   bool operator==(const String& other) const { return other.str == str; }
258 };
259 
260 }  // namespace
261 
TYPED_TEST(SmallMapTest,TryReplace)262 TYPED_TEST(SmallMapTest, TryReplace) {
263   SmallMap<int, String, TestFixture::kCapacity> map = ftl::init::map(1, "a")(2, "B");
264   using Pair = typename decltype(map)::value_type;
265 
266   {
267     // Replacing fails unless mapping exists.
268     const auto it = map.try_replace(3, "c");
269     EXPECT_EQ(it, map.end());
270   }
271   {
272     // Replacement arguments can refer to the replaced mapping.
273     const auto ref = map.get(2).transform([](const String& s) { return s.str[0]; });
274     ASSERT_TRUE(ref);
275 
276     // Construct std::string from one character.
277     const auto it = map.try_replace(2, 1u, static_cast<char>(std::tolower(*ref)));
278     ASSERT_NE(it, map.end());
279     EXPECT_EQ(*it, Pair(2, "b"));
280   }
281 
282   if constexpr (map.static_capacity() > 0) {
283     EXPECT_FALSE(map.dynamic());
284   } else {
285     EXPECT_TRUE(map.dynamic());
286   }
287 
288   EXPECT_TRUE(map.try_emplace(3, "abc").second);
289   EXPECT_TRUE(map.try_emplace(4, "d").second);
290   EXPECT_TRUE(map.dynamic());
291 
292   {
293     // Replacing fails unless mapping exists.
294     const auto it = map.try_replace(5, "e");
295     EXPECT_EQ(it, map.end());
296   }
297   {
298     // Replacement arguments can refer to the replaced mapping.
299     const auto ref = map.get(3);
300     ASSERT_TRUE(ref);
301 
302     // Construct std::string from substring.
303     const auto it = map.try_replace(3, ref->get().str, 2u, 1u);
304     ASSERT_NE(it, map.end());
305     EXPECT_EQ(*it, Pair(3, "c"));
306   }
307 
308   EXPECT_EQ(map, SmallMap(ftl::init::map(4, "d"s)(3, "c"s)(2, "b"s)(1, "a"s)));
309 }
310 
TYPED_TEST(SmallMapTest,EmplaceOrReplace)311 TYPED_TEST(SmallMapTest, EmplaceOrReplace) {
312   SmallMap<int, String, TestFixture::kCapacity> map = ftl::init::map(1, "a")(2, "B");
313   using Pair = typename decltype(map)::value_type;
314 
315   {
316     // New mapping is emplaced.
317     const auto [it, emplace] = map.emplace_or_replace(3, "c");
318     EXPECT_TRUE(emplace);
319     EXPECT_EQ(*it, Pair(3, "c"));
320   }
321   {
322     // Replacement arguments can refer to the replaced mapping.
323     const auto ref = map.get(2).transform([](const String& s) { return s.str[0]; });
324     ASSERT_TRUE(ref);
325 
326     // Construct std::string from one character.
327     const auto [it, emplace] = map.emplace_or_replace(2, 1u, static_cast<char>(std::tolower(*ref)));
328     EXPECT_FALSE(emplace);
329     EXPECT_EQ(*it, Pair(2, "b"));
330   }
331 
332   if constexpr (map.static_capacity() > 0) {
333     EXPECT_FALSE(map.dynamic());
334   } else {
335     EXPECT_TRUE(map.dynamic());
336   }
337 
338   EXPECT_FALSE(map.emplace_or_replace(3, "abc").second);  // Replace.
339   EXPECT_TRUE(map.emplace_or_replace(4, "d").second);     // Emplace.
340   EXPECT_TRUE(map.dynamic());
341 
342   {
343     // New mapping is emplaced.
344     const auto [it, emplace] = map.emplace_or_replace(5, "e");
345     EXPECT_TRUE(emplace);
346     EXPECT_EQ(*it, Pair(5, "e"));
347   }
348   {
349     // Replacement arguments can refer to the replaced mapping.
350     const auto ref = map.get(3);
351     ASSERT_TRUE(ref);
352 
353     // Construct std::string from substring.
354     const auto [it, emplace] = map.emplace_or_replace(3, ref->get().str, 2u, 1u);
355     EXPECT_FALSE(emplace);
356     EXPECT_EQ(*it, Pair(3, "c"));
357   }
358 
359   EXPECT_EQ(map, SmallMap(ftl::init::map(5, "e"s)(4, "d"s)(3, "c"s)(2, "b"s)(1, "a"s)));
360 }
361 
TEST(SmallMap,Erase)362 TEST(SmallMap, Erase) {
363   {
364     SmallMap map = ftl::init::map(1, '1')(2, '2')(3, '3')(4, '4');
365     EXPECT_FALSE(map.dynamic());
366 
367     EXPECT_FALSE(map.erase(0));  // Key not found.
368 
369     EXPECT_TRUE(map.erase(2));
370     EXPECT_EQ(map, SmallMap(ftl::init::map(1, '1')(3, '3')(4, '4')));
371 
372     EXPECT_TRUE(map.erase(1));
373     EXPECT_EQ(map, SmallMap(ftl::init::map(3, '3')(4, '4')));
374 
375     EXPECT_TRUE(map.erase(4));
376     EXPECT_EQ(map, SmallMap(ftl::init::map(3, '3')));
377 
378     EXPECT_TRUE(map.erase(3));
379     EXPECT_FALSE(map.erase(3));  // Key not found.
380 
381     EXPECT_TRUE(map.empty());
382     EXPECT_FALSE(map.dynamic());
383   }
384   {
385     SmallMap map = ftl::init::map(1, '1')(2, '2')(3, '3');
386     map.try_emplace(4, '4');
387     EXPECT_TRUE(map.dynamic());
388 
389     EXPECT_FALSE(map.erase(0));  // Key not found.
390 
391     EXPECT_TRUE(map.erase(2));
392     EXPECT_EQ(map, SmallMap(ftl::init::map(1, '1')(3, '3')(4, '4')));
393 
394     EXPECT_TRUE(map.erase(1));
395     EXPECT_EQ(map, SmallMap(ftl::init::map(3, '3')(4, '4')));
396 
397     EXPECT_TRUE(map.erase(4));
398     EXPECT_EQ(map, SmallMap(ftl::init::map(3, '3')));
399 
400     EXPECT_TRUE(map.erase(3));
401     EXPECT_FALSE(map.erase(3));  // Key not found.
402 
403     EXPECT_TRUE(map.empty());
404     EXPECT_TRUE(map.dynamic());
405   }
406 }
407 
TEST(SmallMap,Clear)408 TEST(SmallMap, Clear) {
409   SmallMap map = ftl::init::map(1, '1')(2, '2')(3, '3');
410 
411   map.clear();
412 
413   EXPECT_TRUE(map.empty());
414   EXPECT_FALSE(map.dynamic());
415 
416   map = ftl::init::map(1, '1')(2, '2')(3, '3');
417   map.try_emplace(4, '4');
418 
419   map.clear();
420 
421   EXPECT_TRUE(map.empty());
422   EXPECT_TRUE(map.dynamic());
423 }
424 
TEST(SmallMap,KeyEqual)425 TEST(SmallMap, KeyEqual) {
426   struct KeyEqual {
427     bool operator()(int lhs, int rhs) const { return lhs % 10 == rhs % 10; }
428   };
429 
430   SmallMap<int, char, 1, KeyEqual> map;
431 
432   EXPECT_TRUE(map.try_emplace(3, '3').second);
433   EXPECT_FALSE(map.try_emplace(13, '3').second);
434 
435   EXPECT_TRUE(map.try_emplace(22, '2').second);
436   EXPECT_TRUE(map.contains(42));
437 
438   EXPECT_TRUE(map.try_emplace(111, '1').second);
439   EXPECT_EQ(map.get(321), '1');
440 
441   map.erase(123);
442   EXPECT_EQ(map, SmallMap(ftl::init::map<int, char, KeyEqual>(1, '1')(2, '2')));
443 }
444 
445 }  // namespace android::test
446