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 };
70
83 template <class Key, class Value, class Lock = NullLock,
84 class Map = std::unordered_map<
85 Key, typename std::list<KeyValuePair<Key, Value>>::iterator>>
86 class Cache {
87 public:
88 typedef KeyValuePair<Key, Value> node_type;
89 typedef std::list<KeyValuePair<Key, Value>> list_type;
90 typedef Map map_type;
91 typedef Lock lock_type;
92 using Guard = std::lock_guard<lock_type>;
102 explicit Cache(size_t maxSize = 64, size_t elasticity = 10)
103 : maxSize_(maxSize), elasticity_(elasticity) {}
104 virtual ~Cache() = default;
105 size_t size() const {
106 Guard g(lock_);
107 return cache_.size();
108 }
109 bool empty() const {
110 Guard g(lock_);
111 return cache_.empty();
112 }
113 void clear() {
114 Guard g(lock_);
115 cache_.clear();
116 keys_.clear();
117 }
118 void insert(const Key& k, const Value& v) {
119 Guard g(lock_);
120 const auto iter = cache_.find(k);
121 if (iter != cache_.end()) {
122 iter->second->value = v;
123 keys_.splice(keys_.begin(), keys_, iter->second);
124 return;
125 }
126
127 keys_.emplace_front(k, v);
128 cache_[k] = keys_.begin();
129 prune();
130 }
131 bool tryGet(const Key& kIn, Value& vOut) {
132 Guard g(lock_);
133 const auto iter = cache_.find(kIn);
134 if (iter == cache_.end()) {
135 return false;
136 }
137 keys_.splice(keys_.begin(), keys_, iter->second);
138 vOut = iter->second->value;
139 return true;
140 }
145 const Value& get(const Key& k) {
146 Guard g(lock_);
147 const auto iter = cache_.find(k);
148 if (iter == cache_.end()) {
149 throw KeyNotFound();
150 }
151 keys_.splice(keys_.begin(), keys_, iter->second);
152 return iter->second->value;
153 }
157 Value getCopy(const Key& k) {
158 return get(k);
159 }
160 bool remove(const Key& k) {
161 Guard g(lock_);
162 auto iter = cache_.find(k);
163 if (iter == cache_.end()) {
164 return false;
165 }
166 keys_.erase(iter->second);
167 cache_.erase(iter);
168 return true;
169 }
170 bool contains(const Key& k) {
171 Guard g(lock_);
172 return cache_.find(k) != cache_.end();
173 }
174
175 bool getOldestEntry(Key& kOut, Value& vOut) {
176 Guard g(lock_);
177 if( keys_.empty() ) {
178 return false;
179 }
180 kOut = keys_.back().key;
181 vOut = keys_.back().value;
182 return true;
183 }
184
185 size_t getMaxSize() const { return maxSize_; }
186 size_t getElasticity() const { return elasticity_; }
187 size_t getMaxAllowedSize() const { return maxSize_ + elasticity_; }
188 template <typename F>
189 void cwalk(F& f) const {
190 Guard g(lock_);
191 std::for_each(keys_.begin(), keys_.end(), f);
192 }
193
194 Cache(Cache&& other):
195 cache_(std::move(other.cache_)),
196 keys_(std::move(other.keys_)),
197 maxSize_(other.maxSize_),
198 elasticity_(other.elasticity_) {}
199
200 protected:
201 size_t prune() {
202 size_t maxAllowed = maxSize_ + elasticity_;
203 if (maxSize_ == 0 || cache_.size() <= maxAllowed) { /* ERO: changed < to <= */
204 return 0;
205 }
206 size_t count = 0;
207 while (cache_.size() > maxSize_) {
208 cache_.erase(keys_.back().key);
209 keys_.pop_back();
210 ++count;
211 }
212 return count;
213 }
214
215 private:
216 // Disallow copying.
217 Cache(const Cache&) = delete;
218 Cache& operator=(const Cache&) = delete;
219
220 mutable Lock lock_{};
221 Map cache_{};
222 list_type keys_{};
223 size_t maxSize_;
224 size_t elasticity_;
225 };
226
227 } // namespace LRUCache11
228
OGRWktFormat::F
@ F
F-type formatting.