value_allocator.hpp

// Copyright Takatoshi Kondo 2020
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
 
#if !defined(ASYNC_MQTT_UTIL_VALUE_ALLOCATOR_HPP)
#define ASYNC_MQTT_UTIL_VALUE_ALLOCATOR_HPP
 
#include <ostream>
#include <limits>
 
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/identity.hpp>
 
#include <async_mqtt/util/optional.hpp>
 
namespace async_mqtt {
 
namespace mi = boost::multi_index;
 
template <typename T>
class value_allocator {
    using value_type = T;
 
    class value_interval {
    public:
        explicit value_interval(value_type v) : low_{v}, high_{v} {}
        value_interval(value_type l, value_type h) : low_{l}, high_{h} {}
 
        // true
        // | lhs |   | rhs |
        //
        // false
        // | lhs |
        //      | rhs |
        //
        // false
        // |   lhs   |
        //   | rhs |
        //
        // false
        //   | lhs |
        // |   rhs   |
        //
        // false
        //   | lhs |
        // | rhs |
        //
        // false
        // | rhs |   | lhs |
        //
        friend bool operator<(value_interval const& lhs, value_interval const& rhs) {
            return
                (lhs.low_ < rhs.low_) &&
                (lhs.high_ < rhs.low_);
        }
        value_type low() const {
            return low_;
        }
        value_type high() const {
            return high_;
        }
 
        friend std::ostream& operator<<(std::ostream& o, value_interval const v) {
            o << '[' << v.low() << ',' << v.high() << ']';
            return o;
        }
 
    private:
        value_type low_;
        value_type high_;
    };
 
public:
    value_allocator(value_type lowest, value_type highest)
        :lowest_{lowest}, highest_{highest} {
 
        BOOST_ASSERT(std::numeric_limits<value_type>::min() <= lowest);
        BOOST_ASSERT(highest <= std::numeric_limits<value_type>::max());
        // create one interval that contains whole values
        pool_.emplace(lowest_, highest_);
    }
 
    optional<value_type> allocate() {
        if (pool_.empty()) return nullopt;
 
        // The smallest interval is the target.
        auto it = pool_.begin();
        value_type value = it->low();
 
        if (it->low() + 1 <= it->high()) {
            // If the interval contains other value, then update the interval.
            pool_.modify(
                it,
                [&](auto& e) {
                    BOOST_ASSERT(it->low() < highest_);
                    e = value_interval{value_type(it->low() + 1) , it->high()};
                }
            );
        }
        else {
            pool_.erase(it);
        }
 
        return value;
    }
 
    optional<value_type> first_vacant() const {
        if (pool_.empty()) return nullopt;
 
        // The smallest interval is the target.
        auto it = pool_.begin();
        return it->low();
    }
 
    void deallocate(value_type value) {
        BOOST_ASSERT(lowest_ <= value && value <= highest_);
        auto itr = pool_.upper_bound(value_interval{value});
        if (itr == pool_.end()) {
 
            // ..... v
 
            if (itr == pool_.begin()) {
                // value is fully allocated
                pool_.emplace(value);
                return;
            }
 
            auto itl = itr;
            --itl;
            if (itl->high() + 1 == value) { // Can concat to the left interval
                // Concat left
                pool_.modify(
                    itl,
                    [&](auto& e) {
                        e = value_interval{itl->low(), value};
                    }
                );
            }
            else {
                // No concat
                pool_.emplace(value);
            }
        }
        else if (itr == pool_.begin()) {
 
            // v .....
 
            if (value + 1 == itr->low()) { // Can concat to the right interval
                // Concat right
                pool_.modify(
                    itr,
                    [&](auto& e) {
                        e = value_interval{value, itr->high()};
                    }
                );
            }
            else {
                // No concat
                pool_.emplace(value);
            }
        }
        else {
 
            // .. v ..
 
            auto itl = itr;
            --itl;
            if (itl->high() + 1 == value) { // Can concat to the left interval
                if (value + 1 == itr->low()) { // Can concat to the right interval
                    // Concat both
                    auto right = itr->high();
                    pool_.erase(itr);
                    pool_.modify(
                        itl,
                        [&](auto& e) {
                            e = value_interval{itl->low(), right};
                        }
                    );
 
                }
                else {
                    // Concat left
                    pool_.modify(
                        itl,
                        [&](auto& e) {
                            e = value_interval{itl->low(), value};
                        }
                    );
                }
            }
            else {
                if (value + 1 == itr->low()) { // Can concat to the right interval
                    // Concat right
                    pool_.modify(
                        itr,
                        [&](auto& e) {
                            e = value_interval{value, itr->high()};
                        }
                    );
                }
                else {
                    // No concat
                    pool_.emplace(value);
                }
            }
        }
    }
 
    bool use(value_type value) {
        auto it = pool_.find(value_interval{value});
        if (it == pool_.end()) return false;
 
        value_interval iv = *it;
        pool_.erase (it);
        if (iv.low() < value) {
            pool_.emplace(iv.low(), value - 1);
        }
        if (value + 1 <= iv.high()) {
            pool_.emplace(value + 1, iv.high());
        }
        return true;
    }
 
    bool is_used(value_type value) const {
        auto it = pool_.find(value_interval{value});
        return it == pool_.end();
    }
 
    void clear() {
        pool_.clear();
        pool_.emplace(lowest_, highest_);
    }
 
    std::size_t interval_count() const {
        return pool_.size();
    }
 
    std::ostream& dump(std::ostream& o) {
        for (auto const& e : pool_) {
            o << e;
        }
        return o;
    }
private:
    using mi_value_interval = mi::multi_index_container<
        value_interval,
        mi::indexed_by<
            mi::ordered_unique<
                mi::identity<value_interval>
            >
        >
    >;
    mi_value_interval pool_;
    value_type lowest_;
    value_type highest_;
};
 
} // namespace async_mqtt
 
#endif // ASYNC_MQTT_UTIL_VALUE_ALLOCATOR_HPP