diff options
author | 2020-02-25 22:27:31 +0100 | |
---|---|---|
committer | 2020-02-25 17:56:58 -0500 | |
commit | b832dce8489ef7b6231384909fd9b68d5a5ff2b7 (patch) | |
tree | 3ad4be9a9a4105366be714da9458e076a77be18f /absl/hash | |
parent | aa844899c937bde5d2b24f276b59997e5b668bde (diff) |
Creation of LTS branch "lts_2020_02_25"20200225
- 0033c9ea91a52ade7c6b725aa2ef3cbe15463421 Fix build on FreeBSD/powerpc (#616) by kgotlinux <60880393+kgotlinux@users.noreply.github.com>
- 0d5ce2797eb695aee7e019e25323251ef6ffc277 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- b69c7d880caddfc25bf348dbcfe9d45fdd8bc6e6 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 2a5633fc077a58528cdbfe78720f3f6bfdc6044d Merge "Export of internal Abseil changes" by Xiaoyi Zhang <zhangxy@google.com>
- f9b3d6e493c1b6ab3dbdab71c5f8fa849db4abaf Add RISCV support to GetProgramCounter() (#621) by Khem Raj <raj.khem@gmail.com>
- 0232c87f21c26718aa3eb2d86678070f3b498a4e Add missing ABSL_HAVE_VDSO_SUPPORT conditional (#622) by Sinan Kaya <41809318+franksinankaya@users.noreply.github.com>
- 3c814105108680997d0821077694f663693b5382 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- c44657f55692eddf5504156645d1f4ec7b3acabd Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 98eb410c93ad059f9bba1bf43f5bb916fc92a5ea Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- bf78e977309c4cb946914b456404141ddac1c302 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- d95d1567165d449e4c213ea31a15cbb112a9865f Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 24713a7036a81498334807fa5c7ad3cb7c643711 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 72382c21fefed981b4b8a2a1b82e2d231c2c2e39 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 08a7e7bf972c8451855a5022f2faf3d3655db015 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 36bcd9599b3f48c99357ba61cf33584889306d6a Fix pointer format specifier in documentation (#614) by Andre Nguyen <andre-nguyen@users.noreply.github.com>
- 0f86336b6939ea673cc1cbe29189286cae67d63a Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- c512f118dde6ffd51cb7d8ac8804bbaf4d266c3a Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 37dd2562ec830d547a1524bb306be313ac3f2556 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 44427702614d7b86b064ba06a390f5eb2f85dbf6 fix: Add support for more ARM processors detection (#608) by Andre Nguyen <andre-nguyen@users.noreply.github.com>
- 159bf2bf6d1cc8087e02468d071e94d1177d1bae Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- a2e6adecc294dc4cd98cc285a9134ce58e0f2ad0 Use https links. (#586) by nlewycky <nicholas@mxc.ca>
- 564001ae506a17c51fa1223684a78f05f91d3d91 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- b3aaac8a37c467a1125c794196caa90d0957bdc3 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 63ee2f8877915a3565c29707dba8fe4d7822596a Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- a048203a881f11f4b7b8df5fb563aec85522f8db Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 1de0166368e2ae67347f92099d6dca3ab3a4a496 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- ad904b6cd3906ddf79878003d92b7bc08d7786ae Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 29235139149790f5afc430c11cec8f1eb1677607 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- bf86cfe165ef7d70dfe68f0b8fc0c018bc79a577 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 12bc53e0318d80569270a5b26ccbc62b52022b89 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 1e39f8626a4dadec1f56920b999dd4c3cfae333e Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 77f87009a34c745255bd84d8f2647040d831a2b3 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- d659fe54b35ab9b8e35c72e50a4b8814167d5a84 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- a4b757b5d42694306a9de853cee0a5fba9c7bbe9 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 0514227d2547793b23e209809276375e41c76617 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 7f4fe64af80fe3c84db8ea938276c3690573c45e Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 16d9fd58a51c6083234e2e9f8f50e49ed5ed02e4 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- bcaae6009c0833b73c6fa7bdd972921d8081a724 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 8ba96a8244bbe334d09542e92d566673a65c1f78 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 2103fd9acdf58279f739860bff3f8c9f4b845605 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 3df7b52a6ada51a72a23796b844549a7b282f1b8 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- fa8c75182fbfdeddb2485fc0d53baeda3f40b7a3 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 85092b4b648ca729c6263c4a302a41dfff28705e Fix Conan builds (#400) by Adrian Ostrowski <adr.ostrowski@gmail.com>
- e96ae2203b80d5ae2e0b7abe0c77b722b224b16d Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 20de2db748ca0471cfb61cb53e813dd12938c12b Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 846e5dbedac123d12455adcfe6f53c8b5dcbfeef Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 8207907f4f7fbaeeaa2b7340c76875e06fd345ba Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 078b89b3c046d230ef3ad39494e5852184eb528b Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 19b021cb3ff23048dfbe236a4e611925d8930831 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- ecc0033b54847f6c9ee37dbb0be8aa17e5b6d37b Always enable proper symbolize implementation on Windows ... by Loo Rong Jie <loorongjie@gmail.com>
- 2796d500aea5a31d26b8b24a33fab7a1c8fa2f32 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- e4c8d0eb8ef4acb5d7a4252b3b87feb391ef7e41 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- a15364ce4d88534ae2295127e5d8e32aefb6b446 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- ab3552a18964e7063c8324f45b3896a6a20b08a8 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- e9f9000c7c80993cb589d011616b7a8016e42f4a Fix ABSL_WAITER_MODE detection for mingw (#342) by Joe Sylve <Joe.Sylve@gmail.com>
- abea769b551f7a100f540967cb95debdb0080df8 Fix ABSL_HAVE_ALARM check on mingw (#341) by Joe Sylve <Joe.Sylve@gmail.com>
- 25597bdfc148e91e27678ec30efa52f4fc8c164f Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- aad33fefaa8f744d71ce747a53717b835bdf8e84 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 8fe7214fe2d7a45ecc4d85f6a524c6b1532426de Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- debac94cfb5a0fa75d1d97c399682bd1c72e3191 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 882b3501a31eb0e4ae4213afb91a0e43feda7d5f Fix spelling errors (#384) by Sungmann Cho <55860394+chosungmann@users.noreply.github.com>
- 502efe6d7841bff82b1aeef5500491fe9a48c635 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- ccdd1d57b6386ebc26fb0c7d99b604672437c124 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- ddf8e52a2918dd0ccec75d3e2426125fa3926724 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 6ec136281086b71da32b5fb068bd6e46b78a5c79 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- ac78ffc3bc0a8b295cab9a03817760fd460df2a1 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 5374c56e5196320681993869e3126b51edac2a43 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 97c1664b4bbab5f78fac2b151ab02656268fb34b Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 325fd7b042ff4ec34f7dd32e602cd81ad0e24b22 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 83c1d65c90a92aa49632b9ac5a793214bb0768bc Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- eb6b7bd23bc0815bfd784e1a74021ce166765280 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 9ddac555b7861dc178d0dbe758a1cfbed718784b Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 1948f6f967e34db9793cfa8b4bcbaf370d039fd8 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- a0d1e098c2f99694fa399b175a7ccf920762030e Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 2d2d7fbc283315b676159716376e739d3d23ed94 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 0302d1e5fa4fcdd1763b7d1bb3212943b1ae911d supppress unused variable warning for gcc (#372) by Martin <pizzard@users.noreply.github.com>
- 262d74ba81b1fc4d71f459555cde8ecb39786d68 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- f0afae0d49af3e15a7169e019634d7719143d94d Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 0e7afdcbd24c7e5b7cab4e0217d8886f1525b520 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 9a41ffdd3a0ccbcdd29c4e3886b28e06f2cd9c66 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 36910d3d7e9fccadd6603f232d0c4f54dcd47c7e [bazel] Add fixes for --incompatible_load_cc_rules_from_b... by Yannic <contact@yannic-bonenberger.com>
- aae8143cf9aa611f70d7ea9b95b8b8b383b2271a Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- d9aa92d7fb324314f9df487ac23d32a25650b742 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 321ab5303023c86cd15d9ddc5740fb4b4fde32e1 Export of internal Abseil changes by Abseil Team <absl-team@google.com>
- 4ef574064e75b86f115549e9eb4c7e806781b3ab Export of internal Abseil changes by Abseil Team <absl-team@google.com>
GitOrigin-RevId: 0033c9ea91a52ade7c6b725aa2ef3cbe15463421
Change-Id: I8a2b70063cb3ab40c6943a6db0fe40cae71ed8d7
Diffstat (limited to 'absl/hash')
-rw-r--r-- | absl/hash/BUILD.bazel | 5 | ||||
-rw-r--r-- | absl/hash/hash.h | 4 | ||||
-rw-r--r-- | absl/hash/hash_test.cc | 148 | ||||
-rw-r--r-- | absl/hash/hash_testing.h | 4 | ||||
-rw-r--r-- | absl/hash/internal/city.cc | 4 | ||||
-rw-r--r-- | absl/hash/internal/city.h | 7 | ||||
-rw-r--r-- | absl/hash/internal/city_test.cc | 4 | ||||
-rw-r--r-- | absl/hash/internal/hash.cc | 34 | ||||
-rw-r--r-- | absl/hash/internal/hash.h | 141 | ||||
-rw-r--r-- | absl/hash/internal/spy_hash_state.h | 17 |
10 files changed, 343 insertions, 25 deletions
diff --git a/absl/hash/BUILD.bazel b/absl/hash/BUILD.bazel index 8c2daf70..ffe8c294 100644 --- a/absl/hash/BUILD.bazel +++ b/absl/hash/BUILD.bazel @@ -1,5 +1,5 @@ # -# Copyright 2018 The Abseil Authors. +# Copyright 2019 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. @@ -14,6 +14,7 @@ # limitations under the License. # +load("@rules_cc//cc:defs.bzl", "cc_library", "cc_test") load( "//absl:copts/configure_copts.bzl", "ABSL_DEFAULT_COPTS", @@ -70,9 +71,9 @@ cc_test( deps = [ ":hash", ":hash_testing", + ":spy_hash_state", "//absl/base:core_headers", "//absl/container:flat_hash_set", - "//absl/hash:spy_hash_state", "//absl/meta:type_traits", "//absl/numeric:int128", "@com_google_googletest//:gtest_main", diff --git a/absl/hash/hash.h b/absl/hash/hash.h index d36f0960..23a65ea8 100644 --- a/absl/hash/hash.h +++ b/absl/hash/hash.h @@ -73,7 +73,7 @@ #include "absl/hash/internal/hash.h" namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN // ----------------------------------------------------------------------------- // `absl::Hash` @@ -318,7 +318,7 @@ class HashState : public hash_internal::HashStateBase<HashState> { void (*combine_contiguous_)(void*, const unsigned char*, size_t); }; -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_HASH_HASH_H_ diff --git a/absl/hash/hash_test.cc b/absl/hash/hash_test.cc index 2a4e2262..f02a537a 100644 --- a/absl/hash/hash_test.cc +++ b/absl/hash/hash_test.cc @@ -274,8 +274,8 @@ TEST(HashValueTest, Strings) { const std::string small = "foo"; const std::string dup = "foofoo"; - const std::string large = "large"; - const std::string huge = std::string(5000, 'a'); + 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(), @@ -300,6 +300,33 @@ TEST(HashValueTest, Strings) { SpyHash(absl::string_view("ABC"))); } +TEST(HashValueTest, WString) { + EXPECT_TRUE((is_hashable<std::wstring>::value)); + + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple( + std::wstring(), std::wstring(L"ABC"), std::wstring(L"ABC"), + std::wstring(L"Some other different string"), + std::wstring(L"Iñtërnâtiônàlizætiøn")))); +} + +TEST(HashValueTest, U16String) { + EXPECT_TRUE((is_hashable<std::u16string>::value)); + + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple( + std::u16string(), std::u16string(u"ABC"), std::u16string(u"ABC"), + std::u16string(u"Some other different string"), + std::u16string(u"Iñtërnâtiônàlizætiøn")))); +} + +TEST(HashValueTest, U32String) { + EXPECT_TRUE((is_hashable<std::u32string>::value)); + + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple( + std::u32string(), std::u32string(U"ABC"), std::u32string(U"ABC"), + std::u32string(U"Some other different string"), + std::u32string(U"Iñtërnâtiônàlizætiøn")))); +} + TEST(HashValueTest, StdArray) { EXPECT_TRUE((is_hashable<std::array<int, 3>>::value)); @@ -378,6 +405,116 @@ struct Private { } }; +// Test helper for combine_piecewise_buffer. It holds a string_view to the +// buffer-to-be-hashed. Its AbslHashValue specialization will split up its +// contents at the character offsets requested. +class PiecewiseHashTester { + public: + // Create a hash view of a buffer to be hashed contiguously. + explicit PiecewiseHashTester(absl::string_view buf) + : buf_(buf), piecewise_(false), split_locations_() {} + + // Create a hash view of a buffer to be hashed piecewise, with breaks at the + // given locations. + PiecewiseHashTester(absl::string_view buf, std::set<size_t> split_locations) + : buf_(buf), + piecewise_(true), + split_locations_(std::move(split_locations)) {} + + template <typename H> + friend H AbslHashValue(H h, const PiecewiseHashTester& p) { + if (!p.piecewise_) { + return H::combine_contiguous(std::move(h), p.buf_.data(), p.buf_.size()); + } + absl::hash_internal::PiecewiseCombiner combiner; + if (p.split_locations_.empty()) { + h = combiner.add_buffer(std::move(h), p.buf_.data(), p.buf_.size()); + return combiner.finalize(std::move(h)); + } + size_t begin = 0; + for (size_t next : p.split_locations_) { + absl::string_view chunk = p.buf_.substr(begin, next - begin); + h = combiner.add_buffer(std::move(h), chunk.data(), chunk.size()); + begin = next; + } + absl::string_view last_chunk = p.buf_.substr(begin); + if (!last_chunk.empty()) { + h = combiner.add_buffer(std::move(h), last_chunk.data(), + last_chunk.size()); + } + return combiner.finalize(std::move(h)); + } + + private: + absl::string_view buf_; + bool piecewise_; + std::set<size_t> split_locations_; +}; + +// Dummy object that hashes as two distinct contiguous buffers, "foo" followed +// by "bar" +struct DummyFooBar { + template <typename H> + friend H AbslHashValue(H h, const DummyFooBar&) { + const char* foo = "foo"; + const char* bar = "bar"; + h = H::combine_contiguous(std::move(h), foo, 3); + h = H::combine_contiguous(std::move(h), bar, 3); + return h; + } +}; + +TEST(HashValueTest, CombinePiecewiseBuffer) { + absl::Hash<PiecewiseHashTester> hash; + + // Check that hashing an empty buffer through the piecewise API works. + EXPECT_EQ(hash(PiecewiseHashTester("")), hash(PiecewiseHashTester("", {}))); + + // Similarly, small buffers should give consistent results + EXPECT_EQ(hash(PiecewiseHashTester("foobar")), + hash(PiecewiseHashTester("foobar", {}))); + EXPECT_EQ(hash(PiecewiseHashTester("foobar")), + hash(PiecewiseHashTester("foobar", {3}))); + + // But hashing "foobar" in pieces gives a different answer than hashing "foo" + // contiguously, then "bar" contiguously. + EXPECT_NE(hash(PiecewiseHashTester("foobar", {3})), + absl::Hash<DummyFooBar>()(DummyFooBar{})); + + // Test hashing a large buffer incrementally, broken up in several different + // ways. Arrange for breaks on and near the stride boundaries to look for + // off-by-one errors in the implementation. + // + // This test is run on a buffer that is a multiple of the stride size, and one + // that isn't. + for (size_t big_buffer_size : {1024 * 2 + 512, 1024 * 3}) { + SCOPED_TRACE(big_buffer_size); + std::string big_buffer; + for (int i = 0; i < big_buffer_size; ++i) { + // Arbitrary std::string + big_buffer.push_back(32 + (i * (i / 3)) % 64); + } + auto big_buffer_hash = hash(PiecewiseHashTester(big_buffer)); + + const int possible_breaks = 9; + size_t breaks[possible_breaks] = {1, 512, 1023, 1024, 1025, + 1536, 2047, 2048, 2049}; + for (unsigned test_mask = 0; test_mask < (1u << possible_breaks); + ++test_mask) { + SCOPED_TRACE(test_mask); + std::set<size_t> break_locations; + for (int j = 0; j < possible_breaks; ++j) { + if (test_mask & (1u << j)) { + break_locations.insert(breaks[j]); + } + } + EXPECT_EQ( + hash(PiecewiseHashTester(big_buffer, std::move(break_locations))), + big_buffer_hash); + } + } +} + TEST(HashValueTest, PrivateSanity) { // Sanity check that Private is working as the tests below expect it to work. EXPECT_TRUE(is_hashable<Private>::value); @@ -458,7 +595,10 @@ TEST(IsHashableTest, PoisonHash) { EXPECT_FALSE(absl::is_copy_assignable<absl::Hash<X>>::value); EXPECT_FALSE(absl::is_move_assignable<absl::Hash<X>>::value); EXPECT_FALSE(IsHashCallable<X>::value); +#if !defined(__GNUC__) || __GNUC__ < 9 + // This doesn't compile on GCC 9. EXPECT_FALSE(IsAggregateInitializable<absl::Hash<X>>::value); +#endif } #endif // ABSL_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_ @@ -544,7 +684,7 @@ H AbslHashValue(H state, CustomHashType<Tags...> t) { } // namespace namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace hash_internal { template <InvokeTag... Tags> struct is_uniquely_represented< @@ -552,7 +692,7 @@ struct is_uniquely_represented< typename EnableIfContained<InvokeTag::kUniquelyRepresented, Tags...>::type> : std::true_type {}; } // namespace hash_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #if ABSL_HASH_INTERNAL_SUPPORT_LEGACY_HASH_ diff --git a/absl/hash/hash_testing.h b/absl/hash/hash_testing.h index 6e39028f..1e1c5741 100644 --- a/absl/hash/hash_testing.h +++ b/absl/hash/hash_testing.h @@ -28,7 +28,7 @@ #include "absl/types/variant.h" namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN // Run the absl::Hash algorithm over all the elements passed in and verify that // their hash expansion is congruent with their `==` operator. @@ -372,7 +372,7 @@ VerifyTypeImplementsAbslHashCorrectly(std::initializer_list<T> values, equals); } -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_HASH_HASH_TESTING_H_ diff --git a/absl/hash/internal/city.cc b/absl/hash/internal/city.cc index c7ad1591..e122c184 100644 --- a/absl/hash/internal/city.cc +++ b/absl/hash/internal/city.cc @@ -30,7 +30,7 @@ #include "absl/base/optimization.h" namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace hash_internal { #ifdef ABSL_IS_BIG_ENDIAN @@ -342,5 +342,5 @@ uint64_t CityHash64WithSeeds(const char *s, size_t len, uint64_t seed0, } } // namespace hash_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl diff --git a/absl/hash/internal/city.h b/absl/hash/internal/city.h index 7586ba08..161c7748 100644 --- a/absl/hash/internal/city.h +++ b/absl/hash/internal/city.h @@ -47,10 +47,13 @@ #include <stdint.h> #include <stdlib.h> // for size_t. + #include <utility> +#include "absl/base/config.h" + namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace hash_internal { typedef std::pair<uint64_t, uint64_t> uint128; @@ -87,7 +90,7 @@ inline uint64_t Hash128to64(const uint128 &x) { } } // namespace hash_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_HASH_INTERNAL_CITY_H_ diff --git a/absl/hash/internal/city_test.cc b/absl/hash/internal/city_test.cc index 1b9373c2..251d381d 100644 --- a/absl/hash/internal/city_test.cc +++ b/absl/hash/internal/city_test.cc @@ -20,7 +20,7 @@ #include "gtest/gtest.h" namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace hash_internal { static const uint64_t k0 = 0xc3a5c85c97cb3127ULL; @@ -591,5 +591,5 @@ TEST(CityHashTest, Unchanging) { } } // namespace hash_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl diff --git a/absl/hash/internal/hash.cc b/absl/hash/internal/hash.cc index 087b389b..b44ecb3a 100644 --- a/absl/hash/internal/hash.cc +++ b/absl/hash/internal/hash.cc @@ -15,11 +15,41 @@ #include "absl/hash/internal/hash.h" namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace hash_internal { +uint64_t CityHashState::CombineLargeContiguousImpl32(uint64_t state, + const unsigned char* first, + size_t len) { + while (len >= PiecewiseChunkSize()) { + state = + Mix(state, absl::hash_internal::CityHash32(reinterpret_cast<const char*>(first), + PiecewiseChunkSize())); + len -= PiecewiseChunkSize(); + first += PiecewiseChunkSize(); + } + // Handle the remainder. + return CombineContiguousImpl(state, first, len, + std::integral_constant<int, 4>{}); +} + +uint64_t CityHashState::CombineLargeContiguousImpl64(uint64_t state, + const unsigned char* first, + size_t len) { + while (len >= PiecewiseChunkSize()) { + state = + Mix(state, absl::hash_internal::CityHash64(reinterpret_cast<const char*>(first), + PiecewiseChunkSize())); + len -= PiecewiseChunkSize(); + first += PiecewiseChunkSize(); + } + // Handle the remainder. + return CombineContiguousImpl(state, first, len, + std::integral_constant<int, 8>{}); +} + ABSL_CONST_INIT const void* const CityHashState::kSeed = &kSeed; } // namespace hash_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl diff --git a/absl/hash/internal/hash.h b/absl/hash/internal/hash.h index 81f1edf8..ae7a60cd 100644 --- a/absl/hash/internal/hash.h +++ b/absl/hash/internal/hash.h @@ -50,9 +50,15 @@ #include "absl/hash/internal/city.h" namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace hash_internal { +class PiecewiseCombiner; + +// Internal detail: Large buffers are hashed in smaller chunks. This function +// returns the size of these chunks. +constexpr size_t PiecewiseChunkSize() { return 1024; } + // HashStateBase // // A hash state object represents an intermediate state in the computation @@ -69,7 +75,7 @@ namespace hash_internal { // // `static H combine_contiguous(H state, const unsigned char*, size_t)`. // -// `HashStateBase` will provide a complete implementations for a hash state +// `HashStateBase` will provide a complete implementation for a hash state // object in terms of this method. // // Example: @@ -118,6 +124,9 @@ class HashStateBase { // for-loop instead. template <typename T> static H combine_contiguous(H state, const T* data, size_t size); + + private: + friend class PiecewiseCombiner; }; // is_uniquely_represented @@ -188,6 +197,61 @@ H hash_bytes(H hash_state, const T& value) { return H::combine_contiguous(std::move(hash_state), start, sizeof(value)); } +// PiecewiseCombiner +// +// PiecewiseCombiner is an internal-only helper class for hashing a piecewise +// buffer of `char` or `unsigned char` as though it were contiguous. This class +// provides two methods: +// +// H add_buffer(state, data, size) +// H finalize(state) +// +// `add_buffer` can be called zero or more times, followed by a single call to +// `finalize`. This will produce the same hash expansion as concatenating each +// buffer piece into a single contiguous buffer, and passing this to +// `H::combine_contiguous`. +// +// Example usage: +// PiecewiseCombiner combiner; +// for (const auto& piece : pieces) { +// state = combiner.add_buffer(std::move(state), piece.data, piece.size); +// } +// return combiner.finalize(std::move(state)); +class PiecewiseCombiner { + public: + PiecewiseCombiner() : position_(0) {} + PiecewiseCombiner(const PiecewiseCombiner&) = delete; + PiecewiseCombiner& operator=(const PiecewiseCombiner&) = delete; + + // PiecewiseCombiner::add_buffer() + // + // Appends the given range of bytes to the sequence to be hashed, which may + // modify the provided hash state. + template <typename H> + H add_buffer(H state, const unsigned char* data, size_t size); + template <typename H> + H add_buffer(H state, const char* data, size_t size) { + return add_buffer(std::move(state), + reinterpret_cast<const unsigned char*>(data), size); + } + + // PiecewiseCombiner::finalize() + // + // Finishes combining the hash sequence, which may may modify the provided + // hash state. + // + // Once finalize() is called, add_buffer() may no longer be called. The + // resulting hash state will be the same as if the pieces passed to + // add_buffer() were concatenated into a single flat buffer, and then provided + // to H::combine_contiguous(). + template <typename H> + H finalize(H state); + + private: + unsigned char buf_[PiecewiseChunkSize()]; + size_t position_; +}; + // ----------------------------------------------------------------------------- // AbslHashValue for Basic Types // ----------------------------------------------------------------------------- @@ -364,6 +428,19 @@ H AbslHashValue(H hash_state, absl::string_view str) { str.size()); } +// Support std::wstring, std::u16string and std::u32string. +template <typename Char, typename Alloc, typename H, + typename = absl::enable_if_t<std::is_same<Char, wchar_t>::value || + std::is_same<Char, char16_t>::value || + std::is_same<Char, char32_t>::value>> +H AbslHashValue( + H hash_state, + const std::basic_string<Char, std::char_traits<Char>, Alloc>& str) { + return H::combine( + H::combine_contiguous(std::move(hash_state), str.data(), str.size()), + str.size()); +} + // ----------------------------------------------------------------------------- // AbslHashValue for Sequence Containers // ----------------------------------------------------------------------------- @@ -631,7 +708,8 @@ struct is_hashable : std::integral_constant<bool, HashSelect::template Apply<T>::value> {}; // CityHashState -class CityHashState : public HashStateBase<CityHashState> { +class ABSL_DLL CityHashState + : public HashStateBase<CityHashState> { // absl::uint128 is not an alias or a thin wrapper around the intrinsic. // We use the intrinsic when available to improve performance. #ifdef ABSL_HAVE_INTRINSIC_INT128 @@ -710,6 +788,16 @@ class CityHashState : public HashStateBase<CityHashState> { std::integral_constant<int, 8> /* sizeof_size_t*/); + // Slow dispatch path for calls to CombineContiguousImpl with a size argument + // larger than PiecewiseChunkSize(). Has the same effect as calling + // CombineContiguousImpl() repeatedly with the chunk stride size. + static uint64_t CombineLargeContiguousImpl32(uint64_t state, + const unsigned char* first, + size_t len); + static uint64_t CombineLargeContiguousImpl64(uint64_t state, + const unsigned char* first, + size_t len); + // Reads 9 to 16 bytes from p. // The first 8 bytes are in .first, the rest (zero padded) bytes are in // .second. @@ -777,6 +865,9 @@ inline uint64_t CityHashState::CombineContiguousImpl( // multiplicative hash. uint64_t v; if (len > 8) { + if (ABSL_PREDICT_FALSE(len > PiecewiseChunkSize())) { + return CombineLargeContiguousImpl32(state, first, len); + } v = absl::hash_internal::CityHash32(reinterpret_cast<const char*>(first), len); } else if (len >= 4) { v = Read4To8(first, len); @@ -797,6 +888,9 @@ inline uint64_t CityHashState::CombineContiguousImpl( // multiplicative hash. uint64_t v; if (len > 16) { + if (ABSL_PREDICT_FALSE(len > PiecewiseChunkSize())) { + return CombineLargeContiguousImpl64(state, first, len); + } v = absl::hash_internal::CityHash64(reinterpret_cast<const char*>(first), len); } else if (len > 8) { auto p = Read9To16(first, len); @@ -813,7 +907,6 @@ inline uint64_t CityHashState::CombineContiguousImpl( return Mix(state, v); } - struct AggregateBarrier {}; // HashImpl @@ -850,8 +943,46 @@ template <typename T> H HashStateBase<H>::combine_contiguous(H state, const T* data, size_t size) { return hash_internal::hash_range_or_bytes(std::move(state), data, size); } + +// HashStateBase::PiecewiseCombiner::add_buffer() +template <typename H> +H PiecewiseCombiner::add_buffer(H state, const unsigned char* data, + size_t size) { + if (position_ + size < PiecewiseChunkSize()) { + // This partial chunk does not fill our existing buffer + memcpy(buf_ + position_, data, size); + position_ += size; + return state; + } + + // Complete the buffer and hash it + const size_t bytes_needed = PiecewiseChunkSize() - position_; + memcpy(buf_ + position_, data, bytes_needed); + state = H::combine_contiguous(std::move(state), buf_, PiecewiseChunkSize()); + data += bytes_needed; + size -= bytes_needed; + + // Hash whatever chunks we can without copying + while (size >= PiecewiseChunkSize()) { + state = H::combine_contiguous(std::move(state), data, PiecewiseChunkSize()); + data += PiecewiseChunkSize(); + size -= PiecewiseChunkSize(); + } + // Fill the buffer with the remainder + memcpy(buf_, data, size); + position_ = size; + return state; +} + +// HashStateBase::PiecewiseCombiner::finalize() +template <typename H> +H PiecewiseCombiner::finalize(H state) { + // Hash the remainder left in the buffer, which may be empty + return H::combine_contiguous(std::move(state), buf_, position_); +} + } // namespace hash_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_HASH_INTERNAL_HASH_H_ diff --git a/absl/hash/internal/spy_hash_state.h b/absl/hash/internal/spy_hash_state.h index 57cd70b2..c0831208 100644 --- a/absl/hash/internal/spy_hash_state.h +++ b/absl/hash/internal/spy_hash_state.h @@ -25,7 +25,7 @@ #include "absl/strings/str_join.h" namespace absl { -inline namespace lts_2019_08_08 { +ABSL_NAMESPACE_BEGIN namespace hash_internal { // SpyHashState is an implementation of the HashState API that simply @@ -147,6 +147,19 @@ class SpyHashStateImpl : public HashStateBase<SpyHashStateImpl<T>> { static SpyHashStateImpl combine_contiguous(SpyHashStateImpl hash_state, const unsigned char* begin, size_t size) { + const size_t large_chunk_stride = PiecewiseChunkSize(); + if (size > large_chunk_stride) { + // Combining a large contiguous buffer must have the same effect as + // doing it piecewise by the stride length, followed by the (possibly + // empty) remainder. + while (size >= large_chunk_stride) { + hash_state = SpyHashStateImpl::combine_contiguous( + std::move(hash_state), begin, large_chunk_stride); + begin += large_chunk_stride; + size -= large_chunk_stride; + } + } + hash_state.hash_representation_.emplace_back( reinterpret_cast<const char*>(begin), size); return hash_state; @@ -212,7 +225,7 @@ void AbslHashValue(SpyHashStateImpl<T>, const U&); using SpyHashState = SpyHashStateImpl<void>; } // namespace hash_internal -} // inline namespace lts_2019_08_08 +ABSL_NAMESPACE_END } // namespace absl #endif // ABSL_HASH_INTERNAL_SPY_HASH_STATE_H_ |