GDAL
cpl_mem_cache.h
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
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
43namespace lru11
44{
45/*
46 * a noop lockable concept that can be used in place of std::mutex
47 */
48class NullLock
49{
50 public:
51 void lock()
52 {
53 }
54
55 void unlock()
56 {
57 }
58
59 bool try_lock()
60 {
61 return true;
62 }
63};
64
68class KeyNotFound : public std::invalid_argument
69{
70 public:
71 KeyNotFound() : std::invalid_argument("key_not_found")
72 {
73 }
74};
75
76template <typename K, typename V> struct KeyValuePair
77{
78 public:
79 K key;
80 V value;
81
82 KeyValuePair(const K &k, const V &v) : key(k), value(v)
83 {
84 }
85
86 KeyValuePair(const K &k, V &&v) : key(k), value(std::move(v))
87 {
88 }
89};
90
103template <class Key, class Value, class Lock = NullLock,
104 class Map = std::unordered_map<
105 Key, typename std::list<KeyValuePair<Key, Value>>::iterator>>
106class Cache
107{
108 public:
109 typedef KeyValuePair<Key, Value> node_type;
110 typedef std::list<KeyValuePair<Key, Value>> list_type;
111 typedef Map map_type;
112 typedef Lock lock_type;
113 using Guard = std::lock_guard<lock_type>;
114
123 explicit Cache(size_t maxSize = 64, size_t elasticity = 10)
124 : maxSize_(maxSize), elasticity_(elasticity)
125 {
126 }
127
128 virtual ~Cache() = default;
129
130 size_t size() const
131 {
132 Guard g(lock_);
133 return cache_.size();
134 }
135
136 bool empty() const
137 {
138 Guard g(lock_);
139 return cache_.empty();
140 }
141
142 void clear()
143 {
144 Guard g(lock_);
145 cache_.clear();
146 keys_.clear();
147 }
148
149 void insert(const Key &k, const Value &v)
150 {
151 Guard g(lock_);
152 const auto iter = cache_.find(k);
153 if (iter != cache_.end())
154 {
155 iter->second->value = v;
156 keys_.splice(keys_.begin(), keys_, iter->second);
157 return;
158 }
159
160 keys_.emplace_front(k, v);
161 cache_[k] = keys_.begin();
162 prune();
163 }
164
165 Value &insert(const Key &k, Value &&v)
166 {
167 Guard g(lock_);
168 const auto iter = cache_.find(k);
169 if (iter != cache_.end())
170 {
171 iter->second->value = std::move(v);
172 keys_.splice(keys_.begin(), keys_, iter->second);
173 return keys_.front().value;
174 }
175
176 keys_.emplace_front(k, std::move(v));
177 cache_[k] = keys_.begin();
178 prune();
179 return keys_.front().value;
180 }
181
182 bool tryGet(const Key &kIn, Value &vOut)
183 {
184 Guard g(lock_);
185 const auto iter = cache_.find(kIn);
186 if (iter == cache_.end())
187 {
188 return false;
189 }
190 keys_.splice(keys_.begin(), keys_, iter->second);
191 vOut = iter->second->value;
192 return true;
193 }
194
199 const Value &get(const Key &k)
200 {
201 Guard g(lock_);
202 const auto iter = cache_.find(k);
203 if (iter == cache_.end())
204 {
205 throw KeyNotFound();
206 }
207 keys_.splice(keys_.begin(), keys_, iter->second);
208 return iter->second->value;
209 }
210
211 Value *getPtr(const Key &k)
212 {
213 Guard g(lock_);
214 const auto iter = cache_.find(k);
215 if (iter == cache_.end())
216 {
217 return nullptr;
218 }
219 keys_.splice(keys_.begin(), keys_, iter->second);
220 return &(iter->second->value);
221 }
222
226 Value getCopy(const Key &k)
227 {
228 return get(k);
229 }
230
231 bool remove(const Key &k)
232 {
233 Guard g(lock_);
234 auto iter = cache_.find(k);
235 if (iter == cache_.end())
236 {
237 return false;
238 }
239 keys_.erase(iter->second);
240 cache_.erase(iter);
241 return true;
242 }
243
244 bool contains(const Key &k)
245 {
246 Guard g(lock_);
247 return cache_.find(k) != cache_.end();
248 }
249
250 bool getOldestEntry(Key &kOut, Value &vOut)
251 {
252 Guard g(lock_);
253 if (keys_.empty())
254 {
255 return false;
256 }
257 kOut = keys_.back().key;
258 vOut = keys_.back().value;
259 return true;
260 }
261
262 bool removeAndRecycleOldestEntry(Value &vOut)
263 {
264 Guard g(lock_);
265 if (keys_.empty())
266 {
267 return false;
268 }
269 vOut = std::move(keys_.back().value);
270 cache_.erase(keys_.back().key);
271 keys_.pop_back();
272 return true;
273 }
274
275 size_t getMaxSize() const
276 {
277 return maxSize_;
278 }
279
280 size_t getElasticity() const
281 {
282 return elasticity_;
283 }
284
285 size_t getMaxAllowedSize() const
286 {
287 return maxSize_ + elasticity_;
288 }
289
290 template <typename F> void cwalk(F &f) const
291 {
292 Guard g(lock_);
293 std::for_each(keys_.begin(), keys_.end(), f);
294 }
295
296 Cache(Cache &&other)
297 : cache_(std::move(other.cache_)), keys_(std::move(other.keys_)),
298 maxSize_(other.maxSize_), elasticity_(other.elasticity_)
299 {
300 }
301
302 protected:
303 size_t prune()
304 {
305 size_t maxAllowed = maxSize_ + elasticity_;
306 if (maxSize_ == 0 || cache_.size() <= maxAllowed)
307 { /* ERO: changed < to <= */
308 return 0;
309 }
310 size_t count = 0;
311 while (cache_.size() > maxSize_)
312 {
313 cache_.erase(keys_.back().key);
314 keys_.pop_back();
315 ++count;
316 }
317 return count;
318 }
319
320 private:
321 // Disallow copying.
322 Cache(const Cache &) = delete;
323 Cache &operator=(const Cache &) = delete;
324
325 mutable Lock lock_{};
326 Map cache_{};
327 list_type keys_{};
328 size_t maxSize_;
329 size_t elasticity_;
330};
331
332} // namespace lru11
333
@ F
F-type formatting.