1 //---------------------------------------------------------------------------//
2 // Copyright (c) 2013 Kyle Lutz <kyle.r.lutz@gmail.com>
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
8 // See http://boostorg.github.com/compute for more information.
9 //---------------------------------------------------------------------------//
11 #ifndef BOOST_COMPUTE_DETAIL_LRU_CACHE_HPP
12 #define BOOST_COMPUTE_DETAIL_LRU_CACHE_HPP
18 #include <boost/optional.hpp>
24 // a cache which evicts the least recently used item when it is full
25 template<class Key, class Value>
30 typedef Value value_type;
31 typedef std::list<key_type> list_type;
34 std::pair<value_type, typename list_type::iterator>
37 lru_cache(size_t capacity)
38 : m_capacity(capacity)
51 size_t capacity() const
61 bool contains(const key_type &key)
63 return m_map.find(key) != m_map.end();
66 void insert(const key_type &key, const value_type &value)
68 typename map_type::iterator i = m_map.find(key);
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
76 // insert the new item
77 m_list.push_front(key);
78 m_map[key] = std::make_pair(value, m_list.begin());
82 boost::optional<value_type> get(const key_type &key)
84 // lookup value in the cache
85 typename map_type::iterator i = m_map.find(key);
91 // return the value, but first update its place in the most
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
97 m_list.push_front(key);
99 // update iterator in map
101 const value_type &value = i->second.first;
102 m_map[key] = std::make_pair(value, j);
108 // the item is already at the front of the most recently
109 // used list so just return it
110 return i->second.first;
123 // evict item from the end of most recently used list
124 typename list_type::iterator i = --m_list.end();
135 } // end detail namespace
136 } // end compute namespace
137 } // end boost namespace
139 #endif // BOOST_COMPUTE_DETAIL_LRU_CACHE_HPP