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.