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 lru_cache(size_t capacity)37 lru_cache(size_t capacity) 38 : m_capacity(capacity) 39 { 40 } 41 ~lru_cache()42 ~lru_cache() 43 { 44 } 45 size() const46 size_t size() const 47 { 48 return m_map.size(); 49 } 50 capacity() const51 size_t capacity() const 52 { 53 return m_capacity; 54 } 55 empty() const56 bool empty() const 57 { 58 return m_map.empty(); 59 } 60 contains(const key_type & key)61 bool contains(const key_type &key) 62 { 63 return m_map.find(key) != m_map.end(); 64 } 65 insert(const key_type & key,const value_type & value)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 get(const key_type & key)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 clear()114 void clear() 115 { 116 m_map.clear(); 117 m_list.clear(); 118 } 119 120 private: evict()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 140