aboutsummaryrefslogtreecommitdiff
path: root/gd/common/lru_cache_test.cc
diff options
context:
space:
mode:
Diffstat (limited to 'gd/common/lru_cache_test.cc')
-rw-r--r--gd/common/lru_cache_test.cc461
1 files changed, 0 insertions, 461 deletions
diff --git a/gd/common/lru_cache_test.cc b/gd/common/lru_cache_test.cc
deleted file mode 100644
index 62b03dd2e..000000000
--- a/gd/common/lru_cache_test.cc
+++ /dev/null
@@ -1,461 +0,0 @@
-/*
- * Copyright 2020 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-#include <chrono>
-#include <limits>
-
-#include <gmock/gmock.h>
-#include <gtest/gtest.h>
-
-#include "common/lru_cache.h"
-
-namespace testing {
-
-using bluetooth::common::LruCache;
-
-TEST(LruCacheTest, empty_test) {
- LruCache<int, int> cache(3); // capacity = 3;
- EXPECT_EQ(cache.size(), 0);
- EXPECT_EQ(cache.find(42), cache.end());
- cache.clear(); // should not crash
- EXPECT_EQ(cache.find(42), cache.end());
- EXPECT_FALSE(cache.contains(42));
- EXPECT_FALSE(cache.extract(42));
-}
-
-TEST(LruCacheTest, comparison_test) {
- LruCache<int, int> cache_1(2);
- cache_1.insert_or_assign(1, 10);
- cache_1.insert_or_assign(2, 20);
- LruCache<int, int> cache_2(2);
- cache_2.insert_or_assign(1, 10);
- cache_2.insert_or_assign(2, 20);
- EXPECT_EQ(cache_1, cache_2);
- // Cache with different order should not be equal
- cache_2.find(1);
- EXPECT_NE(cache_1, cache_2);
- cache_1.find(1);
- EXPECT_EQ(cache_1, cache_2);
- // Cache with different value should be different
- cache_2.insert_or_assign(1, 11);
- EXPECT_NE(cache_1, cache_2);
- // Cache with different capacity should not be equal
- LruCache<int, int> cache_3(3);
- cache_3.insert_or_assign(1, 10);
- cache_3.insert_or_assign(2, 20);
- EXPECT_NE(cache_1, cache_3);
- // Empty cache should not be equal to non-empty ones
- LruCache<int, int> cache_4(2);
- EXPECT_NE(cache_1, cache_4);
- // Empty caches should be equal
- LruCache<int, int> cache_5(2);
- EXPECT_EQ(cache_4, cache_5);
- // Empty caches with different capacity should not be equal
- LruCache<int, int> cache_6(3);
- EXPECT_NE(cache_4, cache_6);
-}
-
-TEST(LruCacheTest, try_emplace_test) {
- LruCache<int, int> cache(2);
- cache.insert_or_assign(1, 10);
- cache.insert_or_assign(2, 20);
- auto result = cache.try_emplace(42, 420);
- // 1, 10 evicted
- EXPECT_EQ(std::get<2>(result), std::make_pair(1, 10));
- auto iter = cache.find(42);
- EXPECT_EQ(iter->second, 420);
- EXPECT_EQ(iter, std::get<0>(result));
- ASSERT_THAT(cache, ElementsAre(Pair(42, 420), Pair(2, 20)));
-}
-
-TEST(LruCacheTest, copy_test) {
- LruCache<int, std::shared_ptr<int>> cache(2);
- cache.insert_or_assign(1, std::make_shared<int>(100));
- auto iter = cache.find(1);
- EXPECT_EQ(*iter->second, 100);
- LruCache<int, std::shared_ptr<int>> new_cache = cache;
- iter = new_cache.find(1);
- EXPECT_EQ(*iter->second, 100);
- *iter->second = 300;
- iter = new_cache.find(1);
- EXPECT_EQ(*iter->second, 300);
- // Since copy is used, shared_ptr should increase count
- EXPECT_EQ(iter->second.use_count(), 2);
-}
-
-TEST(LruCacheTest, move_test) {
- LruCache<int, std::shared_ptr<int>> cache(2);
- cache.insert_or_assign(1, std::make_shared<int>(100));
- auto iter = cache.find(1);
- EXPECT_EQ(*iter->second, 100);
- LruCache<int, std::shared_ptr<int>> new_cache = std::move(cache);
- iter = new_cache.find(1);
- EXPECT_EQ(*iter->second, 100);
- *iter->second = 300;
- iter = new_cache.find(1);
- EXPECT_EQ(*iter->second, 300);
- // Since move is used, shared_ptr should not increase count
- EXPECT_EQ(iter->second.use_count(), 1);
-}
-
-TEST(LruCacheTest, move_insert_unique_ptr_test) {
- LruCache<int, std::unique_ptr<int>> cache(2);
- cache.insert_or_assign(1, std::make_unique<int>(100));
- auto iter = cache.find(1);
- EXPECT_EQ(*iter->second, 100);
- cache.insert_or_assign(1, std::make_unique<int>(400));
- iter = cache.find(1);
- EXPECT_EQ(*iter->second, 400);
-}
-
-TEST(LruCacheTest, move_insert_cache_test) {
- LruCache<int, LruCache<int, int>> cache(2);
- LruCache<int, int> m1(2);
- m1.insert_or_assign(1, 100);
- cache.insert_or_assign(1, std::move(m1));
- auto iter = cache.find(1);
- EXPECT_THAT(iter->second, ElementsAre(Pair(1, 100)));
- LruCache<int, int> m2(2);
- m2.insert_or_assign(2, 200);
- cache.insert_or_assign(1, std::move(m2));
- iter = cache.find(1);
- EXPECT_THAT(iter->second, ElementsAre(Pair(2, 200)));
-}
-
-TEST(LruCacheTest, erase_one_item_test) {
- LruCache<int, int> cache(3);
- cache.insert_or_assign(1, 10);
- cache.insert_or_assign(2, 20);
- cache.insert_or_assign(3, 30);
- auto iter = cache.find(2);
- // 2, 3, 1
- cache.find(3);
- // 3, 2, 1
- iter = cache.erase(iter);
- EXPECT_EQ(iter->first, 1);
- EXPECT_EQ(iter->second, 10);
- EXPECT_THAT(cache, ElementsAre(Pair(3, 30), Pair(1, 10)));
-}
-
-TEST(LruCacheTest, erase_in_for_loop_test) {
- LruCache<int, int> cache(3);
- cache.insert_or_assign(1, 10);
- cache.insert_or_assign(2, 20);
- cache.insert_or_assign(3, 30);
- for (auto iter = cache.begin(); iter != cache.end();) {
- if (iter->first == 2) {
- iter = cache.erase(iter);
- } else {
- ++iter;
- }
- }
- EXPECT_THAT(cache, ElementsAre(Pair(3, 30), Pair(1, 10)));
-}
-
-TEST(LruCacheTest, get_and_contains_key_test) {
- LruCache<int, int> cache(3); // capacity = 3;
- EXPECT_EQ(cache.size(), 0);
- EXPECT_EQ(cache.find(42), cache.end());
- EXPECT_FALSE(cache.contains(42));
- EXPECT_FALSE(cache.insert_or_assign(56, 200));
- EXPECT_EQ(cache.find(42), cache.end());
- EXPECT_FALSE(cache.contains(42));
- EXPECT_NE(cache.find(56), cache.end());
- EXPECT_TRUE(cache.contains(56));
- auto iter = cache.find(56);
- EXPECT_NE(iter, cache.end());
- EXPECT_EQ(iter->second, 200);
- EXPECT_TRUE(cache.extract(56));
- EXPECT_FALSE(cache.contains(56));
-}
-
-TEST(LruCacheTest, put_and_get_sequence_1) {
- // Section 1: Ordered put and ordered get
- LruCache<int, int> cache(3); // capacity = 3;
- EXPECT_FALSE(cache.insert_or_assign(1, 10));
- EXPECT_EQ(cache.size(), 1);
- EXPECT_FALSE(cache.insert_or_assign(2, 20));
- EXPECT_EQ(cache.size(), 2);
- EXPECT_FALSE(cache.insert_or_assign(3, 30));
- EXPECT_EQ(cache.size(), 3);
- // 3, 2, 1 after above operations
-
- auto evicted = cache.insert_or_assign(4, 40);
- // 4, 3, 2 after above operations, 1 is evicted
- EXPECT_TRUE(evicted);
- EXPECT_EQ(*evicted, std::make_pair(1, 10));
- EXPECT_EQ(cache.find(1), cache.end());
- LruCache<int, int>::const_iterator iter;
- EXPECT_NE(iter = cache.find(4), cache.end());
- EXPECT_EQ(iter->second, 40);
- EXPECT_NE(iter = cache.find(2), cache.end());
- EXPECT_EQ(iter->second, 20);
- EXPECT_NE(iter = cache.find(3), cache.end());
- EXPECT_EQ(iter->second, 30);
- // 3, 2, 4 after above operations
-
- // Section 2: Over capacity put and ordered get
- evicted = cache.insert_or_assign(5, 50);
- // 5, 3, 2 after above operations, 4 is evicted
- EXPECT_EQ(cache.size(), 3);
- EXPECT_TRUE(evicted);
- EXPECT_EQ(*evicted, std::make_pair(4, 40));
-
- EXPECT_TRUE(cache.extract(3));
- // 5, 2 should be in cache, 3 is removed
- EXPECT_FALSE(cache.insert_or_assign(6, 60));
- // 6, 5, 2 should be in cache
-
- // Section 3: Out of order get
- EXPECT_EQ(cache.find(3), cache.end());
- EXPECT_EQ(cache.find(4), cache.end());
- EXPECT_NE(iter = cache.find(2), cache.end());
- // 2, 6, 5 should be in cache
- EXPECT_EQ(iter->second, 20);
- EXPECT_NE(iter = cache.find(6), cache.end());
- // 6, 2, 5 should be in cache
- EXPECT_EQ(iter->second, 60);
- EXPECT_NE(iter = cache.find(5), cache.end());
- // 5, 6, 2 should be in cache
- EXPECT_EQ(iter->second, 50);
- evicted = cache.insert_or_assign(7, 70);
- // 7, 5, 6 should be in cache, 2 is evicted
- EXPECT_TRUE(evicted);
- EXPECT_EQ(*evicted, std::make_pair(2, 20));
-}
-
-TEST(LruCacheTest, put_and_get_sequence_2) {
- // Section 1: Replace item in cache
- LruCache<int, int> cache(2); // size = 2;
- EXPECT_FALSE(cache.insert_or_assign(1, 10));
- EXPECT_FALSE(cache.insert_or_assign(2, 20));
- // 2, 1 in cache
- auto evicted = cache.insert_or_assign(3, 30);
- // 3, 2 in cache, 1 is evicted
- EXPECT_TRUE(evicted);
- EXPECT_EQ(*evicted, std::make_pair(1, 10));
- EXPECT_FALSE(cache.insert_or_assign(2, 200));
- // 2, 3 in cache, nothing is evicted
- EXPECT_EQ(cache.size(), 2);
-
- EXPECT_FALSE(cache.contains(1));
- LruCache<int, int>::const_iterator iter;
- EXPECT_NE(iter = cache.find(2), cache.end());
- EXPECT_EQ(iter->second, 200);
- EXPECT_NE(iter = cache.find(3), cache.end());
- // 3, 2 in cache
- EXPECT_EQ(iter->second, 30);
-
- evicted = cache.insert_or_assign(4, 40);
- // 4, 3 in cache, 2 is evicted
- EXPECT_TRUE(evicted);
- EXPECT_EQ(*evicted, std::make_pair(2, 200));
-
- EXPECT_FALSE(cache.contains(2));
- EXPECT_NE(iter = cache.find(3), cache.end());
- EXPECT_EQ(iter->second, 30);
- EXPECT_NE(iter = cache.find(4), cache.end());
- EXPECT_EQ(iter->second, 40);
- // 4, 3 in cache
-
- EXPECT_TRUE(cache.extract(4));
- EXPECT_FALSE(cache.contains(4));
- // 3 in cache
- EXPECT_EQ(cache.size(), 1);
- EXPECT_FALSE(cache.insert_or_assign(2, 2000));
- // 2, 3 in cache
-
- EXPECT_FALSE(cache.contains(4));
- EXPECT_NE(iter = cache.find(3), cache.end());
- EXPECT_EQ(iter->second, 30);
- EXPECT_NE(iter = cache.find(2), cache.end());
- EXPECT_EQ(iter->second, 2000);
-
- EXPECT_TRUE(cache.extract(2));
- EXPECT_TRUE(cache.extract(3));
- EXPECT_FALSE(cache.insert_or_assign(5, 50));
- EXPECT_FALSE(cache.insert_or_assign(1, 100));
- EXPECT_FALSE(cache.insert_or_assign(5, 1000));
- EXPECT_EQ(cache.size(), 2);
- // 5, 1 in cache
-
- evicted = cache.insert_or_assign(6, 2000);
- // 6, 5 in cache
- EXPECT_TRUE(evicted);
- EXPECT_EQ(*evicted, std::make_pair(1, 100));
-
- EXPECT_FALSE(cache.contains(2));
- EXPECT_FALSE(cache.contains(3));
- EXPECT_NE(iter = cache.find(6), cache.end());
- EXPECT_EQ(iter->second, 2000);
- EXPECT_NE(iter = cache.find(5), cache.end());
- EXPECT_EQ(iter->second, 1000);
-}
-
-TEST(LruCacheTest, in_place_modification_test) {
- LruCache<int, int> cache(2);
- cache.insert_or_assign(1, 10);
- cache.insert_or_assign(2, 20);
- auto iter = cache.find(2);
- ASSERT_THAT(cache, ElementsAre(Pair(2, 20), Pair(1, 10)));
- iter->second = 200;
- ASSERT_THAT(cache, ElementsAre(Pair(2, 200), Pair(1, 10)));
- cache.insert_or_assign(1, 100);
- // 1, 2 in cache
- ASSERT_THAT(cache, ElementsAre(Pair(1, 100), Pair(2, 200)));
- // modifying iterator does not warm up key
- iter->second = 400;
- ASSERT_THAT(cache, ElementsAre(Pair(1, 100), Pair(2, 400)));
-}
-
-TEST(LruCacheTest, get_test) {
- LruCache<int, int> cache(2);
- EXPECT_FALSE(cache.insert_or_assign(1, 10));
- EXPECT_FALSE(cache.insert_or_assign(2, 20));
- EXPECT_TRUE(cache.contains(1));
- // 1, 2 in cache
- auto evicted = cache.insert_or_assign(3, 30);
- // 3, 1 in cache
- EXPECT_TRUE(evicted);
- EXPECT_EQ(*evicted, std::make_pair(2, 20));
-}
-
-TEST(LruCacheTest, remove_test) {
- LruCache<int, int> cache(10);
- for (int key = 0; key <= 30; key++) {
- cache.insert_or_assign(key, key * 100);
- }
- for (int key = 0; key <= 20; key++) {
- EXPECT_FALSE(cache.contains(key));
- }
- for (int key = 21; key <= 30; key++) {
- EXPECT_TRUE(cache.contains(key));
- }
- for (int key = 0; key <= 20; key++) {
- EXPECT_FALSE(cache.extract(key));
- }
- for (int key = 21; key <= 30; key++) {
- auto removed = cache.extract(key);
- EXPECT_TRUE(removed);
- EXPECT_EQ(*removed, std::make_pair(key, key * 100));
- }
- for (int key = 21; key <= 30; key++) {
- EXPECT_FALSE(cache.contains(key));
- }
-}
-
-TEST(LruCacheTest, clear_test) {
- LruCache<int, int> cache(10);
- for (int key = 0; key < 10; key++) {
- cache.insert_or_assign(key, key * 100);
- }
- for (int key = 0; key < 10; key++) {
- EXPECT_TRUE(cache.contains(key));
- }
- cache.clear();
- for (int key = 0; key < 10; key++) {
- EXPECT_FALSE(cache.contains(key));
- }
-
- for (int key = 0; key < 10; key++) {
- cache.insert_or_assign(key, key * 1000);
- }
- for (int key = 0; key < 10; key++) {
- EXPECT_TRUE(cache.contains(key));
- }
-}
-
-TEST(LruCacheTest, container_test) {
- LruCache<int, int> lru_cache(2);
- lru_cache.insert_or_assign(1, 10);
- lru_cache.insert_or_assign(2, 20);
- // Warm elements first
- ASSERT_THAT(lru_cache, ElementsAre(Pair(2, 20), Pair(1, 10)));
-}
-
-TEST(LruCacheTest, iterator_test) {
- LruCache<int, int> lru_cache(2);
- lru_cache.insert_or_assign(1, 10);
- lru_cache.insert_or_assign(2, 20);
- // Warm elements first
- std::list<std::pair<int, int>> list(lru_cache.begin(), lru_cache.end());
- ASSERT_THAT(list, ElementsAre(Pair(2, 20), Pair(1, 10)));
-}
-
-TEST(LruCacheTest, for_loop_test) {
- LruCache<int, int> lru_cache(2);
- lru_cache.insert_or_assign(1, 10);
- lru_cache.insert_or_assign(2, 20);
- // Warm elements first
- std::list<std::pair<int, int>> list;
- for (const auto& node : lru_cache) {
- list.emplace_back(node);
- }
- ASSERT_THAT(list, ElementsAre(Pair(2, 20), Pair(1, 10)));
- list.clear();
- for (auto& node : lru_cache) {
- list.emplace_back(node);
- node.second = node.second * 2;
- }
- ASSERT_THAT(list, ElementsAre(Pair(2, 20), Pair(1, 10)));
- list.clear();
- for (const auto& node : lru_cache) {
- list.emplace_back(node);
- }
- ASSERT_THAT(list, ElementsAre(Pair(2, 40), Pair(1, 20)));
-}
-
-TEST(LruCacheTest, pressure_test) {
- auto started = std::chrono::high_resolution_clock::now();
- int capacity = 0xFFFF; // 2^16 = 65535
- LruCache<int, int> cache(static_cast<size_t>(capacity));
-
- // fill the cache
- for (int key = 0; key < capacity; key++) {
- cache.insert_or_assign(key, key);
- }
-
- // make sure the cache is full
- for (int key = 0; key < capacity; key++) {
- EXPECT_TRUE(cache.contains(key));
- }
-
- // refresh the entire cache
- for (int key = 0; key < capacity; key++) {
- int new_key = key + capacity;
- cache.insert_or_assign(new_key, new_key);
- EXPECT_FALSE(cache.contains(key));
- EXPECT_TRUE(cache.contains(new_key));
- }
-
- // clear the entire cache
- LruCache<int, int>::const_iterator iter;
- for (int key = capacity; key < 2 * capacity; key++) {
- EXPECT_NE(iter = cache.find(key), cache.end());
- EXPECT_EQ(iter->second, key);
- EXPECT_TRUE(cache.extract(key));
- }
- EXPECT_EQ(cache.size(), 0);
-
- // test execution time
- auto done = std::chrono::high_resolution_clock::now();
- int execution_time = std::chrono::duration_cast<std::chrono::microseconds>(done - started).count();
- // Shouldn't be more than 1120ms
- int execution_time_per_cycle_us = 17;
- EXPECT_LT(execution_time, execution_time_per_cycle_us * capacity);
-}
-
-} // namespace testing
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-05 10:15:06 +0000