ceph/src/boost/boost/compute/detail/lru_cache.hpp

   1 //---------------------------------------------------------------------------//
   2 // Copyright (c) 2013 Kyle Lutz <kyle.r.lutz@gmail.com>
   3 //
   4 // Distributed under the Boost Software License, Version 1.0
   5 // See accompanying file LICENSE_1_0.txt or copy at
   6 // http://www.boost.org/LICENSE_1_0.txt
   7 //
   8 // See http://boostorg.github.com/compute for more information.
   9 //---------------------------------------------------------------------------//
  10
  11 #ifndef BOOST_COMPUTE_DETAIL_LRU_CACHE_HPP
  12 #define BOOST_COMPUTE_DETAIL_LRU_CACHE_HPP
  13
  14 #include <map>
  15 #include <list>
  16 #include <utility>
  17
  18 #include <boost/optional.hpp>
  19
  20 namespace boost {
  21 namespace compute {
  22 namespace detail {
  23
  24 // a cache which evicts the least recently used item when it is full
  25 template<class Key, class Value>
  26 class lru_cache
  27 {
  28 public:
  29     typedef Key key_type;
  30     typedef Value value_type;
  31     typedef std::list<key_type> list_type;
  32     typedef std::map<
  33                 key_type,
  34                 std::pair<value_type, typename list_type::iterator>
  35             > map_type;
  36
  37     lru_cache(size_t capacity)
  38         : m_capacity(capacity)
  39     {
  40     }
  41
  42     ~lru_cache()
  43     {
  44     }
  45
  46     size_t size() const
  47     {
  48         return m_map.size();
  49     }
  50
  51     size_t capacity() const
  52     {
  53         return m_capacity;
  54     }
  55
  56     bool empty() const
  57     {
  58         return m_map.empty();
  59     }
  60
  61     bool contains(const key_type &key)
  62     {
  63         return m_map.find(key) != m_map.end();
  64     }
  65
  66     void insert(const key_type &key, const value_type &value)
  67     {
  68         typename map_type::iterator i = m_map.find(key);
  69         if(i == m_map.end()){
  70             // insert item into the cache, but first check if it is full
  71             if(size() >= m_capacity){
  72                 // cache is full, evict the least recently used item
  73                 evict();
  74             }
  75
  76             // insert the new item
  77             m_list.push_front(key);
  78             m_map[key] = std::make_pair(value, m_list.begin());
  79         }
  80     }
  81
  82     boost::optional<value_type> get(const key_type &key)
  83     {
  84         // lookup value in the cache
  85         typename map_type::iterator i = m_map.find(key);
  86         if(i == m_map.end()){
  87             // value not in cache
  88             return boost::none;
  89         }
  90
  91         // return the value, but first update its place in the most
  92         // recently used list
  93         typename list_type::iterator j = i->second.second;
  94         if(j != m_list.begin()){
  95             // move item to the front of the most recently used list
  96             m_list.erase(j);
  97             m_list.push_front(key);
  98
  99             // update iterator in map
 100             j = m_list.begin();
 101             const value_type &value = i->second.first;
 102             m_map[key] = std::make_pair(value, j);
 103
 104             // return the value
 105             return value;
 106         }
 107         else {
 108             // the item is already at the front of the most recently
 109             // used list so just return it
 110             return i->second.first;
 111         }
 112     }
 113
 114     void clear()
 115     {
 116         m_map.clear();
 117         m_list.clear();
 118     }
 119
 120 private:
 121     void evict()
 122     {
 123         // evict item from the end of most recently used list
 124         typename list_type::iterator i = --m_list.end();
 125         m_map.erase(*i);
 126         m_list.erase(i);
 127     }
 128
 129 private:
 130     map_type m_map;
 131     list_type m_list;
 132     size_t m_capacity;
 133 };
 134
 135 } // end detail namespace
 136 } // end compute namespace
 137 } // end boost namespace
 138
 139 #endif // BOOST_COMPUTE_DETAIL_LRU_CACHE_HPP