src/System/LRUCache.hpp

// Copyright 2020 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/Debug.hpp"

#include <cstddef>
#include <cstdint>
#include <functional>
#include <unordered_set>
#include <vector>

namespace sw {

// LRUCache is a least recently used cache of a fixed capacity.
template<typename KEY, typename DATA, typename HASH = std::hash<KEY> >
class LRUCache
{
	struct Entry;

public:
	using Key = KEY;
	using Data = DATA;
	using Hash = HASH;

	// view is a const accessor of a single cache entry.
	class view
	{
	public:
		inline view(Entry *);

		inline const Key &key() const;
		inline const Data &data() const;

	private:
		Entry *entry;
	};

	class iterator
	{
	public:
		inline iterator(Entry *);
		inline view operator*() const;
		inline iterator &operator++();
		inline bool operator==(const iterator &) const;
		inline bool operator!=(const iterator &) const;

	private:
		Entry *entry;
	};

	// Construct a LRU cache with the given maximum number of entries.
	inline LRUCache(size_t capacity);
	inline ~LRUCache() = default;

	// lookup() looks up the cache entry with the given key.
	// If the entry is found, this is moved to the most-recent position in the
	// cache, and its data is returned.
	// If the entry is not found, then a default initialized Data is returned.
	inline Data lookup(const Key &key);

	// add() adds the data to the cache using the given key, placed at the
	// most-recent position in the cache.
	// If an existing entry exists in the cache with the given key, then this is
	// replaced with data.
	// If no existing entry exists in the cache, and the cache is already full
	// then the least recently used entry is evicted before adding the new
	// entry.
	inline void add(const Key &key, const Data &data);

	// clear() clears the cache of all elements.
	inline void clear();

	// Range based iterators.
	inline iterator begin() const;
	inline iterator end() const;

private:
	LRUCache(const LRUCache &) = delete;
	LRUCache(LRUCache &&) = delete;
	LRUCache &operator=(const LRUCache &) = delete;
	LRUCache &operator=(LRUCache &&) = delete;

	// Keyed holds a key. See find() for more information.
	struct Keyed
	{
		Key key = {};
	};

	// Cache entry structure.
	// Holds the unique copy of the key and data, along with pointers for
	// maintaining the linked list.
	struct Entry : Keyed
	{
		Data data = {};
		Entry *next = nullptr;
		Entry *prev = nullptr;
	};

	// KeyedComparator is a custom hasher and equality helper for Keyed.
	struct KeyedComparator
	{
		// Hash function.
		inline uint64_t operator()(const Keyed *k) const;

		// Equality function.
		inline uint64_t operator()(const Keyed *a, const Keyed *b) const;
	};

	// find() returns the Entry* for the given key, or nullptr.
	// find() performs this by casting the Key pointer to a Keyed pointer for
	// searching the std::unordered_set.
	//
	// This is to avoid having a duplicate Key held by both an
	// unordered_map<Key, Entry*> and the Entry itself, as the Key type may be
	// large.
	//
	// While we could use an unordered_set<Entry*>, this then requires the
	// construction of a temporary Entry to perform the call to
	// unordered_set<Entry*>::find(). This is undesirable as the Data type might
	// be large or have an expensive constructor.
	//
	// C++20 gains a new templated overload for unordered_set<Entry*>::find()
	// which would allow us to use unordered_set<Entry*>::find(Key*).
	// Until we can use C++20, keep this casting nastiness hidden away in this
	// one function.
	inline Entry *find(const Key &key);

	// unlinks the entry from the list it is linked in.
	inline void unlink(Entry *);

	// links the entry to the head of the LRU.
	inline void link(Entry *);

	// storage holds the allocations of all the entries.
	// This vector must not change size for the lifetime of the cache.
	std::vector<Entry> storage;

	// set is an unordered set of Keyed*, using the KeyedComparator for hash and
	// equality testing.
	std::unordered_set<const Keyed *, KeyedComparator, KeyedComparator> set;

	Entry *free = nullptr;  // Singly-linked (prev is nullptr) list of free entries.
	Entry *head = nullptr;  // Pointer to the most recently used entry in the LRU.
	Entry *tail = nullptr;  // Pointer to the least recently used entry in the LRU.
};

////////////////////////////////////////////////////////////////////////////////
// LRUCache<>::view
////////////////////////////////////////////////////////////////////////////////
template<typename KEY, typename DATA, typename HASH>
LRUCache<KEY, DATA, HASH>::view::view(Entry *entry)
    : entry(entry)
{}

template<typename KEY, typename DATA, typename HASH>
const KEY &LRUCache<KEY, DATA, HASH>::view::key() const
{
	return entry->key;
}

template<typename KEY, typename DATA, typename HASH>
const DATA &LRUCache<KEY, DATA, HASH>::view::data() const
{
	return entry->data;
}

////////////////////////////////////////////////////////////////////////////////
// LRUCache<>::iterator
////////////////////////////////////////////////////////////////////////////////
template<typename KEY, typename DATA, typename HASH>
LRUCache<KEY, DATA, HASH>::iterator::iterator(Entry *entry)
    : entry(entry)
{}

template<typename KEY, typename DATA, typename HASH>
typename LRUCache<KEY, DATA, HASH>::view LRUCache<KEY, DATA, HASH>::iterator::operator*() const
{
	return view{ entry };
}

template<typename KEY, typename DATA, typename HASH>
typename LRUCache<KEY, DATA, HASH>::iterator &LRUCache<KEY, DATA, HASH>::iterator::operator++()
{
	entry = entry->next;
	return *this;
}

template<typename KEY, typename DATA, typename HASH>
bool LRUCache<KEY, DATA, HASH>::iterator::operator==(const iterator &rhs) const
{
	return entry == rhs.entry;
}

template<typename KEY, typename DATA, typename HASH>
bool LRUCache<KEY, DATA, HASH>::iterator::operator!=(const iterator &rhs) const
{
	return entry != rhs.entry;
}

////////////////////////////////////////////////////////////////////////////////
// LRUCache<>
////////////////////////////////////////////////////////////////////////////////
template<typename KEY, typename DATA, typename HASH>
LRUCache<KEY, DATA, HASH>::LRUCache(size_t capacity)
    : storage(capacity)
{
	for(size_t i = 0; i < capacity; i++)
	{
		Entry *entry = &storage[i];
		entry->next = free;  // No need for back link here.
		free = entry;
	}
}

template<typename KEY, typename DATA, typename HASH>
DATA LRUCache<KEY, DATA, HASH>::lookup(const Key &key)
{
	if(Entry *entry = find(key))
	{
		unlink(entry);
		link(entry);
		return entry->data;
	}
	return {};
}

template<typename KEY, typename DATA, typename HASH>
void LRUCache<KEY, DATA, HASH>::add(const Key &key, const Data &data)
{
	if(Entry *entry = find(key))
	{
		// Move entry to front.
		unlink(entry);
		link(entry);
		entry->data = data;
		return;
	}

	Entry *entry = free;
	if(entry)
	{
		// Unlink from free.
		free = entry->next;
		entry->next = nullptr;
	}
	else
	{
		// Unlink least recently used.
		entry = tail;
		unlink(entry);
		set.erase(entry);
	}

	// link as most recently used.
	link(entry);
	if(tail == nullptr)
	{
		tail = entry;
	}

	entry->key = key;
	entry->data = data;
	set.emplace(entry);
}

template<typename KEY, typename DATA, typename HASH>
void LRUCache<KEY, DATA, HASH>::clear()
{
	while(Entry *entry = head)
	{
		unlink(entry);
		entry->next = free;  // No need for back link here.
		free = entry;
	}
	set.clear();
}

template<typename KEY, typename DATA, typename HASH>
typename LRUCache<KEY, DATA, HASH>::iterator LRUCache<KEY, DATA, HASH>::begin() const
{
	return { head };
}

template<typename KEY, typename DATA, typename HASH>
typename LRUCache<KEY, DATA, HASH>::iterator LRUCache<KEY, DATA, HASH>::end() const
{
	return { nullptr };
}

template<typename KEY, typename DATA, typename HASH>
void LRUCache<KEY, DATA, HASH>::unlink(Entry *entry)
{
	if(head == entry) { head = entry->next; }
	if(tail == entry) { tail = entry->prev; }
	if(entry->prev) { entry->prev->next = entry->next; }
	if(entry->next) { entry->next->prev = entry->prev; }
	entry->prev = nullptr;
	entry->next = nullptr;
}

template<typename KEY, typename DATA, typename HASH>
void LRUCache<KEY, DATA, HASH>::link(Entry *entry)
{
	ASSERT_MSG(entry->next == nullptr, "link() called on entry already linked");
	ASSERT_MSG(entry->prev == nullptr, "link() called on entry already linked");
	if(head)
	{
		entry->next = head;
		head->prev = entry;
	}
	head = entry;
	if(!tail) { tail = entry; }
}

template<typename KEY, typename DATA, typename HASH>
typename LRUCache<KEY, DATA, HASH>::Entry *LRUCache<KEY, DATA, HASH>::find(const Key &key)
{
	auto asKeyed = reinterpret_cast<const Keyed *>(&key);
	auto it = set.find(asKeyed);
	if(it == set.end())
	{
		return nullptr;
	}
	return const_cast<Entry *>(static_cast<const Entry *>(*it));
}

////////////////////////////////////////////////////////////////////////////////
// LRUCache<>::KeyedComparator
////////////////////////////////////////////////////////////////////////////////
template<typename KEY, typename DATA, typename HASH>
uint64_t LRUCache<KEY, DATA, HASH>::KeyedComparator::operator()(const Keyed *k) const
{
	return Hash()(k->key);
}

template<typename KEY, typename DATA, typename HASH>
uint64_t LRUCache<KEY, DATA, HASH>::KeyedComparator::operator()(const Keyed *a, const Keyed *b) const
{
	return a->key == b->key;
}

}  // namespace sw

#endif  // sw_LRUCache_hpp