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