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