(Roll forward with template functions) Reduce SwissTable iterator template bloat and DWARF debug info size. Move type-independent iterator state, comparisons, assertions, and untyped slot accessors into HashSetIteratorBase, leaving only typed slot casts in raw_hash_set::iterator. Implement slot-size-dependent traversal operations as member function templates on HashSetIteratorBase rather than a derived class template, so that instantiating raw_hash_set::iterator does not evaluate sizeof(slot_type) when the value type is incomplete. Mark single-instruction unchecked iterator and slot helpers as always-inline to avoid emitting per-instantiation DWARF subprogram entries. PiperOrigin-RevId: 1011121955
diff --git a/absl/container/flat_hash_map_test.cc b/absl/container/flat_hash_map_test.cc index 213cb70..2daa235 100644 --- a/absl/container/flat_hash_map_test.cc +++ b/absl/container/flat_hash_map_test.cc
@@ -400,9 +400,18 @@ TEST(FlatHashMap, RecursiveTypeCompiles) { struct RecursiveType { flat_hash_map<int, RecursiveType> m; + flat_hash_map<int, RecursiveType>::iterator it; + flat_hash_map<int, RecursiveType>::const_iterator cit; + void Erase(int key) { m.erase(key); } }; RecursiveType t; t.m[0] = RecursiveType{}; + t.it = t.m.begin(); + t.cit = t.m.cbegin(); + EXPECT_NE(t.it, t.m.end()); + EXPECT_NE(t.cit, t.m.cend()); + t.Erase(0); + EXPECT_TRUE(t.m.empty()); } TEST(FlatHashMap, FlatHashMapPolicyDestroyReturnsTrue) {
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index 1d2875f..422181e 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h
@@ -1865,6 +1865,96 @@ } } +// Base class for iterators that stores type-erased control and slot pointers +// and implements operations that do not depend on the slot type. +// Slot-size-dependent operations (increment, skip_empty_or_deleted) are member +// function templates rather than a derived class template so that instantiating +// raw_hash_set::iterator does not evaluate sizeof(slot_type) when the value +// type is incomplete (b/299109480). +class HashSetIteratorBase : private HashSetIteratorGenerationInfo { + public: + // We use DefaultIterSlot() for default-constructed iterators so that + // they can be distinguished from end iterators, which have nullptr slot_. + HashSetIteratorBase() : slot_(DefaultIterSlot()) {} + + protected: + HashSetIteratorBase(ctrl_t* ctrl, void* slot, + const GenerationType* generation_ptr) + : HashSetIteratorGenerationInfo(generation_ptr), + ctrl_(ctrl), + slot_(slot) { + // This assumption helps the compiler know that any non-end iterator is + // not equal to any end iterator. + ABSL_ASSUME(slot != nullptr); + } + // For end() iterators. + explicit HashSetIteratorBase(const GenerationType* generation_ptr) + : HashSetIteratorGenerationInfo(generation_ptr), slot_(nullptr) {} + + void assert_is_full(const char* operation) const { + AssertIsFull(ctrl_, slot_, generation(), generation_ptr(), operation); + } + void* deref_slot() const { + assert_is_full("operator*()"); + return slot_; + } + void* arrow_slot() const { + assert_is_full("operator->"); + return slot_; + } + + template <size_t kSlotSize> + void increment() { + assert_is_full("operator++"); + ++ctrl_; + slot_ = static_cast<char*>(slot_) + kSlotSize; + skip_empty_or_deleted<kSlotSize>(); + if (ABSL_PREDICT_FALSE(*ctrl_ == ctrl_t::kSentinel)) slot_ = nullptr; + } + + // Fixes up `ctrl_` to point to a full or sentinel by advancing `ctrl_` and + // `slot_` until they reach one. + template <size_t kSlotSize> + void skip_empty_or_deleted() { + while (IsEmptyOrDeleted(*ctrl_)) { + ++ctrl_; + slot_ = static_cast<char*>(slot_) + kSlotSize; + } + } + + bool equals(const HashSetIteratorBase& b) const { + if constexpr (SwisstableDebugEnabled()) { + AssertIsValidForComparison(ctrl_, slot_, generation(), generation_ptr()); + AssertIsValidForComparison(b.ctrl_, b.slot_, b.generation(), + b.generation_ptr()); + AssertSameContainer(ctrl_, b.ctrl_, slot_, b.slot_, generation_ptr(), + b.generation_ptr()); + } + return unchecked_equals(b); + } + + // An equality check which skips ABSL Hardening iterator invalidation + // checks. + // Should be used when the lifetimes of the iterators are well-enough + // understood to prove that they cannot be invalid. + // Note: `b` is passed by reference because `HashSetIteratorBase` has an + // anonymous union member (`ctrl_`), which causes Clang to lower by-value + // copies as `memcpy` that affects compiler inlining decisions. + ABSL_ATTRIBUTE_ALWAYS_INLINE bool unchecked_equals( + const HashSetIteratorBase& b) const { + return slot_ == b.slot_; + } + + ctrl_t* control() const { return ctrl_; } + + // To avoid uninitialized member warnings, put ctrl_ in an anonymous union. + // The member is not initialized on singleton and end iterators. + union { + ctrl_t* ctrl_; + }; + void* slot_; +}; + struct FindInfo { size_t offset; size_t probe_length; @@ -2643,7 +2733,8 @@ static_assert(std::is_same_v<const_pointer, const value_type*>, "Allocators with custom pointer types are not supported"); - class iterator : private HashSetIteratorGenerationInfo { + class iterator : private HashSetIteratorBase { + using Base = HashSetIteratorBase; friend class raw_hash_set; friend struct HashtableFreeFunctionsAccess; @@ -2656,29 +2747,21 @@ using pointer = std::remove_reference_t<reference>*; using difference_type = typename raw_hash_set::difference_type; - // We use DefaultIterSlot() for default-constructed iterators so that - // they can be distinguished from end iterators, which have nullptr slot_. - iterator() : slot_(static_cast<slot_type*>(DefaultIterSlot())) {} + iterator() = default; // PRECONDITION: not an end() iterator. reference operator*() const { - assert_is_full("operator*()"); - return unchecked_deref(); + return PolicyTraits::element(to_slot(this->deref_slot())); } // PRECONDITION: not an end() iterator. pointer operator->() const { - assert_is_full("operator->"); - return &operator*(); + return &PolicyTraits::element(to_slot(this->arrow_slot())); } // PRECONDITION: not an end() iterator. iterator& operator++() { - assert_is_full("operator++"); - ++ctrl_; - ++slot_; - skip_empty_or_deleted(); - if (ABSL_PREDICT_FALSE(*ctrl_ == ctrl_t::kSentinel)) slot_ = nullptr; + this->increment<sizeof(slot_type)>(); return *this; } // PRECONDITION: not an end() iterator. @@ -2689,66 +2772,24 @@ } friend bool operator==(const iterator& a, const iterator& b) { - if constexpr (SwisstableDebugEnabled()) { - AssertIsValidForComparison(a.ctrl_, a.slot_, a.generation(), - a.generation_ptr()); - AssertIsValidForComparison(b.ctrl_, b.slot_, b.generation(), - b.generation_ptr()); - AssertSameContainer(a.ctrl_, b.ctrl_, a.slot_, b.slot_, - a.generation_ptr(), b.generation_ptr()); - } - return a.unchecked_equals(b); + return a.equals(b); } friend bool operator!=(const iterator& a, const iterator& b) { return !(a == b); } private: - iterator(ctrl_t* ctrl, slot_type* slot, - const GenerationType* generation_ptr) - : HashSetIteratorGenerationInfo(generation_ptr), - ctrl_(ctrl), - slot_(slot) { - // This assumption helps the compiler know that any non-end iterator is - // not equal to any end iterator. - ABSL_ASSUME(slot != nullptr); - } - // For end() iterators. - explicit iterator(const GenerationType* generation_ptr) - : HashSetIteratorGenerationInfo(generation_ptr), slot_(nullptr) {} - - void assert_is_full(const char* operation) const { - AssertIsFull(ctrl_, slot_, generation(), generation_ptr(), operation); - } - - // Fixes up `ctrl_` to point to a full or sentinel by advancing `ctrl_` and - // `slot_` until they reach one. - void skip_empty_or_deleted() { - while (IsEmptyOrDeleted(*ctrl_)) { - ++ctrl_; - ++slot_; - } - } - - // An equality check which skips ABSL Hardening iterator invalidation - // checks. - // Should be used when the lifetimes of the iterators are well-enough - // understood to prove that they cannot be invalid. - bool unchecked_equals(const iterator& b) const { return slot_ == b.slot(); } + using Base::Base; // Dereferences the iterator without ABSL Hardening iterator invalidation // checks. - reference unchecked_deref() const { return PolicyTraits::element(slot_); } + ABSL_ATTRIBUTE_ALWAYS_INLINE reference unchecked_deref() const { + return PolicyTraits::element(slot()); + } - ctrl_t* control() const { return ctrl_; } - slot_type* slot() const { return slot_; } - - // To avoid uninitialized member warnings, put ctrl_ in an anonymous union. - // The member is not initialized on singleton and end iterators. - union { - ctrl_t* ctrl_; - }; - slot_type* slot_; + ABSL_ATTRIBUTE_ALWAYS_INLINE slot_type* slot() const { + return to_slot(this->slot_); + } }; class const_iterator { @@ -2785,16 +2826,16 @@ } private: - const_iterator(const ctrl_t* ctrl, const slot_type* slot, - const GenerationType* gen) - : inner_(const_cast<ctrl_t*>(ctrl), const_cast<slot_type*>(slot), gen) { - } - bool unchecked_equals(const const_iterator& b) const { + ABSL_ATTRIBUTE_ALWAYS_INLINE bool unchecked_equals( + const const_iterator& b) const { return inner_.unchecked_equals(b.inner_); } - reference unchecked_deref() const { return inner_.unchecked_deref(); } - ctrl_t* control() const { return inner_.control(); } - slot_type* slot() const { return inner_.slot(); } + ABSL_ATTRIBUTE_ALWAYS_INLINE reference unchecked_deref() const { + return inner_.unchecked_deref(); + } + ABSL_ATTRIBUTE_ALWAYS_INLINE slot_type* slot() const { + return inner_.slot(); + } iterator inner_; }; @@ -3033,7 +3074,7 @@ if (is_small()) return single_iterator(); iterator it = {control(), slot_array(capacity()), common().generation_ptr()}; - it.skip_empty_or_deleted(); + it.template skip_empty_or_deleted<sizeof(slot_type)>(); ABSL_SWISSTABLE_ASSERT(IsFull(*it.control())); return it; } @@ -4090,28 +4131,26 @@ } return {InsertIteratorControl(), slot, common().generation_ptr()}; } - iterator iterator_at(size_t i) ABSL_ATTRIBUTE_LIFETIME_BOUND { - return {control() + i, slot_array() + i, common().generation_ptr()}; - } - const_iterator iterator_at(size_t i) const ABSL_ATTRIBUTE_LIFETIME_BOUND { - return const_cast<raw_hash_set*>(this)->iterator_at(i); - } iterator iterator_at_ptr(ctrl_t* ctrl, void* slot) ABSL_ATTRIBUTE_LIFETIME_BOUND { - return {ctrl, to_slot(slot), common().generation_ptr()}; + return {ctrl, slot, common().generation_ptr()}; } // For use in raw_hash_map and friend functions. - static typename iterator::reference unchecked_deref(iterator it) { + ABSL_ATTRIBUTE_ALWAYS_INLINE static decltype(auto) unchecked_deref( + iterator it) { return it.unchecked_deref(); } - static const_reference unchecked_deref(const_iterator it) { + ABSL_ATTRIBUTE_ALWAYS_INLINE static const_reference unchecked_deref( + const_iterator it) { return it.unchecked_deref(); } - static bool unchecked_equals(iterator a, iterator b) { + ABSL_ATTRIBUTE_ALWAYS_INLINE static bool unchecked_equals(iterator a, + iterator b) { return a.unchecked_equals(b); } - static bool unchecked_equals(const_iterator a, const_iterator b) { + ABSL_ATTRIBUTE_ALWAYS_INLINE static bool unchecked_equals(const_iterator a, + const_iterator b) { return a.unchecked_equals(b); }