tlx
Loading...
Searching...
No Matches
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 <tb@panthema.net>
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
27namespace 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 */
41template <typename Key, typename Alloc = std::allocator<Key> >
43{
44protected:
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 std::allocator_traits<Alloc>::template rebind_alloc<
51 std::pair<const Key, ListIterator> > >;
52
53public:
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
145private:
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 */
161template <typename Key, typename Value,
162 typename Alloc = std::allocator<std::pair<Key, Value> > >
164{
165public:
166 using KeyValuePair = typename std::pair<Key, Value>;
167
168protected:
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 std::allocator_traits<Alloc>::template rebind_alloc<
175 std::pair<const Key, ListIterator> > >;
176
177public:
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
291private:
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/******************************************************************************/
This is an expected O(1) LRU cache which contains a map of (key -> value) elements.
Definition: lru_cache.hpp:164
void put(const Key &key, const Value &value)
put or replace/touch item in LRU cache
Definition: lru_cache.hpp:189
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 pair in LRU cache for key. Returns true if it exists.
Definition: lru_cache.hpp:215
typename std::list< KeyValuePair, Alloc > List
Definition: lru_cache.hpp:169
List list_
list of entries in least-recently used order.
Definition: lru_cache.hpp:293
size_t size() const noexcept
return number of items in LRU cache
Definition: lru_cache.hpp:276
typename std::pair< Key, Value > KeyValuePair
Definition: lru_cache.hpp:166
const Value & get_touch(const Key &key)
get and touch value from LRU cache for key.
Definition: lru_cache.hpp:259
Map map_
map for accelerated access to keys
Definition: lru_cache.hpp:295
typename List::iterator ListIterator
Definition: lru_cache.hpp:170
LruCacheMap(const Alloc &alloc=Alloc())
Definition: lru_cache.hpp:178
KeyValuePair pop()
return the least recently used key value pair
Definition: lru_cache.hpp:281
bool exists(const Key &key) const
test if key exists in LRU cache
Definition: lru_cache.hpp:271
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
const Value & get(const Key &key)
get and touch value from LRU cache for key.
Definition: lru_cache.hpp:248
typename std::unordered_map< Key, ListIterator, std::hash< Key >, std::equal_to< Key >, typename std::allocator_traits< Alloc >::template rebind_alloc< std::pair< const Key, ListIterator > > > Map
Definition: lru_cache.hpp:175
void erase(const Key &key)
remove key from LRU cache
Definition: lru_cache.hpp:225
This is an expected O(1) LRU cache which contains a set of key-only elements.
Definition: lru_cache.hpp:43
void touch(const Key &key)
touch value from LRU cache for key.
Definition: lru_cache.hpp:80
bool touch_if_exists(const Key &key) noexcept
touch value from LRU cache for key.
Definition: lru_cache.hpp:92
List list_
list of entries in least-recently used order.
Definition: lru_cache.hpp:147
size_t size() const noexcept
return number of items in LRU cache
Definition: lru_cache.hpp:130
void put(const Key &key)
put or replace/touch item in LRU cache
Definition: lru_cache.hpp:65
LruCacheSet(const Alloc &alloc=Alloc())
Definition: lru_cache.hpp:54
Map map_
map for accelerated access to keys
Definition: lru_cache.hpp:149
Key pop()
return the least recently used key value pair
Definition: lru_cache.hpp:135
typename List::iterator ListIterator
Definition: lru_cache.hpp:46
bool exists(const Key &key) const
test if key exists in LRU cache
Definition: lru_cache.hpp:125
bool erase_if_exists(const Key &key) noexcept
remove key from LRU cache
Definition: lru_cache.hpp:114
void clear()
clear LRU
Definition: lru_cache.hpp:59
typename std::unordered_map< Key, ListIterator, std::hash< Key >, std::equal_to< Key >, typename std::allocator_traits< Alloc >::template rebind_alloc< std::pair< const Key, ListIterator > > > Map
Definition: lru_cache.hpp:51
void erase(const Key &key)
remove key from LRU cache
Definition: lru_cache.hpp:102
typename std::list< Key, Alloc > List
Definition: lru_cache.hpp:45
STL namespace.