<commit_before>/**
 * MIT License
 * 
 * Copyright (c) 2017 Tessil
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */
#ifndef TSL_HOPSCOTCH_HASH_H
#define TSL_HOPSCOTCH_HASH_H


#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <exception>
#include <functional>
#include <initializer_list>
#include <iterator>
#include <memory>
#include <ratio>
#include <stdexcept>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>

#if (defined(__GNUC__) && (__GNUC__ == 4) && (__GNUC_MINOR__ < 9))
#define TSL_NO_RANGE_ERASE_WITH_CONST_ITERATOR
#endif



/*
 * Only activate tsl_assert if TSL_DEBUG is defined. 
 * This way we avoid the performance hit when NDEBUG is not defined with assert as tsl_assert is used a lot
 * (people usually compile with "-O3" and not "-O3 -DNDEBUG").
 */
#ifndef tsl_assert
    #ifdef TSL_DEBUG
    #define tsl_assert(expr) assert(expr)
    #else
    #define tsl_assert(expr) (static_cast<void>(0))
    #endif
#endif

namespace tsl {

/**
 * Grow the map by a factor of two keeping bucket_count to a power of two. It allows
 * the map to use a mask operation instead of a modulo operation to map a hash to a bucket.
 */
class power_of_two_growth_policy {
public:
    /**
     * Called on map creation and rehash. The number of buckets requested is passed by parameter.
     * This number is a minimum, the policy may update this value with a higher value if needed.
     */
    power_of_two_growth_policy(std::size_t& min_bucket_count_in_out) {
        const std::size_t min_bucket_count = MIN_BUCKETS_SIZE;
        
        min_bucket_count_in_out = std::max(min_bucket_count, min_bucket_count_in_out);
        min_bucket_count_in_out = round_up_to_power_of_two(min_bucket_count_in_out);
        m_mask = min_bucket_count_in_out - 1;
    }
    
    /**
     * Return the bucket [0, bucket_count()) to which the hash belongs.
     */
    std::size_t bucket_for_hash(std::size_t hash) const {
        return hash & m_mask;
    }
    
    /**
     * Return the bucket count to uses when the bucket array grows on rehash.
     */
    std::size_t next_bucket_count() const {
        return (m_mask + 1) * 2;
    }
    
private:    
    // TODO could be faster
    static std::size_t round_up_to_power_of_two(std::size_t value) {
        if(is_power_of_two(value)) {
            return value;
        }
        
        std::size_t power = 1;
        while(power < value) {
            power <<= 1;
        }
        
        return power;
    }
    
    static constexpr bool is_power_of_two(std::size_t value) {
        return value != 0 && (value & (value - 1)) == 0;
    }    
private:
    static const std::size_t MIN_BUCKETS_SIZE = 2;
    
    std::size_t m_mask;
};

/**
 * Grow the map by GrowthFactor::num/GrowthFactor::den and use a modulo to map a hash
 * to a bucket. Slower but it can be usefull if you want a slower growth.
 */
template<class GrowthFactor = std::ratio<3, 2>>
class mod_growth_policy {
public:
    mod_growth_policy(std::size_t& min_bucket_count_in_out) {
        const std::size_t min_bucket_count = MIN_BUCKETS_SIZE;
        
        min_bucket_count_in_out = std::max(min_bucket_count, min_bucket_count_in_out);
        m_bucket_count = min_bucket_count_in_out;
    }
    
    std::size_t bucket_for_hash(std::size_t hash) const {
        tsl_assert(m_bucket_count != 0);
        return hash % m_bucket_count;
    }
    
    std::size_t next_bucket_count() const {
        return static_cast<std::size_t>(
                    std::ceil(static_cast<double>(m_bucket_count) * REHASH_SIZE_MULTIPLICATION_FACTOR));
    }
    
private:
    static const std::size_t MIN_BUCKETS_SIZE = 2;
    static constexpr double REHASH_SIZE_MULTIPLICATION_FACTOR = 1.0*GrowthFactor::num/GrowthFactor::den;
    static_assert(REHASH_SIZE_MULTIPLICATION_FACTOR >= 1.1, "Grow factor should be >= 1.1.");
    
    std::size_t m_bucket_count;
};



namespace detail_hopscotch_hash {

static constexpr const std::array<std::size_t, 38> PRIMES = {{
    17ul, 29ul, 37ul, 53ul, 67ul, 79ul, 97ul, 131ul, 193ul, 257ul, 389ul, 521ul, 769ul, 1031ul, 1543ul, 2053ul, 
    3079ul, 6151ul, 12289ul, 24593ul, 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, 1572869ul, 3145739ul, 
    6291469ul, 12582917ul, 25165843ul, 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul, 
    1610612741ul, 3221225473ul, 4294967291ul
}};

template<unsigned int IPrime>
static std::size_t mod(std::size_t hash) { return hash % PRIMES[IPrime]; }

// MOD_PRIME[iprime](hash) returns hash % PRIMES[iprime]. This table allows for faster modulo as the
// compiler can optimize the modulo code better with a constant known at the compilation.
static constexpr const std::array<std::size_t(*)(std::size_t), 38> MOD_PRIME = {{ 
    &mod<0>, &mod<1>, &mod<2>, &mod<3>, &mod<4>, &mod<5>, &mod<6>, &mod<7>, &mod<8>, &mod<9>, &mod<10>, 
    &mod<11>, &mod<12>, &mod<13>, &mod<14>, &mod<15>, &mod<16>, &mod<17>, &mod<18>, &mod<19>, &mod<20>, 
    &mod<21>, &mod<22>, &mod<23>, &mod<24>, &mod<25>, &mod<26>, &mod<27>, &mod<28>, &mod<29>, &mod<30>, 
    &mod<31>, &mod<32>, &mod<33>, &mod<34>, &mod<35>, &mod<36>, &mod<37> 
}};

}

/**
 * Grow the map by using prime numbers as size. Slower than tsl::power_of_two_growth_policy in general 
 * but will probably distribute the values around better in the buckets with a poor hash function.
 */
class prime_growth_policy {
public:
    prime_growth_policy(std::size_t& min_bucket_count_in_out) {
        auto it_prime = std::lower_bound(tsl::detail_hopscotch_hash::PRIMES.begin(), 
                                         tsl::detail_hopscotch_hash::PRIMES.end(), min_bucket_count_in_out);
        if(it_prime == tsl::detail_hopscotch_hash::PRIMES.end()) {
            throw std::length_error("The map exceeds its maxmimum size.");
        }
        
        m_iprime = static_cast<unsigned int>(std::distance(tsl::detail_hopscotch_hash::PRIMES.begin(), it_prime));
        min_bucket_count_in_out = *it_prime;
    }
    
    std::size_t bucket_for_hash(std::size_t hash) const {
        return bucket_for_hash_iprime(hash, m_iprime);
    }
    
    std::size_t next_bucket_count() const {
        if(m_iprime + 1 >= tsl::detail_hopscotch_hash::PRIMES.size()) {
            throw std::length_error("The map exceeds its maxmimum size.");
        }
        
        return tsl::detail_hopscotch_hash::PRIMES[m_iprime + 1];
    }   
    
private:  
    std::size_t bucket_for_hash_iprime(std::size_t hash, unsigned int iprime) const {
        tsl_assert(iprime < tsl::detail_hopscotch_hash::MOD_PRIME.size());
        return tsl::detail_hopscotch_hash::MOD_PRIME[iprime](hash);
    }
    
private:
    unsigned int m_iprime;
};


namespace detail_hopscotch_hash {
    
    
    
template<typename T>
struct make_void {
    using type = void;
};


template<typename T, typename = void>
struct has_is_transparent : std::false_type {
};

template<typename T>
struct has_is_transparent<T, typename make_void<typename T::is_transparent>::type> : std::true_type {
};

template<typename T, typename = void>
struct has_key_compare : std::false_type {
};

template<typename T>
struct has_key_compare<T, typename make_void<typename T::key_compare>::type> : std::true_type {
};





/*
 * smallest_type_for_min_bits::type returns the smallest type that can fit MinBits.
 */
static const size_t SMALLEST_TYPE_MAX_BITS_SUPPORTED = 64;
template<unsigned int MinBits, typename Enable = void>
class smallest_type_for_min_bits {
};

template<unsigned int MinBits>
class smallest_type_for_min_bits<MinBits, typename std::enable_if<(MinBits > 0) && (MinBits <= 8)>::type> {
public:
    using type = std::uint8_t;
};

template<unsigned int MinBits>
class smallest_type_for_min_bits<MinBits, typename std::enable_if<(MinBits > 8) && (MinBits <= 16)>::type> {
public:
    using type = std::uint16_t;
};

template<unsigned int MinBits>
class smallest_type_for_min_bits<MinBits, typename std::enable_if<(MinBits > 16) && (MinBits <= 32)>::type> {
public:
    using type = std::uint32_t;
};

template<unsigned int MinBits>
class smallest_type_for_min_bits<MinBits, typename std::enable_if<(MinBits > 32) && (MinBits <= 64)>::type> {
public:
    using type = std::uint64_t;
};
        


/*
 * Each bucket may store up to three elements:
 * - An aligned storage to store a value_type object with placement-new.
 * - An (optional) hash of the value in the bucket.
 * - An unsigned integer of type neighborhood_bitmap used to tell us which buckets in the neighborhood of the 
 *   current bucket contain a value with a hash belonging to the current bucket. 
 * 
 * For a bucket 'b' a bit 'i' (counting from 0 and from the least significant bit to the most significant) 
 * set to 1 means that the bucket 'b+i' contains a value with a hash belonging to bucket 'b'.
 * The bits used for that, start from the third least significant bit.
 * 
 * The least significant bit is set to 1 if there is a value in the bucket storage.
 * The second least significant bit is set to 1 if there is an overflow. More than NeighborhoodSize values 
 * give the same hash, all overflow values are stored in the m_overflow_elements list of the map.
 */
static const size_t NB_RESERVED_BITS_IN_NEIGHBORHOOD = 2; 


template<bool StoreHash>
class hopscotch_bucket_hash {
public:    
    using hash_type = std::false_type;
    
    bool bucket_hash_equal(std::size_t /*hash*/) const {
        return true;
    }
    
    std::size_t truncated_bucket_hash() const {
        assert(false);
        return 0;
    }<commit_msg>Replace size_t with std::size_t.<commit_after>/**
 * MIT License
 * 
 * Copyright (c) 2017 Tessil
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */
#ifndef TSL_HOPSCOTCH_HASH_H
#define TSL_HOPSCOTCH_HASH_H


#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <exception>
#include <functional>
#include <initializer_list>
#include <iterator>
#include <memory>
#include <ratio>
#include <stdexcept>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>

#if (defined(__GNUC__) && (__GNUC__ == 4) && (__GNUC_MINOR__ < 9))
#define TSL_NO_RANGE_ERASE_WITH_CONST_ITERATOR
#endif



/*
 * Only activate tsl_assert if TSL_DEBUG is defined. 
 * This way we avoid the performance hit when NDEBUG is not defined with assert as tsl_assert is used a lot
 * (people usually compile with "-O3" and not "-O3 -DNDEBUG").
 */
#ifndef tsl_assert
    #ifdef TSL_DEBUG
    #define tsl_assert(expr) assert(expr)
    #else
    #define tsl_assert(expr) (static_cast<void>(0))
    #endif
#endif

namespace tsl {

/**
 * Grow the map by a factor of two keeping bucket_count to a power of two. It allows
 * the map to use a mask operation instead of a modulo operation to map a hash to a bucket.
 */
class power_of_two_growth_policy {
public:
    /**
     * Called on map creation and rehash. The number of buckets requested is passed by parameter.
     * This number is a minimum, the policy may update this value with a higher value if needed.
     */
    power_of_two_growth_policy(std::size_t& min_bucket_count_in_out) {
        const std::size_t min_bucket_count = MIN_BUCKETS_SIZE;
        
        min_bucket_count_in_out = std::max(min_bucket_count, min_bucket_count_in_out);
        min_bucket_count_in_out = round_up_to_power_of_two(min_bucket_count_in_out);
        m_mask = min_bucket_count_in_out - 1;
    }
    
    /**
     * Return the bucket [0, bucket_count()) to which the hash belongs.
     */
    std::size_t bucket_for_hash(std::size_t hash) const {
        return hash & m_mask;
    }
    
    /**
     * Return the bucket count to uses when the bucket array grows on rehash.
     */
    std::size_t next_bucket_count() const {
        return (m_mask + 1) * 2;
    }
    
private:    
    // TODO could be faster
    static std::size_t round_up_to_power_of_two(std::size_t value) {
        if(is_power_of_two(value)) {
            return value;
        }
        
        std::size_t power = 1;
        while(power < value) {
            power <<= 1;
        }
        
        return power;
    }
    
    static constexpr bool is_power_of_two(std::size_t value) {
        return value != 0 && (value & (value - 1)) == 0;
    }    
private:
    static const std::size_t MIN_BUCKETS_SIZE = 2;
    
    std::size_t m_mask;
};

/**
 * Grow the map by GrowthFactor::num/GrowthFactor::den and use a modulo to map a hash
 * to a bucket. Slower but it can be usefull if you want a slower growth.
 */
template<class GrowthFactor = std::ratio<3, 2>>
class mod_growth_policy {
public:
    mod_growth_policy(std::size_t& min_bucket_count_in_out) {
        const std::size_t min_bucket_count = MIN_BUCKETS_SIZE;
        
        min_bucket_count_in_out = std::max(min_bucket_count, min_bucket_count_in_out);
        m_bucket_count = min_bucket_count_in_out;
    }
    
    std::size_t bucket_for_hash(std::size_t hash) const {
        tsl_assert(m_bucket_count != 0);
        return hash % m_bucket_count;
    }
    
    std::size_t next_bucket_count() const {
        return static_cast<std::size_t>(
                    std::ceil(static_cast<double>(m_bucket_count) * REHASH_SIZE_MULTIPLICATION_FACTOR));
    }
    
private:
    static const std::size_t MIN_BUCKETS_SIZE = 2;
    static constexpr double REHASH_SIZE_MULTIPLICATION_FACTOR = 1.0*GrowthFactor::num/GrowthFactor::den;
    static_assert(REHASH_SIZE_MULTIPLICATION_FACTOR >= 1.1, "Grow factor should be >= 1.1.");
    
    std::size_t m_bucket_count;
};



namespace detail_hopscotch_hash {

static constexpr const std::array<std::size_t, 38> PRIMES = {{
    17ul, 29ul, 37ul, 53ul, 67ul, 79ul, 97ul, 131ul, 193ul, 257ul, 389ul, 521ul, 769ul, 1031ul, 1543ul, 2053ul, 
    3079ul, 6151ul, 12289ul, 24593ul, 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, 1572869ul, 3145739ul, 
    6291469ul, 12582917ul, 25165843ul, 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul, 
    1610612741ul, 3221225473ul, 4294967291ul
}};

template<unsigned int IPrime>
static std::size_t mod(std::size_t hash) { return hash % PRIMES[IPrime]; }

// MOD_PRIME[iprime](hash) returns hash % PRIMES[iprime]. This table allows for faster modulo as the
// compiler can optimize the modulo code better with a constant known at the compilation.
static constexpr const std::array<std::size_t(*)(std::size_t), 38> MOD_PRIME = {{ 
    &mod<0>, &mod<1>, &mod<2>, &mod<3>, &mod<4>, &mod<5>, &mod<6>, &mod<7>, &mod<8>, &mod<9>, &mod<10>, 
    &mod<11>, &mod<12>, &mod<13>, &mod<14>, &mod<15>, &mod<16>, &mod<17>, &mod<18>, &mod<19>, &mod<20>, 
    &mod<21>, &mod<22>, &mod<23>, &mod<24>, &mod<25>, &mod<26>, &mod<27>, &mod<28>, &mod<29>, &mod<30>, 
    &mod<31>, &mod<32>, &mod<33>, &mod<34>, &mod<35>, &mod<36>, &mod<37> 
}};

}

/**
 * Grow the map by using prime numbers as size. Slower than tsl::power_of_two_growth_policy in general 
 * but will probably distribute the values around better in the buckets with a poor hash function.
 */
class prime_growth_policy {
public:
    prime_growth_policy(std::size_t& min_bucket_count_in_out) {
        auto it_prime = std::lower_bound(tsl::detail_hopscotch_hash::PRIMES.begin(), 
                                         tsl::detail_hopscotch_hash::PRIMES.end(), min_bucket_count_in_out);
        if(it_prime == tsl::detail_hopscotch_hash::PRIMES.end()) {
            throw std::length_error("The map exceeds its maxmimum size.");
        }
        
        m_iprime = static_cast<unsigned int>(std::distance(tsl::detail_hopscotch_hash::PRIMES.begin(), it_prime));
        min_bucket_count_in_out = *it_prime;
    }
    
    std::size_t bucket_for_hash(std::size_t hash) const {
        return bucket_for_hash_iprime(hash, m_iprime);
    }
    
    std::size_t next_bucket_count() const {
        if(m_iprime + 1 >= tsl::detail_hopscotch_hash::PRIMES.size()) {
            throw std::length_error("The map exceeds its maxmimum size.");
        }
        
        return tsl::detail_hopscotch_hash::PRIMES[m_iprime + 1];
    }   
    
private:  
    std::size_t bucket_for_hash_iprime(std::size_t hash, unsigned int iprime) const {
        tsl_assert(iprime < tsl::detail_hopscotch_hash::MOD_PRIME.size());
        return tsl::detail_hopscotch_hash::MOD_PRIME[iprime](hash);
    }
    
private:
    unsigned int m_iprime;
};


namespace detail_hopscotch_hash {
    
    
    
template<typename T>
struct make_void {
    using type = void;
};


template<typename T, typename = void>
struct has_is_transparent : std::false_type {
};

template<typename T>
struct has_is_transparent<T, typename make_void<typename T::is_transparent>::type> : std::true_type {
};

template<typename T, typename = void>
struct has_key_compare : std::false_type {
};

template<typename T>
struct has_key_compare<T, typename make_void<typename T::key_compare>::type> : std::true_type {
};





/*
 * smallest_type_for_min_bits::type returns the smallest type that can fit MinBits.
 */
static const size_t SMALLEST_TYPE_MAX_BITS_SUPPORTED = 64;
template<unsigned int MinBits, typename Enable = void>
class smallest_type_for_min_bits {
};

template<unsigned int MinBits>
class smallest_type_for_min_bits<MinBits, typename std::enable_if<(MinBits > 0) && (MinBits <= 8)>::type> {
public:
    using type = std::uint8_t;
};

template<unsigned int MinBits>
class smallest_type_for_min_bits<MinBits, typename std::enable_if<(MinBits > 8) && (MinBits <= 16)>::type> {
public:
    using type = std::uint16_t;
};

template<unsigned int MinBits>
class smallest_type_for_min_bits<MinBits, typename std::enable_if<(MinBits > 16) && (MinBits <= 32)>::type> {
public:
    using type = std::uint32_t;
};

template<unsigned int MinBits>
class smallest_type_for_min_bits<MinBits, typename std::enable_if<(MinBits > 32) && (MinBits <= 64)>::type> {
public:
    using type = std::uint64_t;
};
        


/*
 * Each bucket may store up to three elements:
 * - An aligned storage to store a value_type object with placement-new.
 * - An (optional) hash of the value in the bucket.
 * - An unsigned integer of type neighborhood_bitmap used to tell us which buckets in the neighborhood of the 
 *   current bucket contain a value with a hash belonging to the current bucket. 
 * 
 * For a bucket 'b' a bit 'i' (counting from 0 and from the least significant bit to the most significant) 
 * set to 1 means that the bucket 'b+i' contains a value with a hash belonging to bucket 'b'.
 * The bits used for that, start from the third least significant bit.
 * 
 * The least significant bit is set to 1 if there is a value in the bucket storage.
 * The second least significant bit is set to 1 if there is an overflow. More than NeighborhoodSize values 
 * give the same hash, all overflow values are stored in the m_overflow_elements list of the map.
 */
static const std::size_t NB_RESERVED_BITS_IN_NEIGHBORHOOD = 2; 


template<bool StoreHash>
class hopscotch_bucket_hash {
public:    
    using hash_type = std::false_type;
    
    bool bucket_hash_equal(std::size_t /*hash*/) const {
        return true;
    }
    
    std::size_t truncated_bucket_hash() const {
        assert(false);
        return 0;
    }
{'fraction_non_alphanumeric': 0.10514698976237438, 'fraction_numerical': 0.030994646379261765, 'mean_word_length': 3.729069509216078, 'pattern_counts': {'":': 0, '<': 195, '<?xml version=': 0, '>': 191, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2445162', 'n_tokens_mistral': 7646, 'n_tokens_neox': 6992, 'n_words': 2067}