1 // Copyright 2020 The SwiftShader Authors. All Rights Reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #ifndef sw_LRUCache_hpp
16 #define sw_LRUCache_hpp
17
18 #include "System/Debug.hpp"
19
20 #include <cstddef>
21 #include <cstdint>
22 #include <functional>
23 #include <unordered_set>
24 #include <vector>
25
26 namespace sw {
27
28 // LRUCache is a least recently used cache of a fixed capacity.
29 template<typename KEY, typename DATA, typename HASH = std::hash<KEY> >
30 class LRUCache
31 {
32 struct Entry;
33
34 public:
35 using Key = KEY;
36 using Data = DATA;
37 using Hash = HASH;
38
39 // view is a const accessor of a single cache entry.
40 class view
41 {
42 public:
43 inline view(Entry *);
44
45 inline const Key &key() const;
46 inline const Data &data() const;
47
48 private:
49 Entry *entry;
50 };
51
52 class iterator
53 {
54 public:
55 inline iterator(Entry *);
56 inline view operator*() const;
57 inline iterator &operator++();
58 inline bool operator==(const iterator &) const;
59 inline bool operator!=(const iterator &) const;
60
61 private:
62 Entry *entry;
63 };
64
65 // Construct a LRU cache with the given maximum number of entries.
66 inline LRUCache(size_t capacity);
67 inline ~LRUCache() = default;
68
69 // lookup() looks up the cache entry with the given key.
70 // If the entry is found, this is moved to the most-recent position in the
71 // cache, and its data is returned.
72 // If the entry is not found, then a default initialized Data is returned.
73 inline Data lookup(const Key &key);
74
75 // add() adds the data to the cache using the given key, placed at the
76 // most-recent position in the cache.
77 // If an existing entry exists in the cache with the given key, then this is
78 // replaced with data.
79 // If no existing entry exists in the cache, and the cache is already full
80 // then the least recently used entry is evicted before adding the new
81 // entry.
82 inline void add(const Key &key, const Data &data);
83
84 // clear() clears the cache of all elements.
85 inline void clear();
86
87 // Range based iterators.
88 inline iterator begin() const;
89 inline iterator end() const;
90
91 private:
92 LRUCache(const LRUCache &) = delete;
93 LRUCache(LRUCache &&) = delete;
94 LRUCache &operator=(const LRUCache &) = delete;
95 LRUCache &operator=(LRUCache &&) = delete;
96
97 // Keyed holds a key. See find() for more information.
98 struct Keyed
99 {
100 Key key = {};
101 };
102
103 // Cache entry structure.
104 // Holds the unique copy of the key and data, along with pointers for
105 // maintaining the linked list.
106 struct Entry : Keyed
107 {
108 Data data = {};
109 Entry *next = nullptr;
110 Entry *prev = nullptr;
111 };
112
113 // KeyedComparator is a custom hasher and equality helper for Keyed.
114 struct KeyedComparator
115 {
116 // Hash function.
117 inline uint64_t operator()(const Keyed *k) const;
118
119 // Equality function.
120 inline uint64_t operator()(const Keyed *a, const Keyed *b) const;
121 };
122
123 // find() returns the Entry* for the given key, or nullptr.
124 // find() performs this by casting the Key pointer to a Keyed pointer for
125 // searching the std::unordered_set.
126 //
127 // This is to avoid having a duplicate Key held by both an
128 // unordered_map<Key, Entry*> and the Entry itself, as the Key type may be
129 // large.
130 //
131 // While we could use an unordered_set<Entry*>, this then requires the
132 // construction of a temporary Entry to perform the call to
133 // unordered_set<Entry*>::find(). This is undesirable as the Data type might
134 // be large or have an expensive constructor.
135 //
136 // C++20 gains a new templated overload for unordered_set<Entry*>::find()
137 // which would allow us to use unordered_set<Entry*>::find(Key*).
138 // Until we can use C++20, keep this casting nastiness hidden away in this
139 // one function.
140 inline Entry *find(const Key &key);
141
142 // unlinks the entry from the list it is linked in.
143 inline void unlink(Entry *);
144
145 // links the entry to the head of the LRU.
146 inline void link(Entry *);
147
148 // storage holds the allocations of all the entries.
149 // This vector must not change size for the lifetime of the cache.
150 std::vector<Entry> storage;
151
152 // set is an unordered set of Keyed*, using the KeyedComparator for hash and
153 // equality testing.
154 std::unordered_set<const Keyed *, KeyedComparator, KeyedComparator> set;
155
156 Entry *free = nullptr; // Singly-linked (prev is nullptr) list of free entries.
157 Entry *head = nullptr; // Pointer to the most recently used entry in the LRU.
158 Entry *tail = nullptr; // Pointer to the least recently used entry in the LRU.
159 };
160
161 ////////////////////////////////////////////////////////////////////////////////
162 // LRUCache<>::view
163 ////////////////////////////////////////////////////////////////////////////////
164 template<typename KEY, typename DATA, typename HASH>
view(Entry * entry)165 LRUCache<KEY, DATA, HASH>::view::view(Entry *entry)
166 : entry(entry)
167 {}
168
169 template<typename KEY, typename DATA, typename HASH>
key() const170 const KEY &LRUCache<KEY, DATA, HASH>::view::key() const
171 {
172 return entry->key;
173 }
174
175 template<typename KEY, typename DATA, typename HASH>
data() const176 const DATA &LRUCache<KEY, DATA, HASH>::view::data() const
177 {
178 return entry->data;
179 }
180
181 ////////////////////////////////////////////////////////////////////////////////
182 // LRUCache<>::iterator
183 ////////////////////////////////////////////////////////////////////////////////
184 template<typename KEY, typename DATA, typename HASH>
iterator(Entry * entry)185 LRUCache<KEY, DATA, HASH>::iterator::iterator(Entry *entry)
186 : entry(entry)
187 {}
188
189 template<typename KEY, typename DATA, typename HASH>
operator *() const190 typename LRUCache<KEY, DATA, HASH>::view LRUCache<KEY, DATA, HASH>::iterator::operator*() const
191 {
192 return view{ entry };
193 }
194
195 template<typename KEY, typename DATA, typename HASH>
operator ++()196 typename LRUCache<KEY, DATA, HASH>::iterator &LRUCache<KEY, DATA, HASH>::iterator::operator++()
197 {
198 entry = entry->next;
199 return *this;
200 }
201
202 template<typename KEY, typename DATA, typename HASH>
operator ==(const iterator & rhs) const203 bool LRUCache<KEY, DATA, HASH>::iterator::operator==(const iterator &rhs) const
204 {
205 return entry == rhs.entry;
206 }
207
208 template<typename KEY, typename DATA, typename HASH>
operator !=(const iterator & rhs) const209 bool LRUCache<KEY, DATA, HASH>::iterator::operator!=(const iterator &rhs) const
210 {
211 return entry != rhs.entry;
212 }
213
214 ////////////////////////////////////////////////////////////////////////////////
215 // LRUCache<>
216 ////////////////////////////////////////////////////////////////////////////////
217 template<typename KEY, typename DATA, typename HASH>
LRUCache(size_t capacity)218 LRUCache<KEY, DATA, HASH>::LRUCache(size_t capacity)
219 : storage(capacity)
220 {
221 for(size_t i = 0; i < capacity; i++)
222 {
223 Entry *entry = &storage[i];
224 entry->next = free; // No need for back link here.
225 free = entry;
226 }
227 }
228
229 template<typename KEY, typename DATA, typename HASH>
lookup(const Key & key)230 DATA LRUCache<KEY, DATA, HASH>::lookup(const Key &key)
231 {
232 if(Entry *entry = find(key))
233 {
234 unlink(entry);
235 link(entry);
236 return entry->data;
237 }
238 return {};
239 }
240
241 template<typename KEY, typename DATA, typename HASH>
add(const Key & key,const Data & data)242 void LRUCache<KEY, DATA, HASH>::add(const Key &key, const Data &data)
243 {
244 if(Entry *entry = find(key))
245 {
246 // Move entry to front.
247 unlink(entry);
248 link(entry);
249 entry->data = data;
250 return;
251 }
252
253 Entry *entry = free;
254 if(entry)
255 {
256 // Unlink from free.
257 free = entry->next;
258 entry->next = nullptr;
259 }
260 else
261 {
262 // Unlink least recently used.
263 entry = tail;
264 unlink(entry);
265 set.erase(entry);
266 }
267
268 // link as most recently used.
269 link(entry);
270 if(tail == nullptr)
271 {
272 tail = entry;
273 }
274
275 entry->key = key;
276 entry->data = data;
277 set.emplace(entry);
278 }
279
280 template<typename KEY, typename DATA, typename HASH>
clear()281 void LRUCache<KEY, DATA, HASH>::clear()
282 {
283 while(Entry *entry = head)
284 {
285 unlink(entry);
286 entry->next = free; // No need for back link here.
287 free = entry;
288 }
289 set.clear();
290 }
291
292 template<typename KEY, typename DATA, typename HASH>
begin() const293 typename LRUCache<KEY, DATA, HASH>::iterator LRUCache<KEY, DATA, HASH>::begin() const
294 {
295 return { head };
296 }
297
298 template<typename KEY, typename DATA, typename HASH>
end() const299 typename LRUCache<KEY, DATA, HASH>::iterator LRUCache<KEY, DATA, HASH>::end() const
300 {
301 return { nullptr };
302 }
303
304 template<typename KEY, typename DATA, typename HASH>
unlink(Entry * entry)305 void LRUCache<KEY, DATA, HASH>::unlink(Entry *entry)
306 {
307 if(head == entry) { head = entry->next; }
308 if(tail == entry) { tail = entry->prev; }
309 if(entry->prev) { entry->prev->next = entry->next; }
310 if(entry->next) { entry->next->prev = entry->prev; }
311 entry->prev = nullptr;
312 entry->next = nullptr;
313 }
314
315 template<typename KEY, typename DATA, typename HASH>
link(Entry * entry)316 void LRUCache<KEY, DATA, HASH>::link(Entry *entry)
317 {
318 ASSERT_MSG(entry->next == nullptr, "link() called on entry already linked");
319 ASSERT_MSG(entry->prev == nullptr, "link() called on entry already linked");
320 if(head)
321 {
322 entry->next = head;
323 head->prev = entry;
324 }
325 head = entry;
326 if(!tail) { tail = entry; }
327 }
328
329 template<typename KEY, typename DATA, typename HASH>
find(const Key & key)330 typename LRUCache<KEY, DATA, HASH>::Entry *LRUCache<KEY, DATA, HASH>::find(const Key &key)
331 {
332 auto asKeyed = reinterpret_cast<const Keyed *>(&key);
333 auto it = set.find(asKeyed);
334 if(it == set.end())
335 {
336 return nullptr;
337 }
338 return const_cast<Entry *>(static_cast<const Entry *>(*it));
339 }
340
341 ////////////////////////////////////////////////////////////////////////////////
342 // LRUCache<>::KeyedComparator
343 ////////////////////////////////////////////////////////////////////////////////
344 template<typename KEY, typename DATA, typename HASH>
operator ()(const Keyed * k) const345 uint64_t LRUCache<KEY, DATA, HASH>::KeyedComparator::operator()(const Keyed *k) const
346 {
347 return Hash()(k->key);
348 }
349
350 template<typename KEY, typename DATA, typename HASH>
operator ()(const Keyed * a,const Keyed * b) const351 uint64_t LRUCache<KEY, DATA, HASH>::KeyedComparator::operator()(const Keyed *a, const Keyed *b) const
352 {
353 return a->key == b->key;
354 }
355
356 } // namespace sw
357
358 #endif // sw_LRUCache_hpp
359