An LRU cache template

Question

I recently implemented a cache for a pet project of mine. The main objectives behind this implementation were:

1. Support move-only types for values: C++11 is here, and some of the objects that will be used with this template are movable but not copyable. Keys are fine with a copyable requirement because move-only keys make little sense in my opinion.

2. Fast key lookup.

3. Lazy evaluation: if the creation of the cached value type is an expensive operation, unnecessary creation is undesirable. Instead of creating the value directly and passing it along, I can simply pass a lambda or an existing factory function or function object, like this:

   lru_cache<int,int> c;
   c.get_or_add(17, [&blah]{ return long_calculation(blah); });
   

4. Simple syntax when lazy evaluation is not needed: sometimes if an instance is available, or its creation is "free", using a lambda can be cumbersome. I'd rather just pass it directly:

   c.get_or_add(17, 42); // int literals are "free", no need for laziness
   

Points 1 and 2 are achieved with a hash map of nodes in a linked list. The hash map gives fast lookup, and the linked list tracks the order of use. I tried to use Boost.Intrusive for the internal linked list, but its hooks don't have move semantics, so I had to roll my own :)

Points 3 and 4 are achieved through the meta::lazy<T>::eval function. It alone decides whether the argument is a function that is to be called or just a value to be returned.

Here is the code:

// for wheels::meta::lazy
#include "../meta/traits.hpp"

#include <functional>
#include <cstddef>
#include <type_traits>
#include <unordered_map>
#include <utility>

namespace wheels {
    //! A cache that evicts the least recently used item.
    template <typename Key,
              typename T,
              typename Hash = std::hash<Key>,
              typename Pred = std::equal_to<Key>>
    class lru_cache {
    public:
        //! Initializes an LRU cache with the given capacity.
        lru_cache(std::size_t capacity) : front(), back(), map(), capacity(capacity) {}

        //! Fetches an item from the cache, or adds one if it doesn't exist.
        /*! The value parameter can be passed directly, or lazily (i.e. as a factory function). */
        template <typename Lazy>
        T& get_or_add(Key const& key, Lazy value) {
            auto it = map.find(key);
            if(it != map.end()) {
                touch(it);
                return it->second.value;
            } else {
                return add(key, meta::lazy<T>::eval(value));
            }
        }

        //! Flushes the cache evicting all entries.
        void flush() {
            front = back = nullptr;
            map.clear();
        }

    private:
        //! Moves a recently used entry to the front.
        template <typename Iterator>
        void touch(Iterator it) noexcept {
            auto& entry = it->second;
            unplug(entry);
            push_front(entry);
        }
        //! Adds a new entry.
        template <typename Tf>
        T& add(Key const& key, Tf&& value) {
            cache_entry entry(key, std::forward<Tf>(value));
            auto item = std::make_pair(key, std::move(entry));
            auto it = map.insert(std::move(item)).first;
            push_front(it->second);
            if(map.size() > capacity) evict();
            return it->second.value;
        }
        //! Evicts the least recently used entry.
        void evict() {
            map.erase(back->key);
            unplug(*back);
        }

        //! An entry in the cache. Maintains a linked list to track the LRU.
        struct cache_entry {
            template <typename Tf>
            cache_entry(Key const& key, Tf&& value)
            : key(key), value(std::forward<Tf>(value)), next(), prev() {}

            cache_entry(cache_entry&& that)
            : key(std::move(that.key)), value(std::move(that.value)) {}

            Key key;
            T value;
            cache_entry* next;
            cache_entry* prev;
        };

        //! Unplugs an entry from the linked list.
        void unplug(cache_entry& entry) {
            if(entry.prev) {
                entry.prev->next = entry.next;
            } else {
                front = entry.next;
            }
            if(entry.next) {
                entry.next->prev = entry.prev;
            } else {
                back = entry.prev;
            }
        }
        //! Pushes an entry to the front of the linked list.
        void push_front(cache_entry& entry) {
            entry.prev = nullptr;
            entry.next = front;
            if(front) {
                front->prev = &entry;
            } else {
                back = &entry;
            }
            front = &entry;
        }

        cache_entry* front; //! Front of the internal linked list.
        cache_entry* back; //! Back of the internal linked list.

        //! Hash table for quick lookup by key.
        std::unordered_map<Key,cache_entry, Hash> map;
        //! Maximum capacity.
        std::size_t capacity;
    };
}

I'm particularly concerned about exception safety (which I've been a bit lax about, and it's something I'm still assimilating), but any criticism is welcome.

Answer 1

I think you can make the maintenance of the list a lot easier if the list is circular.
With a circular list there are no test for NULL when inserting or removing an element (you just need a fake head node so that an empty list points back at itself).

Also you are not using encapsulation enough, this makes your methods a little more complex than they need to be. For example the cache_entry should be able to add and move itself around in the list.

Here is a simplified example of what I mean to try and show what I mean. Unfortunately there is no way I can implement the full template thing you have (way beyond me skill level).

The only worry I have for this technique is exception safety. There are no problems with this simplified version but I can quite convince myself this is true for your more complex cache. I would need to write the unit tests to make myself convinced.

#include <map>

class simple_cache
{
        // The node(s) used to maintain the circular list.
        struct Link
        {
            // Links are created into a list.
            Link(Link* n, Link* p)
                : next(n)
                , prev(p)
            {}

            // Remove a `this` from the list.
            void unlink()
            {
                // Unlink this from the chain
                prev->next      = next;
                next->prev      = prev;
            }

            // Move a link to `head` of the list.
            // But we do need to pass the head of the list.
            void move(Link& head)
            {
                unlink();

                // Put this node back into the chain at the head node
                this->next      = &head;
                this->prev      = head.prev;

                head.prev->next = this;
                head.prev       = this;
            }

            Link*    next;
            Link*    prev;
        };
        // A cache_entry is a link
        // So we can add it to the circular list.
        struct cache_entry: public Link
        {
            // Create a link AND add it to the head of the list.
            cache_entry(int key, int value, Link& head)
                : Link(&head, head.prev)
                , key(key)
                , value(value)
            {
                head.prev->next = this;
                head.prev       = this;
            }

            int         key;
            int         value;
        };
        typedef std::map<int, cache_entry>      Data;
        Link    head;   // Circular linked list
                        // If there are zero elements it points at itself
        Data    data;
    public:
        simple_cache() 
          : head(&head, &head)
        {}

        void add(int key, int value)
        {
            Data::iterator  find    = data.find(key);
            if (find != data.end())
            {
                find->second.value  = value;
                find->second.move(head);
            }
            else
            {
                data.insert(std::make_pair(key,cache_entry(key, value,head)));
                if (data.size() > 5)
                {
                    evict();
                }
            }
        }
    private:
        void evict()
        {
            /* This function will explode if called when the list is empty
             * i.e. if the only link in the chain is the fake node.
             * Thus it is important to make sure that you only call this
             * when their is a real node in the list.
             *
             * Maybe a check and exception may be worth it (though if done 
             * correctly it should be possible to make sure it does not happen)
             */


            // Get and remove the last element from the list
            Link*   lastElement = head.prev;
            lastElement->unlink();

            // Now remove it from the map.
            data.erase(static_cast<cache_entry*>(lastElement)->key);
        }

};