]>
git.proxmox.com Git - ceph.git/blob - ceph/src/common/lru_map.h
1e1acc95f76de304abd7be5970c0627f8afbb471
6 #include "common/Mutex.h"
9 template <class K
, class V
>
13 typename
std::list
<K
>::iterator lru_iter
;
16 std::map
<K
, entry
> entries
;
17 std::list
<K
> entries_lru
;
26 virtual ~UpdateContext() {}
28 /* update should return true if object is updated */
29 virtual bool update(V
*v
) = 0;
32 bool _find(const K
& key
, V
*value
, UpdateContext
*ctx
);
33 void _add(const K
& key
, V
& value
);
36 lru_map(int _max
) : lock("lru_map"), max(_max
) {}
39 bool find(const K
& key
, V
& value
);
44 * - will return true if object is found
45 * - if ctx is set will return true if object is found and updated
47 bool find_and_update(const K
& key
, V
*value
, UpdateContext
*ctx
);
48 void add(const K
& key
, V
& value
);
49 void erase(const K
& key
);
52 template <class K
, class V
>
53 bool lru_map
<K
, V
>::_find(const K
& key
, V
*value
, UpdateContext
*ctx
)
55 typename
std::map
<K
, entry
>::iterator iter
= entries
.find(key
);
56 if (iter
== entries
.end()) {
60 entry
& e
= iter
->second
;
61 entries_lru
.erase(e
.lru_iter
);
66 r
= ctx
->update(&e
.value
);
71 entries_lru
.push_front(key
);
72 e
.lru_iter
= entries_lru
.begin();
77 template <class K
, class V
>
78 bool lru_map
<K
, V
>::find(const K
& key
, V
& value
)
80 Mutex::Locker
l(lock
);
81 return _find(key
, &value
, NULL
);
84 template <class K
, class V
>
85 bool lru_map
<K
, V
>::find_and_update(const K
& key
, V
*value
, UpdateContext
*ctx
)
87 Mutex::Locker
l(lock
);
88 return _find(key
, value
, ctx
);
91 template <class K
, class V
>
92 void lru_map
<K
, V
>::_add(const K
& key
, V
& value
)
94 typename
std::map
<K
, entry
>::iterator iter
= entries
.find(key
);
95 if (iter
!= entries
.end()) {
96 entry
& e
= iter
->second
;
97 entries_lru
.erase(e
.lru_iter
);
100 entries_lru
.push_front(key
);
101 entry
& e
= entries
[key
];
103 e
.lru_iter
= entries_lru
.begin();
105 while (entries
.size() > max
) {
106 typename
std::list
<K
>::reverse_iterator riter
= entries_lru
.rbegin();
107 iter
= entries
.find(*riter
);
108 // assert(iter != entries.end());
110 entries_lru
.pop_back();
115 template <class K
, class V
>
116 void lru_map
<K
, V
>::add(const K
& key
, V
& value
)
118 Mutex::Locker
l(lock
);
122 template <class K
, class V
>
123 void lru_map
<K
, V
>::erase(const K
& key
)
125 Mutex::Locker
l(lock
);
126 typename
std::map
<K
, entry
>::iterator iter
= entries
.find(key
);
127 if (iter
== entries
.end())
130 entry
& e
= iter
->second
;
131 entries_lru
.erase(e
.lru_iter
);