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