Github   Telegram
Loading...
Searching...
No Matches
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