2
\$\begingroup\$

I'm working on a simple LRU cache for C++. There's nothing spectacular or unusual about it, but I would like it to be thread safe.

(I'm going to be using this for instructional/benchmarking/entertainment purposes in a blog post, not in production, so mostly I just want to avoid embarrassing myself or causing undue hardship in case a reader copy/pastes it into their own project.)

My design so far:

  • I use boost::bimap as the container.
  • I don't allow the value to be a raw pointer since there's shared ownership between the churning cache and the caller(s). A shared_ptr is more appropriate.
  • I use a cache-aside pattern. I've seen a couple of implementations that use a read-through callback to populate the cache in the event of a miss, but I avoid this approach because I'm performing accesses under a lock. I wouldn't want an expensive callback to block all threads.

I've never used a bimap before and would appreciate feedback about mistakes and missed optimizations. Stylistic input would be welcome, too--I'm a sporadic C++ user (at best) these days and not very up-to-date on idioms/practices.

Finally, since sharing mutable state between threads kills kittens etc., I'm looking for ideas for how to make the compiler complain if the user tries storing a shared_ptr of a non-const type.

That is, this should be fine:

LruCache<int, std::shared_ptr<const std::string> safe_lru(100);

but storing a non-const value in a shared pointer should make the compiler throw a fit:

LruCache<int, std::shared_ptr<std::string> evil_lru(100);

Are there any template metaprogramming wizards out there who can help me enforce this?

#pragma once

#include <boost/bimap.hpp>
#include <boost/bimap/unordered_set_of.hpp>
#include <boost/bimap/list_of.hpp>
#include <boost/optional.hpp>
#include <cassert>
#include <memory>
#include <mutex>
#include <type_traits>

namespace foo {

// Thread-safe LRU cache implementation.
template<
    typename Key, 
    typename Val,
    typename Hash = std::hash<Key>,
    typename Equals = std::equal_to<Key>
   >
class LruCache
{
static_assert(!std::is_pointer<Val>::value, "LruCache of raw pointers not allowed (ownership of values is shared between LruCache and callers). Use a shared_ptr or value semantics instead.");

public:
    using Container = boost::bimaps::bimap<
        boost::bimaps::unordered_set_of<Key, Hash, Equals>,
        boost::bimaps::list_of<Val>
    >;

    using Mutex = std::mutex;
    using Lock = std::lock_guard<Mutex>;

    LruCache(size_t capacity) :
        capacity_(capacity),
        container_(),
        mutex_()
    { 
        assert(cap > 0);
    }

    LruCache(const LruCache&) = delete;

    // Creates/updates the value associated with the given key and
    // makes it the most recently accessed.
    void set(const Key& key, const Val& val)
    {
        Lock l(mutex_);

        auto left_iter = container_.left.find(key);

        if (left_iter == container_.left.end())
        {
            // Adding a new item to the front of the container.
            // If there isn't room, remove an item from the end.
            if (container_.size() == capacity_)
            {
                auto end_iter = container_.right.erase(--container_.right.end());

                // erase() returned an iterator pointing to the element immediately following 
                // the one that was deleted, or end() if no such element exists. Debugging sanity check:
                assert(end_iter == container_.right.end());
            }

            // Add the new item to front of the container.
            container_.right.push_front({ val, key });
        }
        else
        {
            // Item with this key exists. Update with new value and move to front of container.
            left_iter->second = val;
            container_.right.relocate(container_.right.begin(), container_.project_right(left_iter));
        }
    }

    // Gets a boost::optional<V> associated with the given key and
    // makes it the most recently accessed if it exists.
    boost::optional<Val> get(const Key& key)
    {
        Lock l(mutex_);

        auto left_iter = container_.left.find(key);

        if (left_iter != container_.left.end())
        {
            // Item exists. Move to front of container and return the value.
            container_.right.relocate(container_.right.begin(), container_.project_right(left_iter));
            return left_iter->second;
        }
        else
        {
            // Not found.
            return boost::none;
        }
    }

    // Removes the value associated with the provided key. Returns
    // true if removed successfully, false if the element didn't exist.
    bool erase(const Key& key)
    {
        Lock l(mutex_);

        size_t elements_erased = container_.left.erase(key);
        assert(elements_erased < 2);

        return (elements_erased != 0);
    }

    // Clears all items from the LruCache.
    void clear()
    {
        Lock l(mutex_);
        container_.clear();
    }


private:
    size_t capacity_;
    Container container_;
    Mutex mutex_;
};
}
\$\endgroup\$
  • \$\begingroup\$ std::is_const might be of use, but I don't know how you'd make it work with a shared_ptr without hardcoding for the smart pointer wrapper. \$\endgroup\$ – glampert May 14 '16 at 18:06
  • \$\begingroup\$ It is old and my comment is not about code review but I share for those who will seek for a LRU cache implementation. Check out this - github.com/bloomberg/bde/blob/… \$\endgroup\$ – Kirill Lykov Feb 22 at 12:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.