// SwiftShader Software Renderer | |
// | |
// Copyright(c) 2005-2011 TransGaming Inc. | |
// | |
// All rights reserved. No part of this software may be copied, distributed, transmitted, | |
// transcribed, stored in a retrieval system, translated into any human or computer | |
// language by any means, or disclosed to third parties without the explicit written | |
// agreement of TransGaming Inc. Without such an agreement, no rights or licenses, express | |
// or implied, including but not limited to any patent rights, are granted to you. | |
// | |
#ifndef sw_LRUCache_hpp | |
#define sw_LRUCache_hpp | |
#include "Common/Math.hpp" | |
namespace sw | |
{ | |
template<class Key, class Data> | |
class LRUCache | |
{ | |
public: | |
LRUCache(int n); | |
~LRUCache(); | |
Data *query(const Key &key) const; | |
Data *add(const Key &key, Data *data); | |
int getSize() {return size;} | |
Key &getKey(int i) {return key[i];} | |
private: | |
int size; | |
int mask; | |
int top; | |
int fill; | |
Key *key; | |
Key **ref; | |
Data **data; | |
}; | |
} | |
namespace sw | |
{ | |
template<class Key, class Data> | |
LRUCache<Key, Data>::LRUCache(int n) | |
{ | |
size = ceilPow2(n); | |
mask = size - 1; | |
top = 0; | |
fill = 0; | |
key = new Key[size]; | |
ref = new Key*[size]; | |
data = new Data*[size]; | |
for(int i = 0; i < size; i++) | |
{ | |
data[i] = 0; | |
ref[i] = &key[i]; | |
} | |
} | |
template<class Key, class Data> | |
LRUCache<Key, Data>::~LRUCache() | |
{ | |
delete[] key; | |
key = 0; | |
delete[] ref; | |
ref = 0; | |
for(int i = 0; i < size; i++) | |
{ | |
if(data[i]) | |
{ | |
data[i]->unbind(); | |
data[i] = 0; | |
} | |
} | |
delete[] data; | |
data = 0; | |
} | |
template<class Key, class Data> | |
Data *LRUCache<Key, Data>::query(const Key &key) const | |
{ | |
for(int i = top; i > top - fill; i--) | |
{ | |
int j = i & mask; | |
if(key == *ref[j]) | |
{ | |
Data *hit = data[j]; | |
if(i != top) | |
{ | |
// Move one up | |
int k = (j + 1) & mask; | |
Data *swapD = data[k]; | |
data[k] = data[j]; | |
data[j] = swapD; | |
Key *swapK = ref[k]; | |
ref[k] = ref[j]; | |
ref[j] = swapK; | |
} | |
return hit; | |
} | |
} | |
return 0; // Not found | |
} | |
template<class Key, class Data> | |
Data *LRUCache<Key, Data>::add(const Key &key, Data *data) | |
{ | |
top = (top + 1) & mask; | |
fill = fill + 1 < size ? fill + 1 : size; | |
*ref[top] = key; | |
data->bind(); | |
if(this->data[top]) | |
{ | |
this->data[top]->unbind(); | |
} | |
this->data[top] = data; | |
return data; | |
} | |
} | |
#endif // sw_LRUCache_hpp |