From d936052d32a5b7ca08b0199a6724724aea432309 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Mon, 9 Mar 2020 12:34:31 -0700 Subject: Export of internal Abseil changes -- 2c5c118f0615ba90e48ee2f18eccc9f511740f6d by Samuel Benzaquen : Rename internal macros to follow the convention in absl. PiperOrigin-RevId: 299906738 -- 92d84a707c7ebc4ec19bdd92d5765d1b6d218c1e by Derek Mauro : Import GitHub #629: Skip the .exe suffix in the helpshort filter on Windows PiperOrigin-RevId: 299892396 -- 2a6910d4be6c67a8376628764121b528ff53504d by Abseil Team : Use unsigned int128 intrinsic when available. It generates better branchless code. PiperOrigin-RevId: 299848585 -- 110c16cf0a739e1df5028fb6fbd03ef5dde1d278 by Derek Mauro : Import GitHub #594: Avoid reading the registry for Windows UWP apps PiperOrigin-RevId: 299821671 -- d8397d367e88163e5e8a47f379c716352dc91d03 by Greg Falcon : Add absl::Hash support for Cord. The hash function is heterogeneous with other string types: a Cord and a string with the same byte sequence will hash to the same value. SwissTable types know about Cord, and will allow heterogeneous lookup (e.g., you can pass a Cord to flat_hash_map::find(), and vice versa.) Add a missing dependency to the cmake Cord target. PiperOrigin-RevId: 299443713 GitOrigin-RevId: 2c5c118f0615ba90e48ee2f18eccc9f511740f6d Change-Id: I7b087c7984b0cb52c4b337d49266c467b98ebdf9 --- absl/hash/BUILD.bazel | 2 ++ absl/hash/CMakeLists.txt | 2 ++ absl/hash/hash.h | 1 + absl/hash/hash_test.cc | 49 +++++++++++++++++++++++++++++++++-------------- absl/hash/internal/hash.h | 21 ++++++++++++++++++++ 5 files changed, 61 insertions(+), 14 deletions(-) (limited to 'absl/hash') diff --git a/absl/hash/BUILD.bazel b/absl/hash/BUILD.bazel index ffe8c294a0bc..59eac78484ac 100644 --- a/absl/hash/BUILD.bazel +++ b/absl/hash/BUILD.bazel @@ -43,6 +43,7 @@ cc_library( "//absl/meta:type_traits", "//absl/numeric:int128", "//absl/strings", + "//absl/strings:cord", "//absl/types:optional", "//absl/types:variant", "//absl/utility", @@ -76,6 +77,7 @@ cc_test( "//absl/container:flat_hash_set", "//absl/meta:type_traits", "//absl/numeric:int128", + "//absl/strings:cord_test_helpers", "@com_google_googletest//:gtest_main", ], ) diff --git a/absl/hash/CMakeLists.txt b/absl/hash/CMakeLists.txt index febc551fcedb..4e55514743b0 100644 --- a/absl/hash/CMakeLists.txt +++ b/absl/hash/CMakeLists.txt @@ -25,6 +25,7 @@ absl_cc_library( COPTS ${ABSL_DEFAULT_COPTS} DEPS + absl::cord absl::core_headers absl::endian absl::fixed_array @@ -62,6 +63,7 @@ absl_cc_test( COPTS ${ABSL_TEST_COPTS} DEPS + absl::cord_test_helpers absl::hash absl::hash_testing absl::core_headers diff --git a/absl/hash/hash.h b/absl/hash/hash.h index 23a65ea8687e..3dbeab6977af 100644 --- a/absl/hash/hash.h +++ b/absl/hash/hash.h @@ -98,6 +98,7 @@ ABSL_NAMESPACE_BEGIN // * std::tuple, if all the Ts... are hashable // * std::unique_ptr and std::shared_ptr // * All string-like types including: +// * absl::Cord // * std::string // * std::string_view (as well as any instance of std::basic_string that // uses char and std::char_traits) diff --git a/absl/hash/hash_test.cc b/absl/hash/hash_test.cc index f02a537ae8fc..e55e0ca9545f 100644 --- a/absl/hash/hash_test.cc +++ b/absl/hash/hash_test.cc @@ -42,6 +42,7 @@ #include "absl/hash/internal/spy_hash_state.h" #include "absl/meta/type_traits.h" #include "absl/numeric/int128.h" +#include "absl/strings/cord_test_helpers.h" namespace { @@ -269,6 +270,22 @@ struct WrapInTuple { } }; +absl::Cord FlatCord(absl::string_view sv) { + absl::Cord c(sv); + c.Flatten(); + return c; +} + +absl::Cord FragmentedCord(absl::string_view sv) { + if (sv.size() < 2) { + return absl::Cord(sv); + } + size_t halfway = sv.size() / 2; + std::vector parts = {sv.substr(0, halfway), + sv.substr(halfway)}; + return absl::MakeFragmentedCord(parts); +} + TEST(HashValueTest, Strings) { EXPECT_TRUE((is_hashable::value)); @@ -277,23 +294,27 @@ TEST(HashValueTest, Strings) { const std::string large = std::string(2048, 'x'); // multiple of chunk size const std::string huge = std::string(5000, 'a'); // not a multiple - EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple( - std::string(), absl::string_view(), - std::string(""), absl::string_view(""), - std::string(small), absl::string_view(small), - std::string(dup), absl::string_view(dup), - std::string(large), absl::string_view(large), - std::string(huge), absl::string_view(huge)))); + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple( // + std::string(), absl::string_view(), absl::Cord(), // + std::string(""), absl::string_view(""), absl::Cord(""), // + std::string(small), absl::string_view(small), absl::Cord(small), // + std::string(dup), absl::string_view(dup), absl::Cord(dup), // + std::string(large), absl::string_view(large), absl::Cord(large), // + std::string(huge), absl::string_view(huge), FlatCord(huge), // + FragmentedCord(huge)))); // Also check that nested types maintain the same hash. const WrapInTuple t{}; - EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple( - t(std::string()), t(absl::string_view()), - t(std::string("")), t(absl::string_view("")), - t(std::string(small)), t(absl::string_view(small)), - t(std::string(dup)), t(absl::string_view(dup)), - t(std::string(large)), t(absl::string_view(large)), - t(std::string(huge)), t(absl::string_view(huge))))); + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple( // + t(std::string()), t(absl::string_view()), t(absl::Cord()), // + t(std::string("")), t(absl::string_view("")), t(absl::Cord("")), // + t(std::string(small)), t(absl::string_view(small)), // + t(absl::Cord(small)), // + t(std::string(dup)), t(absl::string_view(dup)), t(absl::Cord(dup)), // + t(std::string(large)), t(absl::string_view(large)), // + t(absl::Cord(large)), // + t(std::string(huge)), t(absl::string_view(huge)), // + t(FlatCord(huge)), t(FragmentedCord(huge))))); // Make sure that hashing a `const char*` does not use its std::string-value. EXPECT_NE(SpyHash(static_cast("ABC")), diff --git a/absl/hash/internal/hash.h b/absl/hash/internal/hash.h index 1cc2c5e5ae48..025d287f39c9 100644 --- a/absl/hash/internal/hash.h +++ b/absl/hash/internal/hash.h @@ -43,6 +43,7 @@ #include "absl/container/fixed_array.h" #include "absl/meta/type_traits.h" #include "absl/numeric/int128.h" +#include "absl/strings/cord.h" #include "absl/strings/string_view.h" #include "absl/types/optional.h" #include "absl/types/variant.h" @@ -413,6 +414,7 @@ H AbslHashValue(H hash_state, const std::shared_ptr& ptr) { // All the string-like types supported here provide the same hash expansion for // the same character sequence. These types are: // +// - `absl::Cord` // - `std::string` (and std::basic_string, A> for // any allocator A) // - `absl::string_view` and `std::string_view` @@ -441,6 +443,25 @@ H AbslHashValue( str.size()); } +template +H HashFragmentedCord(H hash_state, const absl::Cord& c) { + PiecewiseCombiner combiner; + c.ForEachChunk([&combiner, &hash_state](absl::string_view chunk) { + hash_state = + combiner.add_buffer(std::move(hash_state), chunk.data(), chunk.size()); + }); + return H::combine(combiner.finalize(std::move(hash_state)), c.size()); +} + +template +H AbslHashValue(H hash_state, const absl::Cord& c) { + absl::optional maybe_flat = c.TryFlat(); + if (maybe_flat.has_value()) { + return H::combine(std::move(hash_state), *maybe_flat); + } + return hash_internal::HashFragmentedCord(std::move(hash_state), c); +} + // ----------------------------------------------------------------------------- // AbslHashValue for Sequence Containers // ----------------------------------------------------------------------------- -- cgit 1.4.1