src/Device/LRUCache.hpp

   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
  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 // An LRU cache which can take a 'snapshot' of its current state. This is useful
  51 // for allowing concurrent read access without requiring a mutex to be locked.
  52 template<class Key, class Data, class Hasher = std::hash<Key>>
  53 class LRUSnapshotCache : public LRUCache<Key, Data>
  54 {
  55         using LRUBase = LRUCache<Key, Data>;
  56
  57 public:
  58         LRUSnapshotCache(int n)
  59             : LRUBase(n)
  60         {}
  61         ~LRUSnapshotCache() { clearSnapshot(); }
  62
  63         Data add(const Key &key, const Data &data) override
  64         {
  65                 snapshotNeedsUpdate = true;
  66                 return LRUBase::add(key, data);
  67         }
  68
  69         void updateSnapshot();
  70         const Data &querySnapshot(const Key &key) const;
  71
  72 private:
  73         void clearSnapshot();
  74         bool snapshotNeedsUpdate = false;
  75         std::unordered_map<Key, Data, Hasher> snapshot;
  76 };
  77
  78 }  // namespace sw
  79
  80 namespace sw {
  81
  82 template<class Key, class Data>
  83 LRUCache<Key, Data>::LRUCache(int n)
  84 {
  85         size = ceilPow2(n);
  86         mask = size - 1;
  87         top = 0;
  88         fill = 0;
  89
  90         key = new Key[size];
  91         ref = new Key *[size];
  92         data = new Data[size];
  93
  94         for(int i = 0; i < size; i++)
  95         {
  96                 ref[i] = &key[i];
  97         }
  98 }
  99
 100 template<class Key, class Data>
 101 LRUCache<Key, Data>::~LRUCache()
 102 {
 103         delete[] key;
 104         key = nullptr;
 105
 106         delete[] ref;
 107         ref = nullptr;
 108
 109         delete[] data;
 110         data = nullptr;
 111 }
 112
 113 template<class Key, class Data>
 114 Data LRUCache<Key, Data>::query(const Key &key) const
 115 {
 116         for(int i = top; i > top - fill; i--)
 117         {
 118                 int j = i & mask;
 119
 120                 if(key == *ref[j])
 121                 {
 122                         Data hit = data[j];
 123
 124                         if(i != top)
 125                         {
 126                                 // Move one up
 127                                 int k = (j + 1) & mask;
 128
 129                                 Data swapD = data[k];
 130                                 data[k] = data[j];
 131                                 data[j] = swapD;
 132
 133                                 Key *swapK = ref[k];
 134                                 ref[k] = ref[j];
 135                                 ref[j] = swapK;
 136                         }
 137
 138                         return hit;
 139                 }
 140         }
 141
 142         return {};  // Not found
 143 }
 144
 145 template<class Key, class Data>
 146 Data LRUCache<Key, Data>::add(const Key &key, const Data &data)
 147 {
 148         top = (top + 1) & mask;
 149         fill = fill + 1 < size ? fill + 1 : size;
 150
 151         *ref[top] = key;
 152         this->data[top] = data;
 153
 154         return data;
 155 }
 156
 157 template<class Key, class Data, class Hasher>
 158 void LRUSnapshotCache<Key, Data, Hasher>::clearSnapshot()
 159 {
 160         snapshot.clear();
 161 }
 162
 163 template<class Key, class Data, class Hasher>
 164 void LRUSnapshotCache<Key, Data, Hasher>::updateSnapshot()
 165 {
 166         if(snapshotNeedsUpdate)
 167         {
 168                 clearSnapshot();
 169
 170                 for(int i = 0; i < LRUBase::size; i++)
 171                 {
 172                         if(LRUBase::data[i])
 173                         {
 174                                 snapshot[*LRUBase::ref[i]] = LRUBase::data[i];
 175                         }
 176                 }
 177
 178                 snapshotNeedsUpdate = false;
 179         }
 180 }
 181
 182 template<class Key, class Data, class Hasher>
 183 const Data &LRUSnapshotCache<Key, Data, Hasher>::querySnapshot(const Key &key) const
 184 {
 185         auto it = snapshot.find(key);
 186         static Data null = {};
 187         return (it != snapshot.end()) ? it->second : null;
 188 }
 189
 190 }  // namespace sw
 191
 192 #endif  // sw_LRUCache_hpp