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 <limits>
19
20 #include <gmock/gmock.h>
21 #include <gtest/gtest.h>
22
23 #include "common/lru_cache.h"
24
25 namespace testing {
26
27 using bluetooth::common::LruCache;
28
TEST(LruCacheTest,empty_test)29 TEST(LruCacheTest, empty_test) {
30 LruCache<int, int> cache(3); // capacity = 3;
31 EXPECT_EQ(cache.size(), 0);
32 EXPECT_EQ(cache.find(42), cache.end());
33 cache.clear(); // should not crash
34 EXPECT_EQ(cache.find(42), cache.end());
35 EXPECT_FALSE(cache.contains(42));
36 EXPECT_FALSE(cache.extract(42));
37 }
38
TEST(LruCacheTest,comparison_test)39 TEST(LruCacheTest, comparison_test) {
40 LruCache<int, int> cache_1(2);
41 cache_1.insert_or_assign(1, 10);
42 cache_1.insert_or_assign(2, 20);
43 LruCache<int, int> cache_2(2);
44 cache_2.insert_or_assign(1, 10);
45 cache_2.insert_or_assign(2, 20);
46 EXPECT_EQ(cache_1, cache_2);
47 // Cache with different order should not be equal
48 cache_2.find(1);
49 EXPECT_NE(cache_1, cache_2);
50 cache_1.find(1);
51 EXPECT_EQ(cache_1, cache_2);
52 // Cache with different value should be different
53 cache_2.insert_or_assign(1, 11);
54 EXPECT_NE(cache_1, cache_2);
55 // Cache with different capacity should not be equal
56 LruCache<int, int> cache_3(3);
57 cache_3.insert_or_assign(1, 10);
58 cache_3.insert_or_assign(2, 20);
59 EXPECT_NE(cache_1, cache_3);
60 // Empty cache should not be equal to non-empty ones
61 LruCache<int, int> cache_4(2);
62 EXPECT_NE(cache_1, cache_4);
63 // Empty caches should be equal
64 LruCache<int, int> cache_5(2);
65 EXPECT_EQ(cache_4, cache_5);
66 // Empty caches with different capacity should not be equal
67 LruCache<int, int> cache_6(3);
68 EXPECT_NE(cache_4, cache_6);
69 }
70
TEST(LruCacheTest,try_emplace_test)71 TEST(LruCacheTest, try_emplace_test) {
72 LruCache<int, int> cache(2);
73 cache.insert_or_assign(1, 10);
74 cache.insert_or_assign(2, 20);
75 auto result = cache.try_emplace(42, 420);
76 // 1, 10 evicted
77 EXPECT_EQ(std::get<2>(result), std::make_pair(1, 10));
78 auto iter = cache.find(42);
79 EXPECT_EQ(iter->second, 420);
80 EXPECT_EQ(iter, std::get<0>(result));
81 ASSERT_THAT(cache, ElementsAre(Pair(42, 420), Pair(2, 20)));
82 }
83
TEST(LruCacheTest,copy_test)84 TEST(LruCacheTest, copy_test) {
85 LruCache<int, std::shared_ptr<int>> cache(2);
86 cache.insert_or_assign(1, std::make_shared<int>(100));
87 auto iter = cache.find(1);
88 EXPECT_EQ(*iter->second, 100);
89 LruCache<int, std::shared_ptr<int>> new_cache = cache;
90 iter = new_cache.find(1);
91 EXPECT_EQ(*iter->second, 100);
92 *iter->second = 300;
93 iter = new_cache.find(1);
94 EXPECT_EQ(*iter->second, 300);
95 // Since copy is used, shared_ptr should increase count
96 EXPECT_EQ(iter->second.use_count(), 2);
97 }
98
TEST(LruCacheTest,move_test)99 TEST(LruCacheTest, move_test) {
100 LruCache<int, std::shared_ptr<int>> cache(2);
101 cache.insert_or_assign(1, std::make_shared<int>(100));
102 auto iter = cache.find(1);
103 EXPECT_EQ(*iter->second, 100);
104 LruCache<int, std::shared_ptr<int>> new_cache = std::move(cache);
105 iter = new_cache.find(1);
106 EXPECT_EQ(*iter->second, 100);
107 *iter->second = 300;
108 iter = new_cache.find(1);
109 EXPECT_EQ(*iter->second, 300);
110 // Since move is used, shared_ptr should not increase count
111 EXPECT_EQ(iter->second.use_count(), 1);
112 }
113
TEST(LruCacheTest,move_insert_unique_ptr_test)114 TEST(LruCacheTest, move_insert_unique_ptr_test) {
115 LruCache<int, std::unique_ptr<int>> cache(2);
116 cache.insert_or_assign(1, std::make_unique<int>(100));
117 auto iter = cache.find(1);
118 EXPECT_EQ(*iter->second, 100);
119 cache.insert_or_assign(1, std::make_unique<int>(400));
120 iter = cache.find(1);
121 EXPECT_EQ(*iter->second, 400);
122 }
123
TEST(LruCacheTest,move_insert_cache_test)124 TEST(LruCacheTest, move_insert_cache_test) {
125 LruCache<int, LruCache<int, int>> cache(2);
126 LruCache<int, int> m1(2);
127 m1.insert_or_assign(1, 100);
128 cache.insert_or_assign(1, std::move(m1));
129 auto iter = cache.find(1);
130 EXPECT_THAT(iter->second, ElementsAre(Pair(1, 100)));
131 LruCache<int, int> m2(2);
132 m2.insert_or_assign(2, 200);
133 cache.insert_or_assign(1, std::move(m2));
134 iter = cache.find(1);
135 EXPECT_THAT(iter->second, ElementsAre(Pair(2, 200)));
136 }
137
TEST(LruCacheTest,erase_one_item_test)138 TEST(LruCacheTest, erase_one_item_test) {
139 LruCache<int, int> cache(3);
140 cache.insert_or_assign(1, 10);
141 cache.insert_or_assign(2, 20);
142 cache.insert_or_assign(3, 30);
143 auto iter = cache.find(2);
144 // 2, 3, 1
145 cache.find(3);
146 // 3, 2, 1
147 iter = cache.erase(iter);
148 EXPECT_EQ(iter->first, 1);
149 EXPECT_EQ(iter->second, 10);
150 EXPECT_THAT(cache, ElementsAre(Pair(3, 30), Pair(1, 10)));
151 }
152
TEST(LruCacheTest,erase_in_for_loop_test)153 TEST(LruCacheTest, erase_in_for_loop_test) {
154 LruCache<int, int> cache(3);
155 cache.insert_or_assign(1, 10);
156 cache.insert_or_assign(2, 20);
157 cache.insert_or_assign(3, 30);
158 for (auto iter = cache.begin(); iter != cache.end();) {
159 if (iter->first == 2) {
160 iter = cache.erase(iter);
161 } else {
162 ++iter;
163 }
164 }
165 EXPECT_THAT(cache, ElementsAre(Pair(3, 30), Pair(1, 10)));
166 }
167
TEST(LruCacheTest,get_and_contains_key_test)168 TEST(LruCacheTest, get_and_contains_key_test) {
169 LruCache<int, int> cache(3); // capacity = 3;
170 EXPECT_EQ(cache.size(), 0);
171 EXPECT_EQ(cache.find(42), cache.end());
172 EXPECT_FALSE(cache.contains(42));
173 EXPECT_FALSE(cache.insert_or_assign(56, 200));
174 EXPECT_EQ(cache.find(42), cache.end());
175 EXPECT_FALSE(cache.contains(42));
176 EXPECT_NE(cache.find(56), cache.end());
177 EXPECT_TRUE(cache.contains(56));
178 auto iter = cache.find(56);
179 EXPECT_NE(iter, cache.end());
180 EXPECT_EQ(iter->second, 200);
181 EXPECT_TRUE(cache.extract(56));
182 EXPECT_FALSE(cache.contains(56));
183 }
184
TEST(LruCacheTest,put_and_get_sequence_1)185 TEST(LruCacheTest, put_and_get_sequence_1) {
186 // Section 1: Ordered put and ordered get
187 LruCache<int, int> cache(3); // capacity = 3;
188 EXPECT_FALSE(cache.insert_or_assign(1, 10));
189 EXPECT_EQ(cache.size(), 1);
190 EXPECT_FALSE(cache.insert_or_assign(2, 20));
191 EXPECT_EQ(cache.size(), 2);
192 EXPECT_FALSE(cache.insert_or_assign(3, 30));
193 EXPECT_EQ(cache.size(), 3);
194 // 3, 2, 1 after above operations
195
196 auto evicted = cache.insert_or_assign(4, 40);
197 // 4, 3, 2 after above operations, 1 is evicted
198 EXPECT_TRUE(evicted);
199 EXPECT_EQ(*evicted, std::make_pair(1, 10));
200 EXPECT_EQ(cache.find(1), cache.end());
201 LruCache<int, int>::const_iterator iter;
202 EXPECT_NE(iter = cache.find(4), cache.end());
203 EXPECT_EQ(iter->second, 40);
204 EXPECT_NE(iter = cache.find(2), cache.end());
205 EXPECT_EQ(iter->second, 20);
206 EXPECT_NE(iter = cache.find(3), cache.end());
207 EXPECT_EQ(iter->second, 30);
208 // 3, 2, 4 after above operations
209
210 // Section 2: Over capacity put and ordered get
211 evicted = cache.insert_or_assign(5, 50);
212 // 5, 3, 2 after above operations, 4 is evicted
213 EXPECT_EQ(cache.size(), 3);
214 EXPECT_TRUE(evicted);
215 EXPECT_EQ(*evicted, std::make_pair(4, 40));
216
217 EXPECT_TRUE(cache.extract(3));
218 // 5, 2 should be in cache, 3 is removed
219 EXPECT_FALSE(cache.insert_or_assign(6, 60));
220 // 6, 5, 2 should be in cache
221
222 // Section 3: Out of order get
223 EXPECT_EQ(cache.find(3), cache.end());
224 EXPECT_EQ(cache.find(4), cache.end());
225 EXPECT_NE(iter = cache.find(2), cache.end());
226 // 2, 6, 5 should be in cache
227 EXPECT_EQ(iter->second, 20);
228 EXPECT_NE(iter = cache.find(6), cache.end());
229 // 6, 2, 5 should be in cache
230 EXPECT_EQ(iter->second, 60);
231 EXPECT_NE(iter = cache.find(5), cache.end());
232 // 5, 6, 2 should be in cache
233 EXPECT_EQ(iter->second, 50);
234 evicted = cache.insert_or_assign(7, 70);
235 // 7, 5, 6 should be in cache, 2 is evicted
236 EXPECT_TRUE(evicted);
237 EXPECT_EQ(*evicted, std::make_pair(2, 20));
238 }
239
TEST(LruCacheTest,put_and_get_sequence_2)240 TEST(LruCacheTest, put_and_get_sequence_2) {
241 // Section 1: Replace item in cache
242 LruCache<int, int> cache(2); // size = 2;
243 EXPECT_FALSE(cache.insert_or_assign(1, 10));
244 EXPECT_FALSE(cache.insert_or_assign(2, 20));
245 // 2, 1 in cache
246 auto evicted = cache.insert_or_assign(3, 30);
247 // 3, 2 in cache, 1 is evicted
248 EXPECT_TRUE(evicted);
249 EXPECT_EQ(*evicted, std::make_pair(1, 10));
250 EXPECT_FALSE(cache.insert_or_assign(2, 200));
251 // 2, 3 in cache, nothing is evicted
252 EXPECT_EQ(cache.size(), 2);
253
254 EXPECT_FALSE(cache.contains(1));
255 LruCache<int, int>::const_iterator iter;
256 EXPECT_NE(iter = cache.find(2), cache.end());
257 EXPECT_EQ(iter->second, 200);
258 EXPECT_NE(iter = cache.find(3), cache.end());
259 // 3, 2 in cache
260 EXPECT_EQ(iter->second, 30);
261
262 evicted = cache.insert_or_assign(4, 40);
263 // 4, 3 in cache, 2 is evicted
264 EXPECT_TRUE(evicted);
265 EXPECT_EQ(*evicted, std::make_pair(2, 200));
266
267 EXPECT_FALSE(cache.contains(2));
268 EXPECT_NE(iter = cache.find(3), cache.end());
269 EXPECT_EQ(iter->second, 30);
270 EXPECT_NE(iter = cache.find(4), cache.end());
271 EXPECT_EQ(iter->second, 40);
272 // 4, 3 in cache
273
274 EXPECT_TRUE(cache.extract(4));
275 EXPECT_FALSE(cache.contains(4));
276 // 3 in cache
277 EXPECT_EQ(cache.size(), 1);
278 EXPECT_FALSE(cache.insert_or_assign(2, 2000));
279 // 2, 3 in cache
280
281 EXPECT_FALSE(cache.contains(4));
282 EXPECT_NE(iter = cache.find(3), cache.end());
283 EXPECT_EQ(iter->second, 30);
284 EXPECT_NE(iter = cache.find(2), cache.end());
285 EXPECT_EQ(iter->second, 2000);
286
287 EXPECT_TRUE(cache.extract(2));
288 EXPECT_TRUE(cache.extract(3));
289 EXPECT_FALSE(cache.insert_or_assign(5, 50));
290 EXPECT_FALSE(cache.insert_or_assign(1, 100));
291 EXPECT_FALSE(cache.insert_or_assign(5, 1000));
292 EXPECT_EQ(cache.size(), 2);
293 // 5, 1 in cache
294
295 evicted = cache.insert_or_assign(6, 2000);
296 // 6, 5 in cache
297 EXPECT_TRUE(evicted);
298 EXPECT_EQ(*evicted, std::make_pair(1, 100));
299
300 EXPECT_FALSE(cache.contains(2));
301 EXPECT_FALSE(cache.contains(3));
302 EXPECT_NE(iter = cache.find(6), cache.end());
303 EXPECT_EQ(iter->second, 2000);
304 EXPECT_NE(iter = cache.find(5), cache.end());
305 EXPECT_EQ(iter->second, 1000);
306 }
307
TEST(LruCacheTest,in_place_modification_test)308 TEST(LruCacheTest, in_place_modification_test) {
309 LruCache<int, int> cache(2);
310 cache.insert_or_assign(1, 10);
311 cache.insert_or_assign(2, 20);
312 auto iter = cache.find(2);
313 ASSERT_THAT(cache, ElementsAre(Pair(2, 20), Pair(1, 10)));
314 iter->second = 200;
315 ASSERT_THAT(cache, ElementsAre(Pair(2, 200), Pair(1, 10)));
316 cache.insert_or_assign(1, 100);
317 // 1, 2 in cache
318 ASSERT_THAT(cache, ElementsAre(Pair(1, 100), Pair(2, 200)));
319 // modifying iterator does not warm up key
320 iter->second = 400;
321 ASSERT_THAT(cache, ElementsAre(Pair(1, 100), Pair(2, 400)));
322 }
323
TEST(LruCacheTest,get_test)324 TEST(LruCacheTest, get_test) {
325 LruCache<int, int> cache(2);
326 EXPECT_FALSE(cache.insert_or_assign(1, 10));
327 EXPECT_FALSE(cache.insert_or_assign(2, 20));
328 EXPECT_TRUE(cache.contains(1));
329 // 1, 2 in cache
330 auto evicted = cache.insert_or_assign(3, 30);
331 // 3, 1 in cache
332 EXPECT_TRUE(evicted);
333 EXPECT_EQ(*evicted, std::make_pair(2, 20));
334 }
335
TEST(LruCacheTest,remove_test)336 TEST(LruCacheTest, remove_test) {
337 LruCache<int, int> cache(10);
338 for (int key = 0; key <= 30; key++) {
339 cache.insert_or_assign(key, key * 100);
340 }
341 for (int key = 0; key <= 20; key++) {
342 EXPECT_FALSE(cache.contains(key));
343 }
344 for (int key = 21; key <= 30; key++) {
345 EXPECT_TRUE(cache.contains(key));
346 }
347 for (int key = 0; key <= 20; key++) {
348 EXPECT_FALSE(cache.extract(key));
349 }
350 for (int key = 21; key <= 30; key++) {
351 auto removed = cache.extract(key);
352 EXPECT_TRUE(removed);
353 EXPECT_EQ(*removed, std::make_pair(key, key * 100));
354 }
355 for (int key = 21; key <= 30; key++) {
356 EXPECT_FALSE(cache.contains(key));
357 }
358 }
359
TEST(LruCacheTest,clear_test)360 TEST(LruCacheTest, clear_test) {
361 LruCache<int, int> cache(10);
362 for (int key = 0; key < 10; key++) {
363 cache.insert_or_assign(key, key * 100);
364 }
365 for (int key = 0; key < 10; key++) {
366 EXPECT_TRUE(cache.contains(key));
367 }
368 cache.clear();
369 for (int key = 0; key < 10; key++) {
370 EXPECT_FALSE(cache.contains(key));
371 }
372
373 for (int key = 0; key < 10; key++) {
374 cache.insert_or_assign(key, key * 1000);
375 }
376 for (int key = 0; key < 10; key++) {
377 EXPECT_TRUE(cache.contains(key));
378 }
379 }
380
TEST(LruCacheTest,container_test)381 TEST(LruCacheTest, container_test) {
382 LruCache<int, int> lru_cache(2);
383 lru_cache.insert_or_assign(1, 10);
384 lru_cache.insert_or_assign(2, 20);
385 // Warm elements first
386 ASSERT_THAT(lru_cache, ElementsAre(Pair(2, 20), Pair(1, 10)));
387 }
388
TEST(LruCacheTest,iterator_test)389 TEST(LruCacheTest, iterator_test) {
390 LruCache<int, int> lru_cache(2);
391 lru_cache.insert_or_assign(1, 10);
392 lru_cache.insert_or_assign(2, 20);
393 // Warm elements first
394 std::list<std::pair<int, int>> list(lru_cache.begin(), lru_cache.end());
395 ASSERT_THAT(list, ElementsAre(Pair(2, 20), Pair(1, 10)));
396 }
397
TEST(LruCacheTest,for_loop_test)398 TEST(LruCacheTest, for_loop_test) {
399 LruCache<int, int> lru_cache(2);
400 lru_cache.insert_or_assign(1, 10);
401 lru_cache.insert_or_assign(2, 20);
402 // Warm elements first
403 std::list<std::pair<int, int>> list;
404 for (const auto& node : lru_cache) {
405 list.emplace_back(node);
406 }
407 ASSERT_THAT(list, ElementsAre(Pair(2, 20), Pair(1, 10)));
408 list.clear();
409 for (auto& node : lru_cache) {
410 list.emplace_back(node);
411 node.second = node.second * 2;
412 }
413 ASSERT_THAT(list, ElementsAre(Pair(2, 20), Pair(1, 10)));
414 list.clear();
415 for (const auto& node : lru_cache) {
416 list.emplace_back(node);
417 }
418 ASSERT_THAT(list, ElementsAre(Pair(2, 40), Pair(1, 20)));
419 }
420
TEST(LruCacheTest,pressure_test)421 TEST(LruCacheTest, pressure_test) {
422 auto started = std::chrono::high_resolution_clock::now();
423 int capacity = 0xFFFF; // 2^16 = 65535
424 LruCache<int, int> cache(static_cast<size_t>(capacity));
425
426 // fill the cache
427 for (int key = 0; key < capacity; key++) {
428 cache.insert_or_assign(key, key);
429 }
430
431 // make sure the cache is full
432 for (int key = 0; key < capacity; key++) {
433 EXPECT_TRUE(cache.contains(key));
434 }
435
436 // refresh the entire cache
437 for (int key = 0; key < capacity; key++) {
438 int new_key = key + capacity;
439 cache.insert_or_assign(new_key, new_key);
440 EXPECT_FALSE(cache.contains(key));
441 EXPECT_TRUE(cache.contains(new_key));
442 }
443
444 // clear the entire cache
445 LruCache<int, int>::const_iterator iter;
446 for (int key = capacity; key < 2 * capacity; key++) {
447 EXPECT_NE(iter = cache.find(key), cache.end());
448 EXPECT_EQ(iter->second, key);
449 EXPECT_TRUE(cache.extract(key));
450 }
451 EXPECT_EQ(cache.size(), 0);
452
453 // test execution time
454 auto done = std::chrono::high_resolution_clock::now();
455 int execution_time = std::chrono::duration_cast<std::chrono::microseconds>(done - started).count();
456 // Shouldn't be more than 1120ms
457 int execution_time_per_cycle_us = 17;
458 EXPECT_LT(execution_time, execution_time_per_cycle_us * capacity);
459 }
460
461 } // namespace testing
462