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 "common/list_map.h"
18 
19 #include <gmock/gmock.h>
20 #include <gtest/gtest.h>
21 
22 #include <memory>
23 
24 namespace testing {
25 
26 using bluetooth::common::ListMap;
27 
TEST(ListMapTest,empty_test)28 TEST(ListMapTest, empty_test) {
29   ListMap<int, int> list_map;
30   EXPECT_EQ(list_map.size(), 0ul);
31   EXPECT_EQ(list_map.find(42), list_map.end());
32   list_map.clear();  // should not crash
33   EXPECT_EQ(list_map.find(42), list_map.end());
34   EXPECT_FALSE(list_map.contains(42));
35   EXPECT_FALSE(list_map.extract(42));
36 }
37 
TEST(ListMapTest,comparison_test)38 TEST(ListMapTest, comparison_test) {
39   ListMap<int, int> list_map_1;
40   list_map_1.insert_or_assign(1, 10);
41   list_map_1.insert_or_assign(2, 20);
42   ListMap<int, int> list_map_2;
43   list_map_2.insert_or_assign(1, 10);
44   list_map_2.insert_or_assign(2, 20);
45   EXPECT_EQ(list_map_1, list_map_2);
46   // List map with different value should be different
47   list_map_2.insert_or_assign(1, 11);
48   EXPECT_NE(list_map_1, list_map_2);
49   // List maps with different order should not be equal
50   ListMap<int, int> list_map_3;
51   list_map_3.insert_or_assign(2, 20);
52   list_map_3.insert_or_assign(1, 10);
53   EXPECT_NE(list_map_1, list_map_3);
54   // Empty list map should not be equal to non-empty ones
55   ListMap<int, int> list_map_4;
56   EXPECT_NE(list_map_1, list_map_4);
57   // Empty list maps should be equal
58   ListMap<int, int> list_map_5;
59   EXPECT_EQ(list_map_4, list_map_5);
60 }
61 
TEST(ListMapTest,copy_test)62 TEST(ListMapTest, copy_test) {
63   ListMap<int, std::shared_ptr<int>> list_map;
64   list_map.insert_or_assign(1, std::make_shared<int>(100));
65   auto iter = list_map.find(1);
66   EXPECT_EQ(*iter->second, 100);
67   ListMap<int, std::shared_ptr<int>> new_list_map = list_map;
68   iter = new_list_map.find(1);
69   EXPECT_EQ(*iter->second, 100);
70   *iter->second = 300;
71   iter = new_list_map.find(1);
72   EXPECT_EQ(*iter->second, 300);
73   // Since copy is used, shared_ptr should increase count
74   EXPECT_EQ(iter->second.use_count(), 2);
75 }
76 
TEST(ListMapTest,move_test)77 TEST(ListMapTest, move_test) {
78   ListMap<int, std::shared_ptr<int>> list_map;
79   list_map.insert_or_assign(1, std::make_shared<int>(100));
80   auto iter = list_map.find(1);
81   EXPECT_EQ(*iter->second, 100);
82   ListMap<int, std::shared_ptr<int>> new_list_map = std::move(list_map);
83   iter = new_list_map.find(1);
84   EXPECT_EQ(*iter->second, 100);
85   *iter->second = 300;
86   iter = new_list_map.find(1);
87   EXPECT_EQ(*iter->second, 300);
88   // Since move is used, shared_ptr should not increase count
89   EXPECT_EQ(iter->second.use_count(), 1);
90 }
91 
TEST(ListMapTest,move_insert_unique_ptr_test)92 TEST(ListMapTest, move_insert_unique_ptr_test) {
93   ListMap<int, std::unique_ptr<int>> list_map;
94   list_map.insert_or_assign(1, std::make_unique<int>(100));
95   auto iter = list_map.find(1);
96   EXPECT_EQ(*iter->second, 100);
97   list_map.insert_or_assign(1, std::make_unique<int>(400));
98   iter = list_map.find(1);
99   EXPECT_EQ(*iter->second, 400);
100 }
101 
TEST(ListMapTest,move_insert_list_map_test)102 TEST(ListMapTest, move_insert_list_map_test) {
103   ListMap<int, ListMap<int, int>> list_map;
104   ListMap<int, int> m1;
105   m1.insert_or_assign(1, 100);
106   list_map.insert_or_assign(1, std::move(m1));
107   auto iter = list_map.find(1);
108   EXPECT_THAT(iter->second, ElementsAre(Pair(1, 100)));
109   ListMap<int, int> m2;
110   m2.insert_or_assign(2, 200);
111   list_map.insert_or_assign(1, std::move(m2));
112   iter = list_map.find(1);
113   EXPECT_THAT(iter->second, ElementsAre(Pair(2, 200)));
114 }
115 
TEST(ListMapTest,erase_one_item_test)116 TEST(ListMapTest, erase_one_item_test) {
117   ListMap<int, int> list_map;
118   list_map.insert_or_assign(1, 10);
119   list_map.insert_or_assign(2, 20);
120   list_map.insert_or_assign(3, 30);
121   auto iter = list_map.find(2);
122   iter = list_map.erase(iter);
123   EXPECT_EQ(iter->first, 3);
124   EXPECT_EQ(iter->second, 30);
125 }
126 
TEST(ListMapTest,erase_in_for_loop_test)127 TEST(ListMapTest, erase_in_for_loop_test) {
128   ListMap<int, int> list_map;
129   list_map.insert_or_assign(1, 10);
130   list_map.insert_or_assign(2, 20);
131   list_map.insert_or_assign(3, 30);
132   for (auto iter = list_map.begin(); iter != list_map.end();) {
133     if (iter->first == 2) {
134       iter = list_map.erase(iter);
135     } else {
136       ++iter;
137     }
138   }
139   EXPECT_THAT(list_map, ElementsAre(Pair(1, 10), Pair(3, 30)));
140 }
141 
TEST(ListMapTest,splice_different_list_test)142 TEST(ListMapTest, splice_different_list_test) {
143   ListMap<int, int> list_map;
144   list_map.insert_or_assign(1, 10);
145   list_map.insert_or_assign(2, 20);
146   list_map.insert_or_assign(3, 30);
147   ListMap<int, int> list_map_2;
148   list_map_2.insert_or_assign(4, 40);
149   list_map_2.insert_or_assign(5, 50);
150   list_map.splice(list_map.find(2), list_map_2, list_map_2.find(4));
151   EXPECT_EQ(list_map_2.find(4), list_map_2.end());
152   auto iter = list_map.find(4);
153   EXPECT_NE(iter, list_map.end());
154   EXPECT_EQ(iter->second, 40);
155   EXPECT_THAT(list_map, ElementsAre(Pair(1, 10), Pair(4, 40), Pair(2, 20), Pair(3, 30)));
156 }
157 
TEST(ListMapTest,splice_same_list_test)158 TEST(ListMapTest, splice_same_list_test) {
159   ListMap<int, int> list_map;
160   list_map.insert_or_assign(1, 10);
161   list_map.insert_or_assign(2, 20);
162   list_map.insert_or_assign(3, 30);
163   list_map.splice(list_map.find(2), list_map, list_map.find(3));
164   EXPECT_THAT(list_map, ElementsAre(Pair(1, 10), Pair(3, 30), Pair(2, 20)));
165   list_map.extract(2);
166   list_map.insert_or_assign(list_map.begin(), 4, 40);
167   EXPECT_THAT(list_map, ElementsAre(Pair(4, 40), Pair(1, 10), Pair(3, 30)));
168   auto iter = list_map.find(4);
169   EXPECT_EQ(iter->second, 40);
170   list_map.splice(list_map.begin(), list_map, list_map.find(4));
171   list_map.splice(list_map.begin(), list_map, list_map.find(3));
172   list_map.splice(list_map.begin(), list_map, list_map.find(1));
173   EXPECT_THAT(list_map, ElementsAre(Pair(1, 10), Pair(3, 30), Pair(4, 40)));
174   iter = list_map.find(4);
175   EXPECT_EQ(iter->second, 40);
176   iter = list_map.find(3);
177   EXPECT_EQ(iter->second, 30);
178 }
179 
TEST(ListMapTest,put_get_and_contains_key_test)180 TEST(ListMapTest, put_get_and_contains_key_test) {
181   ListMap<int, int> list_map;
182   EXPECT_EQ(list_map.size(), 0ul);
183   EXPECT_EQ(list_map.find(42), list_map.end());
184   EXPECT_FALSE(list_map.contains(42));
185   list_map.insert_or_assign(56, 200);
186   EXPECT_EQ(list_map.find(42), list_map.end());
187   EXPECT_FALSE(list_map.contains(42));
188   auto iter = list_map.find(56);
189   EXPECT_NE(iter, list_map.end());
190   EXPECT_TRUE(list_map.contains(56));
191   EXPECT_EQ(iter->second, 200);
192   EXPECT_TRUE(list_map.extract(56));
193   EXPECT_FALSE(list_map.contains(56));
194 }
195 
TEST(ListMapTest,try_emplace_at_position_test)196 TEST(ListMapTest, try_emplace_at_position_test) {
197   ListMap<int, int> list_map;
198   list_map.insert_or_assign(1, 10);
199   list_map.insert_or_assign(2, 20);
200   auto iter = list_map.find(2);
201   EXPECT_EQ(iter->second, 20);
202   auto result = list_map.try_emplace(iter, 42, 420);
203   EXPECT_TRUE(result.second);
204   iter = list_map.find(42);
205   EXPECT_EQ(iter->second, 420);
206   EXPECT_EQ(iter, result.first);
207   ASSERT_THAT(list_map, ElementsAre(Pair(1, 10), Pair(42, 420), Pair(2, 20)));
208   EXPECT_FALSE(list_map.try_emplace(result.first, 42, 420).second);
209 }
210 
TEST(ListMapTest,try_emplace_back_test)211 TEST(ListMapTest, try_emplace_back_test) {
212   ListMap<int, int> list_map;
213   list_map.insert_or_assign(1, 10);
214   list_map.insert_or_assign(2, 20);
215   auto result = list_map.try_emplace_back(42, 420);
216   EXPECT_TRUE(result.second);
217   auto iter = list_map.find(42);
218   EXPECT_EQ(iter->second, 420);
219   EXPECT_EQ(iter, result.first);
220   ASSERT_THAT(list_map, ElementsAre(Pair(1, 10), Pair(2, 20), Pair(42, 420)));
221   EXPECT_FALSE(list_map.try_emplace_back(42, 420).second);
222 }
223 
TEST(ListMapTest,insert_at_position_test)224 TEST(ListMapTest, insert_at_position_test) {
225   ListMap<int, int> list_map;
226   list_map.insert_or_assign(1, 10);
227   list_map.insert_or_assign(2, 20);
228   auto iter = list_map.find(2);
229   EXPECT_EQ(iter->second, 20);
230   list_map.insert_or_assign(iter, 42, 420);
231   iter = list_map.find(42);
232   EXPECT_EQ(iter->second, 420);
233   ASSERT_THAT(list_map, ElementsAre(Pair(1, 10), Pair(42, 420), Pair(2, 20)));
234 }
235 
TEST(ListMapTest,in_place_modification_test)236 TEST(ListMapTest, in_place_modification_test) {
237   ListMap<int, int> list_map;
238   list_map.insert_or_assign(1, 10);
239   list_map.insert_or_assign(2, 20);
240   auto iter = list_map.find(2);
241   iter->second = 200;
242   ASSERT_THAT(list_map, ElementsAre(Pair(1, 10), Pair(2, 200)));
243 }
244 
TEST(ListMapTest,get_test)245 TEST(ListMapTest, get_test) {
246   ListMap<int, int> list_map;
247   list_map.insert_or_assign(1, 10);
248   list_map.insert_or_assign(2, 20);
249   auto iter = list_map.find(1);
250   EXPECT_NE(iter, list_map.end());
251   EXPECT_EQ(iter->second, 10);
252 }
253 
TEST(ListMapTest,remove_test)254 TEST(ListMapTest, remove_test) {
255   ListMap<int, int> list_map;
256   for (int key = 0; key <= 30; key++) {
257     list_map.insert_or_assign(key, key * 100);
258   }
259   for (int key = 0; key <= 30; key++) {
260     EXPECT_TRUE(list_map.contains(key));
261   }
262   for (int key = 0; key <= 30; key++) {
263     auto removed = list_map.extract(key);
264     EXPECT_TRUE(removed);
265     EXPECT_EQ(*removed, std::make_pair(key, key * 100));
266   }
267   for (int key = 0; key <= 30; key++) {
268     EXPECT_FALSE(list_map.contains(key));
269   }
270 }
271 
TEST(ListMapTest,clear_test)272 TEST(ListMapTest, clear_test) {
273   ListMap<int, int> list_map;
274   for (int key = 0; key < 10; key++) {
275     list_map.insert_or_assign(key, key * 100);
276   }
277   for (int key = 0; key < 10; key++) {
278     EXPECT_TRUE(list_map.contains(key));
279   }
280   list_map.clear();
281   for (int key = 0; key < 10; key++) {
282     EXPECT_FALSE(list_map.contains(key));
283   }
284 
285   for (int key = 0; key < 10; key++) {
286     list_map.insert_or_assign(key, key * 1000);
287   }
288   for (int key = 0; key < 10; key++) {
289     EXPECT_TRUE(list_map.contains(key));
290   }
291 }
292 
TEST(ListMapTest,container_test)293 TEST(ListMapTest, container_test) {
294   ListMap<int, int> list_map;
295   list_map.insert_or_assign(1, 10);
296   list_map.insert_or_assign(2, 20);
297   ASSERT_THAT(list_map, ElementsAre(Pair(1, 10), Pair(2, 20)));
298 }
299 
TEST(ListMapTest,iterator_test)300 TEST(ListMapTest, iterator_test) {
301   ListMap<int, int> list_map;
302   list_map.insert_or_assign(1, 10);
303   list_map.insert_or_assign(2, 20);
304   std::list<std::pair<int, int>> list(list_map.begin(), list_map.end());
305   ASSERT_THAT(list, ElementsAre(Pair(1, 10), Pair(2, 20)));
306 }
307 
TEST(ListMapTest,for_loop_test)308 TEST(ListMapTest, for_loop_test) {
309   ListMap<int, int> list_map;
310   list_map.insert_or_assign(1, 10);
311   list_map.insert_or_assign(2, 20);
312   std::list<std::pair<int, int>> list;
313   for (const auto& node : list_map) {
314     list.emplace_back(node);
315   }
316   ASSERT_THAT(list, ElementsAre(Pair(1, 10), Pair(2, 20)));
317   list.clear();
318   for (auto& node : list_map) {
319     list.emplace_back(node);
320     node.second = node.second * 2;
321   }
322   ASSERT_THAT(list, ElementsAre(Pair(1, 10), Pair(2, 20)));
323   list.clear();
324   for (const auto& node : list_map) {
325     list.emplace_back(node);
326   }
327   ASSERT_THAT(list, ElementsAre(Pair(1, 20), Pair(2, 40)));
328 }
329 
TEST(ListMapTest,pressure_test)330 TEST(ListMapTest, pressure_test) {
331   int num_entries = 0xFFFF;  // 2^16 = 65535
332   ListMap<int, int> list_map;
333 
334   // fill the list_map
335   for (int key = 0; key < num_entries; key++) {
336     list_map.insert_or_assign(key, key);
337   }
338 
339   // make sure the list_map is full
340   for (int key = 0; key < num_entries; key++) {
341     EXPECT_TRUE(list_map.contains(key));
342   }
343 
344   // clear the entire list_map
345   for (int key = 0; key < num_entries; key++) {
346     auto iter = list_map.find(key);
347     EXPECT_NE(iter, list_map.end());
348     EXPECT_EQ(iter->second, key);
349     EXPECT_TRUE(list_map.extract(key));
350   }
351   EXPECT_EQ(list_map.size(), 0ul);
352 }
353 
354 }  // namespace testing
355