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