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
|
#ifndef CEPH_LRU_MAP_H
#define CEPH_LRU_MAP_H
#include <list>
#include <map>
#include "common/Mutex.h"
template <class K, class V>
class lru_map {
struct entry {
V value;
typename std::list<K>::iterator lru_iter;
};
std::map<K, entry> entries;
std::list<K> entries_lru;
Mutex lock;
size_t max;
public:
lru_map(int _max) : lock("lru_map"), max(_max) {}
virtual ~lru_map() {}
bool find(const K& key, V& value);
void add(const K& key, V& value);
void erase(const K& key);
};
template <class K, class V>
bool lru_map<K, V>::find(const K& key, V& value)
{
lock.Lock();
typename std::map<K, entry>::iterator iter = entries.find(key);
if (iter == entries.end()) {
lock.Unlock();
return false;
}
entry& e = iter->second;
entries_lru.erase(e.lru_iter);
value = e.value;
entries_lru.push_front(key);
e.lru_iter = entries_lru.begin();
lock.Unlock();
return true;
}
template <class K, class V>
void lru_map<K, V>::add(const K& key, V& value)
{
lock.Lock();
typename std::map<K, entry>::iterator iter = entries.find(key);
if (iter != entries.end()) {
entry& e = iter->second;
entries_lru.erase(e.lru_iter);
}
entries_lru.push_front(key);
entry& e = entries[key];
e.value = value;
e.lru_iter = entries_lru.begin();
while (entries.size() > max) {
typename std::list<K>::reverse_iterator riter = entries_lru.rbegin();
iter = entries.find(*riter);
// assert(iter != entries.end());
entries.erase(iter);
entries_lru.pop_back();
}
lock.Unlock();
}
template <class K, class V>
void lru_map<K, V>::erase(const K& key)
{
Mutex::Locker l(lock);
typename std::map<K, entry>::iterator iter = entries.find(key);
if (iter == entries.end())
return;
entry& e = iter->second;
entries_lru.erase(e.lru_iter);
entries.erase(iter);
}
#endif
|
