Debian Codegraph @

LspCpp/include/LibLsp/lsp/lru_cache.h

raw
1 #pragma once
2
3 #include <algorithm>
4 #include <cassert>
5 #include <limits>
6 #include <memory>
7 #include <vector>
8 #include <cstdint>
9 // Cache that evicts old entries which have not been used recently. Implemented
10 // using array/linear search so this works well for small array sizes.
11 template<typename TKey, typename TValue>
12 struct LruCache
13 {
14 explicit LruCache(int max_entries);
15
16 // Fetches an entry for |key|. If it does not exist, |allocator| will be
17 // invoked to create one.
18 template<typename TAllocator>
19 TValue Get(TKey const& key, TAllocator allocator);
20 // Returns true if there is an entry for |key|.
21 bool Has(TKey const& key);
22 // Fetches the entry for |filename| and updates it's usage so it is less
23 // likely to be evicted.
24 bool TryGet(TKey const& key, TValue* dest);
25 // TryGetEntry, except the entry is removed from the cache.
26 bool TryTake(TKey const& key, TValue* dest);
27 // Inserts an entry. Evicts the oldest unused entry if there is no space.
28 void Insert(TKey const& key, TValue const& value);
29
30 // Call |func| on existing entries. If |func| returns false iteration
31 // terminates early.
32 template<typename TFunc>
33 void IterateValues(TFunc func);
34
35 // Empties the cache
36 void Clear(void);
37
38 private:
39 // There is a global score counter, when we access an element we increase
40 // its score to the current global value, so it has the highest overall
41 // score. This means that the oldest/least recently accessed value has the
42 // lowest score.
43 //
44 // There is a bit of special logic to handle score overlow.
45 struct Entry
46 {
47 uint32_t score = 0;
48 TKey key;
49 TValue value;
50 bool operator<(Entry const& other) const
51 {
52 return score < other.score;
53 }
54 };
55
56 void IncrementScore();
57
58 std::vector<Entry> entries_;
59 int max_entries_ = 1;
60 uint32_t next_score_ = 0;
61 };
62
63 template<typename TKey, typename TValue>
64 LruCache<TKey, TValue>::LruCache(int max_entries) : max_entries_(max_entries)
65 {
66 assert(max_entries > 0);
67 }
68
69 template<typename TKey, typename TValue>
70 template<typename TAllocator>
71 TValue LruCache<TKey, TValue>::Get(TKey const& key, TAllocator allocator)
72 {
73 for (Entry& entry : entries_)
74 {
75 if (entry.key == key)
76 {
77 return entry.value;
78 }
79 }
80
81 auto result = allocator();
82 Insert(key, result);
83 return result;
84 }
85
86 template<typename TKey, typename TValue>
87 bool LruCache<TKey, TValue>::Has(TKey const& key)
88 {
89 for (Entry& entry : entries_)
90 {
91 if (entry.key == key)
92 {
93 return true;
94 }
95 }
96 return false;
97 }
98
99 template<typename TKey, typename TValue>
100 bool LruCache<TKey, TValue>::TryGet(TKey const& key, TValue* dest)
101 {
102 // Assign new score.
103 for (Entry& entry : entries_)
104 {
105 if (entry.key == key)
106 {
107 entry.score = next_score_;
108 IncrementScore();
109 if (dest)
110 {
111 *dest = entry.value;
112 }
113 return true;
114 }
115 }
116
117 return false;
118 }
119
120 template<typename TKey, typename TValue>
121 bool LruCache<TKey, TValue>::TryTake(TKey const& key, TValue* dest)
122 {
123 for (size_t i = 0; i < entries_.size(); ++i)
124 {
125 if (entries_[i].key == key)
126 {
127 if (dest)
128 {
129 *dest = entries_[i].value;
130 }
131 entries_.erase(entries_.begin() + i);
132 return true;
133 }
134 }
135
136 return false;
137 }
138
139 template<typename TKey, typename TValue>
140 void LruCache<TKey, TValue>::Insert(TKey const& key, TValue const& value)
141 {
142 if ((int)entries_.size() >= max_entries_)
143 {
144 entries_.erase(std::min_element(entries_.begin(), entries_.end()));
145 }
146
147 Entry entry;
148 entry.score = next_score_;
149 IncrementScore();
150 entry.key = key;
151 entry.value = value;
152 entries_.push_back(entry);
153 }
154
155 template<typename TKey, typename TValue>
156 template<typename TFunc>
157 void LruCache<TKey, TValue>::IterateValues(TFunc func)
158 {
159 for (Entry& entry : entries_)
160 {
161 if (!func(entry.value))
162 {
163 break;
164 }
165 }
166 }
167
168 template<typename TKey, typename TValue>
169 void LruCache<TKey, TValue>::IncrementScore()
170 {
171 // Overflow.
172 if (++next_score_ == 0)
173 {
174 std::sort(entries_.begin(), entries_.end());
175 for (Entry& entry : entries_)
176 {
177 entry.score = next_score_++;
178 }
179 }
180 }
181
182 template<typename TKey, typename TValue>
183 void LruCache<TKey, TValue>::Clear(void)
184 {
185 entries_.clear();
186 next_score_ = 0;
187 }