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.