Simple LRU cache backed by a hash table and a fixed-size circular queue.
// ---------------------------------------------------------------------------- | |
// Least Recently Used cache backed by a hash table | |
// (unprdered_map) and a fixed-size circular queue. | |
// | |
// License: | |
// Public Domain. | |
// Feel free to copy, distribute, and modify this file as you see fit. | |
// ---------------------------------------------------------------------------- | |
#include <cassert> | |
#include <cstdio> | |
#include <cstdlib> | |
#include <cstring> | |
#include <algorithm> | |
#include <utility> | |
#include <array> | |
#include <unordered_map> | |
// ---------------------------------------------------------------------------- | |
// Simple fixed-size circular queue. Once the capacity is full it starts | |
// popping the front of the queue to make room for new items pushed at the end. | |
template | |
< | |
typename T, | |
int Capacity, | |
bool ResetItems = true | |
> | |
class CircularQueue final | |
{ | |
private: | |
int m_head; | |
int m_tail; | |
int m_count; | |
std::array<T, Capacity> m_items; | |
public: | |
CircularQueue() | |
{ | |
clear(); | |
} | |
void clear() | |
{ | |
m_head = -1; | |
m_tail = -1; | |
m_count = 0; | |
if (ResetItems) | |
{ | |
m_items.fill(T{}); | |
} | |
} | |
void pushBack(const T & item) | |
{ | |
if (m_head == (Capacity - 1)) | |
{ | |
m_head = -1; | |
} | |
else if (m_count < Capacity) | |
{ | |
++m_count; | |
} | |
++m_head; | |
if (m_head == m_tail || m_tail == -1) | |
{ | |
m_tail = (m_tail + 1) % Capacity; | |
} | |
m_items[m_head] = item; | |
} | |
void popFront() | |
{ | |
assert(!isEmpty()); | |
if (ResetItems) | |
{ | |
m_items[m_tail] = T{}; | |
} | |
if (--m_count == 0) | |
{ | |
m_head = m_tail = -1; | |
} | |
else | |
{ | |
assert(m_tail != m_head); | |
m_tail = (m_tail + 1) % Capacity; | |
} | |
} | |
int size() const { return m_count; } | |
int capacity() const { return Capacity; } | |
int frontIndex() const { return m_tail; } | |
int backIndex() const { return m_head; } | |
bool isEmpty() const { return (m_count == 0); } | |
bool isFull() const { return (m_count == Capacity); } | |
T & front() { assert(!isEmpty()); return m_items[m_tail]; } | |
const T & front() const { assert(!isEmpty()); return m_items[m_tail]; } | |
T & back() { assert(!isEmpty()); return m_items[m_head]; } | |
const T & back() const { assert(!isEmpty()); return m_items[m_head]; } | |
T & operator[](std::size_t index) { return m_items[index]; } | |
const T & operator[](std::size_t index) const { return m_items[index]; } | |
}; | |
// ---------------------------------------------------------------------------- | |
// Simple fixed-size cache that keeps track of the | |
// Most Recently Used (MRU) and Least Recently Used (LRU) | |
// items in it. Once the cache is full, the LRU item | |
// is removed to make room for the new insertion, which | |
// becomes the MRU item. The cache uses a hash-table and | |
// a circular queue under the hood. | |
template | |
< | |
typename K, // Key type | |
typename V, // Value type | |
int CacheSize, // Size of the cache in items | |
int HTPrimeSize // CacheSize rounded up to a prime, for the hash-table | |
> | |
class LruCache final | |
{ | |
private: | |
std::unordered_map<K, V> m_cache; // Size capped to CacheSize | |
CircularQueue<K, CacheSize> m_lruQ; // back=MRU, front=LRU | |
public: | |
using Pair = std::pair<K, V>; | |
LruCache() | |
: m_cache{ HTPrimeSize } | |
{ } | |
V * access(const K & key) | |
{ | |
auto iter = m_cache.find(key); | |
if (iter == m_cache.end()) | |
{ | |
return nullptr; | |
} | |
m_lruQ.pushBack(iter->first); | |
return &iter->second; | |
} | |
bool insert(const K & key, const V & value, Pair * outOptEvictedEntry = nullptr) | |
{ | |
assert(access(key) == nullptr); // No duplicate keys | |
bool entryEvicted = false; | |
if (m_cache.size() == CacheSize) | |
{ | |
// Make room for a new item by removing the oldest cached. | |
// Need to call in a loop because the LRU queue might have | |
// multiple references to the same item, which might have | |
// already been removed from the cache by a previous insert. | |
for (;;) | |
{ | |
auto iter = m_cache.find(m_lruQ.front()); | |
m_lruQ.popFront(); | |
if (iter != m_cache.end()) | |
{ | |
if (outOptEvictedEntry) | |
{ | |
*outOptEvictedEntry = *iter; | |
} | |
m_cache.erase(iter); | |
entryEvicted = true; | |
break; | |
} | |
} | |
assert(m_cache.size() == CacheSize - 1); | |
} | |
m_cache.insert({ key, value }); | |
m_lruQ.pushBack(key); | |
return entryEvicted; | |
} | |
void clear() | |
{ | |
m_cache.clear(); | |
m_lruQ.clear(); | |
} | |
int size() const | |
{ | |
return static_cast<int>(m_cache.size()); | |
} | |
bool isEmpty() const | |
{ | |
return m_cache.empty(); | |
} | |
Pair mru() const | |
{ | |
assert(!isEmpty()); | |
return *m_cache.find(m_lruQ.back()); | |
} | |
Pair lru() const | |
{ | |
assert(!isEmpty()); | |
return *m_cache.find(m_lruQ.front()); | |
} | |
int copyContents(std::array<Pair, CacheSize> & dest) const | |
{ | |
int n = 0; | |
for (const Pair & p : m_cache) | |
{ | |
dest[n++] = p; | |
} | |
return n; | |
} | |
}; | |
// ---------------------------------------------------------------------------- | |
template<typename QueueType> | |
void TestCircularQueue(QueueType & Q) | |
{ | |
Q.pushBack(42); | |
assert(Q.front() == 42); | |
assert(Q.back() == 42); | |
assert(Q.size() == 1); | |
Q.popFront(); assert(Q.isEmpty()); | |
Q.pushBack(1); // front | |
Q.pushBack(2); assert(Q.front() == 1); | |
Q.pushBack(3); assert(Q.front() == 1); | |
Q.pushBack(4); assert(Q.front() == 1); | |
Q.pushBack(5); assert(Q.front() == 1); | |
Q.pushBack(6); assert(Q.front() == 1); | |
Q.pushBack(7); assert(Q.front() == 1); | |
Q.pushBack(8); // back | |
assert(Q.isFull()); | |
assert(Q.size() == Q.capacity()); | |
assert(Q.front() == 2); | |
assert(Q.back() == 8); | |
Q.popFront(); | |
assert(Q.front() == 3); | |
assert(Q.back() == 8); | |
Q.pushBack(9); | |
assert(Q.front() == 3); | |
assert(Q.back() == 9); | |
Q.pushBack(10); | |
Q.pushBack(11); | |
assert(Q.front() == 5); | |
assert(Q.back() == 11); | |
Q.popFront(); | |
Q.popFront(); | |
Q.popFront(); | |
Q.popFront(); | |
Q.pushBack(12); | |
assert(Q.front() == 9); | |
assert(Q.back() == 12); | |
Q.pushBack(13); assert(Q.back() == 13); | |
Q.pushBack(14); assert(Q.back() == 14); | |
Q.pushBack(15); assert(Q.back() == 15); | |
Q.pushBack(16); | |
assert(Q.front() == 10); | |
assert(Q.back() == 16); | |
int expected = 10; | |
while (!Q.isEmpty()) | |
{ | |
assert(Q.front() == expected); | |
Q.popFront(); | |
++expected; | |
} | |
assert(Q.size() == 0); | |
for (int i = 0; i < 1000; ++i) | |
{ | |
Q.pushBack(i); | |
} | |
Q.clear(); | |
} | |
// ---------------------------------------------------------------------------- | |
template<typename CacheType> | |
void TestLruCache(CacheType & C) | |
{ | |
auto strEq = [](const char * a, const char * b) { return std::strcmp(a, b) == 0; }; | |
C.insert(1, "hello"); | |
C.insert(2, " C++ "); | |
C.insert(3, "world"); | |
auto mru = C.mru(); | |
auto lru = C.lru(); | |
assert(mru.first == 3 && strEq(mru.second, "world")); | |
assert(lru.first == 1 && strEq(lru.second, "hello")); | |
C.insert(4, "testing"); | |
C.insert(5, "123...."); | |
mru = C.mru(); | |
lru = C.lru(); | |
assert(mru.first == 5 && strEq(mru.second, "123....")); | |
assert(lru.first == 1 && strEq(lru.second, "hello")); | |
C.insert( 6, "six"); | |
C.insert( 7, "seven"); | |
C.insert( 8, "eight"); | |
C.insert( 9, "nine"); | |
C.insert(10, "ten"); | |
mru = C.mru(); | |
lru = C.lru(); | |
assert(mru.first == 10 && strEq(mru.second, "ten")); | |
assert(lru.first == 3 && strEq(lru.second, "world")); | |
assert(C.access(1) == nullptr); // "hello" -> removed from the LRU | |
assert(C.access(2) == nullptr); // " C++ " -> removed from the LRU | |
auto * a = C.access(3); | |
assert(a != nullptr && strEq(*a, "world")); | |
mru = C.mru(); | |
assert(mru.first == 3 && strEq(mru.second, "world")); | |
auto * b = C.access(4); | |
assert(b != nullptr && strEq(*b, "testing")); | |
mru = C.mru(); | |
assert(mru.first == 4 && strEq(mru.second, "testing")); | |
lru = C.lru(); | |
assert(lru.first == 5 && strEq(lru.second, "123....")); | |
C.clear(); | |
} | |
// ---------------------------------------------------------------------------- | |
void TestCacheHistory() | |
{ | |
struct HistoryItem | |
{ | |
int key; | |
int count; | |
int timestamp; | |
}; | |
using History = LruCache<int, HistoryItem, 50, 101>; | |
History hist; | |
std::srand(1337); | |
for (int i = 0; i < 1000; ++i) | |
{ | |
const int key = std::rand() % 60; | |
auto * item = hist.access(key); | |
if (item != nullptr) | |
{ | |
item->count++; | |
} | |
else | |
{ | |
History::Pair dropped; | |
const bool itemWasDropped = hist.insert(key, { key, 0, i }, &dropped); | |
if (itemWasDropped) | |
{ | |
std::printf("Cache dropped item %-2i, count=%-2i, timestamp=%i\n", | |
dropped.first, dropped.second.count, dropped.second.timestamp); | |
} | |
} | |
} | |
std::array<History::Pair, 50> contents; | |
const int count = hist.copyContents(contents); | |
std::sort(std::begin(contents), std::begin(contents) + count, | |
[](const History::Pair & a, const History::Pair & b) | |
{ | |
return (a.second.count > b.second.count); | |
}); | |
std::printf("Sorted history:\n"); | |
for (int i = 0; i < count; ++i) | |
{ | |
std::printf("[%-2i]: key=%-2i, count=%-2i, timestamp=%i\n", | |
i, contents[i].second.key, contents[i].second.count, contents[i].second.timestamp); | |
} | |
std::printf("---------------\n"); | |
} | |
// ---------------------------------------------------------------------------- | |
int main() | |
{ | |
{ | |
CircularQueue<int, 7> Q; | |
TestCircularQueue(Q); | |
TestCircularQueue(Q); | |
TestCircularQueue(Q); | |
} | |
{ | |
LruCache<int, const char *, 8, 11> C; | |
TestLruCache(C); | |
TestLruCache(C); | |
TestLruCache(C); | |
} | |
TestCacheHistory(); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment