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