src/Renderer/LRUCache.hpp

   1 // SwiftShader Software Renderer\r
   2 //\r
   3 // Copyright(c) 2005-2011 TransGaming Inc.\r
   4 //\r
   5 // All rights reserved. No part of this software may be copied, distributed, transmitted,\r
   6 // transcribed, stored in a retrieval system, translated into any human or computer\r
   7 // language by any means, or disclosed to third parties without the explicit written\r
   8 // agreement of TransGaming Inc. Without such an agreement, no rights or licenses, express\r
   9 // or implied, including but not limited to any patent rights, are granted to you.\r
  10 //\r
  11 \r
  12 #ifndef sw_LRUCache_hpp\r
  13 #define sw_LRUCache_hpp\r
  14 \r
  15 #include "Common/Math.hpp"\r
  16 \r
  17 namespace sw\r
  18 {\r
  19         template<class Key, class Data>\r
  20         class LRUCache\r
  21         {\r
  22         public:\r
  23                 LRUCache(int n);\r
  24 \r
  25                 ~LRUCache();\r
  26 \r
  27                 Data *query(const Key &key) const;\r
  28                 Data *add(const Key &key, Data *data);\r
  29                 \r
  30                 int getSize() {return size;}\r
  31                 Key &getKey(int i) {return key[i];}\r
  32 \r
  33         private:\r
  34                 int size;\r
  35                 int mask;\r
  36                 int top;\r
  37                 int fill;\r
  38 \r
  39                 Key *key;\r
  40                 Key **ref;\r
  41                 Data **data;\r
  42         };\r
  43 }\r
  44 \r
  45 namespace sw\r
  46 {\r
  47         template<class Key, class Data>\r
  48         LRUCache<Key, Data>::LRUCache(int n)\r
  49         {\r
  50                 size = ceilPow2(n);\r
  51                 mask = size - 1;\r
  52                 top = 0;\r
  53                 fill = 0;\r
  54 \r
  55                 key = new Key[size];\r
  56                 ref = new Key*[size];\r
  57                 data = new Data*[size];\r
  58                 \r
  59                 for(int i = 0; i < size; i++)\r
  60                 {\r
  61                         data[i] = 0;\r
  62 \r
  63                         ref[i] = &key[i];\r
  64                 }\r
  65         }\r
  66 \r
  67         template<class Key, class Data>\r
  68         LRUCache<Key, Data>::~LRUCache()\r
  69         {\r
  70                 delete[] key;\r
  71                 key = 0;\r
  72 \r
  73                 delete[] ref;\r
  74                 ref = 0;\r
  75 \r
  76                 for(int i = 0; i < size; i++)\r
  77                 {\r
  78                         if(data[i])\r
  79                         {\r
  80                                 data[i]->unbind();\r
  81                                 data[i] = 0;\r
  82                         }\r
  83                 }\r
  84 \r
  85                 delete[] data;\r
  86                 data = 0;\r
  87         }\r
  88 \r
  89         template<class Key, class Data>\r
  90         Data *LRUCache<Key, Data>::query(const Key &key) const\r
  91         {\r
  92                 for(int i = top; i > top - fill; i--)\r
  93                 {\r
  94                         int j = i & mask;\r
  95 \r
  96                         if(key == *ref[j])\r
  97                         {\r
  98                                 Data *hit = data[j];\r
  99 \r
 100                                 if(i != top)\r
 101                                 {\r
 102                                         // Move one up\r
 103                                         int k = (j + 1) & mask;\r
 104 \r
 105                                         Data *swapD = data[k];\r
 106                                         data[k] = data[j];\r
 107                                         data[j] = swapD;\r
 108 \r
 109                                         Key *swapK = ref[k];\r
 110                                         ref[k] = ref[j];\r
 111                                         ref[j] = swapK;\r
 112                                 }\r
 113 \r
 114                                 return hit;\r
 115                         }\r
 116                 }\r
 117 \r
 118                 return 0;   // Not found\r
 119         }\r
 120         \r
 121         template<class Key, class Data>\r
 122         Data *LRUCache<Key, Data>::add(const Key &key, Data *data)\r
 123         {\r
 124                 top = (top + 1) & mask;\r
 125                 fill = fill + 1 < size ? fill + 1 : size;\r
 126 \r
 127                 *ref[top] = key;\r
 128         \r
 129                 data->bind();\r
 130                 \r
 131                 if(this->data[top])\r
 132                 {\r
 133                         this->data[top]->unbind();\r
 134                 }\r
 135 \r
 136                 this->data[top] = data;\r
 137 \r
 138                 return data;\r
 139         }\r
 140 }\r
 141 \r
 142 #endif   // sw_LRUCache_hpp\r