summaryrefslogtreecommitdiff
path: root/absl/hash
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2019-02-19 14:29:09 -0800
committerGravatar Jon Cohen <cohenjon@google.com>2019-02-20 18:02:20 -0500
commit93d155bc4414f6c121bb1f19dba9fdb27c8943bc (patch)
tree47facabc0db6f4204fe5b7cdba5420276b00a1f0 /absl/hash
parent426eaa4aa44e4580418bee46c1bd13911151bfb1 (diff)
Export of internal Abseil changes.
-- 3d20ce6cd6541579abecaba169d4b8716d511272 by Jon Cohen <cohenjon@google.com>: Only use LSAN for clang version >= 3.5. This should fix https://github.com/abseil/abseil-cpp/issues/244 PiperOrigin-RevId: 234675129 -- e15bd4ec7a81aa95cc3d09fa1e0e81d58ae478fb by Conrad Parker <conradparker@google.com>: Fix errors in apply() sample code The following changes are made: * Make the example method public. * Give the two user functions different names to avoid confusion about whether apply() can select the correct overload of a function based on its tuple argument (it can't). * Pass tuple2 to the second example apply() invocation, instead of passing its contents individually. * Fix a s/tuple/tuple3/ typo in the third example apply() invocation. PiperOrigin-RevId: 234223407 -- de0ed71e21bc76ddf9fe715fdbaef74cd0df95c7 by Abseil Team <absl-team@google.com>: First test if a macro is defined to avoid -Wundef. ABSL clients may need to compile their code with the -Wundef warning flag. It will be helpful if ABSL header files can be compiled without the -Wundef warning. How to avoid the -Wundef warning: If a macro may be undefined, we need to first test whether the macro is defined before testing its value. We can't rely on the C preprocessor rule that an undefined macro has the value 0L. PiperOrigin-RevId: 234201123 -- fa484ad7dae0cac21140a96662809ecb0ec8eb5d by Abseil Team <absl-team@google.com>: Internal change. PiperOrigin-RevId: 234185697 -- d69b1baef681e27954b065375ecf9c2320463b2b by Samuel Benzaquen <sbenza@google.com>: Mix pointers more thoroughly. Some pointer alignments interact badly with the mixing constant. By mixing twice we reduce this problem. PiperOrigin-RevId: 234178401 -- 1041d0e474610f3a8fea0db90958857327d6da1c by Samuel Benzaquen <sbenza@google.com>: Record rehashes in the hashtablez struct. Only recording the probe length on insertion causes a huge overestimation of the total probe length at any given time. With natural growth, elements are inserted when the load factor is between (max load/2, max load). However, after a rehash the majority of elements are actually inserted when the load factor is less than max/2 and have a much lower average probe length. Also reset some values when the table is cleared. PiperOrigin-RevId: 234013580 -- 299205caf3c89c47339f7409bc831746602cea84 by Mark Barolak <mbar@google.com>: Fix a sample code snippet that assumes `absl::string_view::const_iterator` is `const char*`. This is generally true, however in C++17 builds, absl::string_view is an alias for std::string_view and on MSVC, the std::string_view::const_iterator is an object instead of just a pointer. PiperOrigin-RevId: 233844595 -- af6c6370cf51a1e6c1469c79dfb2a486a4009136 by Abseil Team <absl-team@google.com>: Internal change. PiperOrigin-RevId: 233773470 -- 6e59e4b8e2bb6101b448f0f32b0bea81fe399ccf by Abseil Team <absl-team@google.com>: fix typo in {Starts|Ends}WithIgnoreCase comment in match.h PiperOrigin-RevId: 233662951 GitOrigin-RevId: 3d20ce6cd6541579abecaba169d4b8716d511272 Change-Id: Ib9a29b1c38c6aedf5d9f3f7f00596e8d30e864dd
Diffstat (limited to 'absl/hash')
-rw-r--r--absl/hash/hash_test.cc30
-rw-r--r--absl/hash/internal/hash.h7
2 files changed, 36 insertions, 1 deletions
diff --git a/absl/hash/hash_test.cc b/absl/hash/hash_test.cc
index a5af93ad..2c9e46b7 100644
--- a/absl/hash/hash_test.cc
+++ b/absl/hash/hash_test.cc
@@ -135,6 +135,36 @@ TEST(HashValueTest, Pointer) {
std::make_tuple(&i, ptr, nullptr, ptr + 1, n)));
}
+TEST(HashValueTest, PointerAlignment) {
+ // We want to make sure that pointer alignment will not cause bits to be
+ // stuck.
+
+ constexpr size_t kTotalSize = 1 << 20;
+ std::unique_ptr<char[]> data(new char[kTotalSize]);
+ constexpr size_t kLog2NumValues = 5;
+ constexpr size_t kNumValues = 1 << kLog2NumValues;
+
+ for (size_t align = 1; align < kTotalSize / kNumValues;
+ align < 8 ? align += 1 : align < 1024 ? align += 8 : align += 32) {
+ SCOPED_TRACE(align);
+ ASSERT_LE(align * kNumValues, kTotalSize);
+
+ size_t bits_or = 0;
+ size_t bits_and = ~size_t{};
+
+ for (size_t i = 0; i < kNumValues; ++i) {
+ size_t hash = absl::Hash<void*>()(data.get() + i * align);
+ bits_or |= hash;
+ bits_and &= hash;
+ }
+
+ // Limit the scope to the bits we would be using for Swisstable.
+ constexpr size_t kMask = (1 << (kLog2NumValues + 7)) - 1;
+ size_t stuck_bits = (~bits_or | bits_and) & kMask;
+ EXPECT_EQ(stuck_bits, 0) << "0x" << std::hex << stuck_bits;
+ }
+}
+
// TODO(EricWF): MSVC 15 has a bug that causes it to incorrectly evaluate the
// SFINAE in internal/hash.h, causing this test to fail.
#if !defined(_MSC_VER)
diff --git a/absl/hash/internal/hash.h b/absl/hash/internal/hash.h
index ba6d7468..bd07677a 100644
--- a/absl/hash/internal/hash.h
+++ b/absl/hash/internal/hash.h
@@ -264,7 +264,12 @@ H AbslHashValue(H hash_state, long double value) {
// AbslHashValue() for hashing pointers
template <typename H, typename T>
H AbslHashValue(H hash_state, T* ptr) {
- return hash_internal::hash_bytes(std::move(hash_state), ptr);
+ auto v = reinterpret_cast<uintptr_t>(ptr);
+ // Due to alignment, pointers tend to have low bits as zero, and the next few
+ // bits follow a pattern since they are also multiples of some base value.
+ // Mixing the pointer twice helps prevent stuck low bits for certain alignment
+ // values.
+ return H::combine(std::move(hash_state), v, v);
}
// AbslHashValue() for hashing nullptr_t