1 //
2 // Copyright 2024 gRPC authors.
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 "src/core/util/lru_cache.h"
18
19 #include "absl/log/check.h"
20 #include "absl/strings/numbers.h"
21 #include "absl/strings/str_cat.h"
22 #include "gmock/gmock.h"
23 #include "gtest/gtest.h"
24
25 namespace grpc_core {
26
TEST(LruCache,Basic)27 TEST(LruCache, Basic) {
28 std::vector<int> created_list;
29 auto create = [&](const std::string& key) {
30 int value;
31 CHECK(absl::SimpleAtoi(key, &value));
32 created_list.push_back(value);
33 return value;
34 };
35 // Create a cache with max size 5.
36 LruCache<std::string, int> cache(5);
37 // Insert 5 values.
38 const std::array<int, 5> kOrder = {3, 1, 2, 0, 4};
39 for (int i : kOrder) {
40 std::string key = absl::StrCat(i);
41 EXPECT_EQ(absl::nullopt, cache.Get(key));
42 EXPECT_EQ(i, cache.GetOrInsert(key, create));
43 EXPECT_EQ(i, cache.Get(key));
44 }
45 EXPECT_THAT(created_list, ::testing::ElementsAreArray(kOrder));
46 created_list.clear();
47 // Get those same 5 values. This should not trigger any more insertions.
48 for (int i : kOrder) {
49 std::string key = absl::StrCat(i);
50 EXPECT_EQ(i, cache.GetOrInsert(key, create));
51 }
52 EXPECT_THAT(created_list, ::testing::ElementsAre());
53 // Now insert new elements.
54 // Each insertion should remove the least recently used element.
55 const std::array<int, 5> kOrder2 = {7, 6, 8, 5, 9};
56 for (size_t i = 0; i < kOrder2.size(); ++i) {
57 int value2 = kOrder2[i];
58 std::string key2 = absl::StrCat(value2);
59 EXPECT_EQ(absl::nullopt, cache.Get(key2));
60 EXPECT_EQ(value2, cache.GetOrInsert(key2, create));
61 EXPECT_EQ(value2, cache.Get(key2));
62 int value1 = kOrder[i];
63 std::string key1 = absl::StrCat(value1);
64 EXPECT_EQ(absl::nullopt, cache.Get(key1));
65 }
66 EXPECT_THAT(created_list, ::testing::ElementsAreArray(kOrder2));
67 }
68
TEST(LruCache,SetMaxSize)69 TEST(LruCache, SetMaxSize) {
70 auto create = [&](const std::string& key) {
71 int value;
72 CHECK(absl::SimpleAtoi(key, &value));
73 return value;
74 };
75 // Create a cache with max size 10.
76 LruCache<std::string, int> cache(10);
77 // Insert 10 values.
78 for (int i = 1; i <= 10; ++i) {
79 std::string key = absl::StrCat(i);
80 EXPECT_EQ(absl::nullopt, cache.Get(key));
81 EXPECT_EQ(i, cache.GetOrInsert(key, create));
82 EXPECT_EQ(i, cache.Get(key));
83 }
84 // Set max size to 15. All elements should still be present.
85 cache.SetMaxSize(15);
86 for (int i = 1; i <= 10; ++i) {
87 std::string key = absl::StrCat(i);
88 EXPECT_EQ(i, cache.Get(key));
89 }
90 // Set max size to 6. This should remove the first 4 elements.
91 cache.SetMaxSize(6);
92 for (int i = 1; i <= 4; ++i) {
93 std::string key = absl::StrCat(i);
94 EXPECT_EQ(absl::nullopt, cache.Get(key)) << i;
95 }
96 for (int i = 5; i <= 10; ++i) {
97 std::string key = absl::StrCat(i);
98 EXPECT_EQ(i, cache.Get(key));
99 }
100 }
101
102 } // namespace grpc_core
103
main(int argc,char ** argv)104 int main(int argc, char** argv) {
105 ::testing::InitGoogleTest(&argc, argv);
106 return RUN_ALL_TESTS();
107 }
108