1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
2 // vim: ts=8 sw=2 smarttab
6 #include <boost/intrusive_ptr.hpp>
7 #include <boost/intrusive/set.hpp>
8 #include <boost/intrusive/list.hpp>
10 namespace ceph::common
{
13 * intrusive_lru: lru implementation with embedded map and list hook
15 * Note, this implementation currently is entirely thread-unsafe.
18 template <typename K
, typename V
, typename VToK
>
19 struct intrusive_lru_config
{
22 using key_of_value
= VToK
;
25 template <typename Config
>
28 template <typename Config
>
29 class intrusive_lru_base
;
31 template <typename Config
>
32 void intrusive_ptr_add_ref(intrusive_lru_base
<Config
> *p
);
34 template <typename Config
>
35 void intrusive_ptr_release(intrusive_lru_base
<Config
> *p
);
38 template <typename Config
>
39 class intrusive_lru_base
{
40 unsigned use_count
= 0;
42 // null if unreferenced
43 intrusive_lru
<Config
> *lru
= nullptr;
46 boost::intrusive::set_member_hook
<> set_hook
;
47 boost::intrusive::list_member_hook
<> list_hook
;
49 using Ref
= boost::intrusive_ptr
<typename
Config::value_type
>;
50 using lru_t
= intrusive_lru
<Config
>;
52 friend intrusive_lru
<Config
>;
53 friend void intrusive_ptr_add_ref
<>(intrusive_lru_base
<Config
> *);
54 friend void intrusive_ptr_release
<>(intrusive_lru_base
<Config
> *);
56 virtual ~intrusive_lru_base() {}
59 template <typename Config
>
61 using base_t
= intrusive_lru_base
<Config
>;
62 using K
= typename
Config::key_type
;
63 using T
= typename
Config::value_type
;
64 using TRef
= typename
base_t::Ref
;
66 using lru_set_option_t
= boost::intrusive::member_hook
<
68 boost::intrusive::set_member_hook
<>,
71 using VToK
= typename
Config::key_of_value
;
73 using type
= typename
VToK::type
;
74 const type
&operator()(const base_t
&obc
) {
75 return VToK()(static_cast<const T
&>(obc
));
78 using lru_set_t
= boost::intrusive::set
<
81 boost::intrusive::key_of_value
<VToKWrapped
>
85 using lru_list_t
= boost::intrusive::list
<
87 boost::intrusive::member_hook
<
89 boost::intrusive::list_member_hook
<>,
91 lru_list_t unreferenced_list
;
93 size_t lru_target_size
= 0;
96 while (!unreferenced_list
.empty() &&
97 lru_set
.size() > lru_target_size
) {
98 auto &b
= unreferenced_list
.front();
100 unreferenced_list
.pop_front();
101 lru_set
.erase_and_dispose(
102 lru_set
.iterator_to(b
),
103 [](auto *p
) { delete p
; }
108 void access(base_t
&b
) {
111 unreferenced_list
.erase(lru_list_t::s_iterator_to(b
));
115 void insert(base_t
&b
) {
122 void unreferenced(base_t
&b
) {
124 unreferenced_list
.push_back(b
);
131 * Returns the TRef corresponding to k if it exists or
132 * creates it otherwise. Return is:
133 * std::pair(reference_to_val, found)
135 std::pair
<TRef
, bool> get_or_create(const K
&k
) {
136 typename
lru_set_t::insert_commit_data icd
;
137 auto [iter
, missing
] = lru_set
.insert_check(
142 lru_set
.insert_commit(*ret
, icd
);
144 return {TRef(ret
), false};
147 return {TRef(static_cast<T
*>(&*iter
)), true};
152 * Returns the TRef corresponding to k if it exists or
155 TRef
get(const K
&k
) {
156 if (auto iter
= lru_set
.find(k
); iter
!= std::end(lru_set
)) {
158 return TRef(static_cast<T
*>(&*iter
));
164 void set_target_size(size_t target_size
) {
165 lru_target_size
= target_size
;
169 friend void intrusive_ptr_add_ref
<>(intrusive_lru_base
<Config
> *);
170 friend void intrusive_ptr_release
<>(intrusive_lru_base
<Config
> *);
173 template <typename Config
>
174 void intrusive_ptr_add_ref(intrusive_lru_base
<Config
> *p
) {
180 template <typename Config
>
181 void intrusive_ptr_release(intrusive_lru_base
<Config
> *p
) {
183 assert(p
->use_count
> 0);
185 if (p
->use_count
== 0) {
186 p
->lru
->unreferenced(*p
);