| /** |
| * Copyright 2011-2015 Quickstep Technologies LLC. |
| * Copyright 2015 Pivotal Software, Inc. |
| * |
| * 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 |
| * |
| * http://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 <cstddef> |
| #include <cstdint> |
| #include <cstdlib> |
| #include <memory> |
| #include <vector> |
| |
| #include "utility/BitVector.hpp" |
| |
| #include "gtest/gtest.h" |
| |
| using std::free; |
| using std::malloc; |
| using std::size_t; |
| using std::uint8_t; |
| using std::uint16_t; |
| using std::uint32_t; |
| using std::vector; |
| |
| namespace quickstep { |
| |
| template <typename BitVectorType> |
| class BitVectorTest : public ::testing::Test { |
| protected: |
| virtual void TearDown() { |
| for (vector<void*>::iterator it = allocated_chunks_.begin(); |
| it != allocated_chunks_.end(); |
| ++it) { |
| free(*it); |
| } |
| allocated_chunks_.clear(); |
| } |
| |
| BitVectorType* createBitVector(const size_t bit_size) { |
| void *bytes = malloc(BitVectorType::BytesNeeded(bit_size)); |
| allocated_chunks_.push_back(bytes); |
| return new BitVectorType(bytes, bit_size); |
| } |
| |
| void runClearTest(const size_t bit_size) { |
| std::unique_ptr<BitVectorType> bit_vector(createBitVector(bit_size)); |
| bit_vector->clear(); |
| for (size_t i = 0; i < bit_size; ++i) { |
| EXPECT_FALSE(bit_vector->getBit(i)); |
| } |
| EXPECT_EQ(0u, bit_vector->onesCount()); |
| EXPECT_EQ(0u, bit_vector->firstZero()); |
| EXPECT_EQ(bit_size / 2, bit_vector->firstZero(bit_size / 2)); |
| EXPECT_EQ(bit_size - 1, bit_vector->lastZero()); |
| EXPECT_EQ((bit_size / 2) - 1, bit_vector->lastZero(bit_size / 2)); |
| EXPECT_EQ(bit_size, bit_vector->firstOne()); |
| EXPECT_EQ(bit_size, bit_vector->firstOne(bit_size / 2)); |
| EXPECT_EQ(bit_size, bit_vector->lastOne()); |
| EXPECT_EQ(bit_size, bit_vector->lastOne(bit_size / 2)); |
| } |
| |
| void runFlipBitsTest(const size_t bit_size) { |
| std::unique_ptr<BitVectorType> bit_vector(createBitVector(bit_size)); |
| bit_vector->clear(); |
| |
| bit_vector->setBit(0, true); |
| bit_vector->setBit(bit_size / 2, true); |
| bit_vector->setBit(bit_size - 1, true); |
| bit_vector->flipBits(); |
| |
| for (size_t i = 0; i < bit_size; ++i) { |
| if ((i == 0) || (i == bit_size / 2) || (i == bit_size - 1)) { |
| EXPECT_FALSE(bit_vector->getBit(i)); |
| } else { |
| EXPECT_TRUE(bit_vector->getBit(i)); |
| } |
| } |
| |
| EXPECT_EQ(bit_size - 3, bit_vector->onesCount()); |
| |
| EXPECT_EQ(0u, bit_vector->firstZero()); |
| EXPECT_EQ(bit_size / 2, bit_vector->firstZero(1)); |
| EXPECT_EQ(bit_size - 1, bit_vector->firstZero((bit_size / 2) + 1)); |
| |
| EXPECT_EQ(1u, bit_vector->firstOne()); |
| EXPECT_EQ(2u, bit_vector->firstOne(2)); |
| EXPECT_EQ((bit_size / 2) + 1, bit_vector->firstOne(bit_size / 2)); |
| EXPECT_EQ(bit_size, bit_vector->firstOne(bit_size - 1)); |
| |
| EXPECT_EQ(bit_size - 1, bit_vector->lastZero()); |
| EXPECT_EQ(bit_size / 2, bit_vector->lastZero(bit_size - 1)); |
| EXPECT_EQ(0u, bit_vector->lastZero(bit_size / 2)); |
| |
| EXPECT_EQ(bit_size - 2, bit_vector->lastOne()); |
| EXPECT_EQ(bit_size - 3, bit_vector->lastOne(bit_size - 2)); |
| EXPECT_EQ((bit_size / 2) - 1, bit_vector->lastOne(bit_size / 2)); |
| EXPECT_EQ(bit_size, bit_vector->lastOne(1)); |
| } |
| |
| void runIntersectWithTest(const size_t bit_size) { |
| std::unique_ptr<BitVectorType> bit_vector(createBitVector(bit_size)); |
| bit_vector->clear(); |
| bit_vector->setBit(0, true); |
| bit_vector->setBit(bit_size / 2, true); |
| bit_vector->setBit(bit_size - 1, true); |
| |
| std::unique_ptr<BitVectorType> other_bit_vector(createBitVector(bit_size)); |
| other_bit_vector->clear(); |
| other_bit_vector->setBit(1, true); |
| other_bit_vector->setBit(bit_size / 2, true); |
| other_bit_vector->setBit(bit_size - 2, true); |
| |
| bit_vector->intersectWith(*other_bit_vector); |
| |
| for (size_t i = 0; i < bit_size; ++i) { |
| if (i == bit_size / 2) { |
| EXPECT_TRUE(bit_vector->getBit(i)); |
| } else { |
| EXPECT_FALSE(bit_vector->getBit(i)); |
| } |
| } |
| |
| // '*other_bit_vector' should be unmodified |
| for (size_t i = 0; i < bit_size; ++i) { |
| if ((i == 1) || (i == bit_size / 2) || (i == bit_size - 2)) { |
| EXPECT_TRUE(other_bit_vector->getBit(i)); |
| } else { |
| EXPECT_FALSE(other_bit_vector->getBit(i)); |
| } |
| } |
| } |
| |
| void runUnionWithTest(const size_t bit_size) { |
| std::unique_ptr<BitVectorType> bit_vector(createBitVector(bit_size)); |
| bit_vector->clear(); |
| bit_vector->setBit(0, true); |
| bit_vector->setBit(bit_size / 2, true); |
| bit_vector->setBit(bit_size - 1, true); |
| |
| std::unique_ptr<BitVectorType> other_bit_vector(createBitVector(bit_size)); |
| other_bit_vector->clear(); |
| other_bit_vector->setBit(1, true); |
| other_bit_vector->setBit(bit_size / 2, true); |
| other_bit_vector->setBit(bit_size - 2, true); |
| |
| bit_vector->unionWith(*other_bit_vector); |
| |
| for (size_t i = 0; i < bit_size; ++i) { |
| if ((i == 0) || (i == 1) || (i == bit_size / 2) |
| || (i == bit_size - 2) || (i == bit_size - 1)) { |
| EXPECT_TRUE(bit_vector->getBit(i)); |
| } else { |
| EXPECT_FALSE(bit_vector->getBit(i)); |
| } |
| } |
| |
| // '*other_bit_vector' should be unmodified |
| for (size_t i = 0; i < bit_size; ++i) { |
| if ((i == 1) || (i == bit_size / 2) || (i == bit_size - 2)) { |
| EXPECT_TRUE(other_bit_vector->getBit(i)); |
| } else { |
| EXPECT_FALSE(other_bit_vector->getBit(i)); |
| } |
| } |
| } |
| |
| void runZeroLengthTest(BitVectorType *bit_vector) { |
| BitVectorType other_zero_length_bit_vector(0); |
| |
| // Check initial metadata. |
| CheckZeroLengthMetaData(*bit_vector); |
| |
| // Do some no-op modifying operations and recheck metadata after each. |
| bit_vector->clear(); |
| CheckZeroLengthMetaData(*bit_vector); |
| bit_vector->flipBits(); |
| CheckZeroLengthMetaData(*bit_vector); |
| |
| // Some compilers may aggressively propagate constants through inlined |
| // functions (especially for RELEASE builds), eventually resulting in a |
| // call to std::memset() with a constant zero-length parameter |
| // (effectively a no-op). Some C standard library implementations |
| // (including glibc) have memset declared with an attribute to warn about a |
| // constant zero for the length parameter. Storing the zero-length constant |
| // in a variable marked volatile prevents constant propagation and |
| // supresses warnings for memset() when we intentionally test |
| // BitVector::setBitRange() with length 0. |
| const volatile std::size_t kZeroLen = 0; |
| bit_vector->setBitRange(0, kZeroLen, false); |
| CheckZeroLengthMetaData(*bit_vector); |
| bit_vector->setBitRange(0, kZeroLen, true); |
| CheckZeroLengthMetaData(*bit_vector); |
| bit_vector->assignFrom(other_zero_length_bit_vector); |
| CheckZeroLengthMetaData(*bit_vector); |
| bit_vector->intersectWith(other_zero_length_bit_vector); |
| CheckZeroLengthMetaData(*bit_vector); |
| bit_vector->unionWith(other_zero_length_bit_vector); |
| CheckZeroLengthMetaData(*bit_vector); |
| } |
| |
| static void CheckZeroLengthMetaData(const BitVectorType &bit_vector) { |
| EXPECT_EQ(0u, bit_vector.size()); |
| EXPECT_FALSE(bit_vector.any()); |
| EXPECT_TRUE(bit_vector.all()); |
| EXPECT_EQ(0u, bit_vector.onesCount()); |
| EXPECT_EQ(0u, bit_vector.firstOne()); |
| EXPECT_EQ(0u, bit_vector.firstZero()); |
| EXPECT_EQ(0u, bit_vector.lastOne()); |
| EXPECT_EQ(0u, bit_vector.lastZero()); |
| } |
| |
| static const size_t kSmallBitSize = 8; |
| static const size_t kBigBitSize = 160; |
| static const size_t kBiggerBitSize = 1024; |
| vector<void*> allocated_chunks_; |
| }; |
| |
| typedef ::testing::Types<BitVector<false>, BitVector<true>> TestTypes; |
| TYPED_TEST_CASE(BitVectorTest, TestTypes); |
| |
| // Static const members must be defined out-of-line to work with EXPECT_* |
| // macros. |
| template <typename BitVectorType> const size_t BitVectorTest<BitVectorType>::kSmallBitSize; |
| template <typename BitVectorType> const size_t BitVectorTest<BitVectorType>::kBigBitSize; |
| template <typename BitVectorType> const size_t BitVectorTest<BitVectorType>::kBiggerBitSize; |
| |
| TYPED_TEST(BitVectorTest, BytesNeededTest) { |
| if (TypeParam::kShortVersionEnabled) { |
| EXPECT_EQ(sizeof(uint8_t), TypeParam::BytesNeeded(7)); |
| EXPECT_EQ(sizeof(uint8_t), TypeParam::BytesNeeded(8)); |
| EXPECT_EQ(sizeof(uint16_t), TypeParam::BytesNeeded(9)); |
| EXPECT_EQ(sizeof(uint16_t), TypeParam::BytesNeeded(15)); |
| EXPECT_EQ(sizeof(uint16_t), TypeParam::BytesNeeded(16)); |
| EXPECT_EQ(sizeof(uint32_t), TypeParam::BytesNeeded(17)); |
| EXPECT_EQ(sizeof(uint32_t), TypeParam::BytesNeeded(31)); |
| EXPECT_EQ(sizeof(uint32_t), TypeParam::BytesNeeded(32)); |
| } else { |
| EXPECT_EQ(sizeof(size_t), TypeParam::BytesNeeded(7)); |
| EXPECT_EQ(sizeof(size_t), TypeParam::BytesNeeded(8)); |
| EXPECT_EQ(sizeof(size_t), TypeParam::BytesNeeded(9)); |
| EXPECT_EQ(sizeof(size_t), TypeParam::BytesNeeded(15)); |
| EXPECT_EQ(sizeof(size_t), TypeParam::BytesNeeded(16)); |
| EXPECT_EQ(sizeof(size_t), TypeParam::BytesNeeded(17)); |
| EXPECT_EQ(sizeof(size_t), TypeParam::BytesNeeded(31)); |
| EXPECT_EQ(sizeof(size_t), TypeParam::BytesNeeded(32)); |
| } |
| |
| if (sizeof(size_t) == 4) { |
| // 32-bit build. |
| EXPECT_EQ(sizeof(size_t) * 2, TypeParam::BytesNeeded(33)); |
| EXPECT_EQ(sizeof(size_t) * 2, TypeParam::BytesNeeded(63)); |
| EXPECT_EQ(sizeof(size_t) * 2, TypeParam::BytesNeeded(64)); |
| EXPECT_EQ(sizeof(size_t) * 3, TypeParam::BytesNeeded(65)); |
| } else if (sizeof(size_t) == 8) { |
| // 64-bit build. |
| EXPECT_EQ(sizeof(size_t), TypeParam::BytesNeeded(33)); |
| EXPECT_EQ(sizeof(size_t), TypeParam::BytesNeeded(63)); |
| EXPECT_EQ(sizeof(size_t), TypeParam::BytesNeeded(64)); |
| EXPECT_EQ(sizeof(size_t) * 2, TypeParam::BytesNeeded(65)); |
| } else { |
| // The exotic far future. |
| } |
| } |
| |
| TYPED_TEST(BitVectorTest, ByteClearTest) { |
| TestFixture::runClearTest(7); |
| TestFixture::runClearTest(8); |
| } |
| |
| TYPED_TEST(BitVectorTest, ShortClearTest) { |
| TestFixture::runClearTest(9); |
| TestFixture::runClearTest(15); |
| TestFixture::runClearTest(16); |
| } |
| |
| TYPED_TEST(BitVectorTest, WordClearTest) { |
| TestFixture::runClearTest(17); |
| TestFixture::runClearTest(31); |
| TestFixture::runClearTest(32); |
| } |
| |
| TYPED_TEST(BitVectorTest, RegularClearTest) { |
| TestFixture::runClearTest(33); |
| TestFixture::runClearTest(63); |
| TestFixture::runClearTest(64); |
| TestFixture::runClearTest(65); |
| TestFixture::runClearTest(200); |
| } |
| |
| TYPED_TEST(BitVectorTest, SetAndGetTest) { |
| std::unique_ptr<TypeParam> small_bit_vector(this->createBitVector(TestFixture::kSmallBitSize)); |
| small_bit_vector->clear(); |
| |
| small_bit_vector->setBit(2, true); |
| small_bit_vector->setBit(3, true); |
| small_bit_vector->setBit(4, true); |
| small_bit_vector->setBit(3, false); |
| |
| for (size_t i = 0; i < TestFixture::kSmallBitSize; ++i) { |
| if ((i == 2) || (i == 4)) { |
| EXPECT_TRUE(small_bit_vector->getBit(i)); |
| } else { |
| EXPECT_FALSE(small_bit_vector->getBit(i)); |
| } |
| } |
| EXPECT_EQ(2u, small_bit_vector->onesCount()); |
| EXPECT_EQ(0u, small_bit_vector->firstZero()); |
| EXPECT_EQ(1u, small_bit_vector->firstZero(1)); |
| EXPECT_EQ(3u, small_bit_vector->firstZero(2)); |
| EXPECT_EQ(2u, small_bit_vector->firstOne()); |
| EXPECT_EQ(2u, small_bit_vector->firstOne(2)); |
| EXPECT_EQ(4u, small_bit_vector->firstOne(3)); |
| EXPECT_EQ(TestFixture::kSmallBitSize - 1, small_bit_vector->lastZero()); |
| EXPECT_EQ(0u, small_bit_vector->lastZero(1)); |
| EXPECT_EQ(1u, small_bit_vector->lastZero(3)); |
| EXPECT_EQ(3u, small_bit_vector->lastZero(4)); |
| EXPECT_EQ(4u, small_bit_vector->lastOne()); |
| EXPECT_EQ(TestFixture::kSmallBitSize, small_bit_vector->lastOne(2)); |
| EXPECT_EQ(2u, small_bit_vector->lastOne(3)); |
| |
| // Set all the bits. |
| for (size_t i = 0; i < TestFixture::kSmallBitSize; ++i) { |
| small_bit_vector->setBit(i, true); |
| } |
| EXPECT_EQ(TestFixture::kSmallBitSize, small_bit_vector->onesCount()); |
| EXPECT_EQ(TestFixture::kSmallBitSize, small_bit_vector->firstZero()); |
| EXPECT_EQ(0u, small_bit_vector->firstOne()); |
| EXPECT_EQ(TestFixture::kSmallBitSize / 2, |
| small_bit_vector->firstOne(TestFixture::kSmallBitSize / 2)); |
| EXPECT_EQ(TestFixture::kSmallBitSize, small_bit_vector->lastZero()); |
| EXPECT_EQ(TestFixture::kSmallBitSize - 1, small_bit_vector->lastOne()); |
| EXPECT_EQ((TestFixture::kSmallBitSize / 2) - 1, |
| small_bit_vector->lastOne(TestFixture::kSmallBitSize / 2)); |
| for (size_t i = 0; i < TestFixture::kSmallBitSize; ++i) { |
| EXPECT_TRUE(small_bit_vector->getBit(i)); |
| EXPECT_EQ(i, small_bit_vector->firstOne(i)); |
| if (i > 0) { |
| EXPECT_EQ(i - 1, small_bit_vector->lastOne(i)); |
| } |
| } |
| |
| |
| std::unique_ptr<TypeParam> big_bit_vector(this->createBitVector(TestFixture::kBigBitSize)); |
| big_bit_vector->clear(); |
| |
| // Set some bits, particularly around potential boundaries between size_t strides. |
| big_bit_vector->setBit(0, true); |
| big_bit_vector->setBit(5, true); |
| big_bit_vector->setBit(31, true); |
| big_bit_vector->setBit(32, true); |
| big_bit_vector->setBit(63, true); |
| big_bit_vector->setBit(64, true); |
| big_bit_vector->setBit(127, true); |
| big_bit_vector->setBit(128, true); |
| |
| for (size_t i = 0; i < TestFixture::kBigBitSize; ++i) { |
| if ((i == 0) || (i == 5) || (i == 31) || (i == 32) || (i == 63) || (i == 64) || (i == 127) || (i == 128)) { |
| EXPECT_TRUE(big_bit_vector->getBit(i)); |
| } else { |
| EXPECT_FALSE(big_bit_vector->getBit(i)); |
| } |
| } |
| EXPECT_EQ(8u, big_bit_vector->onesCount()); |
| EXPECT_EQ(1u, big_bit_vector->firstZero()); |
| EXPECT_EQ(2u, big_bit_vector->firstZero(2)); |
| EXPECT_EQ(0u, big_bit_vector->firstOne()); |
| EXPECT_EQ(5u, big_bit_vector->firstOne(1)); |
| EXPECT_EQ(TestFixture::kBigBitSize - 1, big_bit_vector->lastZero()); |
| EXPECT_EQ(126u, big_bit_vector->lastZero(129)); |
| EXPECT_EQ(TestFixture::kBigBitSize, big_bit_vector->lastZero(1)); |
| EXPECT_EQ(128u, big_bit_vector->lastOne()); |
| EXPECT_EQ(127u, big_bit_vector->lastOne(128)); |
| EXPECT_EQ(64u, big_bit_vector->lastOne(127)); |
| |
| // Unset bits and make sure things still look right. |
| // TODO(chasseur): More checks for lastZero() and lastOne(). |
| big_bit_vector->setBit(0, false); |
| EXPECT_EQ(7u, big_bit_vector->onesCount()); |
| EXPECT_EQ(0u, big_bit_vector->firstZero()); |
| EXPECT_EQ(1u, big_bit_vector->firstZero(1)); |
| EXPECT_EQ(6u, big_bit_vector->firstZero(5)); |
| EXPECT_EQ(5u, big_bit_vector->firstOne()); |
| EXPECT_EQ(31u, big_bit_vector->firstOne(6)); |
| |
| big_bit_vector->setBit(5, false); |
| EXPECT_EQ(6u, big_bit_vector->onesCount()); |
| EXPECT_EQ(0u, big_bit_vector->firstZero()); |
| EXPECT_EQ(1u, big_bit_vector->firstZero(1)); |
| EXPECT_EQ(33u, big_bit_vector->firstZero(31)); |
| EXPECT_EQ(31u, big_bit_vector->firstOne()); |
| EXPECT_EQ(32u, big_bit_vector->firstOne(32)); |
| |
| big_bit_vector->setBit(31, false); |
| EXPECT_EQ(5u, big_bit_vector->onesCount()); |
| EXPECT_EQ(0u, big_bit_vector->firstZero()); |
| EXPECT_EQ(1u, big_bit_vector->firstZero(1)); |
| EXPECT_EQ(33u, big_bit_vector->firstZero(32)); |
| EXPECT_EQ(32u, big_bit_vector->firstOne()); |
| EXPECT_EQ(63u, big_bit_vector->firstOne(33)); |
| |
| big_bit_vector->setBit(32, false); |
| EXPECT_EQ(4u, big_bit_vector->onesCount()); |
| EXPECT_EQ(0u, big_bit_vector->firstZero()); |
| EXPECT_EQ(1u, big_bit_vector->firstZero(1)); |
| EXPECT_EQ(65u, big_bit_vector->firstZero(63)); |
| EXPECT_EQ(63u, big_bit_vector->firstOne()); |
| EXPECT_EQ(64u, big_bit_vector->firstOne(64)); |
| |
| big_bit_vector->setBit(63, false); |
| EXPECT_EQ(3u, big_bit_vector->onesCount()); |
| EXPECT_EQ(0u, big_bit_vector->firstZero()); |
| EXPECT_EQ(1u, big_bit_vector->firstZero(1)); |
| EXPECT_EQ(65u, big_bit_vector->firstZero(64)); |
| EXPECT_EQ(64u, big_bit_vector->firstOne()); |
| EXPECT_EQ(127u, big_bit_vector->firstOne(65)); |
| |
| big_bit_vector->setBit(64, false); |
| EXPECT_EQ(2u, big_bit_vector->onesCount()); |
| EXPECT_EQ(0u, big_bit_vector->firstZero()); |
| EXPECT_EQ(1u, big_bit_vector->firstZero(1)); |
| EXPECT_EQ(129u, big_bit_vector->firstZero(127)); |
| EXPECT_EQ(127u, big_bit_vector->firstOne()); |
| EXPECT_EQ(128u, big_bit_vector->firstOne(128)); |
| |
| big_bit_vector->setBit(127, false); |
| EXPECT_EQ(1u, big_bit_vector->onesCount()); |
| EXPECT_EQ(0u, big_bit_vector->firstZero()); |
| EXPECT_EQ(1u, big_bit_vector->firstZero(1)); |
| EXPECT_EQ(129u, big_bit_vector->firstZero(128)); |
| EXPECT_EQ(128u, big_bit_vector->firstOne()); |
| EXPECT_EQ(TestFixture::kBigBitSize, big_bit_vector->firstOne(129)); |
| |
| big_bit_vector->setBit(128, false); |
| EXPECT_EQ(0u, big_bit_vector->onesCount()); |
| EXPECT_EQ(0u, big_bit_vector->firstZero()); |
| EXPECT_EQ(TestFixture::kBigBitSize, big_bit_vector->firstOne()); |
| |
| for (size_t i = 0; i < TestFixture::kBigBitSize; ++i) { |
| EXPECT_FALSE(big_bit_vector->getBit(i)); |
| } |
| |
| // Set all the bits. |
| for (size_t i = 0; i < TestFixture::kBigBitSize; ++i) { |
| big_bit_vector->setBit(i, true); |
| } |
| EXPECT_EQ(TestFixture::kBigBitSize, big_bit_vector->onesCount()); |
| EXPECT_EQ(TestFixture::kBigBitSize, big_bit_vector->firstZero()); |
| EXPECT_EQ(TestFixture::kBigBitSize, big_bit_vector->firstZero(TestFixture::kBigBitSize / 2)); |
| EXPECT_EQ(0u, big_bit_vector->firstOne()); |
| for (size_t i = 0; i < TestFixture::kBigBitSize; ++i) { |
| EXPECT_TRUE(big_bit_vector->getBit(i)); |
| EXPECT_EQ(i, big_bit_vector->firstOne(i)); |
| EXPECT_EQ(TestFixture::kBigBitSize, big_bit_vector->firstZero(i)); |
| } |
| } |
| |
| TYPED_TEST(BitVectorTest, AssignFromTest) { |
| std::unique_ptr<TypeParam> small_bit_vector(this->createBitVector(TestFixture::kSmallBitSize)); |
| small_bit_vector->clear(); |
| |
| small_bit_vector->setBit(2, true); |
| small_bit_vector->setBit(4, true); |
| |
| std::unique_ptr<TypeParam> small_bit_vector_copy(this->createBitVector(TestFixture::kSmallBitSize)); |
| small_bit_vector_copy->assignFrom(*small_bit_vector); |
| for (size_t i = 0; i < TestFixture::kSmallBitSize; ++i) { |
| if ((i == 2) || (i == 4)) { |
| EXPECT_TRUE(small_bit_vector_copy->getBit(i)); |
| } else { |
| EXPECT_FALSE(small_bit_vector_copy->getBit(i)); |
| } |
| } |
| |
| std::unique_ptr<TypeParam> big_bit_vector(this->createBitVector(TestFixture::kBigBitSize)); |
| big_bit_vector->clear(); |
| |
| big_bit_vector->setBit(2, true); |
| big_bit_vector->setBit(4, true); |
| big_bit_vector->setBit(42, true); |
| big_bit_vector->setBit(77, true); |
| |
| std::unique_ptr<TypeParam> big_bit_vector_copy(this->createBitVector(TestFixture::kBigBitSize)); |
| big_bit_vector_copy->assignFrom(*big_bit_vector); |
| for (size_t i = 0; i < TestFixture::kBigBitSize; ++i) { |
| if ((i == 2) || (i == 4) || (i == 42) || (i == 77)) { |
| EXPECT_TRUE(big_bit_vector_copy->getBit(i)); |
| } else { |
| EXPECT_FALSE(big_bit_vector_copy->getBit(i)); |
| } |
| } |
| } |
| |
| TYPED_TEST(BitVectorTest, ByteFlipBitsTest) { |
| TestFixture::runFlipBitsTest(7); |
| TestFixture::runFlipBitsTest(8); |
| } |
| |
| TYPED_TEST(BitVectorTest, ShortFlipBitsTest) { |
| TestFixture::runFlipBitsTest(9); |
| TestFixture::runFlipBitsTest(15); |
| TestFixture::runFlipBitsTest(16); |
| } |
| |
| TYPED_TEST(BitVectorTest, WordFlipBitsTest) { |
| TestFixture::runFlipBitsTest(17); |
| TestFixture::runFlipBitsTest(31); |
| TestFixture::runFlipBitsTest(32); |
| } |
| |
| TYPED_TEST(BitVectorTest, RegularFlipBitsTest) { |
| TestFixture::runFlipBitsTest(33); |
| TestFixture::runFlipBitsTest(63); |
| TestFixture::runFlipBitsTest(64); |
| TestFixture::runFlipBitsTest(65); |
| TestFixture::runFlipBitsTest(200); |
| } |
| |
| TYPED_TEST(BitVectorTest, ByteIntersectWithTest) { |
| TestFixture::runIntersectWithTest(7); |
| TestFixture::runIntersectWithTest(8); |
| } |
| |
| TYPED_TEST(BitVectorTest, ShortIntersectWithTest) { |
| TestFixture::runIntersectWithTest(9); |
| TestFixture::runIntersectWithTest(15); |
| TestFixture::runIntersectWithTest(16); |
| } |
| |
| TYPED_TEST(BitVectorTest, WordIntersectWithTest) { |
| TestFixture::runIntersectWithTest(17); |
| TestFixture::runIntersectWithTest(31); |
| TestFixture::runIntersectWithTest(32); |
| } |
| |
| TYPED_TEST(BitVectorTest, RegularIntersectWithTest) { |
| TestFixture::runIntersectWithTest(33); |
| TestFixture::runIntersectWithTest(63); |
| TestFixture::runIntersectWithTest(64); |
| TestFixture::runIntersectWithTest(65); |
| TestFixture::runIntersectWithTest(200); |
| } |
| |
| TYPED_TEST(BitVectorTest, ByteUnionWithTest) { |
| TestFixture::runUnionWithTest(7); |
| TestFixture::runUnionWithTest(8); |
| } |
| |
| TYPED_TEST(BitVectorTest, ShortUnionWithTest) { |
| TestFixture::runUnionWithTest(9); |
| TestFixture::runUnionWithTest(15); |
| TestFixture::runUnionWithTest(16); |
| } |
| |
| TYPED_TEST(BitVectorTest, WordUnionWithTest) { |
| TestFixture::runUnionWithTest(17); |
| TestFixture::runUnionWithTest(31); |
| TestFixture::runUnionWithTest(32); |
| } |
| |
| TYPED_TEST(BitVectorTest, RegularUnionWithTest) { |
| TestFixture::runUnionWithTest(33); |
| TestFixture::runUnionWithTest(63); |
| TestFixture::runUnionWithTest(64); |
| TestFixture::runUnionWithTest(65); |
| TestFixture::runUnionWithTest(200); |
| } |
| |
| TYPED_TEST(BitVectorTest, SetBitRangeTest) { |
| std::unique_ptr<TypeParam> small_bit_vector(this->createBitVector(TestFixture::kSmallBitSize)); |
| small_bit_vector->clear(); |
| |
| small_bit_vector->setBitRange(2, 4, true); |
| small_bit_vector->setBitRange(3, 2, false); |
| |
| for (size_t i = 0; i < TestFixture::kSmallBitSize; ++i) { |
| if ((i == 2) || (i == 5)) { |
| EXPECT_TRUE(small_bit_vector->getBit(i)); |
| } else { |
| EXPECT_FALSE(small_bit_vector->getBit(i)); |
| } |
| } |
| |
| std::unique_ptr<TypeParam> bigger_bit_vector(this->createBitVector(TestFixture::kBiggerBitSize)); |
| bigger_bit_vector->clear(); |
| |
| // Set with exact size_t boundaries. |
| bigger_bit_vector->setBitRange(128, 512, true); |
| bigger_bit_vector->setBitRange(192, 64, false); |
| for (size_t i = 0; i < TestFixture::kBiggerBitSize; ++i) { |
| if (((i >= 128) && (i < 192)) || ((i >= 192 + 64) && (i < 128 + 512))) { |
| EXPECT_TRUE(bigger_bit_vector->getBit(i)); |
| } else { |
| EXPECT_FALSE(bigger_bit_vector->getBit(i)); |
| } |
| } |
| |
| // Set with boundaries that don't align with size_t strides. |
| bigger_bit_vector->clear(); |
| bigger_bit_vector->setBitRange(111, 222, true); |
| bigger_bit_vector->setBitRange(123, 55, false); |
| for (size_t i = 0; i < TestFixture::kBiggerBitSize; ++i) { |
| if (((i >= 111) && (i < 123)) || ((i >= 123 + 55) && (i < 111 + 222))) { |
| EXPECT_TRUE(bigger_bit_vector->getBit(i)); |
| } else { |
| EXPECT_FALSE(bigger_bit_vector->getBit(i)); |
| } |
| } |
| |
| // Set with boundaries all inside the same size_t stride. |
| bigger_bit_vector->clear(); |
| bigger_bit_vector->setBitRange(130, 20, true); |
| bigger_bit_vector->setBitRange(135, 5, false); |
| for (size_t i = 0; i < TestFixture::kBiggerBitSize; ++i) { |
| if (((i >= 130) && (i < 135)) || ((i >= 135 + 5) && (i < 130 + 20))) { |
| EXPECT_TRUE(bigger_bit_vector->getBit(i)); |
| } else { |
| EXPECT_FALSE(bigger_bit_vector->getBit(i)); |
| } |
| } |
| } |
| |
| TYPED_TEST(BitVectorTest, SetAndGetBitWordTest) { |
| std::unique_ptr<TypeParam> bigger_bit_vector(this->createBitVector(TestFixture::kBiggerBitSize)); |
| bigger_bit_vector->clear(); |
| |
| // Set with exact size_t boundaries. |
| const std::size_t bits_in_word = sizeof(std::size_t) << 3; |
| const std::size_t word_mask = static_cast<std::size_t>(-1); |
| const std::size_t last_word_id = (TestFixture::kBiggerBitSize - 1) / bits_in_word; |
| |
| // This test should work on both 32bit architecture and 64-bit architecture. |
| bigger_bit_vector->setBitWord(2, static_cast<std::size_t>(1) << ((bits_in_word - 1) - 3)); |
| bigger_bit_vector->setBitWord(6, ~(static_cast<std::size_t>(1) << ((bits_in_word - 1) - 11))); |
| bigger_bit_vector->setBitWord(last_word_id, word_mask); |
| for (size_t i = 0; i < TestFixture::kBiggerBitSize; ++i) { |
| if (i == 2 * bits_in_word + 3 |
| || (i >= 6 * bits_in_word && i < 7 * bits_in_word && i != 6 * bits_in_word + 11) |
| || i >= last_word_id * bits_in_word) { |
| EXPECT_TRUE(bigger_bit_vector->getBit(i)); |
| } else { |
| EXPECT_FALSE(bigger_bit_vector->getBit(i)); |
| } |
| } |
| for (size_t word_id = 0; word_id <= last_word_id; ++word_id) { |
| if (word_id == 2) { |
| EXPECT_EQ(static_cast<std::size_t>(1) << ((bits_in_word - 1) - 3), |
| bigger_bit_vector->getBitWord(word_id)); |
| } else if (word_id == 6) { |
| EXPECT_EQ(~(static_cast<std::size_t>(1) << ((bits_in_word - 1) - 11)), |
| bigger_bit_vector->getBitWord(word_id)); |
| } else if (word_id == last_word_id) { |
| size_t last_word = word_mask |
| << ((last_word_id + 1) * bits_in_word - TestFixture::kBiggerBitSize); |
| EXPECT_EQ(last_word, bigger_bit_vector->getBitWord(word_id)); |
| } else { |
| EXPECT_EQ(0u, bigger_bit_vector->getBitWord(word_id)); |
| } |
| } |
| } |
| |
| TYPED_TEST(BitVectorTest, ShiftTailForwardTest) { |
| std::unique_ptr<TypeParam> small_bit_vector(this->createBitVector(TestFixture::kSmallBitSize)); |
| small_bit_vector->clear(); |
| |
| small_bit_vector->setBit(2, true); |
| small_bit_vector->setBit(4, true); |
| small_bit_vector->setBit(6, true); |
| |
| small_bit_vector->shiftTailForward(3, 3); |
| |
| for (size_t i = 0; i < TestFixture::kSmallBitSize; ++i) { |
| if ((i == 2) || (i == 3)) { |
| EXPECT_TRUE(small_bit_vector->getBit(i)); |
| } else { |
| EXPECT_FALSE(small_bit_vector->getBit(i)); |
| } |
| } |
| EXPECT_EQ(2u, small_bit_vector->onesCount()); |
| |
| std::unique_ptr<TypeParam> big_bit_vector(this->createBitVector(TestFixture::kBigBitSize)); |
| big_bit_vector->clear(); |
| |
| big_bit_vector->setBit(11, true); |
| big_bit_vector->setBit(13, true); |
| big_bit_vector->setBit(27, true); |
| big_bit_vector->setBit(42, true); |
| big_bit_vector->setBit(84, true); |
| big_bit_vector->setBit(88, true); |
| big_bit_vector->setBit(91, true); |
| big_bit_vector->setBit(123, true); |
| |
| big_bit_vector->shiftTailForward(15, 70); |
| for (size_t i = 0; i < TestFixture::kBigBitSize; ++i) { |
| if ((i == 11) || (i == 13) || (i == 88 - 70) || (i == 91 - 70) || (i == 123 - 70)) { |
| EXPECT_TRUE(big_bit_vector->getBit(i)); |
| } else { |
| EXPECT_FALSE(big_bit_vector->getBit(i)); |
| } |
| } |
| EXPECT_EQ(5u, big_bit_vector->onesCount()); |
| |
| // Also try a relatively small shift within the same word. |
| big_bit_vector->clear(); |
| big_bit_vector->setBit(11, true); |
| big_bit_vector->setBit(13, true); |
| big_bit_vector->setBit(27, true); |
| big_bit_vector->setBit(42, true); |
| big_bit_vector->setBit(45, true); |
| big_bit_vector->setBit(51, true); |
| big_bit_vector->setBit(84, true); |
| big_bit_vector->setBit(88, true); |
| big_bit_vector->setBit(91, true); |
| big_bit_vector->setBit(123, true); |
| |
| big_bit_vector->shiftTailForward(43, 7); |
| for (size_t i = 0; i < TestFixture::kBigBitSize; ++i) { |
| if ((i == 11) || (i == 13) || (i == 27) || (i == 42) || (i == 51 - 7) |
| || (i == 84 - 7) || (i == 88 - 7) || (i == 91 - 7) || (i == 123 - 7)) { |
| EXPECT_TRUE(big_bit_vector->getBit(i)); |
| } else { |
| EXPECT_FALSE(big_bit_vector->getBit(i)); |
| } |
| } |
| EXPECT_EQ(9u, big_bit_vector->onesCount()); |
| |
| // Align the shift distance to size_t. |
| big_bit_vector->clear(); |
| big_bit_vector->setBit(11, true); |
| big_bit_vector->setBit(13, true); |
| big_bit_vector->setBit(27, true); |
| big_bit_vector->setBit(42, true); |
| big_bit_vector->setBit(45, true); |
| big_bit_vector->setBit(51, true); |
| big_bit_vector->setBit(84, true); |
| big_bit_vector->setBit(88, true); |
| big_bit_vector->setBit(91, true); |
| big_bit_vector->setBit(123, true); |
| big_bit_vector->setBit(128, true); |
| big_bit_vector->setBit(137, true); |
| |
| big_bit_vector->shiftTailForward(43, 64); |
| for (size_t i = 0; i < TestFixture::kBigBitSize; ++i) { |
| if ((i == 11) || (i == 13) || (i == 27) || (i == 42) |
| || (i == 123 - 64) || (i == 128 - 64) || (i == 137 - 64)) { |
| EXPECT_TRUE(big_bit_vector->getBit(i)); |
| } else { |
| EXPECT_FALSE(big_bit_vector->getBit(i)); |
| } |
| } |
| EXPECT_EQ(7u, big_bit_vector->onesCount()); |
| |
| // Exactly align both the tail start and the shift distance to size_t. |
| big_bit_vector->clear(); |
| big_bit_vector->setBit(11, true); |
| big_bit_vector->setBit(13, true); |
| big_bit_vector->setBit(27, true); |
| big_bit_vector->setBit(42, true); |
| big_bit_vector->setBit(45, true); |
| big_bit_vector->setBit(51, true); |
| big_bit_vector->setBit(84, true); |
| big_bit_vector->setBit(88, true); |
| big_bit_vector->setBit(91, true); |
| big_bit_vector->setBit(123, true); |
| big_bit_vector->setBit(128, true); |
| big_bit_vector->setBit(137, true); |
| |
| big_bit_vector->shiftTailForward(64, 64); |
| for (size_t i = 0; i < TestFixture::kBigBitSize; ++i) { |
| if ((i == 11) || (i == 13) || (i == 27) || (i == 42) || (i == 45) |
| || (i == 51) || (i == 128 - 64) || (i == 137 - 64)) { |
| EXPECT_TRUE(big_bit_vector->getBit(i)); |
| } else { |
| EXPECT_FALSE(big_bit_vector->getBit(i)); |
| } |
| } |
| EXPECT_EQ(8u, big_bit_vector->onesCount()); |
| |
| std::unique_ptr<TypeParam> bigger_bit_vector(this->createBitVector(TestFixture::kBiggerBitSize)); |
| bigger_bit_vector->clear(); |
| bigger_bit_vector->flipBits(); |
| |
| bigger_bit_vector->shiftTailForward(123, 456); |
| for (size_t i = 0; i < TestFixture::kBiggerBitSize; ++i) { |
| if (i < TestFixture::kBiggerBitSize - 456) { |
| EXPECT_TRUE(bigger_bit_vector->getBit(i)); |
| } else { |
| EXPECT_FALSE(bigger_bit_vector->getBit(i)); |
| } |
| } |
| EXPECT_EQ(TestFixture::kBiggerBitSize - 456, bigger_bit_vector->onesCount()); |
| |
| // Also try a nicely-aligned shift. |
| bigger_bit_vector->clear(); |
| bigger_bit_vector->flipBits(); |
| |
| bigger_bit_vector->shiftTailForward(123, 512); |
| for (size_t i = 0; i < TestFixture::kBiggerBitSize; ++i) { |
| if (i < TestFixture::kBiggerBitSize - 512) { |
| EXPECT_TRUE(bigger_bit_vector->getBit(i)); |
| } else { |
| EXPECT_FALSE(bigger_bit_vector->getBit(i)); |
| } |
| } |
| EXPECT_EQ(TestFixture::kBiggerBitSize - 512, bigger_bit_vector->onesCount()); |
| |
| // Even nicer, align the tail start as well. |
| bigger_bit_vector->clear(); |
| bigger_bit_vector->flipBits(); |
| |
| bigger_bit_vector->shiftTailForward(128, 512); |
| for (size_t i = 0; i < TestFixture::kBiggerBitSize; ++i) { |
| if (i < TestFixture::kBiggerBitSize - 512) { |
| EXPECT_TRUE(bigger_bit_vector->getBit(i)); |
| } else { |
| EXPECT_FALSE(bigger_bit_vector->getBit(i)); |
| } |
| } |
| EXPECT_EQ(TestFixture::kBiggerBitSize - 512, bigger_bit_vector->onesCount()); |
| |
| // Finally, do a shift so large that it just zeroes out the entire tail. |
| bigger_bit_vector->clear(); |
| bigger_bit_vector->flipBits(); |
| |
| bigger_bit_vector->shiftTailForward(567, 1000); |
| for (size_t i = 0; i < TestFixture::kBiggerBitSize; ++i) { |
| if (i < 567) { |
| EXPECT_TRUE(bigger_bit_vector->getBit(i)); |
| } else { |
| EXPECT_FALSE(bigger_bit_vector->getBit(i)); |
| } |
| } |
| EXPECT_EQ(567u, bigger_bit_vector->onesCount()); |
| } |
| |
| TYPED_TEST(BitVectorTest, ShiftTailBackwardTest) { |
| std::unique_ptr<TypeParam> small_bit_vector(this->createBitVector(TestFixture::kSmallBitSize)); |
| small_bit_vector->clear(); |
| |
| small_bit_vector->setBit(2, true); |
| small_bit_vector->setBit(4, true); |
| small_bit_vector->setBit(6, true); |
| |
| small_bit_vector->shiftTailBackward(3, 3); |
| |
| for (size_t i = 0; i < TestFixture::kSmallBitSize; ++i) { |
| if ((i == 2) || (i == 7)) { |
| EXPECT_TRUE(small_bit_vector->getBit(i)); |
| } else { |
| EXPECT_FALSE(small_bit_vector->getBit(i)); |
| } |
| } |
| EXPECT_EQ(2u, small_bit_vector->onesCount()); |
| |
| std::unique_ptr<TypeParam> big_bit_vector(this->createBitVector(TestFixture::kBigBitSize)); |
| big_bit_vector->clear(); |
| |
| big_bit_vector->setBit(11, true); |
| big_bit_vector->setBit(13, true); |
| big_bit_vector->setBit(27, true); |
| big_bit_vector->setBit(42, true); |
| big_bit_vector->setBit(84, true); |
| big_bit_vector->setBit(88, true); |
| big_bit_vector->setBit(91, true); |
| big_bit_vector->setBit(123, true); |
| |
| big_bit_vector->shiftTailBackward(15, 70); |
| for (size_t i = 0; i < TestFixture::kBigBitSize; ++i) { |
| if ((i == 11) || (i == 13) || (i == 27 + 70) |
| || (i == 42 + 70) || (i == 88 + 70) || (i == 84 + 70)) { |
| EXPECT_TRUE(big_bit_vector->getBit(i)); |
| } else { |
| EXPECT_FALSE(big_bit_vector->getBit(i)); |
| } |
| } |
| EXPECT_EQ(6u, big_bit_vector->onesCount()); |
| |
| // Also try a relatively small shift within the same word. |
| big_bit_vector->clear(); |
| big_bit_vector->setBit(11, true); |
| big_bit_vector->setBit(13, true); |
| big_bit_vector->setBit(27, true); |
| big_bit_vector->setBit(42, true); |
| big_bit_vector->setBit(45, true); |
| big_bit_vector->setBit(51, true); |
| big_bit_vector->setBit(84, true); |
| big_bit_vector->setBit(88, true); |
| big_bit_vector->setBit(91, true); |
| big_bit_vector->setBit(123, true); |
| |
| big_bit_vector->shiftTailBackward(43, 7); |
| for (size_t i = 0; i < TestFixture::kBigBitSize; ++i) { |
| if ((i == 11) || (i == 13) || (i == 27) || (i == 42) || (i == 45 + 7) || (i == 51 + 7) |
| || (i == 84 + 7) || (i == 88 + 7) || (i == 91 + 7) || (i == 123 + 7)) { |
| EXPECT_TRUE(big_bit_vector->getBit(i)); |
| } else { |
| EXPECT_FALSE(big_bit_vector->getBit(i)); |
| } |
| } |
| EXPECT_EQ(10u, big_bit_vector->onesCount()); |
| |
| // Align the shift distance to size_t. |
| big_bit_vector->clear(); |
| big_bit_vector->setBit(11, true); |
| big_bit_vector->setBit(13, true); |
| big_bit_vector->setBit(27, true); |
| big_bit_vector->setBit(42, true); |
| big_bit_vector->setBit(45, true); |
| big_bit_vector->setBit(51, true); |
| big_bit_vector->setBit(84, true); |
| big_bit_vector->setBit(88, true); |
| big_bit_vector->setBit(91, true); |
| big_bit_vector->setBit(123, true); |
| big_bit_vector->setBit(128, true); |
| big_bit_vector->setBit(137, true); |
| |
| big_bit_vector->shiftTailBackward(43, 64); |
| for (size_t i = 0; i < TestFixture::kBigBitSize; ++i) { |
| if ((i == 11) || (i == 13) || (i == 27) || (i == 42) |
| || (i == 45 + 64) || (i == 51 + 64) || (i == 84 + 64) |
| || (i == 88 + 64) || (i == 91 + 64)) { |
| EXPECT_TRUE(big_bit_vector->getBit(i)); |
| } else { |
| EXPECT_FALSE(big_bit_vector->getBit(i)); |
| } |
| } |
| EXPECT_EQ(9u, big_bit_vector->onesCount()); |
| |
| // Exactly align both the tail start and the shift distance to size_t. |
| big_bit_vector->clear(); |
| big_bit_vector->setBit(11, true); |
| big_bit_vector->setBit(13, true); |
| big_bit_vector->setBit(27, true); |
| big_bit_vector->setBit(42, true); |
| big_bit_vector->setBit(45, true); |
| big_bit_vector->setBit(51, true); |
| big_bit_vector->setBit(84, true); |
| big_bit_vector->setBit(88, true); |
| big_bit_vector->setBit(91, true); |
| big_bit_vector->setBit(123, true); |
| big_bit_vector->setBit(128, true); |
| big_bit_vector->setBit(137, true); |
| |
| big_bit_vector->shiftTailBackward(64, 64); |
| for (size_t i = 0; i < TestFixture::kBigBitSize; ++i) { |
| if ((i == 11) || (i == 13) || (i == 27) || (i == 42) || (i == 45) |
| || (i == 51) || (i == 84 + 64) || (i == 88 + 64) || (i == 91 + 64)) { |
| EXPECT_TRUE(big_bit_vector->getBit(i)); |
| } else { |
| EXPECT_FALSE(big_bit_vector->getBit(i)); |
| } |
| } |
| EXPECT_EQ(9u, big_bit_vector->onesCount()); |
| |
| std::unique_ptr<TypeParam> bigger_bit_vector(this->createBitVector(TestFixture::kBiggerBitSize)); |
| bigger_bit_vector->clear(); |
| bigger_bit_vector->flipBits(); |
| |
| bigger_bit_vector->shiftTailBackward(123, 456); |
| for (size_t i = 0; i < TestFixture::kBiggerBitSize; ++i) { |
| if ((i < 123) || (i >= 123 + 456)) { |
| EXPECT_TRUE(bigger_bit_vector->getBit(i)); |
| } else { |
| EXPECT_FALSE(bigger_bit_vector->getBit(i)); |
| } |
| } |
| EXPECT_EQ(TestFixture::kBiggerBitSize - 456, bigger_bit_vector->onesCount()); |
| |
| // Also try a nicely-aligned shift. |
| bigger_bit_vector->clear(); |
| bigger_bit_vector->flipBits(); |
| |
| bigger_bit_vector->shiftTailBackward(123, 512); |
| for (size_t i = 0; i < TestFixture::kBiggerBitSize; ++i) { |
| if ((i < 123) || (i >= 123 + 512)) { |
| EXPECT_TRUE(bigger_bit_vector->getBit(i)); |
| } else { |
| EXPECT_FALSE(bigger_bit_vector->getBit(i)); |
| } |
| } |
| EXPECT_EQ(TestFixture::kBiggerBitSize - 512, bigger_bit_vector->onesCount()); |
| |
| // Even nicer, align the tail start as well. |
| bigger_bit_vector->clear(); |
| bigger_bit_vector->flipBits(); |
| |
| bigger_bit_vector->shiftTailBackward(128, 512); |
| for (size_t i = 0; i < TestFixture::kBiggerBitSize; ++i) { |
| if ((i < 128) || (i >= 128 + 512)) { |
| EXPECT_TRUE(bigger_bit_vector->getBit(i)); |
| } else { |
| EXPECT_FALSE(bigger_bit_vector->getBit(i)); |
| } |
| } |
| EXPECT_EQ(TestFixture::kBiggerBitSize - 512, bigger_bit_vector->onesCount()); |
| |
| // Finally, do a shift so large that it just zeroes out the entire tail. |
| bigger_bit_vector->clear(); |
| bigger_bit_vector->flipBits(); |
| |
| bigger_bit_vector->shiftTailBackward(567, 1000); |
| for (size_t i = 0; i < TestFixture::kBiggerBitSize; ++i) { |
| if (i < 567) { |
| EXPECT_TRUE(bigger_bit_vector->getBit(i)); |
| } else { |
| EXPECT_FALSE(bigger_bit_vector->getBit(i)); |
| } |
| } |
| EXPECT_EQ(567u, bigger_bit_vector->onesCount()); |
| } |
| |
| TYPED_TEST(BitVectorTest, RebindTest) { |
| std::unique_ptr<TypeParam> big_bit_vector(this->createBitVector(TestFixture::kBigBitSize)); |
| big_bit_vector->clear(); |
| |
| // Set some bits, particularly around potential boundaries between size_t |
| // strides. |
| big_bit_vector->setBit(0, true); |
| big_bit_vector->setBit(5, true); |
| big_bit_vector->setBit(31, true); |
| big_bit_vector->setBit(32, true); |
| big_bit_vector->setBit(63, true); |
| big_bit_vector->setBit(64, true); |
| big_bit_vector->setBit(127, true); |
| big_bit_vector->setBit(128, true); |
| |
| // Destroy the old BitVector and create a new one bound to the same memory. |
| ASSERT_EQ(1u, this->allocated_chunks_.size()); |
| big_bit_vector.reset(new TypeParam(this->allocated_chunks_.back(), TestFixture::kBigBitSize)); |
| |
| // Make sure bits set in the original BitVector instance are set in the |
| // rebound instance. |
| for (size_t i = 0; i < TestFixture::kBigBitSize; ++i) { |
| if ((i == 0) || (i == 5) || (i == 31) || (i == 32) || (i == 63) || (i == 64) || (i == 127) || (i == 128)) { |
| EXPECT_TRUE(big_bit_vector->getBit(i)); |
| } else { |
| EXPECT_FALSE(big_bit_vector->getBit(i)); |
| } |
| } |
| EXPECT_EQ(8u, big_bit_vector->onesCount()); |
| EXPECT_EQ(1u, big_bit_vector->firstZero()); |
| EXPECT_EQ(2u, big_bit_vector->firstZero(2)); |
| EXPECT_EQ(0u, big_bit_vector->firstOne()); |
| EXPECT_EQ(5u, big_bit_vector->firstOne(1)); |
| EXPECT_EQ(TestFixture::kBigBitSize - 1, big_bit_vector->lastZero()); |
| EXPECT_EQ(126u, big_bit_vector->lastZero(129)); |
| EXPECT_EQ(TestFixture::kBigBitSize, big_bit_vector->lastZero(1)); |
| EXPECT_EQ(128u, big_bit_vector->lastOne()); |
| EXPECT_EQ(127u, big_bit_vector->lastOne(128)); |
| EXPECT_EQ(64u, big_bit_vector->lastOne(127)); |
| } |
| |
| TYPED_TEST(BitVectorTest, AnyTest) { |
| std::unique_ptr<TypeParam> small_bit_vector(this->createBitVector(TestFixture::kSmallBitSize)); |
| |
| small_bit_vector->clear(); |
| EXPECT_FALSE(small_bit_vector->any()); |
| |
| small_bit_vector->setBit(0, true); |
| EXPECT_TRUE(small_bit_vector->any()); |
| small_bit_vector->setBit(0, false); |
| EXPECT_FALSE(small_bit_vector->any()); |
| |
| small_bit_vector->setBit(TestFixture::kSmallBitSize - 1, true); |
| EXPECT_TRUE(small_bit_vector->any()); |
| small_bit_vector->setBit(TestFixture::kSmallBitSize - 1, false); |
| EXPECT_FALSE(small_bit_vector->any()); |
| |
| small_bit_vector->setBit(TestFixture::kSmallBitSize / 2, true); |
| EXPECT_TRUE(small_bit_vector->any()); |
| small_bit_vector->setBit(TestFixture::kSmallBitSize / 2 + 1, true); |
| EXPECT_TRUE(small_bit_vector->any()); |
| small_bit_vector->setBit(TestFixture::kSmallBitSize / 2, false); |
| EXPECT_TRUE(small_bit_vector->any()); |
| small_bit_vector->setBit(TestFixture::kSmallBitSize / 2 + 1, false); |
| EXPECT_FALSE(small_bit_vector->any()); |
| |
| |
| std::unique_ptr<TypeParam> big_bit_vector(this->createBitVector(TestFixture::kBigBitSize)); |
| |
| big_bit_vector->clear(); |
| EXPECT_FALSE(big_bit_vector->any()); |
| |
| big_bit_vector->setBit(0, true); |
| EXPECT_TRUE(big_bit_vector->any()); |
| big_bit_vector->setBit(0, false); |
| EXPECT_FALSE(big_bit_vector->any()); |
| |
| big_bit_vector->setBit(TestFixture::kBigBitSize - 1, true); |
| EXPECT_TRUE(big_bit_vector->any()); |
| big_bit_vector->setBit(TestFixture::kBigBitSize - 1, false); |
| EXPECT_FALSE(big_bit_vector->any()); |
| |
| big_bit_vector->setBit(TestFixture::kBigBitSize / 2, true); |
| EXPECT_TRUE(big_bit_vector->any()); |
| big_bit_vector->setBit(TestFixture::kBigBitSize / 2 + 1, true); |
| EXPECT_TRUE(big_bit_vector->any()); |
| big_bit_vector->setBit(TestFixture::kBigBitSize / 2, false); |
| EXPECT_TRUE(big_bit_vector->any()); |
| big_bit_vector->setBit(TestFixture::kBigBitSize / 2 + 1, false); |
| EXPECT_FALSE(big_bit_vector->any()); |
| } |
| |
| TYPED_TEST(BitVectorTest, AllTest) { |
| std::unique_ptr<TypeParam> small_bit_vector(this->createBitVector(TestFixture::kSmallBitSize)); |
| |
| small_bit_vector->clear(); |
| EXPECT_FALSE(small_bit_vector->all()); |
| small_bit_vector->flipBits(); |
| EXPECT_TRUE(small_bit_vector->all()); |
| |
| small_bit_vector->setBit(0, false); |
| EXPECT_FALSE(small_bit_vector->all()); |
| small_bit_vector->setBit(0, true); |
| EXPECT_TRUE(small_bit_vector->all()); |
| |
| small_bit_vector->setBit(TestFixture::kSmallBitSize - 1, false); |
| EXPECT_FALSE(small_bit_vector->all()); |
| small_bit_vector->setBit(TestFixture::kSmallBitSize - 1, true); |
| EXPECT_TRUE(small_bit_vector->all()); |
| |
| small_bit_vector->setBit(TestFixture::kSmallBitSize / 2, false); |
| EXPECT_FALSE(small_bit_vector->all()); |
| small_bit_vector->setBit(TestFixture::kSmallBitSize / 2 + 1, false); |
| EXPECT_FALSE(small_bit_vector->all()); |
| small_bit_vector->setBit(TestFixture::kSmallBitSize / 2, true); |
| EXPECT_FALSE(small_bit_vector->all()); |
| small_bit_vector->setBit(TestFixture::kSmallBitSize / 2 + 1, true); |
| EXPECT_TRUE(small_bit_vector->all()); |
| |
| |
| std::unique_ptr<TypeParam> big_bit_vector(this->createBitVector(TestFixture::kBigBitSize)); |
| |
| big_bit_vector->clear(); |
| EXPECT_FALSE(big_bit_vector->all()); |
| big_bit_vector->flipBits(); |
| EXPECT_TRUE(big_bit_vector->all()); |
| |
| big_bit_vector->setBit(0, false); |
| EXPECT_FALSE(big_bit_vector->all()); |
| big_bit_vector->setBit(0, true); |
| EXPECT_TRUE(big_bit_vector->all()); |
| |
| big_bit_vector->setBit(TestFixture::kBigBitSize - 1, false); |
| EXPECT_FALSE(big_bit_vector->all()); |
| big_bit_vector->setBit(TestFixture::kBigBitSize - 1, true); |
| EXPECT_TRUE(big_bit_vector->all()); |
| |
| big_bit_vector->setBit(TestFixture::kBigBitSize / 2, false); |
| EXPECT_FALSE(big_bit_vector->all()); |
| big_bit_vector->setBit(TestFixture::kBigBitSize / 2 + 1, false); |
| EXPECT_FALSE(big_bit_vector->all()); |
| big_bit_vector->setBit(TestFixture::kBigBitSize / 2, true); |
| EXPECT_FALSE(big_bit_vector->all()); |
| big_bit_vector->setBit(TestFixture::kBigBitSize / 2 + 1, true); |
| EXPECT_TRUE(big_bit_vector->all()); |
| } |
| |
| TYPED_TEST(BitVectorTest, ZeroLengthTest) { |
| EXPECT_EQ(0u, TypeParam::BytesNeeded(0)); |
| |
| // Test a BitVector that owns its own memory. |
| TypeParam owning_zero_length_bit_vector(0); |
| this->runZeroLengthTest(&owning_zero_length_bit_vector); |
| |
| // Test a BitVector that does not own its own memory. |
| unsigned buffer = 0xDEADBEEF; |
| TypeParam non_owning_zero_length_bit_vector(&buffer, 0); |
| this->runZeroLengthTest(&owning_zero_length_bit_vector); |
| // Make sure the provided memory location is unmodified. |
| EXPECT_EQ(0xDEADBEEF, buffer); |
| } |
| |
| } // namespace quickstep |