]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |