MRUCache.h

/**************************************************************************
 * BASF2 (Belle Analysis Framework 2)                                     *
 * Copyright(C) 2010-2011  Belle II Collaboration                         *
 *                                                                        *
 * Author: The Belle II Collaboration                                     *
 * Contributors: Martin Ritter                                            *
 *                                                                        *
 * This software is provided "as is" without any warranty.                *
 **************************************************************************/
 
#pragma once
 
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/member.hpp>
 
namespace Belle2 {
  template <class KEY, class VALUE> class MRUCache {
  public:
    typedef std::pair<KEY, VALUE> value_type;
    typedef boost::multi_index_container <
    value_type,
    boost::multi_index::indexed_by <
    boost::multi_index::sequenced<>,
    boost::multi_index::hashed_unique <
    boost::multi_index::member<value_type, KEY, &value_type::first>
    >
    >
    > container_type;
    typedef typename container_type::const_iterator iterator;
    typedef typename container_type::template nth_index<1>::type::const_iterator hash_iterator;
 
    explicit MRUCache(size_t maxSize): m_maxSize(maxSize), m_hits(0), m_misses(0), m_overflows(0) {}
 
    void insert(const KEY& key, const VALUE& value) { insert(value_type(key, value)); }
 
    void insert(const value_type& item)
    {
      std::pair<iterator, bool> p = m_container.push_front(item);
      if (!p.second) {  /* duplicate item, put existing in front */
        m_container.replace(p.first, item);
        update(p.first);
      } else if (m_container.size() > m_maxSize) {  /* keep the length <= maxSize */
        ++m_overflows;
        m_container.pop_back();
      }
    }
 
    bool retrieve(const KEY& key, VALUE& value)
    {
      hash_iterator it = m_container.template get<1>().find(key);
      if (it == m_container.template get<1>().end()) {
        ++m_misses;
        return false;
      }
      update(m_container.template project<0>(it));
      value = it->second;
      ++m_hits;
      return true;
    }
 
    iterator begin() const { return m_container.begin();  }
    iterator end() const { return m_container.end();  }
 
    size_t size() const { return m_container.size(); }
    void clear()
    {
      m_container.clear();
      m_hits = 0;
      m_misses = 0;
      m_overflows = 0;
    }
 
    void setMaxSize(size_t maxSize) { m_maxSize = maxSize; }
    size_t getMaxSize() const { return m_maxSize; }
    unsigned int getHits() const { return m_hits; }
    unsigned int getMisses() const { return m_misses; }
    unsigned int getOverflows() const { return m_overflows; }
 
  protected:
    void update(const iterator& item)
    {
      m_container.relocate(m_container.begin(), item);
    }
 
    container_type m_container;
    size_t m_maxSize;
    unsigned int m_hits;
    unsigned int m_misses;
    unsigned int m_overflows;
  };
}