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  size_t getMaxSize() const { return maxSize_; }
176  size_t getElasticity() const { return elasticity_; }
177  size_t getMaxAllowedSize() const { return maxSize_ + elasticity_; }
178  template <typename F>
179  void cwalk(F& f) const {
180  Guard g(lock_);
181  std::for_each(keys_.begin(), keys_.end(), f);
182  }
183 
184  protected:
185  size_t prune() {
186  size_t maxAllowed = maxSize_ + elasticity_;
187  if (maxSize_ == 0 || cache_.size() <= maxAllowed) { /* ERO: changed < to <= */
188  return 0;
189  }
190  size_t count = 0;
191  while (cache_.size() > maxSize_) {
192  cache_.erase(keys_.back().key);
193  keys_.pop_back();
194  ++count;
195  }
196  return count;
197  }
198 
199  private:
200  // Dissallow copying.
201  Cache(const Cache&) = delete;
202  Cache& operator=(const Cache&) = delete;
203 
204  mutable Lock lock_{};
205  Map cache_{};
206  list_type keys_{};
207  size_t maxSize_;
208  size_t elasticity_;
209 };
210 
211 } // namespace LRUCache11
212 

Generated for GDAL by doxygen 1.8.8.