cache.h

#ifndef VGSTOOLS_CACHE_H
#define VGSTOOLS_CACHE_H

#include "stdext.h"

#include <cassert>
#include <list>
#include <map>

/*  Interface for TValue:
 *  size_t weight()
 *  bool is_newer( time_t )
 *  bool load()
 *
 */

namespace vgstools {

template<typename TKey, typename TValue, typename KeyComp = std::less<TKey>>
class cache
{
public:
  typedef TKey key_type;
  typedef TValue mapped_type;
  typedef std::shared_ptr<mapped_type> ptr_type;

private:
  typedef std::pair<key_type, ptr_type> value_type;

  typedef std::list<value_type> ValueList;
  typedef std::map<key_type, typename ValueList::iterator, KeyComp> KeyMap;

public:
  cache( size_t maxWeight )
      : m_maxWeight( maxWeight )
      , m_currentWeight( 0 ) {}

  size_t weight() const { return m_currentWeight; }
  size_t count() const { return m_values.size(); }

  ptr_type get( key_type const& key )
  {
    assert( m_lookup.size() == m_values.size() );

    typename KeyMap::iterator it = m_lookup.find( key );
    ptr_type result = it != m_lookup.end() ? it->second->second : ptr_type( new mapped_type( key ) );

    if ( it != m_lookup.end() ) {
      if ( result->is_current() ) {
        if ( it->second != m_values.begin() ) {
          m_values.erase( it->second );
          it->second = m_values.insert( m_values.begin(), std::make_pair( key, result ) );
        }
        return result;
      }

      m_currentWeight -= result->weight();
      m_values.erase( it->second );
    }

    if ( !result->load() ) {
      if ( it != m_lookup.end() )
        m_lookup.erase( it );
      return ptr_type();
    }

    // put new object into cache
    if ( result->weight() < m_maxWeight ) {
      m_currentWeight += result->weight();

      typename ValueList::iterator element = m_values.insert( m_values.begin(), std::make_pair( key, result ) );
      if ( it != m_lookup.end() )
        it->second = element;
      else
        m_lookup.insert( std::make_pair( key, element ) );

      while ( m_currentWeight > m_maxWeight ) {
        value_type& value = m_values.back();
        m_currentWeight -= value.second->weight();
        m_lookup.erase( m_lookup.find( value.first ) );
        m_values.pop_back();
      }
    }

    return result;
  }

private:
  std::size_t m_maxWeight;
  std::size_t m_currentWeight;
  ValueList m_values;
  KeyMap m_lookup;
};

} // namespace vgstools

#endif // VGSTOOLS_CACHE_H