text: // 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
  