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 namespace sw 21 { 22 template<class Key, class Data> 23 class LRUCache 24 { 25 public: 26 LRUCache(int n); 27 28 ~LRUCache(); 29 30 Data *query(const Key &key) const; 31 Data *add(const Key &key, Data *data); 32 getSize()33 int getSize() {return size;} getKey(int i)34 Key &getKey(int i) {return key[i];} 35 36 private: 37 int size; 38 int mask; 39 int top; 40 int fill; 41 42 Key *key; 43 Key **ref; 44 Data **data; 45 }; 46 } 47 48 namespace sw 49 { 50 template<class Key, class Data> LRUCache(int n)51 LRUCache<Key, Data>::LRUCache(int n) 52 { 53 size = ceilPow2(n); 54 mask = size - 1; 55 top = 0; 56 fill = 0; 57 58 key = new Key[size]; 59 ref = new Key*[size]; 60 data = new Data*[size]; 61 62 for(int i = 0; i < size; i++) 63 { 64 data[i] = nullptr; 65 66 ref[i] = &key[i]; 67 } 68 } 69 70 template<class Key, class Data> ~LRUCache()71 LRUCache<Key, Data>::~LRUCache() 72 { 73 delete[] key; 74 key = nullptr; 75 76 delete[] ref; 77 ref = nullptr; 78 79 for(int i = 0; i < size; i++) 80 { 81 if(data[i]) 82 { 83 data[i]->unbind(); 84 data[i] = nullptr; 85 } 86 } 87 88 delete[] data; 89 data = nullptr; 90 } 91 92 template<class Key, class Data> query(const Key & key) const93 Data *LRUCache<Key, Data>::query(const Key &key) const 94 { 95 for(int i = top; i > top - fill; i--) 96 { 97 int j = i & mask; 98 99 if(key == *ref[j]) 100 { 101 Data *hit = data[j]; 102 103 if(i != top) 104 { 105 // Move one up 106 int k = (j + 1) & mask; 107 108 Data *swapD = data[k]; 109 data[k] = data[j]; 110 data[j] = swapD; 111 112 Key *swapK = ref[k]; 113 ref[k] = ref[j]; 114 ref[j] = swapK; 115 } 116 117 return hit; 118 } 119 } 120 121 return nullptr; // Not found 122 } 123 124 template<class Key, class Data> add(const Key & key,Data * data)125 Data *LRUCache<Key, Data>::add(const Key &key, Data *data) 126 { 127 top = (top + 1) & mask; 128 fill = fill + 1 < size ? fill + 1 : size; 129 130 *ref[top] = key; 131 132 data->bind(); 133 134 if(this->data[top]) 135 { 136 this->data[top]->unbind(); 137 } 138 139 this->data[top] = data; 140 141 return data; 142 } 143 } 144 145 #endif // sw_LRUCache_hpp 146