blob: 8f955a078d726443545a2e9970847c95fef3a52a (
plain)
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
|
/*
* Copyright 2023 jacqueline <me@jacqueline.id.au>
*
* SPDX-License-Identifier: GPL-3.0-only
*/
#pragma once
#include <algorithm>
#include <bitset>
#include <cstdint>
#include <list>
#include <optional>
#include <unordered_map>
#include <utility>
namespace util {
/*
* Basic least recently used cache. Stores the `Size` most recently accessed
* entries in memory.
*
* Not safe for use from multiple tasks, but all operations are constant time.
*/
template <int Size, typename K, typename V>
class LruCache {
public:
LruCache() : entries_(), key_to_it_() {}
auto Put(K key, V val) -> void {
if (key_to_it_.contains(key)) {
// This key was already present. Overwrite by removing the previous
// value.
entries_.erase(key_to_it_[key]);
key_to_it_.erase(key);
} else if (entries_.size() >= Size) {
// Cache is full. Evict the last entry.
key_to_it_.erase(entries_.back().first);
entries_.pop_back();
}
// Add the new value.
entries_.push_front({key, val});
key_to_it_[key] = entries_.begin();
}
auto Get(K key) -> std::optional<V> {
if (!key_to_it_.contains(key)) {
return {};
}
// Use splice() to move the entry to the front of the list. This approach
// doesn't invalidate any of the iterators in key_to_it_, and is constant
// time.
auto it = key_to_it_[key];
entries_.splice(entries_.begin(), entries_, it);
return it->second;
}
auto Clear() -> void {
entries_.clear();
key_to_it_.clear();
}
private:
std::list<std::pair<K, V>> entries_;
std::unordered_map<K, decltype(entries_.begin())> key_to_it_;
};
} // namespace util
|
