blob: d4d2bdbd0d3efe92faecd950ba321de27e52d990 [file] [log] [blame]
// Copyright 2016 The SwiftShader Authors. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#ifndef sw_LRUCache_hpp
#define sw_LRUCache_hpp
#include "System/Math.hpp"
#include <type_traits>
#include <unordered_map>
namespace sw {
template<class Key, class Data>
class LRUCache
{
public:
LRUCache(int n);
virtual ~LRUCache();
Data query(const Key &key) const;
virtual Data add(const Key &key, const Data &data);
int getSize() { return size; }
Key &getKey(int i) { return key[i]; }
protected:
int size;
int mask;
int top;
int fill;
Key *key;
Key **ref;
Data *data;
};
template<class Key, class Data, class Hasher = std::hash<Key>>
class LRUConstCache : public LRUCache<Key, Data>
{
using LRUBase = LRUCache<Key, Data>;
public:
LRUConstCache(int n)
: LRUBase(n)
{}
~LRUConstCache() { clearConstCache(); }
Data add(const Key &key, const Data &data) override
{
constCacheNeedsUpdate = true;
return LRUBase::add(key, data);
}
void updateConstCache();
const Data &queryConstCache(const Key &key) const;
private:
void clearConstCache();
bool constCacheNeedsUpdate = false;
std::unordered_map<Key, Data, Hasher> constCache;
};
// Traits-like helper class for checking if objects can be compared using memcmp().
// Useful for statically asserting if a cache key can implement operator==() with memcmp().
template<typename T>
struct is_memcmparable
{
// std::is_trivially_copyable is not available in older GCC versions.
#if !defined(__GNUC__) || __GNUC__ > 5
static const bool value = std::is_trivially_copyable<T>::value;
#else
// At least check it doesn't have virtual methods.
static const bool value = !std::is_polymorphic<T>::value;
#endif
};
} // namespace sw
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++)
{
ref[i] = &key[i];
}
}
template<class Key, class Data>
LRUCache<Key, Data>::~LRUCache()
{
delete[] key;
key = nullptr;
delete[] ref;
ref = nullptr;
delete[] data;
data = nullptr;
}
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 {}; // Not found
}
template<class Key, class Data>
Data LRUCache<Key, Data>::add(const Key &key, const Data &data)
{
top = (top + 1) & mask;
fill = fill + 1 < size ? fill + 1 : size;
*ref[top] = key;
this->data[top] = data;
return data;
}
template<class Key, class Data, class Hasher>
void LRUConstCache<Key, Data, Hasher>::clearConstCache()
{
constCache.clear();
}
template<class Key, class Data, class Hasher>
void LRUConstCache<Key, Data, Hasher>::updateConstCache()
{
if(constCacheNeedsUpdate)
{
clearConstCache();
for(int i = 0; i < LRUBase::size; i++)
{
if(LRUBase::data[i])
{
constCache[*LRUBase::ref[i]] = LRUBase::data[i];
}
}
constCacheNeedsUpdate = false;
}
}
template<class Key, class Data, class Hasher>
const Data &LRUConstCache<Key, Data, Hasher>::queryConstCache(const Key &key) const
{
auto it = constCache.find(key);
static Data null = {};
return (it != constCache.end()) ? it->second : null;
}
} // namespace sw
#endif // sw_LRUCache_hpp