hash.h

Go to the documentation of this file.

/* *****************************************************************************
 * 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 <https://www.gnu.org/licenses/>.
 * ****************************************************************************/
 
#ifndef HASH_H
#define HASH_H
 
#include "iterators.h"
#include "tdecl.h"
#include "traits.h"
#include "variant.h"
 
#include <climits>
#include <cstdint>
#include <numeric>
#include <string>
#include <unordered_map>
#include <unordered_set>
 
#if KBLIB_USE_CXX17
#  include <optional>
#  include <string_view>
#  include <variant>
#endif
 
namespace kblib {
 
template <typename Integral, typename CharT>
constexpr auto to_bytes_le(Integral ival,
                           CharT (&dest)[sizeof(Integral)]) noexcept -> void {
   static_assert(std::is_integral<CharT>::value and sizeof(CharT) == 1
                     and not std::is_same<CharT, bool>::value,
                 "CharT must be a char-like type.");
   for (int byte = 0; byte != sizeof(Integral); ++byte) {
      dest[byte] = static_cast<CharT>(to_unsigned(ival)
                                      >> to_unsigned(CHAR_BIT * byte));
   }
}
 
template <typename Integral, typename CharT>
constexpr auto to_bytes_be(Integral ival,
                           CharT (&dest)[sizeof(Integral)]) noexcept -> void {
   static_assert(std::is_integral<CharT>::value and sizeof(CharT) == 1
                     and not std::is_same<CharT, bool>::value,
                 "CharT must be a char-like type.");
   for (auto byte : range(sizeof(Integral))) {
      dest[(sizeof(Integral) - 1) - byte]
          = static_cast<CharT>(ival >> (CHAR_BIT * byte));
   }
}
 
template <typename Integral, typename CharT>
constexpr auto to_bytes(Integral val, CharT (&dest)[sizeof(Integral)]) noexcept
    -> void {
   static_assert(std::is_integral<CharT>::value and sizeof(CharT) == 1
                     and not std::is_same<CharT, bool>::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 {
 
   template <typename UInt>
   struct fnv_prime;
 
   template <>
   struct fnv_prime<std::uint32_t>
       : std::integral_constant<std::uint32_t, 16777619ul> {};
   template <>
   struct fnv_prime<std::uint64_t>
       : std::integral_constant<std::uint64_t, 1099511628211ull> {};
 
   template <typename UInt>
   struct fnv_prime {
      KBLIB_CONSTANT_M UInt value = (sizeof(UInt) == sizeof(std::uint64_t)
                                         ? fnv_prime<std::uint64_t>::value
                                         : fnv_prime<std::uint32_t>::value);
   };
 
   template <typename UInt>
   struct fnv_offset;
 
   template <>
   struct fnv_offset<std::uint32_t>
       : std::integral_constant<std::uint32_t, 2166136261ul> {};
   template <>
   struct fnv_offset<std::uint64_t>
       : std::integral_constant<std::uint64_t, 14695981039346656037ull> {};
 
   template <typename UInt>
   struct fnv_offset {
      KBLIB_CONSTANT_M UInt value = (sizeof(UInt) == sizeof(std::uint64_t)
                                         ? fnv_offset<std::uint64_t>::value
                                         : fnv_offset<std::uint32_t>::value);
   };
 
} // namespace fnv
 
template <typename HashInt, typename Span>
KBLIB_NODISCARD constexpr auto FNVa(Span&& s,
                                    HashInt hval
                                    = fnv::fnv_offset<HashInt>::value) noexcept
    -> HashInt {
   static_assert(sizeof(*std::begin(s)) == 1,
                 "Can only hash char-like objects.");
   const HashInt prime = fnv::fnv_prime<HashInt>::value;
   for (auto&& c : s) {
      hval ^= static_cast<HashInt>(static_cast<unsigned char>(c));
      hval *= prime;
   }
   return hval;
}
 
template <typename HashInt, typename CharT, std::size_t N>
KBLIB_NODISCARD constexpr auto FNVa_a(
    const CharT (&s)[N],
    HashInt hval = fnv::fnv_offset<HashInt>::value) noexcept -> HashInt {
   static_assert(sizeof(s[0]) == 1, "Can only hash char-like objects.");
   const HashInt prime = fnv::fnv_prime<HashInt>::value;
   for (auto&& c : s) {
      hval ^= static_cast<HashInt>(static_cast<unsigned char>(c));
      hval *= prime;
   }
   return hval;
}
 
#if KBLIB_USE_CXX17
KBLIB_NODISCARD constexpr auto FNV32a(
    std::string_view s,
    std::uint32_t hval = fnv::fnv_offset<std::uint32_t>::value) noexcept
    -> std::uint32_t {
   const std::uint32_t prime = fnv::fnv_prime<std::uint32_t>::value;
   for (auto&& c : s) {
      hval ^= static_cast<std::uint32_t>(static_cast<unsigned char>(c));
      hval *= prime;
   }
   return hval;
}
#endif
 
template <typename HashInt>
KBLIB_NODISCARD constexpr auto FNVa_s(
    const char* begin, std::size_t length,
    HashInt hval = fnv::fnv_offset<HashInt>::value) noexcept -> HashInt {
   const HashInt prime = fnv::fnv_prime<HashInt>::value;
   //  for (const char* pos = begin; pos != begin + length; ++pos) {
   //    hval ^= static_cast<HashInt>(static_cast<unsigned char>(*pos));
   //    hval *= prime;
   //  }
   for (const char* pos : range(begin, begin + length)) {
      hval ^= static_cast<HashInt>(static_cast<unsigned char>(*pos));
      hval *= prime;
   }
   return hval;
}
 
template <std::size_t N>
KBLIB_NODISCARD constexpr auto FNV32a_a(
    const char (&s)[N],
    std::uint32_t hval = fnv::fnv_offset<std::uint32_t>::value) noexcept
    -> std::uint32_t {
   const std::uint32_t prime = fnv::fnv_prime<std::uint32_t>::value;
   for (auto&& c : s) {
      hval ^= static_cast<std::uint32_t>(static_cast<unsigned char>(c));
      hval *= prime;
   }
   return hval;
}
 
KBLIB_NODISCARD constexpr auto FNV32a_s(
    const char* begin, std::size_t length,
    uint32_t hval = fnv::fnv_offset<std::uint32_t>::value) noexcept
    -> std::uint32_t {
   const std::uint32_t prime = fnv::fnv_prime<std::uint32_t>::value;
   for (const char* pos = begin; pos != begin + length; ++pos) {
      hval ^= static_cast<std::uint32_t>(static_cast<unsigned char>(*pos));
      hval *= prime;
   }
   return hval;
}
 
inline namespace literals {
   KBLIB_NODISCARD constexpr auto operator""_fnv32(const char* str,
                                                   std::size_t length) noexcept
       -> std::uint32_t {
      return FNVa_s<std::uint32_t>(str, length);
   }
 
   KBLIB_NODISCARD constexpr auto operator""_fnv64(const char* str,
                                                   std::size_t length) noexcept
       -> std::uint64_t {
      return FNVa_s<std::uint64_t>(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<std::uint32_t>(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<std::uint64_t>(bytes);
   }
 
} // namespace literals
 
template <typename T>
struct padding_bits
    : std::integral_constant<int, CHAR_BIT * sizeof(T)
                                      - std::numeric_limits<T>::digits
                                      - std::numeric_limits<T>::is_signed> {};
 
template <typename T>
constexpr int padding_bits_v = padding_bits<T>::value;
 
template <typename Key = void, typename HashInt = std::size_t, typename = void>
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 <typename Key, typename = void>
struct is_hashable : std::false_type {};
 
template <typename Key>
struct is_hashable<Key, void_if_t<std::is_constructible<FNV_hash<Key>>::value>>
    : std::true_type {};
 
template <typename Key>
KBLIB_CONSTANT_V is_hashable_v = is_hashable<Key>::value;
 
template <typename Key>
using FNV32_hash = FNV_hash<Key, std::uint32_t>;
 
template <typename HashInt>
struct FNV_hash<bool, HashInt, void> {
   KBLIB_NODISCARD constexpr auto operator()(
       bool key, HashInt offset
                 = fnv::fnv_offset<HashInt>::value) const noexcept -> HashInt {
      char tmp[1] = {key};
      return FNVa_a(tmp, offset);
   }
};
 
template <typename HashInt>
struct FNV_hash<char, HashInt, void> {
   KBLIB_NODISCARD constexpr auto operator()(
       char key, HashInt offset
                 = fnv::fnv_offset<HashInt>::value) const noexcept -> HashInt {
      char tmp[1] = {key};
      return FNVa_a(tmp, offset);
   }
};
 
template <typename HashInt>
struct FNV_hash<signed char, HashInt, void> {
   KBLIB_NODISCARD constexpr auto operator()(
       signed char key,
       HashInt offset = fnv::fnv_offset<HashInt>::value) const noexcept
       -> HashInt {
      signed char tmp[1] = {key};
      return FNVa_a(tmp, offset);
   }
};
 
template <typename HashInt>
struct FNV_hash<unsigned char, HashInt, void> {
   KBLIB_NODISCARD constexpr auto operator()(
       unsigned char key,
       HashInt offset = fnv::fnv_offset<HashInt>::value) const noexcept
       -> HashInt {
      unsigned char tmp[1] = {key};
      return FNVa_a(tmp, offset);
   }
};
 
template <typename T, typename HashInt>
struct FNV_hash<T, HashInt, void_if_t<std::is_empty<T>::value>> {
   KBLIB_NODISCARD constexpr auto operator()(
       const T&, HashInt offset
                 = fnv::fnv_offset<HashInt>::value) const noexcept -> HashInt {
      return FNVa_a("", offset); // hashes the null terminator
   }
};
 
#if __cpp_lib_has_unique_object_representations
template <typename T>
KBLIB_CONSTANT_V is_trivially_hashable_v
    = (std::is_trivially_copyable_v<
           T> and std::has_unique_object_representations_v<T> and not std::is_empty<T>::value);
#else
template <typename T>
KBLIB_CONSTANT_V is_trivially_hashable_v
    = (std::is_integral<T>::value and padding_bits<T>::value == 0)
      or std::is_pointer<T>::value or std::is_member_object_pointer<T>::value
      or std::is_member_function_pointer<T>::value;
#endif
template <typename T>
struct is_trivially_hashable : bool_constant<is_trivially_hashable_v<T>> {};
 
template <typename T, typename HashInt>
struct FNV_hash<
    T, HashInt,
    void_if_t<std::is_integral<T>::value and is_trivially_hashable_v<T>>> {
   KBLIB_NODISCARD constexpr auto operator()(
       T key, HashInt offset = fnv::fnv_offset<HashInt>::value) const noexcept
       -> HashInt {
      unsigned char tmp[sizeof(T)]{};
      to_bytes(key, tmp);
      return FNVa_a(tmp, offset);
   }
};
 
// uses std::is_pointer instead of just specializing on T* for cv pointers
template <typename T, typename HashInt>
struct FNV_hash<T, HashInt, void_if_t<std::is_pointer<T>::value>> {
   KBLIB_NODISCARD auto operator()(
       T key_in, HashInt offset
                 = fnv::fnv_offset<HashInt>::value) const noexcept -> HashInt {
      return FNV_hash<std::uintptr_t, HashInt>{}(
          reinterpret_cast<std::uintptr_t>(key_in), offset);
   }
};
 
template <typename T, typename HashInt>
struct FNV_hash<T, HashInt,
                void_if_t<(std::is_base_of<std::forward_iterator_tag,
                                           typename std::iterator_traits<
                                               T>::iterator_category>::value and
                           not std::is_pointer<T>::value and
                           not is_trivially_hashable_v<T> and
                           std::is_pointer<typename fakestd::invoke_result<
                               decltype(&T::operator->), T>::type>::value)>> {
   KBLIB_NODISCARD auto operator()(
       T key_in, HashInt offset
                 = fnv::fnv_offset<HashInt>::value) const noexcept -> HashInt {
      if (key_in
          == T{}) { // avoid calling to_pointer on a value-initialized iterator
         return FNV_hash<std::uintptr_t, HashInt>{}(0, offset);
      } else {
         return FNV_hash<std::uintptr_t, HashInt>{}(
             reinterpret_cast<std::uintptr_t>(to_pointer(key_in)), offset);
      }
   }
};
 
namespace asserts {
 
   template <typename Container>
   KBLIB_CONSTANT_V is_trivial_container
       = (is_contiguous<Container>::value
          and is_trivially_hashable_v<typename Container::value_type>);
   static_assert(is_trivial_container<std::string>,
                 "kblib bug: std::string should be trivially hashable");
 
} // namespace asserts
 
template <typename Container, typename HashInt>
struct FNV_hash<
    Container, HashInt,
    void_if_t<(
        is_contiguous_v<
            Container> and is_trivially_hashable_v<typename Container::value_type>)>> {
 
   KBLIB_NODISCARD auto hash_fast(const Container& key,
                                  HashInt offset) const noexcept -> HashInt {
      return FNVa_s<HashInt>(reinterpret_cast<const char*>(key.data()),
                             key.size() * sizeof(*key.begin()), offset);
   }
 
   KBLIB_NODISCARD auto operator()(
       const Container& key,
       HashInt offset = fnv::fnv_offset<HashInt>::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<T>{}(e, offset);
         }
      } else {
         return hash_fast(key, offset);
      }
#else
      return hash_fast(key, offset);
#endif
   }
};
 
template <typename T, typename HashInt>
struct FNV_hash<
    T, HashInt,
    void_if_t<not is_contiguous<T>::value and not std::is_integral<T>::value
              and not std::is_pointer<T>::value
              and is_trivially_hashable_v<T>>> {
   KBLIB_NODISCARD KBLIB_CXX20(constexpr) auto operator()(
       T key, HashInt offset = fnv::fnv_offset<HashInt>::value) const noexcept
       -> HashInt {
      char tmp[sizeof(T)];
      std::memcpy(tmp, &key, sizeof(T));
      return FNVa_a(tmp, offset);
   }
};
 
template <typename Container, typename HashInt>
struct FNV_hash<
    Container, HashInt,
    void_if_t<
        value_detected<Container>::value
        and is_hashable_v<
            value_detected_t<Container>> and not hash_detected<Container>::value
        and is_iterable<Container>::value
        and not (is_contiguous<Container>::value
                 and is_trivially_hashable_v<typename Container::value_type>)
        and not is_iterator_v<Container>>> {
   KBLIB_NODISCARD constexpr auto operator()(
       const Container& key,
       HashInt offset = fnv::fnv_offset<HashInt>::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, HashInt>{}(elem, offset_);
                             });
   }
};
 
namespace detail_hash {
 
   template <typename Tuple, typename HashInt, std::size_t I>
   constexpr auto hash_tuple_impl(const Tuple& tuple, HashInt offset,
                                  std::index_sequence<I>) noexcept -> HashInt {
      return FNV_hash<typename std::tuple_element<I, Tuple>::type, HashInt>{}(
          std::get<I>(tuple), offset);
   }
 
   template <typename Tuple, typename HashInt, std::size_t I, std::size_t I2,
             std::size_t... Is>
   constexpr auto hash_tuple_impl(const Tuple& tuple, HashInt offset,
                                  std::index_sequence<I, I2, Is...>) noexcept
       -> HashInt {
      HashInt first_hash
          = FNV_hash<typename std::tuple_element<I, Tuple>::type, HashInt>{}(
              std::get<I>(tuple), offset);
      return hash_tuple_impl(tuple, first_hash,
                             std::index_sequence<I2, Is...>{});
   }
 
#if KBLIB_USE_CXX17
   template <typename Tuple, std::size_t... Is>
   constexpr auto all_hashable_impl(std::index_sequence<Is...>) -> bool {
      return (...
              and is_hashable_v<typename std::tuple_element<Is, Tuple>::type>);
   }
#else
 
   template <typename Tuple, typename IS>
   struct all_hashable_impl_t;
 
   template <typename Tuple, std::size_t I, std::size_t... Is>
   struct all_hashable_impl_t<Tuple, std::index_sequence<I, Is...>>
       : bool_constant<(
             is_hashable_v<
                 typename std::tuple_element<I, Tuple>::
                     type> and all_hashable_impl_t<Tuple, std::index_sequence<Is...>>::value)> {
   };
 
   template <typename Tuple, std::size_t I>
   struct all_hashable_impl_t<Tuple, std::index_sequence<I>>
       : bool_constant<
             is_hashable_v<typename std::tuple_element<I, Tuple>::type>> {};
 
   template <typename Tuple, std::size_t... Is>
   constexpr auto all_hashable_impl(std::index_sequence<Is...>) -> bool {
      return all_hashable_impl_t<Tuple, std::index_sequence<Is...>>::value;
   }
#endif
 
   template <
       typename Tuple,
       typename std::enable_if<(std::tuple_size<Tuple>::value > 0u), int>::type
       = 0>
   constexpr auto all_hashable() -> bool {
      return all_hashable_impl<Tuple>(
          std::make_index_sequence<std::tuple_size<Tuple>::value>{});
   }
 
} // namespace detail_hash
 
template <typename Tuple, typename HashInt>
struct FNV_hash<Tuple, HashInt,
                void_if_t<detail_hash::all_hashable<Tuple>()
                          and not is_trivially_hashable_v<
                              Tuple> and (std::tuple_size<Tuple>::value > 0u)
                          and not is_linear_container_v<Tuple>>> {
   KBLIB_NODISCARD constexpr auto operator()(
       const Tuple& key,
       HashInt offset = fnv::fnv_offset<HashInt>::value) const noexcept
       -> HashInt {
      return detail_hash::hash_tuple_impl(
          key, offset,
          std::make_index_sequence<std::tuple_size<Tuple>::value>{});
   }
};
 
#if KBLIB_USE_CXX17
 
template <typename T, typename HashInt>
struct FNV_hash<std::optional<T>, HashInt, void> {
   KBLIB_NODISCARD constexpr auto operator()(
       const std::optional<T>& key,
       HashInt offset = fnv::fnv_offset<HashInt>::value) const noexcept
       -> HashInt {
      if (key) {
         return FNV_hash<T, HashInt>{}(key.value(), offset);
      } else {
         return FNV_hash<std::nullopt_t, HashInt>{}(std::nullopt, offset);
      }
   }
};
 
template <typename... Ts, typename HashInt>
struct FNV_hash<std::variant<Ts...>, HashInt,
                void_if_t<detail_hash::all_hashable<std::tuple<Ts...>>()>> {
   KBLIB_NODISCARD constexpr auto operator()(
       const std::variant<Ts...>& key,
       HashInt offset = fnv::fnv_offset<HashInt>::value) const noexcept
       -> HashInt {
      // Variant index is hashed alongside the value
      offset = FNV_hash<HashInt>{}(key.index(), offset);
      // visit2_nop does nothing when the variant is valueless_by_exception
      kblib::visit2_nop(key, [&](auto& V) {
         offset = FNV_hash<typename std::remove_reference<decltype(V)>::type,
                           HashInt>{}(V, offset);
      });
      return offset;
   }
};
 
#endif
 
template <typename HashInt>
struct FNV_hash<void, HashInt, void> {
   KBLIB_CONSTANT_MV is_transparent = true;
 
   template <typename T>
   KBLIB_NODISCARD constexpr auto operator()(const T& key,
                                             HashInt offset
                                             = fnv::fnv_offset<HashInt>::value)
       -> enable_if_t<is_hashable_v<T>, HashInt> {
      return FNV_hash<T>{}(key, offset);
   }
};
 
template <typename Key, typename Value>
using hash_map = std::unordered_map<Key, Value, FNV_hash<>, std::equal_to<>>;
template <typename Key, typename Value>
using hash_multimap
    = std::unordered_multimap<Key, Value, FNV_hash<>, std::equal_to<>>;
template <typename T, typename HashInt>
using hash_set = std::unordered_set<T, FNV_hash<>, std::equal_to<>>;
template <typename T, typename HashInt>
using hash_multiset = std::unordered_set<T, FNV_hash<>, std::equal_to<>>;
 
} // namespace kblib
 
#endif // HASH_H