]>
git.proxmox.com Git - ceph.git/blob - ceph/src/common/LRUSet.h
1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
2 // vim: ts=8 sw=2 smarttab
7 #include <boost/intrusive/list.hpp>
8 #include <boost/intrusive/unordered_set.hpp>
9 #include "include/encoding.h"
11 /// Combination of an LRU with fast hash-based membership lookup
12 template<class T
, int NUM_BUCKETS
=128>
16 : boost::intrusive::unordered_set_base_hook
<> {
21 boost::intrusive::list_member_hook
<> lru_item
;
23 Node(const T
& v
) : value(v
) {}
25 friend std::size_t hash_value(const Node
&node
) {
26 return std::hash
<T
>{}(node
.value
);
28 friend bool operator<(const Node
&a
, const Node
&b
) {
29 return a
.value
< b
.value
;
31 friend bool operator>(const Node
&a
, const Node
&b
) {
32 return a
.value
> b
.value
;
34 friend bool operator==(const Node
&a
, const Node
&b
) {
35 return a
.value
== b
.value
;
39 struct NodeDeleteDisposer
{
40 void operator()(Node
*n
) { delete n
; }
44 boost::intrusive::list
<
46 boost::intrusive::member_hook
<Node
,
47 boost::intrusive::list_member_hook
<>,
52 typename
boost::intrusive::unordered_set
<Node
>::bucket_type base_buckets
[NUM_BUCKETS
];
53 boost::intrusive::unordered_set
<Node
> set
;
57 : set(typename
boost::intrusive::unordered_set
<Node
>::bucket_traits(base_buckets
,
64 LRUSet(const LRUSet
& other
)
65 : set(typename
boost::intrusive::unordered_set
<Node
>::bucket_traits(base_buckets
,
67 for (auto & i
: other
.lru
) {
71 const LRUSet
& operator=(const LRUSet
& other
) {
73 for (auto& i
: other
.lru
) {
87 bool contains(const T
& item
) const {
88 return set
.count(item
) > 0;
95 void insert(const T
& item
) {
97 Node
*n
= new Node(item
);
102 bool erase(const T
& item
) {
103 auto p
= set
.find(item
);
104 if (p
== set
.end()) {
107 lru
.erase(lru
.iterator_to(*p
));
108 set
.erase_and_dispose(p
, NodeDeleteDisposer());
112 void prune(size_t max
) {
113 while (set
.size() > max
) {
114 auto p
= lru
.begin();
116 lru
.erase_and_dispose(p
, NodeDeleteDisposer());
120 void encode(bufferlist
& bl
) const {
122 ENCODE_START(1, 1, bl
);
123 uint32_t n
= set
.size();
125 auto p
= set
.begin();
127 encode(p
->value
, bl
);
133 void decode(bufferlist::const_iterator
& p
) {