glampert/simple_lru_cache.cpp

## simple_lru_cache.cpp

// ----------------------------------------------------------------------------
// 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();
}

	// ----------------------------------------------------------------------------
	// 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();
	}