LRUCache.h

// LruCache.h
//
// Author David Barrett-Lennard
// (C)opyright Cedanet Pty Ltd 2006

#pragma once
#ifndef Ceda_cxUtils_LruCache_H
#define Ceda_cxUtils_LruCache_H

/*
LRU cache
---------

multi_index_container

lru_cache<Key,Value> 
    has map, list and capacity
    not threadsafe
    insert may cause an eviction

lru_cache_x<Key,Value,Calculator>
    has mutex, lru_cache<Key,Value>,  map<key, condition_variable>

    get():
        lock mutex
      again:
        look up lru_cache. found --> return value
        look up map<key, (count,cv) >  found --> increment count, wait on signalled, decrement count, goto again:
                                       else insert (1,cv), call calculator(), insert into lru_cache, signal cv, decrement count, return value

We want an LRU cache with a max size on the number of elements.  

Then we to separately implement the concept of taking responsibility for insert a (key,value)
*/

#include "CedaAssert.h"
#include <map>
#include <list>
#include <utility>
#include <mutex>
#include <condition_variable>

namespace ceda 
{

template<typename Key, typename Value>
class LruCache
{
public:
    typedef Key key_type;
    typedef Value value_type;

    LruCache(size_t capacity) : capacity_(capacity) {}

    size_t size() const { return map_.size(); }
    size_t capacity() const { return capacity_; }
    bool empty() const { return map_.empty(); }

    bool contains(const Key &key) { return map_.find(key) != map_.end(); }

    // Try to insert a (key,value) pair.
    // Returns false if insertion failed because that key is already present.
    bool insert(const Key &key, const Value &value)
    {
        auto i = map_.find(key);
        if (i == map_.end())
        {
            if (size() >= capacity_)
            {
                // Cache is full, evict the LRU
                auto last = --list_.end();
                map_.erase(*last);
                list_.erase(last);
            }

            // Insert new item
            list_.push_front(key);
            map_[key] = std::make_pair(value, list_.begin());
            return true;
        }
        else
        {
            // Value with key already exists, don't replace
            return false;
        }
    }

    bool get(const Key &key, Value& value)
    {
        auto i = map_.find(key);
        if (i == map_.end())
        {
            // value not in cache
            return false;
        }

        value = i->second.first;

        // Update place in the most recently used list
        auto j = i->second.second;
        if (j != list_.begin())
        {
            // Move to front of list
            list_.erase(j);
            list_.push_front(key);

            // Update map
            i->second.second = list_.begin();
        }

        return true;
    }

    void clear()
    {
        map_.clear();
        list_.clear();
    }

private:
    typedef std::list<Key> list_type;
    typedef std::map<Key, std::pair<Value, typename list_type::iterator>> map_type;

    map_type map_;
    list_type list_;
    size_t capacity_;
};

template<typename Key, typename Value, typename Calculator>
class GetOrCalcLruCache
{
public:
    typedef Key key_type;
    typedef Value value_type;

    GetOrCalcLruCache(size_t capacity, Calculator c = Calculator()) : 
        calculator_(c), 
        cache_(capacity), 
        numHits_(0), 
        numCalcs_(0),
        numWaits_(0) {}

    ~GetOrCalcLruCache()
    {
        cxAssert( calculatorsMap_.empty() );
    }

    int64 NumHits() const { return numHits_; }
    int64 NumCalcs() const { return numCalcs_; }
    int64 NumWaits() const { return numWaits_; }
    
    void clear()
    {
        std::lock_guard<std::mutex> lock(mutex_);
        cache_.clear();
    }

    // Used to poll for whether an entry for the given key is currently present in the map.
    bool IsCached(const Key& key) const
    {
        std::lock_guard<std::mutex> lock(mutex_);
        return cache_.contains(key);
    }

    // Allows for polling whether an entry in the map is already present.  This function always
    // returns quickly without blocking on a calculation - either directly or indirectly.
    bool GetCachedValue(const Key& key, Value& value) 
    {
        std::lock_guard<std::mutex> lock(mutex_);
        return cache_.get(key, value);
    }

    // Try to insert a (key,value) pair.  Returns false if insertion failed because that key
    // is already present.
    bool InsertCachedValue(const Key& key, const Value& value)
    {
        std::lock_guard<std::mutex> lock(mutex_);
        return cache_.insert(key, value);
    }

    Value operator[](const Key& key) 
    {
        Entry* e = nullptr;
        {
            std::unique_lock<std::mutex> lock(mutex_);
            while(1)
            {
                Value value;
                if (cache_.get(key, value))
                {
                    ++numHits_;
                    return value;
                }
                auto i = calculatorsMap_.find(key);
                if (i == calculatorsMap_.end())
                {
                    ++numCalcs_;
                    e = &calculatorsMap_[key];
                    cxAssert(e->count_ == 1);
                    cxAssert(!e->calculated_);
                    break;
                }
                else
                {
                    ++numWaits_;
                    e = &i->second;
                    cxAssert(!e->calculated_);
                    cxAssert(e->count_ > 0);
                    ++e->count_;
                    e->cv_.wait(lock,[e]{ return e->calculated_; });
                    
                    cxAssert(e->calculated_);
                    cxAssert(e->count_ > 0);

                    if (--e->count_ == 0)
                    {
                        calculatorsMap_.erase(key);
                    }
                }
            }
        }

        cxAssert(e != nullptr);

        // Calculate value without holding a lock
        Value value = calculator_(key);

        {
            std::lock_guard<std::mutex> lock(mutex_);

            cxAssert(e->count_ > 0);
            cxAssert(!e->calculated_);

            cxVerify( cache_.insert(key,value) );
            e->calculated_ = true;

            e->cv_.notify_all();

            cxAssert(e->count_ > 0);
            if (--e->count_ == 0)
            {
                calculatorsMap_.erase(key);
            }

            return value;
        }
    }

private:
    struct Entry
    {
        Entry() : count_(1), calculated_(false) {}
        ~Entry()
        {
            cxAssert(count_ == 0);
            cxAssert(calculated_);
        }

        int count_;
        std::condition_variable cv_;
        bool calculated_;
    };
    
    mutable std::mutex mutex_;
    Calculator calculator_;
    LruCache<Key,Value> cache_;
    std::map<Key, Entry> calculatorsMap_;

    int64 numHits_;
    int64 numCalcs_;
    int64 numWaits_;
};

} // namespace ceda

#if 0

namespace ceda
{

template <typename Value>
struct DefaultValuePtrDeleter 
{
    void OnDelete(Value* v)
    {
        delete v;
    }
};

template <typename Value>
struct DoNothingValueDeleter 
{
    void OnDelete(Value& v)
    {
    }
};
 
///////////////////////////////////////////////////////////////////////////////////////////////////
// LRUCache<Key,Value>

/*
Implements a cache with a Least Recently Used (LRU) eviction policy.  LRUCache is templatised in

    class Key               Used to uniquely identify entries in the cache
    class Value             Represents the value of an element in the cache
    class ValueDeleter      Allows the value deletion policy to be controlled

If the cache stores large objects that are expensive to copy (e.g. images), then Value should be a 
pointer type.  This is where it is useful to be able to control the destruction policy.  For example
the ValueDeleter may be implemented as follows

struct ValueDeleter 
{
    void OnDelete(Image* image)
    {
        delete image;
    }
};
 
The ValueDeleter must be a cloneable object with a method called OnDelete() that takes a Value 
either by reference or value.

struct ValueDeleter 
{
    void OnDelete(Value v)
};

OnDelete() is called each time a value in the cache is deleted.
*/


template <typename Key, typename Value, typename ValueDeleter>
class LRUCache
{
public:
    //typedef std::pair<Key,Value> value_type;

    struct value_type
    {
        Key m_key;
        Value m_value;
    };

    struct Node : public value_type
    {
        Node() : prev_(nullptr), next_(nullptr) {}

        bool operator<(const Node& rhs) const { return m_key < rhs.m_key; }
        bool operator==(const Node& rhs) const { return m_key == rhs.m_key; }
        bool operator!=(const Node& rhs) const { return m_key != rhs.m_key; }
    
        Node* prev_;
        Node* next_;
    };

private:
    typedef std::set<Node> NODES;
    
    //typedef std::map<Key,Node*> MAP;

public:
    LRUCache(ValueDeleter valueDeleter, ssize_t maxSize) :
        m_valueDeleter(valueDeleter),
        m_maxSize(maxSize),
        first_(nullptr),
        last_(nullptr)
    {
        cxAssert(maxSize > 0);
    }

    ~LRUCache()
    {
        Clear();
    }

    // Clear all entries in the cache
    void Clear()
    {
        // Delete all the modes in the map
        for(MAP::iterator i = m_map.begin() ; i != m_map.end() ; ++i)
        {
            Node* node = i->second;
            cxAssert(node != nullptr);
            m_valueDeleter.OnDelete(node->second);
            delete node;
        }
        m_map.clear();
        first_ = nullptr;
        last_ = nullptr;
    }

    void SetMaxCacheSize(ssize_t maxSize)
    {
        cxAssert(maxSize > 0);
        RemoveLRUValues(maxSize);
        m_maxSize = maxSize;
    }

    bool IsEmpty() const
    {
        return first_ != nullptr;
    }

    // Find the value with the given key in the cache, or returns nullptr if not found
    Value* Find(const Key& key)
    {
        MAP::const_iterator i = m_map.find(key);
        if (i == m_map.end())
        {
            return nullptr;
        }
        else
        {
            Node* node = i->second;
            cxAssert(node != nullptr);
            if (node != last_)
            {
                // Send node to the back of the queue for the LRU algorithm
                // Note that there is no need to modify the map.
                RemoveNode(node);
                PushBackNode(node);
            }
            return &node->second;
        }
    }

    void Insert(/*takes*/ Node* node)
    {
        cxAssert(node);
        // An existing entry must not already be present in the cache
        cxAssert(m_map.find(node->first) == m_map.end());

        // Remove entries in cache as required
        RemoveLRUValues(m_maxSize-1);

        PushBackNode(node);
        m_map.insert(MAP::value_type(node->first,node));
    }

    // Insert the given key,value pair into the cache.  If necessary an existing value will be evicted
    void Insert(const Key& key, const Value& value)
    {
        Node* node = new Node;
        node->first = key;
        node->second = value;
        Insert(node);
    }

    struct const_iterator
    {
        const_iterator(typename MAP::const_iterator pos) : m_pos(pos) {}
        
        const value_type& operator*() const
        { 
            return *(m_pos->second);
        }

        const value_type* operator->() const
        {
            return m_pos->second;
        }

        const_iterator& operator++()           // Prefix
        {
            ++m_pos;
            return *this;
        }
        
        const const_iterator operator++(int)   // Postfix
        {
            const_iterator it = *this;
            ++(*this);
            return it;
        }

        bool operator==(const const_iterator& other) const
        {
            return m_pos == other.m_pos;
        }

        bool operator!=(const const_iterator& other) const
        {
            return !operator==(other);
        }

        typename MAP::const_iterator m_pos;
    };

    const_iterator begin() const { return const_iterator(m_map.begin()); }
    const_iterator end() const { return const_iterator(m_map.end()); }
private:
    void RemoveLRUValues(ssize_t size)
    {
        cxAssert(size >= 0);

        // Remove entries in cache as required
        while (m_map.size() > size)
        {
            // Pop next node from the front of the eviction queue
            Node* node = PopFrontNode();
            cxAssert(node != nullptr);

            // Remove entry from map
            MAP::iterator i = m_map.find(node->first);
            cxAssert(i != m_map.end());
            m_map.erase(i);

            m_valueDeleter.OnDelete(node->second);
            delete node;
        }
    }

    void RemoveNode(Node* s)
    {
        cxAssert(s != nullptr);

        if (s->prev_)
        {
            cxAssert(s->prev_->next_ == s);
            s->prev_->next_ = s->next_;    
        }
        else
        {
            cxAssert(first_ == s);
            first_ = s->next_;    
        }

        if (s->next_)
        {
            cxAssert(s->next_->prev_ == s);
            s->next_->prev_ = s->prev_;
        }
        else
        {
            cxAssert(last_ == s);
            last_ = s->prev_;
        }

        s->prev_ = nullptr;
        s->next_ = nullptr;
    }

    Node* PopFrontNode()
    {
        cxAssert(first_ != nullptr);

        Node* node = first_;
        RemoveNode(node);
        return node;
    }

    void PushBackNode(Node* s)
    {
        cxAssert(s != nullptr);
        cxAssert(s->prev_ == nullptr);
        cxAssert(s->next_ == nullptr);

        if (last_)
        {
            cxAssert(first_ != nullptr);
            cxAssert(last_->next_ == nullptr);
            last_->next_ = s;
            s->prev_ = last_;
        }
        else
        {
            cxAssert(first_ == nullptr);
            first_ = s;
        }
        last_ = s;
    }

    ValueDeleter m_valueDeleter;

    // Maximum number of entries permitted in the cache
    ssize_t m_maxSize;

    // Provides fast access to values in the cache that are uniquely identified by a key
    MAP m_map;

    // Nodes form a doubly linked list for an eviction queue to implement the LRU eviction policy
    Node* first_;
    Node* last_;
};

} // namespace ceda

#endif

#endif // include guard