41 #include <unordered_map>
51 bool try_lock() {
return true; }
57 class KeyNotFound :
public std::invalid_argument {
59 KeyNotFound() : std::invalid_argument(
"key_not_found") {}
62 template <
typename K,
typename V>
68 KeyValuePair(
const K& k,
const V& v) : key(k), value(v) {}
69 KeyValuePair(
const K& k, V&& v): key(k), value(std::move(v)) {}
84 template <
class Key,
class Value,
class Lock = NullLock,
85 class Map = std::unordered_map<
86 Key,
typename std::list<KeyValuePair<Key, Value>>::iterator>>
89 typedef KeyValuePair<Key, Value> node_type;
90 typedef std::list<KeyValuePair<Key, Value>> list_type;
92 typedef Lock lock_type;
93 using Guard = std::lock_guard<lock_type>;
103 explicit Cache(
size_t maxSize = 64,
size_t elasticity = 10)
104 : maxSize_(maxSize), elasticity_(elasticity) {}
105 virtual ~Cache() =
default;
106 size_t size()
const {
108 return cache_.size();
112 return cache_.empty();
119 void insert(
const Key& k,
const Value& v) {
121 const auto iter = cache_.find(k);
122 if (iter != cache_.end()) {
123 iter->second->value = v;
124 keys_.splice(keys_.begin(), keys_, iter->second);
128 keys_.emplace_front(k, v);
129 cache_[k] = keys_.begin();
132 Value& insert(
const Key& k, Value&& v) {
134 const auto iter = cache_.find(k);
135 if (iter != cache_.end()) {
136 iter->second->value = std::move(v);
137 keys_.splice(keys_.begin(), keys_, iter->second);
138 return keys_.front().value;
141 keys_.emplace_front(k, std::move(v));
142 cache_[k] = keys_.begin();
144 return keys_.front().value;
146 bool tryGet(
const Key& kIn, Value& vOut) {
148 const auto iter = cache_.find(kIn);
149 if (iter == cache_.end()) {
152 keys_.splice(keys_.begin(), keys_, iter->second);
153 vOut = iter->second->value;
160 const Value& get(
const Key& k) {
162 const auto iter = cache_.find(k);
163 if (iter == cache_.end()) {
166 keys_.splice(keys_.begin(), keys_, iter->second);
167 return iter->second->value;
169 Value* getPtr(
const Key& k) {
171 const auto iter = cache_.find(k);
172 if (iter == cache_.end()) {
175 keys_.splice(keys_.begin(), keys_, iter->second);
176 return &(iter->second->value);
181 Value getCopy(
const Key& k) {
184 bool remove(
const Key& k) {
186 auto iter = cache_.find(k);
187 if (iter == cache_.end()) {
190 keys_.erase(iter->second);
194 bool contains(
const Key& k) {
196 return cache_.find(k) != cache_.end();
199 bool getOldestEntry(Key& kOut, Value& vOut) {
201 if( keys_.empty() ) {
204 kOut = keys_.back().key;
205 vOut = keys_.back().value;
209 bool removeAndRecycleOldestEntry(Value& vOut) {
211 if( keys_.empty() ) {
214 vOut = std::move(keys_.back().value);
215 cache_.erase(keys_.back().key);
220 size_t getMaxSize()
const {
return maxSize_; }
221 size_t getElasticity()
const {
return elasticity_; }
222 size_t getMaxAllowedSize()
const {
return maxSize_ + elasticity_; }
223 template <
typename F>
224 void cwalk(
F& f)
const {
226 std::for_each(keys_.begin(), keys_.end(), f);
229 Cache(Cache&& other):
230 cache_(std::move(other.cache_)),
231 keys_(std::move(other.keys_)),
232 maxSize_(other.maxSize_),
233 elasticity_(other.elasticity_) {}
237 size_t maxAllowed = maxSize_ + elasticity_;
238 if (maxSize_ == 0 || cache_.size() <= maxAllowed) {
242 while (cache_.size() > maxSize_) {
243 cache_.erase(keys_.back().key);
252 Cache(
const Cache&) =
delete;
253 Cache& operator=(
const Cache&) =
delete;
255 mutable Lock lock_{};