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  protected:
195  size_t prune() {
196  size_t maxAllowed = maxSize_ + elasticity_;
197  if (maxSize_ == 0 || cache_.size() <= maxAllowed) { /* ERO: changed < to <= */
198  return 0;
199  }
200  size_t count = 0;
201  while (cache_.size() > maxSize_) {
202  cache_.erase(keys_.back().key);
203  keys_.pop_back();
204  ++count;
205  }
206  return count;
207  }
208 
209  private:
210  // Dissallow copying.
211  Cache(const Cache&) = delete;
212  Cache& operator=(const Cache&) = delete;
213 
214  mutable Lock lock_{};
215  Map cache_{};
216  list_type keys_{};
217  size_t maxSize_;
218  size_t elasticity_;
219 };
220 
221 } // namespace LRUCache11
222 

Generated for GDAL by doxygen 1.8.8.