hash.hpp

 
#pragma once
 
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <iostream>
#include <map>
#include <optional>
#include <set>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>
 
#include "smats/util/concepts.h"
 
namespace smats {
 
template <InvocableHashAlgorithm HashAlgorithm, Hashable<HashAlgorithm> T>
void hash_append(HashAlgorithm& hasher, const T& hashable) noexcept {
  hashable.hash(hasher);
}
 
void hash_append(InvocableHashAlgorithm auto& hasher, const std::integral auto& item) noexcept {
  hasher(std::addressof(item), sizeof(item));
}
 
template <class T>
void hash_append(InvocableHashAlgorithm auto& hasher, const T* item) noexcept {
  using smats::hash_append;
  hash_append(hasher, reinterpret_cast<std::uintptr_t>(item));
};
 
void hash_append(InvocableHashAlgorithm auto& hasher, const IsEnum auto& item) noexcept {
  using smats::hash_append;
  hasher(std::addressof(item), sizeof(item));
}
 
template <std::floating_point T>
void hash_append(InvocableHashAlgorithm auto& hasher, const T& item) noexcept {
// Hashing a NaN makes no sense, since they cannot compare as equal.
#ifndef NDEBUG
  if (std::isnan(item)) {
    std::cerr << "Hashing a NaN makes no sense, since they cannot compare as equal." << std::endl;
    std::terminate();
  }
#endif
  // +0.0 and -0.0 are equal, so must hash identically.
  if (item == 0.0) {
    const T zero{0.0};
    hasher(std::addressof(zero), sizeof(zero));
  } else {
    hasher(std::addressof(item), sizeof(item));
  }
}
 
template <class Traits, class Allocator>
void hash_append(InvocableHashAlgorithm auto& hasher, const std::basic_string<char, Traits, Allocator>& item) noexcept {
  hasher(item.data(), item.size());
  // All collection types must send their size, after their contents.
  // See the #hash_append_vector anchor in N3980.
  hash_append(hasher, item.size());
}
 
// Prior to this point, we've defined hashers for primitive types and similar kinds of "singular" types,
// where the template arguments form a bounded set.
//
// Following this point, we'll define hashers for types where the template argument can be anything (e.g., collections).
// That means for proper namespace lookups we need to declare them all first, and then define them all second.
 
template <class T1, class T2>
void hash_append(InvocableHashAlgorithm auto& hasher, const std::pair<T1, T2>& item) noexcept;
 
template <class T>
void hash_append(InvocableHashAlgorithm auto& hasher, const std::optional<T>& item) noexcept;
 
template <class T1, class T2, class Compare, class Allocator>
void hash_append(InvocableHashAlgorithm auto& hasher, const std::map<T1, T2, Compare, Allocator>& item) noexcept;
 
template <class Key, class Compare, class Allocator>
void hash_append(InvocableHashAlgorithm auto& hasher, const std::set<Key, Compare, Allocator>& item) noexcept;
 
// Now the templates can be defined
 
template <class T1, class T2>
void hash_append(InvocableHashAlgorithm auto& hasher, const std::pair<T1, T2>& item) noexcept {
  using smats::hash_append;
  hash_append(hasher, item.first);
  hash_append(hasher, item.second);
}
template <class T>
void hash_append(InvocableHashAlgorithm auto& hasher, const std::optional<T>& item) noexcept {
  if (item) {
    hash_append(hasher, *item);
  }
  hash_append(hasher, item.has_value());
};
 
// NOLINTNEXTLINE(runtime/references) Per hash_append convention.
// Provides @ref hash_append for a range, as given by two iterators.
template <class Iter>
void hash_append_range(InvocableHashAlgorithm auto& hasher, Iter begin, Iter end) noexcept {
  using smats::hash_append;
  size_t count{0};
  for (Iter iter = begin; iter != end; ++iter, ++count) {
    hash_append(hasher, *iter);
  }
  // All collection types must send their size, after their contents.
  // See the #hash_append_vector anchor in N3980.
  hash_append(hasher, count);
}
template <class T1, class T2, class Compare, class Allocator>
void hash_append(InvocableHashAlgorithm auto& hasher, const std::map<T1, T2, Compare, Allocator>& item) noexcept {
  return hash_append_range(hasher, item.begin(), item.end());
};
template <class Key, class Compare, class Allocator>
void hash_append(InvocableHashAlgorithm auto& hasher, const std::set<Key, Compare, Allocator>& item) noexcept {
  return hash_append_range(hasher, item.begin(), item.end());
};
 
template <class HashAlgorithm>
struct uhash {
  using result_type = typename HashAlgorithm::result_type;
 
  template <class T>
  result_type operator()(const T& item) const noexcept {
    HashAlgorithm hasher;
    using smats::hash_append;
    hash_append(hasher, item);
    return static_cast<result_type>(hasher);
  }
};
 
namespace hash {
class FNV1a {
 public:
  using result_type = size_t;
 
  void operator()(const void* data, const size_t length) noexcept {
    const auto* const begin = static_cast<const uint8_t*>(data);
    const uint8_t* const end = begin + length;
    for (const uint8_t* iter = begin; iter < end; ++iter) {
      hash_ = (hash_ ^ *iter) * k_fnv_prime;
    }
  }
 
  constexpr void add_byte(const uint8_t byte) noexcept { hash_ = (hash_ ^ byte) * k_fnv_prime; }
 
  explicit constexpr operator size_t() const noexcept { return hash_; }
 
 private:
  static_assert(sizeof(result_type) == (64 / 8), "We require a 64-bit size_t");
  result_type hash_{0xcbf29ce484222325u};                
  static constexpr size_t k_fnv_prime = 1099511628211u;  
};
}  // namespace hash
 
using DefaultHashAlgorithm = hash::FNV1a;                
using DefaultHash = smats::uhash<DefaultHashAlgorithm>;  
 
struct DelegatingHasher {
  using Func = std::function<void(const void*, size_t)>;
  using result_type = typename DefaultHashAlgorithm::result_type;  
 
  explicit DelegatingHasher(Func func) : func_(std::move(func)) {
    if (!static_cast<bool>(func_)) throw std::runtime_error("The function must be non-empty");
  }
  void operator()(const void* data, size_t length) noexcept { func_(data, length); }
  operator result_type() noexcept { std::terminate(); }
 
 private:
  const Func func_;  
};
 
}  // namespace smats