Volume Cartographer 2.27.0
LRUCache.hpp
Go to the documentation of this file.
1#pragma once
2
5#include <cstddef>
6#include <list>
7#include <memory>
8#include <mutex>
9#include <shared_mutex>
10#include <unordered_map>
11
13
14namespace volcart
15{
16
18struct NoOpMutex {
19};
20
43template <typename TKey, typename TValue, class TMutex = std::shared_mutex>
44class LRUCache final : public Cache<TKey, TValue>
45{
46public:
49
55 using TPair = std::pair<TKey, TValue>;
56
62 using TListIterator = typename std::list<TPair>::iterator;
63
65 using Pointer = std::shared_ptr<LRUCache<TKey, TValue>>;
66
70
72 explicit LRUCache(std::size_t capacity) : BaseClass(capacity) {}
73
75 static auto New() -> Pointer
76 {
77 return std::make_shared<LRUCache<TKey, TValue>>();
78 }
79
81 static auto New(std::size_t capacity) -> Pointer
82 {
83 return std::make_shared<LRUCache<TKey, TValue>>(capacity);
84 }
89 void setCapacity(std::size_t capacity) override
90 {
91 std::unique_lock lock(cache_mutex_);
92 if (capacity <= 0) {
93 throw std::invalid_argument(
94 "Cannot create cache with capacity <= 0");
95 }
97 evict();
98 }
99
101 auto capacity() const -> std::size_t override { return capacity_; }
102
104 auto size() const -> std::size_t override { return lookup_.size(); }
109 auto get(const TKey& k) -> TValue override
110 {
111 std::unique_lock lock(cache_mutex_);
112 auto lookupIter = lookup_.find(k);
113 if (lookupIter == std::end(lookup_)) {
114 throw std::invalid_argument("Key not in cache");
115 }
116
117 items_.splice(std::begin(items_), items_, lookupIter->second);
118 return lookupIter->second->second;
119 }
120
122 void put(const TKey& k, const TValue& v) override
123 {
124 std::unique_lock lock(cache_mutex_);
125 // If already in cache, need to refresh it
126 auto lookupIter = lookup_.find(k);
127 if (lookupIter != std::end(lookup_)) {
128 auto& [key, val] = *lookupIter->second;
130 BaseClass::on_eject_(key, val);
131 }
132 items_.erase(lookupIter->second);
133 lookup_.erase(lookupIter);
134 }
135
136 items_.push_front(TPair(k, v));
137 lookup_[k] = std::begin(items_);
138 evict();
139 }
140
142 auto contains(const TKey& k) -> bool override
143 {
144 std::shared_lock lock(cache_mutex_);
145 return lookup_.find(k) != std::end(lookup_);
146 }
147
161 void onEvict(std::function<bool(TKey&, TValue&)> fn) override
162 {
164 }
165
171 void resetOnEvict() override { BaseClass::on_eject_ = {}; }
172
181 void evict() override
182 { // Already below capacity
183 if (lookup_.size() <= capacity_) {
184 return;
185 }
186
187 // If we don't have an onEject callback, fast remove the last element
188 if (not BaseClass::on_eject_) {
189 while (lookup_.size() > capacity_) {
190 auto& [key, _] = items_.back();
191 lookup_.erase(key);
192 items_.pop_back();
193 }
194 return;
195 }
196
197 // Else iterate the items in reverse until we find one we can remove
198 for (auto it = items_.rbegin(); it != items_.rend();) {
199 // Get the key and value
200 auto& [key, value] = *it;
201
202 // Eject this item
203 if (BaseClass::on_eject_(key, value)) {
204 lookup_.erase(key);
205 it = std::next(it);
206 it = std::reverse_iterator(items_.erase(it.base()));
207 } else {
208 ++it;
209 }
210
211 // Stop when we've reset to capacity
212 if (lookup_.size() <= capacity_) {
213 break;
214 }
215 }
216 }
217
219 void purge() override
220 {
221 std::unique_lock lock(cache_mutex_);
222 // If we have an on_eject_ function, check every item
224 for (auto it = items_.begin(); it != items_.end();) {
225 auto& [key, value] = *it;
226 if (BaseClass::on_eject_(key, value)) {
227 lookup_.erase(key);
228 it = items_.erase(it);
229 } else {
230 ++it;
231 }
232 }
233 }
234
235 // Otherwise, remove everything
236 else {
237 lookup_.clear();
238 items_.clear();
239 }
240 }
243private:
245 std::list<TPair> items_;
247 std::unordered_map<TKey, TListIterator> lookup_;
249 mutable TMutex cache_mutex_;
250};
251} // namespace volcart
Abstract Base Class for Key-Value Caches.
Definition: Cache.hpp:18
std::function< bool(TKey &, TValue &)> on_eject_
Definition: Cache.hpp:71
std::size_t capacity_
Definition: Cache.hpp:68
std::shared_ptr< Cache > Pointer
Definition: Cache.hpp:24
Least Recently Used Cache.
Definition: LRUCache.hpp:45
auto size() const -> std::size_t override
Get the current number of elements in the cache.
Definition: LRUCache.hpp:104
void put(const TKey &k, const TValue &v) override
Put an item into the cache.
Definition: LRUCache.hpp:122
auto contains(const TKey &k) -> bool override
Check if an item is already in the cache.
Definition: LRUCache.hpp:142
void setCapacity(std::size_t capacity) override
Set the maximum number of elements in the cache.
Definition: LRUCache.hpp:89
std::list< TPair > items_
Definition: LRUCache.hpp:245
auto get(const TKey &k) -> TValue override
Get an item from the cache by key.
Definition: LRUCache.hpp:109
std::pair< TKey, TValue > TPair
Templated Key/Value pair.
Definition: LRUCache.hpp:55
std::shared_ptr< LRUCache< TKey, TValue > > Pointer
Definition: LRUCache.hpp:65
typename std::list< TPair >::iterator TListIterator
Templated Key/Value pair iterator.
Definition: LRUCache.hpp:62
std::size_t capacity_
Definition: Cache.hpp:68
auto capacity() const -> std::size_t override
Get the maximum number of elements in the cache.
Definition: LRUCache.hpp:101
LRUCache()
Default constructor.
Definition: LRUCache.hpp:69
void purge() override
Evict all items ignoring cache policy.
Definition: LRUCache.hpp:219
LRUCache(std::size_t capacity)
Constructor with cache capacity parameter.
Definition: LRUCache.hpp:72
std::unordered_map< TKey, TListIterator > lookup_
Definition: LRUCache.hpp:247
void onEvict(std::function< bool(TKey &, TValue &)> fn) override
Set a callback function for validating if an item can be evicted.
Definition: LRUCache.hpp:161
void resetOnEvict() override
Remove the validation callback function.
Definition: LRUCache.hpp:171
void evict() override
Evict items following the cache policy.
Definition: LRUCache.hpp:181
Volume Cartographer library