Line data Source code
1 : /*
2 : * LRUCache11 - a templated C++11 based LRU cache class that allows
3 : * specification of
4 : * key, value and optionally the map container type (defaults to
5 : * std::unordered_map)
6 : * By using the std::map and a linked list of keys it allows O(1) insert, delete
7 : * and
8 : * refresh operations.
9 : *
10 : * This is a header-only library and all you need is the LRUCache11.hpp file
11 : *
12 : * Github: https://github.com/mohaps/lrucache11
13 : *
14 : * This is a follow-up to the LRUCache project -
15 : * https://github.com/mohaps/lrucache
16 : *
17 : * Copyright (c) 2012-22 SAURAV MOHAPATRA <mohaps@gmail.com>
18 : *
19 : * Permission to use, copy, modify, and distribute this software for any
20 : * purpose with or without fee is hereby granted, provided that the above
21 : * copyright notice and this permission notice appear in all copies.
22 : *
23 : * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
24 : * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
25 : * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
26 : * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
27 : * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
28 : * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
29 : * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
30 : */
31 :
32 : /*! @cond Doxygen_Suppress */
33 :
34 : #pragma once
35 : #include <algorithm>
36 : #include <cstdint>
37 : #include <list>
38 : #include <mutex>
39 : #include <stdexcept>
40 : #include <thread>
41 : #include <unordered_map>
42 :
43 : namespace lru11
44 : {
45 : /*
46 : * a noop lockable concept that can be used in place of std::mutex
47 : */
48 : class NullLock
49 : {
50 : public:
51 5881186 : void lock()
52 : {
53 5881186 : }
54 :
55 5883146 : void unlock()
56 : {
57 5883146 : }
58 :
59 : bool try_lock()
60 : {
61 : return true;
62 : }
63 : };
64 :
65 : /**
66 : * error raised when a key not in cache is passed to get()
67 : */
68 : class KeyNotFound : public std::invalid_argument
69 : {
70 : public:
71 1 : KeyNotFound() : std::invalid_argument("key_not_found")
72 : {
73 1 : }
74 : };
75 :
76 : template <typename K, typename V> struct KeyValuePair
77 : {
78 : public:
79 : K key;
80 : V value;
81 :
82 4475 : KeyValuePair(const K &k, const V &v) : key(k), value(v)
83 : {
84 4445 : }
85 :
86 14689 : KeyValuePair(const K &k, V &&v) : key(k), value(std::move(v))
87 : {
88 14689 : }
89 :
90 : private:
91 : KeyValuePair(const KeyValuePair &) = delete;
92 : KeyValuePair &operator=(const KeyValuePair &) = delete;
93 : };
94 :
95 : /**
96 : * The LRU Cache class templated by
97 : * Key - key type
98 : * Value - value type
99 : * MapType - an associative container like std::unordered_map
100 : * LockType - a lock type derived from the Lock class (default:
101 : *NullLock = no synchronization)
102 : *
103 : * The default NullLock based template is not thread-safe, however passing
104 : *Lock=std::mutex will make it
105 : * thread-safe
106 : */
107 : template <class Key, class Value, class Lock = NullLock,
108 : class Map = std::unordered_map<
109 : Key, typename std::list<KeyValuePair<Key, Value>>::iterator>>
110 : class Cache
111 : {
112 : public:
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>;
118 :
119 : /**
120 : * the max size is the hard limit of keys and (maxSize + elasticity) is the
121 : * soft limit
122 : * the cache is allowed to grow till maxSize + elasticity and is pruned back
123 : * to maxSize keys
124 : * set maxSize = 0 for an unbounded cache (but in that case, you're better
125 : * off using a std::unordered_map directly anyway! :)
126 : */
127 74106 : explicit Cache(size_t maxSize = 64, size_t elasticity = 10)
128 74106 : : maxSize_(maxSize), elasticity_(elasticity)
129 : {
130 73899 : }
131 :
132 71733 : virtual ~Cache() = default;
133 :
134 813 : size_t size() const
135 : {
136 1626 : Guard g(lock_);
137 813 : return cache_.size();
138 : }
139 :
140 3604 : bool empty() const
141 : {
142 7208 : Guard g(lock_);
143 3604 : return cache_.empty();
144 : }
145 :
146 54308 : void clear()
147 : {
148 108616 : Guard g(lock_);
149 54308 : cache_.clear();
150 54308 : keys_.clear();
151 54308 : }
152 :
153 6182 : void insert(const Key &k, const Value &v)
154 : {
155 6182 : Guard g(lock_);
156 6150 : const auto iter = cache_.find(k);
157 6157 : if (iter != cache_.end())
158 : {
159 1702 : iter->second->value = v;
160 1701 : keys_.splice(keys_.begin(), keys_, iter->second);
161 1702 : return;
162 : }
163 :
164 4468 : keys_.emplace_front(k, v);
165 4469 : cache_[k] = keys_.begin();
166 4466 : prune();
167 : }
168 :
169 15363 : Value &insert(const Key &k, Value &&v)
170 : {
171 30726 : Guard g(lock_);
172 15363 : const auto iter = cache_.find(k);
173 15363 : if (iter != cache_.end())
174 : {
175 674 : iter->second->value = std::move(v);
176 674 : keys_.splice(keys_.begin(), keys_, iter->second);
177 674 : return keys_.front().value;
178 : }
179 :
180 14689 : keys_.emplace_front(k, std::move(v));
181 14689 : cache_[k] = keys_.begin();
182 14689 : prune();
183 14689 : return keys_.front().value;
184 : }
185 :
186 5574234 : bool tryGet(const Key &kIn, Value &vOut)
187 : {
188 11148329 : Guard g(lock_);
189 5574444 : const auto iter = cache_.find(kIn);
190 5573595 : if (iter == cache_.end())
191 : {
192 4425331 : return false;
193 : }
194 1146900 : keys_.splice(keys_.begin(), keys_, iter->second);
195 1148614 : vOut = iter->second->value;
196 1148754 : return true;
197 : }
198 :
199 : /**
200 : * The const reference returned here is only
201 : * guaranteed to be valid till the next insert/delete
202 : */
203 4 : const Value &get(const Key &k)
204 : {
205 5 : Guard g(lock_);
206 4 : const auto iter = cache_.find(k);
207 4 : if (iter == cache_.end())
208 : {
209 1 : throw KeyNotFound();
210 : }
211 3 : keys_.splice(keys_.begin(), keys_, iter->second);
212 6 : return iter->second->value;
213 : }
214 :
215 188713 : Value *getPtr(const Key &k)
216 : {
217 377426 : Guard g(lock_);
218 188713 : const auto iter = cache_.find(k);
219 188713 : if (iter == cache_.end())
220 : {
221 12250 : return nullptr;
222 : }
223 176463 : keys_.splice(keys_.begin(), keys_, iter->second);
224 176463 : return &(iter->second->value);
225 : }
226 :
227 : /**
228 : * returns a copy of the stored object (if found)
229 : */
230 1 : Value getCopy(const Key &k)
231 : {
232 1 : return get(k);
233 : }
234 :
235 2745 : bool remove(const Key &k)
236 : {
237 5490 : Guard g(lock_);
238 2745 : auto iter = cache_.find(k);
239 2745 : if (iter == cache_.end())
240 : {
241 114 : return false;
242 : }
243 2631 : keys_.erase(iter->second);
244 2631 : cache_.erase(iter);
245 2631 : return true;
246 : }
247 :
248 15855 : bool contains(const Key &k)
249 : {
250 15855 : Guard g(lock_);
251 31710 : return cache_.find(k) != cache_.end();
252 : }
253 :
254 0 : bool getOldestEntry(Key &kOut, Value &vOut)
255 : {
256 0 : Guard g(lock_);
257 0 : if (keys_.empty())
258 : {
259 0 : return false;
260 : }
261 0 : kOut = keys_.back().key;
262 0 : vOut = keys_.back().value;
263 0 : return true;
264 : }
265 :
266 137 : bool removeAndRecycleOldestEntry(Value &vOut)
267 : {
268 274 : Guard g(lock_);
269 137 : if (keys_.empty())
270 : {
271 1 : return false;
272 : }
273 136 : vOut = std::move(keys_.back().value);
274 136 : cache_.erase(keys_.back().key);
275 136 : keys_.pop_back();
276 136 : return true;
277 : }
278 :
279 653 : size_t getMaxSize() const
280 : {
281 653 : return maxSize_;
282 : }
283 :
284 1 : size_t getElasticity() const
285 : {
286 1 : return elasticity_;
287 : }
288 :
289 156 : size_t getMaxAllowedSize() const
290 : {
291 156 : return maxSize_ + elasticity_;
292 : }
293 :
294 21877 : template <typename F> void cwalk(F &f) const
295 : {
296 43540 : Guard g(lock_);
297 21877 : std::for_each(keys_.begin(), keys_.end(), f);
298 21877 : }
299 :
300 : Cache(Cache &&other)
301 : : cache_(std::move(other.cache_)), keys_(std::move(other.keys_)),
302 : maxSize_(other.maxSize_), elasticity_(other.elasticity_)
303 : {
304 : }
305 :
306 : protected:
307 19166 : size_t prune()
308 : {
309 19166 : size_t maxAllowed = maxSize_ + elasticity_;
310 19166 : if (maxSize_ == 0 || cache_.size() <= maxAllowed)
311 : { /* ERO: changed < to <= */
312 18131 : return 0;
313 : }
314 1033 : size_t count = 0;
315 9966 : while (cache_.size() > maxSize_)
316 : {
317 8930 : cache_.erase(keys_.back().key);
318 8931 : keys_.pop_back();
319 8933 : ++count;
320 : }
321 1014 : return count;
322 : }
323 :
324 : private:
325 : // Disallow copying.
326 : Cache(const Cache &) = delete;
327 : Cache &operator=(const Cache &) = delete;
328 :
329 : mutable Lock lock_{};
330 : Map cache_{};
331 : list_type keys_{};
332 : size_t maxSize_;
333 : size_t elasticity_;
334 : };
335 :
336 : } // namespace lru11
337 :
338 : /*! @endcond */
|
