userver: userver/cache/nway_lru_cache.hpp Source File
⚠️ This is the documentation for an old userver version. Click here to switch to the latest version.
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages Concepts
nway_lru_cache.hpp
1#pragma once
2
3#include <functional>
4#include <optional>
5#include <vector>
6
7#include <userver/cache/lru_map.hpp>
8#include <userver/dump/dumper.hpp>
9#include <userver/dump/operations.hpp>
10#include <userver/engine/mutex.hpp>
11
12USERVER_NAMESPACE_BEGIN
13
14namespace cache {
15
16/// @ingroup userver_containers
17template <typename T, typename U, typename Hash = std::hash<T>,
18 typename Equal = std::equal_to<T>>
19class NWayLRU final {
20 public:
21 NWayLRU(size_t ways, size_t way_size, const Hash& hash = Hash(),
22 const Equal& equal = Equal());
23
24 void Put(const T& key, U value);
25
26 template <typename Validator>
27 std::optional<U> Get(const T& key, Validator validator);
28
29 std::optional<U> Get(const T& key) {
30 return Get(key, [](const U&) { return true; });
31 }
32
33 U GetOr(const T& key, const U& default_value);
34
35 void Invalidate();
36
37 void InvalidateByKey(const T& key);
38
39 /// Iterates over all items. May be slow for big caches.
40 template <typename Function>
41 void VisitAll(Function func) const;
42
43 size_t GetSize() const;
44
45 void UpdateWaySize(size_t way_size);
46
47 void Write(dump::Writer& writer) const;
48 void Read(dump::Reader& reader);
49
50 /// The dump::Dumper will be notified of any cache updates. This method is not
51 /// thread-safe.
52 void SetDumper(std::shared_ptr<dump::Dumper> dumper);
53
54 private:
55 struct Way {
56 Way(Way&& other) noexcept : cache(std::move(other.cache)) {}
57
58 // max_size is not used, will be reset by Resize() in NWayLRU::NWayLRU
59 Way(const Hash& hash, const Equal& equal) : cache(1, hash, equal) {}
60
61 mutable engine::Mutex mutex;
62 LruMap<T, U, Hash, Equal> cache;
63 };
64
65 Way& GetWay(const T& key);
66
67 void NotifyDumper();
68
69 std::vector<Way> caches_;
70 Hash hash_fn_;
71 std::shared_ptr<dump::Dumper> dumper_{nullptr};
72};
73
74template <typename T, typename U, typename Hash, typename Eq>
75NWayLRU<T, U, Hash, Eq>::NWayLRU(size_t ways, size_t way_size, const Hash& hash,
76 const Eq& equal)
77 : caches_(), hash_fn_(hash) {
78 caches_.reserve(ways);
79 for (size_t i = 0; i < ways; ++i) caches_.emplace_back(hash, equal);
80 if (ways == 0) throw std::logic_error("Ways must be positive");
81
82 for (auto& way : caches_) way.cache.SetMaxSize(way_size);
83}
84
85template <typename T, typename U, typename Hash, typename Eq>
86void NWayLRU<T, U, Hash, Eq>::Put(const T& key, U value) {
87 auto& way = GetWay(key);
88 {
89 std::unique_lock<engine::Mutex> lock(way.mutex);
90 way.cache.Put(key, std::move(value));
91 }
92 NotifyDumper();
93}
94
95template <typename T, typename U, typename Hash, typename Eq>
96template <typename Validator>
97std::optional<U> NWayLRU<T, U, Hash, Eq>::Get(const T& key,
98 Validator validator) {
99 auto& way = GetWay(key);
100 std::unique_lock<engine::Mutex> lock(way.mutex);
101 auto* value = way.cache.Get(key);
102
103 if (value) {
104 if (validator(*value)) return *value;
105 way.cache.Erase(key);
106 }
107
108 return std::nullopt;
109}
110
111template <typename T, typename U, typename Hash, typename Eq>
112void NWayLRU<T, U, Hash, Eq>::InvalidateByKey(const T& key) {
113 auto& way = GetWay(key);
114 {
115 std::unique_lock<engine::Mutex> lock(way.mutex);
116 way.cache.Erase(key);
117 }
118 NotifyDumper();
119}
120
121template <typename T, typename U, typename Hash, typename Eq>
122U NWayLRU<T, U, Hash, Eq>::GetOr(const T& key, const U& default_value) {
123 auto& way = GetWay(key);
124 std::unique_lock<engine::Mutex> lock(way.mutex);
125 return way.cache.GetOr(key, default_value);
126}
127
128template <typename T, typename U, typename Hash, typename Eq>
129void NWayLRU<T, U, Hash, Eq>::Invalidate() {
130 for (auto& way : caches_) {
131 std::unique_lock<engine::Mutex> lock(way.mutex);
132 way.cache.Clear();
133 }
134 NotifyDumper();
135}
136
137template <typename T, typename U, typename Hash, typename Eq>
138template <typename Function>
139void NWayLRU<T, U, Hash, Eq>::VisitAll(Function func) const {
140 for (const auto& way : caches_) {
141 std::unique_lock<engine::Mutex> lock(way.mutex);
142 way.cache.VisitAll(func);
143 }
144}
145
146template <typename T, typename U, typename Hash, typename Eq>
147size_t NWayLRU<T, U, Hash, Eq>::GetSize() const {
148 size_t size{0};
149 for (const auto& way : caches_) {
150 std::unique_lock<engine::Mutex> lock(way.mutex);
151 size += way.cache.GetSize();
152 }
153 return size;
154}
155
156template <typename T, typename U, typename Hash, typename Eq>
157void NWayLRU<T, U, Hash, Eq>::UpdateWaySize(size_t way_size) {
158 for (auto& way : caches_) {
159 std::unique_lock<engine::Mutex> lock(way.mutex);
160 way.cache.SetMaxSize(way_size);
161 }
162}
163
164template <typename T, typename U, typename Hash, typename Eq>
165typename NWayLRU<T, U, Hash, Eq>::Way& NWayLRU<T, U, Hash, Eq>::GetWay(
166 const T& key) {
167 auto n = hash_fn_(key) % caches_.size();
168 return caches_[n];
169}
170
171template <typename T, typename U, typename Hash, typename Equal>
172void NWayLRU<T, U, Hash, Equal>::Write(dump::Writer& writer) const {
173 writer.Write(caches_.size());
174
175 for (const Way& way : caches_) {
176 std::unique_lock<engine::Mutex> lock(way.mutex);
177
178 writer.Write(way.cache.GetSize());
179
180 way.cache.VisitAll([&writer](const T& key, const U& value) {
181 writer.Write(key);
182 writer.Write(value);
183 });
184 }
185}
186
187template <typename T, typename U, typename Hash, typename Equal>
188void NWayLRU<T, U, Hash, Equal>::Read(dump::Reader& reader) {
189 Invalidate();
190
191 const auto ways = reader.Read<std::size_t>();
192 for (std::size_t i = 0; i < ways; ++i) {
193 const auto elements_in_way = reader.Read<std::size_t>();
194 for (std::size_t j = 0; j < elements_in_way; ++j) {
195 auto key = reader.Read<T>();
196 auto value = reader.Read<U>();
197 Put(std::move(key), std::move(value));
198 }
199 }
200}
201
202template <typename T, typename U, typename Hash, typename Equal>
203void NWayLRU<T, U, Hash, Equal>::NotifyDumper() {
204 if (dumper_ != nullptr) {
205 dumper_->OnUpdateCompleted();
206 }
207}
208
209template <typename T, typename U, typename Hash, typename Equal>
210void NWayLRU<T, U, Hash, Equal>::SetDumper(
211 std::shared_ptr<dump::Dumper> dumper) {
212 dumper_ = std::move(dumper);
213}
214
215} // namespace cache
216
217USERVER_NAMESPACE_END