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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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