summaryrefslogtreecommitdiff
path: root/absl/hash
diff options
context:
space:
mode:
Diffstat (limited to 'absl/hash')
-rw-r--r--absl/hash/BUILD.bazel3
-rw-r--r--absl/hash/CMakeLists.txt1
-rw-r--r--absl/hash/hash.h11
-rw-r--r--absl/hash/hash_test.cc75
-rw-r--r--absl/hash/internal/hash.h138
5 files changed, 139 insertions, 89 deletions
diff --git a/absl/hash/BUILD.bazel b/absl/hash/BUILD.bazel
index ffe8c294..5b1e2d01 100644
--- a/absl/hash/BUILD.bazel
+++ b/absl/hash/BUILD.bazel
@@ -24,7 +24,7 @@ load(
package(default_visibility = ["//visibility:public"])
-licenses(["notice"]) # Apache 2.0
+licenses(["notice"])
cc_library(
name = "hash",
@@ -76,6 +76,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 febc551f..61365e9b 100644
--- a/absl/hash/CMakeLists.txt
+++ b/absl/hash/CMakeLists.txt
@@ -62,6 +62,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 23a65ea8..5de132ca 100644
--- a/absl/hash/hash.h
+++ b/absl/hash/hash.h
@@ -37,8 +37,11 @@
// types. Hashing of that combined state is separately done by `absl::Hash`.
//
// One should assume that a hash algorithm is chosen randomly at the start of
-// each process. E.g., absl::Hash<int>()(9) in one process and
-// absl::Hash<int>()(9) in another process are likely to differ.
+// each process. E.g., `absl::Hash<int>{}(9)` in one process and
+// `absl::Hash<int>{}(9)` in another process are likely to differ.
+//
+// `absl::Hash` is intended to strongly mix input bits with a target of passing
+// an [Avalanche Test](https://en.wikipedia.org/wiki/Avalanche_effect).
//
// Example:
//
@@ -85,7 +88,6 @@ ABSL_NAMESPACE_BEGIN
// * T is an arithmetic or pointer type
// * T defines an overload for `AbslHashValue(H, const T&)` for an arbitrary
// hash state `H`.
-// - T defines a specialization of `HASH_NAMESPACE::hash<T>`
// - T defines a specialization of `std::hash<T>`
//
// `absl::Hash` intrinsically supports the following types:
@@ -98,6 +100,7 @@ ABSL_NAMESPACE_BEGIN
// * std::tuple<Ts...>, 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)
@@ -124,8 +127,6 @@ ABSL_NAMESPACE_BEGIN
// * Natively supported types out of the box (see above)
// * Types for which an `AbslHashValue()` overload is provided (such as
// user-defined types). See "Adding Type Support to `absl::Hash`" below.
-// * Types which define a `HASH_NAMESPACE::hash<T>` specialization (aka
-// `__gnu_cxx::hash<T>` for gcc/Clang or `stdext::hash<T>` for MSVC)
// * Types which define a `std::hash<T>` specialization
//
// The fallback to legacy hash functions exists mainly for backwards
diff --git a/absl/hash/hash_test.cc b/absl/hash/hash_test.cc
index f02a537a..39ba24a8 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<absl::string_view> parts = {sv.substr(0, halfway),
+ sv.substr(halfway)};
+ return absl::MakeFragmentedCord(parts);
+}
+
TEST(HashValueTest, Strings) {
EXPECT_TRUE((is_hashable<std::string>::value));
@@ -277,25 +294,29 @@ 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)))));
-
- // Make sure that hashing a `const char*` does not use its std::string-value.
+ 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 string-value.
EXPECT_NE(SpyHash(static_cast<const char*>("ABC")),
SpyHash(absl::string_view("ABC")));
}
@@ -386,7 +407,7 @@ using IntSequenceTypes =
INSTANTIATE_TYPED_TEST_CASE_P(My, HashValueSequenceTest, IntSequenceTypes);
// Private type that only supports AbslHashValue to make sure our chosen hash
-// implentation is recursive within absl::Hash.
+// implementation is recursive within absl::Hash.
// It uses std::abs() on the value to provide different bitwise representations
// of the same logical value.
struct Private {
@@ -491,7 +512,7 @@ TEST(HashValueTest, CombinePiecewiseBuffer) {
SCOPED_TRACE(big_buffer_size);
std::string big_buffer;
for (int i = 0; i < big_buffer_size; ++i) {
- // Arbitrary std::string
+ // Arbitrary string
big_buffer.push_back(32 + (i * (i / 3)) % 64);
}
auto big_buffer_hash = hash(PiecewiseHashTester(big_buffer));
@@ -560,6 +581,24 @@ TEST(HashValueTest, Maps) {
MM{{1, "foo"}, {1, "foo"}, {43, "bar"}}, MM{{1, "foo"}, {43, "baz"}})));
}
+TEST(HashValueTest, ReferenceWrapper) {
+ EXPECT_TRUE(is_hashable<std::reference_wrapper<Private>>::value);
+
+ Private p1{1}, p10{10};
+ EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple(
+ p1, p10, std::ref(p1), std::ref(p10), std::cref(p1), std::cref(p10))));
+
+ EXPECT_TRUE(is_hashable<std::reference_wrapper<int>>::value);
+ int one = 1, ten = 10;
+ EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple(
+ one, ten, std::ref(one), std::ref(ten), std::cref(one), std::cref(ten))));
+
+ EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(
+ std::make_tuple(std::tuple<std::reference_wrapper<int>>(std::ref(one)),
+ std::tuple<std::reference_wrapper<int>>(std::ref(ten)),
+ std::tuple<int>(one), std::tuple<int>(ten))));
+}
+
template <typename T, typename = void>
struct IsHashCallable : std::false_type {};
diff --git a/absl/hash/internal/hash.h b/absl/hash/internal/hash.h
index ae7a60cd..9e608f7c 100644
--- a/absl/hash/internal/hash.h
+++ b/absl/hash/internal/hash.h
@@ -53,12 +53,65 @@ namespace absl {
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; }
+// 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_;
+};
+
// HashStateBase
//
// A hash state object represents an intermediate state in the computation
@@ -125,8 +178,7 @@ class HashStateBase {
template <typename T>
static H combine_contiguous(H state, const T* data, size_t size);
- private:
- friend class PiecewiseCombiner;
+ using AbslInternalPiecewiseCombiner = PiecewiseCombiner;
};
// is_uniquely_represented
@@ -197,61 +249,6 @@ 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
// -----------------------------------------------------------------------------
@@ -413,6 +410,7 @@ H AbslHashValue(H hash_state, const std::shared_ptr<T>& 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<char, std::char_traits<char>, A> for
// any allocator A)
// - `absl::string_view` and `std::string_view`
@@ -553,6 +551,13 @@ typename std::enable_if<is_hashable<Key>::value, H>::type AbslHashValue(
// AbslHashValue for Wrapper Types
// -----------------------------------------------------------------------------
+// AbslHashValue for hashing std::reference_wrapper
+template <typename H, typename T>
+typename std::enable_if<is_hashable<T>::value, H>::type AbslHashValue(
+ H hash_state, std::reference_wrapper<T> opt) {
+ return H::combine(std::move(hash_state), opt.get());
+}
+
// AbslHashValue for hashing absl::optional
template <typename H, typename T>
typename std::enable_if<is_hashable<T>::value, H>::type AbslHashValue(
@@ -955,12 +960,15 @@ H PiecewiseCombiner::add_buffer(H state, const unsigned char* data,
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;
+ // If the buffer is partially filled we need to complete the buffer
+ // and hash it.
+ if (position_ != 0) {
+ 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()) {
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-18 04:53:52 +0000