Move out of line hash/eq consistency assertions in raw_hash_set. PiperOrigin-RevId: 999231519 Change-Id: Ide7922a86ad7cb5f6fbf3e55f76a5d75e85131ab
diff --git a/absl/container/internal/container_memory.h b/absl/container/internal/container_memory.h index 01fe8d0..c408131 100644 --- a/absl/container/internal/container_memory.h +++ b/absl/container/internal/container_memory.h
@@ -562,6 +562,11 @@ size_t operator()(size_t seed) const { return HashElement<Hash, kIsAbsl, kSeedShift>{hash, seed}(key); } + + // Static version of the above to pass to type erased functions. + static size_t GetHash(void* data, size_t seed) { + return (*static_cast<const HashKey*>(data))(seed); + } const Hash& hash; const Key& key; };
diff --git a/absl/container/internal/raw_hash_set.cc b/absl/container/internal/raw_hash_set.cc index f31db0e..3465a90 100644 --- a/absl/container/internal/raw_hash_set.cc +++ b/absl/container/internal/raw_hash_set.cc
@@ -980,6 +980,35 @@ Destruct<kSooEnabled>(c, policy, kStandardDeallocBackingArrayFn); } +void AssertHashEqConsistentImpl(CommonFields& common, const void* hash_fn, + HashSlotFn hash_slot, size_t slot_size, + bool soo_enabled, size_t hash, const void* key, + EqualToKeyFn equal) { + const size_t seed = common.seed().seed(); + + const auto assert_consistent = [&](const ctrl_t*, void* slot) { + const bool is_key_equal = equal(&common, key, slot); + if (!is_key_equal) return; + + [[maybe_unused]] const bool is_hash_equal = + hash == hash_slot(hash_fn, slot, seed); + assert((!is_key_equal || is_hash_equal) && + "eq(k1, k2) must imply that hash(k1) == hash(k2). " + "hash/eq functors are inconsistent."); + }; + + if (common.is_small()) { + assert_consistent( + /*unused*/ nullptr, + soo_enabled ? SingleSlotAddress</*kSooEnabled=*/true>(common) + : SingleSlotAddress</*kSooEnabled=*/false>(common)); + return; + } + // We only do validation for small tables so that it's constant time. + if (common.capacity() > 16) return; + IterateOverFullSlots(common, slot_size, assert_consistent); +} + namespace { // Iterates over full slots in old table, finds new positions for them and @@ -1046,12 +1075,12 @@ ABSL_ATTRIBUTE_COLD ABSL_ATTRIBUTE_NOINLINE void ReportSingleElementTableGrowthToInfozAndForceSample( CommonFields& common, const PolicyFunctions& __restrict policy, - absl::FunctionRef<size_t(size_t)> get_hash) { + void* hasher, HashForKeyFn get_hash) { HashtablezInfoHandle infoz = ForcedTrySample(policy.slot_size, policy.key_size, policy.value_size, policy.soo_capacity()); common.generate_new_seed(/*has_infoz=*/true); - ReportGrowthToInfozImpl(common, infoz, get_hash(common.seed().seed()), + ReportGrowthToInfozImpl(common, infoz, get_hash(hasher, common.seed().seed()), /*total_probe_length=*/0, /*distance_from_desired=*/0); } @@ -1068,10 +1097,10 @@ // avoid calling the hash function and seed extraction in the hot path. // `common` is first and `get_hash` is third to match argument order in callers. ABSL_ATTRIBUTE_COLD ABSL_ATTRIBUTE_NOINLINE void -ReportInsertMissToInfozAndComputeHash( - CommonFields& common, size_t probe_length, - absl::FunctionRef<size_t(size_t)> get_hash) { - common.infoz().RecordInsertMiss(get_hash(common.seed().seed()), probe_length); +ReportInsertMissToInfozAndComputeHash(CommonFields& common, size_t probe_length, + void* hasher, HashForKeyFn get_hash) { + common.infoz().RecordInsertMiss(get_hash(hasher, common.seed().seed()), + probe_length); } // Outlines cold infoz recording with computation of probe_length so callers can @@ -1748,7 +1777,7 @@ void* Grow1To3AndPrepareInsert(CommonFields& common, const PolicyFunctions& __restrict policy, - absl::FunctionRef<size_t(size_t)> get_hash) { + void* hasher, HashForKeyFn get_hash) { // TODO(b/413062340): Refactor to reuse more code with // GrowSooTableToNextCapacityAndPrepareInsert. ABSL_SWISSTABLE_ASSERT(common.capacity() == 1); @@ -1778,7 +1807,7 @@ // When we're sampled, we already have a seed. common.generate_new_seed(/*has_infoz=*/false); } - const size_t new_hash = get_hash(common.seed().seed()); + const size_t new_hash = get_hash(hasher, common.seed().seed()); h2_t new_h2 = H2(new_hash); size_t orig_hash = policy.hash_slot(policy.hash_fn(common), old_slots, common.seed().seed()); @@ -1886,7 +1915,7 @@ void* PrepareInsertSmallNonSoo(CommonFields& common, const PolicyFunctions& __restrict policy, - absl::FunctionRef<size_t(size_t)> get_hash) { + void* hasher, HashForKeyFn get_hash) { ABSL_SWISSTABLE_ASSERT(common.is_small()); ABSL_SWISSTABLE_ASSERT(!policy.soo_enabled); if (common.capacity() == 1) { @@ -1897,11 +1926,11 @@ // Call NOINLINE function to move infoz instructions out of line. if (common.has_infoz()) { ReportInsertMissToInfozAndComputeHash(common, /*probe_length=*/0, - get_hash); + hasher, get_hash); } return res; } else { - return Grow1To3AndPrepareInsert(common, policy, get_hash); + return Grow1To3AndPrepareInsert(common, policy, hasher, get_hash); } } @@ -1923,7 +1952,7 @@ PrepareInsertCommon(common); if (ABSL_PREDICT_FALSE(has_infoz)) { - ReportSingleElementTableGrowthToInfozAndForceSample(common, policy, + ReportSingleElementTableGrowthToInfozAndForceSample(common, policy, hasher, get_hash); } return new_slots; @@ -2037,14 +2066,14 @@ ABSL_ATTRIBUTE_NOINLINE void* GrowEmptySooTableToNextCapacityForceSamplingAndPrepareInsert( CommonFields& common, const PolicyFunctions& __restrict policy, - absl::FunctionRef<size_t(size_t)> get_hash) { + void* hasher, HashForKeyFn get_hash) { const size_t kNewCapacity = NextCapacity(SooCapacity()); ResizeEmptyNonAllocatedTableImpl(common, policy, kNewCapacity, /*blocked_element_count=*/0, /*force_infoz=*/true); PrepareInsertCommon(common); common.OverwriteEmptyAsFull(); - const size_t new_hash = get_hash(common.seed().seed()); + const size_t new_hash = get_hash(hasher, common.seed().seed()); // Compute before `SetCtrl*` to avoid reloading `control_`. void* res = SlotAddress(common.slot_array(kNewCapacity), SooSlotIndex(), policy.slot_size); @@ -2183,12 +2212,12 @@ template <size_t SooSlotMemcpySize, bool TransferUsesMemcpy> void* GrowSooTableToNextCapacityAndPrepareInsert( CommonFields& common, const PolicyFunctions& __restrict policy, - absl::FunctionRef<size_t(size_t)> get_hash, bool force_sampling) { + void* hasher, HashForKeyFn get_hash, bool force_sampling) { AssertSoo(common, policy); if (ABSL_PREDICT_FALSE(force_sampling)) { // The table is empty, it is only used for forced sampling of SOO tables. return GrowEmptySooTableToNextCapacityForceSamplingAndPrepareInsert( - common, policy, get_hash); + common, policy, hasher, get_hash); } ABSL_SWISSTABLE_ASSERT(common.size() == policy.soo_capacity()); static constexpr size_t kNewCapacity = NextCapacity(SooCapacity()); @@ -2211,7 +2240,7 @@ common.generate_new_seed(/*has_infoz=*/false); const h2_t soo_slot_h2 = H2(policy.hash_slot( policy.hash_fn(common), common.soo_data(), common.seed().seed())); - const size_t new_hash = get_hash(common.seed().seed()); + const size_t new_hash = get_hash(hasher, common.seed().seed()); const size_t offset = Resize1To3NewOffset(new_hash); InitializeThreeElementsControlBytes(soo_slot_h2, H2(new_hash), offset, @@ -2497,18 +2526,17 @@ // We need to instantiate ALL possible template combinations because we define // the function in the cc file. template void* GrowSooTableToNextCapacityAndPrepareInsert<0, false>( - CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>, - bool); + CommonFields&, const PolicyFunctions&, void*, HashForKeyFn, bool); template void* GrowSooTableToNextCapacityAndPrepareInsert< - OptimalMemcpySizeForSooSlotTransfer(1), true>( - CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>, - bool); + OptimalMemcpySizeForSooSlotTransfer(1), true>(CommonFields&, + const PolicyFunctions&, void*, + HashForKeyFn, bool); static_assert(VerifyOptimalMemcpySizeForSooSlotTransferRange(2, 3)); template void* GrowSooTableToNextCapacityAndPrepareInsert< - OptimalMemcpySizeForSooSlotTransfer(3), true>( - CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>, - bool); + OptimalMemcpySizeForSooSlotTransfer(3), true>(CommonFields&, + const PolicyFunctions&, void*, + HashForKeyFn, bool); #if UINTPTR_MAX == UINT32_MAX static_assert(MaxSooSlotSize() == 4); @@ -2516,9 +2544,9 @@ #else static_assert(VerifyOptimalMemcpySizeForSooSlotTransferRange(4, 8)); template void* GrowSooTableToNextCapacityAndPrepareInsert< - OptimalMemcpySizeForSooSlotTransfer(8), true>( - CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>, - bool); + OptimalMemcpySizeForSooSlotTransfer(8), true>(CommonFields&, + const PolicyFunctions&, void*, + HashForKeyFn, bool); static_assert(MaxSooSlotSize() == 8); #endif
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index 1792ec2..a851710 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h
@@ -2176,22 +2176,24 @@ return 8; } +using HashForKeyFn = size_t (*)(void* hasher, size_t seed); + // Resizes SOO table to the NextCapacity(SooCapacity()) and prepares insert for // the given new_hash. Returns the new slot. // All possible template combinations are defined in cc file to improve // compilation time. template <size_t SooSlotMemcpySize, bool TransferUsesMemcpy> void* GrowSooTableToNextCapacityAndPrepareInsert( - CommonFields& common, const PolicyFunctions& policy, - absl::FunctionRef<size_t(size_t)> get_hash, bool force_sampling); + CommonFields& common, const PolicyFunctions& policy, void* hasher, + HashForKeyFn get_hash, bool force_sampling); // PrepareInsert for small tables (is_small()==true). // Returns the new slot. // Hash is only computed if the table is sampled or grew to large size // (is_small()==false). void* PrepareInsertSmallNonSoo(CommonFields& common, - const PolicyFunctions& policy, - absl::FunctionRef<size_t(size_t)> get_hash); + const PolicyFunctions& policy, void* hasher, + HashForKeyFn get_hash); // Resizes table with allocated slots and change the table seed. // Tables with SOO enabled must have capacity > policy.soo_capacity. @@ -2240,6 +2242,15 @@ template <bool kSooEnabled> void Destruct(CommonFields& c, const DtorPolicy& policy); +using EqualToKeyFn = bool (*)(void* set, const void* key, void* slot); + +// Asserts that hash and equal functors provided by the user are consistent, +// meaning that `eq(k1, k2)` implies `hash(k1)==hash(k2)`. +void AssertHashEqConsistentImpl(CommonFields& common, const void* hash_fn, + HashSlotFn hash_slot, size_t slot_size, + bool soo_enabled, size_t hash, const void* key, + EqualToKeyFn equal); + // Type-erased versions of raw_hash_set::erase_meta_only_{small,large}. void EraseMetaOnlySmall(CommonFields& c, bool soo_enabled, size_t slot_size); void EraseMetaOnlyLarge(CommonFields& c, size_t index, size_t slot_size); @@ -3871,14 +3882,14 @@ } constexpr bool kUseMemcpy = PolicyTraits::transfer_uses_memcpy() && SooEnabled(); + using Hasher = HashKey<hasher, K, kIsAbslHash, kSeedShift>; + Hasher hash_key{hash_ref(), key}; slot = to_slot( GrowSooTableToNextCapacityAndPrepareInsert< kUseMemcpy ? OptimalMemcpySizeForSooSlotTransfer(sizeof(slot_type)) : 0, - kUseMemcpy>( - common(), GetPolicyFunctions(), - HashKey<hasher, K, kIsAbslHash, kSeedShift>{hash_ref(), key}, - force_sampling)); + kUseMemcpy>(common(), GetPolicyFunctions(), &hash_key, + &Hasher::GetHash, force_sampling)); return {slot, true}; } @@ -3893,9 +3904,10 @@ return {single_slot(), false}; } } - return {to_slot(PrepareInsertSmallNonSoo( - common(), GetPolicyFunctions(), - HashKey<hasher, K, kIsAbslHash, kSeedShift>{hash_ref(), key})), + using Hasher = HashKey<hasher, K, kIsAbslHash, kSeedShift>; + Hasher hash_key{hash_ref(), key}; + return {to_slot(PrepareInsertSmallNonSoo(common(), GetPolicyFunctions(), + &hash_key, &Hasher::GetHash)), true}; } @@ -3957,6 +3969,12 @@ // Asserts that the capacity is not a sentinel invalid value. void AssertNotDebugCapacity() const { common().AssertNotDebugCapacity(); } + template <class K> + static bool equal_to_key_fn(void* set, const void* key, void* slot) { + return static_cast<const raw_hash_set*>(set)->equal_to( + *static_cast<const K*>(key), to_slot(slot)); + } + // 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> @@ -3972,26 +3990,10 @@ std::is_same_v<key_equal, std::equal_to<key_type>>; if constexpr (kIsDebug && !kIsStringAbslHashEq && !kIsScalarAbslHashEq) { if (empty()) return; - - const size_t hash_of_arg = hash_of(key); - const auto assert_consistent = [&](const ctrl_t*, void* slot) { - const bool is_key_equal = equal_to(key, to_slot(slot)); - if (!is_key_equal) return; - - [[maybe_unused]] const bool is_hash_equal = - hash_of_arg == hash_of(to_slot(slot)); - assert((!is_key_equal || is_hash_equal) && - "eq(k1, k2) must imply that hash(k1) == hash(k2). " - "hash/eq functors are inconsistent."); - }; - - if (is_small()) { - assert_consistent(/*unused*/ nullptr, single_slot()); - return; - } - // We only do validation for small tables so that it's constant time. - if (capacity() > 16) return; - IterateOverFullSlots(common(), sizeof(slot_type), assert_consistent); + AssertHashEqConsistentImpl( + common(), get_hash_ref_fn(common()), get_hash_slot_fn(), + sizeof(slot_type), SooEnabled(), hash_of(key), &key, + &equal_to_key_fn<K>); } } @@ -4141,6 +4143,11 @@ // TODO(b/397453582): Remove support for const hasher. return const_cast<std::remove_const_t<hasher>*>(&h->hash_ref()); } + static constexpr HashSlotFn get_hash_slot_fn() { + return PolicyTraits::template get_hash_slot_fn<hasher, kIsAbslHash, + kSeedShift>(); + } + static void transfer_n_slots_fn(void* set, void* dst, void* src, size_t count) { auto* src_slot = to_slot(src); @@ -4259,8 +4266,7 @@ // for standard layout and alignof(Hash) <= alignof(CommonFields). std::is_empty_v<hasher> ? &GetRefForEmptyClass : &raw_hash_set::get_hash_ref_fn, - PolicyTraits::template get_hash_slot_fn<hasher, kIsAbslHash, - kSeedShift>(), + get_hash_slot_fn(), PolicyTraits::transfer_uses_memcpy() ? TransferNRelocatable<sizeof(slot_type)> : &raw_hash_set::transfer_n_slots_fn, @@ -4411,17 +4417,17 @@ // Extern template instantiations reduce binary size and linker input size. // Function definition is in raw_hash_set.cc. extern template void* GrowSooTableToNextCapacityAndPrepareInsert<0, false>( - CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>, + CommonFields&, const PolicyFunctions&, void*, HashForKeyFn, bool); extern template void* GrowSooTableToNextCapacityAndPrepareInsert<1, true>( - CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>, + CommonFields&, const PolicyFunctions&, void*, HashForKeyFn, bool); extern template void* GrowSooTableToNextCapacityAndPrepareInsert<4, true>( - CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>, + CommonFields&, const PolicyFunctions&, void*, HashForKeyFn, bool); #if UINTPTR_MAX == UINT64_MAX extern template void* GrowSooTableToNextCapacityAndPrepareInsert<8, true>( - CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>, + CommonFields&, const PolicyFunctions&, void*, HashForKeyFn, bool); #endif