async_mqtt 5.0.0
Loading...
Searching...
No Matches
value_allocator.hpp
1// Copyright Takatoshi Kondo 2020
2//
3// Distributed under the Boost Software License, Version 1.0.
4// (See accompanying file LICENSE_1_0.txt or copy at
5// http://www.boost.org/LICENSE_1_0.txt)
6
7#if !defined(ASYNC_MQTT_UTIL_VALUE_ALLOCATOR_HPP)
8#define ASYNC_MQTT_UTIL_VALUE_ALLOCATOR_HPP
9
10#include <ostream>
11#include <limits>
12
13#include <boost/multi_index_container.hpp>
14#include <boost/multi_index/ordered_index.hpp>
15#include <boost/multi_index/identity.hpp>
16
17#include <async_mqtt/util/optional.hpp>
18
19namespace async_mqtt {
20
21namespace mi = boost::multi_index;
22
23template <typename T>
24class value_allocator {
25 using value_type = T;
26
27 class value_interval {
28 public:
29 explicit value_interval(value_type v) : low_{v}, high_{v} {}
30 value_interval(value_type l, value_type h) : low_{l}, high_{h} {}
31
32 // true
33 // | lhs | | rhs |
34 //
35 // false
36 // | lhs |
37 // | rhs |
38 //
39 // false
40 // | lhs |
41 // | rhs |
42 //
43 // false
44 // | lhs |
45 // | rhs |
46 //
47 // false
48 // | lhs |
49 // | rhs |
50 //
51 // false
52 // | rhs | | lhs |
53 //
54 friend bool operator<(value_interval const& lhs, value_interval const& rhs) {
55 return
56 (lhs.low_ < rhs.low_) &&
57 (lhs.high_ < rhs.low_);
58 }
59 value_type low() const {
60 return low_;
61 }
62 value_type high() const {
63 return high_;
64 }
65
66 friend std::ostream& operator<<(std::ostream& o, value_interval const v) {
67 o << '[' << v.low() << ',' << v.high() << ']';
68 return o;
69 }
70
71 private:
72 value_type low_;
73 value_type high_;
74 };
75
76public:
83 value_allocator(value_type lowest, value_type highest)
84 :lowest_{lowest}, highest_{highest} {
85
86 BOOST_ASSERT(std::numeric_limits<value_type>::min() <= lowest);
87 BOOST_ASSERT(highest <= std::numeric_limits<value_type>::max());
88 // create one interval that contains whole values
89 pool_.emplace(lowest_, highest_);
90 }
91
96 optional<value_type> allocate() {
97 if (pool_.empty()) return nullopt;
98
99 // The smallest interval is the target.
100 auto it = pool_.begin();
101 value_type value = it->low();
102
103 if (it->low() + 1 <= it->high()) {
104 // If the interval contains other value, then update the interval.
105 pool_.modify(
106 it,
107 [&](auto& e) {
108 BOOST_ASSERT(it->low() < highest_);
109 e = value_interval{value_type(it->low() + 1) , it->high()};
110 }
111 );
112 }
113 else {
114 pool_.erase(it);
115 }
116
117 return value;
118 }
119
124 optional<value_type> first_vacant() const {
125 if (pool_.empty()) return nullopt;
126
127 // The smallest interval is the target.
128 auto it = pool_.begin();
129 return it->low();
130 }
131
136 void deallocate(value_type value) {
137 BOOST_ASSERT(lowest_ <= value && value <= highest_);
138 auto itr = pool_.upper_bound(value_interval{value});
139 if (itr == pool_.end()) {
140
141 // ..... v
142
143 if (itr == pool_.begin()) {
144 // value is fully allocated
145 pool_.emplace(value);
146 return;
147 }
148
149 auto itl = itr;
150 --itl;
151 if (itl->high() + 1 == value) { // Can concat to the left interval
152 // Concat left
153 pool_.modify(
154 itl,
155 [&](auto& e) {
156 e = value_interval{itl->low(), value};
157 }
158 );
159 }
160 else {
161 // No concat
162 pool_.emplace(value);
163 }
164 }
165 else if (itr == pool_.begin()) {
166
167 // v .....
168
169 if (value + 1 == itr->low()) { // Can concat to the right interval
170 // Concat right
171 pool_.modify(
172 itr,
173 [&](auto& e) {
174 e = value_interval{value, itr->high()};
175 }
176 );
177 }
178 else {
179 // No concat
180 pool_.emplace(value);
181 }
182 }
183 else {
184
185 // .. v ..
186
187 auto itl = itr;
188 --itl;
189 if (itl->high() + 1 == value) { // Can concat to the left interval
190 if (value + 1 == itr->low()) { // Can concat to the right interval
191 // Concat both
192 auto right = itr->high();
193 pool_.erase(itr);
194 pool_.modify(
195 itl,
196 [&](auto& e) {
197 e = value_interval{itl->low(), right};
198 }
199 );
200
201 }
202 else {
203 // Concat left
204 pool_.modify(
205 itl,
206 [&](auto& e) {
207 e = value_interval{itl->low(), value};
208 }
209 );
210 }
211 }
212 else {
213 if (value + 1 == itr->low()) { // Can concat to the right interval
214 // Concat right
215 pool_.modify(
216 itr,
217 [&](auto& e) {
218 e = value_interval{value, itr->high()};
219 }
220 );
221 }
222 else {
223 // No concat
224 pool_.emplace(value);
225 }
226 }
227 }
228 }
229
235 bool use(value_type value) {
236 auto it = pool_.find(value_interval{value});
237 if (it == pool_.end()) return false;
238
239 value_interval iv = *it;
240 pool_.erase (it);
241 if (iv.low() < value) {
242 pool_.emplace(iv.low(), value - 1);
243 }
244 if (value + 1 <= iv.high()) {
245 pool_.emplace(value + 1, iv.high());
246 }
247 return true;
248 }
249
255 bool is_used(value_type value) const {
256 auto it = pool_.find(value_interval{value});
257 return it == pool_.end();
258 }
259
263 void clear() {
264 pool_.clear();
265 pool_.emplace(lowest_, highest_);
266 }
267
268 std::size_t interval_count() const {
269 return pool_.size();
270 }
271
272 std::ostream& dump(std::ostream& o) {
273 for (auto const& e : pool_) {
274 o << e;
275 }
276 return o;
277 }
278private:
279 using mi_value_interval = mi::multi_index_container<
280 value_interval,
281 mi::indexed_by<
282 mi::ordered_unique<
283 mi::identity<value_interval>
284 >
285 >
286 >;
287 mi_value_interval pool_;
288 value_type lowest_;
289 value_type highest_;
290};
291
292} // namespace async_mqtt
293
294#endif // ASYNC_MQTT_UTIL_VALUE_ALLOCATOR_HPP