Export of internal Abseil changes.

--
461c1b6eb19490429db3bc6dd10ee32df9429cd7 by Samuel Benzaquen <sbenza@google.com>:

Group all the capacity/growth calculation in one place.
This helps remove the unnecessary floating point operations.

PiperOrigin-RevId: 229928140
GitOrigin-RevId: 461c1b6eb19490429db3bc6dd10ee32df9429cd7
Change-Id: Ib00f85a6033fcd06a1d38a5987670b1524a80f93

1 files changed, 29 insertions, 0 deletions

diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc
index 78b627556d74..d9f1826a09ca 100644
--- a/absl/container/internal/raw_hash_set_test.cc
+++ b/absl/container/internal/raw_hash_set_test.cc
@@ -48,6 +48,8 @@ namespace {
 
 using ::testing::DoubleNear;
 using ::testing::ElementsAre;
+using ::testing::Ge;
+using ::testing::Lt;
 using ::testing::Optional;
 using ::testing::Pair;
 using ::testing::UnorderedElementsAre;
@@ -62,6 +64,33 @@ TEST(Util, NormalizeCapacity) {
   EXPECT_EQ(kMinCapacity * 2 + 1, NormalizeCapacity(kMinCapacity + 2));
 }
 
+TEST(Util, GrowthAndCapacity) {
+  // Verify that GrowthToCapacity gives the minimum capacity that has enough
+  // growth.
+  for (size_t growth = 0; growth < 10000; ++growth) {
+    SCOPED_TRACE(growth);
+    size_t capacity = NormalizeCapacity(GrowthToLowerboundCapacity(growth));
+    // The capacity is large enough for `growth`
+    EXPECT_THAT(CapacityToGrowth(capacity), Ge(growth));
+    if (growth < Group::kWidth - 1) {
+      // Fits in one group, that is the minimum capacity.
+      EXPECT_EQ(capacity, Group::kWidth - 1);
+    } else {
+      // There is no smaller capacity that works.
+      EXPECT_THAT(CapacityToGrowth(capacity / 2), Lt(growth));
+    }
+  }
+
+  for (size_t capacity = Group::kWidth - 1; capacity < 10000;
+       capacity = 2 * capacity + 1) {
+    SCOPED_TRACE(capacity);
+    size_t growth = CapacityToGrowth(capacity);
+    EXPECT_THAT(growth, Lt(capacity));
+    EXPECT_LE(GrowthToLowerboundCapacity(growth), capacity);
+    EXPECT_EQ(NormalizeCapacity(GrowthToLowerboundCapacity(growth)), capacity);
+  }
+}
+
 TEST(Util, probe_seq) {
   probe_seq<16> seq(0, 127);
   auto gen = [&]() {