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 * a noop lockable concept that can be used in place of std::mutex
46 */
47 class NullLock {
48 public:
49 void lock() {}
50 void unlock() {}
51 bool try_lock() { return true; }
52 };
53
57 class KeyNotFound : public std::invalid_argument {
58 public:
59 KeyNotFound() : std::invalid_argument("key_not_found") {}
60 };
61
62 template <typename K, typename V>
63 struct KeyValuePair {
64 public:
65 K key;
66 V value;
67
68 KeyValuePair(const K& k, const V& v) : key(k), value(v) {}
69 KeyValuePair(const K& k, V&& v): key(k), value(std::move(v)) {}
70 };
71
84 template <class Key, class Value, class Lock = NullLock,
85 class Map = std::unordered_map<
86 Key, typename std::list<KeyValuePair<Key, Value>>::iterator>>
87 class Cache {
88 public:
89 typedef KeyValuePair<Key, Value> node_type;
90 typedef std::list<KeyValuePair<Key, Value>> list_type;
91 typedef Map map_type;
92 typedef Lock lock_type;
93 using Guard = std::lock_guard<lock_type>;
103 explicit Cache(size_t maxSize = 64, size_t elasticity = 10)
104 : maxSize_(maxSize), elasticity_(elasticity) {}
105 virtual ~Cache() = default;
106 size_t size() const {
107 Guard g(lock_);
108 return cache_.size();
109 }
110 bool empty() const {
111 Guard g(lock_);
112 return cache_.empty();
113 }
114 void clear() {
115 Guard g(lock_);
116 cache_.clear();
117 keys_.clear();
118 }
119 void insert(const Key& k, const Value& v) {
120 Guard g(lock_);
121 const auto iter = cache_.find(k);
122 if (iter != cache_.end()) {
123 iter->second->value = v;
124 keys_.splice(keys_.begin(), keys_, iter->second);
125 return;
126 }
127
128 keys_.emplace_front(k, v);
129 cache_[k] = keys_.begin();
130 prune();
131 }
132 Value& insert(const Key& k, Value&& v) {
133 Guard g(lock_);
134 const auto iter = cache_.find(k);
135 if (iter != cache_.end()) {
136 iter->second->value = std::move(v);
137 keys_.splice(keys_.begin(), keys_, iter->second);
138 return keys_.front().value;
139 }
140
141 keys_.emplace_front(k, std::move(v));
142 cache_[k] = keys_.begin();
143 prune();
144 return keys_.front().value;
145 }
146 bool tryGet(const Key& kIn, Value& vOut) {
147 Guard g(lock_);
148 const auto iter = cache_.find(kIn);
149 if (iter == cache_.end()) {
150 return false;
151 }
152 keys_.splice(keys_.begin(), keys_, iter->second);
153 vOut = iter->second->value;
154 return true;
155 }
160 const Value& get(const Key& k) {
161 Guard g(lock_);
162 const auto iter = cache_.find(k);
163 if (iter == cache_.end()) {
164 throw KeyNotFound();
165 }
166 keys_.splice(keys_.begin(), keys_, iter->second);
167 return iter->second->value;
168 }
169 Value* getPtr(const Key& k) {
170 Guard g(lock_);
171 const auto iter = cache_.find(k);
172 if (iter == cache_.end()) {
173 return nullptr;
174 }
175 keys_.splice(keys_.begin(), keys_, iter->second);
176 return &(iter->second->value);
177 }
181 Value getCopy(const Key& k) {
182 return get(k);
183 }
184 bool remove(const Key& k) {
185 Guard g(lock_);
186 auto iter = cache_.find(k);
187 if (iter == cache_.end()) {
188 return false;
189 }
190 keys_.erase(iter->second);
191 cache_.erase(iter);
192 return true;
193 }
194 bool contains(const Key& k) {
195 Guard g(lock_);
196 return cache_.find(k) != cache_.end();
197 }
198
199 bool getOldestEntry(Key& kOut, Value& vOut) {
200 Guard g(lock_);
201 if( keys_.empty() ) {
202 return false;
203 }
204 kOut = keys_.back().key;
205 vOut = keys_.back().value;
206 return true;
207 }
208
209 bool removeAndRecycleOldestEntry(Value& vOut) {
210 Guard g(lock_);
211 if( keys_.empty() ) {
212 return false;
213 }
214 vOut = std::move(keys_.back().value);
215 cache_.erase(keys_.back().key);
216 keys_.pop_back();
217 return true;
218 }
219
220 size_t getMaxSize() const { return maxSize_; }
221 size_t getElasticity() const { return elasticity_; }
222 size_t getMaxAllowedSize() const { return maxSize_ + elasticity_; }
223 template <typename F>
224 void cwalk(F& f) const {
225 Guard g(lock_);
226 std::for_each(keys_.begin(), keys_.end(), f);
227 }
228
229 Cache(Cache&& other):
230 cache_(std::move(other.cache_)),
231 keys_(std::move(other.keys_)),
232 maxSize_(other.maxSize_),
233 elasticity_(other.elasticity_) {}
234
235 protected:
236 size_t prune() {
237 size_t maxAllowed = maxSize_ + elasticity_;
238 if (maxSize_ == 0 || cache_.size() <= maxAllowed) { /* ERO: changed < to <= */
239 return 0;
240 }
241 size_t count = 0;
242 while (cache_.size() > maxSize_) {
243 cache_.erase(keys_.back().key);
244 keys_.pop_back();
245 ++count;
246 }
247 return count;
248 }
249
250 private:
251 // Disallow copying.
252 Cache(const Cache&) = delete;
253 Cache& operator=(const Cache&) = delete;
254
255 mutable Lock lock_{};
256 Map cache_{};
257 list_type keys_{};
258 size_t maxSize_;
259 size_t elasticity_;
260 };
261
262 } // namespace LRUCache11
263
OGRWktFormat::F
@ F
F-type formatting.