1 // Copyright 2018 The Dawn 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 COMMON_HASHUTILS_H_
16 #define COMMON_HASHUTILS_H_
17
18 #include "common/Platform.h"
19 #include "common/TypedInteger.h"
20 #include "common/ityp_bitset.h"
21
22 #include <bitset>
23 #include <functional>
24
25 // Wrapper around std::hash to make it a templated function instead of a functor. It is marginally
26 // nicer, and avoids adding to the std namespace to add hashing of other types.
27 template <typename T>
Hash(const T & value)28 size_t Hash(const T& value) {
29 return std::hash<T>()(value);
30 }
31
32 // Add hashing of TypedIntegers
33 template <typename Tag, typename T>
Hash(const TypedInteger<Tag,T> & value)34 size_t Hash(const TypedInteger<Tag, T>& value) {
35 return Hash(static_cast<T>(value));
36 }
37
38 // When hashing sparse structures we want to iteratively build a hash value with only parts of the
39 // data. HashCombine "hashes" together an existing hash and hashable values.
40 //
41 // Example usage to compute the hash of a mask and values corresponding to the mask:
42 //
43 // size_t hash = Hash(mask):
44 // for (uint32_t i : IterateBitSet(mask)) { HashCombine(&hash, hashables[i]); }
45 // return hash;
46 template <typename T>
HashCombine(size_t * hash,const T & value)47 void HashCombine(size_t* hash, const T& value) {
48 #if defined(DAWN_PLATFORM_64_BIT)
49 const size_t offset = 0x9e3779b97f4a7c16;
50 #elif defined(DAWN_PLATFORM_32_BIT)
51 const size_t offset = 0x9e3779b9;
52 #else
53 # error "Unsupported platform"
54 #endif
55 *hash ^= Hash(value) + offset + (*hash << 6) + (*hash >> 2);
56 }
57
58 template <typename T, typename... Args>
HashCombine(size_t * hash,const T & value,const Args &...args)59 void HashCombine(size_t* hash, const T& value, const Args&... args) {
60 HashCombine(hash, value);
61 HashCombine(hash, args...);
62 }
63
64 // Workaround a bug between clang++ and libstdlibc++ by defining our own hashing for bitsets.
65 // When _GLIBCXX_DEBUG is enabled libstdc++ wraps containers into debug containers. For bitset this
66 // means what is normally std::bitset is defined as std::__cxx1988::bitset and is replaced by the
67 // debug version of bitset.
68 // When hashing, std::hash<std::bitset> proxies the call to std::hash<std::__cxx1998::bitset> and
69 // fails on clang because the latter tries to access the private _M_getdata member of the bitset.
70 // It looks like it should work because the non-debug bitset declares
71 //
72 // friend struct std::hash<bitset> // bitset is the name of the class itself
73 //
74 // which should friend std::hash<std::__cxx1998::bitset> but somehow doesn't work on clang.
75 #if defined(_GLIBCXX_DEBUG)
76 template <size_t N>
Hash(const std::bitset<N> & value)77 size_t Hash(const std::bitset<N>& value) {
78 constexpr size_t kWindowSize = sizeof(unsigned long long);
79
80 std::bitset<N> bits = value;
81 size_t hash = 0;
82 for (size_t processedBits = 0; processedBits < N; processedBits += kWindowSize) {
83 HashCombine(&hash, bits.to_ullong());
84 bits >>= kWindowSize;
85 }
86
87 return hash;
88 }
89 #endif
90
91 namespace std {
92 template <typename Index, size_t N>
93 struct hash<ityp::bitset<Index, N>> {
94 public:
95 size_t operator()(const ityp::bitset<Index, N>& value) const {
96 return Hash(static_cast<const std::bitset<N>&>(value));
97 }
98 };
99 } // namespace std
100
101 #endif // COMMON_HASHUTILS_H_
102