Fix 64-bit slot-size threshold in MaxValidSizeForSlotSize().
On 64-bit platforms, MaxValidSizeForSlotSize() returned MaxStorableSize() (2^40 - 1, whose SizeToCapacity() is 2^41 - 1) whenever `slot_size < 1 << 24`. Because kMaxValidCapacity shifts `~uint64_t{}` right by 2 and SizeToCapacity() rounds up to the next power-of-two capacity minus one, any slot_size in (3670016, 2^24) produced a MaxValidSize() exceeding MaxSizeAtMaxValidCapacity(slot_size), and slot sizes in [2^23, 2^24) overflowed 64-bit alloc_size_ calculation in RawHashSetLayout.
Compare slot_size against `CapacityToGrowth(~uint64_t{} >> 2) / MaxStorableSize()` so MaxValidSizeForSlotSize() preserves its division-free fast path for normal slot sizes while matching `(std::min)(MaxStorableSize(), MaxSizeAtMaxValidCapacity(slot_size))` across all slot sizes.
PiperOrigin-RevId: 1023784831
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index 94bbfd1..0036bb8 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -2300,11 +2300,15 @@
// other optimizations for tables with small keys.
template <size_t kSizeOfSizeT = sizeof(size_t)>
-constexpr size_t MaxSizeAtMaxValidCapacity(size_t slot_size) {
+constexpr size_t MaxValidCapacity() {
using SizeT = std::conditional_t<kSizeOfSizeT == 4, uint32_t, uint64_t>;
// We shift right by 2 for a safe margin against overflow.
- constexpr SizeT kMaxValidCapacity = ~SizeT{} >> 2;
- return CapacityToGrowth(kMaxValidCapacity) / slot_size;
+ return ~SizeT{} >> 2;
+}
+
+template <size_t kSizeOfSizeT = sizeof(size_t)>
+constexpr size_t MaxSizeAtMaxValidCapacity(size_t slot_size) {
+ return CapacityToGrowth(MaxValidCapacity<kSizeOfSizeT>()) / slot_size;
}
constexpr size_t MaxStorableSize() {
@@ -2325,8 +2329,11 @@
template <size_t kSizeOfSizeT = sizeof(size_t)>
constexpr size_t MaxValidSizeForSlotSize(size_t slot_size) {
if constexpr (kSizeOfSizeT == 8) {
- // For small slot sizes we are limited by HashtableStackData::kSizeBitCount.
- if (slot_size < size_t{1} << (64 - HashtableInlineData::kSizeBitCount)) {
+ // For small slot sizes we are limited by
+ // HashtableInlineData::kSizeBitCount.
+ constexpr size_t kMaxSlotSizeForMaxStorableSize =
+ CapacityToGrowth(MaxValidCapacity<kSizeOfSizeT>()) / MaxStorableSize();
+ if (ABSL_PREDICT_TRUE(slot_size <= kMaxSlotSizeForMaxStorableSize)) {
return MaxStorableSize();
}
}
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc
index e0a6cb1..32ce635 100644
--- a/absl/container/internal/raw_hash_set_test.cc
+++ b/absl/container/internal/raw_hash_set_test.cc
@@ -5520,6 +5520,7 @@
size_t key_size = slot_size;
size_t max_size = MaxValidSize(key_size, slot_size);
ASSERT_LT(max_size, uint64_t{1} << 60);
+ size_t max_capacity = SizeToCapacity(max_size);
if (key_size <= 4) {
ASSERT_EQ(max_size, uint64_t{1} << 8 * key_size);
} else if (i <= 21) {
@@ -5527,9 +5528,23 @@
ASSERT_GE(max_size,
(uint64_t{1} << HashtableInlineData::kSizeBitCount) - 1);
}
+ ASSERT_LE(max_size, MaxSizeAtMaxValidCapacity(slot_size));
ASSERT_LE(max_size, uint64_t{1} << HashtableInlineData::kSizeBitCount);
ASSERT_LT(absl::uint128(max_size) * slot_size, uint64_t{1} << 63);
+ ASSERT_LT(absl::uint128(max_capacity) * slot_size, uint64_t{1} << 63);
+ if (max_capacity > 0) {
+ RawHashSetLayout layout(max_capacity, slot_size, /*slot_align_mask=*/0,
+ /*has_infoz=*/true,
+ /*blocked_element_count=*/0);
+ ASSERT_GT(layout.alloc_size(), layout.slot_offset());
+ }
}
+ constexpr size_t kThresholdSlotSize =
+ CapacityToGrowth(MaxValidCapacity()) / MaxStorableSize();
+ EXPECT_EQ(MaxValidSize(kThresholdSlotSize, kThresholdSlotSize),
+ MaxStorableSize());
+ EXPECT_LT(MaxValidSize(kThresholdSlotSize + 1, kThresholdSlotSize + 1),
+ MaxStorableSize());
}
EXPECT_LT(MaxValidSize</*kSizeOfSizeT=*/4>(1, 1), 1 << 30);
EXPECT_LT(MaxValidSize</*kSizeOfSizeT=*/4>(2, 2), 1 << 29);