src/Renderer/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 "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
  33                 int getSize() {return size;}
  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>
  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] = 0;
  65
  66                         ref[i] = &key[i];
  67                 }
  68         }
  69
  70         template<class Key, class Data>
  71         LRUCache<Key, Data>::~LRUCache()
  72         {
  73                 delete[] key;
  74                 key = 0;
  75
  76                 delete[] ref;
  77                 ref = 0;
  78
  79                 for(int i = 0; i < size; i++)
  80                 {
  81                         if(data[i])
  82                         {
  83                                 data[i]->unbind();
  84                                 data[i] = 0;
  85                         }
  86                 }
  87
  88                 delete[] data;
  89                 data = 0;
  90         }
  91
  92         template<class Key, class Data>
  93         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 0;   // Not found
 122         }
 123
 124         template<class Key, class 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