1 /* 2 * Copyright (C) 2013 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #include <memory> 18 19 #include "allocator.h" 20 #include "bit_vector-inl.h" 21 #include "gtest/gtest.h" 22 23 namespace art { 24 25 TEST(BitVector, Test) { 26 const size_t kBits = 32; 27 28 BitVector bv(kBits, false, Allocator::GetMallocAllocator()); 29 EXPECT_EQ(1U, bv.GetStorageSize()); 30 EXPECT_EQ(sizeof(uint32_t), bv.GetSizeOf()); 31 EXPECT_FALSE(bv.IsExpandable()); 32 33 EXPECT_EQ(0U, bv.NumSetBits()); 34 EXPECT_EQ(0U, bv.NumSetBits(1)); 35 EXPECT_EQ(0U, bv.NumSetBits(kBits)); 36 for (size_t i = 0; i < kBits; i++) { 37 EXPECT_FALSE(bv.IsBitSet(i)); 38 } 39 EXPECT_EQ(0U, bv.GetRawStorageWord(0)); 40 EXPECT_EQ(0U, *bv.GetRawStorage()); 41 42 EXPECT_TRUE(bv.Indexes().begin().Done()); 43 EXPECT_TRUE(bv.Indexes().begin() == bv.Indexes().end()); 44 45 bv.SetBit(0); 46 bv.SetBit(kBits - 1); 47 EXPECT_EQ(2U, bv.NumSetBits()); 48 EXPECT_EQ(1U, bv.NumSetBits(1)); 49 EXPECT_EQ(2U, bv.NumSetBits(kBits)); 50 EXPECT_TRUE(bv.IsBitSet(0)); 51 for (size_t i = 1; i < kBits - 1; i++) { 52 EXPECT_FALSE(bv.IsBitSet(i)); 53 } 54 EXPECT_TRUE(bv.IsBitSet(kBits - 1)); 55 EXPECT_EQ(0x80000001U, bv.GetRawStorageWord(0)); 56 EXPECT_EQ(0x80000001U, *bv.GetRawStorage()); 57 58 BitVector::IndexIterator iterator = bv.Indexes().begin(); 59 EXPECT_TRUE(iterator != bv.Indexes().end()); 60 EXPECT_EQ(0u, *iterator); 61 ++iterator; 62 EXPECT_TRUE(iterator != bv.Indexes().end()); 63 EXPECT_EQ(kBits - 1u, *iterator); 64 ++iterator; 65 EXPECT_TRUE(iterator == bv.Indexes().end()); 66 } 67 68 TEST(BitVector, NoopAllocator) { 69 const uint32_t kWords = 2; 70 71 uint32_t bits[kWords]; 72 memset(bits, 0, sizeof(bits)); 73 74 BitVector bv(false, Allocator::GetNoopAllocator(), kWords, bits); 75 EXPECT_EQ(kWords, bv.GetStorageSize()); 76 EXPECT_EQ(kWords * sizeof(uint32_t), bv.GetSizeOf()); 77 EXPECT_EQ(bits, bv.GetRawStorage()); 78 EXPECT_EQ(0U, bv.NumSetBits()); 79 80 bv.SetBit(8); 81 EXPECT_EQ(1U, bv.NumSetBits()); 82 EXPECT_EQ(0x00000100U, bv.GetRawStorageWord(0)); 83 EXPECT_EQ(0x00000000U, bv.GetRawStorageWord(1)); 84 EXPECT_EQ(1U, bv.NumSetBits()); 85 86 bv.SetBit(16); 87 EXPECT_EQ(2U, bv.NumSetBits()); 88 EXPECT_EQ(0x00010100U, bv.GetRawStorageWord(0)); 89 EXPECT_EQ(0x00000000U, bv.GetRawStorageWord(1)); 90 EXPECT_EQ(2U, bv.NumSetBits()); 91 92 bv.SetBit(32); 93 EXPECT_EQ(3U, bv.NumSetBits()); 94 EXPECT_EQ(0x00010100U, bv.GetRawStorageWord(0)); 95 EXPECT_EQ(0x00000001U, bv.GetRawStorageWord(1)); 96 EXPECT_EQ(3U, bv.NumSetBits()); 97 98 bv.SetBit(48); 99 EXPECT_EQ(4U, bv.NumSetBits()); 100 EXPECT_EQ(0x00010100U, bv.GetRawStorageWord(0)); 101 EXPECT_EQ(0x00010001U, bv.GetRawStorageWord(1)); 102 EXPECT_EQ(4U, bv.NumSetBits()); 103 104 EXPECT_EQ(0U, bv.NumSetBits(1)); 105 106 EXPECT_EQ(0U, bv.NumSetBits(8)); 107 EXPECT_EQ(1U, bv.NumSetBits(9)); 108 EXPECT_EQ(1U, bv.NumSetBits(10)); 109 110 EXPECT_EQ(1U, bv.NumSetBits(16)); 111 EXPECT_EQ(2U, bv.NumSetBits(17)); 112 EXPECT_EQ(2U, bv.NumSetBits(18)); 113 114 EXPECT_EQ(2U, bv.NumSetBits(32)); 115 EXPECT_EQ(3U, bv.NumSetBits(33)); 116 EXPECT_EQ(3U, bv.NumSetBits(34)); 117 118 EXPECT_EQ(3U, bv.NumSetBits(48)); 119 EXPECT_EQ(4U, bv.NumSetBits(49)); 120 EXPECT_EQ(4U, bv.NumSetBits(50)); 121 122 EXPECT_EQ(4U, bv.NumSetBits(64)); 123 } 124 125 TEST(BitVector, SetInitialBits) { 126 const uint32_t kWords = 2; 127 128 uint32_t bits[kWords]; 129 memset(bits, 0, sizeof(bits)); 130 131 BitVector bv(false, Allocator::GetNoopAllocator(), kWords, bits); 132 bv.SetInitialBits(0u); 133 EXPECT_EQ(0u, bv.NumSetBits()); 134 bv.SetInitialBits(1u); 135 EXPECT_EQ(1u, bv.NumSetBits()); 136 bv.SetInitialBits(32u); 137 EXPECT_EQ(32u, bv.NumSetBits()); 138 bv.SetInitialBits(63u); 139 EXPECT_EQ(63u, bv.NumSetBits()); 140 bv.SetInitialBits(64u); 141 EXPECT_EQ(64u, bv.NumSetBits()); 142 } 143 144 TEST(BitVector, UnionIfNotIn) { 145 { 146 BitVector first(2, true, Allocator::GetMallocAllocator()); 147 BitVector second(5, true, Allocator::GetMallocAllocator()); 148 BitVector third(5, true, Allocator::GetMallocAllocator()); 149 150 second.SetBit(64); 151 third.SetBit(64); 152 bool changed = first.UnionIfNotIn(&second, &third); 153 EXPECT_EQ(0u, first.NumSetBits()); 154 EXPECT_FALSE(changed); 155 } 156 157 { 158 BitVector first(2, true, Allocator::GetMallocAllocator()); 159 BitVector second(5, true, Allocator::GetMallocAllocator()); 160 BitVector third(5, true, Allocator::GetMallocAllocator()); 161 162 second.SetBit(64); 163 bool changed = first.UnionIfNotIn(&second, &third); 164 EXPECT_EQ(1u, first.NumSetBits()); 165 EXPECT_TRUE(changed); 166 EXPECT_TRUE(first.IsBitSet(64)); 167 } 168 } 169 170 TEST(BitVector, Subset) { 171 { 172 BitVector first(2, true, Allocator::GetMallocAllocator()); 173 BitVector second(5, true, Allocator::GetMallocAllocator()); 174 175 EXPECT_TRUE(first.IsSubsetOf(&second)); 176 second.SetBit(4); 177 EXPECT_TRUE(first.IsSubsetOf(&second)); 178 } 179 180 { 181 BitVector first(5, true, Allocator::GetMallocAllocator()); 182 BitVector second(5, true, Allocator::GetMallocAllocator()); 183 184 first.SetBit(5); 185 EXPECT_FALSE(first.IsSubsetOf(&second)); 186 second.SetBit(4); 187 EXPECT_FALSE(first.IsSubsetOf(&second)); 188 } 189 190 { 191 BitVector first(5, true, Allocator::GetMallocAllocator()); 192 BitVector second(5, true, Allocator::GetMallocAllocator()); 193 194 first.SetBit(16); 195 first.SetBit(32); 196 first.SetBit(48); 197 second.SetBit(16); 198 second.SetBit(32); 199 second.SetBit(48); 200 201 EXPECT_TRUE(first.IsSubsetOf(&second)); 202 second.SetBit(8); 203 EXPECT_TRUE(first.IsSubsetOf(&second)); 204 second.SetBit(40); 205 EXPECT_TRUE(first.IsSubsetOf(&second)); 206 second.SetBit(52); 207 EXPECT_TRUE(first.IsSubsetOf(&second)); 208 209 first.SetBit(9); 210 EXPECT_FALSE(first.IsSubsetOf(&second)); 211 } 212 } 213 214 TEST(BitVector, CopyTo) { 215 { 216 // Test copying an empty BitVector. Padding should fill `buf` with zeroes. 217 BitVector bv(0, true, Allocator::GetMallocAllocator()); 218 uint32_t buf; 219 220 bv.CopyTo(&buf, sizeof(buf)); 221 EXPECT_EQ(0u, bv.GetSizeOf()); 222 EXPECT_EQ(0u, buf); 223 } 224 225 { 226 // Test copying when `bv.storage_` and `buf` are of equal lengths. 227 BitVector bv(0, true, Allocator::GetMallocAllocator()); 228 uint32_t buf; 229 230 bv.SetBit(0); 231 bv.SetBit(17); 232 bv.SetBit(26); 233 EXPECT_EQ(sizeof(buf), bv.GetSizeOf()); 234 235 bv.CopyTo(&buf, sizeof(buf)); 236 EXPECT_EQ(0x04020001u, buf); 237 } 238 239 { 240 // Test copying when the `bv.storage_` is longer than `buf`. As long as 241 // `buf` is long enough to hold all set bits, copying should succeed. 242 BitVector bv(0, true, Allocator::GetMallocAllocator()); 243 uint8_t buf[5]; 244 245 bv.SetBit(18); 246 bv.SetBit(39); 247 EXPECT_LT(sizeof(buf), bv.GetSizeOf()); 248 249 bv.CopyTo(buf, sizeof(buf)); 250 EXPECT_EQ(0x00u, buf[0]); 251 EXPECT_EQ(0x00u, buf[1]); 252 EXPECT_EQ(0x04u, buf[2]); 253 EXPECT_EQ(0x00u, buf[3]); 254 EXPECT_EQ(0x80u, buf[4]); 255 } 256 257 { 258 // Test zero padding when `bv.storage_` is shorter than `buf`. 259 BitVector bv(0, true, Allocator::GetMallocAllocator()); 260 uint32_t buf[2]; 261 262 bv.SetBit(18); 263 bv.SetBit(31); 264 EXPECT_GT(sizeof(buf), bv.GetSizeOf()); 265 266 bv.CopyTo(buf, sizeof(buf)); 267 EXPECT_EQ(0x80040000U, buf[0]); 268 EXPECT_EQ(0x00000000U, buf[1]); 269 } 270 } 271 272 } // namespace art 273
