src/tint/utils/math/hash.h - tint - Git at Google

 // Copyright 2021 The Tint Authors
 //
 // Licensed under the Apache License, Version 2.0 (the "License");
 // you may not use this file except in compliance with the License.
 // You may obtain a copy of the License at
 //
 //     http://www.apache.org/licenses/LICENSE-2.0
 //
 // Unless required by applicable law or agreed to in writing, software
 // distributed under the License is distributed on an "AS IS" BASIS,
 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 // See the License for the specific language governing permissions and
 // limitations under the License.

 #ifndef SRC_TINT_UTILS_MATH_HASH_H_
 #define SRC_TINT_UTILS_MATH_HASH_H_

 #include <stdint.h>
 #include <cstdio>
 #include <functional>
 #include <string>
 #include <tuple>
 #include <utility>
 #include <variant>
 #include <vector>

 #include "src/tint/utils/math/crc32.h"

 namespace tint {
 namespace detail {

 /// Helper for obtaining a seed bias value for HashCombine with a bit-width
 /// dependent on the size of size_t.
 template <int SIZE_OF_SIZE_T>
 struct HashCombineOffset {};

 /// Specialization of HashCombineOffset for size_t == 4.
 template <>
 struct HashCombineOffset<4> {
     /// @returns the seed bias value for HashCombine()
     static constexpr inline uint32_t value() {
         constexpr uint32_t base = 0x7f4a7c16;
 #ifdef TINT_HASH_SEED
         return base ^ static_cast<uint32_t>(TINT_HASH_SEED);
 #endif
         return base;
     }
 };

 /// Specialization of HashCombineOffset for size_t == 8.
 template <>
 struct HashCombineOffset<8> {
     /// @returns the seed bias value for HashCombine()
     static constexpr inline uint64_t value() {
         constexpr uint64_t base = 0x9e3779b97f4a7c16;
 #ifdef TINT_HASH_SEED
         return base ^ static_cast<uint64_t>(TINT_HASH_SEED);
 #endif
         return base;
     }
 };

 }  // namespace detail

 /// Forward declarations (see below)
 template <typename... ARGS>
 size_t Hash(const ARGS&... values);

 template <typename... ARGS>
 size_t HashCombine(size_t hash, const ARGS&... values);

 /// A STL-compatible hasher that does a more thorough job than most implementations of std::hash.
 /// Hasher has been optimized for a better quality hash at the expense of increased computation
 /// costs.
 template <typename T>
 struct Hasher {
     /// @param value the value to hash
     /// @returns a hash of the value
     size_t operator()(const T& value) const { return std::hash<T>()(value); }
 };

 /// Hasher specialization for pointers
 /// std::hash<T*> typically uses a reinterpret of the pointer to a size_t.
 /// As most pointers a 4 or 16 byte aligned, this usually results in the LSBs of the hash being 0,
 /// resulting in bad hashes for hashtables. This implementation mixes up those LSBs.
 template <typename T>
 struct Hasher<T*> {
     /// @param ptr the pointer to hash
     /// @returns a hash of the pointer
     size_t operator()(T* ptr) const {
         auto hash = std::hash<T*>()(ptr);
 #ifdef TINT_HASH_SEED
         hash ^= static_cast<uint32_t>(TINT_HASH_SEED);
 #endif
         return hash ^ (hash >> 4);
     }
 };

 /// Hasher specialization for std::vector
 template <typename T>
 struct Hasher<std::vector<T>> {
     /// @param vector the vector to hash
     /// @returns a hash of the vector
     size_t operator()(const std::vector<T>& vector) const {
         auto hash = Hash(vector.size());
         for (auto& el : vector) {
             hash = HashCombine(hash, el);
         }
         return hash;
     }
 };

 /// Hasher specialization for std::tuple
 template <typename... TYPES>
 struct Hasher<std::tuple<TYPES...>> {
     /// @param tuple the tuple to hash
     /// @returns a hash of the tuple
     size_t operator()(const std::tuple<TYPES...>& tuple) const {
         return std::apply(Hash<TYPES...>, tuple);
     }
 };

 /// Hasher specialization for std::pair
 template <typename A, typename B>
 struct Hasher<std::pair<A, B>> {
     /// @param tuple the tuple to hash
     /// @returns a hash of the tuple
     size_t operator()(const std::pair<A, B>& tuple) const { return std::apply(Hash<A, B>, tuple); }
 };

 /// Hasher specialization for std::variant
 template <typename... TYPES>
 struct Hasher<std::variant<TYPES...>> {
     /// @param variant the variant to hash
     /// @returns a hash of the tuple
     size_t operator()(const std::variant<TYPES...>& variant) const {
         return std::visit([](auto&& val) { return Hash(val); }, variant);
     }
 };

 /// Hasher specialization for std::string, which also supports hashing of const char* and
 /// std::string_view without first constructing a std::string.
 template <>
 struct Hasher<std::string> {
     /// @param str the string to hash
     /// @returns a hash of the string
     size_t operator()(const std::string& str) const {
         return std::hash<std::string_view>()(std::string_view(str));
     }

     /// @param str the string to hash
     /// @returns a hash of the string
     size_t operator()(const char* str) const {
         return std::hash<std::string_view>()(std::string_view(str));
     }

     /// @param str the string to hash
     /// @returns a hash of the string
     size_t operator()(const std::string_view& str) const {
         return std::hash<std::string_view>()(str);
     }
 };

 /// @param args the arguments to hash
 /// @returns a hash of the variadic list of arguments.
 ///          The returned hash is dependent on the order of the arguments.
 template <typename... ARGS>
 size_t Hash(const ARGS&... args) {
     if constexpr (sizeof...(ARGS) == 0) {
         return 0;
     } else if constexpr (sizeof...(ARGS) == 1) {
         using T = std::tuple_element_t<0, std::tuple<ARGS...>>;
         return Hasher<T>()(args...);
     } else {
         size_t hash = 102931;  // seed with an arbitrary prime
         return HashCombine(hash, args...);
     }
 }

 /// @param hash the hash value to combine with
 /// @param values the values to hash
 /// @returns a hash of the variadic list of arguments.
 ///          The returned hash is dependent on the order of the arguments.
 template <typename... ARGS>
 size_t HashCombine(size_t hash, const ARGS&... values) {
     constexpr size_t offset = tint::detail::HashCombineOffset<sizeof(size_t)>::value();
     ((hash ^= Hash(values) + (offset ^ (hash >> 2))), ...);
     return hash;
 }

 /// A STL-compatible equal_to implementation that specializes for types.
 template <typename T>
 struct EqualTo {
     /// @param lhs the left hand side value
     /// @param rhs the right hand side value
     /// @returns true if the two values are equal
     constexpr bool operator()(const T& lhs, const T& rhs) const {
         return std::equal_to<T>()(lhs, rhs);
     }
 };

 /// A specialization for EqualTo for std::string, which supports additional comparision with
 /// std::string_view and const char*.
 template <>
 struct EqualTo<std::string> {
     /// @param lhs the left hand side value
     /// @param rhs the right hand side value
     /// @returns true if the two values are equal
     bool operator()(const std::string& lhs, const std::string& rhs) const { return lhs == rhs; }

     /// @param lhs the left hand side value
     /// @param rhs the right hand side value
     /// @returns true if the two values are equal
     bool operator()(const std::string& lhs, const char* rhs) const { return lhs == rhs; }

     /// @param lhs the left hand side value
     /// @param rhs the right hand side value
     /// @returns true if the two values are equal
     bool operator()(const std::string& lhs, std::string_view rhs) const { return lhs == rhs; }

     /// @param lhs the left hand side value
     /// @param rhs the right hand side value
     /// @returns true if the two values are equal
     bool operator()(const char* lhs, const std::string& rhs) const { return lhs == rhs; }

     /// @param lhs the left hand side value
     /// @param rhs the right hand side value
     /// @returns true if the two values are equal
     bool operator()(std::string_view lhs, const std::string& rhs) const { return lhs == rhs; }
 };

 /// Wrapper for a hashable type enabling the wrapped value to be used as a key
 /// for an unordered_map or unordered_set.
 template <typename T>
 struct UnorderedKeyWrapper {
     /// The wrapped value
     T value;
     /// The hash of value
     size_t hash;

     /// Constructor
     /// @param v the value to wrap
     explicit UnorderedKeyWrapper(const T& v) : value(v), hash(Hash(v)) {}

     /// Move constructor
     /// @param v the value to wrap
     explicit UnorderedKeyWrapper(T&& v) : value(std::move(v)), hash(Hash(value)) {}

     /// @returns true if this wrapper comes before other
     /// @param other the RHS of the operator
     bool operator<(const UnorderedKeyWrapper& other) const { return hash < other.hash; }

     /// @returns true if this wrapped value is equal to the other wrapped value
     /// @param other the RHS of the operator
     bool operator==(const UnorderedKeyWrapper& other) const { return value == other.value; }
 };

 }  // namespace tint

 namespace std {

 /// Custom std::hash specialization for tint::UnorderedKeyWrapper
 template <typename T>
 class hash<tint::UnorderedKeyWrapper<T>> {
   public:
     /// @param w the UnorderedKeyWrapper
     /// @return the hash value
     inline std::size_t operator()(const tint::UnorderedKeyWrapper<T>& w) const { return w.hash; }
 };

 }  // namespace std

 #endif  // SRC_TINT_UTILS_MATH_HASH_H_
	// Copyright 2021 The Tint Authors
	//
	// Licensed under the Apache License, Version 2.0 (the "License");
	// you may not use this file except in compliance with the License.
	// You may obtain a copy of the License at
	//
	// http://www.apache.org/licenses/LICENSE-2.0
	//
	// Unless required by applicable law or agreed to in writing, software
	// distributed under the License is distributed on an "AS IS" BASIS,
	// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	// See the License for the specific language governing permissions and
	// limitations under the License.

	#ifndef SRC_TINT_UTILS_MATH_HASH_H_
	#define SRC_TINT_UTILS_MATH_HASH_H_

	#include <stdint.h>
	#include <cstdio>
	#include <functional>
	#include <string>
	#include <tuple>
	#include <utility>
	#include <variant>
	#include <vector>

	#include "src/tint/utils/math/crc32.h"

	namespace tint {
	namespace detail {

	/// Helper for obtaining a seed bias value for HashCombine with a bit-width
	/// dependent on the size of size_t.
	template <int SIZE_OF_SIZE_T>
	struct HashCombineOffset {};

	/// Specialization of HashCombineOffset for size_t == 4.
	template <>
	struct HashCombineOffset<4> {
	/// @returns the seed bias value for HashCombine()
	static constexpr inline uint32_t value() {
	constexpr uint32_t base = 0x7f4a7c16;
	#ifdef TINT_HASH_SEED
	return base ^ static_cast<uint32_t>(TINT_HASH_SEED);
	#endif
	return base;
	}
	};

	/// Specialization of HashCombineOffset for size_t == 8.
	template <>
	struct HashCombineOffset<8> {
	/// @returns the seed bias value for HashCombine()
	static constexpr inline uint64_t value() {
	constexpr uint64_t base = 0x9e3779b97f4a7c16;
	#ifdef TINT_HASH_SEED
	return base ^ static_cast<uint64_t>(TINT_HASH_SEED);
	#endif
	return base;
	}
	};

	} // namespace detail

	/// Forward declarations (see below)
	template <typename... ARGS>
	size_t Hash(const ARGS&... values);

	template <typename... ARGS>
	size_t HashCombine(size_t hash, const ARGS&... values);

	/// A STL-compatible hasher that does a more thorough job than most implementations of std::hash.
	/// Hasher has been optimized for a better quality hash at the expense of increased computation
	/// costs.
	template <typename T>
	struct Hasher {
	/// @param value the value to hash
	/// @returns a hash of the value
	size_t operator()(const T& value) const { return std::hash<T>()(value); }
	};

	/// Hasher specialization for pointers
	/// std::hash<T*> typically uses a reinterpret of the pointer to a size_t.
	/// As most pointers a 4 or 16 byte aligned, this usually results in the LSBs of the hash being 0,
	/// resulting in bad hashes for hashtables. This implementation mixes up those LSBs.
	template <typename T>
	struct Hasher<T*> {
	/// @param ptr the pointer to hash
	/// @returns a hash of the pointer
	size_t operator()(T* ptr) const {
	auto hash = std::hash<T*>()(ptr);
	#ifdef TINT_HASH_SEED
	hash ^= static_cast<uint32_t>(TINT_HASH_SEED);
	#endif
	return hash ^ (hash >> 4);
	}
	};

	/// Hasher specialization for std::vector
	template <typename T>
	struct Hasher<std::vector<T>> {
	/// @param vector the vector to hash
	/// @returns a hash of the vector
	size_t operator()(const std::vector<T>& vector) const {
	auto hash = Hash(vector.size());
	for (auto& el : vector) {
	hash = HashCombine(hash, el);
	}
	return hash;
	}
	};

	/// Hasher specialization for std::tuple
	template <typename... TYPES>
	struct Hasher<std::tuple<TYPES...>> {
	/// @param tuple the tuple to hash
	/// @returns a hash of the tuple
	size_t operator()(const std::tuple<TYPES...>& tuple) const {
	return std::apply(Hash<TYPES...>, tuple);
	}
	};

	/// Hasher specialization for std::pair
	template <typename A, typename B>
	struct Hasher<std::pair<A, B>> {
	/// @param tuple the tuple to hash
	/// @returns a hash of the tuple
	size_t operator()(const std::pair<A, B>& tuple) const { return std::apply(Hash<A, B>, tuple); }
	};

	/// Hasher specialization for std::variant
	template <typename... TYPES>
	struct Hasher<std::variant<TYPES...>> {
	/// @param variant the variant to hash
	/// @returns a hash of the tuple
	size_t operator()(const std::variant<TYPES...>& variant) const {
	return std::visit([](auto&& val) { return Hash(val); }, variant);
	}
	};

	/// Hasher specialization for std::string, which also supports hashing of const char* and
	/// std::string_view without first constructing a std::string.
	template <>
	struct Hasher<std::string> {
	/// @param str the string to hash
	/// @returns a hash of the string
	size_t operator()(const std::string& str) const {
	return std::hash<std::string_view>()(std::string_view(str));
	}

	/// @param str the string to hash
	/// @returns a hash of the string
	size_t operator()(const char* str) const {
	return std::hash<std::string_view>()(std::string_view(str));
	}

	/// @param str the string to hash
	/// @returns a hash of the string
	size_t operator()(const std::string_view& str) const {
	return std::hash<std::string_view>()(str);
	}
	};

	/// @param args the arguments to hash
	/// @returns a hash of the variadic list of arguments.
	/// The returned hash is dependent on the order of the arguments.
	template <typename... ARGS>
	size_t Hash(const ARGS&... args) {
	if constexpr (sizeof...(ARGS) == 0) {
	return 0;
	} else if constexpr (sizeof...(ARGS) == 1) {
	using T = std::tuple_element_t<0, std::tuple<ARGS...>>;
	return Hasher<T>()(args...);
	} else {
	size_t hash = 102931; // seed with an arbitrary prime
	return HashCombine(hash, args...);
	}
	}

	/// @param hash the hash value to combine with
	/// @param values the values to hash
	/// @returns a hash of the variadic list of arguments.
	/// The returned hash is dependent on the order of the arguments.
	template <typename... ARGS>
	size_t HashCombine(size_t hash, const ARGS&... values) {
	constexpr size_t offset = tint::detail::HashCombineOffset<sizeof(size_t)>::value();
	((hash ^= Hash(values) + (offset ^ (hash >> 2))), ...);
	return hash;
	}

	/// A STL-compatible equal_to implementation that specializes for types.
	template <typename T>
	struct EqualTo {
	/// @param lhs the left hand side value
	/// @param rhs the right hand side value
	/// @returns true if the two values are equal
	constexpr bool operator()(const T& lhs, const T& rhs) const {
	return std::equal_to<T>()(lhs, rhs);
	}
	};

	/// A specialization for EqualTo for std::string, which supports additional comparision with
	/// std::string_view and const char*.
	template <>
	struct EqualTo<std::string> {
	/// @param lhs the left hand side value
	/// @param rhs the right hand side value
	/// @returns true if the two values are equal
	bool operator()(const std::string& lhs, const std::string& rhs) const { return lhs == rhs; }

	/// @param lhs the left hand side value
	/// @param rhs the right hand side value
	/// @returns true if the two values are equal
	bool operator()(const std::string& lhs, const char* rhs) const { return lhs == rhs; }

	/// @param lhs the left hand side value
	/// @param rhs the right hand side value
	/// @returns true if the two values are equal
	bool operator()(const std::string& lhs, std::string_view rhs) const { return lhs == rhs; }

	/// @param lhs the left hand side value
	/// @param rhs the right hand side value
	/// @returns true if the two values are equal
	bool operator()(const char* lhs, const std::string& rhs) const { return lhs == rhs; }

	/// @param lhs the left hand side value
	/// @param rhs the right hand side value
	/// @returns true if the two values are equal
	bool operator()(std::string_view lhs, const std::string& rhs) const { return lhs == rhs; }
	};

	/// Wrapper for a hashable type enabling the wrapped value to be used as a key
	/// for an unordered_map or unordered_set.
	template <typename T>
	struct UnorderedKeyWrapper {
	/// The wrapped value
	T value;
	/// The hash of value
	size_t hash;

	/// Constructor
	/// @param v the value to wrap
	explicit UnorderedKeyWrapper(const T& v) : value(v), hash(Hash(v)) {}

	/// Move constructor
	/// @param v the value to wrap
	explicit UnorderedKeyWrapper(T&& v) : value(std::move(v)), hash(Hash(value)) {}

	/// @returns true if this wrapper comes before other
	/// @param other the RHS of the operator
	bool operator<(const UnorderedKeyWrapper& other) const { return hash < other.hash; }

	/// @returns true if this wrapped value is equal to the other wrapped value
	/// @param other the RHS of the operator
	bool operator==(const UnorderedKeyWrapper& other) const { return value == other.value; }
	};

	} // namespace tint

	namespace std {

	/// Custom std::hash specialization for tint::UnorderedKeyWrapper
	template <typename T>
	class hash<tint::UnorderedKeyWrapper<T>> {
	public:
	/// @param w the UnorderedKeyWrapper
	/// @return the hash value
	inline std::size_t operator()(const tint::UnorderedKeyWrapper<T>& w) const { return w.hash; }
	};

	} // namespace std

	#endif // SRC_TINT_UTILS_MATH_HASH_H_