7#if !defined(ASYNC_MQTT_UTIL_VALUE_ALLOCATOR_HPP)
8#define ASYNC_MQTT_UTIL_VALUE_ALLOCATOR_HPP
14#include <boost/multi_index_container.hpp>
15#include <boost/multi_index/ordered_index.hpp>
16#include <boost/multi_index/identity.hpp>
20namespace mi = boost::multi_index;
23class value_allocator {
26 class value_interval {
28 explicit value_interval(value_type v) : low_{v}, high_{v} {}
29 explicit value_interval(value_type l, value_type h) : low_{l}, high_{h} {}
53 friend bool operator<(value_interval
const& lhs, value_interval
const& rhs) {
55 (lhs.low_ < rhs.low_) &&
56 (lhs.high_ < rhs.low_);
58 value_type low()
const {
61 value_type high()
const {
65 friend std::ostream& operator<<(std::ostream& o, value_interval
const v) {
66 o <<
'[' << v.low() <<
',' << v.high() <<
']';
82 explicit value_allocator(value_type lowest, value_type highest)
83 :lowest_{lowest}, highest_{highest} {
85 BOOST_ASSERT(std::numeric_limits<value_type>::min() <= lowest);
86 BOOST_ASSERT(highest <= std::numeric_limits<value_type>::max());
88 pool_.emplace(lowest_, highest_);
95 std::optional<value_type> allocate() {
96 if (pool_.empty())
return std::nullopt;
99 auto it = pool_.begin();
100 value_type value = it->low();
102 if (it->low() + 1 <= it->high()) {
107 BOOST_ASSERT(it->low() < highest_);
108 e = value_interval{value_type(it->low() + 1) , it->high()};
123 std::optional<value_type> first_vacant()
const {
124 if (pool_.empty())
return std::nullopt;
127 auto it = pool_.begin();
135 void deallocate(value_type value) {
136 BOOST_ASSERT(lowest_ <= value && value <= highest_);
137 auto itr = pool_.upper_bound(value_interval{value});
138 if (itr == pool_.end()) {
142 if (itr == pool_.begin()) {
144 pool_.emplace(value);
150 if (itl->high() + 1 == value) {
155 e = value_interval{itl->low(), value};
161 pool_.emplace(value);
164 else if (itr == pool_.begin()) {
168 if (value + 1 == itr->low()) {
173 e = value_interval{value, itr->high()};
179 pool_.emplace(value);
188 if (itl->high() + 1 == value) {
189 if (value + 1 == itr->low()) {
191 auto right = itr->high();
196 e = value_interval{itl->low(), right};
206 e = value_interval{itl->low(), value};
212 if (value + 1 == itr->low()) {
217 e = value_interval{value, itr->high()};
223 pool_.emplace(value);
234 bool use(value_type value) {
235 auto it = pool_.find(value_interval{value});
236 if (it == pool_.end())
return false;
238 value_interval iv = *it;
240 if (iv.low() < value) {
241 pool_.emplace(iv.low(), value - 1);
243 if (value + 1 <= iv.high()) {
244 pool_.emplace(value + 1, iv.high());
254 bool is_used(value_type value)
const {
255 auto it = pool_.find(value_interval{value});
256 return it == pool_.end();
264 pool_.emplace(lowest_, highest_);
267 std::size_t interval_count()
const {
271 std::ostream& dump(std::ostream& o) {
272 for (
auto const& e : pool_) {
278 using mi_value_interval = mi::multi_index_container<
282 mi::identity<value_interval>
286 mi_value_interval pool_;