Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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