hxkey.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 "hxutility.h"
 
HX_NS_BEGIN_

// UTF-8 string detection. Does not match signed/unsigned char.
template<typename T_> struct hxis_string_ : public hxfalse_t { };
template<> struct hxis_string_<char*> : public hxtrue_t { };
template<> struct hxis_string_<const char*> : public hxtrue_t { };
template<> struct hxis_string_<volatile char*> : public hxtrue_t { };
template<> struct hxis_string_<const volatile char*> : public hxtrue_t { };
template<size_t size_> struct hxis_string_<char[size_]> : public hxtrue_t { };
template<size_t size_> struct hxis_string_<const char[size_]> : public hxtrue_t { };
template<size_t size_> struct hxis_string_<volatile char[size_]> : public hxtrue_t { };
template<size_t size_> struct hxis_string_<const volatile char[size_]> : public hxtrue_t { };
template<> struct hxis_string_<char[]> : public hxtrue_t { };
template<> struct hxis_string_<const char[]> : public hxtrue_t { };
template<> struct hxis_string_<volatile char[]> : public hxtrue_t { };
template<> struct hxis_string_<const volatile char[]> : public hxtrue_t { };

template<typename T_>
hxattr_nodiscard constexpr hxinline
bool hxis_string(void) {
    return hxis_string_<hxremove_cvref_t<T_>>::value;
}

template<typename T_=void, typename enabled_t=void>
class hxkey_equal_t {
public:
    template<typename A_, typename B_>
    hxattr_nodiscard hxinline hxconstexpr hxattr_flatten
    bool operator()(const A_& a_, const B_& b_) const { return a_ == b_; }
};

template<typename T_>
class hxkey_equal_t<T_, hxenable_if_t<hxis_string<T_>()>> {
public:
    hxattr_nodiscard hxinline bool operator()(const volatile char* a_, const volatile char* b_) const {
        return ::strcmp(const_cast<const char*>(a_), const_cast<const char*>(b_)) == 0;
    }
};

template<typename A_, typename B_>
hxattr_nodiscard hxinline hxconstexpr hxattr_flatten
bool hxkey_equal(const A_& a_, const B_& b_) {
    return hxkey_equal_t<A_>{}(a_, b_);
}

template<typename T_=void, typename enabled_t=void>
class hxkey_less_t {
public:
    template<typename A_, typename B_>
    hxattr_nodiscard hxinline hxconstexpr hxattr_flatten
    bool operator()(const A_& a_, const B_& b_) const { return a_ < b_; }
};

template<typename T_>
class hxkey_less_t<T_, hxenable_if_t<hxis_string<T_>()>> {
public:
    hxattr_nodiscard hxinline bool operator()(const volatile char* a_, const volatile char* b_) const {
        return ::strcmp(const_cast<const char*>(a_), const_cast<const char*>(b_)) < 0;
    }
};

template<typename A_, typename B_>
hxattr_nodiscard hxinline hxconstexpr hxattr_flatten
bool hxkey_less(const A_& a_, const B_& b_) {
    return hxkey_less_t<A_>{}(a_, b_);
}

// xxhash32 prime constants and avalanche mixing. Useful when hashing sequential
// data. These are used by hxkey_hash_t specializations below.
hxinline_constexpr hxhash_t hxhash_prime1_ = hxhash_t{0x9E3779B1u};
hxinline_constexpr hxhash_t hxhash_prime2_ = hxhash_t{0x85EBCA77u};
hxinline_constexpr hxhash_t hxhash_prime3_ = hxhash_t{0xC2B2AE3Du};
hxinline_constexpr hxhash_t hxhash_prime4_ = hxhash_t{0x27D4EB2Fu};
hxinline_constexpr hxhash_t hxhash_prime5_ = hxhash_t{0x165667B1u};
 
// xxhash32 avalanche: x ^= x >> 15, x *= prime2, x ^= x >> 13, x *= prime3, x ^= x >> 16.
hxattr_nodiscard hxinline hxconstexpr
hxhash_t hxhash_avalanche_(hxhash_t x_) {
    x_ ^= x_ >> 15u;
    x_ *= hxhash_prime2_;
    x_ ^= x_ >> 13u;
    x_ *= hxhash_prime3_;
    x_ ^= x_ >> 16u;
    return x_;
}

template<typename T_, typename enabled_t=void>
class hxkey_hash_t {
public:
    hxattr_nodiscard hxinline hxhash_t operator()(const T_& x_) const {
        // xxhash32 short-input path: seed=0, length=4, single 4-byte word.
        hxhash_t h_ = hxhash_prime5_ + hxhash_t{4u};
        // Did you write a custom hxkey_hash_t specialization?
        h_ += static_cast<hxhash_t>(x_) * hxhash_prime3_;
        h_  = ((h_ << 17u) | (h_ >> 15u)) * hxhash_prime4_;
        return hxhash_avalanche_(h_);
    }
};

template<typename T_>
class hxkey_hash_t<T_, hxenable_if_t<hxis_string<T_>()>> {
public:
    hxattr_nodiscard hxinline hxhash_t operator()(const volatile char* s_) const {
        const char* t_ = const_cast<const char*>(s_);
        hxhash_t h_ = hxhash_prime5_;
        while(*t_ != '\0') {
            h_ += static_cast<hxhash_t>(static_cast<unsigned char>(*t_++)) * hxhash_prime5_;
            h_ = ((h_ << 11u) | (h_ >> 21u)) * hxhash_prime1_;
        }
        return hxhash_avalanche_(h_);
    }
};

template<typename T_>
hxattr_nodiscard hxinline hxattr_flatten hxhash_t hxkey_hash(const T_& x_) {
    return hxkey_hash_t<T_>{}(x_);
}
 
HX_NS_END_