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 private:
91 KeyValuePair(const KeyValuePair &) = delete;
92 KeyValuePair &operator=(const KeyValuePair &) = delete;
93};
94
107template <class Key, class Value, class Lock = NullLock,
108 class Map = std::unordered_map<
109 Key, typename std::list<KeyValuePair<Key, Value>>::iterator>>
110class 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
127 explicit Cache(size_t maxSize = 64, size_t elasticity = 10)
128 : maxSize_(maxSize), elasticity_(elasticity)
129 {
130 }
131
132 virtual ~Cache() = default;
133
134 size_t size() const
135 {
136 Guard g(lock_);
137 return cache_.size();
138 }
139
140 bool empty() const
141 {
142 Guard g(lock_);
143 return cache_.empty();
144 }
145
146 void clear()
147 {
148 Guard g(lock_);
149 cache_.clear();
150 keys_.clear();
151 }
152
153 void insert(const Key &k, const Value &v)
154 {
155 Guard g(lock_);
156 const auto iter = cache_.find(k);
157 if (iter != cache_.end())
158 {
159 iter->second->value = v;
160 keys_.splice(keys_.begin(), keys_, iter->second);
161 return;
162 }
163
164 keys_.emplace_front(k, v);
165 cache_[k] = keys_.begin();
166 prune();
167 }
168
169 Value &insert(const Key &k, Value &&v)
170 {
171 Guard g(lock_);
172 const auto iter = cache_.find(k);
173 if (iter != cache_.end())
174 {
175 iter->second->value = std::move(v);
176 keys_.splice(keys_.begin(), keys_, iter->second);
177 return keys_.front().value;
178 }
179
180 keys_.emplace_front(k, std::move(v));
181 cache_[k] = keys_.begin();
182 prune();
183 return keys_.front().value;
184 }
185
186 bool tryGet(const Key &kIn, Value &vOut)
187 {
188 Guard g(lock_);
189 const auto iter = cache_.find(kIn);
190 if (iter == cache_.end())
191 {
192 return false;
193 }
194 keys_.splice(keys_.begin(), keys_, iter->second);
195 vOut = iter->second->value;
196 return true;
197 }
198
203 const Value &get(const Key &k)
204 {
205 Guard g(lock_);
206 const auto iter = cache_.find(k);
207 if (iter == cache_.end())
208 {
209 throw KeyNotFound();
210 }
211 keys_.splice(keys_.begin(), keys_, iter->second);
212 return iter->second->value;
213 }
214
215 Value *getPtr(const Key &k)
216 {
217 Guard g(lock_);
218 const auto iter = cache_.find(k);
219 if (iter == cache_.end())
220 {
221 return nullptr;
222 }
223 keys_.splice(keys_.begin(), keys_, iter->second);
224 return &(iter->second->value);
225 }
226
230 Value getCopy(const Key &k)
231 {
232 return get(k);
233 }
234
235 bool remove(const Key &k)
236 {
237 Guard g(lock_);
238 auto iter = cache_.find(k);
239 if (iter == cache_.end())
240 {
241 return false;
242 }
243 keys_.erase(iter->second);
244 cache_.erase(iter);
245 return true;
246 }
247
248 bool contains(const Key &k)
249 {
250 Guard g(lock_);
251 return cache_.find(k) != cache_.end();
252 }
253
254 bool getOldestEntry(Key &kOut, Value &vOut)
255 {
256 Guard g(lock_);
257 if (keys_.empty())
258 {
259 return false;
260 }
261 kOut = keys_.back().key;
262 vOut = keys_.back().value;
263 return true;
264 }
265
266 bool removeAndRecycleOldestEntry(Value &vOut)
267 {
268 Guard g(lock_);
269 if (keys_.empty())
270 {
271 return false;
272 }
273 vOut = std::move(keys_.back().value);
274 cache_.erase(keys_.back().key);
275 keys_.pop_back();
276 return true;
277 }
278
279 size_t getMaxSize() const
280 {
281 return maxSize_;
282 }
283
284 size_t getElasticity() const
285 {
286 return elasticity_;
287 }
288
289 size_t getMaxAllowedSize() const
290 {
291 return maxSize_ + elasticity_;
292 }
293
294 template <typename F> void cwalk(F &f) const
295 {
296 Guard g(lock_);
297 std::for_each(keys_.begin(), keys_.end(), f);
298 }
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 size_t prune()
308 {
309 size_t maxAllowed = maxSize_ + elasticity_;
310 if (maxSize_ == 0 || cache_.size() <= maxAllowed)
311 { /* ERO: changed < to <= */
312 return 0;
313 }
314 size_t count = 0;
315 while (cache_.size() > maxSize_)
316 {
317 cache_.erase(keys_.back().key);
318 keys_.pop_back();
319 ++count;
320 }
321 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
@ F
F-type formatting.