summaryrefslogtreecommitdiff
path: root/absl/hash
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2021-05-12 17:01:06 -0700
committerGravatar vslashg <gfalcon@google.com>2021-05-12 20:28:41 -0400
commitce42de10fbea616379826e91c7c23c16bffe6e61 (patch)
tree84e546f054980b875f6be1a6eb3a9256a5b88ba5 /absl/hash
parent7ba826e50dff1878e6ecc6b9af44097c040c8968 (diff)
Export of internal Abseil changes
-- 9fc37c11b9e46287acef00ee06ed9adcba54dd13 by Greg Falcon <gfalcon@google.com>: Rename absl::hash_internal::HashState to absl::hash_internal::MixingHashState. Before this change, we had two classes named HashState: absl::HashState, the public API used for type erasure, and absl::hash_internal::HashState, the internal concrete implementation ordinarily used. The internal class used to be named `CityHashState`, but we renamed it to `HashState` it when we changed underlying hash implementation to wyhash. This inadvertent naming conflict made the code much harder to read, and this change intends to undo that. PiperOrigin-RevId: 373481959 -- 4aec55ffddebd085c239352a2e20721091f719a1 by Greg Falcon <gfalcon@google.com>: Introduce absl::HashOf(), a convenience wrapper around absl::Hash that calculates hashes from the values of its arguments. PiperOrigin-RevId: 373461406 -- 86b5fd8db50bbc8bd0aa9258523527381fe0445d by Abseil Team <absl-team@google.com>: Improve speed of BlockingCounter by making its most common path lock free. With the new implementation, the fast path of BlockingCounter::DecrementCount() is only a fetch_sub operation. This is most times much more efficient than the previous implementation (full mutex lock/unlock). As a matter of fact, in most actual usecases in practice, the waiter thread is already waiting on the Wait() call when DecrementCount() is called, which makes Mutex::Unlock() take the slow path as there's a waiter thread that it might need to wake up. PiperOrigin-RevId: 373394164 -- 65c876be5eac0cd32583ff8535ede4109d39cf3f by Martijn Vels <mvels@google.com>: Move the 'sample copied cord' logic into MaybeTrackCord(), This changes move the logic for selecting if a cord should remain being sampled from Cord to CordzInfo::MaybeTrackCord, and updates the documentation for the latter method. PiperOrigin-RevId: 373363168 -- e84410bd0aada293a81dfb82656c952e209e21fb by Martijn Vels <mvels@google.com>: Add check for the first call to cordz_should_profile() for each thread. This prevents the first cord of a newly created thread to be always sampled, which is a 'bad' kind of determinism for sampling. PiperOrigin-RevId: 373229768 -- bf09c589dc099ac8f4af780bf7e609c53c27574c by Samuel Benzaquen <sbenza@google.com>: Refactor the Flags structure into an enum. This gives us more control over the representation and allows for easier merging during parsing. PiperOrigin-RevId: 373163038 -- b947b0c51083b7b6508284b5d31819596c91729e by Derek Mauro <dmauro@google.com>: Fixes warnings about shadowed variables Fixes #956 PiperOrigin-RevId: 373158133 GitOrigin-RevId: 9fc37c11b9e46287acef00ee06ed9adcba54dd13 Change-Id: I91f35699f9bf439d1a870c6493946a310afe088c
Diffstat (limited to 'absl/hash')
-rw-r--r--absl/hash/hash.h22
-rw-r--r--absl/hash/hash_test.cc22
-rw-r--r--absl/hash/internal/hash.cc14
-rw-r--r--absl/hash/internal/hash.h46
4 files changed, 74 insertions, 30 deletions
diff --git a/absl/hash/hash.h b/absl/hash/hash.h
index 5de132ca..69c44fde 100644
--- a/absl/hash/hash.h
+++ b/absl/hash/hash.h
@@ -73,6 +73,8 @@
#ifndef ABSL_HASH_HASH_H_
#define ABSL_HASH_HASH_H_
+#include <tuple>
+
#include "absl/hash/internal/hash.h"
namespace absl {
@@ -214,6 +216,26 @@ ABSL_NAMESPACE_BEGIN
template <typename T>
using Hash = absl::hash_internal::Hash<T>;
+// HashOf
+//
+// absl::HashOf() is a helper that generates a hash from the values of its
+// arguments. It dispatches to absl::Hash directly, as follows:
+// * HashOf(t) == absl::Hash<T>{}(t)
+// * HashOf(a, b, c) == HashOf(std::make_tuple(a, b, c))
+//
+// HashOf(a1, a2, ...) == HashOf(b1, b2, ...) is guaranteed when
+// * The argument lists have pairwise identical C++ types
+// * a1 == b1 && a2 == b2 && ...
+//
+// The requirement that the arguments match in both type and value is critical.
+// It means that `a == b` does not necessarily imply `HashOf(a) == HashOf(b)` if
+// `a` and `b` have different types. For example, `HashOf(2) != HashOf(2.0)`.
+template <typename... Types>
+size_t HashOf(const Types&... values) {
+ auto tuple = std::tie(values...);
+ return absl::Hash<decltype(tuple)>{}(tuple);
+}
+
// HashState
//
// A type erased version of the hash state concept, for use in user-defined
diff --git a/absl/hash/hash_test.cc b/absl/hash/hash_test.cc
index 1d2e6cf0..02b7733d 100644
--- a/absl/hash/hash_test.cc
+++ b/absl/hash/hash_test.cc
@@ -973,4 +973,26 @@ TEST(HashTest, DoesNotUseImplicitConversionsToBool) {
absl::Hash<ValueWithBoolConversion>()(ValueWithBoolConversion{1}));
}
+TEST(HashOf, MatchesHashForSingleArgument) {
+ std::string s = "forty two";
+ int i = 42;
+ double d = 42.0;
+ std::tuple<int, int> t{4, 2};
+
+ EXPECT_EQ(absl::HashOf(s), absl::Hash<std::string>{}(s));
+ EXPECT_EQ(absl::HashOf(i), absl::Hash<int>{}(i));
+ EXPECT_EQ(absl::HashOf(d), absl::Hash<double>{}(d));
+ EXPECT_EQ(absl::HashOf(t), (absl::Hash<std::tuple<int, int>>{}(t)));
+}
+
+TEST(HashOf, MatchesHashOfTupleForMultipleArguments) {
+ std::string hello = "hello";
+ std::string world = "world";
+
+ EXPECT_EQ(absl::HashOf(), absl::HashOf(std::make_tuple()));
+ EXPECT_EQ(absl::HashOf(hello), absl::HashOf(std::make_tuple(hello)));
+ EXPECT_EQ(absl::HashOf(hello, world),
+ absl::HashOf(std::make_tuple(hello, world)));
+}
+
} // namespace
diff --git a/absl/hash/internal/hash.cc b/absl/hash/internal/hash.cc
index 1433eb9d..06f53a59 100644
--- a/absl/hash/internal/hash.cc
+++ b/absl/hash/internal/hash.cc
@@ -18,9 +18,8 @@ namespace absl {
ABSL_NAMESPACE_BEGIN
namespace hash_internal {
-uint64_t HashState::CombineLargeContiguousImpl32(uint64_t state,
- const unsigned char* first,
- size_t len) {
+uint64_t MixingHashState::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),
@@ -33,9 +32,8 @@ uint64_t HashState::CombineLargeContiguousImpl32(uint64_t state,
std::integral_constant<int, 4>{});
}
-uint64_t HashState::CombineLargeContiguousImpl64(uint64_t state,
- const unsigned char* first,
- size_t len) {
+uint64_t MixingHashState::CombineLargeContiguousImpl64(
+ uint64_t state, const unsigned char* first, size_t len) {
while (len >= PiecewiseChunkSize()) {
state = Mix(state, Hash64(first, PiecewiseChunkSize()));
len -= PiecewiseChunkSize();
@@ -46,7 +44,7 @@ uint64_t HashState::CombineLargeContiguousImpl64(uint64_t state,
std::integral_constant<int, 8>{});
}
-ABSL_CONST_INIT const void* const HashState::kSeed = &kSeed;
+ABSL_CONST_INIT const void* const MixingHashState::kSeed = &kSeed;
// The salt array used by Wyhash. This array is NOT the mechanism used to make
// absl::Hash non-deterministic between program invocations. See `Seed()` for
@@ -61,7 +59,7 @@ constexpr uint64_t kWyhashSalt[5] = {
uint64_t{0x452821E638D01377},
};
-uint64_t HashState::WyhashImpl(const unsigned char* data, size_t len) {
+uint64_t MixingHashState::WyhashImpl(const unsigned char* data, size_t len) {
return Wyhash(data, len, Seed(), kWyhashSalt);
}
diff --git a/absl/hash/internal/hash.h b/absl/hash/internal/hash.h
index 7fb0af0b..69dbbc6b 100644
--- a/absl/hash/internal/hash.h
+++ b/absl/hash/internal/hash.h
@@ -379,7 +379,7 @@ template <typename H, typename... Ts>
// This SFINAE gets MSVC confused under some conditions. Let's just disable it
// for now.
H
-#else // _MSC_VER
+#else // _MSC_VER
typename std::enable_if<absl::conjunction<is_hashable<Ts>...>::value, H>::type
#endif // _MSC_VER
AbslHashValue(H hash_state, const std::tuple<Ts...>& t) {
@@ -714,8 +714,8 @@ template <typename T>
struct is_hashable
: std::integral_constant<bool, HashSelect::template Apply<T>::value> {};
-// HashState
-class ABSL_DLL HashState : public HashStateBase<HashState> {
+// MixingHashState
+class ABSL_DLL MixingHashState : public HashStateBase<MixingHashState> {
// 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
@@ -734,22 +734,23 @@ class ABSL_DLL HashState : public HashStateBase<HashState> {
public:
// Move only
- HashState(HashState&&) = default;
- HashState& operator=(HashState&&) = default;
+ MixingHashState(MixingHashState&&) = default;
+ MixingHashState& operator=(MixingHashState&&) = default;
- // HashState::combine_contiguous()
+ // MixingHashState::combine_contiguous()
//
// Fundamental base case for hash recursion: mixes the given range of bytes
// into the hash state.
- static HashState combine_contiguous(HashState hash_state,
- const unsigned char* first, size_t size) {
- return HashState(
+ static MixingHashState combine_contiguous(MixingHashState hash_state,
+ const unsigned char* first,
+ size_t size) {
+ return MixingHashState(
CombineContiguousImpl(hash_state.state_, first, size,
std::integral_constant<int, sizeof(size_t)>{}));
}
- using HashState::HashStateBase::combine_contiguous;
+ using MixingHashState::HashStateBase::combine_contiguous;
- // HashState::hash()
+ // MixingHashState::hash()
//
// For performance reasons in non-opt mode, we specialize this for
// integral types.
@@ -761,24 +762,24 @@ class ABSL_DLL HashState : public HashStateBase<HashState> {
return static_cast<size_t>(Mix(Seed(), static_cast<uint64_t>(value)));
}
- // Overload of HashState::hash()
+ // Overload of MixingHashState::hash()
template <typename T, absl::enable_if_t<!IntegralFastPath<T>::value, int> = 0>
static size_t hash(const T& value) {
- return static_cast<size_t>(combine(HashState{}, value).state_);
+ return static_cast<size_t>(combine(MixingHashState{}, value).state_);
}
private:
// Invoked only once for a given argument; that plus the fact that this is
// move-only ensures that there is only one non-moved-from object.
- HashState() : state_(Seed()) {}
+ MixingHashState() : state_(Seed()) {}
// Workaround for MSVC bug.
// We make the type copyable to fix the calling convention, even though we
// never actually copy it. Keep it private to not affect the public API of the
// type.
- HashState(const HashState&) = default;
+ MixingHashState(const MixingHashState&) = default;
- explicit HashState(uint64_t state) : state_(state) {}
+ explicit MixingHashState(uint64_t state) : state_(state) {}
// Implementation of the base case for combine_contiguous where we actually
// mix the bytes into the state.
@@ -793,7 +794,6 @@ class ABSL_DLL HashState : public HashStateBase<HashState> {
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.
@@ -911,8 +911,8 @@ class ABSL_DLL HashState : public HashStateBase<HashState> {
uint64_t state_;
};
-// HashState::CombineContiguousImpl()
-inline uint64_t HashState::CombineContiguousImpl(
+// MixingHashState::CombineContiguousImpl()
+inline uint64_t MixingHashState::CombineContiguousImpl(
uint64_t state, const unsigned char* first, size_t len,
std::integral_constant<int, 4> /* sizeof_size_t */) {
// For large values we use CityHash, for small ones we just use a
@@ -934,8 +934,8 @@ inline uint64_t HashState::CombineContiguousImpl(
return Mix(state, v);
}
-// Overload of HashState::CombineContiguousImpl()
-inline uint64_t HashState::CombineContiguousImpl(
+// Overload of MixingHashState::CombineContiguousImpl()
+inline uint64_t MixingHashState::CombineContiguousImpl(
uint64_t state, const unsigned char* first, size_t len,
std::integral_constant<int, 8> /* sizeof_size_t */) {
// For large values we use Wyhash or CityHash depending on the platform, for
@@ -976,7 +976,9 @@ struct PoisonedHash : private AggregateBarrier {
template <typename T>
struct HashImpl {
- size_t operator()(const T& value) const { return HashState::hash(value); }
+ size_t operator()(const T& value) const {
+ return MixingHashState::hash(value);
+ }
};
template <typename T>