hash_utils.hpp

Go to the documentation of this file.

 
#ifndef __BOXES_HASH_UTILS_HPP__
#define __BOXES_HASH_UTILS_HPP__
 
#include "compiler.hpp"
 
#include <concepts>
#include <cstdint>
#include <random>
#include <set>
#include <string>
#include <vector>
 
namespace boxes::hash {
 
template <typename T>
concept Hash64 = requires(T t, const uint8_t *data, std::size_t len) {
  { t(data, len) };
  { t.final() } -> std::same_as<uint64_t>;
  { t.reset() };
};
 
template <typename T>
concept HashFamily64 =
    requires(T t, std::size_t i, const uint8_t *data, std::size_t len) {
      { t(i, data, len) };
      { t.final(i) } -> std::same_as<uint64_t>;
      { t.reset() };
      { t.size() } -> std::same_as<std::size_t>;
    };
 
template <typename HashFamilyT, typename T>
uint64_t hashType64(HashFamilyT &h, std::size_t idx, const T &t) {
  h(idx, reinterpret_cast<const uint8_t *>(&t), sizeof(T));
  return h.final(idx);
}
 
template <typename HashFamilyT>
uint64_t hashType64(HashFamilyT &h, std::size_t idx, const std::string &s) {
  h(idx, reinterpret_cast<const uint8_t *>(s.data()), s.size());
  return h.final(idx);
}
 
template <typename HashFamilyT, typename T>
uint64_t hashType64(HashFamilyT &h, std::size_t idx, const std::vector<T> &v) {
  h(reinterpret_cast<const uint8_t *>(v.data()), v.size() * sizeof(T));
  return h.final(idx);
}
 
template <typename HashFamilyT>
uint64_t hashType64(HashFamilyT &h, std::size_t idx,
                    const std::vector<std::string> &v) {
  for (const auto &s : v) {
    h(reinterpret_cast<const uint8_t *>(s.data()), s.size());
  }
  return h.final(idx);
}
 
template <Hash64 HT> HT makeHashWithRandomSeed() {
  std::random_device rd;
  std::mt19937 gen(rd());
  std::uniform_int_distribution<uint64_t> dis;
  return HT{dis(gen)};
}
 
template <Hash64 H1, Hash64 H2> class KirschMitzenmacher {
public:
  explicit KirschMitzenmacher(H1 h1, H2 h2, std::size_t k)
      : h1{std::move(h1)}, h2{std::move(h2)}, k{k} {}
 
  void reset() {
    h1.reset();
    h2.reset();
  }
 
  void operator()(std::size_t idx, const uint8_t *data, std::size_t len) {
    if (idx == 0) {
      h1(data, len);
      h2(data, len);
    }
  }
 
  uint64_t final(std::size_t i) const { return h1.final() + i * h2.final(); }
 
  std::size_t size() const BOXES_NOTHROW { return k; }
 
protected:
  H1 h1;
  H2 h2;
  std::size_t k;
};
 
template <Hash64 HashT> class HashWithSeedFamily {
public:
  explicit HashWithSeedFamily(std::size_t n) {
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<uint64_t> dis;
    std::set<uint64_t> seeds;
 
    for (std::size_t i = 0; i < n; ++i) {
      uint64_t seed = 0;
      do {
        // make sure all seeds are unique
        seed = dis(gen);
      } while (!seeds.insert(seed).second);
      hashes.emplace_back(dis(gen));
    }
  }
 
  void reset() {
    for (auto &h : hashes) {
      h.reset();
    }
  }
 
  std::size_t size() const BOXES_NOTHROW { return hashes.size(); }
 
  void operator()(std::size_t idx, const uint8_t *data, std::size_t len) {
    hashes.at(idx)(data, len);
  }
 
  uint64_t final(std::size_t i) const { return hashes.at(i).final(); }
 
protected:
  std::vector<HashT> hashes;
};
 
template <Hash64 H1, Hash64 H2>
KirschMitzenmacher<H1, H2> makeKirschMitzenmacher(H1 h1, H2 h2, std::size_t k) {
  return KirschMitzenmacher<H1, H2>{std::move(h1), std::move(h2), k};
}
 
} // namespace boxes::hash
 
#endif // __BOXES_HASH_UTILS_HPP__