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_LIB_HASH_HASH_H_
19#define TENSORFLOW_LIB_HASH_HASH_H_
20
21#include <stddef.h>
22#include <stdint.h>
23
24#include <string>
25
26#include "tensorflow/core/lib/core/stringpiece.h"
27#include "tensorflow/core/platform/types.h"
28
29namespace tensorflow {
30
31extern uint32 Hash32(const char* data, size_t n, uint32 seed);
32extern uint64 Hash64(const char* data, size_t n, uint64 seed);
33
34inline uint64 Hash64(const char* data, size_t n) {
35 return Hash64(data, n, 0xDECAFCAFFE);
36}
37
38inline uint64 Hash64(const string& str) {
39 return Hash64(str.data(), str.size());
40}
41
42inline uint64 Hash64Combine(uint64 a, uint64 b) {
43 return a ^ (b + 0x9e3779b97f4a7800ULL + (a << 10) + (a >> 4));
44}
45
46// Hash functor suitable for use with power-of-two sized hashtables. Use
47// instead of std::hash<T>.
48//
49// In particular, tensorflow::hash is not the identity function for pointers.
50// This is important for power-of-two sized hashtables like FlatMap and FlatSet,
51// because otherwise they waste the majority of their hash buckets.
52template <typename T>
53struct hash {
54 size_t operator()(const T& t) const { return std::hash<T>()(t); }
55};
56
57template <typename T>
58struct hash<T*> {
59 size_t operator()(const T* t) const {
60 // Hash pointers as integers, but bring more entropy to the lower bits.
61 size_t k = static_cast<size_t>(reinterpret_cast<uintptr_t>(t));
62 return k + (k >> 6);
63 }
64};
65
66template <>
67struct hash<string> {
68 size_t operator()(const string& s) const {
69 return static_cast<size_t>(Hash64(s));
70 }
71};
72
73template <>
74struct hash<StringPiece> {
75 size_t operator()(StringPiece sp) const {
76 return static_cast<size_t>(Hash64(sp.data(), sp.size()));
77 }
78};
79using StringPieceHasher = ::tensorflow::hash<StringPiece>;
80
81template <typename T, typename U>
82struct hash<std::pair<T, U>> {
83 size_t operator()(const std::pair<T, U>& p) const {
84 return Hash64Combine(hash<T>()(p.first), hash<U>()(p.second));
85 }
86};
87
88} // namespace tensorflow
89
90#endif // TENSORFLOW_LIB_HASH_HASH_H_
91