From fcb104594b0bb4b8ac306cb2f55ecdad40974683 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Tue, 4 Dec 2018 11:01:12 -0800 Subject: Creation of LTS branch "lts_2018_12_18" - 44b0fafc62d9b8f192e8180cbe9c4b806b339d57 Export of internal Abseil changes. by Abseil Team - 926bfeb9fff223429c12224b7514243886323e8d Export of internal Abseil changes. by Abseil Team - 13327debebc5c2d1d4991b69fe50450e340e50e4 Export of internal Abseil changes. by Abseil Team - 3088e76c597e068479e82508b1770a7ad0c806b6 Export of internal Abseil changes. by Abseil Team - f6ae816808cd913e0e2b3e2af14f328fa1071af0 Export of internal Abseil changes. by Abseil Team - a06c4a1d9093137b7217a5aaba8920d62e835dc0 Export of internal Abseil changes. by Abseil Team - 7b46e1d31a6b08b1c6da2a13e7b151a20446fa07 Export of internal Abseil changes. by Abseil Team - 070f6e47b33a2909d039e620c873204f78809492 Export of internal Abseil changes. by Abseil Team - 7990fd459e9339467814ddb95000c87cb1e4d945 Export of internal Abseil changes. by Abseil Team - f95179062eb65ce40895cc76f1398cce25394369 Export of internal Abseil changes. by Abseil Team - cc8dcd307b76a575d2e3e0958a4fe4c7193c2f68 Export of internal Abseil changes. by Abseil Team - a705aa78dc76fc5c79d501e61dcc077eca68a8a4 Merge pull request #194 from Mizux/windows by Xiaoyi Zhang - a4c3ffff11eec0ee45742f915c255e9f870b7e0f Export of internal Abseil changes. by Abseil Team - 01174578651b73021d9b8c3820f6fea707dacdf0 Merge pull request #201 from ccawley2011/fix-byteswap by Matt Calabrese <38107210+mattcalabrese-google@users.noreply.github.com> - f86f9413856b65afdd61fea938d684b8ab73115a Export of internal Abseil changes. by Abseil Team - 94c298e2a0ae409e283cab96c954a685bd865a70 Export of internal Abseil changes. by Abseil Team - 0884a6a04e4497d11b1b398cc0e422b118bf977a Export of internal Abseil changes. by Abseil Team - c16d5557cd05119b5b7b1318ef778ebe3195b4a1 Export of internal Abseil changes. by Abseil Team - 45221ccc4ed643e4209b0cc5798e97203f108fa8 Export of internal Abseil changes. by Abseil Team - 2019e17a520575ab365b2b5134d71068182c70b8 Export of internal Abseil changes. by Abseil Team - 5b70a8910b2e6fb0ce5193a41873139a126d2f7f Export of internal Abseil changes. by Abseil Team - a00bdd176d66ef0b417d9576052a19091fbdf891 Export of internal Abseil changes. by Abseil Team - f340f773edab951656b19b6f1a77c964a78ec4c2 Export of internal Abseil changes. by Abseil Team - 445998d7ac4e5d3c50411d377e3b50e960d2d6c2 Export of internal Abseil changes. by Abseil Team - e821380d69a549dc64900693942789d21aa4df5e Export of internal Abseil changes. by Abseil Team - f21d187b80e3b7f08fb279775ea9c8b48c636030 Export of internal Abseil changes. by Abseil Team - 5441bbe1db5d0f2ca24b5b60166367b0966790af Fix code snippet in comment (#174) by Loo Rong Jie - 5aae0cffae8ffaacab965756169b34e511b353df Fix CMake build (#173) by Stephan Dollberg - 48cd2c3f351ff188bc85684b84a91b6e6d17d896 Export of internal Abseil changes. by Abseil Team - e291c279e458761e77a69b09b129d3d1e81f1e80 Export of internal Abseil changes. by Abseil Team - e01d95528ea2137a4a27a88d1f57c6cb260aafed Export of internal Abseil changes. by Abseil Team - 8ff1374008259719b54a8cb128ef951c02da164c Export of internal Abseil changes. by Abseil Team - 02451914b9ad5320f81f56a89f3eef1f8683227c Export of internal Abseil changes. by Abseil Team - 921fd5cf02ec0d665439a790148d59faa7d4a72c Merge pull request #166 from rongjiecomputer/cmake-test by Gennadiy Civil - fb462224c058487763f263b7995d70efd0242c17 Export of internal Abseil changes. by Abseil Team - c075ad321696fa5072e097f0a51e4fe76a6fe13e Export of internal Abseil changes. by Abseil Team - 0f4bc966754ec6cd28d5f03467d56f1efdc598e3 Export of internal Abseil changes. by Abseil Team - 6c7e5ffc43decd92f7bdfc510ad8a245a20b6dea Export of internal Abseil changes. by Abseil Team - d6df769173bf0263489f98874b93034db0e479a2 Export of internal Abseil changes. by Abseil Team - 28080f5f050c9530aa9f2b39c60d8217038d64ff Export of internal Abseil changes. by Abseil Team - 9c987f429bba32fb4446280fd3b91e2472d71d4d Export of internal Abseil changes. by Abseil Team - 5e7d459eeca7bc53deab0ee9634601386b53d7c0 Export of internal Abseil changes. by Abseil Team - bed5bd6e185c7e0311f3a1f2dab4c96083dac636 Export of internal Abseil changes. by Abseil Team - fefc83638fb69395d259ed245699310610429064 Export of internal Abseil changes. by Abseil Team - d8cfe9f2a77fbee02c09642491e62a3f3677e0f6 Export of internal Abseil changes. by Abseil Team - ad5c960b2eb914881d1ceba0e996a0a8f3f6ca59 Export of internal Abseil changes. by Abseil Team - 86f0fe93ad9d6d033a319476736a3256369c1f75 Export of internal Abseil changes. by Abseil Team - f0f15c2778b0e4959244dd25e63f445a455870f5 Export of internal Abseil changes. by Abseil Team - 29ff6d4860070bf8fcbd39c8805d0c32d56628a3 Removed "warning treated as error" flag from MSVC (#153) by vocaviking - 083d04dd4a62ebbf037079b06e49b323c5e1192a Export of internal Abseil changes. by Abseil Team - bea85b52733022294eef108a2e42d77b616ddca2 Export of internal Abseil changes. by Abseil Team - 8f96be6ca60d967bd4b37f93d0a03bcff4145200 Export of internal Abseil changes. by Abseil Team - 92e07e5590752d6b8e67f7f2f86c6286561e8cea Merge pull request #152 from clnperez/fix-multi-defines-p... by Derek Mauro <761129+derekmauro@users.noreply.github.com> - 2125e6444a9de9e41f21ecdc674dd7d8759c149d Export of internal Abseil changes. by Abseil Team - 9acad869d21731f5bc50430a33fe61cc0ffcbb0b Merge pull request #150 from OlafvdSpek/patch-2 by Jonathan Cohen - c2e00d341913bf03b4597ade5b056042e23e8c58 Export of internal Abseil changes. by Abseil Team - 9e060686d1c325f34f9806b45fe77bafeed00aee Export of internal Abseil changes. by Abseil Team - 7aa411ceafc1272a28579cca739a97a2fb79055a Export of internal Abseil changes. by Abseil Team - 2c5af55ed34850d8b7dd46177c8ca53fdfda920e Export of internal Abseil changes. by Abseil Team - 44aa275286baf97fc13529aca547a88b180beb08 Merge pull request #143 from rongjiecomputer/kernel by Xiaoyi Zhang - 42f22a28401c952f1fc5942231c7fdac80811bf5 Export of internal Abseil changes. by Abseil Team - b973bc53ef366f0253b85eeed9a79b241884a843 Merge pull request #139 from siepkes/smartos-support by ahedberg - e0def7473e52336f58759e11db4cd9467e5e0356 Export of internal Abseil changes. by Abseil Team - f826f1d489b61b64df1d94afbe5981841a82e5fa Merge pull request #138 from edbaunton/remove-deprecated-... by ahedberg - 7b50a4a94b0c7df68b3a854c850b551aaef0a8b4 Export of internal Abseil changes. by Abseil Team - a5030ca5125b9d557ecfeea8acc8b1a8e49f6d27 Merge pull request #144 from rongjiecomputer/winsock2 by Xiaoyi Zhang - 02687955b7ca8fc02ada9b14bc247deeb108d341 Export of internal Abseil changes. by Abseil Team - 8f612ebb152fb7e05643a2bcf78cb89a8c0641ad Export of internal Abseil changes. by Abseil Team - 134496a31d8b324f762de3bee9a002658c984456 Export of internal Abseil changes. by Abseil Team - ba8d6cf07766263723e86736f20a51c1c9c67b19 Export of internal Abseil changes. by Abseil Team - be1e84b988fceabcea4fc9e93f899539f0c81901 Export of internal Abseil changes. by Abseil Team - 16ac2ec2e38cdf47f9330a312e319d57da659c10 Merge pull request #134 from rongjiecomputer/cmake by Alex Strelnikov - 7efd8dc0f1075356e9c7caa950afd1ecf854e8b9 Export of internal Abseil changes. by Abseil Team - 87a4c07856e7dc69958019d47b2f02ae47746ec0 Export of internal Abseil changes. by Abseil Team - 4491d606df34c44efda47b6d17b605262f17e182 Export of internal Abseil changes. by Abseil Team GitOrigin-RevId: 44b0fafc62d9b8f192e8180cbe9c4b806b339d57 Change-Id: I2c427b5b41b2d34101922048b00f3d9dafcb498d --- absl/hash/internal/hash.h | 898 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 898 insertions(+) create mode 100644 absl/hash/internal/hash.h (limited to 'absl/hash/internal/hash.h') diff --git a/absl/hash/internal/hash.h b/absl/hash/internal/hash.h new file mode 100644 index 00000000..a51ca954 --- /dev/null +++ b/absl/hash/internal/hash.h @@ -0,0 +1,898 @@ +// Copyright 2018 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +// +// ----------------------------------------------------------------------------- +// File: hash.h +// ----------------------------------------------------------------------------- +// +#ifndef ABSL_HASH_INTERNAL_HASH_H_ +#define ABSL_HASH_INTERNAL_HASH_H_ + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include "absl/base/internal/endian.h" +#include "absl/base/port.h" +#include "absl/container/fixed_array.h" +#include "absl/meta/type_traits.h" +#include "absl/numeric/int128.h" +#include "absl/strings/string_view.h" +#include "absl/types/optional.h" +#include "absl/types/variant.h" +#include "absl/utility/utility.h" +#include "absl/hash/internal/city.h" + +namespace absl { +inline namespace lts_2018_12_18 { +namespace hash_internal { + +// HashStateBase +// +// A hash state object represents an intermediate state in the computation +// of an unspecified hash algorithm. `HashStateBase` provides a CRTP style +// base class for hash state implementations. Developers adding type support +// for `absl::Hash` should not rely on any parts of the state object other than +// the following member functions: +// +// * HashStateBase::combine() +// * HashStateBase::combine_contiguous() +// +// A derived hash state class of type `H` must provide a static member function +// with a signature similar to the following: +// +// `static H combine_contiguous(H state, const unsigned char*, size_t)`. +// +// `HashStateBase` will provide a complete implementations for a hash state +// object in terms of this method. +// +// Example: +// +// // Use CRTP to define your derived class. +// struct MyHashState : HashStateBase { +// static H combine_contiguous(H state, const unsigned char*, size_t); +// using MyHashState::HashStateBase::combine; +// using MyHashState::HashStateBase::combine_contiguous; +// }; +template +class HashStateBase { + public: + // HashStateBase::combine() + // + // Combines an arbitrary number of values into a hash state, returning the + // updated state. + // + // Each of the value types `T` must be separately hashable by the Abseil + // hashing framework. + // + // NOTE: + // + // state = H::combine(std::move(state), value1, value2, value3); + // + // is guaranteed to produce the same hash expansion as: + // + // state = H::combine(std::move(state), value1); + // state = H::combine(std::move(state), value2); + // state = H::combine(std::move(state), value3); + template + static H combine(H state, const T& value, const Ts&... values); + static H combine(H state) { return state; } + + // HashStateBase::combine_contiguous() + // + // Combines a contiguous array of `size` elements into a hash state, returning + // the updated state. + // + // NOTE: + // + // state = H::combine_contiguous(std::move(state), data, size); + // + // is NOT guaranteed to produce the same hash expansion as a for-loop (it may + // perform internal optimizations). If you need this guarantee, use the + // for-loop instead. + template + static H combine_contiguous(H state, const T* data, size_t size); +}; + +// is_uniquely_represented +// +// `is_uniquely_represented` is a trait class that indicates whether `T` +// is uniquely represented. +// +// A type is "uniquely represented" if two equal values of that type are +// guaranteed to have the same bytes in their underlying storage. In other +// words, if `a == b`, then `memcmp(&a, &b, sizeof(T))` is guaranteed to be +// zero. This property cannot be detected automatically, so this trait is false +// by default, but can be specialized by types that wish to assert that they are +// uniquely represented. This makes them eligible for certain optimizations. +// +// If you have any doubt whatsoever, do not specialize this template. +// The default is completely safe, and merely disables some optimizations +// that will not matter for most types. Specializing this template, +// on the other hand, can be very hazardous. +// +// To be uniquely represented, a type must not have multiple ways of +// representing the same value; for example, float and double are not +// uniquely represented, because they have distinct representations for +// +0 and -0. Furthermore, the type's byte representation must consist +// solely of user-controlled data, with no padding bits and no compiler- +// controlled data such as vptrs or sanitizer metadata. This is usually +// very difficult to guarantee, because in most cases the compiler can +// insert data and padding bits at its own discretion. +// +// If you specialize this template for a type `T`, you must do so in the file +// that defines that type (or in this file). If you define that specialization +// anywhere else, `is_uniquely_represented` could have different meanings +// in different places. +// +// The Enable parameter is meaningless; it is provided as a convenience, +// to support certain SFINAE techniques when defining specializations. +template +struct is_uniquely_represented : std::false_type {}; + +// is_uniquely_represented +// +// unsigned char is a synonym for "byte", so it is guaranteed to be +// uniquely represented. +template <> +struct is_uniquely_represented : std::true_type {}; + +// is_uniquely_represented for non-standard integral types +// +// Integral types other than bool should be uniquely represented on any +// platform that this will plausibly be ported to. +template +struct is_uniquely_represented< + Integral, typename std::enable_if::value>::type> + : std::true_type {}; + +// is_uniquely_represented +// +// +template <> +struct is_uniquely_represented : std::false_type {}; + +// hash_bytes() +// +// Convenience function that combines `hash_state` with the byte representation +// of `value`. +template +H hash_bytes(H hash_state, const T& value) { + const unsigned char* start = reinterpret_cast(&value); + return H::combine_contiguous(std::move(hash_state), start, sizeof(value)); +} + +// ----------------------------------------------------------------------------- +// AbslHashValue for Basic Types +// ----------------------------------------------------------------------------- + +// Note: Default `AbslHashValue` implementations live in `hash_internal`. This +// allows us to block lexical scope lookup when doing an unqualified call to +// `AbslHashValue` below. User-defined implementations of `AbslHashValue` can +// only be found via ADL. + +// AbslHashValue() for hashing bool values +// +// We use SFINAE to ensure that this overload only accepts bool, not types that +// are convertible to bool. +template +typename std::enable_if::value, H>::type AbslHashValue( + H hash_state, B value) { + return H::combine(std::move(hash_state), + static_cast(value ? 1 : 0)); +} + +// AbslHashValue() for hashing enum values +template +typename std::enable_if::value, H>::type AbslHashValue( + H hash_state, Enum e) { + // In practice, we could almost certainly just invoke hash_bytes directly, + // but it's possible that a sanitizer might one day want to + // store data in the unused bits of an enum. To avoid that risk, we + // convert to the underlying type before hashing. Hopefully this will get + // optimized away; if not, we can reopen discussion with c-toolchain-team. + return H::combine(std::move(hash_state), + static_cast::type>(e)); +} +// AbslHashValue() for hashing floating-point values +template +typename std::enable_if::value, H>::type +AbslHashValue(H hash_state, Float value) { + return hash_internal::hash_bytes(std::move(hash_state), + value == 0 ? 0 : value); +} + +// Long double has the property that it might have extra unused bytes in it. +// For example, in x86 sizeof(long double)==16 but it only really uses 80-bits +// of it. This means we can't use hash_bytes on a long double and have to +// convert it to something else first. +template +H AbslHashValue(H hash_state, long double value) { + const int category = std::fpclassify(value); + switch (category) { + case FP_INFINITE: + // Add the sign bit to differentiate between +Inf and -Inf + hash_state = H::combine(std::move(hash_state), std::signbit(value)); + break; + + case FP_NAN: + case FP_ZERO: + default: + // Category is enough for these. + break; + + case FP_NORMAL: + case FP_SUBNORMAL: + // We can't convert `value` directly to double because this would have + // undefined behavior if the value is out of range. + // std::frexp gives us a value in the range (-1, -.5] or [.5, 1) that is + // guaranteed to be in range for `double`. The truncation is + // implementation defined, but that works as long as it is deterministic. + int exp; + auto mantissa = static_cast(std::frexp(value, &exp)); + hash_state = H::combine(std::move(hash_state), mantissa, exp); + } + + return H::combine(std::move(hash_state), category); +} + +// AbslHashValue() for hashing pointers +template +H AbslHashValue(H hash_state, T* ptr) { + return hash_internal::hash_bytes(std::move(hash_state), ptr); +} + +// AbslHashValue() for hashing nullptr_t +template +H AbslHashValue(H hash_state, std::nullptr_t) { + return H::combine(std::move(hash_state), static_cast(nullptr)); +} + +// ----------------------------------------------------------------------------- +// AbslHashValue for Composite Types +// ----------------------------------------------------------------------------- + +// is_hashable() +// +// Trait class which returns true if T is hashable by the absl::Hash framework. +// Used for the AbslHashValue implementations for composite types below. +template +struct is_hashable; + +// AbslHashValue() for hashing pairs +template +typename std::enable_if::value && is_hashable::value, + H>::type +AbslHashValue(H hash_state, const std::pair& p) { + return H::combine(std::move(hash_state), p.first, p.second); +} + +// hash_tuple() +// +// Helper function for hashing a tuple. The third argument should +// be an index_sequence running from 0 to tuple_size - 1. +template +H hash_tuple(H hash_state, const Tuple& t, absl::index_sequence) { + return H::combine(std::move(hash_state), std::get(t)...); +} + +// AbslHashValue for hashing tuples +template +#if defined(_MSC_VER) +// This SFINAE gets MSVC confused under some conditions. Let's just disable it +// for now. +H +#else // _MSC_VER +typename std::enable_if...>::value, H>::type +#endif // _MSC_VER +AbslHashValue(H hash_state, const std::tuple& t) { + return hash_internal::hash_tuple(std::move(hash_state), t, + absl::make_index_sequence()); +} + +// ----------------------------------------------------------------------------- +// AbslHashValue for Pointers +// ----------------------------------------------------------------------------- + +// AbslHashValue for hashing unique_ptr +template +H AbslHashValue(H hash_state, const std::unique_ptr& ptr) { + return H::combine(std::move(hash_state), ptr.get()); +} + +// AbslHashValue for hashing shared_ptr +template +H AbslHashValue(H hash_state, const std::shared_ptr& ptr) { + return H::combine(std::move(hash_state), ptr.get()); +} + +// ----------------------------------------------------------------------------- +// AbslHashValue for String-Like Types +// ----------------------------------------------------------------------------- + +// AbslHashValue for hashing strings +// +// All the string-like types supported here provide the same hash expansion for +// the same character sequence. These types are: +// +// - `std::string` (and std::basic_string, A> for +// any allocator A) +// - `absl::string_view` and `std::string_view` +// +// For simplicity, we currently support only `char` strings. This support may +// be broadened, if necessary, but with some caution - this overload would +// misbehave in cases where the traits' `eq()` member isn't equivalent to `==` +// on the underlying character type. +template +H AbslHashValue(H hash_state, absl::string_view str) { + return H::combine( + H::combine_contiguous(std::move(hash_state), str.data(), str.size()), + str.size()); +} + +// ----------------------------------------------------------------------------- +// AbslHashValue for Sequence Containers +// ----------------------------------------------------------------------------- + +// AbslHashValue for hashing std::array +template +typename std::enable_if::value, H>::type AbslHashValue( + H hash_state, const std::array& array) { + return H::combine_contiguous(std::move(hash_state), array.data(), + array.size()); +} + +// AbslHashValue for hashing std::deque +template +typename std::enable_if::value, H>::type AbslHashValue( + H hash_state, const std::deque& deque) { + // TODO(gromer): investigate a more efficient implementation taking + // advantage of the chunk structure. + for (const auto& t : deque) { + hash_state = H::combine(std::move(hash_state), t); + } + return H::combine(std::move(hash_state), deque.size()); +} + +// AbslHashValue for hashing std::forward_list +template +typename std::enable_if::value, H>::type AbslHashValue( + H hash_state, const std::forward_list& list) { + size_t size = 0; + for (const T& t : list) { + hash_state = H::combine(std::move(hash_state), t); + ++size; + } + return H::combine(std::move(hash_state), size); +} + +// AbslHashValue for hashing std::list +template +typename std::enable_if::value, H>::type AbslHashValue( + H hash_state, const std::list& list) { + for (const auto& t : list) { + hash_state = H::combine(std::move(hash_state), t); + } + return H::combine(std::move(hash_state), list.size()); +} + +// AbslHashValue for hashing std::vector +// +// Do not use this for vector. It does not have a .data(), and a fallback +// for std::hash<> is most likely faster. +template +typename std::enable_if::value && !std::is_same::value, + H>::type +AbslHashValue(H hash_state, const std::vector& vector) { + return H::combine(H::combine_contiguous(std::move(hash_state), vector.data(), + vector.size()), + vector.size()); +} + +// ----------------------------------------------------------------------------- +// AbslHashValue for Ordered Associative Containers +// ----------------------------------------------------------------------------- + +// AbslHashValue for hashing std::map +template +typename std::enable_if::value && is_hashable::value, + H>::type +AbslHashValue(H hash_state, const std::map& map) { + for (const auto& t : map) { + hash_state = H::combine(std::move(hash_state), t); + } + return H::combine(std::move(hash_state), map.size()); +} + +// AbslHashValue for hashing std::multimap +template +typename std::enable_if::value && is_hashable::value, + H>::type +AbslHashValue(H hash_state, + const std::multimap& map) { + for (const auto& t : map) { + hash_state = H::combine(std::move(hash_state), t); + } + return H::combine(std::move(hash_state), map.size()); +} + +// AbslHashValue for hashing std::set +template +typename std::enable_if::value, H>::type AbslHashValue( + H hash_state, const std::set& set) { + for (const auto& t : set) { + hash_state = H::combine(std::move(hash_state), t); + } + return H::combine(std::move(hash_state), set.size()); +} + +// AbslHashValue for hashing std::multiset +template +typename std::enable_if::value, H>::type AbslHashValue( + H hash_state, const std::multiset& set) { + for (const auto& t : set) { + hash_state = H::combine(std::move(hash_state), t); + } + return H::combine(std::move(hash_state), set.size()); +} + +// ----------------------------------------------------------------------------- +// AbslHashValue for Wrapper Types +// ----------------------------------------------------------------------------- + +// AbslHashValue for hashing absl::optional +template +typename std::enable_if::value, H>::type AbslHashValue( + H hash_state, const absl::optional& opt) { + if (opt) hash_state = H::combine(std::move(hash_state), *opt); + return H::combine(std::move(hash_state), opt.has_value()); +} + +// VariantVisitor +template +struct VariantVisitor { + H&& hash_state; + template + H operator()(const T& t) const { + return H::combine(std::move(hash_state), t); + } +}; + +// AbslHashValue for hashing absl::variant +template +typename std::enable_if...>::value, H>::type +AbslHashValue(H hash_state, const absl::variant& v) { + if (!v.valueless_by_exception()) { + hash_state = absl::visit(VariantVisitor{std::move(hash_state)}, v); + } + return H::combine(std::move(hash_state), v.index()); +} + +// ----------------------------------------------------------------------------- +// AbslHashValue for Other Types +// ----------------------------------------------------------------------------- + +// AbslHashValue for hashing std::bitset is not defined, for the same reason as +// for vector (see std::vector above): It does not expose the raw bytes, +// and a fallback to std::hash<> is most likely faster. + +// ----------------------------------------------------------------------------- + +// hash_range_or_bytes() +// +// Mixes all values in the range [data, data+size) into the hash state. +// This overload accepts only uniquely-represented types, and hashes them by +// hashing the entire range of bytes. +template +typename std::enable_if::value, H>::type +hash_range_or_bytes(H hash_state, const T* data, size_t size) { + const auto* bytes = reinterpret_cast(data); + return H::combine_contiguous(std::move(hash_state), bytes, sizeof(T) * size); +} + +// hash_range_or_bytes() +template +typename std::enable_if::value, H>::type +hash_range_or_bytes(H hash_state, const T* data, size_t size) { + for (const auto end = data + size; data < end; ++data) { + hash_state = H::combine(std::move(hash_state), *data); + } + return hash_state; +} + +// InvokeHashTag +// +// InvokeHash(H, const T&) invokes the appropriate hash implementation for a +// hasher of type `H` and a value of type `T`. If `T` is not hashable, there +// will be no matching overload of InvokeHash(). +// Note: Some platforms (eg MSVC) do not support the detect idiom on +// std::hash. In those platforms the last fallback will be std::hash and +// InvokeHash() will always have a valid overload even if std::hash is not +// valid. +// +// We try the following options in order: +// * If is_uniquely_represented, hash bytes directly. +// * ADL AbslHashValue(H, const T&) call. +// * std::hash + +// In MSVC we can't probe std::hash or stdext::hash because it triggers a +// static_assert instead of failing substitution. +#if defined(_MSC_VER) +#define ABSL_HASH_INTERNAL_CAN_POISON_ 0 +#else // _MSC_VER +#define ABSL_HASH_INTERNAL_CAN_POISON_ 1 +#endif // _MSC_VER + +#if defined(ABSL_INTERNAL_LEGACY_HASH_NAMESPACE) && \ + ABSL_HASH_INTERNAL_CAN_POISON_ +#define ABSL_HASH_INTERNAL_SUPPORT_LEGACY_HASH_ 1 +#else +#define ABSL_HASH_INTERNAL_SUPPORT_LEGACY_HASH_ 0 +#endif + +enum class InvokeHashTag { + kUniquelyRepresented, + kHashValue, +#if ABSL_HASH_INTERNAL_SUPPORT_LEGACY_HASH_ + kLegacyHash, +#endif // ABSL_HASH_INTERNAL_SUPPORT_LEGACY_HASH_ + kStdHash, + kNone +}; + +// HashSelect +// +// Type trait to select the appropriate hash implementation to use. +// HashSelect::value is an instance of InvokeHashTag that indicates the best +// available hashing mechanism. +// See `Note` above about MSVC. +template +struct HashSelect { + private: + struct State : HashStateBase { + static State combine_contiguous(State hash_state, const unsigned char*, + size_t); + using State::HashStateBase::combine_contiguous; + }; + + // `Probe::value` evaluates to `V::value` if it is a valid + // expression, and `false` otherwise. + // `Probe::tag` always evaluates to `Tag`. + template