| // Copyright 2019 The Chromium Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include "util/yet_another_bit_vector.h" |
| |
| #include <algorithm> |
| |
| #include "absl/algorithm/container.h" |
| #include "absl/types/span.h" |
| #include "gtest/gtest.h" |
| |
| namespace openscreen { |
| namespace { |
| |
| constexpr uint8_t kBitPatterns[] = {0b00000000, 0b11111111, 0b01010101, |
| 0b10101010, 0b00100100, 0b01001001, |
| 0b10010010, 0b00110110}; |
| |
| // These are used for testing various vector sizes, begins/ends of ranges, etc. |
| // They will exercise both the "inlined storage" (size <= 64 case) and |
| // "heap-allocated storage" cases. These are all of the prime numbers less than |
| // 200, and also any non-negative multiples of 64 less than 200. |
| const int kTestSizes[] = {0, 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, |
| 29, 31, 37, 41, 43, 47, 53, 59, 61, 64, 67, |
| 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, |
| 127, 128, 131, 137, 139, 149, 151, 157, 163, 167, 173, |
| 179, 181, 191, 192, 193, 197, 199}; |
| |
| // Returns a subspan of |kTestSizes| that contains all values in the range |
| // [first,last]. |
| absl::Span<const int> GetTestSizesInRange(int first, int last) { |
| const auto begin = absl::c_lower_bound(kTestSizes, first); |
| const auto end = absl::c_upper_bound(kTestSizes, last); |
| return absl::Span<const int>(&*begin, std::distance(begin, end)); |
| } |
| |
| // Returns true if an infinitely-repeating |pattern| has a bit set at the given |
| // |position|. |
| constexpr bool IsSetInPattern(uint8_t pattern, int position) { |
| constexpr int kRepeatPeriod = sizeof(pattern) * CHAR_BIT; |
| return !!((pattern >> (position % kRepeatPeriod)) & 1); |
| } |
| |
| // Fills an infinitely-repeating |pattern| in |v|, but only modifies the bits at |
| // and after the given |from| position. |
| void FillWithPattern(uint8_t pattern, int from, YetAnotherBitVector* v) { |
| for (int i = from; i < v->size(); ++i) { |
| if (IsSetInPattern(pattern, i)) { |
| v->Set(i); |
| } else { |
| v->Clear(i); |
| } |
| } |
| } |
| |
| // Tests that construction and resizes initialize the vector to the correct size |
| // and set or clear all of its bits, as requested. |
| TEST(YetAnotherBitVectorTest, ConstructsAndResizes) { |
| YetAnotherBitVector v; |
| ASSERT_EQ(v.size(), 0); |
| |
| for (int fill_set = 0; fill_set <= 1; ++fill_set) { |
| for (int size : kTestSizes) { |
| const bool all_bits_should_be_set = !!fill_set; |
| v.Resize(size, all_bits_should_be_set ? YetAnotherBitVector::SET |
| : YetAnotherBitVector::CLEARED); |
| ASSERT_EQ(size, v.size()); |
| for (int i = 0; i < size; ++i) { |
| ASSERT_EQ(all_bits_should_be_set, v.IsSet(i)); |
| } |
| } |
| } |
| } |
| |
| // Tests that individual bits can be set and cleared for various vector sizes |
| // and bit patterns. |
| TEST(YetAnotherBitVectorTest, SetsAndClearsIndividualBits) { |
| YetAnotherBitVector v; |
| for (int fill_set = 0; fill_set <= 1; ++fill_set) { |
| for (int size : kTestSizes) { |
| v.Resize(size, fill_set ? YetAnotherBitVector::SET |
| : YetAnotherBitVector::CLEARED); |
| |
| for (uint8_t pattern : kBitPatterns) { |
| FillWithPattern(pattern, 0, &v); |
| for (int i = 0; i < size; ++i) { |
| ASSERT_EQ(IsSetInPattern(pattern, i), v.IsSet(i)); |
| } |
| } |
| } |
| } |
| } |
| |
| // Tests that the vector shifts its bits right by various amounts, for various |
| // vector sizes and bit patterns. |
| TEST(YetAnotherBitVectorTest, ShiftsRight) { |
| YetAnotherBitVector v; |
| for (int size : kTestSizes) { |
| v.Resize(size, YetAnotherBitVector::CLEARED); |
| |
| for (int steps_per_shift : GetTestSizesInRange(0, size)) { |
| for (uint8_t pattern : kBitPatterns) { |
| FillWithPattern(pattern, 0, &v); |
| |
| if (size == 0 || steps_per_shift == 0) { |
| v.ShiftRight(0); |
| for (int i = 0; i < size; ++i) { |
| ASSERT_EQ(IsSetInPattern(pattern, i), v.IsSet(i)); |
| } |
| } else { |
| const int num_shifts = 2 * size / steps_per_shift; |
| for (int iteration = 1; iteration <= num_shifts; ++iteration) { |
| v.ShiftRight(steps_per_shift); |
| const int total_shift_amount = iteration * steps_per_shift; |
| for (int i = 0; i < size; ++i) { |
| const int original_position = i + total_shift_amount; |
| if (original_position >= size) { |
| ASSERT_FALSE(v.IsSet(i)); |
| } else { |
| ASSERT_EQ(IsSetInPattern(pattern, original_position), |
| v.IsSet(i)); |
| } |
| } |
| } |
| } |
| } |
| } |
| } |
| } |
| |
| // Tests the FindFirstSet() operation, for various vector sizes and bit |
| // patterns. |
| TEST(YetAnotherBitVectorTest, FindsTheFirstBitSet) { |
| YetAnotherBitVector v; |
| |
| // For various sizes of vector where no bits are set, the FFS operation should |
| // always return size(). |
| for (int size : kTestSizes) { |
| v.Resize(size, YetAnotherBitVector::CLEARED); |
| ASSERT_EQ(size, v.FindFirstSet()); |
| } |
| |
| // For various sizes of vector where only one bit is set, the FFS operation |
| // should always return the position of that bit. |
| for (int size : kTestSizes) { |
| v.Resize(size, YetAnotherBitVector::CLEARED); |
| |
| for (int position_plus_one : GetTestSizesInRange(1, size)) { |
| const int position = position_plus_one - 1; |
| v.Set(position); |
| ASSERT_EQ(position, v.FindFirstSet()); |
| v.Clear(position); |
| } |
| } |
| |
| // For various sizes of vector where a pattern of bits are set, the FFS |
| // operation should always return the first one set. |
| for (int size : kTestSizes) { |
| v.Resize(size, YetAnotherBitVector::CLEARED); |
| |
| for (int position_plus_one : GetTestSizesInRange(1, size)) { |
| const int position = position_plus_one - 1; |
| v.ClearAll(); |
| v.Set(position); |
| for (uint8_t pattern : kBitPatterns) { |
| FillWithPattern(pattern, position_plus_one, &v); |
| ASSERT_EQ(position, v.FindFirstSet()); |
| } |
| v.Clear(position); |
| } |
| } |
| } |
| |
| // Tests the CountBitsSet() operation, for various vector sizes, bit patterns, |
| // and ranges of bits being counted. |
| TEST(YetAnotherBitVector, CountsTheNumberOfBitsSet) { |
| YetAnotherBitVector v; |
| |
| // For various sizes of vector where no bits are set, the operation should |
| // always return zero for any range. |
| for (int size : kTestSizes) { |
| v.Resize(size, YetAnotherBitVector::CLEARED); |
| for (int begin : GetTestSizesInRange(0, size)) { |
| for (int end : GetTestSizesInRange(begin, size)) { |
| ASSERT_EQ(0, v.CountBitsSet(begin, end)); |
| } |
| } |
| } |
| |
| // For various sizes of vector where all bits are set, the operation should |
| // always return the length of the range (or zero for invalid ranges). |
| for (int size : kTestSizes) { |
| v.Resize(size, YetAnotherBitVector::SET); |
| for (int begin : GetTestSizesInRange(0, size)) { |
| for (int end : GetTestSizesInRange(begin, size)) { |
| ASSERT_EQ(end - begin, v.CountBitsSet(begin, end)); |
| } |
| } |
| } |
| |
| // Test various sizes of vector where various patterns of bits are set. |
| for (int size : kTestSizes) { |
| v.Resize(size, YetAnotherBitVector::CLEARED); |
| for (uint8_t pattern : kBitPatterns) { |
| FillWithPattern(pattern, 0, &v); |
| |
| for (int begin : GetTestSizesInRange(0, size)) { |
| for (int end : GetTestSizesInRange(begin, size)) { |
| // Note: The expected value being manually computed by examining each |
| // bit individually by calling IsSet(). Thus, this value is only good |
| // if IsSet() is working (which is tested by a different unit test). |
| int expected_popcount = 0; |
| for (int i = begin; i < end; ++i) { |
| if (v.IsSet(i)) { |
| ++expected_popcount; |
| } |
| } |
| |
| ASSERT_EQ(expected_popcount, v.CountBitsSet(begin, end)); |
| } |
| } |
| } |
| } |
| } |
| |
| } // namespace |
| } // namespace openscreen |