41#include <unordered_map>
68class KeyNotFound :
public std::invalid_argument
71 KeyNotFound() : std::invalid_argument(
"key_not_found")
76template <
typename K,
typename V>
struct KeyValuePair
82 KeyValuePair(
const K &k,
const V &v) : key(k), value(v)
86 KeyValuePair(
const K &k, V &&v) : key(k), value(std::move(v))
91 KeyValuePair(
const KeyValuePair &) =
delete;
92 KeyValuePair &operator=(
const KeyValuePair &) =
delete;
107template <
class Key,
class Value,
class Lock = NullLock,
108 class Map = std::unordered_map<
109 Key,
typename std::list<KeyValuePair<Key, Value>>::iterator>>
113 typedef KeyValuePair<Key, Value> node_type;
114 typedef std::list<KeyValuePair<Key, Value>> list_type;
115 typedef Map map_type;
116 typedef Lock lock_type;
117 using Guard = std::lock_guard<lock_type>;
127 explicit Cache(
size_t maxSize = 64,
size_t elasticity = 10)
128 : maxSize_(maxSize), elasticity_(elasticity)
132 virtual ~Cache() =
default;
137 return cache_.size();
143 return cache_.empty();
153 void insert(
const Key &k,
const Value &v)
156 const auto iter = cache_.find(k);
157 if (iter != cache_.end())
159 iter->second->value = v;
160 keys_.splice(keys_.begin(), keys_, iter->second);
164 keys_.emplace_front(k, v);
165 cache_[k] = keys_.begin();
169 Value &insert(
const Key &k, Value &&v)
172 const auto iter = cache_.find(k);
173 if (iter != cache_.end())
175 iter->second->value = std::move(v);
176 keys_.splice(keys_.begin(), keys_, iter->second);
177 return keys_.front().value;
180 keys_.emplace_front(k, std::move(v));
181 cache_[k] = keys_.begin();
183 return keys_.front().value;
186 bool tryGet(
const Key &kIn, Value &vOut)
189 const auto iter = cache_.find(kIn);
190 if (iter == cache_.end())
194 keys_.splice(keys_.begin(), keys_, iter->second);
195 vOut = iter->second->value;
203 const Value &get(
const Key &k)
206 const auto iter = cache_.find(k);
207 if (iter == cache_.end())
211 keys_.splice(keys_.begin(), keys_, iter->second);
212 return iter->second->value;
215 Value *getPtr(
const Key &k)
218 const auto iter = cache_.find(k);
219 if (iter == cache_.end())
223 keys_.splice(keys_.begin(), keys_, iter->second);
224 return &(iter->second->value);
230 Value getCopy(
const Key &k)
235 bool remove(
const Key &k)
238 auto iter = cache_.find(k);
239 if (iter == cache_.end())
243 keys_.erase(iter->second);
248 bool contains(
const Key &k)
251 return cache_.find(k) != cache_.end();
254 bool getOldestEntry(Key &kOut, Value &vOut)
261 kOut = keys_.back().key;
262 vOut = keys_.back().value;
266 bool removeAndRecycleOldestEntry(Value &vOut)
273 vOut = std::move(keys_.back().value);
274 cache_.erase(keys_.back().key);
279 size_t getMaxSize()
const
284 size_t getElasticity()
const
289 size_t getMaxAllowedSize()
const
291 return maxSize_ + elasticity_;
294 template <
typename F>
void cwalk(
F &f)
const
297 std::for_each(keys_.begin(), keys_.end(), f);
301 : cache_(std::move(other.cache_)), keys_(std::move(other.keys_)),
302 maxSize_(other.maxSize_), elasticity_(other.elasticity_)
309 size_t maxAllowed = maxSize_ + elasticity_;
310 if (maxSize_ == 0 || cache_.size() <= maxAllowed)
315 while (cache_.size() > maxSize_)
317 cache_.erase(keys_.back().key);
326 Cache(
const Cache &) =
delete;
327 Cache &operator=(
const Cache &) =
delete;
329 mutable Lock lock_{};