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 #include <random>
19
20 #include "allocator.h"
21 #include "base/stl_util.h"
22 #include "bit_vector-inl.h"
23 #include "gtest/gtest.h"
24 #include "transform_iterator.h"
25
26 namespace art {
27
TEST(BitVector,Test)28 TEST(BitVector, Test) {
29 const size_t kBits = 32;
30
31 BitVector bv(kBits, false, Allocator::GetMallocAllocator());
32 EXPECT_EQ(1U, bv.GetStorageSize());
33 EXPECT_EQ(sizeof(uint32_t), bv.GetSizeOf());
34 EXPECT_FALSE(bv.IsExpandable());
35
36 EXPECT_EQ(0U, bv.NumSetBits());
37 EXPECT_EQ(0U, bv.NumSetBits(1));
38 EXPECT_EQ(0U, bv.NumSetBits(kBits));
39 for (size_t i = 0; i < kBits; i++) {
40 EXPECT_FALSE(bv.IsBitSet(i));
41 }
42 EXPECT_EQ(0U, bv.GetRawStorageWord(0));
43 EXPECT_EQ(0U, *bv.GetRawStorage());
44
45 EXPECT_TRUE(bv.Indexes().begin().Done());
46 EXPECT_TRUE(bv.Indexes().begin() == bv.Indexes().end());
47
48 bv.SetBit(0);
49 bv.SetBit(kBits - 1);
50 EXPECT_EQ(2U, bv.NumSetBits());
51 EXPECT_EQ(1U, bv.NumSetBits(1));
52 EXPECT_EQ(2U, bv.NumSetBits(kBits));
53 EXPECT_TRUE(bv.IsBitSet(0));
54 for (size_t i = 1; i < kBits - 1; i++) {
55 EXPECT_FALSE(bv.IsBitSet(i));
56 }
57 EXPECT_TRUE(bv.IsBitSet(kBits - 1));
58 EXPECT_EQ(0x80000001U, bv.GetRawStorageWord(0));
59 EXPECT_EQ(0x80000001U, *bv.GetRawStorage());
60
61 BitVector::IndexIterator iterator = bv.Indexes().begin();
62 EXPECT_TRUE(iterator != bv.Indexes().end());
63 EXPECT_EQ(0u, *iterator);
64 ++iterator;
65 EXPECT_TRUE(iterator != bv.Indexes().end());
66 EXPECT_EQ(kBits - 1u, *iterator);
67 ++iterator;
68 EXPECT_TRUE(iterator == bv.Indexes().end());
69 }
70
71 struct MessyAllocator : public Allocator {
72 public:
MessyAllocatorart::MessyAllocator73 MessyAllocator() : malloc_(Allocator::GetMallocAllocator()) {}
~MessyAllocatorart::MessyAllocator74 ~MessyAllocator() {}
75
Allocart::MessyAllocator76 void* Alloc(size_t s) override {
77 void* res = malloc_->Alloc(s);
78 memset(res, 0xfe, s);
79 return res;
80 }
81
Freeart::MessyAllocator82 void Free(void* v) override {
83 malloc_->Free(v);
84 }
85
86 private:
87 Allocator* malloc_;
88 };
89
TEST(BitVector,MessyAllocator)90 TEST(BitVector, MessyAllocator) {
91 MessyAllocator alloc;
92 BitVector bv(32, false, &alloc);
93 EXPECT_EQ(bv.NumSetBits(), 0u);
94 EXPECT_EQ(bv.GetHighestBitSet(), -1);
95 }
96
TEST(BitVector,NoopAllocator)97 TEST(BitVector, NoopAllocator) {
98 const uint32_t kWords = 2;
99
100 uint32_t bits[kWords];
101 memset(bits, 0, sizeof(bits));
102
103 BitVector bv(false, Allocator::GetNoopAllocator(), kWords, bits);
104 EXPECT_EQ(kWords, bv.GetStorageSize());
105 EXPECT_EQ(kWords * sizeof(uint32_t), bv.GetSizeOf());
106 EXPECT_EQ(bits, bv.GetRawStorage());
107 EXPECT_EQ(0U, bv.NumSetBits());
108
109 bv.SetBit(8);
110 EXPECT_EQ(1U, bv.NumSetBits());
111 EXPECT_EQ(0x00000100U, bv.GetRawStorageWord(0));
112 EXPECT_EQ(0x00000000U, bv.GetRawStorageWord(1));
113 EXPECT_EQ(1U, bv.NumSetBits());
114
115 bv.SetBit(16);
116 EXPECT_EQ(2U, bv.NumSetBits());
117 EXPECT_EQ(0x00010100U, bv.GetRawStorageWord(0));
118 EXPECT_EQ(0x00000000U, bv.GetRawStorageWord(1));
119 EXPECT_EQ(2U, bv.NumSetBits());
120
121 bv.SetBit(32);
122 EXPECT_EQ(3U, bv.NumSetBits());
123 EXPECT_EQ(0x00010100U, bv.GetRawStorageWord(0));
124 EXPECT_EQ(0x00000001U, bv.GetRawStorageWord(1));
125 EXPECT_EQ(3U, bv.NumSetBits());
126
127 bv.SetBit(48);
128 EXPECT_EQ(4U, bv.NumSetBits());
129 EXPECT_EQ(0x00010100U, bv.GetRawStorageWord(0));
130 EXPECT_EQ(0x00010001U, bv.GetRawStorageWord(1));
131 EXPECT_EQ(4U, bv.NumSetBits());
132
133 EXPECT_EQ(0U, bv.NumSetBits(1));
134
135 EXPECT_EQ(0U, bv.NumSetBits(8));
136 EXPECT_EQ(1U, bv.NumSetBits(9));
137 EXPECT_EQ(1U, bv.NumSetBits(10));
138
139 EXPECT_EQ(1U, bv.NumSetBits(16));
140 EXPECT_EQ(2U, bv.NumSetBits(17));
141 EXPECT_EQ(2U, bv.NumSetBits(18));
142
143 EXPECT_EQ(2U, bv.NumSetBits(32));
144 EXPECT_EQ(3U, bv.NumSetBits(33));
145 EXPECT_EQ(3U, bv.NumSetBits(34));
146
147 EXPECT_EQ(3U, bv.NumSetBits(48));
148 EXPECT_EQ(4U, bv.NumSetBits(49));
149 EXPECT_EQ(4U, bv.NumSetBits(50));
150
151 EXPECT_EQ(4U, bv.NumSetBits(64));
152 }
153
TEST(BitVector,SetInitialBits)154 TEST(BitVector, SetInitialBits) {
155 const uint32_t kWords = 2;
156
157 uint32_t bits[kWords];
158 memset(bits, 0, sizeof(bits));
159
160 BitVector bv(false, Allocator::GetNoopAllocator(), kWords, bits);
161 bv.SetInitialBits(0u);
162 EXPECT_EQ(0u, bv.NumSetBits());
163 bv.SetInitialBits(1u);
164 EXPECT_EQ(1u, bv.NumSetBits());
165 bv.SetInitialBits(32u);
166 EXPECT_EQ(32u, bv.NumSetBits());
167 bv.SetInitialBits(63u);
168 EXPECT_EQ(63u, bv.NumSetBits());
169 bv.SetInitialBits(64u);
170 EXPECT_EQ(64u, bv.NumSetBits());
171 }
172
TEST(BitVector,UnionIfNotIn)173 TEST(BitVector, UnionIfNotIn) {
174 {
175 BitVector first(2, true, Allocator::GetMallocAllocator());
176 BitVector second(5, true, Allocator::GetMallocAllocator());
177 BitVector third(5, true, Allocator::GetMallocAllocator());
178
179 second.SetBit(64);
180 third.SetBit(64);
181 bool changed = first.UnionIfNotIn(&second, &third);
182 EXPECT_EQ(0u, first.NumSetBits());
183 EXPECT_FALSE(changed);
184 }
185
186 {
187 BitVector first(2, true, Allocator::GetMallocAllocator());
188 BitVector second(5, true, Allocator::GetMallocAllocator());
189 BitVector third(5, true, Allocator::GetMallocAllocator());
190
191 second.SetBit(64);
192 bool changed = first.UnionIfNotIn(&second, &third);
193 EXPECT_EQ(1u, first.NumSetBits());
194 EXPECT_TRUE(changed);
195 EXPECT_TRUE(first.IsBitSet(64));
196 }
197 }
198
TEST(BitVector,Subset)199 TEST(BitVector, Subset) {
200 {
201 BitVector first(2, true, Allocator::GetMallocAllocator());
202 BitVector second(5, true, Allocator::GetMallocAllocator());
203
204 EXPECT_TRUE(first.IsSubsetOf(&second));
205 second.SetBit(4);
206 EXPECT_TRUE(first.IsSubsetOf(&second));
207 }
208
209 {
210 BitVector first(5, true, Allocator::GetMallocAllocator());
211 BitVector second(5, true, Allocator::GetMallocAllocator());
212
213 first.SetBit(5);
214 EXPECT_FALSE(first.IsSubsetOf(&second));
215 second.SetBit(4);
216 EXPECT_FALSE(first.IsSubsetOf(&second));
217 }
218
219 {
220 BitVector first(5, true, Allocator::GetMallocAllocator());
221 BitVector second(5, true, Allocator::GetMallocAllocator());
222
223 first.SetBit(16);
224 first.SetBit(32);
225 first.SetBit(48);
226 second.SetBit(16);
227 second.SetBit(32);
228 second.SetBit(48);
229
230 EXPECT_TRUE(first.IsSubsetOf(&second));
231 second.SetBit(8);
232 EXPECT_TRUE(first.IsSubsetOf(&second));
233 second.SetBit(40);
234 EXPECT_TRUE(first.IsSubsetOf(&second));
235 second.SetBit(52);
236 EXPECT_TRUE(first.IsSubsetOf(&second));
237
238 first.SetBit(9);
239 EXPECT_FALSE(first.IsSubsetOf(&second));
240 }
241 }
242
TEST(BitVector,CopyTo)243 TEST(BitVector, CopyTo) {
244 {
245 // Test copying an empty BitVector. Padding should fill `buf` with zeroes.
246 BitVector bv(0, true, Allocator::GetMallocAllocator());
247 uint32_t buf;
248
249 bv.CopyTo(&buf, sizeof(buf));
250 EXPECT_EQ(0u, bv.GetSizeOf());
251 EXPECT_EQ(0u, buf);
252 }
253
254 {
255 // Test copying when `bv.storage_` and `buf` are of equal lengths.
256 BitVector bv(0, true, Allocator::GetMallocAllocator());
257 uint32_t buf;
258
259 bv.SetBit(0);
260 bv.SetBit(17);
261 bv.SetBit(26);
262 EXPECT_EQ(sizeof(buf), bv.GetSizeOf());
263
264 bv.CopyTo(&buf, sizeof(buf));
265 EXPECT_EQ(0x04020001u, buf);
266 }
267
268 {
269 // Test copying when the `bv.storage_` is longer than `buf`. As long as
270 // `buf` is long enough to hold all set bits, copying should succeed.
271 BitVector bv(0, true, Allocator::GetMallocAllocator());
272 uint8_t buf[5];
273
274 bv.SetBit(18);
275 bv.SetBit(39);
276 EXPECT_LT(sizeof(buf), bv.GetSizeOf());
277
278 bv.CopyTo(buf, sizeof(buf));
279 EXPECT_EQ(0x00u, buf[0]);
280 EXPECT_EQ(0x00u, buf[1]);
281 EXPECT_EQ(0x04u, buf[2]);
282 EXPECT_EQ(0x00u, buf[3]);
283 EXPECT_EQ(0x80u, buf[4]);
284 }
285
286 {
287 // Test zero padding when `bv.storage_` is shorter than `buf`.
288 BitVector bv(0, true, Allocator::GetMallocAllocator());
289 uint32_t buf[2];
290
291 bv.SetBit(18);
292 bv.SetBit(31);
293 EXPECT_GT(sizeof(buf), bv.GetSizeOf());
294
295 bv.CopyTo(buf, sizeof(buf));
296 EXPECT_EQ(0x80040000U, buf[0]);
297 EXPECT_EQ(0x00000000U, buf[1]);
298 }
299 }
300
TEST(BitVector,TransformIterator)301 TEST(BitVector, TransformIterator) {
302 BitVector bv(16, false, Allocator::GetMallocAllocator());
303 bv.SetBit(4);
304 bv.SetBit(8);
305
306 auto indexs = bv.Indexes();
307 for (int32_t negative :
308 MakeTransformRange(indexs, [](uint32_t idx) { return -1 * static_cast<int32_t>(idx); })) {
309 EXPECT_TRUE(negative == -4 || negative == -8);
310 }
311 }
312
313 class SingleAllocator : public Allocator {
314 public:
SingleAllocator()315 SingleAllocator() : alloc_count_(0), free_count_(0) {}
~SingleAllocator()316 ~SingleAllocator() {
317 EXPECT_EQ(alloc_count_, 1u);
318 EXPECT_EQ(free_count_, 1u);
319 }
320
Alloc(size_t s)321 void* Alloc(size_t s) override {
322 EXPECT_LT(s, 1024ull);
323 EXPECT_EQ(alloc_count_, free_count_);
324 ++alloc_count_;
325 return bytes_.begin();
326 }
327
Free(void *)328 void Free(void*) override {
329 ++free_count_;
330 }
331
AllocCount() const332 uint32_t AllocCount() const {
333 return alloc_count_;
334 }
FreeCount() const335 uint32_t FreeCount() const {
336 return free_count_;
337 }
338
339 private:
340 std::array<uint8_t, 1024> bytes_;
341 uint32_t alloc_count_;
342 uint32_t free_count_;
343 };
344
TEST(BitVector,MovementFree)345 TEST(BitVector, MovementFree) {
346 SingleAllocator alloc;
347 {
348 BitVector bv(16, false, &alloc);
349 bv.SetBit(13);
350 EXPECT_EQ(alloc.FreeCount(), 0u);
351 EXPECT_EQ(alloc.AllocCount(), 1u);
352 ASSERT_TRUE(bv.GetRawStorage() != nullptr);
353 EXPECT_TRUE(bv.IsBitSet(13));
354 {
355 BitVector bv2(std::move(bv));
356 ASSERT_TRUE(bv.GetRawStorage() == nullptr);
357 EXPECT_TRUE(bv2.IsBitSet(13));
358 EXPECT_EQ(alloc.FreeCount(), 0u);
359 EXPECT_EQ(alloc.AllocCount(), 1u);
360 }
361 EXPECT_EQ(alloc.FreeCount(), 1u);
362 EXPECT_EQ(alloc.AllocCount(), 1u);
363 }
364 EXPECT_EQ(alloc.FreeCount(), 1u);
365 EXPECT_EQ(alloc.AllocCount(), 1u);
366 }
367
TEST(BitVector,ArrayCol)368 TEST(BitVector, ArrayCol) {
369 {
370 BitVectorArray bva(100, 200, true, Allocator::GetMallocAllocator());
371 for (uint32_t i : Range(bva.NumColumns())) {
372 bva.SetBit(bva.NumRows() / 2, i);
373 }
374 EXPECT_EQ(bva.GetRawData().NumSetBits(), bva.NumColumns());
375 }
376 {
377 BitVectorArray bva(100, 200, true, Allocator::GetMallocAllocator());
378 for (uint32_t i : Range(bva.NumRows())) {
379 bva.SetBit(i, bva.NumColumns() / 2);
380 }
381 EXPECT_EQ(bva.GetRawData().NumSetBits(), bva.NumRows());
382 }
383 }
384
TEST(BitVector,ArrayUnion)385 TEST(BitVector, ArrayUnion) {
386 {
387 BitVectorArray bva(100, 200, true, Allocator::GetMallocAllocator());
388 bva.SetBit(4, 12);
389 bva.SetBit(40, 120);
390 bva.SetBit(40, 121);
391 bva.SetBit(40, 122);
392
393 bva.UnionRows(4, 40);
394
395 EXPECT_TRUE(bva.IsBitSet(4, 12));
396 EXPECT_TRUE(bva.IsBitSet(4, 120));
397 EXPECT_TRUE(bva.IsBitSet(4, 121));
398 EXPECT_TRUE(bva.IsBitSet(4, 122));
399 EXPECT_FALSE(bva.IsBitSet(40, 12));
400 EXPECT_TRUE(bva.IsBitSet(40, 120));
401 EXPECT_TRUE(bva.IsBitSet(40, 121));
402 EXPECT_TRUE(bva.IsBitSet(40, 122));
403 EXPECT_EQ(bva.GetRawData().NumSetBits(), 7u);
404 }
405 {
406 BitVectorArray bva(100, 100, true, Allocator::GetMallocAllocator());
407 for (uint32_t i : Range(bva.NumRows())) {
408 bva.SetBit(i, i);
409 }
410 for (uint32_t i : Range(1, bva.NumRows())) {
411 bva.UnionRows(0, i);
412 }
413 for (uint32_t col : Range(bva.NumColumns())) {
414 for (uint32_t row : Range(bva.NumRows())) {
415 // We set every bit where row== column and every bit on row 0 up to number of rows.
416 EXPECT_EQ(bva.IsBitSet(row, col), row == col || (row == 0 && col < bva.NumRows()));
417 }
418 }
419 }
420 }
421
422 } // namespace art
423