1 | /* Copyright 2015 The TensorFlow Authors. All Rights Reserved. |
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 | |
16 | // Simple hash functions used for internal data structures |
17 | |
18 | #ifndef TENSORFLOW_TSL_PLATFORM_HASH_H_ |
19 | #define TENSORFLOW_TSL_PLATFORM_HASH_H_ |
20 | |
21 | #include <stddef.h> |
22 | #include <stdint.h> |
23 | |
24 | #include <functional> |
25 | #include <string> |
26 | |
27 | #include "tensorflow/tsl/platform/stringpiece.h" |
28 | #include "tensorflow/tsl/platform/types.h" |
29 | |
30 | namespace tsl { |
31 | |
32 | extern uint32 Hash32(const char* data, size_t n, uint32 seed); |
33 | extern uint64 Hash64(const char* data, size_t n, uint64 seed); |
34 | |
35 | inline uint64 Hash64(const char* data, size_t n) { |
36 | return Hash64(data, n, 0xDECAFCAFFE); |
37 | } |
38 | |
39 | inline uint64 Hash64(const char* data) { return Hash64(data, ::strlen(data)); } |
40 | |
41 | inline uint64 Hash64(const std::string& str) { |
42 | return Hash64(str.data(), str.size()); |
43 | } |
44 | |
45 | inline uint64 Hash64(const tstring& str) { |
46 | return Hash64(str.data(), str.size()); |
47 | } |
48 | |
49 | inline uint64 Hash64Combine(uint64 a, uint64 b) { |
50 | return a ^ (b + 0x9e3779b97f4a7800ULL + (a << 10) + (a >> 4)); |
51 | } |
52 | |
53 | // Combine two hashes in an order-independent way. This operation should be |
54 | // associative and compute the same hash for a collection of elements |
55 | // independent of traversal order. Note that it is better to combine hashes |
56 | // symmetrically with addition rather than XOR, since (x^x) == 0 but (x+x) != 0. |
57 | inline uint64 Hash64CombineUnordered(uint64 a, uint64 b) { return a + b; } |
58 | |
59 | // Hash functor suitable for use with power-of-two sized hashtables. Use |
60 | // instead of std::hash<T>. |
61 | // |
62 | // In particular, tsl::hash is not the identity function for pointers. |
63 | // This is important for power-of-two sized hashtables like FlatMap and FlatSet, |
64 | // because otherwise they waste the majority of their hash buckets. |
65 | // |
66 | // The second type argument is only used for SFNIAE below. |
67 | template <typename T, typename = void> |
68 | struct hash { |
69 | size_t operator()(const T& t) const { return std::hash<T>()(t); } |
70 | }; |
71 | |
72 | template <typename T> |
73 | struct hash<T, typename std::enable_if<std::is_enum<T>::value>::type> { |
74 | size_t operator()(T value) const { |
75 | // This works around a defect in the std::hash C++ spec that isn't fixed in |
76 | // (at least) gcc 4.8.4: |
77 | // http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#2148 |
78 | // |
79 | // We should be able to remove this and use the default |
80 | // tsl::hash<EnumTy>() once we stop building with GCC versions old |
81 | // enough to not have this defect fixed. |
82 | return std::hash<uint64>()(static_cast<uint64>(value)); |
83 | } |
84 | }; |
85 | |
86 | template <typename T> |
87 | struct hash<T*> { |
88 | size_t operator()(const T* t) const { |
89 | // Hash pointers as integers, but bring more entropy to the lower bits. |
90 | size_t k = static_cast<size_t>(reinterpret_cast<uintptr_t>(t)); |
91 | return k + (k >> 6); |
92 | } |
93 | }; |
94 | |
95 | template <> |
96 | struct hash<string> { |
97 | size_t operator()(const string& s) const { |
98 | return static_cast<size_t>(Hash64(s)); |
99 | } |
100 | }; |
101 | |
102 | template <> |
103 | struct hash<tstring> { |
104 | size_t operator()(const tstring& s) const { |
105 | return static_cast<size_t>(Hash64(s.data(), s.size())); |
106 | } |
107 | }; |
108 | |
109 | template <> |
110 | struct hash<StringPiece> { |
111 | size_t operator()(StringPiece sp) const { |
112 | return static_cast<size_t>(Hash64(sp.data(), sp.size())); |
113 | } |
114 | }; |
115 | using StringPieceHasher = ::tsl::hash<StringPiece>; |
116 | |
117 | template <typename T, typename U> |
118 | struct hash<std::pair<T, U>> { |
119 | size_t operator()(const std::pair<T, U>& p) const { |
120 | return Hash64Combine(hash<T>()(p.first), hash<U>()(p.second)); |
121 | } |
122 | }; |
123 | |
124 | } // namespace tsl |
125 | |
126 | namespace std { |
127 | template <> |
128 | struct hash<tsl::tstring> { |
129 | size_t operator()(const tsl::tstring& s) const { |
130 | return static_cast<size_t>(tsl::Hash64(s.data(), s.size())); |
131 | } |
132 | }; |
133 | } // namespace std |
134 | |
135 | #endif // TENSORFLOW_TSL_PLATFORM_HASH_H_ |
136 | |