lru.hh

// -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
// vi: set et ts=4 sw=2 sts=2:
#ifndef DUNE_COMMON_LRU_HH
#define DUNE_COMMON_LRU_HH

#include <list>
#include <utility>
#include <map>

#include <dune/common/exceptions.hh>

/** @file
    @author Christian Engwer
    @brief LRU Cache Container, using an STL like interface
 */

namespace Dune {

  namespace {

    /*
       hide the default traits in an empty namespace
     */
    template <typename _Key, typename _Tp,
        typename _Alloc = std::allocator<_Tp> >
    struct _lru_default_traits
    {
      typedef _Key key_type;
      typedef _Alloc allocator;
      typedef std::list< std::pair<_Key, _Tp> > list_type;
      typedef typename list_type::iterator iterator;
      typedef typename std::less<key_type> cmp;
      typedef std::map< key_type, iterator, cmp,
          typename allocator::template rebind<std::pair<const key_type, iterator> >::other > map_type;
    };

  } // end empty namespace

  /**
      @brief LRU Cache Container

      Implementation of an LRU (least recently used) cache
      container. This implementation follows the approach presented in
      http://aim.adc.rmit.edu.au/phd/sgreuter/papers/graphite2003.pdf
   */
  template <typename _Key, typename _Tp,
      typename _Traits = _lru_default_traits<_Key, _Tp> >
  class lru
  {
    typedef typename _Traits::list_type list_type;
    typedef typename _Traits::map_type map_type;
    typedef typename _Traits::allocator allocator;
    typedef typename map_type::iterator map_iterator;
    typedef typename map_type::const_iterator const_map_iterator;

  public:
    typedef typename _Traits::key_type key_type;
    typedef typename allocator::value_type value_type;
    typedef typename allocator::pointer pointer;
    typedef typename allocator::const_pointer const_pointer;
    typedef typename allocator::const_reference const_reference;
    typedef typename allocator::reference reference;
    typedef typename allocator::size_type size_type;
    typedef typename list_type::iterator iterator;
    typedef typename list_type::const_iterator const_iterator;

    /**
     *  Returns a read/write reference to the data of the most
     *  recently used entry.
     */
    reference front()
    {
      return _data.front().second;
    }

    /**
     *  Returns a read-only (constant) reference to the data of the
     *  most recently used entry.
     */
    const_reference front() const
    {
      return _data.front().second;
    }

    /**
     *  Returns a read/write reference to the data of the least
     *  recently used entry.
     */
    reference back()
    {
      return _data.back().second;
    }

    /**
     *  Returns a read-only (constant) reference to the data of the
     *  least recently used entry.
     */
    const_reference back (int i) const
    {
      return _data.back().second;
    }


    /**
     * @brief Removes the first element.
     */
    const void pop_front()
    {
      key_type k = _data.front().first;
      _data.pop_front();
      _index.erase(k);
    }
    /**
     * @brief Removes the last element.
     */
    const void pop_back()
    {
      key_type k = _data.back().first;
      _data.pop_back();
      _index.erase(k);
    }

    /**
     * @brief Finds the element whose key is k.
     *
     * @return iterator
     */
    iterator find (const key_type & key)
    {
      const map_iterator it = _index.find(key);
      if (it == _index.end()) return _data.end();
      return it->second;
    }

    /**
     * @brief Finds the element whose key is k.
     *
     * @return const_iterator
     */
    const_iterator find (const key_type & key) const
    {
      const map_iterator it = _index.find(key);
      if (it == _index.end()) return _data.end();
      return it->second;
    }

    /**
     * @brief Insert a value into the container
     *
     * Stores value under key and marks it as most recent. If this key
     * is already present, the associated data is replaced.
     *
     * @param key   associated with data
     * @param data  to store
     *
     * @return reference of stored data
     */
    reference insert (const key_type & key, const_reference data)
    {
      std::pair<key_type, value_type> x(key, data);
      /* insert item as mru */
      iterator it = _data.insert(_data.begin(), x);
      /* store index */
      _index.insert(std::make_pair(key,it));

      return it->second;
    }

    /**
     * @copydoc touch
     */
    reference insert (const key_type & key)
    {
      return touch (key);
    }

    /**
     * @brief mark data associated with key as most recent
     *
     * @return reference of stored data
     */
    reference touch (const key_type & key)
    {
      /* query _index for iterator */
      map_iterator it = _index.find(key);
      if (it == _index.end())
        DUNE_THROW(Dune::RangeError,
          "Failed to touch key " << key << ", it is not in the lru container");
       /* update _data
         move it to the front
       */
      _data.splice(_data.begin(), _data, it->second);
      return it->second->second;
    }

    /**
     * @brief Retrieve number of entries in the container
     */
    size_type size() const
    {
      return _data.size();
    }

    /**
     * @brief ensure a maximum size of the container
     *
     * If new_size is smaller than size the oldest elements are
     * dropped. Otherwise nothing happens.
     */
    void resize(size_type new_size)
    {
      assert(new_size <= size());

      while (new_size < size())
        pop_back();
    }

    /**
     *
     */
    void clear()
    {
      _data.clear();
      _index.clear();
    }

  private:
    list_type _data;
    map_type _index;

  };

} // namespace Dune

#endif // DUNE_COMMON_LRU_HH