lru.hh

Go to the documentation of this file.

// -*- 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 <memory>
 
#include <dune/common/exceptions.hh>
#include <dune/common/unused.hh>
 
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 std::allocator_traits<allocator>::template rebind_alloc<std::pair<const key_type, iterator> > > map_type;
    };
 
  } // end empty namespace
 
  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;
    using pointer = typename allocator::value_type*;
    using const_pointer = typename allocator::value_type const*;
    using const_reference = typename allocator::value_type const&;
    using reference = typename allocator::value_type&;
    typedef typename allocator::size_type size_type;
    typedef typename list_type::iterator iterator;
    typedef typename list_type::const_iterator const_iterator;
 
    reference front()
    {
      return _data.front().second;
    }
 
    const_reference front() const
    {
      return _data.front().second;
    }
 
    reference back()
    {
      return _data.back().second;
    }
 
    const_reference back (int i) const
    {
      DUNE_UNUSED_PARAMETER(i);
      return _data.back().second;
    }
 
 
    void pop_front()
    {
      key_type k = _data.front().first;
      _data.pop_front();
      _index.erase(k);
    }
    void pop_back()
    {
      key_type k = _data.back().first;
      _data.pop_back();
      _index.erase(k);
    }
 
    iterator find (const key_type & key)
    {
      const map_iterator it = _index.find(key);
      if (it == _index.end()) return _data.end();
      return it->second;
    }
 
    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;
    }
 
    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;
    }
 
    reference insert (const key_type & key)
    {
      return touch (key);
    }
 
    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;
    }
 
    size_type size() const
    {
      return _data.size();
    }
 
    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