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