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 1000ms
457   int execution_time_per_cycle_us = 15;
458   EXPECT_LT(execution_time, execution_time_per_cycle_us * capacity);
459 }
460 
461 }  // namespace testing
462