bounded_utf8_length_sequence_test.cc (5144B)
1 // Copyright 2024 The Abseil Authors 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // https://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #include "absl/debugging/internal/bounded_utf8_length_sequence.h" 16 17 #include <cstdint> 18 19 #include "gtest/gtest.h" 20 #include "absl/base/config.h" 21 22 namespace absl { 23 ABSL_NAMESPACE_BEGIN 24 namespace debugging_internal { 25 namespace { 26 27 TEST(BoundedUtf8LengthSequenceTest, RemembersAValueOfOneCorrectly) { 28 BoundedUtf8LengthSequence<32> seq; 29 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(0, 1), 0); 30 EXPECT_EQ(seq.InsertAndReturnSumOfPredecessors(1, 1), 1); 31 } 32 33 TEST(BoundedUtf8LengthSequenceTest, RemembersAValueOfTwoCorrectly) { 34 BoundedUtf8LengthSequence<32> seq; 35 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(0, 2), 0); 36 EXPECT_EQ(seq.InsertAndReturnSumOfPredecessors(1, 1), 2); 37 } 38 39 TEST(BoundedUtf8LengthSequenceTest, RemembersAValueOfThreeCorrectly) { 40 BoundedUtf8LengthSequence<32> seq; 41 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(0, 3), 0); 42 EXPECT_EQ(seq.InsertAndReturnSumOfPredecessors(1, 1), 3); 43 } 44 45 TEST(BoundedUtf8LengthSequenceTest, RemembersAValueOfFourCorrectly) { 46 BoundedUtf8LengthSequence<32> seq; 47 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(0, 4), 0); 48 EXPECT_EQ(seq.InsertAndReturnSumOfPredecessors(1, 1), 4); 49 } 50 51 TEST(BoundedUtf8LengthSequenceTest, RemembersSeveralAppendedValues) { 52 BoundedUtf8LengthSequence<32> seq; 53 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(0, 1), 0); 54 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(1, 4), 1); 55 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(2, 2), 5); 56 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(3, 3), 7); 57 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(4, 1), 10); 58 } 59 60 TEST(BoundedUtf8LengthSequenceTest, RemembersSeveralPrependedValues) { 61 BoundedUtf8LengthSequence<32> seq; 62 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(0, 4), 0); 63 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(0, 3), 0); 64 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(0, 2), 0); 65 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(0, 1), 0); 66 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(4, 1), 10); 67 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(3, 1), 6); 68 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(2, 1), 3); 69 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(1, 1), 1); 70 } 71 72 TEST(BoundedUtf8LengthSequenceTest, RepeatedInsertsShiftValuesOutTheRightEnd) { 73 BoundedUtf8LengthSequence<32> seq; 74 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(0, 2), 0); 75 for (uint32_t i = 1; i < 31; ++i) { 76 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(0, 1), 0) 77 << "while moving the 2 into position " << i; 78 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(31, 1), 32) 79 << "after moving the 2 into position " << i; 80 } 81 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(0, 1), 0) 82 << "while moving the 2 into position 31"; 83 EXPECT_EQ(seq.InsertAndReturnSumOfPredecessors(31, 1), 31) 84 << "after moving the 2 into position 31"; 85 } 86 87 TEST(BoundedUtf8LengthSequenceTest, InsertsIntoWord1LeaveWord0Untouched) { 88 BoundedUtf8LengthSequence<64> seq; 89 for (uint32_t i = 0; i < 32; ++i) { 90 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(i, 2), 2 * i) 91 << "at index " << i; 92 } 93 EXPECT_EQ(seq.InsertAndReturnSumOfPredecessors(32, 1), 64); 94 EXPECT_EQ(seq.InsertAndReturnSumOfPredecessors(32, 1), 64); 95 } 96 97 TEST(BoundedUtf8LengthSequenceTest, InsertsIntoWord0ShiftValuesIntoWord1) { 98 BoundedUtf8LengthSequence<64> seq; 99 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(29, 2), 29); 100 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(30, 3), 31); 101 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(31, 4), 34); 102 103 // Pushing two 1's on the front moves the 3 and 4 into the high word. 104 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(0, 1), 0); 105 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(0, 1), 0); 106 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(34, 1), 31 + 2 + 3 + 4); 107 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(32, 1), 31 + 2); 108 } 109 110 TEST(BoundedUtf8LengthSequenceTest, ValuesAreShiftedCorrectlyAmongThreeWords) { 111 BoundedUtf8LengthSequence<96> seq; 112 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(31, 3), 31); 113 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(63, 4), 62 + 3); 114 115 // This insertion moves both the 3 and the 4 up a word. 116 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(0, 1), 0); 117 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(65, 1), 63 + 3 + 4); 118 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(64, 1), 63 + 3); 119 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(33, 1), 32 + 3); 120 ASSERT_EQ(seq.InsertAndReturnSumOfPredecessors(32, 1), 32); 121 } 122 123 } // namespace 124 } // namespace debugging_internal 125 ABSL_NAMESPACE_END 126 } // namespace absl