Update raw_hash_set constructors to consistently use reservation size. The size argument in raw_hash_set constructors is now always treated as a reservation size, indicating the number of elements the container can hold before a rehash. The `ReservationSize` wrapper struct has been removed. The documentation for flat_hash_map and flat_hash_set has been updated to reflect this change. PiperOrigin-RevId: 940829942 Change-Id: I1a5b54b3f68b6bbd937af4eee4a7455fdae64af8
diff --git a/absl/container/flat_hash_map.h b/absl/container/flat_hash_map.h index 236f80f..816799e 100644 --- a/absl/container/flat_hash_map.h +++ b/absl/container/flat_hash_map.h
@@ -71,9 +71,9 @@ // * Contains a `capacity()` member function indicating the number of element // slots (open, deleted, and empty) within the hash map. // * Returns `void` from the `erase(iterator)` overload. -// * Range constructors (including initializer list) accept reservation size as -// an optional argument instead of bucket count. Reservation size is the -// number of elements that fits in the map before rehash. +// * Constructors accept reservation size as an optional argument instead of +// bucket count. Reservation size is the number of elements that fits in the +// map before rehash. // // TODO(b/519468416): copy redacted version of notable differences to // node_hash_* files.
diff --git a/absl/container/flat_hash_set.h b/absl/container/flat_hash_set.h index a8ca8fb..00115c8 100644 --- a/absl/container/flat_hash_set.h +++ b/absl/container/flat_hash_set.h
@@ -71,9 +71,9 @@ // * Contains a `capacity()` member function indicating the number of element // slots (open, deleted, and empty) within the hash set. // * Returns `void` from the `erase(iterator)` overload. -// * Range constructors (including initializer list) accept reservation size as -// an optional argument instead of bucket count. Reservation size is the -// number of elements that fits in the set before rehash. +// * Constructors accept reservation size as an optional argument instead of +// bucket count. Reservation size is the number of elements that fits in the +// set before rehash. // // By default, `flat_hash_set` uses the `absl::Hash` hashing framework. All // fundamental and Abseil types that support the `absl::Hash` framework have a
diff --git a/absl/container/internal/raw_hash_set.cc b/absl/container/internal/raw_hash_set.cc index cccf849..9180c36 100644 --- a/absl/container/internal/raw_hash_set.cc +++ b/absl/container/internal/raw_hash_set.cc
@@ -2117,16 +2117,6 @@ } } -void ReserveEmptyNonAllocatedTableToFitBucketCount( - CommonFields& common, const PolicyFunctions& __restrict policy, - size_t bucket_count) { - size_t new_capacity = NormalizeCapacity(bucket_count); - ValidateMaxCapacity(new_capacity, policy.key_size, policy.slot_size); - ResizeEmptyNonAllocatedTableImpl(common, policy, new_capacity, - /*blocked_element_count=*/0, - /*force_infoz=*/false); -} - // Resizes a full SOO table to the NextCapacity(SooCapacity()). template <size_t SooSlotMemcpySize, bool TransferUsesMemcpy> size_t GrowSooTableToNextCapacityAndPrepareInsert( @@ -2322,6 +2312,8 @@ void ReserveTableToFitNewSize(CommonFields& common, const PolicyFunctions& __restrict policy, size_t new_size) { + new_size = + std::min(new_size, MaxValidSize(policy.key_size, policy.slot_size)); common.reset_reserved_growth(new_size); common.set_reservation_size(new_size); ABSL_SWISSTABLE_ASSERT(new_size > policy.soo_capacity());
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index 1d841ca..735cba6 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h
@@ -1502,26 +1502,17 @@ // ctrl[i] != ctrl_t::kSentinel for all i < capacity void ConvertDeletedToEmptyAndFullToDeleted(ctrl_t* ctrl, size_t capacity); -// A wrapper around size_t that is used to indicate that the size is a -// reservation size. This is used to differentiate between the reservation size -// and bucket count. Reservation size is the number of elements that fits in the -// set before rehash. -struct ReservationSize { - size_t size; -}; - template <class InputIter> -ReservationSize SelectReservationSizeForIterRange(InputIter first, - InputIter last, - size_t reservation_size) { +size_t SelectReservationSizeForIterRange(InputIter first, InputIter last, + size_t reservation_size) { if (reservation_size != 0) { - return ReservationSize{reservation_size}; + return reservation_size; } if (base_internal::IsAtLeastIterator<std::random_access_iterator_tag, InputIter>()) { - return ReservationSize{static_cast<size_t>(std::distance(first, last))}; + return static_cast<size_t>(std::distance(first, last)); } - return ReservationSize{0}; + return 0; } constexpr bool SwisstableDebugEnabled() { @@ -2001,16 +1992,6 @@ void ReserveTableToFitNewSize(CommonFields& common, const PolicyFunctions& policy, size_t new_size); -// Resizes empty non-allocated table to the next valid capacity after -// `bucket_count`. Requires: -// 1. `c.capacity() == policy.soo_capacity`. -// 2. `c.empty()`. -// 3. `new_size > policy.soo_capacity`. -// 4. `bucket_count <= MaxValidCapacity()`. -// The table will be attempted to be sampled. -void ReserveEmptyNonAllocatedTableToFitBucketCount( - CommonFields& common, const PolicyFunctions& policy, size_t bucket_count); - // Type erased version of raw_hash_set::rehash. // Requires: `n <= MaxValidCapacity()`. void Rehash(CommonFields& common, const PolicyFunctions& policy, size_t n); @@ -2529,26 +2510,23 @@ std::is_nothrow_default_constructible_v<key_equal> && std::is_nothrow_default_constructible_v<allocator_type>) {} - explicit raw_hash_set( - // TODO(b/519468416): treat bucket_count as reservation size. - size_t bucket_count, const hasher& hash = hasher(), - const key_equal& eq = key_equal(), - const allocator_type& alloc = allocator_type()) + explicit raw_hash_set(size_t reservation_size, const hasher& hash = hasher(), + const key_equal& eq = key_equal(), + const allocator_type& alloc = allocator_type()) : settings_(CommonFields::CreateDefault<SooEnabled()>(), hash, eq, alloc) { - if (bucket_count > DefaultCapacity()) { - ReserveEmptyNonAllocatedTableToFitBucketCount( - common(), GetPolicyFunctions(), - (std::min)(bucket_count, MaxValidCapacity())); + if (reservation_size > DefaultCapacity()) { + ReserveTableToFitNewSize(common(), GetPolicyFunctions(), + reservation_size); } } - raw_hash_set(size_t bucket_count, const hasher& hash, + raw_hash_set(size_t reservation_size, const hasher& hash, const allocator_type& alloc) - : raw_hash_set(bucket_count, hash, key_equal(), alloc) {} + : raw_hash_set(reservation_size, hash, key_equal(), alloc) {} - raw_hash_set(size_t bucket_count, const allocator_type& alloc) - : raw_hash_set(bucket_count, hasher(), key_equal(), alloc) {} + raw_hash_set(size_t reservation_size, const allocator_type& alloc) + : raw_hash_set(reservation_size, hasher(), key_equal(), alloc) {} explicit raw_hash_set(const allocator_type& alloc) : raw_hash_set(0, hasher(), key_equal(), alloc) {} @@ -3176,8 +3154,7 @@ void reserve(size_t n) { if (ABSL_PREDICT_TRUE(n > DefaultCapacity())) { - ReserveTableToFitNewSize(common(), GetPolicyFunctions(), - (std::min)(n, MaxValidSize())); + ReserveTableToFitNewSize(common(), GetPolicyFunctions(), n); } } @@ -3361,19 +3338,6 @@ slot_type&& slot; }; - explicit raw_hash_set(ReservationSize reservation_size, - const hasher& hash = hasher(), - const key_equal& eq = key_equal(), - const allocator_type& alloc = allocator_type()) - : settings_(CommonFields::CreateDefault<SooEnabled()>(), hash, eq, - alloc) { - if (reservation_size.size > DefaultCapacity()) { - ReserveTableToFitNewSize( - common(), GetPolicyFunctions(), - (std::min)(reservation_size.size, MaxValidSize())); - } - } - template <typename... Args> void construct(slot_type* slot, Args&&... args) { common().RunWithReentrancyGuard([&] {
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc index f847dba..b004887 100644 --- a/absl/container/internal/raw_hash_set_test.cc +++ b/absl/container/internal/raw_hash_set_test.cc
@@ -1646,34 +1646,56 @@ } TYPED_TEST(SooTest, InsertWithinCapacity) { - TypeParam t; - t.reserve(10); - const size_t original_capacity = t.capacity(); - const auto addr = [&](int i) { - return reinterpret_cast<uintptr_t>(&*t.find(i)); + using TableType = TypeParam; + using ReserveFn = std::function<size_t(size_t, TableType&)>; + ReserveFn reserve_and_insert = [](size_t size, TableType& t) { + t.reserve(size); + size_t cap = t.capacity(); + return cap; }; - // Inserting an element does not change capacity. - t.insert(0); - EXPECT_THAT(t.capacity(), original_capacity); - const uintptr_t original_addr_0 = addr(0); - // Inserting another element does not rehash. - t.insert(1); - EXPECT_THAT(t.capacity(), original_capacity); - EXPECT_THAT(addr(0), original_addr_0); - // Inserting lots of duplicate elements does not rehash. - for (int i = 0; i < 100; ++i) { - t.insert(i % 10); + ReserveFn construct_and_insert = [](size_t size, TableType& t) { + t = TableType(size); + size_t cap = t.capacity(); + return cap; + }; + ReserveFn construct_inisitializer_list_with_reservation = + [](size_t size, TableType& t) { + t = TableType({}, size); + return t.capacity(); + }; + ReserveFn construct_range_iter_with_reservation = [](size_t size, + TableType& t) { + std::vector<int> v; + t = TableType(v.begin(), v.end(), size); + return t.capacity(); + }; + + std::vector<ReserveFn> reserve_and_insert_fns = { + reserve_and_insert, construct_and_insert, + construct_inisitializer_list_with_reservation, + construct_range_iter_with_reservation}; + for (size_t fn_i = 0; fn_i < reserve_and_insert_fns.size(); ++fn_i) { + ReserveFn reserve_and_insert_fn = reserve_and_insert_fns[fn_i]; + for (int size : {3, 5, 7, 11, 27, 36}) { + SCOPED_TRACE(absl::StrCat("fn_i: ", fn_i, ", size: ", size)); + TableType t; + const size_t original_capacity = + reserve_and_insert_fn(static_cast<size_t>(size), t); + const auto addr = [&](int i) { + return reinterpret_cast<uintptr_t>(&*t.find(i)); + }; + // Inserting an element does not change capacity. + t.insert(0); + ASSERT_THAT(t.capacity(), original_capacity); + const uintptr_t original_addr_0 = addr(0); + // Inserting lots of duplicate elements does not rehash. + for (int i = 0; i < size * 5; ++i) { + t.insert(i % size); + } + ASSERT_THAT(t.capacity(), original_capacity); + ASSERT_THAT(addr(0), original_addr_0); + } } - EXPECT_THAT(t.capacity(), original_capacity); - EXPECT_THAT(addr(0), original_addr_0); - // Inserting a range of duplicate elements does not rehash. - std::vector<int> dup_range; - for (int i = 0; i < 100; ++i) { - dup_range.push_back(i % 10); - } - t.insert(dup_range.begin(), dup_range.end()); - EXPECT_THAT(t.capacity(), original_capacity); - EXPECT_THAT(addr(0), original_addr_0); } TYPED_TEST(SooTest, ClearDifferentSizes) { @@ -5046,38 +5068,6 @@ } } -TEST(Table, MaxSizeOverflow) { -#ifdef ABSL_HAVE_EXCEPTIONS - GTEST_SKIP() << "Skipping test because exceptions are enabled. EXPECT_DEATH " - "doesn't work with exceptions."; -#elif defined(ABSL_HAVE_THREAD_SANITIZER) - GTEST_SKIP() << "ThreadSanitizer test runs fail on OOM even in EXPECT_DEATH."; -#else - const std::string expected_death_message = - "new failed|failed to allocate|bad_alloc|exceeds maximum supported size"; - size_t overflow = (std::numeric_limits<size_t>::max)(); - EXPECT_DEATH_IF_SUPPORTED(IntTable t(overflow), expected_death_message); - IntTable t; - EXPECT_DEATH_IF_SUPPORTED(t.reserve(overflow), expected_death_message); - EXPECT_DEATH_IF_SUPPORTED(t.rehash(overflow), expected_death_message); - size_t slightly_overflow = - MaxValidSize(sizeof(IntTable::key_type), sizeof(IntTable::value_type)) + - 1; - size_t slightly_overflow_capacity = - NextCapacity(NormalizeCapacity(slightly_overflow)); - EXPECT_DEATH_IF_SUPPORTED(IntTable t2(slightly_overflow_capacity - 10), - expected_death_message); - EXPECT_DEATH_IF_SUPPORTED(t.reserve(slightly_overflow), - expected_death_message); - EXPECT_DEATH_IF_SUPPORTED(t.rehash(slightly_overflow), - expected_death_message); - IntTable non_empty_table; - non_empty_table.insert(0); - EXPECT_DEATH_IF_SUPPORTED(non_empty_table.reserve(slightly_overflow), - expected_death_message); -#endif // defined(ABSL_HAVE_THREAD_SANITIZER) -} - // Tests that reserving enough space for more than the max number of unique keys // doesn't crash and we end up with kMaxValidCapacity. TEST(Table, MaxSizeOverflowUniqueKeys) {