<commit_before>#ifndef hash_map_hh_INCLUDED
#define hash_map_hh_INCLUDED

#include "hash.hh"
#include "memory.hh"
#include "vector.hh"

namespace Kakoune
{

template<typename T>
constexpr void constexpr_swap(T& lhs, T& rhs)
{
    T tmp = std::move(lhs);
    lhs = std::move(rhs);
    rhs = std::move(tmp);
}

template<MemoryDomain domain,
         template<typename, MemoryDomain> class Container>
struct HashIndex
{
    struct Entry
    {
        size_t hash = 0;
        int index = -1;
    };

    static constexpr float max_fill_rate = 0.5f;

    constexpr HashIndex() = default;
    constexpr HashIndex(size_t count)
    {
        const size_t min_size = (size_t)(count / max_fill_rate) + 1;
        size_t new_size = 4;
        while (new_size < min_size)
            new_size *= 2;
        m_entries.resize(new_size, {});
    }

    using ContainerType = Container<Entry, domain>;

    constexpr void resize(size_t new_size)
    {
        kak_assert(new_size > m_entries.size());
        ContainerType old_entries = std::move(m_entries);
        m_entries.resize(new_size, {});
        for (auto& entry : old_entries)
        {
            if (entry.index >= 0)
                add(entry.hash, entry.index);
        }
    }

    constexpr void reserve(size_t count)
    {
        kak_assert(count > 0);
        const size_t min_size = (size_t)(count / max_fill_rate) + 1;
        size_t new_size = m_entries.empty() ? 4 : m_entries.size();
        while (new_size < min_size)
            new_size *= 2;

        if (new_size > m_entries.size())
            resize(new_size);
    }

    constexpr void add(size_t hash, int index)
    {
        Entry entry{hash, index};
        while (true)
        {
            auto target_slot = compute_slot(entry.hash);
            for (auto slot = target_slot; slot < m_entries.size(); ++slot)
            {
                if (m_entries[slot].index == -1)
                {
                    m_entries[slot] = entry;
                    return;
                }

                // Robin hood hashing
                auto candidate_slot = compute_slot(m_entries[slot].hash);
                if (target_slot < candidate_slot)
                {
                    constexpr_swap(m_entries[slot], entry);<commit_msg>HashMap: Tolerate reserving for 0 elements<commit_after>#ifndef hash_map_hh_INCLUDED
#define hash_map_hh_INCLUDED

#include "hash.hh"
#include "memory.hh"
#include "vector.hh"

namespace Kakoune
{

template<typename T>
constexpr void constexpr_swap(T& lhs, T& rhs)
{
    T tmp = std::move(lhs);
    lhs = std::move(rhs);
    rhs = std::move(tmp);
}

template<MemoryDomain domain,
         template<typename, MemoryDomain> class Container>
struct HashIndex
{
    struct Entry
    {
        size_t hash = 0;
        int index = -1;
    };

    static constexpr float max_fill_rate = 0.5f;

    constexpr HashIndex() = default;
    constexpr HashIndex(size_t count)
    {
        const size_t min_size = (size_t)(count / max_fill_rate) + 1;
        size_t new_size = 4;
        while (new_size < min_size)
            new_size *= 2;
        m_entries.resize(new_size, {});
    }

    using ContainerType = Container<Entry, domain>;

    constexpr void resize(size_t new_size)
    {
        kak_assert(new_size > m_entries.size());
        ContainerType old_entries = std::move(m_entries);
        m_entries.resize(new_size, {});
        for (auto& entry : old_entries)
        {
            if (entry.index >= 0)
                add(entry.hash, entry.index);
        }
    }

    constexpr void reserve(size_t count)
    {
        if (count == 0)
            return;

        const size_t min_size = (size_t)(count / max_fill_rate) + 1;
        size_t new_size = m_entries.empty() ? 4 : m_entries.size();
        while (new_size < min_size)
            new_size *= 2;

        if (new_size > m_entries.size())
            resize(new_size);
    }

    constexpr void add(size_t hash, int index)
    {
        Entry entry{hash, index};
        while (true)
        {
            auto target_slot = compute_slot(entry.hash);
            for (auto slot = target_slot; slot < m_entries.size(); ++slot)
            {
                if (m_entries[slot].index == -1)
                {
                    m_entries[slot] = entry;
                    return;
                }

                // Robin hood hashing
                auto candidate_slot = compute_slot(m_entries[slot].hash);
                if (target_slot < candidate_slot)
                {
                    constexpr_swap(m_entries[slot], entry);
{'fraction_non_alphanumeric': 0.10680674108119939, 'fraction_numerical': 0.005909389363099146, 'mean_word_length': 1.9313662604233484, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 18, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6838114', 'n_tokens_mistral': 1483, 'n_tokens_neox': 1418, 'n_words': 318}