| // Copyright 2025 The Abseil Authors |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // https://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| #include "absl/container/internal/hashtable_control_bytes.h" |
| |
| #include <array> |
| #include <cstddef> |
| #include <cstdint> |
| #include <vector> |
| |
| #include "gmock/gmock.h" |
| #include "gtest/gtest.h" |
| #include "absl/base/config.h" |
| |
| namespace absl { |
| ABSL_NAMESPACE_BEGIN |
| namespace container_internal { |
| namespace { |
| |
| using ::testing::ElementsAre; |
| using ::testing::ElementsAreArray; |
| |
| // Convenience function to static cast to ctrl_t. |
| ctrl_t CtrlT(int i) { return static_cast<ctrl_t>(i); } |
| |
| TEST(BitMask, Smoke) { |
| EXPECT_FALSE((BitMask<uint8_t, 8>(0))); |
| EXPECT_TRUE((BitMask<uint8_t, 8>(5))); |
| |
| EXPECT_THAT((BitMask<uint8_t, 8>(0)), ElementsAre()); |
| EXPECT_THAT((BitMask<uint8_t, 8>(0x1)), ElementsAre(0)); |
| EXPECT_THAT((BitMask<uint8_t, 8>(0x2)), ElementsAre(1)); |
| EXPECT_THAT((BitMask<uint8_t, 8>(0x3)), ElementsAre(0, 1)); |
| EXPECT_THAT((BitMask<uint8_t, 8>(0x4)), ElementsAre(2)); |
| EXPECT_THAT((BitMask<uint8_t, 8>(0x5)), ElementsAre(0, 2)); |
| EXPECT_THAT((BitMask<uint8_t, 8>(0x55)), ElementsAre(0, 2, 4, 6)); |
| EXPECT_THAT((BitMask<uint8_t, 8>(0xAA)), ElementsAre(1, 3, 5, 7)); |
| } |
| |
| TEST(BitMask, WithShift_MatchPortable) { |
| // See the non-SSE version of Group for details on what this math is for. |
| uint64_t ctrl = 0x1716151413121110; |
| uint64_t hash = 0x12; |
| constexpr uint64_t lsbs = 0x0101010101010101ULL; |
| auto x = ctrl ^ (lsbs * hash); |
| uint64_t mask = (x - lsbs) & ~x & kMsbs8Bytes; |
| EXPECT_EQ(0x0000000080800000, mask); |
| |
| BitMask<uint64_t, 8, 3> b(mask); |
| EXPECT_EQ(*b, 2); |
| } |
| |
| constexpr uint64_t kSome8BytesMask = /* */ 0x8000808080008000ULL; |
| constexpr uint64_t kSome8BytesMaskAllOnes = 0xff00ffffff00ff00ULL; |
| constexpr auto kSome8BytesMaskBits = std::array<int, 5>{1, 3, 4, 5, 7}; |
| |
| TEST(BitMask, WithShift_FullMask) { |
| EXPECT_THAT((BitMask<uint64_t, 8, 3>(kMsbs8Bytes)), |
| ElementsAre(0, 1, 2, 3, 4, 5, 6, 7)); |
| EXPECT_THAT( |
| (BitMask<uint64_t, 8, 3, /*NullifyBitsOnIteration=*/true>(kMsbs8Bytes)), |
| ElementsAre(0, 1, 2, 3, 4, 5, 6, 7)); |
| EXPECT_THAT( |
| (BitMask<uint64_t, 8, 3, /*NullifyBitsOnIteration=*/true>(~uint64_t{0})), |
| ElementsAre(0, 1, 2, 3, 4, 5, 6, 7)); |
| } |
| |
| TEST(BitMask, WithShift_EmptyMask) { |
| EXPECT_THAT((BitMask<uint64_t, 8, 3>(0)), ElementsAre()); |
| EXPECT_THAT((BitMask<uint64_t, 8, 3, /*NullifyBitsOnIteration=*/true>(0)), |
| ElementsAre()); |
| } |
| |
| TEST(BitMask, WithShift_SomeMask) { |
| EXPECT_THAT((BitMask<uint64_t, 8, 3>(kSome8BytesMask)), |
| ElementsAreArray(kSome8BytesMaskBits)); |
| EXPECT_THAT((BitMask<uint64_t, 8, 3, /*NullifyBitsOnIteration=*/true>( |
| kSome8BytesMask)), |
| ElementsAreArray(kSome8BytesMaskBits)); |
| EXPECT_THAT((BitMask<uint64_t, 8, 3, /*NullifyBitsOnIteration=*/true>( |
| kSome8BytesMaskAllOnes)), |
| ElementsAreArray(kSome8BytesMaskBits)); |
| } |
| |
| TEST(BitMask, WithShift_SomeMaskExtraBitsForNullify) { |
| // Verify that adding extra bits into non zero bytes is fine. |
| uint64_t extra_bits = 77; |
| for (int i = 0; i < 100; ++i) { |
| // Add extra bits, but keep zero bytes untouched. |
| uint64_t extra_mask = extra_bits & kSome8BytesMaskAllOnes; |
| EXPECT_THAT((BitMask<uint64_t, 8, 3, /*NullifyBitsOnIteration=*/true>( |
| kSome8BytesMask | extra_mask)), |
| ElementsAreArray(kSome8BytesMaskBits)) |
| << i << " " << extra_mask; |
| extra_bits = (extra_bits + 1) * 3; |
| } |
| } |
| |
| TEST(BitMask, LeadingTrailing) { |
| EXPECT_EQ((BitMask<uint32_t, 16>(0x00001a40).LeadingZeros()), 3); |
| EXPECT_EQ((BitMask<uint32_t, 16>(0x00001a40).TrailingZeros()), 6); |
| |
| EXPECT_EQ((BitMask<uint32_t, 16>(0x00000001).LeadingZeros()), 15); |
| EXPECT_EQ((BitMask<uint32_t, 16>(0x00000001).TrailingZeros()), 0); |
| |
| EXPECT_EQ((BitMask<uint32_t, 16>(0x00008000).LeadingZeros()), 0); |
| EXPECT_EQ((BitMask<uint32_t, 16>(0x00008000).TrailingZeros()), 15); |
| |
| EXPECT_EQ((BitMask<uint64_t, 8, 3>(0x0000008080808000).LeadingZeros()), 3); |
| EXPECT_EQ((BitMask<uint64_t, 8, 3>(0x0000008080808000).TrailingZeros()), 1); |
| |
| EXPECT_EQ((BitMask<uint64_t, 8, 3>(0x0000000000000080).LeadingZeros()), 7); |
| EXPECT_EQ((BitMask<uint64_t, 8, 3>(0x0000000000000080).TrailingZeros()), 0); |
| |
| EXPECT_EQ((BitMask<uint64_t, 8, 3>(0x8000000000000000).LeadingZeros()), 0); |
| EXPECT_EQ((BitMask<uint64_t, 8, 3>(0x8000000000000000).TrailingZeros()), 7); |
| } |
| |
| template <class GroupTypeParam> |
| class GroupTest : public testing::Test {}; |
| using GroupTypes = |
| ::testing::Types<Group, GroupPortableImpl, GroupFullEmptyOrDeleted>; |
| TYPED_TEST_SUITE(GroupTest, GroupTypes); |
| |
| TYPED_TEST(GroupTest, Match) { |
| using GroupType = TypeParam; |
| if (GroupType::kWidth == 16) { |
| ctrl_t group[] = {ctrl_t::kEmpty, CtrlT(1), ctrl_t::kDeleted, CtrlT(3), |
| ctrl_t::kEmpty, CtrlT(5), ctrl_t::kSentinel, CtrlT(7), |
| CtrlT(7), CtrlT(5), CtrlT(3), CtrlT(1), |
| CtrlT(1), CtrlT(1), CtrlT(1), CtrlT(1)}; |
| EXPECT_THAT(GroupType{group}.Match(0), ElementsAre()); |
| EXPECT_THAT(GroupType{group}.Match(1), ElementsAre(1, 11, 12, 13, 14, 15)); |
| EXPECT_THAT(GroupType{group}.Match(3), ElementsAre(3, 10)); |
| EXPECT_THAT(GroupType{group}.Match(5), ElementsAre(5, 9)); |
| EXPECT_THAT(GroupType{group}.Match(7), ElementsAre(7, 8)); |
| } else if (GroupType::kWidth == 8) { |
| ctrl_t group[] = {ctrl_t::kEmpty, CtrlT(1), CtrlT(2), |
| ctrl_t::kDeleted, CtrlT(2), CtrlT(1), |
| ctrl_t::kSentinel, CtrlT(1)}; |
| EXPECT_THAT(GroupType{group}.Match(0), ElementsAre()); |
| EXPECT_THAT(GroupType{group}.Match(1), ElementsAre(1, 5, 7)); |
| EXPECT_THAT(GroupType{group}.Match(2), ElementsAre(2, 4)); |
| } else { |
| FAIL() << "No test coverage for Group::kWidth==" << GroupType::kWidth; |
| } |
| } |
| |
| TYPED_TEST(GroupTest, MaskEmpty) { |
| using GroupType = TypeParam; |
| if (GroupType::kWidth == 16) { |
| ctrl_t group[] = {ctrl_t::kEmpty, CtrlT(1), ctrl_t::kDeleted, CtrlT(3), |
| ctrl_t::kEmpty, CtrlT(5), ctrl_t::kSentinel, CtrlT(7), |
| CtrlT(7), CtrlT(5), CtrlT(3), CtrlT(1), |
| CtrlT(1), CtrlT(1), CtrlT(1), CtrlT(1)}; |
| EXPECT_THAT(GroupType{group}.MaskEmpty().LowestBitSet(), 0); |
| } else if (GroupType::kWidth == 8) { |
| ctrl_t group[] = {ctrl_t::kEmpty, CtrlT(1), CtrlT(2), |
| ctrl_t::kDeleted, CtrlT(2), CtrlT(1), |
| ctrl_t::kSentinel, CtrlT(1)}; |
| EXPECT_THAT(GroupType{group}.MaskEmpty().LowestBitSet(), 0); |
| } else { |
| FAIL() << "No test coverage for Group::kWidth==" << GroupType::kWidth; |
| } |
| } |
| |
| TYPED_TEST(GroupTest, MaskFull) { |
| using GroupType = TypeParam; |
| if (GroupType::kWidth == 16) { |
| ctrl_t group[] = { |
| ctrl_t::kEmpty, CtrlT(1), ctrl_t::kDeleted, CtrlT(3), |
| ctrl_t::kEmpty, CtrlT(5), ctrl_t::kSentinel, CtrlT(7), |
| CtrlT(7), CtrlT(5), ctrl_t::kDeleted, CtrlT(1), |
| CtrlT(1), ctrl_t::kSentinel, ctrl_t::kEmpty, CtrlT(1)}; |
| EXPECT_THAT(GroupType{group}.MaskFull(), |
| ElementsAre(1, 3, 5, 7, 8, 9, 11, 12, 15)); |
| } else if (GroupType::kWidth == 8) { |
| ctrl_t group[] = {ctrl_t::kEmpty, CtrlT(1), ctrl_t::kEmpty, |
| ctrl_t::kDeleted, CtrlT(2), ctrl_t::kSentinel, |
| ctrl_t::kSentinel, CtrlT(1)}; |
| EXPECT_THAT(GroupType{group}.MaskFull(), ElementsAre(1, 4, 7)); |
| } else { |
| FAIL() << "No test coverage for Group::kWidth==" << GroupType::kWidth; |
| } |
| } |
| |
| TYPED_TEST(GroupTest, MaskNonFull) { |
| using GroupType = TypeParam; |
| if (GroupType::kWidth == 16) { |
| ctrl_t group[] = { |
| ctrl_t::kEmpty, CtrlT(1), ctrl_t::kDeleted, CtrlT(3), |
| ctrl_t::kEmpty, CtrlT(5), ctrl_t::kSentinel, CtrlT(7), |
| CtrlT(7), CtrlT(5), ctrl_t::kDeleted, CtrlT(1), |
| CtrlT(1), ctrl_t::kSentinel, ctrl_t::kEmpty, CtrlT(1)}; |
| EXPECT_THAT(GroupType{group}.MaskNonFull(), |
| ElementsAre(0, 2, 4, 6, 10, 13, 14)); |
| } else if (GroupType::kWidth == 8) { |
| ctrl_t group[] = {ctrl_t::kEmpty, CtrlT(1), ctrl_t::kEmpty, |
| ctrl_t::kDeleted, CtrlT(2), ctrl_t::kSentinel, |
| ctrl_t::kSentinel, CtrlT(1)}; |
| EXPECT_THAT(GroupType{group}.MaskNonFull(), ElementsAre(0, 2, 3, 5, 6)); |
| } else { |
| FAIL() << "No test coverage for Group::kWidth==" << GroupType::kWidth; |
| } |
| } |
| |
| TYPED_TEST(GroupTest, MaskEmptyOrDeleted) { |
| using GroupType = TypeParam; |
| if (GroupType::kWidth == 16) { |
| ctrl_t group[] = {ctrl_t::kEmpty, CtrlT(1), ctrl_t::kEmpty, CtrlT(3), |
| ctrl_t::kDeleted, CtrlT(5), ctrl_t::kSentinel, CtrlT(7), |
| CtrlT(7), CtrlT(5), CtrlT(3), CtrlT(1), |
| CtrlT(1), CtrlT(1), CtrlT(1), CtrlT(1)}; |
| EXPECT_THAT(GroupType{group}.MaskEmptyOrDeleted().LowestBitSet(), 0); |
| } else if (GroupType::kWidth == 8) { |
| ctrl_t group[] = {ctrl_t::kEmpty, CtrlT(1), CtrlT(2), |
| ctrl_t::kDeleted, CtrlT(2), CtrlT(1), |
| ctrl_t::kSentinel, CtrlT(1)}; |
| EXPECT_THAT(GroupType{group}.MaskEmptyOrDeleted().LowestBitSet(), 0); |
| } else { |
| FAIL() << "No test coverage for Group::kWidth==" << GroupType::kWidth; |
| } |
| } |
| |
| TYPED_TEST(GroupTest, MaskFullOrSentinel) { |
| using GroupType = TypeParam; |
| if (GroupType::kWidth == 16) { |
| ctrl_t group[] = { |
| ctrl_t::kEmpty, ctrl_t::kDeleted, ctrl_t::kEmpty, CtrlT(3), |
| ctrl_t::kDeleted, CtrlT(5), ctrl_t::kSentinel, ctrl_t::kEmpty, |
| ctrl_t::kEmpty, ctrl_t::kDeleted, ctrl_t::kDeleted, ctrl_t::kDeleted, |
| ctrl_t::kEmpty, ctrl_t::kDeleted, ctrl_t::kDeleted, ctrl_t::kDeleted, |
| }; |
| EXPECT_THAT(GroupType{group}.MaskFullOrSentinel().LowestBitSet(), 3); |
| } else if (GroupType::kWidth == 8) { |
| ctrl_t group[] = {ctrl_t::kEmpty, ctrl_t::kDeleted, CtrlT(2), |
| ctrl_t::kDeleted, CtrlT(2), ctrl_t::kSentinel, |
| ctrl_t::kDeleted, ctrl_t::kEmpty}; |
| EXPECT_THAT(GroupType{group}.MaskFullOrSentinel().LowestBitSet(), 2); |
| } else { |
| FAIL() << "No test coverage for Group::kWidth==" << GroupType::kWidth; |
| } |
| } |
| |
| } // namespace |
| } // namespace container_internal |
| ABSL_NAMESPACE_END |
| } // namespace absl |
