41 #include <unordered_map>
66 class KeyNotFound :
public std::invalid_argument
69 KeyNotFound() : std::invalid_argument(
"key_not_found")
74 template <
typename K,
typename V>
struct KeyValuePair
80 KeyValuePair(
const K &k,
const V &v) : key(k), value(v)
83 KeyValuePair(
const K &k, V &&v) : key(k), value(std::move(v))
100 template <
class Key,
class Value,
class Lock = NullLock,
101 class Map = std::unordered_map<
102 Key,
typename std::list<KeyValuePair<Key, Value>>::iterator>>
106 typedef KeyValuePair<Key, Value> node_type;
107 typedef std::list<KeyValuePair<Key, Value>> list_type;
108 typedef Map map_type;
109 typedef Lock lock_type;
110 using Guard = std::lock_guard<lock_type>;
119 explicit Cache(
size_t maxSize = 64,
size_t elasticity = 10)
120 : maxSize_(maxSize), elasticity_(elasticity)
123 virtual ~Cache() =
default;
127 return cache_.size();
132 return cache_.empty();
140 void insert(
const Key &k,
const Value &v)
143 const auto iter = cache_.find(k);
144 if (iter != cache_.end())
146 iter->second->value = v;
147 keys_.splice(keys_.begin(), keys_, iter->second);
151 keys_.emplace_front(k, v);
152 cache_[k] = keys_.begin();
155 Value &insert(
const Key &k, Value &&v)
158 const auto iter = cache_.find(k);
159 if (iter != cache_.end())
161 iter->second->value = std::move(v);
162 keys_.splice(keys_.begin(), keys_, iter->second);
163 return keys_.front().value;
166 keys_.emplace_front(k, std::move(v));
167 cache_[k] = keys_.begin();
169 return keys_.front().value;
171 bool tryGet(
const Key &kIn, Value &vOut)
174 const auto iter = cache_.find(kIn);
175 if (iter == cache_.end())
179 keys_.splice(keys_.begin(), keys_, iter->second);
180 vOut = iter->second->value;
187 const Value &get(
const Key &k)
190 const auto iter = cache_.find(k);
191 if (iter == cache_.end())
195 keys_.splice(keys_.begin(), keys_, iter->second);
196 return iter->second->value;
198 Value *getPtr(
const Key &k)
201 const auto iter = cache_.find(k);
202 if (iter == cache_.end())
206 keys_.splice(keys_.begin(), keys_, iter->second);
207 return &(iter->second->value);
212 Value getCopy(
const Key &k)
216 bool remove(
const Key &k)
219 auto iter = cache_.find(k);
220 if (iter == cache_.end())
224 keys_.erase(iter->second);
228 bool contains(
const Key &k)
231 return cache_.find(k) != cache_.end();
234 bool getOldestEntry(Key &kOut, Value &vOut)
241 kOut = keys_.back().key;
242 vOut = keys_.back().value;
246 bool removeAndRecycleOldestEntry(Value &vOut)
253 vOut = std::move(keys_.back().value);
254 cache_.erase(keys_.back().key);
259 size_t getMaxSize()
const
263 size_t getElasticity()
const
267 size_t getMaxAllowedSize()
const
269 return maxSize_ + elasticity_;
271 template <
typename F>
void cwalk(
F &f)
const
274 std::for_each(keys_.begin(), keys_.end(), f);
278 : cache_(std::move(other.cache_)), keys_(std::move(other.keys_)),
279 maxSize_(other.maxSize_), elasticity_(other.elasticity_)
286 size_t maxAllowed = maxSize_ + elasticity_;
287 if (maxSize_ == 0 || cache_.size() <= maxAllowed)
292 while (cache_.size() > maxSize_)
294 cache_.erase(keys_.back().key);
303 Cache(
const Cache &) =
delete;
304 Cache &operator=(
const Cache &) =
delete;
306 mutable Lock lock_{};