Nix 2.26.3
Nix, the purely functional package manager; unstable internal interfaces
 
Loading...
Searching...
No Matches
lru-cache.hh
Go to the documentation of this file.
1#pragma once
3
4#include <cassert>
5#include <map>
6#include <list>
7#include <optional>
8
9namespace nix {
10
14template<typename Key, typename Value>
15class LRUCache
16{
17private:
18
19 size_t capacity;
20
21 // Stupid wrapper to get around circular dependency between Data
22 // and LRU.
23 struct LRUIterator;
24
25 using Data = std::map<Key, std::pair<LRUIterator, Value>>;
26 using LRU = std::list<typename Data::iterator>;
27
28 struct LRUIterator { typename LRU::iterator it; };
29
30 Data data;
31 LRU lru;
32
33public:
34
35 LRUCache(size_t capacity) : capacity(capacity) { }
36
40 void upsert(const Key & key, const Value & value)
41 {
42 if (capacity == 0) return;
43
44 erase(key);
45
46 if (data.size() >= capacity) {
50 auto oldest = lru.begin();
51 data.erase(*oldest);
52 lru.erase(oldest);
53 }
54
55 auto res = data.emplace(key, std::make_pair(LRUIterator(), value));
56 assert(res.second);
57 auto & i(res.first);
58
59 auto j = lru.insert(lru.end(), i);
60
61 i->second.first.it = j;
62 }
63
64 bool erase(const Key & key)
65 {
66 auto i = data.find(key);
67 if (i == data.end()) return false;
68 lru.erase(i->second.first.it);
69 data.erase(i);
70 return true;
71 }
72
77 std::optional<Value> get(const Key & key)
78 {
79 auto i = data.find(key);
80 if (i == data.end()) return {};
81
85 lru.erase(i->second.first.it);
86 auto j = lru.insert(lru.end(), i);
87 i->second.first.it = j;
88
89 return i->second.second;
90 }
91
92 size_t size() const
93 {
94 return data.size();
95 }
96
97 void clear()
98 {
99 data.clear();
100 lru.clear();
101 }
102};
103
104}
void upsert(const Key &key, const Value &value)
Definition lru-cache.hh:40
std::optional< Value > get(const Key &key)
Definition lru-cache.hh:77
const T::key_type & key
Definition lexer.l:2763
auto i
Definition lexer.l:2745
Strings res
Definition lexer.l:2566
std::variant< std::string, std::string_view > data
Definition lexer.l:177
ExprAttrs::AttrDefs::iterator j
Definition lexer.l:8572
const T & value
Definition lexer.l:492
Definition value.hh:167