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