lru_cache_unittest.cc 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597
  1. // Copyright (c) 2011 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #include "base/containers/lru_cache.h"
  5. #include <cstddef>
  6. #include <memory>
  7. #include <string>
  8. #include "base/memory/ref_counted.h"
  9. #include "base/memory/scoped_refptr.h"
  10. #include "base/tracing_buildflags.h"
  11. #include "testing/gtest/include/gtest/gtest.h"
  12. #if BUILDFLAG(ENABLE_BASE_TRACING)
  13. #include "base/trace_event/memory_usage_estimator.h" // no-presubmit-check
  14. #endif // BUILDFLAG(ENABLE_BASE_TRACING)
  15. namespace base {
  16. namespace {
  17. int cached_item_live_count = 0;
  18. struct CachedItem {
  19. CachedItem() : value(0) { cached_item_live_count++; }
  20. explicit CachedItem(int new_value) : value(new_value) {
  21. cached_item_live_count++;
  22. }
  23. CachedItem(const CachedItem& other) : value(other.value) {
  24. cached_item_live_count++;
  25. }
  26. ~CachedItem() { cached_item_live_count--; }
  27. int value;
  28. };
  29. } // namespace
  30. template <typename LRUCacheTemplate>
  31. class LRUCacheTest : public testing::Test {};
  32. struct LRUCacheTemplate {
  33. template <class Key, class Value, class KeyCompare = std::less<Key>>
  34. using Type = base::LRUCache<Key, Value, KeyCompare>;
  35. };
  36. struct HashingLRUCacheTemplate {
  37. template <class Key,
  38. class Value,
  39. class KeyHash = std::hash<Key>,
  40. class KeyEqual = std::equal_to<Key>>
  41. using Type = base::HashingLRUCache<Key, Value, KeyHash, KeyEqual>;
  42. };
  43. using LRUCacheTemplates =
  44. testing::Types<LRUCacheTemplate, HashingLRUCacheTemplate>;
  45. TYPED_TEST_SUITE(LRUCacheTest, LRUCacheTemplates);
  46. template <typename LRUCacheSetTemplate>
  47. class LRUCacheSetTest : public testing::Test {};
  48. struct LRUCacheSetTemplate {
  49. template <class Value, class Compare = std::less<Value>>
  50. using Type = base::LRUCacheSet<Value, Compare>;
  51. };
  52. struct HashingLRUCacheSetTemplate {
  53. template <class Value,
  54. class Hash = std::hash<Value>,
  55. class Equal = std::equal_to<Value>>
  56. using Type = base::HashingLRUCacheSet<Value, Hash, Equal>;
  57. };
  58. using LRUCacheSetTemplates =
  59. testing::Types<LRUCacheSetTemplate, HashingLRUCacheSetTemplate>;
  60. TYPED_TEST_SUITE(LRUCacheSetTest, LRUCacheSetTemplates);
  61. TYPED_TEST(LRUCacheTest, Basic) {
  62. typedef typename TypeParam::template Type<int, CachedItem> Cache;
  63. Cache cache(Cache::NO_AUTO_EVICT);
  64. // Check failure conditions
  65. {
  66. CachedItem test_item;
  67. EXPECT_TRUE(cache.Get(0) == cache.end());
  68. EXPECT_TRUE(cache.Peek(0) == cache.end());
  69. }
  70. static const int kItem1Key = 5;
  71. CachedItem item1(10);
  72. auto inserted_item = cache.Put(kItem1Key, item1);
  73. EXPECT_EQ(1U, cache.size());
  74. // Check that item1 was properly inserted.
  75. {
  76. auto found = cache.Get(kItem1Key);
  77. EXPECT_TRUE(inserted_item == cache.begin());
  78. EXPECT_TRUE(found != cache.end());
  79. found = cache.Peek(kItem1Key);
  80. EXPECT_TRUE(found != cache.end());
  81. EXPECT_EQ(kItem1Key, found->first);
  82. EXPECT_EQ(item1.value, found->second.value);
  83. }
  84. static const int kItem2Key = 7;
  85. CachedItem item2(12);
  86. cache.Put(kItem2Key, item2);
  87. EXPECT_EQ(2U, cache.size());
  88. // Check that item1 is the oldest since item2 was added afterwards.
  89. {
  90. auto oldest = cache.rbegin();
  91. ASSERT_TRUE(oldest != cache.rend());
  92. EXPECT_EQ(kItem1Key, oldest->first);
  93. EXPECT_EQ(item1.value, oldest->second.value);
  94. }
  95. // Check that item1 is still accessible by key.
  96. {
  97. auto test_item = cache.Get(kItem1Key);
  98. ASSERT_TRUE(test_item != cache.end());
  99. EXPECT_EQ(kItem1Key, test_item->first);
  100. EXPECT_EQ(item1.value, test_item->second.value);
  101. }
  102. // Check that retrieving item1 pushed item2 to oldest.
  103. {
  104. auto oldest = cache.rbegin();
  105. ASSERT_TRUE(oldest != cache.rend());
  106. EXPECT_EQ(kItem2Key, oldest->first);
  107. EXPECT_EQ(item2.value, oldest->second.value);
  108. }
  109. // Remove the oldest item and check that item1 is now the only member.
  110. {
  111. auto next = cache.Erase(cache.rbegin());
  112. EXPECT_EQ(1U, cache.size());
  113. EXPECT_TRUE(next == cache.rbegin());
  114. EXPECT_EQ(kItem1Key, next->first);
  115. EXPECT_EQ(item1.value, next->second.value);
  116. cache.Erase(cache.begin());
  117. EXPECT_EQ(0U, cache.size());
  118. }
  119. // Check that Clear() works properly.
  120. cache.Put(kItem1Key, item1);
  121. cache.Put(kItem2Key, item2);
  122. EXPECT_EQ(2U, cache.size());
  123. cache.Clear();
  124. EXPECT_EQ(0U, cache.size());
  125. }
  126. TYPED_TEST(LRUCacheTest, GetVsPeek) {
  127. typedef typename TypeParam::template Type<int, CachedItem> Cache;
  128. Cache cache(Cache::NO_AUTO_EVICT);
  129. static const int kItem1Key = 1;
  130. CachedItem item1(10);
  131. cache.Put(kItem1Key, item1);
  132. static const int kItem2Key = 2;
  133. CachedItem item2(20);
  134. cache.Put(kItem2Key, item2);
  135. // This should do nothing since the size is bigger than the number of items.
  136. cache.ShrinkToSize(100);
  137. // Check that item1 starts out as oldest
  138. {
  139. auto iter = cache.rbegin();
  140. ASSERT_TRUE(iter != cache.rend());
  141. EXPECT_EQ(kItem1Key, iter->first);
  142. EXPECT_EQ(item1.value, iter->second.value);
  143. }
  144. // Check that Peek doesn't change ordering
  145. {
  146. auto peekiter = cache.Peek(kItem1Key);
  147. ASSERT_TRUE(peekiter != cache.end());
  148. auto iter = cache.rbegin();
  149. ASSERT_TRUE(iter != cache.rend());
  150. EXPECT_EQ(kItem1Key, iter->first);
  151. EXPECT_EQ(item1.value, iter->second.value);
  152. }
  153. }
  154. TYPED_TEST(LRUCacheTest, KeyReplacement) {
  155. typedef typename TypeParam::template Type<int, CachedItem> Cache;
  156. Cache cache(Cache::NO_AUTO_EVICT);
  157. static const int kItem1Key = 1;
  158. CachedItem item1(10);
  159. cache.Put(kItem1Key, item1);
  160. static const int kItem2Key = 2;
  161. CachedItem item2(20);
  162. cache.Put(kItem2Key, item2);
  163. static const int kItem3Key = 3;
  164. CachedItem item3(30);
  165. cache.Put(kItem3Key, item3);
  166. static const int kItem4Key = 4;
  167. CachedItem item4(40);
  168. cache.Put(kItem4Key, item4);
  169. CachedItem item5(50);
  170. cache.Put(kItem3Key, item5);
  171. EXPECT_EQ(4U, cache.size());
  172. for (int i = 0; i < 3; ++i) {
  173. auto iter = cache.rbegin();
  174. ASSERT_TRUE(iter != cache.rend());
  175. }
  176. // Make it so only the most important element is there.
  177. cache.ShrinkToSize(1);
  178. auto iter = cache.begin();
  179. EXPECT_EQ(kItem3Key, iter->first);
  180. EXPECT_EQ(item5.value, iter->second.value);
  181. }
  182. // Make sure that the cache release its pointers properly.
  183. TYPED_TEST(LRUCacheTest, Owning) {
  184. using Cache =
  185. typename TypeParam::template Type<int, std::unique_ptr<CachedItem>>;
  186. Cache cache(Cache::NO_AUTO_EVICT);
  187. int initial_count = cached_item_live_count;
  188. // First insert and item and then overwrite it.
  189. static const int kItem1Key = 1;
  190. cache.Put(kItem1Key, std::make_unique<CachedItem>(20));
  191. cache.Put(kItem1Key, std::make_unique<CachedItem>(22));
  192. // There should still be one item, and one extra live item.
  193. auto iter = cache.Get(kItem1Key);
  194. EXPECT_EQ(1U, cache.size());
  195. EXPECT_TRUE(iter != cache.end());
  196. EXPECT_EQ(initial_count + 1, cached_item_live_count);
  197. // Now remove it.
  198. cache.Erase(cache.begin());
  199. EXPECT_EQ(initial_count, cached_item_live_count);
  200. // Now try another cache that goes out of scope to make sure its pointers
  201. // go away.
  202. {
  203. Cache cache2(Cache::NO_AUTO_EVICT);
  204. cache2.Put(1, std::make_unique<CachedItem>(20));
  205. cache2.Put(2, std::make_unique<CachedItem>(20));
  206. }
  207. // There should be no objects leaked.
  208. EXPECT_EQ(initial_count, cached_item_live_count);
  209. // Check that Clear() also frees things correctly.
  210. {
  211. Cache cache2(Cache::NO_AUTO_EVICT);
  212. cache2.Put(1, std::make_unique<CachedItem>(20));
  213. cache2.Put(2, std::make_unique<CachedItem>(20));
  214. EXPECT_EQ(initial_count + 2, cached_item_live_count);
  215. cache2.Clear();
  216. EXPECT_EQ(initial_count, cached_item_live_count);
  217. }
  218. }
  219. TYPED_TEST(LRUCacheTest, AutoEvict) {
  220. using Cache =
  221. typename TypeParam::template Type<int, std::unique_ptr<CachedItem>>;
  222. static const typename Cache::size_type kMaxSize = 3;
  223. int initial_count = cached_item_live_count;
  224. {
  225. Cache cache(kMaxSize);
  226. static const int kItem1Key = 1, kItem2Key = 2, kItem3Key = 3, kItem4Key = 4;
  227. cache.Put(kItem1Key, std::make_unique<CachedItem>(20));
  228. cache.Put(kItem2Key, std::make_unique<CachedItem>(21));
  229. cache.Put(kItem3Key, std::make_unique<CachedItem>(22));
  230. cache.Put(kItem4Key, std::make_unique<CachedItem>(23));
  231. // The cache should only have kMaxSize items in it even though we inserted
  232. // more.
  233. EXPECT_EQ(kMaxSize, cache.size());
  234. }
  235. // There should be no objects leaked.
  236. EXPECT_EQ(initial_count, cached_item_live_count);
  237. }
  238. TYPED_TEST(LRUCacheTest, HashingLRUCache) {
  239. // Very simple test to make sure that the hashing cache works correctly.
  240. typedef typename TypeParam::template Type<std::string, CachedItem> Cache;
  241. Cache cache(Cache::NO_AUTO_EVICT);
  242. CachedItem one(1);
  243. cache.Put("First", one);
  244. CachedItem two(2);
  245. cache.Put("Second", two);
  246. EXPECT_EQ(one.value, cache.Get("First")->second.value);
  247. EXPECT_EQ(two.value, cache.Get("Second")->second.value);
  248. cache.ShrinkToSize(1);
  249. EXPECT_EQ(two.value, cache.Get("Second")->second.value);
  250. EXPECT_TRUE(cache.Get("First") == cache.end());
  251. }
  252. TYPED_TEST(LRUCacheTest, Swap) {
  253. typedef typename TypeParam::template Type<int, CachedItem> Cache;
  254. Cache cache1(Cache::NO_AUTO_EVICT);
  255. // Insert two items into cache1.
  256. static const int kItem1Key = 1;
  257. CachedItem item1(2);
  258. auto inserted_item = cache1.Put(kItem1Key, item1);
  259. EXPECT_EQ(1U, cache1.size());
  260. static const int kItem2Key = 3;
  261. CachedItem item2(4);
  262. cache1.Put(kItem2Key, item2);
  263. EXPECT_EQ(2U, cache1.size());
  264. // Verify cache1's elements.
  265. {
  266. auto iter = cache1.begin();
  267. ASSERT_TRUE(iter != cache1.end());
  268. EXPECT_EQ(kItem2Key, iter->first);
  269. EXPECT_EQ(item2.value, iter->second.value);
  270. ++iter;
  271. ASSERT_TRUE(iter != cache1.end());
  272. EXPECT_EQ(kItem1Key, iter->first);
  273. EXPECT_EQ(item1.value, iter->second.value);
  274. }
  275. // Create another cache2.
  276. Cache cache2(Cache::NO_AUTO_EVICT);
  277. // Insert three items into cache2.
  278. static const int kItem3Key = 5;
  279. CachedItem item3(6);
  280. inserted_item = cache2.Put(kItem3Key, item3);
  281. EXPECT_EQ(1U, cache2.size());
  282. static const int kItem4Key = 7;
  283. CachedItem item4(8);
  284. cache2.Put(kItem4Key, item4);
  285. EXPECT_EQ(2U, cache2.size());
  286. static const int kItem5Key = 9;
  287. CachedItem item5(10);
  288. cache2.Put(kItem5Key, item5);
  289. EXPECT_EQ(3U, cache2.size());
  290. // Verify cache2's elements.
  291. {
  292. auto iter = cache2.begin();
  293. ASSERT_TRUE(iter != cache2.end());
  294. EXPECT_EQ(kItem5Key, iter->first);
  295. EXPECT_EQ(item5.value, iter->second.value);
  296. ++iter;
  297. ASSERT_TRUE(iter != cache2.end());
  298. EXPECT_EQ(kItem4Key, iter->first);
  299. EXPECT_EQ(item4.value, iter->second.value);
  300. ++iter;
  301. ASSERT_TRUE(iter != cache2.end());
  302. EXPECT_EQ(kItem3Key, iter->first);
  303. EXPECT_EQ(item3.value, iter->second.value);
  304. }
  305. // Swap cache1 and cache2 and verify cache2 has cache1's elements and cache1
  306. // has cache2's elements.
  307. cache2.Swap(cache1);
  308. EXPECT_EQ(3U, cache1.size());
  309. EXPECT_EQ(2U, cache2.size());
  310. // Verify cache1's elements.
  311. {
  312. auto iter = cache1.begin();
  313. ASSERT_TRUE(iter != cache1.end());
  314. EXPECT_EQ(kItem5Key, iter->first);
  315. EXPECT_EQ(item5.value, iter->second.value);
  316. ++iter;
  317. ASSERT_TRUE(iter != cache1.end());
  318. EXPECT_EQ(kItem4Key, iter->first);
  319. EXPECT_EQ(item4.value, iter->second.value);
  320. ++iter;
  321. ASSERT_TRUE(iter != cache1.end());
  322. EXPECT_EQ(kItem3Key, iter->first);
  323. EXPECT_EQ(item3.value, iter->second.value);
  324. }
  325. // Verify cache2's elements.
  326. {
  327. auto iter = cache2.begin();
  328. ASSERT_TRUE(iter != cache2.end());
  329. EXPECT_EQ(kItem2Key, iter->first);
  330. EXPECT_EQ(item2.value, iter->second.value);
  331. ++iter;
  332. ASSERT_TRUE(iter != cache2.end());
  333. EXPECT_EQ(kItem1Key, iter->first);
  334. EXPECT_EQ(item1.value, iter->second.value);
  335. }
  336. }
  337. TYPED_TEST(LRUCacheSetTest, SetTest) {
  338. typedef typename TypeParam::template Type<std::string> Cache;
  339. Cache cache(Cache::NO_AUTO_EVICT);
  340. cache.Put("Hello");
  341. cache.Put("world");
  342. cache.Put("foo");
  343. cache.Put("bar");
  344. // Insert a duplicate element
  345. cache.Put("foo");
  346. // Iterate from oldest to newest
  347. auto r_iter = cache.rbegin();
  348. EXPECT_EQ(*r_iter, "Hello");
  349. ++r_iter;
  350. EXPECT_EQ(*r_iter, "world");
  351. ++r_iter;
  352. EXPECT_EQ(*r_iter, "bar");
  353. ++r_iter;
  354. EXPECT_EQ(*r_iter, "foo");
  355. ++r_iter;
  356. EXPECT_EQ(r_iter, cache.rend());
  357. // Iterate from newest to oldest
  358. auto iter = cache.begin();
  359. EXPECT_EQ(*iter, "foo");
  360. ++iter;
  361. EXPECT_EQ(*iter, "bar");
  362. ++iter;
  363. EXPECT_EQ(*iter, "world");
  364. ++iter;
  365. EXPECT_EQ(*iter, "Hello");
  366. ++iter;
  367. EXPECT_EQ(iter, cache.end());
  368. }
  369. // Generalized dereference function. For the base case, this is the identity
  370. // function.
  371. template <typename T>
  372. struct Deref {
  373. using Target = T;
  374. static const Target& deref(const T& x) { return x; }
  375. };
  376. // `RefCountedData` wraps a type in an interface that supports refcounting.
  377. // Deref this as the wrapped type.
  378. template <typename T>
  379. struct Deref<RefCountedData<T>> {
  380. using Target = typename Deref<T>::Target;
  381. static const Target& deref(const RefCountedData<T>& x) {
  382. return Deref<T>::deref(x.data);
  383. }
  384. };
  385. // `scoped_refptr` is a smart pointer that implements reference counting.
  386. // Deref this as the pointee.
  387. template <typename T>
  388. struct Deref<scoped_refptr<T>> {
  389. using Target = typename Deref<T>::Target;
  390. static const Target& deref(const scoped_refptr<T>& x) {
  391. return Deref<T>::deref(*x);
  392. }
  393. };
  394. // Implementation of a `std::less`-like type that dereferences the given values
  395. // before comparison.
  396. template <typename T>
  397. struct DerefCompare {
  398. bool operator()(const T& lhs, const T& rhs) const {
  399. return Deref<T>::deref(lhs) < Deref<T>::deref(rhs);
  400. }
  401. };
  402. // Implementation of a `std::equal_to`-like type that dereferences the given
  403. // values before comparison.
  404. template <typename T>
  405. struct DerefEqual {
  406. bool operator()(const T& lhs, const T& rhs) const {
  407. return Deref<T>::deref(lhs) == Deref<T>::deref(rhs);
  408. }
  409. };
  410. // Implementation of a `std::hash`-like type that dereferences the given value
  411. // before calculating the hash.
  412. template <typename T, template <class> typename HashT = std::hash>
  413. struct DerefHash {
  414. size_t operator()(const T& x) const {
  415. return HashT<typename Deref<T>::Target>()(Deref<T>::deref(x));
  416. }
  417. };
  418. // This tests that upon replacing a duplicate element in the cache with `Put`,
  419. // the element's identity is replaced as well.
  420. TYPED_TEST(LRUCacheSetTest, ReplacementIdentity) {
  421. using Item = RefCountedData<std::string>;
  422. using Ptr = scoped_refptr<Item>;
  423. // Helper to create the correct type of base::*LRUCacheSet, since they have
  424. // different template arguments.
  425. constexpr auto kCreateCache = []() {
  426. if constexpr (std::is_same_v<TypeParam, LRUCacheSetTemplate>) {
  427. using Cache = typename TypeParam::template Type<Ptr, DerefCompare<Ptr>>;
  428. return Cache(Cache::NO_AUTO_EVICT);
  429. } else if constexpr (std::is_same_v<TypeParam,
  430. HashingLRUCacheSetTemplate>) {
  431. using Cache = typename TypeParam::template Type<Ptr, DerefHash<Ptr>,
  432. DerefEqual<Ptr>>;
  433. return Cache(Cache::NO_AUTO_EVICT);
  434. } else {
  435. static_assert(!sizeof(TypeParam),
  436. "This test was only written to support "
  437. "`LRUCacheSetTemplate` and `HashingLRUCacheSetTemplate`");
  438. }
  439. };
  440. auto cache = kCreateCache();
  441. cache.Put(MakeRefCounted<Item>("Hello"));
  442. cache.Put(MakeRefCounted<Item>("world"));
  443. cache.Put(MakeRefCounted<Item>("foo"));
  444. cache.Put(MakeRefCounted<Item>("bar"));
  445. // Insert a duplicate element
  446. {
  447. auto foo = MakeRefCounted<Item>("foo");
  448. const auto* new_foo_addr = foo.get();
  449. const auto* old_foo_addr = cache.Peek(foo)->get();
  450. auto iter = cache.Put(std::move(foo));
  451. EXPECT_EQ(iter->get(), new_foo_addr);
  452. EXPECT_NE(iter->get(), old_foo_addr);
  453. }
  454. // Iterate from oldest to newest
  455. auto r_iter = cache.rbegin();
  456. EXPECT_EQ((*r_iter)->data, "Hello");
  457. ++r_iter;
  458. EXPECT_EQ((*r_iter)->data, "world");
  459. ++r_iter;
  460. EXPECT_EQ((*r_iter)->data, "bar");
  461. ++r_iter;
  462. EXPECT_EQ((*r_iter)->data, "foo");
  463. ++r_iter;
  464. EXPECT_EQ(r_iter, cache.rend());
  465. // Iterate from newest to oldest
  466. auto iter = cache.begin();
  467. EXPECT_EQ((*iter)->data, "foo");
  468. ++iter;
  469. EXPECT_EQ((*iter)->data, "bar");
  470. ++iter;
  471. EXPECT_EQ((*iter)->data, "world");
  472. ++iter;
  473. EXPECT_EQ((*iter)->data, "Hello");
  474. ++iter;
  475. EXPECT_EQ(iter, cache.end());
  476. }
  477. #if BUILDFLAG(ENABLE_BASE_TRACING)
  478. TYPED_TEST(LRUCacheTest, EstimateMemory) {
  479. typedef typename TypeParam::template Type<std::string, int> Cache;
  480. Cache cache(10);
  481. const std::string key(100u, 'a');
  482. cache.Put(key, 1);
  483. EXPECT_GT(trace_event::EstimateMemoryUsage(cache),
  484. trace_event::EstimateMemoryUsage(key));
  485. }
  486. #endif // BUILDFLAG(ENABLE_BASE_TRACING)
  487. } // namespace base