1 // Copyright 2016 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/Math.hpp"
19
20 #include <type_traits>
21 #include <unordered_map>
22
23 namespace sw {
24
25 template<class Key, class Data>
26 class LRUCache
27 {
28 public:
29 LRUCache(int n);
30
31 virtual ~LRUCache();
32
33 Data query(const Key &key) const;
34 virtual Data add(const Key &key, const Data &data);
35
getSize()36 int getSize() { return size; }
getKey(int i)37 Key &getKey(int i) { return key[i]; }
38
39 protected:
40 int size;
41 int mask;
42 int top;
43 int fill;
44
45 Key *key;
46 Key **ref;
47 Data *data;
48 };
49
50 template<class Key, class Data, class Hasher = std::hash<Key>>
51 class LRUConstCache : public LRUCache<Key, Data>
52 {
53 using LRUBase = LRUCache<Key, Data>;
54
55 public:
LRUConstCache(int n)56 LRUConstCache(int n)
57 : LRUBase(n)
58 {}
~LRUConstCache()59 ~LRUConstCache() { clearConstCache(); }
60
add(const Key & key,const Data & data)61 Data add(const Key &key, const Data &data) override
62 {
63 constCacheNeedsUpdate = true;
64 return LRUBase::add(key, data);
65 }
66
67 void updateConstCache();
68 const Data &queryConstCache(const Key &key) const;
69
70 private:
71 void clearConstCache();
72 bool constCacheNeedsUpdate = false;
73 std::unordered_map<Key, Data, Hasher> constCache;
74 };
75
76 // Traits-like helper class for checking if objects can be compared using memcmp().
77 // Useful for statically asserting if a cache key can implement operator==() with memcmp().
78 template<typename T>
79 struct is_memcmparable
80 {
81 // std::is_trivially_copyable is not available in older GCC versions.
82 #if !defined(__GNUC__) || __GNUC__ > 5
83 static const bool value = std::is_trivially_copyable<T>::value;
84 #else
85 // At least check it doesn't have virtual methods.
86 static const bool value = !std::is_polymorphic<T>::value;
87 #endif
88 };
89 } // namespace sw
90
91 namespace sw {
92
93 template<class Key, class Data>
LRUCache(int n)94 LRUCache<Key, Data>::LRUCache(int n)
95 {
96 size = ceilPow2(n);
97 mask = size - 1;
98 top = 0;
99 fill = 0;
100
101 key = new Key[size];
102 ref = new Key *[size];
103 data = new Data[size];
104
105 for(int i = 0; i < size; i++)
106 {
107 ref[i] = &key[i];
108 }
109 }
110
111 template<class Key, class Data>
~LRUCache()112 LRUCache<Key, Data>::~LRUCache()
113 {
114 delete[] key;
115 key = nullptr;
116
117 delete[] ref;
118 ref = nullptr;
119
120 delete[] data;
121 data = nullptr;
122 }
123
124 template<class Key, class Data>
query(const Key & key) const125 Data LRUCache<Key, Data>::query(const Key &key) const
126 {
127 for(int i = top; i > top - fill; i--)
128 {
129 int j = i & mask;
130
131 if(key == *ref[j])
132 {
133 Data hit = data[j];
134
135 if(i != top)
136 {
137 // Move one up
138 int k = (j + 1) & mask;
139
140 Data swapD = data[k];
141 data[k] = data[j];
142 data[j] = swapD;
143
144 Key *swapK = ref[k];
145 ref[k] = ref[j];
146 ref[j] = swapK;
147 }
148
149 return hit;
150 }
151 }
152
153 return {}; // Not found
154 }
155
156 template<class Key, class Data>
add(const Key & key,const Data & data)157 Data LRUCache<Key, Data>::add(const Key &key, const Data &data)
158 {
159 top = (top + 1) & mask;
160 fill = fill + 1 < size ? fill + 1 : size;
161
162 *ref[top] = key;
163 this->data[top] = data;
164
165 return data;
166 }
167
168 template<class Key, class Data, class Hasher>
clearConstCache()169 void LRUConstCache<Key, Data, Hasher>::clearConstCache()
170 {
171 constCache.clear();
172 }
173
174 template<class Key, class Data, class Hasher>
updateConstCache()175 void LRUConstCache<Key, Data, Hasher>::updateConstCache()
176 {
177 if(constCacheNeedsUpdate)
178 {
179 clearConstCache();
180
181 for(int i = 0; i < LRUBase::size; i++)
182 {
183 if(LRUBase::data[i])
184 {
185 constCache[*LRUBase::ref[i]] = LRUBase::data[i];
186 }
187 }
188
189 constCacheNeedsUpdate = false;
190 }
191 }
192
193 template<class Key, class Data, class Hasher>
queryConstCache(const Key & key) const194 const Data &LRUConstCache<Key, Data, Hasher>::queryConstCache(const Key &key) const
195 {
196 auto it = constCache.find(key);
197 static Data null = {};
198 return (it != constCache.end()) ? it->second : null;
199 }
200
201 } // namespace sw
202
203 #endif // sw_LRUCache_hpp
204