blob: 1c24490644119014709e92a992526f0177b5475c [file] [log] [blame] [edit]
// 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 <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