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