Debian Codegraph @

src/utils/lru_cache.hpp

raw
1 #ifndef LRU_CACHE_HPP
2 #define LRU_CACHE_HPP
3
4 #include "utils/error.hpp"
5 #include "utils/optional.hpp"
6
7 #include <list>
8 #include <unordered_map>
9
10 CPPTRACE_BEGIN_NAMESPACE
11 namespace detail {
12 template<typename K, typename V>
13 class lru_cache {
14 struct kvp {
15 K key;
16 V value;
17 };
18 using list_type = std::list<kvp>;
19 using list_iterator = typename list_type::iterator;
20 mutable list_type lru;
21 std::unordered_map<K, list_iterator> map;
22 optional<std::size_t> max_size;
23
24 public:
25 lru_cache() = default;
26 lru_cache(optional<std::size_t> max_size) : max_size(max_size) {
27 VERIFY(!max_size || max_size.unwrap() > 0);
28 }
29
30 void set_max_size(optional<std::size_t> size) {
31 VERIFY(!size || size.unwrap() > 0);
32 max_size = size;
33 maybe_trim();
34 }
35
36 void maybe_touch(const K& key) {
37 auto it = map.find(key);
38 if(it == map.end()) {
39 return;
40 }
41 auto list_it = it->second;
42 touch(list_it);
43 }
44
45 optional<V&> maybe_get(const K& key) {
46 auto it = map.find(key);
47 if(it == map.end()) {
48 return nullopt;
49 } else {
50 touch(it->second);
51 return it->second->value;
52 }
53 }
54
55 optional<const V&> maybe_get(const K& key) const {
56 auto it = map.find(key);
57 if(it == map.end()) {
58 return nullopt;
59 } else {
60 touch(it->second);
61 return it->second->value;
62 }
63 }
64
65 void set(const K& key, V value) {
66 auto it = map.find(key);
67 if(it == map.end()) {
68 insert(key, std::move(value));
69 } else {
70 touch(it->second);
71 it->second->value = std::move(value);
72 }
73 }
74
75 optional<V&> insert(const K& key, V value) {
76 auto pair = map.insert({key, lru.end()});
77 if(!pair.second) {
78 // didn't insert
79 return nullopt;
80 }
81 auto map_it = pair.first;
82 lru.push_front({key, std::move(value)});
83 map_it->second = lru.begin();
84 maybe_trim();
85 return lru.front().value;
86 }
87
88 std::size_t size() const {
89 return lru.size();
90 }
91
92 private:
93 void touch(list_iterator list_it) const {
94 lru.splice(lru.begin(), lru, list_it);
95 }
96
97 void maybe_trim() {
98 while(max_size && lru.size() > max_size.unwrap()) {
99 const auto& to_remove = lru.back();
100 map.erase(to_remove.key);
101 lru.pop_back();
102 }
103 }
104 };
105 }
106 CPPTRACE_END_NAMESPACE
107
108 #endif