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
|
#ifndef CEPH_LRU_MAP_H
#define CEPH_LRU_MAP_H
#include "common/ceph_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;
ceph::mutex lock = ceph::make_mutex("lru_map::lock");
size_t max;
public:
class UpdateContext {
public:
virtual ~UpdateContext() {}
/* update should return true if object is updated */
virtual bool update(V *v) = 0;
};
bool _find(const K& key, V *value, UpdateContext *ctx);
void _add(const K& key, V& value);
public:
lru_map(int _max) : max(_max) {}
virtual ~lru_map() {}
bool find(const K& key, V& value);
/*
* find_and_update()
*
* - will return true if object is found
* - if ctx is set will return true if object is found and updated
*/
bool find_and_update(const K& key, V *value, UpdateContext *ctx);
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, UpdateContext *ctx)
{
typename std::map<K, entry>::iterator iter = entries.find(key);
if (iter == entries.end()) {
return false;
}
entry& e = iter->second;
entries_lru.erase(e.lru_iter);
bool r = true;
if (ctx)
r = ctx->update(&e.value);
if (value)
*value = e.value;
entries_lru.push_front(key);
e.lru_iter = entries_lru.begin();
return r;
}
template <class K, class V>
bool lru_map<K, V>::find(const K& key, V& value)
{
std::lock_guard l(lock);
return _find(key, &value, NULL);
}
template <class K, class V>
bool lru_map<K, V>::find_and_update(const K& key, V *value, UpdateContext *ctx)
{
std::lock_guard l(lock);
return _find(key, value, ctx);
}
template <class K, class V>
void lru_map<K, V>::_add(const K& key, V& value)
{
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);
// ceph_assert(iter != entries.end());
entries.erase(iter);
entries_lru.pop_back();
}
}
template <class K, class V>
void lru_map<K, V>::add(const K& key, V& value)
{
std::lock_guard l(lock);
_add(key, value);
}
template <class K, class V>
void lru_map<K, V>::erase(const K& key)
{
std::lock_guard 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
|
