From 15957950d997cd9e09c61add5200361d5d1e7e11 Mon Sep 17 00:00:00 2001 From: Evan Brown Date: Tue, 14 Feb 2023 12:30:41 -0800 Subject: Make default-constructed swisstable iterators use EmptyGroup() for ctrl_ so that we can distinguish between end() iterators and default-constructed iterators in debug mode. PiperOrigin-RevId: 509606271 Change-Id: I77b68590b3904a4cf7809b75d814d74cb89603b6 --- absl/container/internal/raw_hash_set.h | 53 +++++++++++++++++++++------------- 1 file changed, 33 insertions(+), 20 deletions(-) (limited to 'absl/container/internal/raw_hash_set.h') diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index a2ada0cb..33e05736 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h @@ -816,6 +816,10 @@ class CommonFieldsGenerationInfoEnabled { // the code more complicated, and there's a benefit in having the sizes of // raw_hash_set in sanitizer mode and non-sanitizer mode a bit more different, // which is that tests are less likely to rely on the size remaining the same. + // TODO(b/254649633): Currently, we can't detect when end iterators from + // different empty tables are compared. If we allocate generations separately + // from control bytes, then we could do so. Another option would be to have N + // empty generations and use a random one for empty hashtables. GenerationType* generation_ = EmptyGeneration(); }; @@ -853,9 +857,6 @@ class HashSetIteratorGenerationInfoEnabled { void set_generation_ptr(const GenerationType* ptr) { generation_ptr_ = ptr; } private: - // TODO(b/254649633): use a different static generation for default - // constructed iterators so that we can detect when default constructed - // iterators are compared to iterators from empty tables. const GenerationType* generation_ptr_ = EmptyGeneration(); GenerationType generation_ = *generation_ptr_; }; @@ -1040,10 +1041,10 @@ size_t SelectBucketCountForIterRange(InputIter first, InputIter last, #define ABSL_INTERNAL_ASSERT_IS_FULL(ctrl, generation, generation_ptr, \ operation) \ do { \ - ABSL_HARDENING_ASSERT( \ - (ctrl != nullptr) && operation \ - " called on invalid iterator. The iterator might be an end() " \ - "iterator or may have been default constructed."); \ + ABSL_HARDENING_ASSERT((ctrl != nullptr) && operation \ + " called on end() iterator."); \ + ABSL_HARDENING_ASSERT((ctrl != EmptyGroup()) && operation \ + " called on default-constructed iterator."); \ if (SwisstableGenerationsEnabled() && generation != *generation_ptr) \ ABSL_INTERNAL_LOG(FATAL, operation \ " called on invalidated iterator. The table could " \ @@ -1058,9 +1059,10 @@ size_t SelectBucketCountForIterRange(InputIter first, InputIter last, inline void AssertIsValidForComparison(const ctrl_t* ctrl, GenerationType generation, const GenerationType* generation_ptr) { - ABSL_HARDENING_ASSERT((ctrl == nullptr || IsFull(*ctrl)) && - "Invalid iterator comparison. The element might have " - "been erased or the table might have rehashed."); + ABSL_HARDENING_ASSERT( + (ctrl == nullptr || ctrl == EmptyGroup() || IsFull(*ctrl)) && + "Invalid iterator comparison. The element might have " + "been erased or the table might have rehashed."); if (SwisstableGenerationsEnabled() && generation != *generation_ptr) { ABSL_INTERNAL_LOG(FATAL, "Invalid iterator comparison. The table could have " @@ -1095,16 +1097,27 @@ inline void AssertSameContainer(const ctrl_t* ctrl_a, const ctrl_t* ctrl_b, const void* const& slot_b, const GenerationType* generation_ptr_a, const GenerationType* generation_ptr_b) { +#if defined(ABSL_SWISSTABLE_ENABLE_GENERATIONS) || \ + ABSL_OPTION_HARDENED == 1 || !defined(NDEBUG) + const bool a_is_default = ctrl_a == EmptyGroup(); + const bool b_is_default = ctrl_b == EmptyGroup(); + if (a_is_default != b_is_default) { + ABSL_INTERNAL_LOG( + FATAL, + "Invalid iterator comparison. Comparing default-constructed iterator " + "with non-default-constructed iterator."); + } + if (a_is_default && b_is_default) return; +#endif + if (SwisstableGenerationsEnabled() && generation_ptr_a != generation_ptr_b) { - // TODO(b/254649633): use a different static generation for default - // constructed iterators so that we can split the empty/default cases. - const bool a_is_empty_or_default = generation_ptr_a == EmptyGeneration(); - const bool b_is_empty_or_default = generation_ptr_b == EmptyGeneration(); - if (a_is_empty_or_default != b_is_empty_or_default) { + const bool a_is_empty = generation_ptr_a == EmptyGeneration(); + const bool b_is_empty = generation_ptr_b == EmptyGeneration(); + if (a_is_empty != b_is_empty) { ABSL_INTERNAL_LOG(FATAL, "Invalid iterator comparison. Comparing iterator from " "a non-empty hashtable with an iterator from an empty " - "hashtable or a default-constructed iterator."); + "hashtable."); } const bool a_is_end = ctrl_a == nullptr; const bool b_is_end = ctrl_b == nullptr; @@ -1509,7 +1522,7 @@ class raw_hash_set { } // For end() iterators. explicit iterator(const GenerationType* generation_ptr) - : HashSetIteratorGenerationInfo(generation_ptr) {} + : HashSetIteratorGenerationInfo(generation_ptr), ctrl_(nullptr) {} // Fixes up `ctrl_` to point to a full by advancing it and `slot_` until // they reach one. @@ -1524,9 +1537,9 @@ class raw_hash_set { if (ABSL_PREDICT_FALSE(*ctrl_ == ctrl_t::kSentinel)) ctrl_ = nullptr; } - // TODO(b/254649633): use non-null control for default-constructed iterators - // so that we can distinguish between them and end iterators in debug mode. - ctrl_t* ctrl_ = nullptr; + // We use EmptyGroup() for default-constructed iterators so that they can + // be distinguished from end iterators, which have nullptr ctrl_. + ctrl_t* ctrl_ = EmptyGroup(); // To avoid uninitialized member warnings, put slot_ in an anonymous union. // The member is not initialized on singleton and end iterators. union { -- cgit v1.2.3