1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
// vim: ts=8 sw=2 smarttab
#pragma once
#include <list>
#include <map>
#include <optional>
#include <type_traits>
#include <unordered_map>
template <class Key, class Value, bool Ordered>
class SimpleLRU {
static_assert(std::is_default_constructible_v<Value>);
using list_type = std::list<Key>;
template<class K, class V>
using map_t = std::conditional_t<Ordered,
std::map<K, V>,
std::unordered_map<K, V>>;
using map_type = map_t<Key, std::pair<Value, typename list_type::iterator>>;
list_type lru;
map_type cache;
const size_t max_size;
public:
SimpleLRU(size_t size = 20)
: cache(size),
max_size(size)
{}
size_t size() const {
return cache.size();
}
size_t capacity() const {
return max_size;
}
using insert_return_type = std::pair<Value, bool>;
insert_return_type insert(const Key& key, Value value);
std::optional<Value> find(const Key& key);
std::optional<std::enable_if<Ordered, Value>> lower_bound(const Key& key);
void erase(const Key& key);
void clear();
private:
// bump the item to the front of the lru list
Value _lru_add(typename map_type::iterator found);
// evict the last element of most recently used list
void _evict();
};
template <class Key, class Value, bool Ordered>
typename SimpleLRU<Key,Value,Ordered>::insert_return_type
SimpleLRU<Key,Value,Ordered>::insert(const Key& key, Value value)
{
if constexpr(Ordered) {
auto found = cache.lower_bound(key);
if (found != cache.end() && found->first == key) {
// already exists
return {found->second.first, true};
} else {
if (size() >= capacity()) {
_evict();
}
lru.push_front(key);
// use lower_bound as hint to save the lookup
cache.emplace_hint(found, key, std::make_pair(value, lru.begin()));
return {std::move(value), false};
}
} else {
// cache is not ordered
auto found = cache.find(key);
if (found != cache.end()) {
// already exists
return {found->second.first, true};
} else {
if (size() >= capacity()) {
_evict();
}
lru.push_front(key);
cache.emplace(key, std::make_pair(value, lru.begin()));
return {std::move(value), false};
}
}
}
template <class Key, class Value, bool Ordered>
std::optional<Value> SimpleLRU<Key,Value,Ordered>::find(const Key& key)
{
if (auto found = cache.find(key); found != cache.end()){
return _lru_add(found);
} else {
return {};
}
}
template <class Key, class Value, bool Ordered>
std::optional<std::enable_if<Ordered, Value>>
SimpleLRU<Key,Value,Ordered>::lower_bound(const Key& key)
{
if (auto found = cache.lower_bound(key); found != cache.end()) {
return _lru_add(found);
} else {
return {};
}
}
template <class Key, class Value, bool Ordered>
void SimpleLRU<Key,Value,Ordered>::clear()
{
lru.clear();
cache.clear();
}
template <class Key, class Value, bool Ordered>
void SimpleLRU<Key,Value,Ordered>::erase(const Key& key)
{
if (auto found = cache.find(key); found != cache.end()) {
lru.erase(found->second.second);
cache.erase(found);
}
}
template <class Key, class Value, bool Ordered>
Value SimpleLRU<Key,Value,Ordered>::_lru_add(
typename SimpleLRU<Key,Value,Ordered>::map_type::iterator found)
{
auto& [value, in_lru] = found->second;
if (in_lru != lru.begin()){
// move item to the front
lru.splice(lru.begin(), lru, in_lru);
}
// the item is already at the front
return value;
}
template <class Key, class Value, bool Ordered>
void SimpleLRU<Key,Value,Ordered>::_evict()
{
// evict the last element of most recently used list
auto last = --lru.end();
cache.erase(*last);
lru.erase(last);
}
|
