/src/LPM/external.protobuf/include/absl/hash/internal/hash.h
Line | Count | Source (jump to first uncovered line) |
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 | | #ifndef ABSL_HASH_INTERNAL_HASH_H_ |
20 | | #define ABSL_HASH_INTERNAL_HASH_H_ |
21 | | |
22 | | #include <algorithm> |
23 | | #include <array> |
24 | | #include <bitset> |
25 | | #include <cmath> |
26 | | #include <cstddef> |
27 | | #include <cstring> |
28 | | #include <deque> |
29 | | #include <forward_list> |
30 | | #include <functional> |
31 | | #include <iterator> |
32 | | #include <limits> |
33 | | #include <list> |
34 | | #include <map> |
35 | | #include <memory> |
36 | | #include <set> |
37 | | #include <string> |
38 | | #include <tuple> |
39 | | #include <type_traits> |
40 | | #include <unordered_map> |
41 | | #include <unordered_set> |
42 | | #include <utility> |
43 | | #include <vector> |
44 | | |
45 | | #include "absl/base/config.h" |
46 | | #include "absl/base/internal/unaligned_access.h" |
47 | | #include "absl/base/port.h" |
48 | | #include "absl/container/fixed_array.h" |
49 | | #include "absl/hash/internal/city.h" |
50 | | #include "absl/hash/internal/low_level_hash.h" |
51 | | #include "absl/meta/type_traits.h" |
52 | | #include "absl/numeric/bits.h" |
53 | | #include "absl/numeric/int128.h" |
54 | | #include "absl/strings/string_view.h" |
55 | | #include "absl/types/optional.h" |
56 | | #include "absl/types/variant.h" |
57 | | #include "absl/utility/utility.h" |
58 | | |
59 | | namespace absl { |
60 | | ABSL_NAMESPACE_BEGIN |
61 | | |
62 | | class HashState; |
63 | | |
64 | | namespace hash_internal { |
65 | | |
66 | | // Internal detail: Large buffers are hashed in smaller chunks. This function |
67 | | // returns the size of these chunks. |
68 | 0 | constexpr size_t PiecewiseChunkSize() { return 1024; } |
69 | | |
70 | | // PiecewiseCombiner |
71 | | // |
72 | | // PiecewiseCombiner is an internal-only helper class for hashing a piecewise |
73 | | // buffer of `char` or `unsigned char` as though it were contiguous. This class |
74 | | // provides two methods: |
75 | | // |
76 | | // H add_buffer(state, data, size) |
77 | | // H finalize(state) |
78 | | // |
79 | | // `add_buffer` can be called zero or more times, followed by a single call to |
80 | | // `finalize`. This will produce the same hash expansion as concatenating each |
81 | | // buffer piece into a single contiguous buffer, and passing this to |
82 | | // `H::combine_contiguous`. |
83 | | // |
84 | | // Example usage: |
85 | | // PiecewiseCombiner combiner; |
86 | | // for (const auto& piece : pieces) { |
87 | | // state = combiner.add_buffer(std::move(state), piece.data, piece.size); |
88 | | // } |
89 | | // return combiner.finalize(std::move(state)); |
90 | | class PiecewiseCombiner { |
91 | | public: |
92 | 0 | PiecewiseCombiner() : position_(0) {} |
93 | | PiecewiseCombiner(const PiecewiseCombiner&) = delete; |
94 | | PiecewiseCombiner& operator=(const PiecewiseCombiner&) = delete; |
95 | | |
96 | | // PiecewiseCombiner::add_buffer() |
97 | | // |
98 | | // Appends the given range of bytes to the sequence to be hashed, which may |
99 | | // modify the provided hash state. |
100 | | template <typename H> |
101 | | H add_buffer(H state, const unsigned char* data, size_t size); |
102 | | template <typename H> |
103 | 0 | H add_buffer(H state, const char* data, size_t size) { |
104 | 0 | return add_buffer(std::move(state), |
105 | 0 | reinterpret_cast<const unsigned char*>(data), size); |
106 | 0 | } |
107 | | |
108 | | // PiecewiseCombiner::finalize() |
109 | | // |
110 | | // Finishes combining the hash sequence, which may may modify the provided |
111 | | // hash state. |
112 | | // |
113 | | // Once finalize() is called, add_buffer() may no longer be called. The |
114 | | // resulting hash state will be the same as if the pieces passed to |
115 | | // add_buffer() were concatenated into a single flat buffer, and then provided |
116 | | // to H::combine_contiguous(). |
117 | | template <typename H> |
118 | | H finalize(H state); |
119 | | |
120 | | private: |
121 | | unsigned char buf_[PiecewiseChunkSize()]; |
122 | | size_t position_; |
123 | | }; |
124 | | |
125 | | // is_hashable() |
126 | | // |
127 | | // Trait class which returns true if T is hashable by the absl::Hash framework. |
128 | | // Used for the AbslHashValue implementations for composite types below. |
129 | | template <typename T> |
130 | | struct is_hashable; |
131 | | |
132 | | // HashStateBase |
133 | | // |
134 | | // An internal implementation detail that contains common implementation details |
135 | | // for all of the "hash state objects" objects generated by Abseil. This is not |
136 | | // a public API; users should not create classes that inherit from this. |
137 | | // |
138 | | // A hash state object is the template argument `H` passed to `AbslHashValue`. |
139 | | // It represents an intermediate state in the computation of an unspecified hash |
140 | | // algorithm. `HashStateBase` provides a CRTP style base class for hash state |
141 | | // implementations. Developers adding type support for `absl::Hash` should not |
142 | | // rely on any parts of the state object other than the following member |
143 | | // functions: |
144 | | // |
145 | | // * HashStateBase::combine() |
146 | | // * HashStateBase::combine_contiguous() |
147 | | // * HashStateBase::combine_unordered() |
148 | | // |
149 | | // A derived hash state class of type `H` must provide a public member function |
150 | | // with a signature similar to the following: |
151 | | // |
152 | | // `static H combine_contiguous(H state, const unsigned char*, size_t)`. |
153 | | // |
154 | | // It must also provide a private template method named RunCombineUnordered. |
155 | | // |
156 | | // A "consumer" is a 1-arg functor returning void. Its argument is a reference |
157 | | // to an inner hash state object, and it may be called multiple times. When |
158 | | // called, the functor consumes the entropy from the provided state object, |
159 | | // and resets that object to its empty state. |
160 | | // |
161 | | // A "combiner" is a stateless 2-arg functor returning void. Its arguments are |
162 | | // an inner hash state object and an ElementStateConsumer functor. A combiner |
163 | | // uses the provided inner hash state object to hash each element of the |
164 | | // container, passing the inner hash state object to the consumer after hashing |
165 | | // each element. |
166 | | // |
167 | | // Given these definitions, a derived hash state class of type H |
168 | | // must provide a private template method with a signature similar to the |
169 | | // following: |
170 | | // |
171 | | // `template <typename CombinerT>` |
172 | | // `static H RunCombineUnordered(H outer_state, CombinerT combiner)` |
173 | | // |
174 | | // This function is responsible for constructing the inner state object and |
175 | | // providing a consumer to the combiner. It uses side effects of the consumer |
176 | | // and combiner to mix the state of each element in an order-independent manner, |
177 | | // and uses this to return an updated value of `outer_state`. |
178 | | // |
179 | | // This inside-out approach generates efficient object code in the normal case, |
180 | | // but allows us to use stack storage to implement the absl::HashState type |
181 | | // erasure mechanism (avoiding heap allocations while hashing). |
182 | | // |
183 | | // `HashStateBase` will provide a complete implementation for a hash state |
184 | | // object in terms of these two methods. |
185 | | // |
186 | | // Example: |
187 | | // |
188 | | // // Use CRTP to define your derived class. |
189 | | // struct MyHashState : HashStateBase<MyHashState> { |
190 | | // static H combine_contiguous(H state, const unsigned char*, size_t); |
191 | | // using MyHashState::HashStateBase::combine; |
192 | | // using MyHashState::HashStateBase::combine_contiguous; |
193 | | // using MyHashState::HashStateBase::combine_unordered; |
194 | | // private: |
195 | | // template <typename CombinerT> |
196 | | // static H RunCombineUnordered(H state, CombinerT combiner); |
197 | | // }; |
198 | | template <typename H> |
199 | | class HashStateBase { |
200 | | public: |
201 | | // HashStateBase::combine() |
202 | | // |
203 | | // Combines an arbitrary number of values into a hash state, returning the |
204 | | // updated state. |
205 | | // |
206 | | // Each of the value types `T` must be separately hashable by the Abseil |
207 | | // hashing framework. |
208 | | // |
209 | | // NOTE: |
210 | | // |
211 | | // state = H::combine(std::move(state), value1, value2, value3); |
212 | | // |
213 | | // is guaranteed to produce the same hash expansion as: |
214 | | // |
215 | | // state = H::combine(std::move(state), value1); |
216 | | // state = H::combine(std::move(state), value2); |
217 | | // state = H::combine(std::move(state), value3); |
218 | | template <typename T, typename... Ts> |
219 | | static H combine(H state, const T& value, const Ts&... values); |
220 | 0 | static H combine(H state) { return state; } |
221 | | |
222 | | // HashStateBase::combine_contiguous() |
223 | | // |
224 | | // Combines a contiguous array of `size` elements into a hash state, returning |
225 | | // the updated state. |
226 | | // |
227 | | // NOTE: |
228 | | // |
229 | | // state = H::combine_contiguous(std::move(state), data, size); |
230 | | // |
231 | | // is NOT guaranteed to produce the same hash expansion as a for-loop (it may |
232 | | // perform internal optimizations). If you need this guarantee, use the |
233 | | // for-loop instead. |
234 | | template <typename T> |
235 | | static H combine_contiguous(H state, const T* data, size_t size); |
236 | | |
237 | | template <typename I> |
238 | | static H combine_unordered(H state, I begin, I end); |
239 | | |
240 | | using AbslInternalPiecewiseCombiner = PiecewiseCombiner; |
241 | | |
242 | | template <typename T> |
243 | | using is_hashable = absl::hash_internal::is_hashable<T>; |
244 | | |
245 | | private: |
246 | | // Common implementation of the iteration step of a "combiner", as described |
247 | | // above. |
248 | | template <typename I> |
249 | | struct CombineUnorderedCallback { |
250 | | I begin; |
251 | | I end; |
252 | | |
253 | | template <typename InnerH, typename ElementStateConsumer> |
254 | | void operator()(InnerH inner_state, ElementStateConsumer cb) { |
255 | | for (; begin != end; ++begin) { |
256 | | inner_state = H::combine(std::move(inner_state), *begin); |
257 | | cb(inner_state); |
258 | | } |
259 | | } |
260 | | }; |
261 | | }; |
262 | | |
263 | | // is_uniquely_represented |
264 | | // |
265 | | // `is_uniquely_represented<T>` is a trait class that indicates whether `T` |
266 | | // is uniquely represented. |
267 | | // |
268 | | // A type is "uniquely represented" if two equal values of that type are |
269 | | // guaranteed to have the same bytes in their underlying storage. In other |
270 | | // words, if `a == b`, then `memcmp(&a, &b, sizeof(T))` is guaranteed to be |
271 | | // zero. This property cannot be detected automatically, so this trait is false |
272 | | // by default, but can be specialized by types that wish to assert that they are |
273 | | // uniquely represented. This makes them eligible for certain optimizations. |
274 | | // |
275 | | // If you have any doubt whatsoever, do not specialize this template. |
276 | | // The default is completely safe, and merely disables some optimizations |
277 | | // that will not matter for most types. Specializing this template, |
278 | | // on the other hand, can be very hazardous. |
279 | | // |
280 | | // To be uniquely represented, a type must not have multiple ways of |
281 | | // representing the same value; for example, float and double are not |
282 | | // uniquely represented, because they have distinct representations for |
283 | | // +0 and -0. Furthermore, the type's byte representation must consist |
284 | | // solely of user-controlled data, with no padding bits and no compiler- |
285 | | // controlled data such as vptrs or sanitizer metadata. This is usually |
286 | | // very difficult to guarantee, because in most cases the compiler can |
287 | | // insert data and padding bits at its own discretion. |
288 | | // |
289 | | // If you specialize this template for a type `T`, you must do so in the file |
290 | | // that defines that type (or in this file). If you define that specialization |
291 | | // anywhere else, `is_uniquely_represented<T>` could have different meanings |
292 | | // in different places. |
293 | | // |
294 | | // The Enable parameter is meaningless; it is provided as a convenience, |
295 | | // to support certain SFINAE techniques when defining specializations. |
296 | | template <typename T, typename Enable = void> |
297 | | struct is_uniquely_represented : std::false_type {}; |
298 | | |
299 | | // is_uniquely_represented<unsigned char> |
300 | | // |
301 | | // unsigned char is a synonym for "byte", so it is guaranteed to be |
302 | | // uniquely represented. |
303 | | template <> |
304 | | struct is_uniquely_represented<unsigned char> : std::true_type {}; |
305 | | |
306 | | // is_uniquely_represented for non-standard integral types |
307 | | // |
308 | | // Integral types other than bool should be uniquely represented on any |
309 | | // platform that this will plausibly be ported to. |
310 | | template <typename Integral> |
311 | | struct is_uniquely_represented< |
312 | | Integral, typename std::enable_if<std::is_integral<Integral>::value>::type> |
313 | | : std::true_type {}; |
314 | | |
315 | | // is_uniquely_represented<bool> |
316 | | // |
317 | | // |
318 | | template <> |
319 | | struct is_uniquely_represented<bool> : std::false_type {}; |
320 | | |
321 | | // hash_bytes() |
322 | | // |
323 | | // Convenience function that combines `hash_state` with the byte representation |
324 | | // of `value`. |
325 | | template <typename H, typename T> |
326 | 0 | H hash_bytes(H hash_state, const T& value) { |
327 | 0 | const unsigned char* start = reinterpret_cast<const unsigned char*>(&value); |
328 | 0 | return H::combine_contiguous(std::move(hash_state), start, sizeof(value)); |
329 | 0 | } |
330 | | |
331 | | // ----------------------------------------------------------------------------- |
332 | | // AbslHashValue for Basic Types |
333 | | // ----------------------------------------------------------------------------- |
334 | | |
335 | | // Note: Default `AbslHashValue` implementations live in `hash_internal`. This |
336 | | // allows us to block lexical scope lookup when doing an unqualified call to |
337 | | // `AbslHashValue` below. User-defined implementations of `AbslHashValue` can |
338 | | // only be found via ADL. |
339 | | |
340 | | // AbslHashValue() for hashing bool values |
341 | | // |
342 | | // We use SFINAE to ensure that this overload only accepts bool, not types that |
343 | | // are convertible to bool. |
344 | | template <typename H, typename B> |
345 | | typename std::enable_if<std::is_same<B, bool>::value, H>::type AbslHashValue( |
346 | | H hash_state, B value) { |
347 | | return H::combine(std::move(hash_state), |
348 | | static_cast<unsigned char>(value ? 1 : 0)); |
349 | | } |
350 | | |
351 | | // AbslHashValue() for hashing enum values |
352 | | template <typename H, typename Enum> |
353 | | typename std::enable_if<std::is_enum<Enum>::value, H>::type AbslHashValue( |
354 | | H hash_state, Enum e) { |
355 | | // In practice, we could almost certainly just invoke hash_bytes directly, |
356 | | // but it's possible that a sanitizer might one day want to |
357 | | // store data in the unused bits of an enum. To avoid that risk, we |
358 | | // convert to the underlying type before hashing. Hopefully this will get |
359 | | // optimized away; if not, we can reopen discussion with c-toolchain-team. |
360 | | return H::combine(std::move(hash_state), |
361 | | static_cast<typename std::underlying_type<Enum>::type>(e)); |
362 | | } |
363 | | // AbslHashValue() for hashing floating-point values |
364 | | template <typename H, typename Float> |
365 | | typename std::enable_if<std::is_same<Float, float>::value || |
366 | | std::is_same<Float, double>::value, |
367 | | H>::type |
368 | | AbslHashValue(H hash_state, Float value) { |
369 | | return hash_internal::hash_bytes(std::move(hash_state), |
370 | | value == 0 ? 0 : value); |
371 | | } |
372 | | |
373 | | // Long double has the property that it might have extra unused bytes in it. |
374 | | // For example, in x86 sizeof(long double)==16 but it only really uses 80-bits |
375 | | // of it. This means we can't use hash_bytes on a long double and have to |
376 | | // convert it to something else first. |
377 | | template <typename H, typename LongDouble> |
378 | | typename std::enable_if<std::is_same<LongDouble, long double>::value, H>::type |
379 | | AbslHashValue(H hash_state, LongDouble value) { |
380 | | const int category = std::fpclassify(value); |
381 | | switch (category) { |
382 | | case FP_INFINITE: |
383 | | // Add the sign bit to differentiate between +Inf and -Inf |
384 | | hash_state = H::combine(std::move(hash_state), std::signbit(value)); |
385 | | break; |
386 | | |
387 | | case FP_NAN: |
388 | | case FP_ZERO: |
389 | | default: |
390 | | // Category is enough for these. |
391 | | break; |
392 | | |
393 | | case FP_NORMAL: |
394 | | case FP_SUBNORMAL: |
395 | | // We can't convert `value` directly to double because this would have |
396 | | // undefined behavior if the value is out of range. |
397 | | // std::frexp gives us a value in the range (-1, -.5] or [.5, 1) that is |
398 | | // guaranteed to be in range for `double`. The truncation is |
399 | | // implementation defined, but that works as long as it is deterministic. |
400 | | int exp; |
401 | | auto mantissa = static_cast<double>(std::frexp(value, &exp)); |
402 | | hash_state = H::combine(std::move(hash_state), mantissa, exp); |
403 | | } |
404 | | |
405 | | return H::combine(std::move(hash_state), category); |
406 | | } |
407 | | |
408 | | // AbslHashValue() for hashing pointers |
409 | | template <typename H, typename T> |
410 | 0 | H AbslHashValue(H hash_state, T* ptr) { |
411 | 0 | auto v = reinterpret_cast<uintptr_t>(ptr); |
412 | 0 | // Due to alignment, pointers tend to have low bits as zero, and the next few |
413 | 0 | // bits follow a pattern since they are also multiples of some base value. |
414 | 0 | // Mixing the pointer twice helps prevent stuck low bits for certain alignment |
415 | 0 | // values. |
416 | 0 | return H::combine(std::move(hash_state), v, v); |
417 | 0 | } |
418 | | |
419 | | // AbslHashValue() for hashing nullptr_t |
420 | | template <typename H> |
421 | | H AbslHashValue(H hash_state, std::nullptr_t) { |
422 | | return H::combine(std::move(hash_state), static_cast<void*>(nullptr)); |
423 | | } |
424 | | |
425 | | // AbslHashValue() for hashing pointers-to-member |
426 | | template <typename H, typename T, typename C> |
427 | | H AbslHashValue(H hash_state, T C::* ptr) { |
428 | | auto salient_ptm_size = [](std::size_t n) -> std::size_t { |
429 | | #if defined(_MSC_VER) |
430 | | // Pointers-to-member-function on MSVC consist of one pointer plus 0, 1, 2, |
431 | | // or 3 ints. In 64-bit mode, they are 8-byte aligned and thus can contain |
432 | | // padding (namely when they have 1 or 3 ints). The value below is a lower |
433 | | // bound on the number of salient, non-padding bytes that we use for |
434 | | // hashing. |
435 | | if (alignof(T C::*) == alignof(int)) { |
436 | | // No padding when all subobjects have the same size as the total |
437 | | // alignment. This happens in 32-bit mode. |
438 | | return n; |
439 | | } else { |
440 | | // Padding for 1 int (size 16) or 3 ints (size 24). |
441 | | // With 2 ints, the size is 16 with no padding, which we pessimize. |
442 | | return n == 24 ? 20 : n == 16 ? 12 : n; |
443 | | } |
444 | | #else |
445 | | // On other platforms, we assume that pointers-to-members do not have |
446 | | // padding. |
447 | | #ifdef __cpp_lib_has_unique_object_representations |
448 | | static_assert(std::has_unique_object_representations<T C::*>::value); |
449 | | #endif // __cpp_lib_has_unique_object_representations |
450 | | return n; |
451 | | #endif |
452 | | }; |
453 | | return H::combine_contiguous(std::move(hash_state), |
454 | | reinterpret_cast<unsigned char*>(&ptr), |
455 | | salient_ptm_size(sizeof ptr)); |
456 | | } |
457 | | |
458 | | // ----------------------------------------------------------------------------- |
459 | | // AbslHashValue for Composite Types |
460 | | // ----------------------------------------------------------------------------- |
461 | | |
462 | | // AbslHashValue() for hashing pairs |
463 | | template <typename H, typename T1, typename T2> |
464 | | typename std::enable_if<is_hashable<T1>::value && is_hashable<T2>::value, |
465 | | H>::type |
466 | | AbslHashValue(H hash_state, const std::pair<T1, T2>& p) { |
467 | | return H::combine(std::move(hash_state), p.first, p.second); |
468 | | } |
469 | | |
470 | | // hash_tuple() |
471 | | // |
472 | | // Helper function for hashing a tuple. The third argument should |
473 | | // be an index_sequence running from 0 to tuple_size<Tuple> - 1. |
474 | | template <typename H, typename Tuple, size_t... Is> |
475 | | H hash_tuple(H hash_state, const Tuple& t, absl::index_sequence<Is...>) { |
476 | | return H::combine(std::move(hash_state), std::get<Is>(t)...); |
477 | | } |
478 | | |
479 | | // AbslHashValue for hashing tuples |
480 | | template <typename H, typename... Ts> |
481 | | #if defined(_MSC_VER) |
482 | | // This SFINAE gets MSVC confused under some conditions. Let's just disable it |
483 | | // for now. |
484 | | H |
485 | | #else // _MSC_VER |
486 | | typename std::enable_if<absl::conjunction<is_hashable<Ts>...>::value, H>::type |
487 | | #endif // _MSC_VER |
488 | | AbslHashValue(H hash_state, const std::tuple<Ts...>& t) { |
489 | | return hash_internal::hash_tuple(std::move(hash_state), t, |
490 | | absl::make_index_sequence<sizeof...(Ts)>()); |
491 | | } |
492 | | |
493 | | // ----------------------------------------------------------------------------- |
494 | | // AbslHashValue for Pointers |
495 | | // ----------------------------------------------------------------------------- |
496 | | |
497 | | // AbslHashValue for hashing unique_ptr |
498 | | template <typename H, typename T, typename D> |
499 | | H AbslHashValue(H hash_state, const std::unique_ptr<T, D>& ptr) { |
500 | | return H::combine(std::move(hash_state), ptr.get()); |
501 | | } |
502 | | |
503 | | // AbslHashValue for hashing shared_ptr |
504 | | template <typename H, typename T> |
505 | | H AbslHashValue(H hash_state, const std::shared_ptr<T>& ptr) { |
506 | | return H::combine(std::move(hash_state), ptr.get()); |
507 | | } |
508 | | |
509 | | // ----------------------------------------------------------------------------- |
510 | | // AbslHashValue for String-Like Types |
511 | | // ----------------------------------------------------------------------------- |
512 | | |
513 | | // AbslHashValue for hashing strings |
514 | | // |
515 | | // All the string-like types supported here provide the same hash expansion for |
516 | | // the same character sequence. These types are: |
517 | | // |
518 | | // - `absl::Cord` |
519 | | // - `std::string` (and std::basic_string<char, std::char_traits<char>, A> for |
520 | | // any allocator A) |
521 | | // - `absl::string_view` and `std::string_view` |
522 | | // |
523 | | // For simplicity, we currently support only `char` strings. This support may |
524 | | // be broadened, if necessary, but with some caution - this overload would |
525 | | // misbehave in cases where the traits' `eq()` member isn't equivalent to `==` |
526 | | // on the underlying character type. |
527 | | template <typename H> |
528 | 0 | H AbslHashValue(H hash_state, absl::string_view str) { |
529 | 0 | return H::combine( |
530 | 0 | H::combine_contiguous(std::move(hash_state), str.data(), str.size()), |
531 | 0 | str.size()); |
532 | 0 | } |
533 | | |
534 | | // Support std::wstring, std::u16string and std::u32string. |
535 | | template <typename Char, typename Alloc, typename H, |
536 | | typename = absl::enable_if_t<std::is_same<Char, wchar_t>::value || |
537 | | std::is_same<Char, char16_t>::value || |
538 | | std::is_same<Char, char32_t>::value>> |
539 | | H AbslHashValue( |
540 | | H hash_state, |
541 | | const std::basic_string<Char, std::char_traits<Char>, Alloc>& str) { |
542 | | return H::combine( |
543 | | H::combine_contiguous(std::move(hash_state), str.data(), str.size()), |
544 | | str.size()); |
545 | | } |
546 | | |
547 | | // ----------------------------------------------------------------------------- |
548 | | // AbslHashValue for Sequence Containers |
549 | | // ----------------------------------------------------------------------------- |
550 | | |
551 | | // AbslHashValue for hashing std::array |
552 | | template <typename H, typename T, size_t N> |
553 | | typename std::enable_if<is_hashable<T>::value, H>::type AbslHashValue( |
554 | | H hash_state, const std::array<T, N>& array) { |
555 | | return H::combine_contiguous(std::move(hash_state), array.data(), |
556 | | array.size()); |
557 | | } |
558 | | |
559 | | // AbslHashValue for hashing std::deque |
560 | | template <typename H, typename T, typename Allocator> |
561 | | typename std::enable_if<is_hashable<T>::value, H>::type AbslHashValue( |
562 | | H hash_state, const std::deque<T, Allocator>& deque) { |
563 | | // TODO(gromer): investigate a more efficient implementation taking |
564 | | // advantage of the chunk structure. |
565 | | for (const auto& t : deque) { |
566 | | hash_state = H::combine(std::move(hash_state), t); |
567 | | } |
568 | | return H::combine(std::move(hash_state), deque.size()); |
569 | | } |
570 | | |
571 | | // AbslHashValue for hashing std::forward_list |
572 | | template <typename H, typename T, typename Allocator> |
573 | | typename std::enable_if<is_hashable<T>::value, H>::type AbslHashValue( |
574 | | H hash_state, const std::forward_list<T, Allocator>& list) { |
575 | | size_t size = 0; |
576 | | for (const T& t : list) { |
577 | | hash_state = H::combine(std::move(hash_state), t); |
578 | | ++size; |
579 | | } |
580 | | return H::combine(std::move(hash_state), size); |
581 | | } |
582 | | |
583 | | // AbslHashValue for hashing std::list |
584 | | template <typename H, typename T, typename Allocator> |
585 | | typename std::enable_if<is_hashable<T>::value, H>::type AbslHashValue( |
586 | | H hash_state, const std::list<T, Allocator>& list) { |
587 | | for (const auto& t : list) { |
588 | | hash_state = H::combine(std::move(hash_state), t); |
589 | | } |
590 | | return H::combine(std::move(hash_state), list.size()); |
591 | | } |
592 | | |
593 | | // AbslHashValue for hashing std::vector |
594 | | // |
595 | | // Do not use this for vector<bool> on platforms that have a working |
596 | | // implementation of std::hash. It does not have a .data(), and a fallback for |
597 | | // std::hash<> is most likely faster. |
598 | | template <typename H, typename T, typename Allocator> |
599 | | typename std::enable_if<is_hashable<T>::value && !std::is_same<T, bool>::value, |
600 | | H>::type |
601 | | AbslHashValue(H hash_state, const std::vector<T, Allocator>& vector) { |
602 | | return H::combine(H::combine_contiguous(std::move(hash_state), vector.data(), |
603 | | vector.size()), |
604 | | vector.size()); |
605 | | } |
606 | | |
607 | | // AbslHashValue special cases for hashing std::vector<bool> |
608 | | |
609 | | #if defined(ABSL_IS_BIG_ENDIAN) && \ |
610 | | (defined(__GLIBCXX__) || defined(__GLIBCPP__)) |
611 | | |
612 | | // std::hash in libstdc++ does not work correctly with vector<bool> on Big |
613 | | // Endian platforms therefore we need to implement a custom AbslHashValue for |
614 | | // it. More details on the bug: |
615 | | // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102531 |
616 | | template <typename H, typename T, typename Allocator> |
617 | | typename std::enable_if<is_hashable<T>::value && std::is_same<T, bool>::value, |
618 | | H>::type |
619 | | AbslHashValue(H hash_state, const std::vector<T, Allocator>& vector) { |
620 | | typename H::AbslInternalPiecewiseCombiner combiner; |
621 | | for (const auto& i : vector) { |
622 | | unsigned char c = static_cast<unsigned char>(i); |
623 | | hash_state = combiner.add_buffer(std::move(hash_state), &c, sizeof(c)); |
624 | | } |
625 | | return H::combine(combiner.finalize(std::move(hash_state)), vector.size()); |
626 | | } |
627 | | #else |
628 | | // When not working around the libstdc++ bug above, we still have to contend |
629 | | // with the fact that std::hash<vector<bool>> is often poor quality, hashing |
630 | | // directly on the internal words and on no other state. On these platforms, |
631 | | // vector<bool>{1, 1} and vector<bool>{1, 1, 0} hash to the same value. |
632 | | // |
633 | | // Mixing in the size (as we do in our other vector<> implementations) on top |
634 | | // of the library-provided hash implementation avoids this QOI issue. |
635 | | template <typename H, typename T, typename Allocator> |
636 | | typename std::enable_if<is_hashable<T>::value && std::is_same<T, bool>::value, |
637 | | H>::type |
638 | | AbslHashValue(H hash_state, const std::vector<T, Allocator>& vector) { |
639 | | return H::combine(std::move(hash_state), |
640 | | std::hash<std::vector<T, Allocator>>{}(vector), |
641 | | vector.size()); |
642 | | } |
643 | | #endif |
644 | | |
645 | | // ----------------------------------------------------------------------------- |
646 | | // AbslHashValue for Ordered Associative Containers |
647 | | // ----------------------------------------------------------------------------- |
648 | | |
649 | | // AbslHashValue for hashing std::map |
650 | | template <typename H, typename Key, typename T, typename Compare, |
651 | | typename Allocator> |
652 | | typename std::enable_if<is_hashable<Key>::value && is_hashable<T>::value, |
653 | | H>::type |
654 | | AbslHashValue(H hash_state, const std::map<Key, T, Compare, Allocator>& map) { |
655 | | for (const auto& t : map) { |
656 | | hash_state = H::combine(std::move(hash_state), t); |
657 | | } |
658 | | return H::combine(std::move(hash_state), map.size()); |
659 | | } |
660 | | |
661 | | // AbslHashValue for hashing std::multimap |
662 | | template <typename H, typename Key, typename T, typename Compare, |
663 | | typename Allocator> |
664 | | typename std::enable_if<is_hashable<Key>::value && is_hashable<T>::value, |
665 | | H>::type |
666 | | AbslHashValue(H hash_state, |
667 | | const std::multimap<Key, T, Compare, Allocator>& map) { |
668 | | for (const auto& t : map) { |
669 | | hash_state = H::combine(std::move(hash_state), t); |
670 | | } |
671 | | return H::combine(std::move(hash_state), map.size()); |
672 | | } |
673 | | |
674 | | // AbslHashValue for hashing std::set |
675 | | template <typename H, typename Key, typename Compare, typename Allocator> |
676 | | typename std::enable_if<is_hashable<Key>::value, H>::type AbslHashValue( |
677 | | H hash_state, const std::set<Key, Compare, Allocator>& set) { |
678 | | for (const auto& t : set) { |
679 | | hash_state = H::combine(std::move(hash_state), t); |
680 | | } |
681 | | return H::combine(std::move(hash_state), set.size()); |
682 | | } |
683 | | |
684 | | // AbslHashValue for hashing std::multiset |
685 | | template <typename H, typename Key, typename Compare, typename Allocator> |
686 | | typename std::enable_if<is_hashable<Key>::value, H>::type AbslHashValue( |
687 | | H hash_state, const std::multiset<Key, Compare, Allocator>& set) { |
688 | | for (const auto& t : set) { |
689 | | hash_state = H::combine(std::move(hash_state), t); |
690 | | } |
691 | | return H::combine(std::move(hash_state), set.size()); |
692 | | } |
693 | | |
694 | | // ----------------------------------------------------------------------------- |
695 | | // AbslHashValue for Unordered Associative Containers |
696 | | // ----------------------------------------------------------------------------- |
697 | | |
698 | | // AbslHashValue for hashing std::unordered_set |
699 | | template <typename H, typename Key, typename Hash, typename KeyEqual, |
700 | | typename Alloc> |
701 | | typename std::enable_if<is_hashable<Key>::value, H>::type AbslHashValue( |
702 | | H hash_state, const std::unordered_set<Key, Hash, KeyEqual, Alloc>& s) { |
703 | | return H::combine( |
704 | | H::combine_unordered(std::move(hash_state), s.begin(), s.end()), |
705 | | s.size()); |
706 | | } |
707 | | |
708 | | // AbslHashValue for hashing std::unordered_multiset |
709 | | template <typename H, typename Key, typename Hash, typename KeyEqual, |
710 | | typename Alloc> |
711 | | typename std::enable_if<is_hashable<Key>::value, H>::type AbslHashValue( |
712 | | H hash_state, |
713 | | const std::unordered_multiset<Key, Hash, KeyEqual, Alloc>& s) { |
714 | | return H::combine( |
715 | | H::combine_unordered(std::move(hash_state), s.begin(), s.end()), |
716 | | s.size()); |
717 | | } |
718 | | |
719 | | // AbslHashValue for hashing std::unordered_set |
720 | | template <typename H, typename Key, typename T, typename Hash, |
721 | | typename KeyEqual, typename Alloc> |
722 | | typename std::enable_if<is_hashable<Key>::value && is_hashable<T>::value, |
723 | | H>::type |
724 | | AbslHashValue(H hash_state, |
725 | | const std::unordered_map<Key, T, Hash, KeyEqual, Alloc>& s) { |
726 | | return H::combine( |
727 | | H::combine_unordered(std::move(hash_state), s.begin(), s.end()), |
728 | | s.size()); |
729 | | } |
730 | | |
731 | | // AbslHashValue for hashing std::unordered_multiset |
732 | | template <typename H, typename Key, typename T, typename Hash, |
733 | | typename KeyEqual, typename Alloc> |
734 | | typename std::enable_if<is_hashable<Key>::value && is_hashable<T>::value, |
735 | | H>::type |
736 | | AbslHashValue(H hash_state, |
737 | | const std::unordered_multimap<Key, T, Hash, KeyEqual, Alloc>& s) { |
738 | | return H::combine( |
739 | | H::combine_unordered(std::move(hash_state), s.begin(), s.end()), |
740 | | s.size()); |
741 | | } |
742 | | |
743 | | // ----------------------------------------------------------------------------- |
744 | | // AbslHashValue for Wrapper Types |
745 | | // ----------------------------------------------------------------------------- |
746 | | |
747 | | // AbslHashValue for hashing std::reference_wrapper |
748 | | template <typename H, typename T> |
749 | | typename std::enable_if<is_hashable<T>::value, H>::type AbslHashValue( |
750 | | H hash_state, std::reference_wrapper<T> opt) { |
751 | | return H::combine(std::move(hash_state), opt.get()); |
752 | | } |
753 | | |
754 | | // AbslHashValue for hashing absl::optional |
755 | | template <typename H, typename T> |
756 | | typename std::enable_if<is_hashable<T>::value, H>::type AbslHashValue( |
757 | | H hash_state, const absl::optional<T>& opt) { |
758 | | if (opt) hash_state = H::combine(std::move(hash_state), *opt); |
759 | | return H::combine(std::move(hash_state), opt.has_value()); |
760 | | } |
761 | | |
762 | | // VariantVisitor |
763 | | template <typename H> |
764 | | struct VariantVisitor { |
765 | | H&& hash_state; |
766 | | template <typename T> |
767 | | H operator()(const T& t) const { |
768 | | return H::combine(std::move(hash_state), t); |
769 | | } |
770 | | }; |
771 | | |
772 | | // AbslHashValue for hashing absl::variant |
773 | | template <typename H, typename... T> |
774 | | typename std::enable_if<conjunction<is_hashable<T>...>::value, H>::type |
775 | | AbslHashValue(H hash_state, const absl::variant<T...>& v) { |
776 | | if (!v.valueless_by_exception()) { |
777 | | hash_state = absl::visit(VariantVisitor<H>{std::move(hash_state)}, v); |
778 | | } |
779 | | return H::combine(std::move(hash_state), v.index()); |
780 | | } |
781 | | |
782 | | // ----------------------------------------------------------------------------- |
783 | | // AbslHashValue for Other Types |
784 | | // ----------------------------------------------------------------------------- |
785 | | |
786 | | // AbslHashValue for hashing std::bitset is not defined on Little Endian |
787 | | // platforms, for the same reason as for vector<bool> (see std::vector above): |
788 | | // It does not expose the raw bytes, and a fallback to std::hash<> is most |
789 | | // likely faster. |
790 | | |
791 | | #if defined(ABSL_IS_BIG_ENDIAN) && \ |
792 | | (defined(__GLIBCXX__) || defined(__GLIBCPP__)) |
793 | | // AbslHashValue for hashing std::bitset |
794 | | // |
795 | | // std::hash in libstdc++ does not work correctly with std::bitset on Big Endian |
796 | | // platforms therefore we need to implement a custom AbslHashValue for it. More |
797 | | // details on the bug: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102531 |
798 | | template <typename H, size_t N> |
799 | | H AbslHashValue(H hash_state, const std::bitset<N>& set) { |
800 | | typename H::AbslInternalPiecewiseCombiner combiner; |
801 | | for (int i = 0; i < N; i++) { |
802 | | unsigned char c = static_cast<unsigned char>(set[i]); |
803 | | hash_state = combiner.add_buffer(std::move(hash_state), &c, sizeof(c)); |
804 | | } |
805 | | return H::combine(combiner.finalize(std::move(hash_state)), N); |
806 | | } |
807 | | #endif |
808 | | |
809 | | // ----------------------------------------------------------------------------- |
810 | | |
811 | | // hash_range_or_bytes() |
812 | | // |
813 | | // Mixes all values in the range [data, data+size) into the hash state. |
814 | | // This overload accepts only uniquely-represented types, and hashes them by |
815 | | // hashing the entire range of bytes. |
816 | | template <typename H, typename T> |
817 | | typename std::enable_if<is_uniquely_represented<T>::value, H>::type |
818 | 0 | hash_range_or_bytes(H hash_state, const T* data, size_t size) { |
819 | 0 | const auto* bytes = reinterpret_cast<const unsigned char*>(data); |
820 | 0 | return H::combine_contiguous(std::move(hash_state), bytes, sizeof(T) * size); |
821 | 0 | } |
822 | | |
823 | | // hash_range_or_bytes() |
824 | | template <typename H, typename T> |
825 | | typename std::enable_if<!is_uniquely_represented<T>::value, H>::type |
826 | | hash_range_or_bytes(H hash_state, const T* data, size_t size) { |
827 | | for (const auto end = data + size; data < end; ++data) { |
828 | | hash_state = H::combine(std::move(hash_state), *data); |
829 | | } |
830 | | return hash_state; |
831 | | } |
832 | | |
833 | | #if defined(ABSL_INTERNAL_LEGACY_HASH_NAMESPACE) && \ |
834 | | ABSL_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_ |
835 | | #define ABSL_HASH_INTERNAL_SUPPORT_LEGACY_HASH_ 1 |
836 | | #else |
837 | | #define ABSL_HASH_INTERNAL_SUPPORT_LEGACY_HASH_ 0 |
838 | | #endif |
839 | | |
840 | | // HashSelect |
841 | | // |
842 | | // Type trait to select the appropriate hash implementation to use. |
843 | | // HashSelect::type<T> will give the proper hash implementation, to be invoked |
844 | | // as: |
845 | | // HashSelect::type<T>::Invoke(state, value) |
846 | | // Also, HashSelect::type<T>::value is a boolean equal to `true` if there is a |
847 | | // valid `Invoke` function. Types that are not hashable will have a ::value of |
848 | | // `false`. |
849 | | struct HashSelect { |
850 | | private: |
851 | | struct State : HashStateBase<State> { |
852 | | static State combine_contiguous(State hash_state, const unsigned char*, |
853 | | size_t); |
854 | | using State::HashStateBase::combine_contiguous; |
855 | | }; |
856 | | |
857 | | struct UniquelyRepresentedProbe { |
858 | | template <typename H, typename T> |
859 | | static auto Invoke(H state, const T& value) |
860 | 0 | -> absl::enable_if_t<is_uniquely_represented<T>::value, H> { |
861 | 0 | return hash_internal::hash_bytes(std::move(state), value); |
862 | 0 | } |
863 | | }; |
864 | | |
865 | | struct HashValueProbe { |
866 | | template <typename H, typename T> |
867 | | static auto Invoke(H state, const T& value) -> absl::enable_if_t< |
868 | | std::is_same<H, |
869 | | decltype(AbslHashValue(std::move(state), value))>::value, |
870 | 0 | H> { |
871 | 0 | return AbslHashValue(std::move(state), value); |
872 | 0 | } Unexecuted instantiation: _ZN4absl12lts_2023012513hash_internal10HashSelect14HashValueProbe6InvokeINS1_15MixingHashStateENS0_11string_viewEEENSt3__19enable_ifIXsr3std7is_sameIT_DTcl13AbslHashValueclsr3stdE4movefp_Efp0_EEEE5valueES9_E4typeES9_RKT0_ Unexecuted instantiation: _ZN4absl12lts_2023012513hash_internal10HashSelect14HashValueProbe6InvokeINS1_15MixingHashStateENS0_4CordEEENSt3__19enable_ifIXsr3std7is_sameIT_DTcl13AbslHashValueclsr3stdE4movefp_Efp0_EEEE5valueES9_E4typeES9_RKT0_ Unexecuted instantiation: _ZN4absl12lts_2023012513hash_internal10HashSelect14HashValueProbe6InvokeINS1_15MixingHashStateEPKN6google8protobuf15FieldDescriptorEEENSt3__19enable_ifIXsr3std7is_sameIT_DTcl13AbslHashValueclsr3stdE4movefp_Efp0_EEEE5valueESD_E4typeESD_RKT0_ |
873 | | }; |
874 | | |
875 | | struct LegacyHashProbe { |
876 | | #if ABSL_HASH_INTERNAL_SUPPORT_LEGACY_HASH_ |
877 | | template <typename H, typename T> |
878 | | static auto Invoke(H state, const T& value) -> absl::enable_if_t< |
879 | | std::is_convertible< |
880 | | decltype(ABSL_INTERNAL_LEGACY_HASH_NAMESPACE::hash<T>()(value)), |
881 | | size_t>::value, |
882 | | H> { |
883 | | return hash_internal::hash_bytes( |
884 | | std::move(state), |
885 | | ABSL_INTERNAL_LEGACY_HASH_NAMESPACE::hash<T>{}(value)); |
886 | | } |
887 | | #endif // ABSL_HASH_INTERNAL_SUPPORT_LEGACY_HASH_ |
888 | | }; |
889 | | |
890 | | struct StdHashProbe { |
891 | | template <typename H, typename T> |
892 | | static auto Invoke(H state, const T& value) |
893 | | -> absl::enable_if_t<type_traits_internal::IsHashable<T>::value, H> { |
894 | | return hash_internal::hash_bytes(std::move(state), std::hash<T>{}(value)); |
895 | | } |
896 | | }; |
897 | | |
898 | | template <typename Hash, typename T> |
899 | | struct Probe : Hash { |
900 | | private: |
901 | | template <typename H, typename = decltype(H::Invoke( |
902 | | std::declval<State>(), std::declval<const T&>()))> |
903 | | static std::true_type Test(int); |
904 | | template <typename U> |
905 | | static std::false_type Test(char); |
906 | | |
907 | | public: |
908 | | static constexpr bool value = decltype(Test<Hash>(0))::value; |
909 | | }; |
910 | | |
911 | | public: |
912 | | // Probe each implementation in order. |
913 | | // disjunction provides short circuiting wrt instantiation. |
914 | | template <typename T> |
915 | | using Apply = absl::disjunction< // |
916 | | Probe<UniquelyRepresentedProbe, T>, // |
917 | | Probe<HashValueProbe, T>, // |
918 | | Probe<LegacyHashProbe, T>, // |
919 | | Probe<StdHashProbe, T>, // |
920 | | std::false_type>; |
921 | | }; |
922 | | |
923 | | template <typename T> |
924 | | struct is_hashable |
925 | | : std::integral_constant<bool, HashSelect::template Apply<T>::value> {}; |
926 | | |
927 | | // MixingHashState |
928 | | class ABSL_DLL MixingHashState : public HashStateBase<MixingHashState> { |
929 | | // absl::uint128 is not an alias or a thin wrapper around the intrinsic. |
930 | | // We use the intrinsic when available to improve performance. |
931 | | #ifdef ABSL_HAVE_INTRINSIC_INT128 |
932 | | using uint128 = __uint128_t; |
933 | | #else // ABSL_HAVE_INTRINSIC_INT128 |
934 | | using uint128 = absl::uint128; |
935 | | #endif // ABSL_HAVE_INTRINSIC_INT128 |
936 | | |
937 | | static constexpr uint64_t kMul = |
938 | | sizeof(size_t) == 4 ? uint64_t{0xcc9e2d51} |
939 | | : uint64_t{0x9ddfea08eb382d69}; |
940 | | |
941 | | template <typename T> |
942 | | using IntegralFastPath = |
943 | | conjunction<std::is_integral<T>, is_uniquely_represented<T>>; |
944 | | |
945 | | public: |
946 | | // Move only |
947 | | MixingHashState(MixingHashState&&) = default; |
948 | | MixingHashState& operator=(MixingHashState&&) = default; |
949 | | |
950 | | // MixingHashState::combine_contiguous() |
951 | | // |
952 | | // Fundamental base case for hash recursion: mixes the given range of bytes |
953 | | // into the hash state. |
954 | | static MixingHashState combine_contiguous(MixingHashState hash_state, |
955 | | const unsigned char* first, |
956 | 0 | size_t size) { |
957 | 0 | return MixingHashState( |
958 | 0 | CombineContiguousImpl(hash_state.state_, first, size, |
959 | 0 | std::integral_constant<int, sizeof(size_t)>{})); |
960 | 0 | } |
961 | | using MixingHashState::HashStateBase::combine_contiguous; |
962 | | |
963 | | // MixingHashState::hash() |
964 | | // |
965 | | // For performance reasons in non-opt mode, we specialize this for |
966 | | // integral types. |
967 | | // Otherwise we would be instantiating and calling dozens of functions for |
968 | | // something that is just one multiplication and a couple xor's. |
969 | | // The result should be the same as running the whole algorithm, but faster. |
970 | | template <typename T, absl::enable_if_t<IntegralFastPath<T>::value, int> = 0> |
971 | | static size_t hash(T value) { |
972 | | return static_cast<size_t>(Mix(Seed(), static_cast<uint64_t>(value))); |
973 | | } |
974 | | |
975 | | // Overload of MixingHashState::hash() |
976 | | template <typename T, absl::enable_if_t<!IntegralFastPath<T>::value, int> = 0> |
977 | 0 | static size_t hash(const T& value) { |
978 | 0 | return static_cast<size_t>(combine(MixingHashState{}, value).state_); |
979 | 0 | } Unexecuted instantiation: unsigned long absl::lts_20230125::hash_internal::MixingHashState::hash<absl::lts_20230125::string_view, 0>(absl::lts_20230125::string_view const&) Unexecuted instantiation: unsigned long absl::lts_20230125::hash_internal::MixingHashState::hash<absl::lts_20230125::Cord, 0>(absl::lts_20230125::Cord const&) Unexecuted instantiation: unsigned long absl::lts_20230125::hash_internal::MixingHashState::hash<google::protobuf::FieldDescriptor const*, 0>(google::protobuf::FieldDescriptor const* const&) |
980 | | |
981 | | private: |
982 | | // Invoked only once for a given argument; that plus the fact that this is |
983 | | // move-only ensures that there is only one non-moved-from object. |
984 | 0 | MixingHashState() : state_(Seed()) {} |
985 | | |
986 | | friend class MixingHashState::HashStateBase; |
987 | | |
988 | | template <typename CombinerT> |
989 | | static MixingHashState RunCombineUnordered(MixingHashState state, |
990 | | CombinerT combiner) { |
991 | | uint64_t unordered_state = 0; |
992 | | combiner(MixingHashState{}, [&](MixingHashState& inner_state) { |
993 | | // Add the hash state of the element to the running total, but mix the |
994 | | // carry bit back into the low bit. This in intended to avoid losing |
995 | | // entropy to overflow, especially when unordered_multisets contain |
996 | | // multiple copies of the same value. |
997 | | auto element_state = inner_state.state_; |
998 | | unordered_state += element_state; |
999 | | if (unordered_state < element_state) { |
1000 | | ++unordered_state; |
1001 | | } |
1002 | | inner_state = MixingHashState{}; |
1003 | | }); |
1004 | | return MixingHashState::combine(std::move(state), unordered_state); |
1005 | | } |
1006 | | |
1007 | | // Allow the HashState type-erasure implementation to invoke |
1008 | | // RunCombinedUnordered() directly. |
1009 | | friend class absl::HashState; |
1010 | | |
1011 | | // Workaround for MSVC bug. |
1012 | | // We make the type copyable to fix the calling convention, even though we |
1013 | | // never actually copy it. Keep it private to not affect the public API of the |
1014 | | // type. |
1015 | | MixingHashState(const MixingHashState&) = default; |
1016 | | |
1017 | 0 | explicit MixingHashState(uint64_t state) : state_(state) {} |
1018 | | |
1019 | | // Implementation of the base case for combine_contiguous where we actually |
1020 | | // mix the bytes into the state. |
1021 | | // Dispatch to different implementations of the combine_contiguous depending |
1022 | | // on the value of `sizeof(size_t)`. |
1023 | | static uint64_t CombineContiguousImpl(uint64_t state, |
1024 | | const unsigned char* first, size_t len, |
1025 | | std::integral_constant<int, 4> |
1026 | | /* sizeof_size_t */); |
1027 | | static uint64_t CombineContiguousImpl(uint64_t state, |
1028 | | const unsigned char* first, size_t len, |
1029 | | std::integral_constant<int, 8> |
1030 | | /* sizeof_size_t */); |
1031 | | |
1032 | | // Slow dispatch path for calls to CombineContiguousImpl with a size argument |
1033 | | // larger than PiecewiseChunkSize(). Has the same effect as calling |
1034 | | // CombineContiguousImpl() repeatedly with the chunk stride size. |
1035 | | static uint64_t CombineLargeContiguousImpl32(uint64_t state, |
1036 | | const unsigned char* first, |
1037 | | size_t len); |
1038 | | static uint64_t CombineLargeContiguousImpl64(uint64_t state, |
1039 | | const unsigned char* first, |
1040 | | size_t len); |
1041 | | |
1042 | | // Reads 9 to 16 bytes from p. |
1043 | | // The least significant 8 bytes are in .first, the rest (zero padded) bytes |
1044 | | // are in .second. |
1045 | | static std::pair<uint64_t, uint64_t> Read9To16(const unsigned char* p, |
1046 | 0 | size_t len) { |
1047 | 0 | uint64_t low_mem = absl::base_internal::UnalignedLoad64(p); |
1048 | 0 | uint64_t high_mem = absl::base_internal::UnalignedLoad64(p + len - 8); |
1049 | 0 | #ifdef ABSL_IS_LITTLE_ENDIAN |
1050 | 0 | uint64_t most_significant = high_mem; |
1051 | 0 | uint64_t least_significant = low_mem; |
1052 | 0 | #else |
1053 | 0 | uint64_t most_significant = low_mem; |
1054 | 0 | uint64_t least_significant = high_mem; |
1055 | 0 | #endif |
1056 | 0 | return {least_significant, most_significant}; |
1057 | 0 | } |
1058 | | |
1059 | | // Reads 4 to 8 bytes from p. Zero pads to fill uint64_t. |
1060 | 0 | static uint64_t Read4To8(const unsigned char* p, size_t len) { |
1061 | 0 | uint32_t low_mem = absl::base_internal::UnalignedLoad32(p); |
1062 | 0 | uint32_t high_mem = absl::base_internal::UnalignedLoad32(p + len - 4); |
1063 | 0 | #ifdef ABSL_IS_LITTLE_ENDIAN |
1064 | 0 | uint32_t most_significant = high_mem; |
1065 | 0 | uint32_t least_significant = low_mem; |
1066 | 0 | #else |
1067 | 0 | uint32_t most_significant = low_mem; |
1068 | 0 | uint32_t least_significant = high_mem; |
1069 | 0 | #endif |
1070 | 0 | return (static_cast<uint64_t>(most_significant) << (len - 4) * 8) | |
1071 | 0 | least_significant; |
1072 | 0 | } |
1073 | | |
1074 | | // Reads 1 to 3 bytes from p. Zero pads to fill uint32_t. |
1075 | 0 | static uint32_t Read1To3(const unsigned char* p, size_t len) { |
1076 | 0 | unsigned char mem0 = p[0]; |
1077 | 0 | unsigned char mem1 = p[len / 2]; |
1078 | 0 | unsigned char mem2 = p[len - 1]; |
1079 | 0 | #ifdef ABSL_IS_LITTLE_ENDIAN |
1080 | 0 | unsigned char significant2 = mem2; |
1081 | 0 | unsigned char significant1 = mem1; |
1082 | 0 | unsigned char significant0 = mem0; |
1083 | 0 | #else |
1084 | 0 | unsigned char significant2 = mem0; |
1085 | 0 | unsigned char significant1 = mem1; |
1086 | 0 | unsigned char significant0 = mem2; |
1087 | 0 | #endif |
1088 | 0 | return static_cast<uint32_t>(significant0 | // |
1089 | 0 | (significant1 << (len / 2 * 8)) | // |
1090 | 0 | (significant2 << ((len - 1) * 8))); |
1091 | 0 | } |
1092 | | |
1093 | 0 | ABSL_ATTRIBUTE_ALWAYS_INLINE static uint64_t Mix(uint64_t state, uint64_t v) { |
1094 | 0 | // Though the 128-bit product on AArch64 needs two instructions, it is |
1095 | 0 | // still a good balance between speed and hash quality. |
1096 | 0 | using MultType = |
1097 | 0 | absl::conditional_t<sizeof(size_t) == 4, uint64_t, uint128>; |
1098 | 0 | // We do the addition in 64-bit space to make sure the 128-bit |
1099 | 0 | // multiplication is fast. If we were to do it as MultType the compiler has |
1100 | 0 | // to assume that the high word is non-zero and needs to perform 2 |
1101 | 0 | // multiplications instead of one. |
1102 | 0 | MultType m = state + v; |
1103 | 0 | m *= kMul; |
1104 | 0 | return static_cast<uint64_t>(m ^ (m >> (sizeof(m) * 8 / 2))); |
1105 | 0 | } |
1106 | | |
1107 | | // An extern to avoid bloat on a direct call to LowLevelHash() with fixed |
1108 | | // values for both the seed and salt parameters. |
1109 | | static uint64_t LowLevelHashImpl(const unsigned char* data, size_t len); |
1110 | | |
1111 | | ABSL_ATTRIBUTE_ALWAYS_INLINE static uint64_t Hash64(const unsigned char* data, |
1112 | 0 | size_t len) { |
1113 | 0 | #ifdef ABSL_HAVE_INTRINSIC_INT128 |
1114 | 0 | return LowLevelHashImpl(data, len); |
1115 | 0 | #else |
1116 | 0 | return hash_internal::CityHash64(reinterpret_cast<const char*>(data), len); |
1117 | 0 | #endif |
1118 | 0 | } |
1119 | | |
1120 | | // Seed() |
1121 | | // |
1122 | | // A non-deterministic seed. |
1123 | | // |
1124 | | // The current purpose of this seed is to generate non-deterministic results |
1125 | | // and prevent having users depend on the particular hash values. |
1126 | | // It is not meant as a security feature right now, but it leaves the door |
1127 | | // open to upgrade it to a true per-process random seed. A true random seed |
1128 | | // costs more and we don't need to pay for that right now. |
1129 | | // |
1130 | | // On platforms with ASLR, we take advantage of it to make a per-process |
1131 | | // random value. |
1132 | | // See https://en.wikipedia.org/wiki/Address_space_layout_randomization |
1133 | | // |
1134 | | // On other platforms this is still going to be non-deterministic but most |
1135 | | // probably per-build and not per-process. |
1136 | 0 | ABSL_ATTRIBUTE_ALWAYS_INLINE static uint64_t Seed() { |
1137 | 0 | #if (!defined(__clang__) || __clang_major__ > 11) && \ |
1138 | 0 | !defined(__apple_build_version__) |
1139 | 0 | return static_cast<uint64_t>(reinterpret_cast<uintptr_t>(&kSeed)); |
1140 | 0 | #else |
1141 | 0 | // Workaround the absence of |
1142 | 0 | // https://github.com/llvm/llvm-project/commit/bc15bf66dcca76cc06fe71fca35b74dc4d521021. |
1143 | 0 | return static_cast<uint64_t>(reinterpret_cast<uintptr_t>(kSeed)); |
1144 | 0 | #endif |
1145 | 0 | } |
1146 | | static const void* const kSeed; |
1147 | | |
1148 | | uint64_t state_; |
1149 | | }; |
1150 | | |
1151 | | // MixingHashState::CombineContiguousImpl() |
1152 | | inline uint64_t MixingHashState::CombineContiguousImpl( |
1153 | | uint64_t state, const unsigned char* first, size_t len, |
1154 | 0 | std::integral_constant<int, 4> /* sizeof_size_t */) { |
1155 | 0 | // For large values we use CityHash, for small ones we just use a |
1156 | 0 | // multiplicative hash. |
1157 | 0 | uint64_t v; |
1158 | 0 | if (len > 8) { |
1159 | 0 | if (ABSL_PREDICT_FALSE(len > PiecewiseChunkSize())) { |
1160 | 0 | return CombineLargeContiguousImpl32(state, first, len); |
1161 | 0 | } |
1162 | 0 | v = hash_internal::CityHash32(reinterpret_cast<const char*>(first), len); |
1163 | 0 | } else if (len >= 4) { |
1164 | 0 | v = Read4To8(first, len); |
1165 | 0 | } else if (len > 0) { |
1166 | 0 | v = Read1To3(first, len); |
1167 | 0 | } else { |
1168 | 0 | // Empty ranges have no effect. |
1169 | 0 | return state; |
1170 | 0 | } |
1171 | 0 | return Mix(state, v); |
1172 | 0 | } |
1173 | | |
1174 | | // Overload of MixingHashState::CombineContiguousImpl() |
1175 | | inline uint64_t MixingHashState::CombineContiguousImpl( |
1176 | | uint64_t state, const unsigned char* first, size_t len, |
1177 | 0 | std::integral_constant<int, 8> /* sizeof_size_t */) { |
1178 | 0 | // For large values we use LowLevelHash or CityHash depending on the platform, |
1179 | 0 | // for small ones we just use a multiplicative hash. |
1180 | 0 | uint64_t v; |
1181 | 0 | if (len > 16) { |
1182 | 0 | if (ABSL_PREDICT_FALSE(len > PiecewiseChunkSize())) { |
1183 | 0 | return CombineLargeContiguousImpl64(state, first, len); |
1184 | 0 | } |
1185 | 0 | v = Hash64(first, len); |
1186 | 0 | } else if (len > 8) { |
1187 | 0 | // This hash function was constructed by the ML-driven algorithm discovery |
1188 | 0 | // using reinforcement learning. We fed the agent lots of inputs from |
1189 | 0 | // microbenchmarks, SMHasher, low hamming distance from generated inputs and |
1190 | 0 | // picked up the one that was good on micro and macrobenchmarks. |
1191 | 0 | auto p = Read9To16(first, len); |
1192 | 0 | uint64_t lo = p.first; |
1193 | 0 | uint64_t hi = p.second; |
1194 | 0 | // Rotation by 53 was found to be most often useful when discovering these |
1195 | 0 | // hashing algorithms with ML techniques. |
1196 | 0 | lo = absl::rotr(lo, 53); |
1197 | 0 | state += kMul; |
1198 | 0 | lo += state; |
1199 | 0 | state ^= hi; |
1200 | 0 | uint128 m = state; |
1201 | 0 | m *= lo; |
1202 | 0 | return static_cast<uint64_t>(m ^ (m >> 64)); |
1203 | 0 | } else if (len >= 4) { |
1204 | 0 | v = Read4To8(first, len); |
1205 | 0 | } else if (len > 0) { |
1206 | 0 | v = Read1To3(first, len); |
1207 | 0 | } else { |
1208 | 0 | // Empty ranges have no effect. |
1209 | 0 | return state; |
1210 | 0 | } |
1211 | 0 | return Mix(state, v); |
1212 | 0 | } |
1213 | | |
1214 | | struct AggregateBarrier {}; |
1215 | | |
1216 | | // HashImpl |
1217 | | |
1218 | | // Add a private base class to make sure this type is not an aggregate. |
1219 | | // Aggregates can be aggregate initialized even if the default constructor is |
1220 | | // deleted. |
1221 | | struct PoisonedHash : private AggregateBarrier { |
1222 | | PoisonedHash() = delete; |
1223 | | PoisonedHash(const PoisonedHash&) = delete; |
1224 | | PoisonedHash& operator=(const PoisonedHash&) = delete; |
1225 | | }; |
1226 | | |
1227 | | template <typename T> |
1228 | | struct HashImpl { |
1229 | 0 | size_t operator()(const T& value) const { |
1230 | 0 | return MixingHashState::hash(value); |
1231 | 0 | } Unexecuted instantiation: absl::lts_20230125::hash_internal::HashImpl<absl::lts_20230125::string_view>::operator()(absl::lts_20230125::string_view const&) const Unexecuted instantiation: absl::lts_20230125::hash_internal::HashImpl<absl::lts_20230125::Cord>::operator()(absl::lts_20230125::Cord const&) const Unexecuted instantiation: absl::lts_20230125::hash_internal::HashImpl<google::protobuf::FieldDescriptor const*>::operator()(google::protobuf::FieldDescriptor const* const&) const |
1232 | | }; |
1233 | | |
1234 | | template <typename T> |
1235 | | struct Hash |
1236 | | : absl::conditional_t<is_hashable<T>::value, HashImpl<T>, PoisonedHash> {}; |
1237 | | |
1238 | | template <typename H> |
1239 | | template <typename T, typename... Ts> |
1240 | 0 | H HashStateBase<H>::combine(H state, const T& value, const Ts&... values) { |
1241 | 0 | return H::combine(hash_internal::HashSelect::template Apply<T>::Invoke( |
1242 | 0 | std::move(state), value), |
1243 | 0 | values...); |
1244 | 0 | } Unexecuted instantiation: absl::lts_20230125::hash_internal::MixingHashState absl::lts_20230125::hash_internal::HashStateBase<absl::lts_20230125::hash_internal::MixingHashState>::combine<absl::lts_20230125::string_view>(absl::lts_20230125::hash_internal::MixingHashState, absl::lts_20230125::string_view const&) Unexecuted instantiation: absl::lts_20230125::hash_internal::MixingHashState absl::lts_20230125::hash_internal::HashStateBase<absl::lts_20230125::hash_internal::MixingHashState>::combine<unsigned long>(absl::lts_20230125::hash_internal::MixingHashState, unsigned long const&) Unexecuted instantiation: absl::lts_20230125::hash_internal::MixingHashState absl::lts_20230125::hash_internal::HashStateBase<absl::lts_20230125::hash_internal::MixingHashState>::combine<absl::lts_20230125::Cord>(absl::lts_20230125::hash_internal::MixingHashState, absl::lts_20230125::Cord const&) Unexecuted instantiation: absl::lts_20230125::hash_internal::MixingHashState absl::lts_20230125::hash_internal::HashStateBase<absl::lts_20230125::hash_internal::MixingHashState>::combine<google::protobuf::FieldDescriptor const*>(absl::lts_20230125::hash_internal::MixingHashState, google::protobuf::FieldDescriptor const* const&) Unexecuted instantiation: absl::lts_20230125::hash_internal::MixingHashState absl::lts_20230125::hash_internal::HashStateBase<absl::lts_20230125::hash_internal::MixingHashState>::combine<unsigned long, unsigned long>(absl::lts_20230125::hash_internal::MixingHashState, unsigned long const&, unsigned long const&) |
1245 | | |
1246 | | // HashStateBase::combine_contiguous() |
1247 | | template <typename H> |
1248 | | template <typename T> |
1249 | 0 | H HashStateBase<H>::combine_contiguous(H state, const T* data, size_t size) { |
1250 | 0 | return hash_internal::hash_range_or_bytes(std::move(state), data, size); |
1251 | 0 | } |
1252 | | |
1253 | | // HashStateBase::combine_unordered() |
1254 | | template <typename H> |
1255 | | template <typename I> |
1256 | | H HashStateBase<H>::combine_unordered(H state, I begin, I end) { |
1257 | | return H::RunCombineUnordered(std::move(state), |
1258 | | CombineUnorderedCallback<I>{begin, end}); |
1259 | | } |
1260 | | |
1261 | | // HashStateBase::PiecewiseCombiner::add_buffer() |
1262 | | template <typename H> |
1263 | | H PiecewiseCombiner::add_buffer(H state, const unsigned char* data, |
1264 | 0 | size_t size) { |
1265 | 0 | if (position_ + size < PiecewiseChunkSize()) { |
1266 | 0 | // This partial chunk does not fill our existing buffer |
1267 | 0 | memcpy(buf_ + position_, data, size); |
1268 | 0 | position_ += size; |
1269 | 0 | return state; |
1270 | 0 | } |
1271 | 0 |
|
1272 | 0 | // If the buffer is partially filled we need to complete the buffer |
1273 | 0 | // and hash it. |
1274 | 0 | if (position_ != 0) { |
1275 | 0 | const size_t bytes_needed = PiecewiseChunkSize() - position_; |
1276 | 0 | memcpy(buf_ + position_, data, bytes_needed); |
1277 | 0 | state = H::combine_contiguous(std::move(state), buf_, PiecewiseChunkSize()); |
1278 | 0 | data += bytes_needed; |
1279 | 0 | size -= bytes_needed; |
1280 | 0 | } |
1281 | 0 |
|
1282 | 0 | // Hash whatever chunks we can without copying |
1283 | 0 | while (size >= PiecewiseChunkSize()) { |
1284 | 0 | state = H::combine_contiguous(std::move(state), data, PiecewiseChunkSize()); |
1285 | 0 | data += PiecewiseChunkSize(); |
1286 | 0 | size -= PiecewiseChunkSize(); |
1287 | 0 | } |
1288 | 0 | // Fill the buffer with the remainder |
1289 | 0 | memcpy(buf_, data, size); |
1290 | 0 | position_ = size; |
1291 | 0 | return state; |
1292 | 0 | } |
1293 | | |
1294 | | // HashStateBase::PiecewiseCombiner::finalize() |
1295 | | template <typename H> |
1296 | 0 | H PiecewiseCombiner::finalize(H state) { |
1297 | 0 | // Hash the remainder left in the buffer, which may be empty |
1298 | 0 | return H::combine_contiguous(std::move(state), buf_, position_); |
1299 | 0 | } |
1300 | | |
1301 | | } // namespace hash_internal |
1302 | | ABSL_NAMESPACE_END |
1303 | | } // namespace absl |
1304 | | |
1305 | | #endif // ABSL_HASH_INTERNAL_HASH_H_ |