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 5830456 : void lock()
52 : {
53 5830456 : }
54 :
55 5826666 : void unlock()
56 : {
57 5826666 : }
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 4290 : KeyValuePair(const K &k, const V &v) : key(k), value(v)
83 : {
84 4290 : }
85 :
86 14472 : KeyValuePair(const K &k, V &&v) : key(k), value(std::move(v))
87 : {
88 14472 : }
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 70774 : explicit Cache(size_t maxSize = 64, size_t elasticity = 10)
128 70774 : : maxSize_(maxSize), elasticity_(elasticity)
129 : {
130 70714 : }
131 :
132 70248 : virtual ~Cache() = default;
133 :
134 803 : size_t size() const
135 : {
136 1606 : Guard g(lock_);
137 803 : return cache_.size();
138 : }
139 :
140 3511 : bool empty() const
141 : {
142 7022 : Guard g(lock_);
143 3511 : return cache_.empty();
144 : }
145 :
146 53204 : void clear()
147 : {
148 106408 : Guard g(lock_);
149 53204 : cache_.clear();
150 53204 : keys_.clear();
151 53204 : }
152 :
153 5081 : void insert(const Key &k, const Value &v)
154 : {
155 5081 : Guard g(lock_);
156 5081 : const auto iter = cache_.find(k);
157 5081 : if (iter != cache_.end())
158 : {
159 791 : iter->second->value = v;
160 791 : keys_.splice(keys_.begin(), keys_, iter->second);
161 791 : return;
162 : }
163 :
164 4290 : keys_.emplace_front(k, v);
165 4290 : cache_[k] = keys_.begin();
166 4290 : prune();
167 : }
168 :
169 15138 : Value &insert(const Key &k, Value &&v)
170 : {
171 30277 : Guard g(lock_);
172 15139 : const auto iter = cache_.find(k);
173 15138 : if (iter != cache_.end())
174 : {
175 667 : iter->second->value = std::move(v);
176 667 : keys_.splice(keys_.begin(), keys_, iter->second);
177 667 : return keys_.front().value;
178 : }
179 :
180 14471 : keys_.emplace_front(k, std::move(v));
181 14471 : cache_[k] = keys_.begin();
182 14471 : prune();
183 14472 : return keys_.front().value;
184 : }
185 :
186 5525736 : bool tryGet(const Key &kIn, Value &vOut)
187 : {
188 11048070 : Guard g(lock_);
189 5523595 : const auto iter = cache_.find(kIn);
190 5523022 : if (iter == cache_.end())
191 : {
192 4385929 : return false;
193 : }
194 1134903 : keys_.splice(keys_.begin(), keys_, iter->second);
195 1137864 : vOut = iter->second->value;
196 1136404 : 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 187609 : Value *getPtr(const Key &k)
216 : {
217 375218 : Guard g(lock_);
218 187609 : const auto iter = cache_.find(k);
219 187608 : if (iter == cache_.end())
220 : {
221 12099 : return nullptr;
222 : }
223 175509 : keys_.splice(keys_.begin(), keys_, iter->second);
224 175510 : 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 2619 : bool remove(const Key &k)
236 : {
237 5238 : Guard g(lock_);
238 2619 : auto iter = cache_.find(k);
239 2619 : if (iter == cache_.end())
240 : {
241 113 : return false;
242 : }
243 2506 : keys_.erase(iter->second);
244 2506 : cache_.erase(iter);
245 2506 : return true;
246 : }
247 :
248 15798 : bool contains(const Key &k)
249 : {
250 15798 : Guard g(lock_);
251 31596 : 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 651 : size_t getMaxSize() const
280 : {
281 651 : return maxSize_;
282 : }
283 :
284 1 : size_t getElasticity() const
285 : {
286 1 : return elasticity_;
287 : }
288 :
289 148 : size_t getMaxAllowedSize() const
290 : {
291 148 : return maxSize_ + elasticity_;
292 : }
293 :
294 21445 : template <typename F> void cwalk(F &f) const
295 : {
296 42676 : Guard g(lock_);
297 21445 : std::for_each(keys_.begin(), keys_.end(), f);
298 21445 : }
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 18762 : size_t prune()
308 : {
309 18762 : size_t maxAllowed = maxSize_ + elasticity_;
310 18762 : if (maxSize_ == 0 || cache_.size() <= maxAllowed)
311 : { /* ERO: changed < to <= */
312 17746 : return 0;
313 : }
314 1016 : size_t count = 0;
315 9962 : while (cache_.size() > maxSize_)
316 : {
317 8946 : cache_.erase(keys_.back().key);
318 8946 : keys_.pop_back();
319 8946 : ++count;
320 : }
321 1015 : 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 */
|
