1 // Copyright 2021 The Tint Authors 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #ifndef SRC_UTILS_HASH_H_ 16 #define SRC_UTILS_HASH_H_ 17 18 #include <stdint.h> 19 #include <cstdio> 20 #include <functional> 21 #include <vector> 22 23 namespace tint { 24 namespace utils { 25 namespace detail { 26 27 /// Helper for obtaining a seed bias value for HashCombine with a bit-width 28 /// dependent on the size of size_t. 29 template <int SIZE_OF_SIZE_T> 30 struct HashCombineOffset {}; 31 32 /// Specialization of HashCombineOffset for size_t == 4. 33 template <> 34 struct HashCombineOffset<4> { 35 /// @returns the seed bias value for HashCombine() 36 static constexpr inline uint32_t value() { return 0x7f4a7c16; } 37 }; 38 39 /// Specialization of HashCombineOffset for size_t == 8. 40 template <> 41 struct HashCombineOffset<8> { 42 /// @returns the seed bias value for HashCombine() 43 static constexpr inline uint64_t value() { return 0x9e3779b97f4a7c16; } 44 }; 45 46 } // namespace detail 47 48 /// HashCombine "hashes" together an existing hash and hashable values. 49 template <typename T> 50 void HashCombine(size_t* hash, const T& value) { 51 constexpr size_t offset = detail::HashCombineOffset<sizeof(size_t)>::value(); 52 *hash ^= std::hash<T>()(value) + offset + (*hash << 6) + (*hash >> 2); 53 } 54 55 /// HashCombine "hashes" together an existing hash and hashable values. 56 template <typename T> 57 void HashCombine(size_t* hash, const std::vector<T>& vector) { 58 HashCombine(hash, vector.size()); 59 for (auto& el : vector) { 60 HashCombine(hash, el); 61 } 62 } 63 64 /// HashCombine "hashes" together an existing hash and hashable values. 65 template <typename T, typename... ARGS> 66 void HashCombine(size_t* hash, const T& value, const ARGS&... args) { 67 HashCombine(hash, value); 68 HashCombine(hash, args...); 69 } 70 71 /// @returns a hash of the combined arguments. The returned hash is dependent on 72 /// the order of the arguments. 73 template <typename... ARGS> 74 size_t Hash(const ARGS&... args) { 75 size_t hash = 102931; // seed with an arbitrary prime 76 HashCombine(&hash, args...); 77 return hash; 78 } 79 80 } // namespace utils 81 } // namespace tint 82 83 #endif // SRC_UTILS_HASH_H_ 84