/* *****************************************************************************
* kblib is a general utility library for C++14 and C++17, intended to provide
* performant high-level abstractions and more expressive ways to do simple
* things.
*
* Copyright (c) 2021 killerbee
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see .
* ****************************************************************************/
/**
* @file
* @brief Provides generic facilities for hashing data, and aliases for standard
* unordered containers using the provided hash objects.
*
* @author killerbee
* @date 2019-2021
* @copyright GNU General Public Licence v3.0
*/
#ifndef HASH_H
#define HASH_H
#include "iterators.h"
#include "tdecl.h"
#include "traits.h"
#include "variant.h"
#include
#include
#include
#include
#include
#include
#if KBLIB_USE_CXX17
# include
# include
# include
#endif
namespace KBLIB_NS {
template
constexpr auto to_bytes_le(Integral ival,
CharT (&dest)[sizeof(Integral)]) noexcept -> void {
static_assert(std::is_integral::value and sizeof(CharT) == 1
and not std::is_same::value,
"CharT must be a char-like type.");
for (int byte = 0; byte != sizeof(Integral); ++byte) {
dest[byte] = static_cast(to_unsigned(ival)
>> to_unsigned(CHAR_BIT * byte));
}
}
template
constexpr auto to_bytes_be(Integral ival,
CharT (&dest)[sizeof(Integral)]) noexcept -> void {
static_assert(std::is_integral::value and sizeof(CharT) == 1
and not std::is_same::value,
"CharT must be a char-like type.");
for (auto byte : range(sizeof(Integral))) {
dest[(sizeof(Integral) - 1) - byte]
= static_cast(ival >> (CHAR_BIT * byte));
}
}
template
constexpr auto to_bytes(Integral val, CharT (&dest)[sizeof(Integral)]) noexcept
-> void {
static_assert(std::is_integral::value and sizeof(CharT) == 1
and not std::is_same::value,
"CharT must be a char-like type.");
if (hash_order == endian::little) {
to_bytes_le(val, dest);
} else {
to_bytes_be(val, dest);
}
}
namespace fnv {
/**
* @brief The prime to use for the FNVa hash algorithm, as a type trait.
*/
template
struct fnv_prime;
template <>
struct fnv_prime
: std::integral_constant {};
template <>
struct fnv_prime
: std::integral_constant {};
template
struct fnv_prime {
KBLIB_CONSTANT_M UInt value = (sizeof(UInt) == sizeof(std::uint64_t)
? fnv_prime::value
: fnv_prime::value);
};
/**
* @brief The starting value for the FNVa hash algorithm, as a type trait.
*/
template
struct fnv_offset;
template <>
struct fnv_offset
: std::integral_constant {};
template <>
struct fnv_offset
: std::integral_constant {};
template
struct fnv_offset {
KBLIB_CONSTANT_M UInt value = (sizeof(UInt) == sizeof(std::uint64_t)
? fnv_offset::value
: fnv_offset::value);
};
} // namespace fnv
/**
* @brief A templatized generic FNVa hash function.
*
* @tparam HashInt The unsigned integer type to use as the hash result. Must be
* either std::uint32_t or std::uint64_t.
* @param s The data to hash. Any range-for-iterable span of char-like objects.
* @param hval The initial value for the hash accumulator. Pass in another hash
* value to create a hash of the concatenation of the two ranges.
* @return HashInt The FNVa hash of the input range.
*/
template
KBLIB_NODISCARD constexpr auto FNVa(Span&& s,
HashInt hval
= fnv::fnv_offset::value) noexcept
-> HashInt {
static_assert(sizeof(*std::begin(s)) == 1,
"Can only hash char-like objects.");
const HashInt prime = fnv::fnv_prime::value;
for (auto&& c : s) {
hval ^= static_cast(static_cast(c));
hval *= prime;
}
return hval;
}
/**
* @brief A templatized FNVa hash function, for raw character arrays, such as
* string literals.
*
* @tparam HashInt The unsigned integer type to use as the hash result. Must be
* either std::uint32_t or std::uint64_t.
* @param s The data to hash. A raw array of char-like objects.
* @param hval The initial value for the hash accumulator. Pass in another hash
* value to create a hash of the concatenation of the two ranges.
* @return HashInt The FNVa hash of the input range.
*/
template
KBLIB_NODISCARD constexpr auto FNVa_a(
const CharT (&s)[N],
HashInt hval = fnv::fnv_offset::value) noexcept -> HashInt {
static_assert(sizeof(s[0]) == 1, "Can only hash char-like objects.");
const HashInt prime = fnv::fnv_prime::value;
for (auto&& c : s) {
hval ^= static_cast(static_cast(c));
hval *= prime;
}
return hval;
}
#if KBLIB_USE_CXX17
/**
* @brief A standard FNV32a hash function, for string_views.
*
* @param s The data to hash.
* @param hval The initial value for the hash accumulator. Pass in another hash
* value to create a hash of the concatenation of the two ranges.
* @return std::uint32_t The FNV32a hash of the input range.
*/
KBLIB_NODISCARD constexpr auto FNV32a(
std::string_view s,
std::uint32_t hval = fnv::fnv_offset::value) noexcept
-> std::uint32_t {
const std::uint32_t prime = fnv::fnv_prime::value;
for (auto&& c : s) {
hval ^= static_cast(static_cast(c));
hval *= prime;
}
return hval;
}
#endif
template
KBLIB_NODISCARD constexpr auto FNVa_s(
const char* begin, std::size_t length,
HashInt hval = fnv::fnv_offset::value) noexcept -> HashInt {
const HashInt prime = fnv::fnv_prime::value;
// for (const char* pos = begin; pos != begin + length; ++pos) {
// hval ^= static_cast(static_cast(*pos));
// hval *= prime;
// }
for (const char* pos : range(begin, begin + length)) {
hval ^= static_cast(static_cast(*pos));
hval *= prime;
}
return hval;
}
/**
* @brief A standard FNV32a hash function, for raw character arrays, such as
* string literals.
*
* @param s The data to hash.
* @param hval The initial value for the hash accumulator. Pass in another hash
* value to create a hash of the concatenation of the two ranges.
* @return HashInt The FNV32a hash of the input range.
*/
template
KBLIB_NODISCARD constexpr auto FNV32a_a(
const char (&s)[N],
std::uint32_t hval = fnv::fnv_offset::value) noexcept
-> std::uint32_t {
const std::uint32_t prime = fnv::fnv_prime::value;
for (auto&& c : s) {
hval ^= static_cast(static_cast(c));
hval *= prime;
}
return hval;
}
KBLIB_NODISCARD constexpr auto FNV32a_s(
const char* begin, std::size_t length,
uint32_t hval = fnv::fnv_offset::value) noexcept
-> std::uint32_t {
const std::uint32_t prime = fnv::fnv_prime::value;
for (const char* pos = begin; pos != begin + length; ++pos) {
hval ^= static_cast(static_cast(*pos));
hval *= prime;
}
return hval;
}
inline namespace literals {
/**
* @brief A literal suffix that produces the FNV32a hash of a string literal.
*/
KBLIB_NODISCARD constexpr auto operator""_fnv32(const char* str,
std::size_t length) noexcept
-> std::uint32_t {
return FNVa_s(str, length);
}
/**
* @brief A literal suffix that produces the FNV64a hash of a string literal.
*/
KBLIB_NODISCARD constexpr auto operator""_fnv64(const char* str,
std::size_t length) noexcept
-> std::uint64_t {
return FNVa_s(str, length);
}
// google-runtime-int not relevant here due to standard requirements
KBLIB_NODISCARD constexpr auto operator""_fnv32(unsigned long long val)
-> std::uint32_t {
unsigned char bytes[sizeof(unsigned long long)]{};
to_bytes(val, bytes);
return FNVa_a(bytes);
}
KBLIB_NODISCARD constexpr auto operator""_fnv64(unsigned long long val)
-> std::uint64_t {
unsigned char bytes[sizeof(unsigned long long)]{};
to_bytes(val, bytes);
return FNVa_a(bytes);
}
} // namespace literals
#if KBLIB_USE_CXX17
/**
* @brief Get the number of padding bits in an integral type.
*
*/
template
constexpr int padding_bits_v
= CHAR_BIT * sizeof(T) - std::numeric_limits::digits
- std::numeric_limits::is_signed;
template <>
inline constexpr int padding_bits_v = 0;
template
struct padding_bits : std::integral_constant> {};
#else
/**
* @brief Get the number of padding bits in an integral type.
*
*/
template
struct padding_bits
: std::integral_constant::digits
- std::numeric_limits::is_signed> {};
template <>
struct padding_bits : std::integral_constant {};
template
constexpr int padding_bits_v = padding_bits::value;
#endif
/**
* @brief The primary template has to exist, but not be constructible, in order
* to be compatible with std::hash.
*
*/
template
struct FNV_hash {
FNV_hash() = delete;
FNV_hash(const FNV_hash&) = delete;
FNV_hash(FNV_hash&&) = delete;
FNV_hash& operator=(const FNV_hash&) = delete;
FNV_hash& operator=(FNV_hash&&) = delete;
};
template
struct is_hashable : std::false_type {};
template
struct is_hashable>::value>>
: std::true_type {};
template
KBLIB_CONSTANT_V is_hashable_v = is_hashable::value;
template
using FNV32_hash = FNV_hash;
/**
* @brief Hasher for bool.
*
*/
template
struct FNV_hash {
KBLIB_NODISCARD constexpr auto operator()(
bool key, HashInt offset
= fnv::fnv_offset::value) const noexcept -> HashInt {
char tmp[1] = {key};
return FNVa_a(tmp, offset);
}
};
/**
* @brief Hasher for char
*
*/
template
struct FNV_hash {
KBLIB_NODISCARD constexpr auto operator()(
char key, HashInt offset
= fnv::fnv_offset::value) const noexcept -> HashInt {
char tmp[1] = {key};
return FNVa_a(tmp, offset);
}
};
/**
* @brief Hasher for signed char
*
*/
template
struct FNV_hash {
KBLIB_NODISCARD constexpr auto operator()(
signed char key,
HashInt offset = fnv::fnv_offset::value) const noexcept
-> HashInt {
signed char tmp[1] = {key};
return FNVa_a(tmp, offset);
}
};
/**
* @brief Hasher for unsigned char
*
*/
template
struct FNV_hash {
KBLIB_NODISCARD constexpr auto operator()(
unsigned char key,
HashInt offset = fnv::fnv_offset::value) const noexcept
-> HashInt {
unsigned char tmp[1] = {key};
return FNVa_a(tmp, offset);
}
};
/**
* @brief An empty type is treated as if it were a single null byte.
*/
template
struct FNV_hash::value>> {
KBLIB_NODISCARD constexpr auto operator()(
const T&, HashInt offset
= fnv::fnv_offset::value) const noexcept -> HashInt {
return FNVa_a("", offset); // hashes the null terminator
}
};
#if __cpp_lib_has_unique_object_representations
template
KBLIB_CONSTANT_V is_trivially_hashable_v
= (std::is_trivially_copyable_v<
T> and std::has_unique_object_representations_v);
#else
template
KBLIB_CONSTANT_V is_trivially_hashable_v
= (std::is_integral::value and padding_bits::value == 0)
or std::is_pointer::value or std::is_member_object_pointer::value
or std::is_member_function_pointer::value;
#endif
template
struct is_trivially_hashable : bool_constant> {};
/**
* @brief Hasher for any integral type without padding type not explicitly
* mentioned above.
*
*/
template
struct FNV_hash<
T, HashInt,
void_if_t::value and is_trivially_hashable_v>> {
KBLIB_NODISCARD constexpr auto operator()(
T key, HashInt offset = fnv::fnv_offset::value) const noexcept
-> HashInt {
unsigned char tmp[sizeof(T)]{};
to_bytes(key, tmp);
return FNVa_a(tmp, offset);
}
};
/**
* @brief Hasher for any pointer type.
*
* @note Unfortunately, this specialization cannot be constexpr
*
*/
// uses std::is_pointer instead of just specializing on T* for cv pointers
template
struct FNV_hash::value>> {
KBLIB_NODISCARD auto operator()(
T key_in, HashInt offset
= fnv::fnv_offset::value) const noexcept -> HashInt {
return FNV_hash{}(
reinterpret_cast(key_in), offset);
}
};
/**
* @brief Hasher for any forward iterator type.
*
* @note Unfortunately, this specialization cannot be constexpr.
*
*/
template
struct FNV_hash::iterator_category>::value and
not std::is_pointer::value and
not is_trivially_hashable_v and
std::is_pointer), T>::type>::value)>> {
KBLIB_NODISCARD auto operator()(
T key_in, HashInt offset
= fnv::fnv_offset::value) const noexcept -> HashInt {
if (key_in
== T{}) { // avoid calling to_pointer on a value-initialized iterator
return FNV_hash{}(0, offset);
} else {
return FNV_hash{}(
reinterpret_cast(to_pointer(key_in)), offset);
}
}
};
/**
* @internal
*/
namespace asserts {
template
KBLIB_CONSTANT_V is_trivial_container
= (is_contiguous::value
and is_trivially_hashable_v);
static_assert(is_trivial_container,
"kblib bug: std::string should be trivially hashable");
} // namespace asserts
/**
* @brief Container hasher, for contiguously-stored trivial elements
*
*/
template
struct FNV_hash<
Container, HashInt,
void_if_t<(
is_contiguous_v<
Container> and is_trivially_hashable_v)>> {
KBLIB_NODISCARD auto hash_fast(const Container& key,
HashInt offset) const noexcept -> HashInt {
return FNVa_s(reinterpret_cast(key.data()),
key.size() * sizeof(*key.begin()), offset);
}
KBLIB_NODISCARD constexpr auto operator()(
const Container& key,
HashInt offset = fnv::fnv_offset::value) const noexcept
-> HashInt {
#if KBLIB_USE_CXX20
if (std::is_constant_evaluated()) {
using T = typename Container::value_type;
for (const auto& e : key) {
offset = FNV_hash{}(e, offset);
}
} else {
return hash_fast(key, offset);
}
#else
return hash_fast(key, offset);
#endif
}
};
/**
* @brief Hasher for any non-integral trivially copyable type that has no
* padding.
*
* @note Unfortunately, this specialization cannot be constexpr until C++20
* brings std::bit_cast.
*
*/
template
struct FNV_hash<
T, HashInt,
void_if_t and not std::is_integral::value
and not std::is_pointer::value
and is_trivially_hashable_v>> {
KBLIB_NODISCARD KBLIB_CXX20(constexpr) auto operator()(
T key, HashInt offset = fnv::fnv_offset::value) const noexcept
-> HashInt {
#if KBLIB_USE_CXX20
auto tmp = std::bit_cast>(key);
return FNVa_s(tmp.data(), tmp.size(), offset);
#else
char tmp[sizeof(T)];
std::memcpy(tmp, &key, sizeof(T));
return FNVa_a(tmp, offset);
#endif
}
};
/**
* @brief Container hasher, for non-trivial elements (or non-contiguous storage)
*
*/
template
struct FNV_hash<
Container, HashInt,
void_if_t<
value_detected::value
and is_hashable_v<
value_detected_t> and not hash_detected::value
and is_iterable::value
and not (is_contiguous::value
and is_trivially_hashable_v)
and not is_iterator_v>> {
KBLIB_NODISCARD constexpr auto operator()(
const Container& key,
HashInt offset = fnv::fnv_offset::value) const noexcept
-> HashInt {
using Elem = typename Container::value_type;
return std::accumulate(cbegin(key), cend(key), offset,
[](HashInt offset_, const Elem& elem) {
return FNV_hash{}(elem, offset_);
});
}
};
/**
* @namespace detail_hash
* @internal
*/
namespace detail_hash {
/**
* @brief Hash each element of a tuple. This overload is for tuples of a
* single type, or as the base case for the other overload.
*
* @param tuple
* @param offset
* @return HashInt
*/
template
constexpr auto hash_tuple_impl(const Tuple& tuple, HashInt offset,
std::index_sequence) noexcept -> HashInt {
return FNV_hash::type, HashInt>{}(
std::get(tuple), offset);
}
/**
* @brief Hash each element of a tuple. This overload is for tuples of at
* least 2 elements.
*
* @param tuple
* @param offset
* @return HashInt
*/
template
constexpr auto hash_tuple_impl(const Tuple& tuple, HashInt offset,
std::index_sequence) noexcept
-> HashInt {
HashInt first_hash
= FNV_hash::type, HashInt>{}(
std::get(tuple), offset);
return hash_tuple_impl(tuple, first_hash,
std::index_sequence{});
}
#if KBLIB_USE_CXX17
template
constexpr auto all_hashable_impl(std::index_sequence) -> bool {
return (...
and is_hashable_v::type>);
}
#else
template
struct all_hashable_impl_t;
template
struct all_hashable_impl_t>
: bool_constant<(
is_hashable_v<
typename std::tuple_element::
type> and all_hashable_impl_t>::value)> {
};
template
struct all_hashable_impl_t>
: bool_constant<
is_hashable_v::type>> {};
template
constexpr auto all_hashable_impl(std::index_sequence) -> bool {
return all_hashable_impl_t>::value;
}
#endif
template <
typename Tuple,
typename std::enable_if<(std::tuple_size::value > 0u), int>::type
= 0>
constexpr auto all_hashable() -> bool {
return all_hashable_impl(
std::make_index_sequence::value>{});
}
} // namespace detail_hash
/**
* @brief Tuple-like (but not array-like) type hasher
*
*/
template
struct FNV_hash()
and not is_trivially_hashable_v<
Tuple> and (std::tuple_size::value > 0u)
and not is_linear_container_v>> {
KBLIB_NODISCARD constexpr auto operator()(
const Tuple& key,
HashInt offset = fnv::fnv_offset::value) const noexcept
-> HashInt {
return detail_hash::hash_tuple_impl(
key, offset,
std::make_index_sequence::value>{});
}
};
#if KBLIB_USE_CXX17
template
struct FNV_hash, HashInt, void> {
KBLIB_NODISCARD constexpr auto operator()(
const std::optional& key,
HashInt offset = fnv::fnv_offset::value) const noexcept
-> HashInt {
if (key) {
return FNV_hash{}(key.value(), offset);
} else {
return FNV_hash{}(std::nullopt, offset);
}
}
};
template
struct FNV_hash, HashInt,
void_if_t>()>> {
KBLIB_NODISCARD constexpr auto operator()(
const std::variant& key,
HashInt offset = fnv::fnv_offset::value) const noexcept
-> HashInt {
// Variant index is hashed alongside the value
offset = FNV_hash{}(key.index(), offset);
// visit2_nop does nothing when the variant is valueless_by_exception
kblib::visit2_nop(key, [&](auto& V) {
offset = FNV_hash::type,
HashInt>{}(V, offset);
});
return offset;
}
};
#endif
/**
* @brief Transparent hasher for any hashable type.
*
*/
template
struct FNV_hash {
KBLIB_CONSTANT_MV is_transparent = true;
template
KBLIB_NODISCARD constexpr auto operator()(
const T& key,
HashInt offset = fnv::fnv_offset::value) const noexcept
-> enable_if_t, HashInt> {
return FNV_hash{}(key, offset);
}
};
template
using hash_map = std::unordered_map, std::equal_to<>>;
template
using hash_multimap
= std::unordered_multimap, std::equal_to<>>;
template
using hash_set = std::unordered_set, std::equal_to<>>;
template
using hash_multiset = std::unordered_set, std::equal_to<>>;
} // namespace KBLIB_NS
#endif // HASH_H