hxslot_map.hpp

Go to the documentation of this file.

#pragma once
// SPDX-FileCopyrightText: © 2017-2026 Adrian Johnston.
// SPDX-License-Identifier: MIT
// This file is licensed under the MIT license found in the LICENSE.md file.

 
#include "libhatchet.h"
 
// HX_USE_MACROS_WITH_MODULE allows including macros alongside the module.
#if HX_USE_MACROS_WITH_MODULE
#error Header does not provide macros alone.
#endif
 
#include "hxallocator.hpp"
#include "hxutility.h"
 
HX_NS_BEGIN_

// Makes the mask a compile time constant when non-0.
template<hxsize_t mask_>
class hxslot_map_mask_ {
public:
    hxinline_constexpr uint32_t get_mask_(void) const { return static_cast<uint32_t>(mask_); }
    hxinline void set_mask_(uint32_t) const { } // GCOVR_EXCL_LINE. Unreachable code below c++17.
};
 
template<>
class hxslot_map_mask_<hxallocator_dynamic_capacity> {
public:
    hxinline hxattr_nodiscard uint32_t get_mask_(void) const { return m_mask_; }
    hxinline void set_mask_(uint32_t mask_) { m_mask_ = mask_; }
private:
    uint32_t m_mask_;
};
 
#if HX_CPLUSPLUS >= 202002L
template<typename T_>
concept hxslot_map_concept_ = requires(T_& x_) {
    sizeof(T_);
    x_.~T_();
};
#else
#define hxslot_map_concept_ typename
#endif

template<hxslot_map_concept_ T_, uint32_t table_size_bits_=hxallocator_dynamic_capacity>
class hxslot_map {
public:
    static_assert(table_size_bits_ < 31u, "Slot index must fit in the low 31-bits of the handle");

    using iterator = T_*;

    using const_iterator = const T_*;
 
    using value_t = T_;

    hxslot_map(void);

    ~hxslot_map();
 
#if HX_CPLUSPLUS >= 202302L
    template<typename self_t_, typename callable_t_>
    hxattr_nodiscard auto and_then(
        this self_t_&& self_, hxhandle_t handle_, callable_t_&& callable_)
        -> hxremove_cvref_t<decltype(
            hxforward<callable_t_>(callable_)(
                hxforward_like<self_t_>(hxdeclval<T_&>())))>;
#endif // HX_CPLUSPLUS >= 202302L

    hxinline hxattr_flatten const T_* begin(void) const { return this->data(); }
 
    hxinline hxattr_flatten T_* begin(void) { return this->data(); }

    hxattr_nodiscard hxsize_t capacity(void) const;

    hxattr_nodiscard hxinline hxattr_flatten
    const T_* cbegin(void) const { return this->data(); }

    hxattr_nodiscard const T_* cend(void) const;

    void clear(void) noexcept;

    hxattr_nodiscard hxinline hxattr_flatten
    const T_* data(void) const { return m_values_.data(); }
 
    hxattr_nodiscard hxinline hxattr_flatten
    T_* data(void) { return m_values_.data(); }

    template<typename... args_t_>
    hxhandle_t emplace(args_t_&&... args_) noexcept;

    hxinline hxattr_nodiscard bool empty(void) const { return m_size_ == 0u; }

    hxattr_nodiscard const T_* end(void) const;
 
    hxattr_nodiscard hxinline hxattr_flatten
    T_* end(void) { return this->data() + this->size(); }

    template<typename callable_t_>
    hxsize_t erase_if(callable_t_&& callable_) noexcept;

    hxattr_nodiscard bool full(void) const;

    hxattr_nodiscard hxattr_flatten hxhandle_t handle_at(hxsize_t index_) const noexcept;

    template<typename... args_t_>
    hxhandle_t insert(args_t_&&... args_) noexcept;

    hxinline hxattr_nodiscard hxsize_t max_size(void) const { return this->capacity(); }
 
#if HX_CPLUSPLUS >= 202302L
    template<typename self_t_, typename callable_t_>
    hxattr_nodiscard auto or_else(
        this self_t_&& self_, hxhandle_t handle_, callable_t_&& callable_)
        -> decltype(self_.end());
#endif // HX_CPLUSPLUS >= 202302L

    bool reset(hxhandle_t handle_) noexcept;

    void set_size_bits(uint32_t bits_);

    hxinline hxattr_nodiscard hxsize_t size(void) const { return static_cast<hxsize_t>(m_size_); }

    hxattr_nodiscard T_* value(hxhandle_t handle_) noexcept;
 
    hxattr_nodiscard const T_* value(hxhandle_t handle_) const noexcept;
 
#if HX_CPLUSPLUS >= 202302L
    template<typename self_t_, typename... args_t_>
    hxattr_nodiscard T_ value_or(
        this self_t_&& self_, hxhandle_t handle_, args_t_&&... args_);
#endif // HX_CPLUSPLUS >= 202302L
 
private:
    // See detail/hxslot_map.inl for the design.
    static hxinline_constexpr hxsize_t s_capacity_ =
        table_size_bits_ == hxallocator_dynamic_capacity
            ? hxallocator_dynamic_capacity
            : static_cast<hxsize_t>(1) << table_size_bits_;
 
    static hxinline_constexpr hxsize_t s_value_capacity_ =
        table_size_bits_ == hxallocator_dynamic_capacity
            ? hxallocator_dynamic_capacity
            : s_capacity_ - 1;
 
    class slot_t_ {
    public:
        uint64_t m_handle_;
        uint32_t m_index_;
        uint32_t m_backref_;
    };
 
    void build_free_list_(void);
 
    uint32_t m_size_;
    hxslot_map_mask_<s_value_capacity_> m_mask_;
    hxallocator<slot_t_, s_capacity_> m_slots_;
    hxallocator<T_, s_value_capacity_> m_values_;
};
 
#include "detail/hxslot_map.inl"
HX_NS_END_