summaryrefslogtreecommitdiff
path: root/absl
diff options
context:
space:
mode:
Diffstat (limited to 'absl')
-rw-r--r--absl/container/BUILD.bazel2
-rw-r--r--absl/container/CMakeLists.txt2
-rw-r--r--absl/container/flat_hash_map_test.cc36
-rw-r--r--absl/container/internal/raw_hash_set.h49
-rw-r--r--absl/container/internal/raw_hash_set_test.cc34
5 files changed, 123 insertions, 0 deletions
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel
index 859163f8..2e32b4dd 100644
--- a/absl/container/BUILD.bazel
+++ b/absl/container/BUILD.bazel
@@ -265,11 +265,13 @@ cc_test(
deps = [
":flat_hash_map",
":hash_generator_testing",
+ ":hash_policy_testing",
":test_allocator",
":unordered_map_constructor_test",
":unordered_map_lookup_test",
":unordered_map_members_test",
":unordered_map_modifiers_test",
+ "//absl/base:config",
"//absl/log:check",
"//absl/meta:type_traits",
"//absl/types:any",
diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt
index b1f5f9d8..a1023def 100644
--- a/absl/container/CMakeLists.txt
+++ b/absl/container/CMakeLists.txt
@@ -306,8 +306,10 @@ absl_cc_test(
DEPS
absl::any
absl::check
+ absl::config
absl::flat_hash_map
absl::hash_generator_testing
+ absl::hash_policy_testing
absl::test_allocator
absl::type_traits
absl::unordered_map_constructor_test
diff --git a/absl/container/flat_hash_map_test.cc b/absl/container/flat_hash_map_test.cc
index 8ef1a62b..eaa86925 100644
--- a/absl/container/flat_hash_map_test.cc
+++ b/absl/container/flat_hash_map_test.cc
@@ -16,12 +16,16 @@
#include <cstddef>
#include <memory>
+#include <string>
#include <type_traits>
#include <utility>
#include <vector>
+#include "gmock/gmock.h"
#include "gtest/gtest.h"
+#include "absl/base/config.h"
#include "absl/container/internal/hash_generator_testing.h"
+#include "absl/container/internal/hash_policy_testing.h"
#include "absl/container/internal/test_allocator.h"
#include "absl/container/internal/unordered_map_constructor_test.h"
#include "absl/container/internal/unordered_map_lookup_test.h"
@@ -363,6 +367,38 @@ TEST(FlatHashMap, FlatHashMapPolicyDestroyReturnsTrue) {
std::allocator<char>>(nullptr, nullptr))()));
}
+struct InconsistentHashEqType {
+ InconsistentHashEqType(int v1, int v2) : v1(v1), v2(v2) {}
+ template <typename H>
+ friend H AbslHashValue(H h, InconsistentHashEqType t) {
+ return H::combine(std::move(h), t.v1);
+ }
+ bool operator==(InconsistentHashEqType t) const { return v2 == t.v2; }
+ int v1, v2;
+};
+
+TEST(Iterator, InconsistentHashEqFunctorsValidation) {
+ if (!IsAssertEnabled()) GTEST_SKIP() << "Assertions not enabled.";
+
+ absl::flat_hash_map<InconsistentHashEqType, int> m;
+ for (int i = 0; i < 10; ++i) m[{i, i}] = 1;
+ // We need to insert multiple times to guarantee that we get the assertion
+ // because it's possible for the hash to collide with the inserted element
+ // that has v2==0. In those cases, the new element won't be inserted.
+ auto insert_conflicting_elems = [&] {
+ for (int i = 100; i < 20000; ++i) {
+ EXPECT_EQ((m[{i, 0}]), 1);
+ }
+ };
+
+ const char* crash_message = "hash/eq functors are inconsistent.";
+#if defined(__arm__) || defined(__aarch64__)
+ // On ARM, the crash message is garbled so don't expect a specific message.
+ crash_message = "";
+#endif
+ EXPECT_DEATH_IF_SUPPORTED(insert_conflicting_elems(), crash_message);
+}
+
} // namespace
} // namespace container_internal
ABSL_NAMESPACE_END
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index 2ea07e40..f494fb1c 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -3317,11 +3317,13 @@ class raw_hash_set {
template <class K = key_type>
iterator find(const key_arg<K>& key,
size_t hash) ABSL_ATTRIBUTE_LIFETIME_BOUND {
+ AssertHashEqConsistent(key);
if (is_soo()) return find_soo(key);
return find_non_soo(key, hash);
}
template <class K = key_type>
iterator find(const key_arg<K>& key) ABSL_ATTRIBUTE_LIFETIME_BOUND {
+ AssertHashEqConsistent(key);
if (is_soo()) return find_soo(key);
prefetch_heap_block();
return find_non_soo(key, hash_ref()(key));
@@ -3822,11 +3824,58 @@ class raw_hash_set {
}
protected:
+ // Asserts that hash and equal functors provided by the user are consistent,
+ // meaning that `eq(k1, k2)` implies `hash(k1)==hash(k2)`.
+ template <class K>
+ void AssertHashEqConsistent(ABSL_ATTRIBUTE_UNUSED const K& key) {
+#ifndef NDEBUG
+ if (empty()) return;
+
+ const size_t hash_of_arg = hash_ref()(key);
+ const auto assert_consistent = [&](const ctrl_t*, slot_type* slot) {
+ const value_type& element = PolicyTraits::element(slot);
+ const bool is_key_equal =
+ PolicyTraits::apply(EqualElement<K>{key, eq_ref()}, element);
+ if (!is_key_equal) return;
+
+ const size_t hash_of_slot =
+ PolicyTraits::apply(HashElement{hash_ref()}, element);
+ const bool is_hash_equal = hash_of_arg == hash_of_slot;
+ if (!is_hash_equal) {
+ // In this case, we're going to crash. Do a couple of other checks for
+ // idempotence issues. Recalculating hash/eq here is also convenient for
+ // debugging with gdb/lldb.
+ const size_t once_more_hash_arg = hash_ref()(key);
+ assert(hash_of_arg == once_more_hash_arg && "hash is not idempotent.");
+ const size_t once_more_hash_slot =
+ PolicyTraits::apply(HashElement{hash_ref()}, element);
+ assert(hash_of_slot == once_more_hash_slot &&
+ "hash is not idempotent.");
+ const bool once_more_eq =
+ PolicyTraits::apply(EqualElement<K>{key, eq_ref()}, element);
+ assert(is_key_equal == once_more_eq && "equality is not idempotent.");
+ }
+ assert((!is_key_equal || is_hash_equal) &&
+ "eq(k1, k2) must imply that hash(k1) == hash(k2). "
+ "hash/eq functors are inconsistent.");
+ };
+
+ if (is_soo()) {
+ assert_consistent(/*unused*/ nullptr, soo_slot());
+ return;
+ }
+ // We only do validation for small tables so that it's constant time.
+ if (capacity() > 16) return;
+ IterateOverFullSlots(common(), slot_array(), assert_consistent);
+#endif
+ }
+
// Attempts to find `key` in the table; if it isn't found, returns an iterator
// where the value can be inserted into, with the control byte already set to
// `key`'s H2. Returns a bool indicating whether an insertion can take place.
template <class K>
std::pair<iterator, bool> find_or_prepare_insert(const K& key) {
+ AssertHashEqConsistent(key);
if (is_soo()) return find_or_prepare_insert_soo(key);
return find_or_prepare_insert_non_soo(key);
}
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc
index 10f793ef..195296a1 100644
--- a/absl/container/internal/raw_hash_set_test.cc
+++ b/absl/container/internal/raw_hash_set_test.cc
@@ -3293,6 +3293,40 @@ TEST(Table, ReserveToNonSoo) {
}
}
+struct InconsistentHashEqType {
+ InconsistentHashEqType(int v1, int v2) : v1(v1), v2(v2) {}
+ template <typename H>
+ friend H AbslHashValue(H h, InconsistentHashEqType t) {
+ return H::combine(std::move(h), t.v1);
+ }
+ bool operator==(InconsistentHashEqType t) const { return v2 == t.v2; }
+ int v1, v2;
+};
+
+TEST(Iterator, InconsistentHashEqFunctorsValidation) {
+ if (!IsAssertEnabled()) GTEST_SKIP() << "Assertions not enabled.";
+
+ ValueTable<InconsistentHashEqType> t;
+ for (int i = 0; i < 10; ++i) t.insert({i, i});
+ // We need to find/insert multiple times to guarantee that we get the
+ // assertion because it's possible for the hash to collide with the inserted
+ // element that has v2==0. In those cases, the new element won't be inserted.
+ auto find_conflicting_elems = [&] {
+ for (int i = 100; i < 20000; ++i) {
+ EXPECT_EQ(t.find({i, 0}), t.end());
+ }
+ };
+ EXPECT_DEATH_IF_SUPPORTED(find_conflicting_elems(),
+ "hash/eq functors are inconsistent.");
+ auto insert_conflicting_elems = [&] {
+ for (int i = 100; i < 20000; ++i) {
+ EXPECT_EQ(t.insert({i, 0}).second, false);
+ }
+ };
+ EXPECT_DEATH_IF_SUPPORTED(insert_conflicting_elems(),
+ "hash/eq functors are inconsistent.");
+}
+
REGISTER_TYPED_TEST_SUITE_P(
SooTest, Empty, Clear, ClearBug, Contains1, Contains2, ContainsEmpty,
CopyConstruct, CopyDifferentCapacities, CopyDifferentSizes,
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-25 11:14:48 +0000