Thrill  0.1
lru_cache.hpp
Go to the documentation of this file.
1 /*******************************************************************************
2  * tlx/container/lru_cache.hpp
3  *
4  * An expected O(1) LRU cache which contains a set of key -> value associations.
5  * Loosely based on https://github.com/lamerman/cpp-lru-cache by Alexander
6  * Ponomarev. Rewritten for Thrill's block pool, then generalized for tlx.
7  *
8  * Part of tlx - http://panthema.net/tlx
9  *
10  * Copyright (C) 2016-2017 Timo Bingmann <[email protected]>
11  *
12  * All rights reserved. Published under the Boost Software License, Version 1.0
13  ******************************************************************************/
14 
15 #ifndef TLX_CONTAINER_LRU_CACHE_HEADER
16 #define TLX_CONTAINER_LRU_CACHE_HEADER
17 
18 #include <cassert>
19 #include <cstddef>
20 #include <functional>
21 #include <list>
22 #include <memory>
23 #include <stdexcept>
24 #include <unordered_map>
25 #include <utility>
26 
27 namespace tlx {
28 
29 //! \addtogroup tlx_container
30 //! \{
31 
32 /*!
33  * This is an expected O(1) LRU cache which contains a set of key-only
34  * elements. Elements can be put() into LRU cache, and tested for existence
35  * using exists(). Insertion and touch() will remark the elements as most
36  * recently used, pushing all other back in priority. The LRU cache itself does
37  * not limit the number of items, because it has no eviction mechanism. Instead,
38  * the user program must check size() after an insert and may extract the least
39  * recently used element.
40  */
41 template <typename Key, typename Alloc = std::allocator<Key> >
43 {
44 protected:
45  using List = typename std::list<Key, Alloc>;
46  using ListIterator = typename List::iterator;
47 
48  using Map = typename std::unordered_map<
49  Key, ListIterator, std::hash<Key>, std::equal_to<Key>,
50  typename Alloc::template rebind<
51  std::pair<const Key, ListIterator> >::other>;
52 
53 public:
54  explicit LruCacheSet(const Alloc& alloc = Alloc())
55  : list_(alloc),
56  map_(0, std::hash<Key>(), std::equal_to<Key>(), alloc) { }
57 
58  //! clear LRU
59  void clear() {
60  list_.clear();
61  map_.clear();
62  }
63 
64  //! put or replace/touch item in LRU cache
65  void put(const Key& key) {
66  // first try to find an existing key
67  typename Map::iterator it = map_.find(key);
68  if (it != map_.end()) {
69  list_.erase(it->second);
70  map_.erase(it);
71  }
72 
73  // insert key into linked list at the front (most recently used)
74  list_.push_front(key);
75  // store iterator to linked list entry in map
76  map_.insert(std::make_pair(key, list_.begin()));
77  }
78 
79  //! touch value from LRU cache for key.
80  void touch(const Key& key) {
81  typename Map::iterator it = map_.find(key);
82  if (it == map_.end()) {
83  throw std::range_error("There is no such key in cache");
84  }
85  else {
86 
87  list_.splice(list_.begin(), list_, it->second);
88  }
89  }
90 
91  //! touch value from LRU cache for key.
92  bool touch_if_exists(const Key& key) noexcept {
93  typename Map::iterator it = map_.find(key);
94  if (it != map_.end()) {
95  list_.splice(list_.begin(), list_, it->second);
96  return true;
97  }
98  return false;
99  }
100 
101  //! remove key from LRU cache
102  void erase(const Key& key) {
103  typename Map::iterator it = map_.find(key);
104  if (it == map_.end()) {
105  throw std::range_error("There is no such key in cache");
106  }
107  else {
108  list_.erase(it->second);
109  map_.erase(it);
110  }
111  }
112 
113  //! remove key from LRU cache
114  bool erase_if_exists(const Key& key) noexcept {
115  typename Map::iterator it = map_.find(key);
116  if (it != map_.end()) {
117  list_.erase(it->second);
118  map_.erase(it);
119  return true;
120  }
121  return false;
122  }
123 
124  //! test if key exists in LRU cache
125  bool exists(const Key& key) const {
126  return map_.find(key) != map_.end();
127  }
128 
129  //! return number of items in LRU cache
130  size_t size() const noexcept {
131  return map_.size();
132  }
133 
134  //! return the least recently used key value pair
135  Key pop() {
136  assert(size());
137  typename List::iterator last = list_.end();
138  --last;
139  Key out = *last;
140  map_.erase(out);
141  list_.pop_back();
142  return out;
143  }
144 
145 private:
146  //! list of entries in least-recently used order.
148  //! map for accelerated access to keys
150 };
151 
152 /*!
153  * This is an expected O(1) LRU cache which contains a map of (key -> value)
154  * elements. Elements can be put() by key into LRU cache, and later retrieved
155  * with get() using the same key. Insertion and retrieval will remark the
156  * elements as most recently used, pushing all other back in priority. The LRU
157  * cache itself does not limit the number of items, because it has no eviction
158  * mechanism. Instead, the user program must check size() before or after an
159  * insert and may extract the least recently used element.
160  */
161 template <typename Key, typename Value,
162  typename Alloc = std::allocator<std::pair<Key, Value> > >
164 {
165 public:
166  using KeyValuePair = typename std::pair<Key, Value>;
167 
168 protected:
169  using List = typename std::list<KeyValuePair, Alloc>;
170  using ListIterator = typename List::iterator;
171 
172  using Map = typename std::unordered_map<
173  Key, ListIterator, std::hash<Key>, std::equal_to<Key>,
174  typename Alloc::template rebind<
175  std::pair<const Key, ListIterator> >::other>;
176 
177 public:
178  explicit LruCacheMap(const Alloc& alloc = Alloc())
179  : list_(alloc),
180  map_(0, std::hash<Key>(), std::equal_to<Key>(), alloc) { }
181 
182  //! clear LRU
183  void clear() {
184  list_.clear();
185  map_.clear();
186  }
187 
188  //! put or replace/touch item in LRU cache
189  void put(const Key& key, const Value& value) {
190  // first try to find an existing key
191  typename Map::iterator it = map_.find(key);
192  if (it != map_.end()) {
193  list_.erase(it->second);
194  map_.erase(it);
195  }
196 
197  // insert key into linked list at the front (most recently used)
198  list_.push_front(KeyValuePair(key, value));
199  // store iterator to linked list entry in map
200  map_.insert(std::make_pair(key, list_.begin()));
201  }
202 
203  //! touch pair in LRU cache for key. Throws if it is not in the map.
204  void touch(const Key& key) {
205  typename Map::iterator it = map_.find(key);
206  if (it == map_.end()) {
207  throw std::range_error("There is no such key in cache");
208  }
209  else {
210  list_.splice(list_.begin(), list_, it->second);
211  }
212  }
213 
214  //! touch pair in LRU cache for key. Returns true if it exists.
215  bool touch_if_exists(const Key& key) noexcept {
216  typename Map::iterator it = map_.find(key);
217  if (it != map_.end()) {
218  list_.splice(list_.begin(), list_, it->second);
219  return true;
220  }
221  return false;
222  }
223 
224  //! remove key from LRU cache
225  void erase(const Key& key) {
226  typename Map::iterator it = map_.find(key);
227  if (it == map_.end()) {
228  throw std::range_error("There is no such key in cache");
229  }
230  else {
231  list_.erase(it->second);
232  map_.erase(it);
233  }
234  }
235 
236  //! remove key from LRU cache
237  bool erase_if_exists(const Key& key) noexcept {
238  typename Map::iterator it = map_.find(key);
239  if (it != map_.end()) {
240  list_.erase(it->second);
241  map_.erase(it);
242  return true;
243  }
244  return false;
245  }
246 
247  //! get and touch value from LRU cache for key.
248  const Value& get(const Key& key) {
249  typename Map::iterator it = map_.find(key);
250  if (it == map_.end()) {
251  throw std::range_error("There is no such key in cache");
252  }
253  else {
254  return it->second->second;
255  }
256  }
257 
258  //! get and touch value from LRU cache for key.
259  const Value& get_touch(const Key& key) {
260  typename Map::iterator it = map_.find(key);
261  if (it == map_.end()) {
262  throw std::range_error("There is no such key in cache");
263  }
264  else {
265  list_.splice(list_.begin(), list_, it->second);
266  return it->second->second;
267  }
268  }
269 
270  //! test if key exists in LRU cache
271  bool exists(const Key& key) const {
272  return map_.find(key) != map_.end();
273  }
274 
275  //! return number of items in LRU cache
276  size_t size() const noexcept {
277  return map_.size();
278  }
279 
280  //! return the least recently used key value pair
282  assert(size());
283  typename List::iterator last = list_.end();
284  --last;
285  KeyValuePair out = *last;
286  map_.erase(last->first);
287  list_.pop_back();
288  return out;
289  }
290 
291 private:
292  //! list of entries in least-recently used order.
294  //! map for accelerated access to keys
296 };
297 
298 //! \}
299 
300 } // namespace tlx
301 
302 #endif // !TLX_CONTAINER_LRU_CACHE_HEADER
303 
304 /******************************************************************************/
typename std::list< KeyValuePair, Alloc > List
Definition: lru_cache.hpp:169
bool exists(const Key &key) const
test if key exists in LRU cache
Definition: lru_cache.hpp:271
void put(const Key &key)
put or replace/touch item in LRU cache
Definition: lru_cache.hpp:65
bool exists(const Key &key) const
test if key exists in LRU cache
Definition: lru_cache.hpp:125
void erase(const Key &key)
remove key from LRU cache
Definition: lru_cache.hpp:102
This is an expected O(1) LRU cache which contains a set of key-only elements.
Definition: lru_cache.hpp:42
void erase(const Key &key)
remove key from LRU cache
Definition: lru_cache.hpp:225
STL namespace.
List list_
list of entries in least-recently used order.
Definition: lru_cache.hpp:293
const Value & get_touch(const Key &key)
get and touch value from LRU cache for key.
Definition: lru_cache.hpp:259
void touch(const Key &key)
touch value from LRU cache for key.
Definition: lru_cache.hpp:80
void put(const Key &key, const Value &value)
put or replace/touch item in LRU cache
Definition: lru_cache.hpp:189
LruCacheMap(const Alloc &alloc=Alloc())
Definition: lru_cache.hpp:178
This is an expected O(1) LRU cache which contains a map of (key -> value) elements.
Definition: lru_cache.hpp:163
typename std::unordered_map< thrill::data::ByteBlock *, ListIterator, std::hash< thrill::data::ByteBlock * >, std::equal_to< thrill::data::ByteBlock * >, typename thrill::mem::FixedPoolAllocator< thrill::data::ByteBlock * > ::template rebind< std::pair< const thrill::data::ByteBlock *, ListIterator > >::other > Map
Definition: lru_cache.hpp:51
int value
Definition: gen_data.py:41
Map map_
map for accelerated access to keys
Definition: lru_cache.hpp:295
void touch(const Key &key)
touch pair in LRU cache for key. Throws if it is not in the map.
Definition: lru_cache.hpp:204
bool touch_if_exists(const Key &key) noexcept
touch value from LRU cache for key.
Definition: lru_cache.hpp:92
bool erase_if_exists(const Key &key) noexcept
remove key from LRU cache
Definition: lru_cache.hpp:114
LruCacheSet(const Alloc &alloc=Alloc())
Definition: lru_cache.hpp:54
Map map_
map for accelerated access to keys
Definition: lru_cache.hpp:149
KeyValuePair pop()
return the least recently used key value pair
Definition: lru_cache.hpp:281
Key pop()
return the least recently used key value pair
Definition: lru_cache.hpp:135
bool erase_if_exists(const Key &key) noexcept
remove key from LRU cache
Definition: lru_cache.hpp:237
void clear()
clear LRU
Definition: lru_cache.hpp:183
typename std::pair< Key, Value > KeyValuePair
Definition: lru_cache.hpp:166
void clear()
clear LRU
Definition: lru_cache.hpp:59
List list_
list of entries in least-recently used order.
Definition: lru_cache.hpp:147
HashCrc32< T > hash
Select a hashing method.
Definition: hash.hpp:262
bool touch_if_exists(const Key &key) noexcept
touch pair in LRU cache for key. Returns true if it exists.
Definition: lru_cache.hpp:215
size_t size() const noexcept
return number of items in LRU cache
Definition: lru_cache.hpp:276
typename std::unordered_map< Key, ListIterator, std::hash< Key >, std::equal_to< Key >, typename Alloc::template rebind< std::pair< const Key, ListIterator > >::other > Map
Definition: lru_cache.hpp:175
size_t size() const noexcept
return number of items in LRU cache
Definition: lru_cache.hpp:130
typename std::list< thrill::data::ByteBlock *, thrill::mem::FixedPoolAllocator< thrill::data::ByteBlock * > > List
Definition: lru_cache.hpp:45