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