Split Table.Decompose and add derived-key and conversion tests. PiperOrigin-RevId: 1024431817
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc index e0a6cb1..2dec4c2 100644 --- a/absl/container/internal/raw_hash_set_test.cc +++ b/absl/container/internal/raw_hash_set_test.cc
@@ -2938,6 +2938,10 @@ return *this; } + friend bool operator==(const DecomposeType& a, const DecomposeType& b) { + return a.i == b.i; + } + template <typename H> friend H AbslHashValue(H h, const DecomposeType& d) { return H::combine(std::move(h), d.i); @@ -2997,9 +3001,6 @@ const int one = 1; const char* three_p = "3"; const auto& three = three_p; - const int elem_vector_count = 256; - std::vector<DecomposeType> elem_vector(elem_vector_count, DecomposeType{0}); - std::iota(elem_vector.begin(), elem_vector.end(), 0); using DecomposeSet = raw_hash_set<DecomposePolicy, Hash, Eq, std::allocator<int>>; @@ -3014,25 +3015,28 @@ EXPECT_EQ(++expected_constructed, decompose_constructed); set1.emplace("3"); EXPECT_EQ(++expected_constructed, decompose_constructed); - EXPECT_EQ(expected_constructed, decompose_constructed); - { // insert(T&&) + { // insert(T&&) / insert(const T&) / insert(hint, ...) set1.insert(1); EXPECT_EQ(expected_constructed, decompose_constructed); - } - - { // insert(const T&) set1.insert(one); EXPECT_EQ(expected_constructed, decompose_constructed); - } - - { // insert(hint, T&&) set1.insert(set1.begin(), 1); EXPECT_EQ(expected_constructed, decompose_constructed); + set1.insert(set1.begin(), one); + EXPECT_EQ(expected_constructed, decompose_constructed); } - { // insert(hint, const T&) - set1.insert(set1.begin(), one); + { // insert(const init_type&) via derived type and reference_wrapper + struct DerivedDecomposeType : DecomposeType { + using DecomposeType::DecomposeType; + }; + const DerivedDecomposeType derived(0); + ++expected_constructed; + EXPECT_FALSE(set1.insert(derived).second); + EXPECT_EQ(set1.insert(set1.begin(), derived)->i, 0); + EXPECT_FALSE(set1.insert(std::cref(elem)).second); + EXPECT_NE(set1.find(derived), set1.end()); EXPECT_EQ(expected_constructed, decompose_constructed); } @@ -3061,6 +3065,16 @@ expected_constructed += construct_three; EXPECT_EQ(expected_constructed, decompose_constructed); } +} + +template <typename Hash, typename Eq> +void TestDecomposeRangeInsert() { + const int elem_vector_count = 256; + std::vector<DecomposeType> elem_vector(elem_vector_count, DecomposeType{0}); + std::iota(elem_vector.begin(), elem_vector.end(), 0); + + using DecomposeSet = + raw_hash_set<DecomposePolicy, Hash, Eq, std::allocator<int>>; decompose_copy_constructed = 0; decompose_copy_assigned = 0; @@ -3093,8 +3107,6 @@ EXPECT_GE(expected_move_constructed, decompose_move_constructed); EXPECT_EQ(0, decompose_move_assigned); EXPECT_EQ(0, decompose_copy_assigned); - expected_copy_constructed = decompose_copy_constructed; - expected_move_constructed = decompose_move_constructed; } { // insert(first, last) @@ -3110,28 +3122,25 @@ EXPECT_GE(expected_move_constructed, decompose_move_constructed); EXPECT_EQ(0, decompose_move_assigned); EXPECT_EQ(0, decompose_copy_assigned); - expected_copy_constructed = decompose_copy_constructed; - expected_move_constructed = decompose_move_constructed; } } -TEST(Table, Decompose) { - if (SwisstableGenerationsEnabled()) { - GTEST_SKIP() << "Generations being enabled causes extra rehashes."; +struct TransparentHashIntOverload { + size_t operator()(const DecomposeType& a) const { + return static_cast<size_t>(a.i); } + size_t operator()(int a) const { return static_cast<size_t>(a); } +}; +struct TransparentEqIntOverload { + bool operator()(const DecomposeType& a, const DecomposeType& b) const { + return a.i == b.i; + } + bool operator()(const DecomposeType& a, int b) const { return a.i == b; } +}; + +TEST(Table, Decompose) { TestDecompose<DecomposeHash, DecomposeEq>(false); - - struct TransparentHashIntOverload { - size_t operator()(const DecomposeType& a) const { return a.i; } - size_t operator()(int a) const { return a; } - }; - struct TransparentEqIntOverload { - bool operator()(const DecomposeType& a, const DecomposeType& b) const { - return a.i == b.i; - } - bool operator()(const DecomposeType& a, int b) const { return a.i == b; } - }; TestDecompose<TransparentHashIntOverload, DecomposeEq>(true); TestDecompose<TransparentHashIntOverload, TransparentEqIntOverload>(true); TestDecompose<DecomposeHash, TransparentEqIntOverload>(true); @@ -3139,6 +3148,125 @@ TransparentEqIntOverload>(true); } +template <typename Hash, typename Eq> +void TestDecomposeNonTransparent() { + using Set = raw_hash_set<DecomposePolicy, Hash, Eq, std::allocator<int>>; + Set set; + set.insert(DecomposeType{0}); + set.insert(DecomposeType{2}); + + decompose_constructed = 0; + // Miss converts for lookup and constructs once in the slot. + set.insert(1); + EXPECT_GE(decompose_constructed, 2); + + const int one = 1; + // TODO(b/413633804): Tighten to EXPECT_EQ(..., 1) once EmplaceDecomposable + // converts non-transparent keys at the lookup boundary. + auto check_hit = [&](absl::FunctionRef<void(Set&, int)> fn) { + decompose_constructed = 0; + fn(set, one); + EXPECT_GE(decompose_constructed, 1); + }; + check_hit([](Set& s, int) { s.insert(1); }); + check_hit([](Set& s, int v) { s.insert(v); }); + check_hit([](Set& s, int) { s.insert(s.begin(), 1); }); + check_hit([](Set& s, int v) { s.insert(s.begin(), v); }); + check_hit([](Set& s, int) { s.emplace(1); }); + check_hit([](Set& s, int v) { s.emplace(v); }); + check_hit([](Set& s, int) { s.emplace_hint(s.begin(), 1); }); + check_hit([](Set& s, int v) { s.emplace_hint(s.begin(), v); }); +} + +TEST(Table, DecomposeNonTransparentSingleConversion) { + struct NonTransparentHash { + size_t operator()(const DecomposeType& a) const { + // Force collisions so per-probe key conversions would increase the + // construction count. + return static_cast<size_t>(a.i) % 2; + } + }; + struct NonTransparentEq { + bool operator()(const DecomposeType& a, const DecomposeType& b) const { + return a.i == b.i; + } + }; + TestDecomposeNonTransparent<NonTransparentHash, DecomposeEq>(); + TestDecomposeNonTransparent<NonTransparentHash, NonTransparentEq>(); + TestDecomposeNonTransparent<DecomposeHash, NonTransparentEq>(); +} + +TEST(Table, EmplaceHeterogeneousKeyHitDoesNotMoveValue) { + absl::flat_hash_map<int64_t, std::unique_ptr<int>> m; + m.emplace(int64_t{1}, std::make_unique<int>(42)); + auto p = std::make_unique<int>(99); + EXPECT_FALSE(m.emplace(1, std::move(p)).second); + EXPECT_NE(p, nullptr); + EXPECT_EQ(*m[1], 42); +} + +TEST(Table, DecomposeRangeInsert) { + if (SwisstableGenerationsEnabled()) { + GTEST_SKIP() << "Generations being enabled causes extra rehashes."; + } + + TestDecomposeRangeInsert<DecomposeHash, DecomposeEq>(); + TestDecomposeRangeInsert<TransparentHashIntOverload, DecomposeEq>(); + TestDecomposeRangeInsert<TransparentHashIntOverload, + TransparentEqIntOverload>(); + TestDecomposeRangeInsert<DecomposeHash, TransparentEqIntOverload>(); + TestDecomposeRangeInsert<absl::TransparentHash<DecomposeType, int>, + TransparentEqIntOverload>(); +} + +TEST(Table, DerivedKeyMap) { + struct DerivedDecomposeType : DecomposeType { + using DecomposeType::DecomposeType; + }; + const DerivedDecomposeType d(2); + absl::flat_hash_map<DecomposeType, int> map; + std::pair<DerivedDecomposeType, int> p(DerivedDecomposeType(10), 100); + EXPECT_TRUE(map.insert(p).second); + EXPECT_TRUE(map.insert({d, 200}).second); + EXPECT_FALSE(map.try_emplace(d, 300).second); + EXPECT_EQ(map.find(d)->second, 200); + EXPECT_EQ(map[d], 200); +} + +TEST(Table, DerivedKeyTrivialSet) { + struct TrivialBase { + int v; + }; + struct TrivialDerived : TrivialBase {}; + struct TrivialHash { + size_t operator()(TrivialBase k) const { return static_cast<size_t>(k.v); } + }; + struct TrivialEq { + bool operator()(TrivialBase a, TrivialBase b) const { return a.v == b.v; } + }; + absl::flat_hash_set<TrivialBase, TrivialHash, TrivialEq> set; + const TrivialDerived td{{7}}; + EXPECT_TRUE(set.insert(td).second); + EXPECT_EQ(set.insert(set.begin(), td)->v, 7); +} + +struct TemplatedConversionProxy { + int v; + template <typename T> + operator T() const { // NOLINT(google-explicit-constructor) + static_assert(std::is_same_v<T, int>); + return T(v); + } +}; + +TEST(Table, InsertTemplatedConversionOperator) { + absl::flat_hash_set<int> set; + const TemplatedConversionProxy p{42}; + EXPECT_TRUE(set.insert(p).second); + EXPECT_EQ(*set.insert(set.begin(), TemplatedConversionProxy{42}), 42); + EXPECT_THAT(set, ElementsAre(42)); +} + struct Modulo1000Hash { size_t operator()(int64_t x) const { return static_cast<size_t>(x) % 1000; } };