Introduce BlockedInfo helper class to raw_hash_set.

BlockedInfo is a structure for log2_period and tail_blocked to represent blocked slots in SwissTable. This class provides helper methods to calculate the number of blocked slots before a given index and the total blocked count for a given capacity. Unit tests are also added to verify its behavior.

PiperOrigin-RevId: 958670631
Change-Id: I2fc0e1c98767edb644b7f8d592be194621f26e52

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 0efe8d4..5a4fce8 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -625,6 +625,45 @@
   const IntType seed_;
 };
 
+// Represents blocked elements info: log2_period and tail_blocked.
+// Every `2**log2_period` is a blocked slot. The first blocked slot is at
+// index `2**log2_period-1`. E.g. if log2_period is 2, then every 4th slot
+// is blocked: 0, 1, 2, X, 4, 5, 6, X, ...
+//
+// tail_blocked is the number of blocked slots at the end in addition.
+// E.g., log2_period = 2 and tail_blocked = 3, then there are 6 blocked for
+// capacity = 15.
+// slots: 0, 1, 2, X, 4, 5, 6, X, 8, 9, 10, X, X, X, X, S. (S = sentinel)
+class BlockedInfo {
+ public:
+  constexpr BlockedInfo(uint8_t log2_period, uint8_t tail_blocked)
+      : log2_period_(log2_period), tail_blocked_(tail_blocked) {
+    ABSL_ASSUME(log2_period < 64);
+  }
+
+  // Returns the log2 of the period for blocked elements.
+  // Every `2**K` element is blocked starting from index `2**K - 1`.
+  constexpr uint8_t log2_period() const { return log2_period_; }
+  // Returns the number of blocked elements at the end of the table.
+  constexpr uint8_t tail_blocked() const { return tail_blocked_; }
+
+  // Returns the number of blocked elements before the given index.
+  // Doesn't account for tail_blocked because there are no useful indices in
+  // the blocked tail.
+  constexpr size_t blocked_before(size_t index) const {
+    return index >> log2_period();
+  }
+
+  // Returns the number of blocked elements in the table.
+  constexpr size_t total_blocked_count(size_t capacity) const {
+    return blocked_before(capacity) + tail_blocked();
+  }
+
+ private:
+  uint8_t log2_period_;
+  uint8_t tail_blocked_;
+};
+
 // Capacity, size and also has additionally
 // 1) one bit that stores whether we have infoz.
 // 2) kBlockedElementsBitCount bits that stores number of blocked elements in

absl/container/internal/raw_hash_set_test.cc

diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc
index 059489e..469341e 100644
--- a/absl/container/internal/raw_hash_set_test.cc
+++ b/absl/container/internal/raw_hash_set_test.cc
@@ -252,6 +252,60 @@
 #endif  // defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
 }
 
+TEST(BlockedInfoTest, ConstructFromComponents) {
+  constexpr BlockedInfo info(10, 2);
+  EXPECT_EQ(info.log2_period(), 10);
+  EXPECT_EQ(info.tail_blocked(), 2);
+
+  constexpr BlockedInfo info_zero(0, 0);
+  EXPECT_EQ(info_zero.log2_period(), 0);
+  EXPECT_EQ(info_zero.tail_blocked(), 0);
+
+  constexpr BlockedInfo info_max(63, 3);
+  EXPECT_EQ(info_max.log2_period(), 63);
+  EXPECT_EQ(info_max.tail_blocked(), 3);
+}
+
+TEST(BlockedInfoTest, BlockedBefore) {
+  constexpr BlockedInfo info3(3, 0);
+  EXPECT_EQ(info3.blocked_before(0), 0);
+  EXPECT_EQ(info3.blocked_before(7), 0);
+  EXPECT_EQ(info3.blocked_before(8), 1);
+  EXPECT_EQ(info3.blocked_before(15), 1);
+  EXPECT_EQ(info3.blocked_before(16), 2);
+  EXPECT_EQ(info3.blocked_before(24), 3);
+  EXPECT_EQ(info3.blocked_before(100), 12);
+
+  constexpr BlockedInfo info0(0, 0);
+  EXPECT_EQ(info0.blocked_before(0), 0);
+  EXPECT_EQ(info0.blocked_before(5), 5);
+  EXPECT_EQ(info0.blocked_before(10), 10);
+
+  constexpr BlockedInfo info4(4, 1);
+  EXPECT_EQ(info4.blocked_before(0), 0);
+  EXPECT_EQ(info4.blocked_before(15), 0);
+  EXPECT_EQ(info4.blocked_before(16), 1);
+  EXPECT_EQ(info4.blocked_before(31), 1);
+  EXPECT_EQ(info4.blocked_before(32), 2);
+}
+
+TEST(BlockedInfoTest, TotalBlockedCount) {
+  constexpr BlockedInfo info(3, 2);
+  EXPECT_EQ(info.total_blocked_count(0), 2);
+  EXPECT_EQ(info.total_blocked_count(7), 2);
+  EXPECT_EQ(info.total_blocked_count(8), 3);
+  EXPECT_EQ(info.total_blocked_count(15), 3);
+  EXPECT_EQ(info.total_blocked_count(31), 5);
+
+  constexpr BlockedInfo info_zero(0, 0);
+  EXPECT_EQ(info_zero.total_blocked_count(0), 0);
+  EXPECT_EQ(info_zero.total_blocked_count(15), 15);
+
+  constexpr BlockedInfo info_tail(5, 3);
+  EXPECT_EQ(info_tail.total_blocked_count(31), 3);
+  EXPECT_EQ(info_tail.total_blocked_count(63), 4);
+}
+
 class GrowthInfoAllocator {
  public:
   explicit GrowthInfoAllocator(size_t capacity) {