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 <cmath>
25 #include <cstring>
26 #include <deque>
27 #include <forward_list>
28 #include <functional>
29 #include <iterator>
30 #include <limits>
31 #include <list>
32 #include <map>
33 #include <memory>
34 #include <set>
35 #include <string>
36 #include <tuple>
37 #include <type_traits>
38 #include <utility>
39 #include <vector>
40
41 #include "absl/base/internal/endian.h"
42 #include "absl/base/port.h"
43 #include "absl/container/fixed_array.h"
44 #include "absl/meta/type_traits.h"
45 #include "absl/numeric/int128.h"
46 #include "absl/strings/string_view.h"
47 #include "absl/types/optional.h"
48 #include "absl/types/variant.h"
49 #include "absl/utility/utility.h"
50 #include "absl/hash/internal/city.h"
51
52 namespace absl {
53 ABSL_NAMESPACE_BEGIN
54 namespace hash_internal {
55
56 // Internal detail: Large buffers are hashed in smaller chunks. This function
57 // returns the size of these chunks.
PiecewiseChunkSize()58 constexpr size_t PiecewiseChunkSize() { return 1024; }
59
60 // PiecewiseCombiner
61 //
62 // PiecewiseCombiner is an internal-only helper class for hashing a piecewise
63 // buffer of `char` or `unsigned char` as though it were contiguous. This class
64 // provides two methods:
65 //
66 // H add_buffer(state, data, size)
67 // H finalize(state)
68 //
69 // `add_buffer` can be called zero or more times, followed by a single call to
70 // `finalize`. This will produce the same hash expansion as concatenating each
71 // buffer piece into a single contiguous buffer, and passing this to
72 // `H::combine_contiguous`.
73 //
74 // Example usage:
75 // PiecewiseCombiner combiner;
76 // for (const auto& piece : pieces) {
77 // state = combiner.add_buffer(std::move(state), piece.data, piece.size);
78 // }
79 // return combiner.finalize(std::move(state));
80 class PiecewiseCombiner {
81 public:
PiecewiseCombiner()82 PiecewiseCombiner() : position_(0) {}
83 PiecewiseCombiner(const PiecewiseCombiner&) = delete;
84 PiecewiseCombiner& operator=(const PiecewiseCombiner&) = delete;
85
86 // PiecewiseCombiner::add_buffer()
87 //
88 // Appends the given range of bytes to the sequence to be hashed, which may
89 // modify the provided hash state.
90 template <typename H>
91 H add_buffer(H state, const unsigned char* data, size_t size);
92 template <typename H>
add_buffer(H state,const char * data,size_t size)93 H add_buffer(H state, const char* data, size_t size) {
94 return add_buffer(std::move(state),
95 reinterpret_cast<const unsigned char*>(data), size);
96 }
97
98 // PiecewiseCombiner::finalize()
99 //
100 // Finishes combining the hash sequence, which may may modify the provided
101 // hash state.
102 //
103 // Once finalize() is called, add_buffer() may no longer be called. The
104 // resulting hash state will be the same as if the pieces passed to
105 // add_buffer() were concatenated into a single flat buffer, and then provided
106 // to H::combine_contiguous().
107 template <typename H>
108 H finalize(H state);
109
110 private:
111 unsigned char buf_[PiecewiseChunkSize()];
112 size_t position_;
113 };
114
115 // HashStateBase
116 //
117 // A hash state object represents an intermediate state in the computation
118 // of an unspecified hash algorithm. `HashStateBase` provides a CRTP style
119 // base class for hash state implementations. Developers adding type support
120 // for `absl::Hash` should not rely on any parts of the state object other than
121 // the following member functions:
122 //
123 // * HashStateBase::combine()
124 // * HashStateBase::combine_contiguous()
125 //
126 // A derived hash state class of type `H` must provide a static member function
127 // with a signature similar to the following:
128 //
129 // `static H combine_contiguous(H state, const unsigned char*, size_t)`.
130 //
131 // `HashStateBase` will provide a complete implementation for a hash state
132 // object in terms of this method.
133 //
134 // Example:
135 //
136 // // Use CRTP to define your derived class.
137 // struct MyHashState : HashStateBase<MyHashState> {
138 // static H combine_contiguous(H state, const unsigned char*, size_t);
139 // using MyHashState::HashStateBase::combine;
140 // using MyHashState::HashStateBase::combine_contiguous;
141 // };
142 template <typename H>
143 class HashStateBase {
144 public:
145 // HashStateBase::combine()
146 //
147 // Combines an arbitrary number of values into a hash state, returning the
148 // updated state.
149 //
150 // Each of the value types `T` must be separately hashable by the Abseil
151 // hashing framework.
152 //
153 // NOTE:
154 //
155 // state = H::combine(std::move(state), value1, value2, value3);
156 //
157 // is guaranteed to produce the same hash expansion as:
158 //
159 // state = H::combine(std::move(state), value1);
160 // state = H::combine(std::move(state), value2);
161 // state = H::combine(std::move(state), value3);
162 template <typename T, typename... Ts>
163 static H combine(H state, const T& value, const Ts&... values);
combine(H state)164 static H combine(H state) { return state; }
165
166 // HashStateBase::combine_contiguous()
167 //
168 // Combines a contiguous array of `size` elements into a hash state, returning
169 // the updated state.
170 //
171 // NOTE:
172 //
173 // state = H::combine_contiguous(std::move(state), data, size);
174 //
175 // is NOT guaranteed to produce the same hash expansion as a for-loop (it may
176 // perform internal optimizations). If you need this guarantee, use the
177 // for-loop instead.
178 template <typename T>
179 static H combine_contiguous(H state, const T* data, size_t size);
180
181 using AbslInternalPiecewiseCombiner = PiecewiseCombiner;
182 };
183
184 // is_uniquely_represented
185 //
186 // `is_uniquely_represented<T>` is a trait class that indicates whether `T`
187 // is uniquely represented.
188 //
189 // A type is "uniquely represented" if two equal values of that type are
190 // guaranteed to have the same bytes in their underlying storage. In other
191 // words, if `a == b`, then `memcmp(&a, &b, sizeof(T))` is guaranteed to be
192 // zero. This property cannot be detected automatically, so this trait is false
193 // by default, but can be specialized by types that wish to assert that they are
194 // uniquely represented. This makes them eligible for certain optimizations.
195 //
196 // If you have any doubt whatsoever, do not specialize this template.
197 // The default is completely safe, and merely disables some optimizations
198 // that will not matter for most types. Specializing this template,
199 // on the other hand, can be very hazardous.
200 //
201 // To be uniquely represented, a type must not have multiple ways of
202 // representing the same value; for example, float and double are not
203 // uniquely represented, because they have distinct representations for
204 // +0 and -0. Furthermore, the type's byte representation must consist
205 // solely of user-controlled data, with no padding bits and no compiler-
206 // controlled data such as vptrs or sanitizer metadata. This is usually
207 // very difficult to guarantee, because in most cases the compiler can
208 // insert data and padding bits at its own discretion.
209 //
210 // If you specialize this template for a type `T`, you must do so in the file
211 // that defines that type (or in this file). If you define that specialization
212 // anywhere else, `is_uniquely_represented<T>` could have different meanings
213 // in different places.
214 //
215 // The Enable parameter is meaningless; it is provided as a convenience,
216 // to support certain SFINAE techniques when defining specializations.
217 template <typename T, typename Enable = void>
218 struct is_uniquely_represented : std::false_type {};
219
220 // is_uniquely_represented<unsigned char>
221 //
222 // unsigned char is a synonym for "byte", so it is guaranteed to be
223 // uniquely represented.
224 template <>
225 struct is_uniquely_represented<unsigned char> : std::true_type {};
226
227 // is_uniquely_represented for non-standard integral types
228 //
229 // Integral types other than bool should be uniquely represented on any
230 // platform that this will plausibly be ported to.
231 template <typename Integral>
232 struct is_uniquely_represented<
233 Integral, typename std::enable_if<std::is_integral<Integral>::value>::type>
234 : std::true_type {};
235
236 // is_uniquely_represented<bool>
237 //
238 //
239 template <>
240 struct is_uniquely_represented<bool> : std::false_type {};
241
242 // hash_bytes()
243 //
244 // Convenience function that combines `hash_state` with the byte representation
245 // of `value`.
246 template <typename H, typename T>
247 H hash_bytes(H hash_state, const T& value) {
248 const unsigned char* start = reinterpret_cast<const unsigned char*>(&value);
249 return H::combine_contiguous(std::move(hash_state), start, sizeof(value));
250 }
251
252 // -----------------------------------------------------------------------------
253 // AbslHashValue for Basic Types
254 // -----------------------------------------------------------------------------
255
256 // Note: Default `AbslHashValue` implementations live in `hash_internal`. This
257 // allows us to block lexical scope lookup when doing an unqualified call to
258 // `AbslHashValue` below. User-defined implementations of `AbslHashValue` can
259 // only be found via ADL.
260
261 // AbslHashValue() for hashing bool values
262 //
263 // We use SFINAE to ensure that this overload only accepts bool, not types that
264 // are convertible to bool.
265 template <typename H, typename B>
266 typename std::enable_if<std::is_same<B, bool>::value, H>::type AbslHashValue(
267 H hash_state, B value) {
268 return H::combine(std::move(hash_state),
269 static_cast<unsigned char>(value ? 1 : 0));
270 }
271
272 // AbslHashValue() for hashing enum values
273 template <typename H, typename Enum>
274 typename std::enable_if<std::is_enum<Enum>::value, H>::type AbslHashValue(
275 H hash_state, Enum e) {
276 // In practice, we could almost certainly just invoke hash_bytes directly,
277 // but it's possible that a sanitizer might one day want to
278 // store data in the unused bits of an enum. To avoid that risk, we
279 // convert to the underlying type before hashing. Hopefully this will get
280 // optimized away; if not, we can reopen discussion with c-toolchain-team.
281 return H::combine(std::move(hash_state),
282 static_cast<typename std::underlying_type<Enum>::type>(e));
283 }
284 // AbslHashValue() for hashing floating-point values
285 template <typename H, typename Float>
286 typename std::enable_if<std::is_same<Float, float>::value ||
287 std::is_same<Float, double>::value,
288 H>::type
289 AbslHashValue(H hash_state, Float value) {
290 return hash_internal::hash_bytes(std::move(hash_state),
291 value == 0 ? 0 : value);
292 }
293
294 // Long double has the property that it might have extra unused bytes in it.
295 // For example, in x86 sizeof(long double)==16 but it only really uses 80-bits
296 // of it. This means we can't use hash_bytes on a long double and have to
297 // convert it to something else first.
298 template <typename H, typename LongDouble>
299 typename std::enable_if<std::is_same<LongDouble, long double>::value, H>::type
300 AbslHashValue(H hash_state, LongDouble value) {
301 const int category = std::fpclassify(value);
302 switch (category) {
303 case FP_INFINITE:
304 // Add the sign bit to differentiate between +Inf and -Inf
305 hash_state = H::combine(std::move(hash_state), std::signbit(value));
306 break;
307
308 case FP_NAN:
309 case FP_ZERO:
310 default:
311 // Category is enough for these.
312 break;
313
314 case FP_NORMAL:
315 case FP_SUBNORMAL:
316 // We can't convert `value` directly to double because this would have
317 // undefined behavior if the value is out of range.
318 // std::frexp gives us a value in the range (-1, -.5] or [.5, 1) that is
319 // guaranteed to be in range for `double`. The truncation is
320 // implementation defined, but that works as long as it is deterministic.
321 int exp;
322 auto mantissa = static_cast<double>(std::frexp(value, &exp));
323 hash_state = H::combine(std::move(hash_state), mantissa, exp);
324 }
325
326 return H::combine(std::move(hash_state), category);
327 }
328
329 // AbslHashValue() for hashing pointers
330 template <typename H, typename T>
331 H AbslHashValue(H hash_state, T* ptr) {
332 auto v = reinterpret_cast<uintptr_t>(ptr);
333 // Due to alignment, pointers tend to have low bits as zero, and the next few
334 // bits follow a pattern since they are also multiples of some base value.
335 // Mixing the pointer twice helps prevent stuck low bits for certain alignment
336 // values.
337 return H::combine(std::move(hash_state), v, v);
338 }
339
340 // AbslHashValue() for hashing nullptr_t
341 template <typename H>
342 H AbslHashValue(H hash_state, std::nullptr_t) {
343 return H::combine(std::move(hash_state), static_cast<void*>(nullptr));
344 }
345
346 // -----------------------------------------------------------------------------
347 // AbslHashValue for Composite Types
348 // -----------------------------------------------------------------------------
349
350 // is_hashable()
351 //
352 // Trait class which returns true if T is hashable by the absl::Hash framework.
353 // Used for the AbslHashValue implementations for composite types below.
354 template <typename T>
355 struct is_hashable;
356
357 // AbslHashValue() for hashing pairs
358 template <typename H, typename T1, typename T2>
359 typename std::enable_if<is_hashable<T1>::value && is_hashable<T2>::value,
360 H>::type
361 AbslHashValue(H hash_state, const std::pair<T1, T2>& p) {
362 return H::combine(std::move(hash_state), p.first, p.second);
363 }
364
365 // hash_tuple()
366 //
367 // Helper function for hashing a tuple. The third argument should
368 // be an index_sequence running from 0 to tuple_size<Tuple> - 1.
369 template <typename H, typename Tuple, size_t... Is>
370 H hash_tuple(H hash_state, const Tuple& t, absl::index_sequence<Is...>) {
371 return H::combine(std::move(hash_state), std::get<Is>(t)...);
372 }
373
374 // AbslHashValue for hashing tuples
375 template <typename H, typename... Ts>
376 #if defined(_MSC_VER)
377 // This SFINAE gets MSVC confused under some conditions. Let's just disable it
378 // for now.
379 H
380 #else // _MSC_VER
381 typename std::enable_if<absl::conjunction<is_hashable<Ts>...>::value, H>::type
382 #endif // _MSC_VER
383 AbslHashValue(H hash_state, const std::tuple<Ts...>& t) {
384 return hash_internal::hash_tuple(std::move(hash_state), t,
385 absl::make_index_sequence<sizeof...(Ts)>());
386 }
387
388 // -----------------------------------------------------------------------------
389 // AbslHashValue for Pointers
390 // -----------------------------------------------------------------------------
391
392 // AbslHashValue for hashing unique_ptr
393 template <typename H, typename T, typename D>
394 H AbslHashValue(H hash_state, const std::unique_ptr<T, D>& ptr) {
395 return H::combine(std::move(hash_state), ptr.get());
396 }
397
398 // AbslHashValue for hashing shared_ptr
399 template <typename H, typename T>
400 H AbslHashValue(H hash_state, const std::shared_ptr<T>& ptr) {
401 return H::combine(std::move(hash_state), ptr.get());
402 }
403
404 // -----------------------------------------------------------------------------
405 // AbslHashValue for String-Like Types
406 // -----------------------------------------------------------------------------
407
408 // AbslHashValue for hashing strings
409 //
410 // All the string-like types supported here provide the same hash expansion for
411 // the same character sequence. These types are:
412 //
413 // - `absl::Cord`
414 // - `std::string` (and std::basic_string<char, std::char_traits<char>, A> for
415 // any allocator A)
416 // - `absl::string_view` and `std::string_view`
417 //
418 // For simplicity, we currently support only `char` strings. This support may
419 // be broadened, if necessary, but with some caution - this overload would
420 // misbehave in cases where the traits' `eq()` member isn't equivalent to `==`
421 // on the underlying character type.
422 template <typename H>
423 H AbslHashValue(H hash_state, absl::string_view str) {
424 return H::combine(
425 H::combine_contiguous(std::move(hash_state), str.data(), str.size()),
426 str.size());
427 }
428
429 // Support std::wstring, std::u16string and std::u32string.
430 template <typename Char, typename Alloc, typename H,
431 typename = absl::enable_if_t<std::is_same<Char, wchar_t>::value ||
432 std::is_same<Char, char16_t>::value ||
433 std::is_same<Char, char32_t>::value>>
434 H AbslHashValue(
435 H hash_state,
436 const std::basic_string<Char, std::char_traits<Char>, Alloc>& str) {
437 return H::combine(
438 H::combine_contiguous(std::move(hash_state), str.data(), str.size()),
439 str.size());
440 }
441
442 // -----------------------------------------------------------------------------
443 // AbslHashValue for Sequence Containers
444 // -----------------------------------------------------------------------------
445
446 // AbslHashValue for hashing std::array
447 template <typename H, typename T, size_t N>
448 typename std::enable_if<is_hashable<T>::value, H>::type AbslHashValue(
449 H hash_state, const std::array<T, N>& array) {
450 return H::combine_contiguous(std::move(hash_state), array.data(),
451 array.size());
452 }
453
454 // AbslHashValue for hashing std::deque
455 template <typename H, typename T, typename Allocator>
456 typename std::enable_if<is_hashable<T>::value, H>::type AbslHashValue(
457 H hash_state, const std::deque<T, Allocator>& deque) {
458 // TODO(gromer): investigate a more efficient implementation taking
459 // advantage of the chunk structure.
460 for (const auto& t : deque) {
461 hash_state = H::combine(std::move(hash_state), t);
462 }
463 return H::combine(std::move(hash_state), deque.size());
464 }
465
466 // AbslHashValue for hashing std::forward_list
467 template <typename H, typename T, typename Allocator>
468 typename std::enable_if<is_hashable<T>::value, H>::type AbslHashValue(
469 H hash_state, const std::forward_list<T, Allocator>& list) {
470 size_t size = 0;
471 for (const T& t : list) {
472 hash_state = H::combine(std::move(hash_state), t);
473 ++size;
474 }
475 return H::combine(std::move(hash_state), size);
476 }
477
478 // AbslHashValue for hashing std::list
479 template <typename H, typename T, typename Allocator>
480 typename std::enable_if<is_hashable<T>::value, H>::type AbslHashValue(
481 H hash_state, const std::list<T, Allocator>& list) {
482 for (const auto& t : list) {
483 hash_state = H::combine(std::move(hash_state), t);
484 }
485 return H::combine(std::move(hash_state), list.size());
486 }
487
488 // AbslHashValue for hashing std::vector
489 //
490 // Do not use this for vector<bool>. It does not have a .data(), and a fallback
491 // for std::hash<> is most likely faster.
492 template <typename H, typename T, typename Allocator>
493 typename std::enable_if<is_hashable<T>::value && !std::is_same<T, bool>::value,
494 H>::type
495 AbslHashValue(H hash_state, const std::vector<T, Allocator>& vector) {
496 return H::combine(H::combine_contiguous(std::move(hash_state), vector.data(),
497 vector.size()),
498 vector.size());
499 }
500
501 // -----------------------------------------------------------------------------
502 // AbslHashValue for Ordered Associative Containers
503 // -----------------------------------------------------------------------------
504
505 // AbslHashValue for hashing std::map
506 template <typename H, typename Key, typename T, typename Compare,
507 typename Allocator>
508 typename std::enable_if<is_hashable<Key>::value && is_hashable<T>::value,
509 H>::type
510 AbslHashValue(H hash_state, const std::map<Key, T, Compare, Allocator>& map) {
511 for (const auto& t : map) {
512 hash_state = H::combine(std::move(hash_state), t);
513 }
514 return H::combine(std::move(hash_state), map.size());
515 }
516
517 // AbslHashValue for hashing std::multimap
518 template <typename H, typename Key, typename T, typename Compare,
519 typename Allocator>
520 typename std::enable_if<is_hashable<Key>::value && is_hashable<T>::value,
521 H>::type
522 AbslHashValue(H hash_state,
523 const std::multimap<Key, T, Compare, Allocator>& map) {
524 for (const auto& t : map) {
525 hash_state = H::combine(std::move(hash_state), t);
526 }
527 return H::combine(std::move(hash_state), map.size());
528 }
529
530 // AbslHashValue for hashing std::set
531 template <typename H, typename Key, typename Compare, typename Allocator>
532 typename std::enable_if<is_hashable<Key>::value, H>::type AbslHashValue(
533 H hash_state, const std::set<Key, Compare, Allocator>& set) {
534 for (const auto& t : set) {
535 hash_state = H::combine(std::move(hash_state), t);
536 }
537 return H::combine(std::move(hash_state), set.size());
538 }
539
540 // AbslHashValue for hashing std::multiset
541 template <typename H, typename Key, typename Compare, typename Allocator>
542 typename std::enable_if<is_hashable<Key>::value, H>::type AbslHashValue(
543 H hash_state, const std::multiset<Key, Compare, Allocator>& set) {
544 for (const auto& t : set) {
545 hash_state = H::combine(std::move(hash_state), t);
546 }
547 return H::combine(std::move(hash_state), set.size());
548 }
549
550 // -----------------------------------------------------------------------------
551 // AbslHashValue for Wrapper Types
552 // -----------------------------------------------------------------------------
553
554 // AbslHashValue for hashing std::reference_wrapper
555 template <typename H, typename T>
556 typename std::enable_if<is_hashable<T>::value, H>::type AbslHashValue(
557 H hash_state, std::reference_wrapper<T> opt) {
558 return H::combine(std::move(hash_state), opt.get());
559 }
560
561 // AbslHashValue for hashing absl::optional
562 template <typename H, typename T>
563 typename std::enable_if<is_hashable<T>::value, H>::type AbslHashValue(
564 H hash_state, const absl::optional<T>& opt) {
565 if (opt) hash_state = H::combine(std::move(hash_state), *opt);
566 return H::combine(std::move(hash_state), opt.has_value());
567 }
568
569 // VariantVisitor
570 template <typename H>
571 struct VariantVisitor {
572 H&& hash_state;
573 template <typename T>
574 H operator()(const T& t) const {
575 return H::combine(std::move(hash_state), t);
576 }
577 };
578
579 // AbslHashValue for hashing absl::variant
580 template <typename H, typename... T>
581 typename std::enable_if<conjunction<is_hashable<T>...>::value, H>::type
582 AbslHashValue(H hash_state, const absl::variant<T...>& v) {
583 if (!v.valueless_by_exception()) {
584 hash_state = absl::visit(VariantVisitor<H>{std::move(hash_state)}, v);
585 }
586 return H::combine(std::move(hash_state), v.index());
587 }
588
589 // -----------------------------------------------------------------------------
590 // AbslHashValue for Other Types
591 // -----------------------------------------------------------------------------
592
593 // AbslHashValue for hashing std::bitset is not defined, for the same reason as
594 // for vector<bool> (see std::vector above): It does not expose the raw bytes,
595 // and a fallback to std::hash<> is most likely faster.
596
597 // -----------------------------------------------------------------------------
598
599 // hash_range_or_bytes()
600 //
601 // Mixes all values in the range [data, data+size) into the hash state.
602 // This overload accepts only uniquely-represented types, and hashes them by
603 // hashing the entire range of bytes.
604 template <typename H, typename T>
605 typename std::enable_if<is_uniquely_represented<T>::value, H>::type
606 hash_range_or_bytes(H hash_state, const T* data, size_t size) {
607 const auto* bytes = reinterpret_cast<const unsigned char*>(data);
608 return H::combine_contiguous(std::move(hash_state), bytes, sizeof(T) * size);
609 }
610
611 // hash_range_or_bytes()
612 template <typename H, typename T>
613 typename std::enable_if<!is_uniquely_represented<T>::value, H>::type
614 hash_range_or_bytes(H hash_state, const T* data, size_t size) {
615 for (const auto end = data + size; data < end; ++data) {
616 hash_state = H::combine(std::move(hash_state), *data);
617 }
618 return hash_state;
619 }
620
621 #if defined(ABSL_INTERNAL_LEGACY_HASH_NAMESPACE) && \
622 ABSL_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_
623 #define ABSL_HASH_INTERNAL_SUPPORT_LEGACY_HASH_ 1
624 #else
625 #define ABSL_HASH_INTERNAL_SUPPORT_LEGACY_HASH_ 0
626 #endif
627
628 // HashSelect
629 //
630 // Type trait to select the appropriate hash implementation to use.
631 // HashSelect::type<T> will give the proper hash implementation, to be invoked
632 // as:
633 // HashSelect::type<T>::Invoke(state, value)
634 // Also, HashSelect::type<T>::value is a boolean equal to `true` if there is a
635 // valid `Invoke` function. Types that are not hashable will have a ::value of
636 // `false`.
637 struct HashSelect {
638 private:
639 struct State : HashStateBase<State> {
640 static State combine_contiguous(State hash_state, const unsigned char*,
641 size_t);
642 using State::HashStateBase::combine_contiguous;
643 };
644
645 struct UniquelyRepresentedProbe {
646 template <typename H, typename T>
647 static auto Invoke(H state, const T& value)
648 -> absl::enable_if_t<is_uniquely_represented<T>::value, H> {
649 return hash_internal::hash_bytes(std::move(state), value);
650 }
651 };
652
653 struct HashValueProbe {
654 template <typename H, typename T>
655 static auto Invoke(H state, const T& value) -> absl::enable_if_t<
656 std::is_same<H,
657 decltype(AbslHashValue(std::move(state), value))>::value,
658 H> {
659 return AbslHashValue(std::move(state), value);
660 }
661 };
662
663 struct LegacyHashProbe {
664 #if ABSL_HASH_INTERNAL_SUPPORT_LEGACY_HASH_
665 template <typename H, typename T>
666 static auto Invoke(H state, const T& value) -> absl::enable_if_t<
667 std::is_convertible<
668 decltype(ABSL_INTERNAL_LEGACY_HASH_NAMESPACE::hash<T>()(value)),
669 size_t>::value,
670 H> {
671 return hash_internal::hash_bytes(
672 std::move(state),
673 ABSL_INTERNAL_LEGACY_HASH_NAMESPACE::hash<T>{}(value));
674 }
675 #endif // ABSL_HASH_INTERNAL_SUPPORT_LEGACY_HASH_
676 };
677
678 struct StdHashProbe {
679 template <typename H, typename T>
680 static auto Invoke(H state, const T& value)
681 -> absl::enable_if_t<type_traits_internal::IsHashable<T>::value, H> {
682 return hash_internal::hash_bytes(std::move(state), std::hash<T>{}(value));
683 }
684 };
685
686 template <typename Hash, typename T>
687 struct Probe : Hash {
688 private:
689 template <typename H, typename = decltype(H::Invoke(
690 std::declval<State>(), std::declval<const T&>()))>
691 static std::true_type Test(int);
692 template <typename U>
693 static std::false_type Test(char);
694
695 public:
696 static constexpr bool value = decltype(Test<Hash>(0))::value;
697 };
698
699 public:
700 // Probe each implementation in order.
701 // disjunction provides short circuiting wrt instantiation.
702 template <typename T>
703 using Apply = absl::disjunction< //
704 Probe<UniquelyRepresentedProbe, T>, //
705 Probe<HashValueProbe, T>, //
706 Probe<LegacyHashProbe, T>, //
707 Probe<StdHashProbe, T>, //
708 std::false_type>;
709 };
710
711 template <typename T>
712 struct is_hashable
713 : std::integral_constant<bool, HashSelect::template Apply<T>::value> {};
714
715 // CityHashState
716 class ABSL_DLL CityHashState
717 : public HashStateBase<CityHashState> {
718 // absl::uint128 is not an alias or a thin wrapper around the intrinsic.
719 // We use the intrinsic when available to improve performance.
720 #ifdef ABSL_HAVE_INTRINSIC_INT128
721 using uint128 = __uint128_t;
722 #else // ABSL_HAVE_INTRINSIC_INT128
723 using uint128 = absl::uint128;
724 #endif // ABSL_HAVE_INTRINSIC_INT128
725
726 static constexpr uint64_t kMul =
727 sizeof(size_t) == 4 ? uint64_t{0xcc9e2d51}
728 : uint64_t{0x9ddfea08eb382d69};
729
730 template <typename T>
731 using IntegralFastPath =
732 conjunction<std::is_integral<T>, is_uniquely_represented<T>>;
733
734 public:
735 // Move only
736 CityHashState(CityHashState&&) = default;
737 CityHashState& operator=(CityHashState&&) = default;
738
739 // CityHashState::combine_contiguous()
740 //
741 // Fundamental base case for hash recursion: mixes the given range of bytes
742 // into the hash state.
743 static CityHashState combine_contiguous(CityHashState hash_state,
744 const unsigned char* first,
745 size_t size) {
746 return CityHashState(
747 CombineContiguousImpl(hash_state.state_, first, size,
748 std::integral_constant<int, sizeof(size_t)>{}));
749 }
750 using CityHashState::HashStateBase::combine_contiguous;
751
752 // CityHashState::hash()
753 //
754 // For performance reasons in non-opt mode, we specialize this for
755 // integral types.
756 // Otherwise we would be instantiating and calling dozens of functions for
757 // something that is just one multiplication and a couple xor's.
758 // The result should be the same as running the whole algorithm, but faster.
759 template <typename T, absl::enable_if_t<IntegralFastPath<T>::value, int> = 0>
760 static size_t hash(T value) {
761 return static_cast<size_t>(Mix(Seed(), static_cast<uint64_t>(value)));
762 }
763
764 // Overload of CityHashState::hash()
765 template <typename T, absl::enable_if_t<!IntegralFastPath<T>::value, int> = 0>
766 static size_t hash(const T& value) {
767 return static_cast<size_t>(combine(CityHashState{}, value).state_);
768 }
769
770 private:
771 // Invoked only once for a given argument; that plus the fact that this is
772 // move-only ensures that there is only one non-moved-from object.
773 CityHashState() : state_(Seed()) {}
774
775 // Workaround for MSVC bug.
776 // We make the type copyable to fix the calling convention, even though we
777 // never actually copy it. Keep it private to not affect the public API of the
778 // type.
779 CityHashState(const CityHashState&) = default;
780
781 explicit CityHashState(uint64_t state) : state_(state) {}
782
783 // Implementation of the base case for combine_contiguous where we actually
784 // mix the bytes into the state.
785 // Dispatch to different implementations of the combine_contiguous depending
786 // on the value of `sizeof(size_t)`.
787 static uint64_t CombineContiguousImpl(uint64_t state,
788 const unsigned char* first, size_t len,
789 std::integral_constant<int, 4>
790 /* sizeof_size_t */);
791 static uint64_t CombineContiguousImpl(uint64_t state,
792 const unsigned char* first, size_t len,
793 std::integral_constant<int, 8>
794 /* sizeof_size_t*/);
795
796 // Slow dispatch path for calls to CombineContiguousImpl with a size argument
797 // larger than PiecewiseChunkSize(). Has the same effect as calling
798 // CombineContiguousImpl() repeatedly with the chunk stride size.
799 static uint64_t CombineLargeContiguousImpl32(uint64_t state,
800 const unsigned char* first,
801 size_t len);
802 static uint64_t CombineLargeContiguousImpl64(uint64_t state,
803 const unsigned char* first,
804 size_t len);
805
806 // Reads 9 to 16 bytes from p.
807 // The first 8 bytes are in .first, the rest (zero padded) bytes are in
808 // .second.
809 static std::pair<uint64_t, uint64_t> Read9To16(const unsigned char* p,
810 size_t len) {
811 uint64_t high = little_endian::Load64(p + len - 8);
812 return {little_endian::Load64(p), high >> (128 - len * 8)};
813 }
814
815 // Reads 4 to 8 bytes from p. Zero pads to fill uint64_t.
816 static uint64_t Read4To8(const unsigned char* p, size_t len) {
817 return (static_cast<uint64_t>(little_endian::Load32(p + len - 4))
818 << (len - 4) * 8) |
819 little_endian::Load32(p);
820 }
821
822 // Reads 1 to 3 bytes from p. Zero pads to fill uint32_t.
823 static uint32_t Read1To3(const unsigned char* p, size_t len) {
824 return static_cast<uint32_t>((p[0]) | //
825 (p[len / 2] << (len / 2 * 8)) | //
826 (p[len - 1] << ((len - 1) * 8)));
827 }
828
829 ABSL_ATTRIBUTE_ALWAYS_INLINE static uint64_t Mix(uint64_t state, uint64_t v) {
830 using MultType =
831 absl::conditional_t<sizeof(size_t) == 4, uint64_t, uint128>;
832 // We do the addition in 64-bit space to make sure the 128-bit
833 // multiplication is fast. If we were to do it as MultType the compiler has
834 // to assume that the high word is non-zero and needs to perform 2
835 // multiplications instead of one.
836 MultType m = state + v;
837 m *= kMul;
838 return static_cast<uint64_t>(m ^ (m >> (sizeof(m) * 8 / 2)));
839 }
840
841 // Seed()
842 //
843 // A non-deterministic seed.
844 //
845 // The current purpose of this seed is to generate non-deterministic results
846 // and prevent having users depend on the particular hash values.
847 // It is not meant as a security feature right now, but it leaves the door
848 // open to upgrade it to a true per-process random seed. A true random seed
849 // costs more and we don't need to pay for that right now.
850 //
851 // On platforms with ASLR, we take advantage of it to make a per-process
852 // random value.
853 // See https://en.wikipedia.org/wiki/Address_space_layout_randomization
854 //
855 // On other platforms this is still going to be non-deterministic but most
856 // probably per-build and not per-process.
857 ABSL_ATTRIBUTE_ALWAYS_INLINE static uint64_t Seed() {
858 #if (!defined(__clang__) || __clang_major__ > 11) && \
859 !defined(__apple_build_version__)
860 return static_cast<uint64_t>(reinterpret_cast<uintptr_t>(&kSeed));
861 #else
862 // Workaround the absence of
863 // https://github.com/llvm/llvm-project/commit/bc15bf66dcca76cc06fe71fca35b74dc4d521021.
864 return static_cast<uint64_t>(reinterpret_cast<uintptr_t>(kSeed));
865 #endif
866 }
867 static const void* const kSeed;
868
869 uint64_t state_;
870 };
871
872 // CityHashState::CombineContiguousImpl()
873 inline uint64_t CityHashState::CombineContiguousImpl(
874 uint64_t state, const unsigned char* first, size_t len,
875 std::integral_constant<int, 4> /* sizeof_size_t */) {
876 // For large values we use CityHash, for small ones we just use a
877 // multiplicative hash.
878 uint64_t v;
879 if (len > 8) {
880 if (ABSL_PREDICT_FALSE(len > PiecewiseChunkSize())) {
881 return CombineLargeContiguousImpl32(state, first, len);
882 }
883 v = absl::hash_internal::CityHash32(reinterpret_cast<const char*>(first), len);
884 } else if (len >= 4) {
885 v = Read4To8(first, len);
886 } else if (len > 0) {
887 v = Read1To3(first, len);
888 } else {
889 // Empty ranges have no effect.
890 return state;
891 }
892 return Mix(state, v);
893 }
894
895 // Overload of CityHashState::CombineContiguousImpl()
896 inline uint64_t CityHashState::CombineContiguousImpl(
897 uint64_t state, const unsigned char* first, size_t len,
898 std::integral_constant<int, 8> /* sizeof_size_t */) {
899 // For large values we use CityHash, for small ones we just use a
900 // multiplicative hash.
901 uint64_t v;
902 if (len > 16) {
903 if (ABSL_PREDICT_FALSE(len > PiecewiseChunkSize())) {
904 return CombineLargeContiguousImpl64(state, first, len);
905 }
906 v = absl::hash_internal::CityHash64(reinterpret_cast<const char*>(first), len);
907 } else if (len > 8) {
908 auto p = Read9To16(first, len);
909 state = Mix(state, p.first);
910 v = p.second;
911 } else if (len >= 4) {
912 v = Read4To8(first, len);
913 } else if (len > 0) {
914 v = Read1To3(first, len);
915 } else {
916 // Empty ranges have no effect.
917 return state;
918 }
919 return Mix(state, v);
920 }
921
922 struct AggregateBarrier {};
923
924 // HashImpl
925
926 // Add a private base class to make sure this type is not an aggregate.
927 // Aggregates can be aggregate initialized even if the default constructor is
928 // deleted.
929 struct PoisonedHash : private AggregateBarrier {
930 PoisonedHash() = delete;
931 PoisonedHash(const PoisonedHash&) = delete;
932 PoisonedHash& operator=(const PoisonedHash&) = delete;
933 };
934
935 template <typename T>
936 struct HashImpl {
937 size_t operator()(const T& value) const { return CityHashState::hash(value); }
938 };
939
940 template <typename T>
941 struct Hash
942 : absl::conditional_t<is_hashable<T>::value, HashImpl<T>, PoisonedHash> {};
943
944 template <typename H>
945 template <typename T, typename... Ts>
946 H HashStateBase<H>::combine(H state, const T& value, const Ts&... values) {
947 return H::combine(hash_internal::HashSelect::template Apply<T>::Invoke(
948 std::move(state), value),
949 values...);
950 }
951
952 // HashStateBase::combine_contiguous()
953 template <typename H>
954 template <typename T>
955 H HashStateBase<H>::combine_contiguous(H state, const T* data, size_t size) {
956 return hash_internal::hash_range_or_bytes(std::move(state), data, size);
957 }
958
959 // HashStateBase::PiecewiseCombiner::add_buffer()
960 template <typename H>
961 H PiecewiseCombiner::add_buffer(H state, const unsigned char* data,
962 size_t size) {
963 if (position_ + size < PiecewiseChunkSize()) {
964 // This partial chunk does not fill our existing buffer
965 memcpy(buf_ + position_, data, size);
966 position_ += size;
967 return state;
968 }
969
970 // If the buffer is partially filled we need to complete the buffer
971 // and hash it.
972 if (position_ != 0) {
973 const size_t bytes_needed = PiecewiseChunkSize() - position_;
974 memcpy(buf_ + position_, data, bytes_needed);
975 state = H::combine_contiguous(std::move(state), buf_, PiecewiseChunkSize());
976 data += bytes_needed;
977 size -= bytes_needed;
978 }
979
980 // Hash whatever chunks we can without copying
981 while (size >= PiecewiseChunkSize()) {
982 state = H::combine_contiguous(std::move(state), data, PiecewiseChunkSize());
983 data += PiecewiseChunkSize();
984 size -= PiecewiseChunkSize();
985 }
986 // Fill the buffer with the remainder
987 memcpy(buf_, data, size);
988 position_ = size;
989 return state;
990 }
991
992 // HashStateBase::PiecewiseCombiner::finalize()
993 template <typename H>
994 H PiecewiseCombiner::finalize(H state) {
995 // Hash the remainder left in the buffer, which may be empty
996 return H::combine_contiguous(std::move(state), buf_, position_);
997 }
998
999 } // namespace hash_internal
1000 ABSL_NAMESPACE_END
1001 } // namespace absl
1002
1003 #endif // ABSL_HASH_INTERNAL_HASH_H_
1004