]>
Commit | Line | Data |
---|---|---|
9f95a23c TL |
1 | // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- |
2 | // vim: ts=8 sw=2 smarttab | |
3 | ||
4 | #pragma once | |
5 | ||
6 | #include <boost/intrusive_ptr.hpp> | |
7 | #include <boost/intrusive/set.hpp> | |
8 | #include <boost/intrusive/list.hpp> | |
9 | ||
10 | namespace ceph::common { | |
11 | ||
12 | /** | |
13 | * intrusive_lru: lru implementation with embedded map and list hook | |
14 | * | |
15 | * Note, this implementation currently is entirely thread-unsafe. | |
16 | */ | |
17 | ||
18 | template <typename K, typename V, typename VToK> | |
19 | struct intrusive_lru_config { | |
20 | using key_type = K; | |
21 | using value_type = V; | |
22 | using key_of_value = VToK; | |
23 | }; | |
24 | ||
25 | template <typename Config> | |
26 | class intrusive_lru; | |
27 | ||
28 | template <typename Config> | |
29 | class intrusive_lru_base; | |
30 | ||
31 | template <typename Config> | |
32 | void intrusive_ptr_add_ref(intrusive_lru_base<Config> *p); | |
33 | ||
34 | template <typename Config> | |
35 | void intrusive_ptr_release(intrusive_lru_base<Config> *p); | |
36 | ||
37 | ||
38 | template <typename Config> | |
39 | class intrusive_lru_base { | |
40 | unsigned use_count = 0; | |
41 | ||
42 | // null if unreferenced | |
43 | intrusive_lru<Config> *lru = nullptr; | |
44 | ||
45 | public: | |
46 | boost::intrusive::set_member_hook<> set_hook; | |
47 | boost::intrusive::list_member_hook<> list_hook; | |
48 | ||
49 | using Ref = boost::intrusive_ptr<typename Config::value_type>; | |
50 | using lru_t = intrusive_lru<Config>; | |
51 | ||
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> *); | |
55 | ||
56 | virtual ~intrusive_lru_base() {} | |
57 | }; | |
58 | ||
59 | template <typename Config> | |
60 | class intrusive_lru { | |
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; | |
65 | ||
66 | using lru_set_option_t = boost::intrusive::member_hook< | |
67 | base_t, | |
68 | boost::intrusive::set_member_hook<>, | |
69 | &base_t::set_hook>; | |
70 | ||
71 | using VToK = typename Config::key_of_value; | |
72 | struct VToKWrapped { | |
73 | using type = typename VToK::type; | |
74 | const type &operator()(const base_t &obc) { | |
75 | return VToK()(static_cast<const T&>(obc)); | |
76 | } | |
77 | }; | |
78 | using lru_set_t = boost::intrusive::set< | |
79 | base_t, | |
80 | lru_set_option_t, | |
81 | boost::intrusive::key_of_value<VToKWrapped> | |
82 | >; | |
83 | lru_set_t lru_set; | |
84 | ||
85 | using lru_list_t = boost::intrusive::list< | |
86 | base_t, | |
87 | boost::intrusive::member_hook< | |
88 | base_t, | |
89 | boost::intrusive::list_member_hook<>, | |
90 | &base_t::list_hook>>; | |
91 | lru_list_t unreferenced_list; | |
92 | ||
93 | size_t lru_target_size = 0; | |
94 | ||
95 | void evict() { | |
96 | while (!unreferenced_list.empty() && | |
97 | lru_set.size() > lru_target_size) { | |
98 | auto &b = unreferenced_list.front(); | |
99 | assert(!b.lru); | |
100 | unreferenced_list.pop_front(); | |
101 | lru_set.erase_and_dispose( | |
102 | lru_set.iterator_to(b), | |
103 | [](auto *p) { delete p; } | |
104 | ); | |
105 | } | |
106 | } | |
107 | ||
108 | void access(base_t &b) { | |
109 | if (b.lru) | |
110 | return; | |
111 | unreferenced_list.erase(lru_list_t::s_iterator_to(b)); | |
112 | b.lru = this; | |
113 | } | |
114 | ||
115 | void insert(base_t &b) { | |
116 | assert(!b.lru); | |
117 | lru_set.insert(b); | |
118 | b.lru = this; | |
119 | evict(); | |
120 | } | |
121 | ||
122 | void unreferenced(base_t &b) { | |
123 | assert(b.lru); | |
124 | unreferenced_list.push_back(b); | |
125 | b.lru = nullptr; | |
126 | evict(); | |
127 | } | |
128 | ||
129 | public: | |
130 | /** | |
131 | * Returns the TRef corresponding to k if it exists or | |
132 | * creates it otherwise. Return is: | |
133 | * std::pair(reference_to_val, found) | |
134 | */ | |
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( | |
138 | k, | |
139 | icd); | |
140 | if (missing) { | |
141 | auto ret = new T(k); | |
142 | lru_set.insert_commit(*ret, icd); | |
143 | insert(*ret); | |
144 | return {TRef(ret), false}; | |
145 | } else { | |
146 | access(*iter); | |
147 | return {TRef(static_cast<T*>(&*iter)), true}; | |
148 | } | |
149 | } | |
150 | ||
f67539c2 TL |
151 | /** |
152 | * Returns the TRef corresponding to k if it exists or | |
153 | * nullptr otherwise. | |
154 | */ | |
155 | TRef get(const K &k) { | |
156 | if (auto iter = lru_set.find(k); iter != std::end(lru_set)) { | |
157 | access(*iter); | |
158 | return TRef(static_cast<T*>(&*iter)); | |
159 | } else { | |
160 | return nullptr; | |
161 | } | |
162 | } | |
163 | ||
9f95a23c TL |
164 | void set_target_size(size_t target_size) { |
165 | lru_target_size = target_size; | |
166 | evict(); | |
167 | } | |
168 | ||
169 | friend void intrusive_ptr_add_ref<>(intrusive_lru_base<Config> *); | |
170 | friend void intrusive_ptr_release<>(intrusive_lru_base<Config> *); | |
171 | }; | |
172 | ||
173 | template <typename Config> | |
174 | void intrusive_ptr_add_ref(intrusive_lru_base<Config> *p) { | |
175 | assert(p); | |
176 | assert(p->lru); | |
177 | p->use_count++; | |
178 | } | |
179 | ||
180 | template <typename Config> | |
181 | void intrusive_ptr_release(intrusive_lru_base<Config> *p) { | |
182 | assert(p); | |
183 | assert(p->use_count > 0); | |
184 | --p->use_count; | |
185 | if (p->use_count == 0) { | |
186 | p->lru->unreferenced(*p); | |
187 | } | |
188 | } | |
189 | ||
190 | ||
191 | } |