Simple LRU cache backed by a hash table and a fixed-size circular queue.

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