LRUCache.h

Go to the documentation of this file.

//-*- Mode: C++ -*-
//  DDC originally by Alexey Sokirko
//  Changes and modifications 2011-2015 by Bryan Jurish
//
//  This file is part of DDC.
// 
//  DDC is free software: you can redistribute it and/or modify
//  it under the terms of the GNU Lesser General Public License as published by
//  the Free Software Foundation, either version 3 of the License, or
//  (at your option) any later version.
// 
//  DDC is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU Lesser General Public License for more details.
// 
//  You should have received a copy of the GNU Lesser General Public License
//  along with DDC.  If not, see <http://www.gnu.org/licenses/>.
//

#ifndef DDC_LRUCACHE_H
#define DDC_LRUCACHE_H

#include "../CommonLib/ddcConfig.h"
#include <list>
#include <map>

#ifdef HAVE_PTHREAD
# include <pthread.h>
# define DDC_IFPTHREAD(x) x
# define DDC_IFPTHREADELSE(x,y) x
#else
# define DDC_IFPTHREAD(x)
# define DDC_IFPTHREADELSE(x,y) y
#endif

//======================================================================
// Globals

#define DDC_DEFAULT_LRU_CACHE_CAPACITY 1024

//======================================================================
template<class Key, class Val>
class ddcLRUCache {
public:
    //------------------------------------------------------------
    // public typedefs

    typedef Key KeyT;

    typedef Val ValT;

#if HAVE_PTHREAD
    typedef pthread_mutex_t* MutexT;
#else
    typedef void* MutexT;
#endif

    typedef std::pair<KeyT,ValT> ItemT;

    typedef std::list<ItemT> ListT;

    typedef std::map<KeyT, typename ListT::iterator> MapT;

    typedef typename MapT::iterator iterator;

    typedef typename MapT::const_iterator const_iterator;

public:
    //------------------------------------------------------------
    // pseudo-private data (public just in case you Know What You're Doing)

    size_t m_capacity;

    size_t m_size;

    ListT m_list;

    MapT  m_map;

    MutexT m_mutex;

public:
    //------------------------------------------------------------
    // public methods: constructors etc

    //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    ddcLRUCache(size_t capacity=DDC_DEFAULT_LRU_CACHE_CAPACITY, MutexT mutex=NULL)
        : m_capacity(capacity),
          m_size(0),
          m_mutex(mutex)
    {};

    //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    void clear()
    {
        m_map.clear();
        m_list.clear();
        m_size = 0;
    };

    //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    void clean()
    {
        while (m_size > m_capacity) {
            const ItemT &lru_item = m_list.back();
            m_map.erase(lru_item.first);
            m_list.pop_back();
            --m_size;
        }
    };

    //------------------------------------------------------------
    // public methods: basic accessors

    inline MutexT mutex() const
    { return m_mutex; };

    inline MutexT mutex(MutexT mut)
    { return m_mutex=mut; };

    inline size_t size() const
    { return m_size; };

    inline size_t capacity() const
    { return m_capacity; };

    inline size_t reserve(size_t cap)
    {
        m_capacity=cap;
        clean();
        return m_capacity;
    };

    //------------------------------------------------------------
    // public methods: locking

    inline void lock()
    { DDC_IFPTHREAD(if (m_mutex) pthread_mutex_lock(m_mutex)); };

    inline void unlock()
    { DDC_IFPTHREAD(if (m_mutex) pthread_mutex_unlock(m_mutex)); };

    //------------------------------------------------------------
    // public methods: map iterators

    inline iterator begin()               { return m_map.begin(); };
    inline iterator end()                 { return m_map.end(); };
    inline const_iterator begin() const   { return m_map.begin(); };
    inline const_iterator end()   const   { return m_map.end(); };

    //------------------------------------------------------------
    // public methods: lookup (no implicit locking; use must call lock() and unlock() if and when appropriate)

    inline iterator find(const KeyT &key)
    { return m_map.find(key); };

    inline iterator lower_bound(const KeyT &key)
    { return m_map.lower_bound(key); };

    inline iterator upper_bound(const KeyT &key)
    { return m_map.upper_bound(key); };
  
    inline const_iterator find(const KeyT &key) const
    { return m_map.find(key); };

    inline const_iterator lower_bound(const KeyT &key) const
    { return m_map.lower_bound(key); };

    inline const_iterator upper_bound(const KeyT &key) const
    { return m_map.upper_bound(key); };

    inline iterator get(const KeyT &key)
    {
        iterator mapi = m_map.find(key);
        if (mapi != m_map.end() && mapi->second != m_list.begin())
            promote(mapi);
        return mapi;
    };

    void promote(const_iterator &it)
    { if (it->second != m_list.begin()) m_list.splice(m_list.begin(), m_list, it->second); };

    void promote(iterator &it)
    { if (it->second != m_list.begin()) m_list.splice(m_list.begin(), m_list, it->second); };

    void insert(const KeyT &key, const ValT &val)
    {
        iterator mapi = get(key);
        if (mapi != m_map.end()) {
            //-- update existing item (it's already been promoted by get() if it exists)
            mapi->second->second = val;
        }
        else if (m_capacity > 0) {
            //-- insert new item (only if we're not just going to delete it again)
            m_list.push_front(std::make_pair(key,val));
            m_map.insert(std::make_pair(key, m_list.begin()));
            ++m_size;
            clean();
        }
        //-- sanity check: FAILS for NavHintCache on v2.1.10 due to bogus NavHintKey::operator<()
        //assert(m_size==m_list.size() && m_size==m_map.size());
    };

};


#endif /* DDC_LRUCACHE_H */

/*--- emacs style variables ---
 * Local Variables:
 *  mode: C++
 *  c-file-style: "ellemtel"
 *  c-basic-offset: 4
 *  tab-width: 8
 *  indent-tabs-mode: nil
 * End:
 */