Add utils/hash.h
Contains hash combining functions borrowed and tweaked from Dawn
Change-Id: I0bc9478bcdba0b923d0b01825c275290ffa29976
Reviewed-on: https://dawn-review.googlesource.com/c/tint/+/46268
Reviewed-by: Corentin Wallez <cwallez@chromium.org>
Commit-Queue: Ben Clayton <bclayton@google.com>
diff --git a/src/BUILD.gn b/src/BUILD.gn
index d7edebb..d71ba68 100644
--- a/src/BUILD.gn
+++ b/src/BUILD.gn
@@ -450,6 +450,8 @@
"type/vector_type.h",
"type/void_type.cc",
"type/void_type.h",
+ "utils/hash.h",
+ "utils/math.h",
"utils/unique_vector.h",
"validator/validator.cc",
"validator/validator.h",
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index 2f1adb3..04b87e1 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -265,6 +265,8 @@
type/vector_type.h
type/void_type.cc
type/void_type.h
+ utils/hash.h
+ utils/math.h
utils/unique_vector.h
validator/validator.cc
validator/validator.h
@@ -507,6 +509,7 @@
type/vector_type_test.cc
utils/command_test.cc
utils/command.h
+ utils/hash_test.cc
utils/math_test.cc
utils/tmpfile_test.cc
utils/tmpfile.h
diff --git a/src/utils/hash.h b/src/utils/hash.h
new file mode 100644
index 0000000..44e1e49
--- /dev/null
+++ b/src/utils/hash.h
@@ -0,0 +1,74 @@
+// 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_UTILS_HASH_H_
+#define SRC_UTILS_HASH_H_
+
+#include <stdint.h>
+#include <cstdio>
+#include <functional>
+
+namespace tint {
+namespace utils {
+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() { return 0x7f4a7c16; }
+};
+
+/// Specialization of HashCombineOffset for size_t == 8.
+template <>
+struct HashCombineOffset<8> {
+ /// @returns the seed bias value for HashCombine()
+ static constexpr inline uint64_t value() { return 0x9e3779b97f4a7c16; }
+};
+
+// When hashing sparse structures we want to iteratively build a hash value with
+// only parts of the data. HashCombine "hashes" together an existing hash and
+// hashable values.
+template <typename T>
+void HashCombine(size_t* hash, const T& value) {
+ constexpr size_t offset = HashCombineOffset<sizeof(size_t)>::value();
+ *hash ^= std::hash<T>()(value) + offset + (*hash << 6) + (*hash >> 2);
+}
+
+template <typename T, typename... ARGS>
+void HashCombine(size_t* hash, const T& value, const ARGS&... args) {
+ HashCombine(hash, value);
+ HashCombine(hash, args...);
+}
+
+} // namespace detail
+
+/// @returns a hash of the combined arguments. The returned hash is dependent on
+/// the order of the arguments.
+template <typename... ARGS>
+size_t Hash(const ARGS&... args) {
+ size_t hash = 102931; // seed with an arbitrary prime
+ detail::HashCombine(&hash, args...);
+ return hash;
+}
+
+} // namespace utils
+} // namespace tint
+
+#endif // SRC_UTILS_HASH_H_
diff --git a/src/utils/hash_test.cc b/src/utils/hash_test.cc
new file mode 100644
index 0000000..177c53b
--- /dev/null
+++ b/src/utils/hash_test.cc
@@ -0,0 +1,38 @@
+// 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.
+
+#include "src/utils/hash.h"
+
+#include <string>
+
+#include "gtest/gtest.h"
+
+namespace tint {
+namespace utils {
+namespace {
+
+TEST(HashTests, Basic) {
+ EXPECT_NE(Hash(123), Hash(321));
+ EXPECT_NE(Hash(123, 456), Hash(123));
+ EXPECT_NE(Hash(123, 456, false), Hash(123, 456));
+ EXPECT_NE(Hash(std::string("hello")), Hash(std::string("world")));
+}
+
+TEST(HashTests, Order) {
+ EXPECT_NE(Hash(123, 456), Hash(456, 123));
+}
+
+} // namespace
+} // namespace utils
+} // namespace tint
diff --git a/test/BUILD.gn b/test/BUILD.gn
index d3d94be..b1d6b65 100644
--- a/test/BUILD.gn
+++ b/test/BUILD.gn
@@ -215,6 +215,7 @@
"../src/type/vector_type_test.cc",
"../src/utils/command.h",
"../src/utils/command_test.cc",
+ "../src/utils/hash_test.cc",
"../src/utils/math_test.cc",
"../src/utils/tmpfile.h",
"../src/utils/tmpfile_test.cc",
