/home/mhx/git/github/libmoost/include/moost/container/lru.hpp

Go to the documentation of this file.

/* vim:set ts=3 sw=3 sts=3 et: */
#ifndef MOOST_CONTAINER_LRU_HPP__
#define MOOST_CONTAINER_LRU_HPP__

#include <list>
#include <limits>

#include <boost/functional/hash.hpp>
#include <boost/type_traits/is_integral.hpp>
#include <boost/function.hpp>

#include "sparse_hash_map.hpp"

namespace moost { namespace container {

   template <typename Key, bool>
   struct get_deleted_key
   {
      Key operator()() const
      { return Key(); } // generic version
   };

   template <typename Key>
   struct get_deleted_key<Key, true>
   {
      Key operator()() const
      { return (std::numeric_limits<Key>::max)(); } // specialized for integrals
   };

   template<class Key,
      typename Data,
      typename HashFcn = boost::hash<Key> >
   class lru
   {
   private:
      typedef std::list< std::pair< Key, Data > > lru_t;

   public:
      typedef typename lru_t::value_type value_type;
      typedef typename lru_t::value_type::first_type key_type;
      typedef typename lru_t::value_type::second_type mapped_type;

      typedef typename lru_t::iterator iterator;
      typedef typename lru_t::const_iterator const_iterator;
      typedef typename lru_t::reference reference;
      typedef typename lru_t::const_reference const_reference;

   private:
      typedef google::sparse_hash_map< key_type, iterator, HashFcn > hm_key_data;
      typedef boost::function<bool(key_type, const mapped_type & value)> evict_func_t;

      lru_t m_lru; // head = oldest, tail = newest
      hm_key_data       m_key_data;
      size_t            m_max_size;

   public:

      lru(size_t max_size = std::numeric_limits<size_t>::max()) : m_max_size(max_size)
      {
         m_key_data.set_deleted_key( get_deleted_key<key_type, boost::is_integral<key_type>::value >()() );
      }

      void set_deleted_key(const key_type & deleted_key)
      {
         m_key_data.set_deleted_key( deleted_key );
      }

      // =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
      // stuff with keys

      bool get(const key_type & key, mapped_type & value, bool bbump = true)
      {
         iterator itr = find(key);

         if(itr == m_lru.end())
            return false;

         // first, move the iterator to the tail of the lru
         if(bbump)
            bump(itr);

         // now get the value
         value = itr->second;
         return true;
      }

      void put(const key_type & key, const mapped_type & value, evict_func_t evict_func = evict_func_t())
      {
         insert(key, value, evict_func);
      }

      void erase(const key_type & key)
      {
         iterator itr = find(key);

         if(itr != m_lru.end())
            erase(itr);
      }

      bool peek(const key_type & key, mapped_type & value)
      {
         return get(key, value, false);
      }

      // bump something to the top of the lru
      bool bump(const key_type & key)
      {
         iterator itr = find(key);

         if(itr == m_lru.end())
            return false;

         return bump(itr);
      }

      bool exists(const key_type & key) const
      {
         return find(key) != m_lru.end();
      }

      // =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
      // stuff with iterators

      const_iterator find(const key_type & key) const
      {
         typename hm_key_data::const_iterator it_key_data = m_key_data.find(key);
         return it_key_data == m_key_data.end() ? m_lru.end() : it_key_data->second;
      }

      iterator find(const key_type & key)
      {
         typename hm_key_data::iterator it_key_data = m_key_data.find(key);
         return it_key_data == m_key_data.end() ? m_lru.end() : it_key_data->second;
      }

      reference front()
      {
         return m_lru.front();
      }

      const_reference front() const
      {
         return m_lru.front();
      }

      reference back()
      {
         return m_lru.back();
      }

      const_reference back() const
      {
         return m_lru.back();
      }

      std::pair<iterator, bool> insert(const key_type & key, const mapped_type & value, evict_func_t evict_func = evict_func_t())
      {
         if (m_max_size == 0)
            m_lru.end();

         typename hm_key_data::iterator it_key_data = m_key_data.find(key);

         bool const existed = (it_key_data != m_key_data.end());

         if (existed)
         {
            erase(it_key_data->second);
         }

         if (m_key_data.size() == m_max_size)
         {
            if(evict_func)
            {
               typename std::list< std::pair< key_type, mapped_type > >::iterator it;
               for (it = m_lru.begin(); it != m_lru.end(); ++it)
               {
                  if (evict_func(it->first, it->second))
                     break;
               }

               if (it == m_lru.end()) // we couldn't evict anything?  then we can't insert this element
               {
                  evict_func(key, value);
                  return std::make_pair(it, existed);
               }

               erase(it);
            }
            else
            {
               erase(m_lru.begin());
            }
         }

         // insert
         return std::make_pair(
            m_key_data[key] = m_lru.insert( m_lru.end(), std::make_pair(key, value) ),
            existed
         );
      }

      bool bump(iterator itr)
      {
         m_lru.splice(m_lru.end(), m_lru, itr);
         return true;
      }

      void erase(iterator it)
      {
         m_key_data.erase(it->first);
         m_lru.erase(it);
      }

      // =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
      // operators

      mapped_type const & operator[](key_type const & key) const
      {
         iterator itr = find(key);
         if(itr == m_lru.end()) { throw std::runtime_error("key not found"); }
         return itr->second;
      }

      mapped_type & operator[](key_type const & key)
      {
         iterator itr = find(key);
         if(itr == m_lru.end()) { throw std::runtime_error("key not found"); }
         return itr->second;
      }

      // =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
      // everything else

      void clear()
      {
          m_key_data.clear();
          m_lru.clear();
      }

      void purge()
      {
         clear();

         // We use Scott Meyers "swap trick" to purge memory. This is necessary
         // because the underlying structure of a hash map is a vector, which
         // doesn't give up its memory without a fight
         hm_key_data(m_key_data).swap(m_key_data);
      }

      size_t size() const
      {
         return m_key_data.size();
      }

      bool empty() const
      {
         return m_lru.empty();
      }

      size_t max_size() const
      {
         return m_max_size;
      }

      iterator begin()
      {
         return m_lru.begin();
      }

      const_iterator begin() const
      {
         return m_lru.begin();
      }

      iterator end()
      {
         return m_lru.end();
      }

      const_iterator end() const
      {
         return m_lru.end();
      }

   };

}} // moost::container

#endif // MOOST_CONTAINER_LRU_HPP__