blob: f6fcdaf82ebdcd755e57d3506ebe0cceffe2eea9 (
plain) (
blame)
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
|
#pragma once
#include <list>
#include <map>
#include <optional>
namespace nix {
/* A simple least-recently used cache. Not thread-safe. */
template <typename Key, typename Value>
class LRUCache {
private:
size_t capacity;
// Stupid wrapper to get around circular dependency between Data
// and LRU.
struct LRUIterator;
using Data = std::map<Key, std::pair<LRUIterator, Value>>;
using LRU = std::list<typename Data::iterator>;
struct LRUIterator {
typename LRU::iterator it;
};
Data data;
LRU lru;
public:
LRUCache(size_t capacity) : capacity(capacity) {}
/* Insert or upsert an item in the cache. */
void upsert(const Key& key, const Value& value) {
if (capacity == 0) {
return;
}
erase(key);
if (data.size() >= capacity) {
/* Retire the oldest item. */
auto oldest = lru.begin();
data.erase(*oldest);
lru.erase(oldest);
}
auto res = data.emplace(key, std::make_pair(LRUIterator(), value));
assert(res.second);
auto& i(res.first);
auto j = lru.insert(lru.end(), i);
i->second.first.it = j;
}
bool erase(const Key& key) {
auto i = data.find(key);
if (i == data.end()) {
return false;
}
lru.erase(i->second.first.it);
data.erase(i);
return true;
}
/* Look up an item in the cache. If it exists, it becomes the most
recently used item. */
std::optional<Value> get(const Key& key) {
auto i = data.find(key);
if (i == data.end()) {
return {};
}
/* Move this item to the back of the LRU list. */
lru.erase(i->second.first.it);
auto j = lru.insert(lru.end(), i);
i->second.first.it = j;
return i->second.second;
}
size_t size() { return data.size(); }
void clear() {
data.clear();
lru.clear();
}
};
} // namespace nix
|
