hxhash_table.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 "hxkey.hpp"
#include "hxptr.hpp"
#include "hxallocator.hpp"
#include "hxrange.hpp"
 
HX_NS_BEGIN_
 
#include "detail/hxpow2_allocator.hpp"
 
class hxhash_node_base;
 
#if HX_CPLUSPLUS >= 202002L
template<typename node_t_>
concept hxhash_table_concept_ =
    requires(node_t_& node_, const node_t_& const_node_) {
        sizeof(typename node_t_::key_t); // node must publish a key_t type
        { &node_ } -> hxconvertible_to<hxhash_node_base*>; // node_t must derive from hxhash_node_base
        // returns the node's key
        { const_node_.hash_key() } -> hxconvertible_to<const typename node_t_::key_t&>;
    };
#else
#define hxhash_table_concept_ typename
#endif

class hxhash_node_base {
protected:
    friend class hxhash_table_base_;
    template<hxhash_table_concept_ node_t_, typename deleter_t_, bool multi_t_,
        uint32_t table_size_bits_> friend class hxhash_table;

    hxhash_node_base(hxhash_t hash_) : hash_next(hxnull), hash_val(hash_) { }
 
    hxhash_node_base* hash_next;
    hxhash_t hash_val;
};

template<typename key_t_>
class hxhash_table_set_node : public hxhash_node_base {
public:
    using key_t = key_t_;

    template<typename ref_t_>
    hxhash_table_set_node(ref_t_&& key_)
        : hxhash_node_base(0), m_key_(hxforward<ref_t_>(key_)) {
        this->hash_val = hxkey_hash(m_key_);
    }

    hxhash_table_set_node(void) = delete;
    hxhash_table_set_node(const hxhash_table_set_node& src_) = delete;
    hxhash_table_set_node& operator=(const hxhash_table_set_node& x_) = delete;

    bool operator==(const hxhash_table_set_node& x_) const { return hxkey_equal(m_key_, x_.m_key_); }

    bool operator<(const hxhash_table_set_node& x_) const { return hxkey_less(m_key_, x_.m_key_); }

    const key_t_& hash_key(void) const { return m_key_; }

    hxhash_t hash_value(void) const { return this->hash_val; }

    static hxhash_t hash_value(const key_t_& key_) { return hxkey_hash(key_); }
 
private:
    key_t_ m_key_;
};

template<typename key_t_, typename value_t_>
class hxhash_table_map_node : public hxhash_table_set_node<key_t_> {
public:
    using key_t = key_t_;
    using value_t = value_t_;

    hxhash_table_map_node(const key_t_& key_) :
        hxhash_table_set_node<key_t_>(key_) { }

    template<typename ref_t_>
    hxhash_table_map_node(const key_t_& key_, ref_t_&& value_) :
        hxhash_table_set_node<key_t_>(key_), m_value_(hxforward<ref_t_>(value_)) { }

    bool operator==(const hxhash_table_map_node& x_) const;

    bool operator<(const hxhash_table_map_node& x_) const;

    const value_t_& value(void) const { return m_value_; }

    value_t_& value(void) { return m_value_; }
 
private:
    value_t_ m_value_;
};

// Internal. Type erased shared code.
class hxhash_table_base_ {
private:
    template<hxhash_table_concept_ node_t_, typename deleter_t_, bool multi_t_, uint32_t table_size_bits_>
    friend class hxhash_table;
    using hxhash_equal_fn_ = bool(*)(const hxhash_node_base* node_, const void* key_);
    using hxhash_deleter_fn_ = void(*)(hxhash_node_base* node_, void* context_);
    static hxsize_t chain_count_multi_(const hxhash_node_base* head_, const void* key_,
        hxhash_equal_fn_ equal_);
    static void chain_erase_at_(hxhash_node_base** head_, hxhash_node_base* node_);
    static hxsize_t chain_erase_multi_(hxhash_node_base** head_, const void* key_,
        hxhash_equal_fn_ equal_, hxhash_deleter_fn_ deleter_, void* deleter_context_);
    static hxhash_node_base* chain_extract_(hxhash_node_base** head_, const void* key_,
        hxhash_equal_fn_ equal_);
    static hxsize_t chain_length_(const hxhash_node_base* head_);
    static hxhash_node_base* chain_replace_(hxhash_node_base** head_, hxhash_node_base* node_,
        const void* key_, hxhash_equal_fn_ equal_);
    static void table_clear_(hxhash_node_base** table_, hxsize_t bucket_count_,
        hxhash_deleter_fn_ deleter_, void* deleter_context_);
};

template<hxhash_table_concept_ node_t_,
    typename deleter_t_=hxdefault_delete,
    bool multi_t_ = false,
    uint32_t table_size_bits_=hxallocator_dynamic_capacity>
class hxhash_table : private deleter_t_, private hxhash_table_base_ {
public:
    using node_t = node_t_;
    using key_t = typename node_t_::key_t;

    class const_iterator
    {
    public:
        const_iterator(void) : m_next_bucket_(hxnull), m_bucket_end_(hxnull),
            m_current_node_(hxnull) { }

        const_iterator& operator++(void);
        const_iterator operator++(int) { const_iterator t_(*this); operator++(); return t_; }
        bool operator==(const const_iterator& x_) const;
#if HX_CPLUSPLUS < 202002L // C++20 defaults != from ==.
        bool operator!=(const const_iterator& x_) const { return !(*this == x_); }
#endif
        const node_t_& operator*(void) const;
        const node_t_* operator->(void) const;
    private:
        friend class hxhash_table;
        const_iterator(const hxhash_table* table_);
        const_iterator(const hxhash_table* table_, node_t_* node_);
        void next_bucket_(void);
        hxhash_node_base** m_next_bucket_;
        hxhash_node_base** m_bucket_end_;
    protected:
        node_t_* m_current_node_;
    };

    class iterator : public const_iterator
    {
    public:
        iterator(void) { }
        iterator& operator++(void) { const_iterator::operator++(); return *this; }
        iterator operator++(int) { iterator t_(*this); const_iterator::operator++(); return t_; }
        node_t_& operator*(void) const;
        node_t_* operator->(void) const;
    private:
        friend class hxhash_table;
        iterator(hxhash_table* table_) : const_iterator(table_) { }
        iterator(hxhash_table* table_, node_t_* node_) : const_iterator(table_, node_) { }
        iterator(const const_iterator& src_) : const_iterator(src_) { }
    };

    explicit hxhash_table(deleter_t_ deleter_=deleter_t_());

    ~hxhash_table(void) { this->clear(this->deleter()); }

    template<hxrange_concept_ range_t_,
        hxenable_if_t<!hxis_lvalue_reference<range_t_>(), int> = 0>
    void add_range(range_t_&& range_) noexcept;
 
#if HX_CPLUSPLUS >= 202302L
    template<typename self_t_, typename callable_t_>
    hxattr_nodiscard auto and_then(
        this self_t_&& self_, const key_t& key_, callable_t_&& callable_)
        -> hxremove_cvref_t<decltype(
            hxforward<callable_t_>(callable_)(
                hxforward_like<self_t_>(hxdeclval<node_t_&>())))>;

    template<typename self_t_, typename callable_t_>
    hxattr_nodiscard auto and_then(
        this self_t_&& self_, const_iterator it_, callable_t_&& callable_)
        -> hxremove_cvref_t<decltype(
            hxforward<callable_t_>(callable_)(hxforward_like<self_t_>(
                hxdeclval<const node_t_&>())))>;
#endif // HX_CPLUSPLUS >= 202302L

    const_iterator begin(void) const { return const_iterator(this); }

    iterator begin(void) { return iterator(this); }

    hxattr_nodiscard hxsize_t bucket_count(void) const { return m_table_.capacity(); }

    const_iterator cbegin(void) const { return const_iterator(this); }

    const_iterator cend(void) const { return const_iterator(); }

    template<typename deleter_u_>
    void clear(deleter_u_&& deleter_) noexcept;

    void clear(void) noexcept { this->clear(this->deleter()); }

    hxattr_nodiscard hxsize_t count(const typename node_t_::key_t& key_) const;

    hxattr_nodiscard const deleter_t_& deleter(void) const;
 
    hxattr_nodiscard deleter_t_& deleter(void);

    template<hxsystem_allocator_t allocator_=hxsystem_allocator_current,
        hxalignment_t align_=hxalignment, bool multi_=multi_t_, class... args_t_>
    hxenable_if_t<multi_, iterator> emplace(args_t_&&... args_) noexcept;

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

    const_iterator end(void) const { return const_iterator(); }

    iterator end(void) { return iterator(); }

    template<typename deleter_u_>
    hxsize_t erase(const typename node_t_::key_t& key_, deleter_u_&& deleter_) noexcept;

    hxsize_t erase(const typename node_t_::key_t& key_) noexcept;

    iterator erase(const const_iterator& it_) noexcept;

    hxptr<node_t_, deleter_t_> extract(const typename node_t_::key_t& key_) noexcept;

    hxptr<node_t_, deleter_t_> extract(const const_iterator& it_) noexcept;

    hxattr_nodiscard hxattr_flatten const_iterator find(
        const typename node_t_::key_t& key_, const const_iterator& previous_=const_iterator()) const;
 
    hxattr_nodiscard hxattr_flatten iterator find(
        const typename node_t_::key_t& key_, const const_iterator& previous_=const_iterator());

    hxattr_nodiscard bool has_value(const key_t& key_) const;

    iterator insert(node_t_* ptr_) noexcept;

    template<typename deleter_u_>
    iterator insert(hxptr<node_t_, deleter_u_>&& ptr_) noexcept;

    hxattr_nodiscard float load_factor(void) const;

    hxattr_nodiscard hxsize_t load_max(void) const;
 
#if HX_CPLUSPLUS >= 202302L
    template<typename self_t_, typename callable_t_>
    hxattr_nodiscard auto or_else(
        this self_t_&& self_, const key_t& key_, callable_t_&& callable_)
        -> decltype(self_.end());

    template<typename self_t_, typename callable_t_>
    hxattr_nodiscard auto or_else(
        this self_t_&& self_, const_iterator it_, callable_t_&& callable_)
        -> decltype(self_.end());
#endif // HX_CPLUSPLUS >= 202302L

    void release_all(void);

    hxsize_t release_key(const typename node_t_::key_t& key_);

    hxptr<node_t_, deleter_t_> replace(node_t_* ptr_) noexcept;

    void set_size_bits(hxhash_t bits_);

    hxattr_nodiscard hxsize_t size(void) const { return m_size_; }

    template<hxsystem_allocator_t allocator_=hxsystem_allocator_current,
        hxalignment_t align_=hxalignment, bool multi_=multi_t_, class... args_t_>
    hxenable_if_t<!multi_, iterator> try_emplace(
        const typename node_t_::key_t& key_, args_t_&&... args_) noexcept;
 
#if HX_CPLUSPLUS >= 202302L
    template<typename self_t_> hxattr_nodiscard
    auto value_or(this self_t_&& self_, const key_t& key_, const node_t_* default_value_)
        -> decltype(self_.end());

    template<typename self_t_> hxattr_nodiscard
    auto value_or(this self_t_&& self_, const_iterator it_, const node_t_* default_value_)
        -> decltype(self_.end());
#endif // HX_CPLUSPLUS >= 202302L
 
private:
    static_assert(table_size_bits_ < hxhash_bits, "Hash bits must be [0..hxhash_bits)");
 
    // Deleted for being bug prone.
    hxhash_table(const hxhash_table&) = delete;
 
    hxhash_node_base** get_bucket_head_(hxhash_t hash_);
    const hxhash_node_base*const* get_bucket_head_(hxhash_t hash_) const;
 
    hxsize_t m_size_;
    hxdetail_::hxpow2_allocator_<hxhash_node_base*, table_size_bits_, true> m_table_;
};
 
#include "detail/hxhash_table.inl"
HX_NS_END_