1/* Copyright 2015 The TensorFlow Authors. All Rights Reserved.
2
3Licensed under the Apache License, Version 2.0 (the "License");
4you may not use this file except in compliance with the License.
5You may obtain a copy of the License at
6
7 http://www.apache.org/licenses/LICENSE-2.0
8
9Unless required by applicable law or agreed to in writing, software
10distributed under the License is distributed on an "AS IS" BASIS,
11WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12See the License for the specific language governing permissions and
13limitations 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
30namespace tsl {
31
32extern uint32 Hash32(const char* data, size_t n, uint32 seed);
33extern uint64 Hash64(const char* data, size_t n, uint64 seed);
34
35inline uint64 Hash64(const char* data, size_t n) {
36 return Hash64(data, n, 0xDECAFCAFFE);
37}
38
39inline uint64 Hash64(const char* data) { return Hash64(data, ::strlen(data)); }
40
41inline uint64 Hash64(const std::string& str) {
42 return Hash64(str.data(), str.size());
43}
44
45inline uint64 Hash64(const tstring& str) {
46 return Hash64(str.data(), str.size());
47}
48
49inline 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.
57inline 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.
67template <typename T, typename = void>
68struct hash {
69 size_t operator()(const T& t) const { return std::hash<T>()(t); }
70};
71
72template <typename T>
73struct 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
86template <typename T>
87struct 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
95template <>
96struct hash<string> {
97 size_t operator()(const string& s) const {
98 return static_cast<size_t>(Hash64(s));
99 }
100};
101
102template <>
103struct hash<tstring> {
104 size_t operator()(const tstring& s) const {
105 return static_cast<size_t>(Hash64(s.data(), s.size()));
106 }
107};
108
109template <>
110struct hash<StringPiece> {
111 size_t operator()(StringPiece sp) const {
112 return static_cast<size_t>(Hash64(sp.data(), sp.size()));
113 }
114};
115using StringPieceHasher = ::tsl::hash<StringPiece>;
116
117template <typename T, typename U>
118struct 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
126namespace std {
127template <>
128struct 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