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