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 "Common/Math.hpp" 19 20 #include <cstring> 21 #include <type_traits> 22 23 namespace sw 24 { 25 template<class Key, class Data> 26 class LRUCache 27 { 28 public: 29 LRUCache(int n); 30 31 ~LRUCache(); 32 33 Data query(const Key &key) const; 34 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 private: 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 // Helper class for clearing the memory of objects at construction. 51 // Useful as the first base class of cache keys which may contain padding bytes or bits otherwise left uninitialized. 52 template<class T> 53 struct Memset 54 { Memsetsw::Memset55 Memset(T *object, int val) 56 { 57 static_assert(std::is_base_of<Memset<T>, T>::value, "Memset<T> must only clear the memory of a type of which it is a base class"); 58 59 // GCC 8+ warns that 60 // "‘void* memset(void*, int, size_t)’ clearing an object of non-trivial type ‘T’; 61 // use assignment or value-initialization instead [-Werror=class-memaccess]" 62 // This is benign iff it happens before any of the base or member constructrs are called. 63 #if defined(__GNUC__) && (__GNUC__ >= 8) 64 #pragma GCC diagnostic push 65 #pragma GCC diagnostic ignored "-Wclass-memaccess" 66 #endif 67 68 memset(object, 0, sizeof(T)); 69 70 #if defined(__GNUC__) && (__GNUC__ >= 8) 71 #pragma GCC diagnostic pop 72 #endif 73 } 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 } 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 nullptr; // 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 169 #endif // sw_LRUCache_hpp 170