1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
|
/*
* Copyright 2018 Google
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#ifndef FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_HASHING_H_
#define FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_HASHING_H_
#include <iterator>
#include <string>
#include <type_traits>
namespace firebase {
namespace firestore {
namespace util {
// This is a pretty terrible hash implementation for lack of a better one being
// readily available. It exists as a portability crutch between our existing
// Objective-C code where overriding `-isEqual:` also requires `-hash` and C++
// where `operator==()` can be defined without defining a hash code.
//
// It's based on the recommendation in Effective Java, Item 9, wherein you
// implement composite hashes like so:
//
// size_t result = first_;
// result = 31 * result + second_;
// result = 31 * result + third_;
// // ...
// return result;
//
// This is the basis of this implementation because that's what the existing
// Objective-C code mostly does by hand. Using this implementation gets the
// same result by calling
//
// return util::Hash(first_, second_, /* ..., */ third_);
//
// TODO(wilhuff): Replace this with whatever Abseil releases.
namespace impl {
/**
* A type trait that identifies whether or not std::hash is available for a
* given type.
*
* This type should not be necessary since specialization failure on an
* expression like `decltype(std::hash<K>{}(value)` should be enough to disable
* overloads that require `std::hash` to be defined but unfortunately some
* standard libraries ship with std::hash defined for all types that only
* fail later (e.g. via static_assert). One such implementation is the libc++
* that ships with Xcode 8.3.3, which is a supported platform.
*/
template <typename T>
struct has_std_hash {
// There may be other types for which std::hash is defined but they don't
// matter for our purposes.
enum {
value = std::is_arithmetic<T>{} || std::is_pointer<T>{} ||
std::is_same<T, std::string>{}
};
constexpr operator bool() const {
return value;
}
};
/**
* A type that's equivalent to size_t if std::hash<T> is defined or a compile
* error otherwise.
*
* This is effectively just a safe implementation of
* `decltype(std::hash<T>{}(std::declval<T>()))`.
*/
template <typename T>
using std_hash_type = typename std::enable_if<has_std_hash<T>{}, size_t>::type;
/**
* Combines a hash_value with whatever accumulated state there is so far.
*/
inline size_t Combine(size_t state, size_t hash_value) {
return 31 * state + hash_value;
}
/**
* Explicit ordering of hashers, allowing SFINAE without all the enable_if
* cruft.
*
* In order we try:
* * A Hash() member, if defined and the return type is an integral type
* * A std::hash specialization, if available
* * A range-based specialization, valid if either of the above hold on the
* members of the range.
*
* Explicit ordering resolves the ambiguity of the case where a std::hash
* specialization is available, but the type is also a range for whose members
* std::hash is also available, e.g. with std::string.
*
* HashChoice is a recursive type, defined such that HashChoice<0> is the most
* specific type with HashChoice<1> and beyond being progressively less
* specific. This causes the compiler to prioritize the overloads with
* lower-numbered HashChoice types, allowing compilation to succeed even if
* multiple specializations match.
*/
template <int I>
struct HashChoice : HashChoice<I + 1> {};
template <>
struct HashChoice<2> {};
template <typename K>
size_t InvokeHash(const K& value);
/**
* Hashes the given value if it defines a Hash() member.
*
* @return The result of `value.Hash()`.
*/
template <typename K>
auto RankedInvokeHash(const K& value, HashChoice<0>) -> decltype(value.Hash()) {
return value.Hash();
}
/**
* Hashes the given value if it has a specialization of std::hash.
*
* @return The result of `std::hash<K>{}(value)`
*/
template <typename K>
std_hash_type<K> RankedInvokeHash(const K& value, HashChoice<1>) {
return std::hash<K>{}(value);
}
/**
* Hashes the contents of the given range of values if the value_type of the
* range can be hashed.
*/
template <typename Range>
auto RankedInvokeHash(const Range& range, HashChoice<2>)
-> decltype(impl::InvokeHash(*std::begin(range))) {
size_t result = 0;
size_t size = 0;
for (auto&& element : range) {
++size;
result = Combine(result, InvokeHash(element));
}
result = Combine(result, size);
return result;
}
template <typename K>
size_t InvokeHash(const K& value) {
return RankedInvokeHash(value, HashChoice<0>{});
}
inline size_t HashInternal(size_t state) {
return state;
}
template <typename T, typename... Ts>
size_t HashInternal(size_t state, const T& value, const Ts&... rest) {
state = Combine(state, InvokeHash(value));
return HashInternal(state, rest...);
}
} // namespace impl
template <typename... Ts>
size_t Hash(const Ts&... values) {
return impl::HashInternal(0u, values...);
}
} // namespace util
} // namespace firestore
} // namespace firebase
#endif // FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_HASHING_H_
|
