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
|
/*
* 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 <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 {
/**
* 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>
auto RankedInvokeHash(const K& value, HashChoice<1>)
-> decltype(std::hash<K>{}(value)) {
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_
|
