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 #ifndef GRPC_SRC_CORE_UTIL_LRU_CACHE_H
18 #define GRPC_SRC_CORE_UTIL_LRU_CACHE_H
19
20 #include <list>
21 #include <tuple>
22 #include <utility>
23
24 #include "absl/container/flat_hash_map.h"
25 #include "absl/functional/any_invocable.h"
26 #include "absl/log/check.h"
27 #include "absl/types/optional.h"
28
29 namespace grpc_core {
30
31 // A simple LRU cache. Retains at most max_size entries.
32 // Caller is responsible for synchronization.
33 // TODO(roth): Support heterogenous lookups.
34 template <typename Key, typename Value>
35 class LruCache {
36 public:
LruCache(size_t max_size)37 explicit LruCache(size_t max_size) : max_size_(max_size) {
38 CHECK_GT(max_size, 0UL);
39 }
40
41 // Returns the value for key, or nullopt if not present.
42 absl::optional<Value> Get(Key key);
43
44 // If key is present in the cache, returns the corresponding value.
45 // Otherwise, inserts a new entry in the map, calling create() to
46 // construct the new value. If inserting a new entry causes the cache
47 // to be too large, removes the least recently used entry.
48 Value GetOrInsert(Key key, absl::AnyInvocable<Value(const Key&)> create);
49
50 // Changes the max size of the cache. If there are currently more than
51 // max_size entries, deletes least-recently-used entries to enforce
52 // the new max size.
53 void SetMaxSize(size_t max_size);
54
55 private:
56 struct CacheEntry {
57 Value value;
58 typename std::list<Key>::iterator lru_iterator;
59
CacheEntryCacheEntry60 explicit CacheEntry(Value v) : value(std::move(v)) {}
61 };
62
63 void RemoveOldestEntry();
64
65 size_t max_size_;
66 absl::flat_hash_map<Key, CacheEntry> cache_;
67 std::list<Key> lru_list_;
68 };
69
70 //
71 // implementation -- no user-serviceable parts below
72 //
73
74 template <typename Key, typename Value>
Get(Key key)75 absl::optional<Value> LruCache<Key, Value>::Get(Key key) {
76 auto it = cache_.find(key);
77 if (it == cache_.end()) return absl::nullopt;
78 // Found the entry. Move the entry to the end of the LRU list.
79 auto new_lru_it = lru_list_.insert(lru_list_.end(), *it->second.lru_iterator);
80 lru_list_.erase(it->second.lru_iterator);
81 it->second.lru_iterator = new_lru_it;
82 return it->second.value;
83 }
84
85 template <typename Key, typename Value>
GetOrInsert(Key key,absl::AnyInvocable<Value (const Key &)> create)86 Value LruCache<Key, Value>::GetOrInsert(
87 Key key, absl::AnyInvocable<Value(const Key&)> create) {
88 auto value = Get(key);
89 if (value.has_value()) return std::move(*value);
90 // Entry not found. We'll need to insert a new entry.
91 // If the cache is at max size, remove the least recently used entry.
92 if (cache_.size() == max_size_) RemoveOldestEntry();
93 // Create a new entry, insert it, and return it.
94 auto it = cache_
95 .emplace(std::piecewise_construct, std::forward_as_tuple(key),
96 std::forward_as_tuple(create(key)))
97 .first;
98 it->second.lru_iterator = lru_list_.insert(lru_list_.end(), std::move(key));
99 return it->second.value;
100 }
101
102 template <typename Key, typename Value>
SetMaxSize(size_t max_size)103 void LruCache<Key, Value>::SetMaxSize(size_t max_size) {
104 max_size_ = max_size;
105 while (cache_.size() > max_size_) {
106 RemoveOldestEntry();
107 }
108 }
109
110 template <typename Key, typename Value>
RemoveOldestEntry()111 void LruCache<Key, Value>::RemoveOldestEntry() {
112 auto lru_it = lru_list_.begin();
113 CHECK(lru_it != lru_list_.end());
114 auto cache_it = cache_.find(*lru_it);
115 CHECK(cache_it != cache_.end());
116 cache_.erase(cache_it);
117 lru_list_.pop_front();
118 }
119
120 } // namespace grpc_core
121
122 #endif // GRPC_SRC_CORE_UTIL_LRU_CACHE_H
123