1 // Copyright 2018 The Abseil Authors.
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 // https://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 // File: hash.h
17 // -----------------------------------------------------------------------------
18 //
19 // This header file defines the Abseil `hash` library and the Abseil hashing
20 // framework. This framework consists of the following:
21 //
22 // * The `absl::Hash` functor, which is used to invoke the hasher within the
23 // Abseil hashing framework. `absl::Hash<T>` supports most basic types and
24 // a number of Abseil types out of the box.
25 // * `AbslHashValue`, an extension point that allows you to extend types to
26 // support Abseil hashing without requiring you to define a hashing
27 // algorithm.
28 // * `HashState`, a type-erased class which implements the manipulation of the
29 // hash state (H) itself, contains member functions `combine()` and
30 // `combine_contiguous()`, which you can use to contribute to an existing
31 // hash state when hashing your types.
32 //
33 // Unlike `std::hash` or other hashing frameworks, the Abseil hashing framework
34 // provides most of its utility by abstracting away the hash algorithm (and its
35 // implementation) entirely. Instead, a type invokes the Abseil hashing
36 // framework by simply combining its state with the state of known, hashable
37 // types. Hashing of that combined state is separately done by `absl::Hash`.
38 //
39 // One should assume that a hash algorithm is chosen randomly at the start of
40 // each process. E.g., `absl::Hash<int>{}(9)` in one process and
41 // `absl::Hash<int>{}(9)` in another process are likely to differ.
42 //
43 // `absl::Hash` is intended to strongly mix input bits with a target of passing
44 // an [Avalanche Test](https://en.wikipedia.org/wiki/Avalanche_effect).
45 //
46 // Example:
47 //
48 // // Suppose we have a class `Circle` for which we want to add hashing:
49 // class Circle {
50 // public:
51 // ...
52 // private:
53 // std::pair<int, int> center_;
54 // int radius_;
55 // };
56 //
57 // // To add hashing support to `Circle`, we simply need to add a free
58 // // (non-member) function `AbslHashValue()`, and return the combined hash
59 // // state of the existing hash state and the class state. You can add such a
60 // // free function using a friend declaration within the body of the class:
61 // class Circle {
62 // public:
63 // ...
64 // template <typename H>
65 // friend H AbslHashValue(H h, const Circle& c) {
66 // return H::combine(std::move(h), c.center_, c.radius_);
67 // }
68 // ...
69 // };
70 //
71 // For more information, see Adding Type Support to `absl::Hash` below.
72 //
73 #ifndef ABSL_HASH_HASH_H_
74 #define ABSL_HASH_HASH_H_
75
76 #include <tuple>
77
78 #include "absl/hash/internal/hash.h"
79
80 namespace absl {
81 ABSL_NAMESPACE_BEGIN
82
83 // -----------------------------------------------------------------------------
84 // `absl::Hash`
85 // -----------------------------------------------------------------------------
86 //
87 // `absl::Hash<T>` is a convenient general-purpose hash functor for any type `T`
88 // satisfying any of the following conditions (in order):
89 //
90 // * T is an arithmetic or pointer type
91 // * T defines an overload for `AbslHashValue(H, const T&)` for an arbitrary
92 // hash state `H`.
93 // - T defines a specialization of `std::hash<T>`
94 //
95 // `absl::Hash` intrinsically supports the following types:
96 //
97 // * All integral types (including bool)
98 // * All enum types
99 // * All floating-point types (although hashing them is discouraged)
100 // * All pointer types, including nullptr_t
101 // * std::pair<T1, T2>, if T1 and T2 are hashable
102 // * std::tuple<Ts...>, if all the Ts... are hashable
103 // * std::unique_ptr and std::shared_ptr
104 // * All string-like types including:
105 // * absl::Cord
106 // * std::string
107 // * std::string_view (as well as any instance of std::basic_string that
108 // uses char and std::char_traits)
109 // * All the standard sequence containers (provided the elements are hashable)
110 // * All the standard ordered associative containers (provided the elements are
111 // hashable)
112 // * absl types such as the following:
113 // * absl::string_view
114 // * absl::InlinedVector
115 // * absl::FixedArray
116 // * absl::uint128
117 // * absl::Time, absl::Duration, and absl::TimeZone
118 //
119 // Note: the list above is not meant to be exhaustive. Additional type support
120 // may be added, in which case the above list will be updated.
121 //
122 // -----------------------------------------------------------------------------
123 // absl::Hash Invocation Evaluation
124 // -----------------------------------------------------------------------------
125 //
126 // When invoked, `absl::Hash<T>` searches for supplied hash functions in the
127 // following order:
128 //
129 // * Natively supported types out of the box (see above)
130 // * Types for which an `AbslHashValue()` overload is provided (such as
131 // user-defined types). See "Adding Type Support to `absl::Hash`" below.
132 // * Types which define a `std::hash<T>` specialization
133 //
134 // The fallback to legacy hash functions exists mainly for backwards
135 // compatibility. If you have a choice, prefer defining an `AbslHashValue`
136 // overload instead of specializing any legacy hash functors.
137 //
138 // -----------------------------------------------------------------------------
139 // The Hash State Concept, and using `HashState` for Type Erasure
140 // -----------------------------------------------------------------------------
141 //
142 // The `absl::Hash` framework relies on the Concept of a "hash state." Such a
143 // hash state is used in several places:
144 //
145 // * Within existing implementations of `absl::Hash<T>` to store the hashed
146 // state of an object. Note that it is up to the implementation how it stores
147 // such state. A hash table, for example, may mix the state to produce an
148 // integer value; a testing framework may simply hold a vector of that state.
149 // * Within implementations of `AbslHashValue()` used to extend user-defined
150 // types. (See "Adding Type Support to absl::Hash" below.)
151 // * Inside a `HashState`, providing type erasure for the concept of a hash
152 // state, which you can use to extend the `absl::Hash` framework for types
153 // that are otherwise difficult to extend using `AbslHashValue()`. (See the
154 // `HashState` class below.)
155 //
156 // The "hash state" concept contains two member functions for mixing hash state:
157 //
158 // * `H::combine(state, values...)`
159 //
160 // Combines an arbitrary number of values into a hash state, returning the
161 // updated state. Note that the existing hash state is move-only and must be
162 // passed by value.
163 //
164 // Each of the value types T must be hashable by H.
165 //
166 // NOTE:
167 //
168 // state = H::combine(std::move(state), value1, value2, value3);
169 //
170 // must be guaranteed to produce the same hash expansion as
171 //
172 // state = H::combine(std::move(state), value1);
173 // state = H::combine(std::move(state), value2);
174 // state = H::combine(std::move(state), value3);
175 //
176 // * `H::combine_contiguous(state, data, size)`
177 //
178 // Combines a contiguous array of `size` elements into a hash state,
179 // returning the updated state. Note that the existing hash state is
180 // move-only and must be passed by value.
181 //
182 // NOTE:
183 //
184 // state = H::combine_contiguous(std::move(state), data, size);
185 //
186 // need NOT be guaranteed to produce the same hash expansion as a loop
187 // (it may perform internal optimizations). If you need this guarantee, use a
188 // loop instead.
189 //
190 // -----------------------------------------------------------------------------
191 // Adding Type Support to `absl::Hash`
192 // -----------------------------------------------------------------------------
193 //
194 // To add support for your user-defined type, add a proper `AbslHashValue()`
195 // overload as a free (non-member) function. The overload will take an
196 // existing hash state and should combine that state with state from the type.
197 //
198 // Example:
199 //
200 // template <typename H>
201 // H AbslHashValue(H state, const MyType& v) {
202 // return H::combine(std::move(state), v.field1, ..., v.fieldN);
203 // }
204 //
205 // where `(field1, ..., fieldN)` are the members you would use on your
206 // `operator==` to define equality.
207 //
208 // Notice that `AbslHashValue` is not a class member, but an ordinary function.
209 // An `AbslHashValue` overload for a type should only be declared in the same
210 // file and namespace as said type. The proper `AbslHashValue` implementation
211 // for a given type will be discovered via ADL.
212 //
213 // Note: unlike `std::hash', `absl::Hash` should never be specialized. It must
214 // only be extended by adding `AbslHashValue()` overloads.
215 //
216 template <typename T>
217 using Hash = absl::hash_internal::Hash<T>;
218
219 // HashOf
220 //
221 // absl::HashOf() is a helper that generates a hash from the values of its
222 // arguments. It dispatches to absl::Hash directly, as follows:
223 // * HashOf(t) == absl::Hash<T>{}(t)
224 // * HashOf(a, b, c) == HashOf(std::make_tuple(a, b, c))
225 //
226 // HashOf(a1, a2, ...) == HashOf(b1, b2, ...) is guaranteed when
227 // * The argument lists have pairwise identical C++ types
228 // * a1 == b1 && a2 == b2 && ...
229 //
230 // The requirement that the arguments match in both type and value is critical.
231 // It means that `a == b` does not necessarily imply `HashOf(a) == HashOf(b)` if
232 // `a` and `b` have different types. For example, `HashOf(2) != HashOf(2.0)`.
233 template <int&... ExplicitArgumentBarrier, typename... Types>
HashOf(const Types &...values)234 size_t HashOf(const Types&... values) {
235 auto tuple = std::tie(values...);
236 return absl::Hash<decltype(tuple)>{}(tuple);
237 }
238
239 // HashState
240 //
241 // A type erased version of the hash state concept, for use in user-defined
242 // `AbslHashValue` implementations that can't use templates (such as PImpl
243 // classes, virtual functions, etc.). The type erasure adds overhead so it
244 // should be avoided unless necessary.
245 //
246 // Note: This wrapper will only erase calls to:
247 // combine_contiguous(H, const unsigned char*, size_t)
248 //
249 // All other calls will be handled internally and will not invoke overloads
250 // provided by the wrapped class.
251 //
252 // Users of this class should still define a template `AbslHashValue` function,
253 // but can use `absl::HashState::Create(&state)` to erase the type of the hash
254 // state and dispatch to their private hashing logic.
255 //
256 // This state can be used like any other hash state. In particular, you can call
257 // `HashState::combine()` and `HashState::combine_contiguous()` on it.
258 //
259 // Example:
260 //
261 // class Interface {
262 // public:
263 // template <typename H>
264 // friend H AbslHashValue(H state, const Interface& value) {
265 // state = H::combine(std::move(state), std::type_index(typeid(*this)));
266 // value.HashValue(absl::HashState::Create(&state));
267 // return state;
268 // }
269 // private:
270 // virtual void HashValue(absl::HashState state) const = 0;
271 // };
272 //
273 // class Impl : Interface {
274 // private:
275 // void HashValue(absl::HashState state) const override {
276 // absl::HashState::combine(std::move(state), v1_, v2_);
277 // }
278 // int v1_;
279 // std::string v2_;
280 // };
281 class HashState : public hash_internal::HashStateBase<HashState> {
282 public:
283 // HashState::Create()
284 //
285 // Create a new `HashState` instance that wraps `state`. All calls to
286 // `combine()` and `combine_contiguous()` on the new instance will be
287 // redirected to the original `state` object. The `state` object must outlive
288 // the `HashState` instance.
289 template <typename T>
Create(T * state)290 static HashState Create(T* state) {
291 HashState s;
292 s.Init(state);
293 return s;
294 }
295
296 HashState(const HashState&) = delete;
297 HashState& operator=(const HashState&) = delete;
298 HashState(HashState&&) = default;
299 HashState& operator=(HashState&&) = default;
300
301 // HashState::combine()
302 //
303 // Combines an arbitrary number of values into a hash state, returning the
304 // updated state.
305 using HashState::HashStateBase::combine;
306
307 // HashState::combine_contiguous()
308 //
309 // Combines a contiguous array of `size` elements into a hash state, returning
310 // the updated state.
combine_contiguous(HashState hash_state,const unsigned char * first,size_t size)311 static HashState combine_contiguous(HashState hash_state,
312 const unsigned char* first, size_t size) {
313 hash_state.combine_contiguous_(hash_state.state_, first, size);
314 return hash_state;
315 }
316 using HashState::HashStateBase::combine_contiguous;
317
318 private:
319 HashState() = default;
320
321 template <typename T>
CombineContiguousImpl(void * p,const unsigned char * first,size_t size)322 static void CombineContiguousImpl(void* p, const unsigned char* first,
323 size_t size) {
324 T& state = *static_cast<T*>(p);
325 state = T::combine_contiguous(std::move(state), first, size);
326 }
327
328 template <typename T>
Init(T * state)329 void Init(T* state) {
330 state_ = state;
331 combine_contiguous_ = &CombineContiguousImpl<T>;
332 }
333
334 // Do not erase an already erased state.
Init(HashState * state)335 void Init(HashState* state) {
336 state_ = state->state_;
337 combine_contiguous_ = state->combine_contiguous_;
338 }
339
340 void* state_;
341 void (*combine_contiguous_)(void*, const unsigned char*, size_t);
342 };
343
344 ABSL_NAMESPACE_END
345 } // namespace absl
346
347 #endif // ABSL_HASH_HASH_H_
348