diff options
author | 2019-01-18 07:54:14 -0800 | |
---|---|---|
committer | 2019-01-18 14:05:08 -0500 | |
commit | 0b1e6d417b414aad9282e32e8c49c719edeb63c1 (patch) | |
tree | 249747e061ac3bc4af717a367da8c4a50486dbbe /absl/container/internal/raw_hash_set_test.cc | |
parent | efccc502606bed768e50a6cd5806d8eb13e4e935 (diff) |
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
Diffstat (limited to 'absl/container/internal/raw_hash_set_test.cc')
-rw-r--r-- | absl/container/internal/raw_hash_set_test.cc | 29 |
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 78b62755..d9f1826a 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 = [&]() { |