1 /*
2 * Copyright (C) 2019 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 "src/trace_processor/containers/bit_vector.h"
18
19 #include <bitset>
20 #include <random>
21
22 #include "src/trace_processor/containers/bit_vector_iterators.h"
23 #include "test/gtest_and_gmock.h"
24
25 namespace perfetto {
26 namespace trace_processor {
27 namespace {
28
TEST(BitVectorUnittest,CreateAllTrue)29 TEST(BitVectorUnittest, CreateAllTrue) {
30 BitVector bv(2049, true);
31
32 // Ensure that a selection of interesting bits are set.
33 ASSERT_TRUE(bv.IsSet(0));
34 ASSERT_TRUE(bv.IsSet(1));
35 ASSERT_TRUE(bv.IsSet(511));
36 ASSERT_TRUE(bv.IsSet(512));
37 ASSERT_TRUE(bv.IsSet(2047));
38 ASSERT_TRUE(bv.IsSet(2048));
39 }
40
TEST(BitVectorUnittest,CreateAllFalse)41 TEST(BitVectorUnittest, CreateAllFalse) {
42 BitVector bv(2049, false);
43
44 // Ensure that a selection of interesting bits are cleared.
45 ASSERT_FALSE(bv.IsSet(0));
46 ASSERT_FALSE(bv.IsSet(1));
47 ASSERT_FALSE(bv.IsSet(511));
48 ASSERT_FALSE(bv.IsSet(512));
49 ASSERT_FALSE(bv.IsSet(2047));
50 ASSERT_FALSE(bv.IsSet(2048));
51 }
52
TEST(BitVectorUnittest,Set)53 TEST(BitVectorUnittest, Set) {
54 BitVector bv(2049, false);
55 bv.Set(0);
56 bv.Set(1);
57 bv.Set(511);
58 bv.Set(512);
59 bv.Set(2047);
60
61 // Ensure the bits we touched are set.
62 ASSERT_TRUE(bv.IsSet(0));
63 ASSERT_TRUE(bv.IsSet(1));
64 ASSERT_TRUE(bv.IsSet(511));
65 ASSERT_TRUE(bv.IsSet(512));
66 ASSERT_TRUE(bv.IsSet(2047));
67
68 // Ensure that a selection of other interestinng bits are
69 // still cleared.
70 ASSERT_FALSE(bv.IsSet(2));
71 ASSERT_FALSE(bv.IsSet(63));
72 ASSERT_FALSE(bv.IsSet(64));
73 ASSERT_FALSE(bv.IsSet(510));
74 ASSERT_FALSE(bv.IsSet(513));
75 ASSERT_FALSE(bv.IsSet(1023));
76 ASSERT_FALSE(bv.IsSet(1024));
77 ASSERT_FALSE(bv.IsSet(2046));
78 ASSERT_FALSE(bv.IsSet(2048));
79 ASSERT_FALSE(bv.IsSet(2048));
80 }
81
TEST(BitVectorUnittest,Clear)82 TEST(BitVectorUnittest, Clear) {
83 BitVector bv(2049, true);
84 bv.Clear(0);
85 bv.Clear(1);
86 bv.Clear(511);
87 bv.Clear(512);
88 bv.Clear(2047);
89
90 // Ensure the bits we touched are cleared.
91 ASSERT_FALSE(bv.IsSet(0));
92 ASSERT_FALSE(bv.IsSet(1));
93 ASSERT_FALSE(bv.IsSet(511));
94 ASSERT_FALSE(bv.IsSet(512));
95 ASSERT_FALSE(bv.IsSet(2047));
96
97 // Ensure that a selection of other interestinng bits are
98 // still set.
99 ASSERT_TRUE(bv.IsSet(2));
100 ASSERT_TRUE(bv.IsSet(63));
101 ASSERT_TRUE(bv.IsSet(64));
102 ASSERT_TRUE(bv.IsSet(510));
103 ASSERT_TRUE(bv.IsSet(513));
104 ASSERT_TRUE(bv.IsSet(1023));
105 ASSERT_TRUE(bv.IsSet(1024));
106 ASSERT_TRUE(bv.IsSet(2046));
107 ASSERT_TRUE(bv.IsSet(2048));
108 }
109
TEST(BitVectorUnittest,AppendToEmpty)110 TEST(BitVectorUnittest, AppendToEmpty) {
111 BitVector bv;
112 bv.AppendTrue();
113 bv.AppendFalse();
114
115 ASSERT_EQ(bv.size(), 2u);
116 ASSERT_TRUE(bv.IsSet(0));
117 ASSERT_FALSE(bv.IsSet(1));
118 }
119
TEST(BitVectorUnittest,AppendToExisting)120 TEST(BitVectorUnittest, AppendToExisting) {
121 BitVector bv(2046, false);
122 bv.AppendTrue();
123 bv.AppendFalse();
124 bv.AppendTrue();
125 bv.AppendTrue();
126
127 ASSERT_EQ(bv.size(), 2050u);
128 ASSERT_TRUE(bv.IsSet(2046));
129 ASSERT_FALSE(bv.IsSet(2047));
130 ASSERT_TRUE(bv.IsSet(2048));
131 ASSERT_TRUE(bv.IsSet(2049));
132 }
133
TEST(BitVectorUnittest,CountSetBits)134 TEST(BitVectorUnittest, CountSetBits) {
135 BitVector bv(2049, false);
136 bv.Set(0);
137 bv.Set(1);
138 bv.Set(511);
139 bv.Set(512);
140 bv.Set(2047);
141 bv.Set(2048);
142
143 ASSERT_EQ(bv.CountSetBits(), 6u);
144
145 ASSERT_EQ(bv.CountSetBits(0), 0u);
146 ASSERT_EQ(bv.CountSetBits(1), 1u);
147 ASSERT_EQ(bv.CountSetBits(2), 2u);
148 ASSERT_EQ(bv.CountSetBits(3), 2u);
149 ASSERT_EQ(bv.CountSetBits(511), 2u);
150 ASSERT_EQ(bv.CountSetBits(512), 3u);
151 ASSERT_EQ(bv.CountSetBits(1023), 4u);
152 ASSERT_EQ(bv.CountSetBits(1024), 4u);
153 ASSERT_EQ(bv.CountSetBits(2047), 4u);
154 ASSERT_EQ(bv.CountSetBits(2048), 5u);
155 ASSERT_EQ(bv.CountSetBits(2049), 6u);
156 }
157
TEST(BitVectorUnittest,IndexOfNthSet)158 TEST(BitVectorUnittest, IndexOfNthSet) {
159 BitVector bv(2050, false);
160 bv.Set(0);
161 bv.Set(1);
162 bv.Set(511);
163 bv.Set(512);
164 bv.Set(2047);
165 bv.Set(2048);
166
167 ASSERT_EQ(bv.IndexOfNthSet(0), 0u);
168 ASSERT_EQ(bv.IndexOfNthSet(1), 1u);
169 ASSERT_EQ(bv.IndexOfNthSet(2), 511u);
170 ASSERT_EQ(bv.IndexOfNthSet(3), 512u);
171 ASSERT_EQ(bv.IndexOfNthSet(4), 2047u);
172 ASSERT_EQ(bv.IndexOfNthSet(5), 2048u);
173 }
174
TEST(BitVectorUnittest,Resize)175 TEST(BitVectorUnittest, Resize) {
176 BitVector bv(1, false);
177
178 bv.Resize(2, true);
179 ASSERT_EQ(bv.size(), 2u);
180 ASSERT_EQ(bv.IsSet(1), true);
181
182 bv.Resize(2049, false);
183 ASSERT_EQ(bv.size(), 2049u);
184 ASSERT_EQ(bv.IsSet(2), false);
185 ASSERT_EQ(bv.IsSet(2047), false);
186 ASSERT_EQ(bv.IsSet(2048), false);
187
188 // Set these two bits; the first should be preserved and the
189 // second should disappear.
190 bv.Set(512);
191 bv.Set(513);
192
193 bv.Resize(513, false);
194 ASSERT_EQ(bv.size(), 513u);
195 ASSERT_EQ(bv.IsSet(1), true);
196 ASSERT_EQ(bv.IsSet(512), true);
197 ASSERT_EQ(bv.CountSetBits(), 2u);
198
199 // When we resize up, we need to be sure that the set bit from
200 // before we resized down is not still present as a garbage bit.
201 bv.Resize(514, false);
202 ASSERT_EQ(bv.size(), 514u);
203 ASSERT_EQ(bv.IsSet(513), false);
204 ASSERT_EQ(bv.CountSetBits(), 2u);
205 }
206
TEST(BitVectorUnittest,ResizeHasCorrectCount)207 TEST(BitVectorUnittest, ResizeHasCorrectCount) {
208 BitVector bv(1, false);
209 ASSERT_EQ(bv.CountSetBits(), 0u);
210
211 bv.Resize(1024, true);
212 ASSERT_EQ(bv.CountSetBits(), 1023u);
213 }
214
TEST(BitVectorUnittest,AppendAfterResizeDown)215 TEST(BitVectorUnittest, AppendAfterResizeDown) {
216 BitVector bv(2049, false);
217 bv.Set(2048);
218 ASSERT_TRUE(bv.IsSet(2048));
219 bv.Resize(2048);
220 ASSERT_EQ(bv.size(), 2048u);
221 bv.AppendFalse();
222 ASSERT_EQ(bv.size(), 2049u);
223 ASSERT_FALSE(bv.IsSet(2048));
224 ASSERT_EQ(bv.CountSetBits(), 0u);
225 }
226
TEST(BitVectorUnittest,UpdateSetBits)227 TEST(BitVectorUnittest, UpdateSetBits) {
228 BitVector bv(6, false);
229 bv.Set(1);
230 bv.Set(2);
231 bv.Set(4);
232
233 BitVector picker(3u, true);
234 picker.Clear(1);
235
236 bv.UpdateSetBits(picker);
237
238 ASSERT_TRUE(bv.IsSet(1));
239 ASSERT_FALSE(bv.IsSet(2));
240 ASSERT_TRUE(bv.IsSet(4));
241 }
242
TEST(BitVectorUnittest,UpdateSetBitsSmallerPicker)243 TEST(BitVectorUnittest, UpdateSetBitsSmallerPicker) {
244 BitVector bv(6, false);
245 bv.Set(1);
246 bv.Set(2);
247 bv.Set(4);
248
249 BitVector picker(2u, true);
250 picker.Clear(1);
251
252 bv.UpdateSetBits(picker);
253
254 ASSERT_TRUE(bv.IsSet(1));
255 ASSERT_FALSE(bv.IsSet(2));
256 ASSERT_FALSE(bv.IsSet(4));
257 }
258
TEST(BitVectorUnittest,UpdateSetBitsWordBoundary)259 TEST(BitVectorUnittest, UpdateSetBitsWordBoundary) {
260 BitVector bv(65, true);
261
262 BitVector picker(65u, true);
263 picker.Clear(64);
264
265 bv.UpdateSetBits(picker);
266
267 ASSERT_FALSE(bv.IsSet(64));
268 }
269
TEST(BitVectorUnittest,UpdateSetBitsStress)270 TEST(BitVectorUnittest, UpdateSetBitsStress) {
271 static constexpr uint32_t kCount = 21903;
272 std::minstd_rand0 rand;
273
274 BitVector bv;
275 std::bitset<kCount> bv_std_lib;
276 for (uint32_t i = 0; i < kCount; ++i) {
277 bool res = rand() % 2u;
278 if (res) {
279 bv.AppendTrue();
280 } else {
281 bv.AppendFalse();
282 }
283 bv_std_lib[i] = res;
284 }
285
286 BitVector picker;
287 for (uint32_t i = 0; i < bv_std_lib.count(); ++i) {
288 bool res = rand() % 2u;
289 if (res) {
290 picker.AppendTrue();
291 } else {
292 picker.AppendFalse();
293 }
294 }
295 bv.UpdateSetBits(picker);
296
297 ASSERT_EQ(bv.size(), kCount);
298
299 uint32_t set_bit_i = 0;
300 for (uint32_t i = 0; i < kCount; ++i) {
301 if (bv_std_lib.test(i)) {
302 ASSERT_EQ(bv.IsSet(i), picker.IsSet(set_bit_i++));
303 } else {
304 ASSERT_FALSE(bv.IsSet(i));
305 }
306 }
307 }
308
TEST(BitVectorUnittest,IterateAllBitsConst)309 TEST(BitVectorUnittest, IterateAllBitsConst) {
310 BitVector bv;
311 for (uint32_t i = 0; i < 12345; ++i) {
312 if (i % 7 == 0 || i % 13 == 0) {
313 bv.AppendTrue();
314 } else {
315 bv.AppendFalse();
316 }
317 }
318
319 uint32_t i = 0;
320 for (auto it = bv.IterateAllBits(); it; it.Next(), ++i) {
321 ASSERT_EQ(it.IsSet(), i % 7 == 0 || i % 13 == 0);
322 ASSERT_EQ(it.index(), i);
323 }
324 }
325
TEST(BitVectorUnittest,IterateAllBitsSet)326 TEST(BitVectorUnittest, IterateAllBitsSet) {
327 BitVector bv;
328 for (uint32_t i = 0; i < 12345; ++i) {
329 if (i % 7 == 0 || i % 13 == 0) {
330 bv.AppendTrue();
331 } else {
332 bv.AppendFalse();
333 }
334 }
335
336 // Unset every 15th bit.
337 for (auto it = bv.IterateAllBits(); it; it.Next()) {
338 if (it.index() % 15 == 0) {
339 it.Set();
340 }
341 }
342
343 // Go through the iterator manually and check it has updated
344 // to not have every 15th bit set.
345 uint32_t count = 0;
346 for (uint32_t i = 0; i < 12345; ++i) {
347 bool is_set = i % 15 == 0 || i % 7 == 0 || i % 13 == 0;
348
349 ASSERT_EQ(bv.IsSet(i), is_set);
350 ASSERT_EQ(bv.CountSetBits(i), count);
351
352 if (is_set) {
353 ASSERT_EQ(bv.IndexOfNthSet(count++), i);
354 }
355 }
356 }
357
TEST(BitVectorUnittest,IterateAllBitsClear)358 TEST(BitVectorUnittest, IterateAllBitsClear) {
359 BitVector bv;
360 for (uint32_t i = 0; i < 12345; ++i) {
361 if (i % 7 == 0 || i % 13 == 0) {
362 bv.AppendTrue();
363 } else {
364 bv.AppendFalse();
365 }
366 }
367
368 // Unset every 15th bit.
369 for (auto it = bv.IterateAllBits(); it; it.Next()) {
370 if (it.index() % 15 == 0) {
371 it.Clear();
372 }
373 }
374
375 // Go through the iterator manually and check it has updated
376 // to not have every 15th bit set.
377 uint32_t count = 0;
378 for (uint32_t i = 0; i < 12345; ++i) {
379 bool is_set = i % 15 != 0 && (i % 7 == 0 || i % 13 == 0);
380
381 ASSERT_EQ(bv.IsSet(i), is_set);
382 ASSERT_EQ(bv.CountSetBits(i), count);
383
384 if (is_set) {
385 ASSERT_EQ(bv.IndexOfNthSet(count++), i);
386 }
387 }
388 }
389
TEST(BitVectorUnittest,IterateSetBitsConst)390 TEST(BitVectorUnittest, IterateSetBitsConst) {
391 BitVector bv;
392 std::vector<uint32_t> set_indices;
393 for (uint32_t i = 0; i < 12345; ++i) {
394 if (i % 7 == 0 || i % 13 == 0) {
395 bv.AppendTrue();
396 set_indices.emplace_back(i);
397 } else {
398 bv.AppendFalse();
399 }
400 }
401
402 uint32_t i = 0;
403 for (auto it = bv.IterateSetBits(); it; it.Next(), ++i) {
404 ASSERT_EQ(it.IsSet(), true);
405 ASSERT_EQ(it.index(), set_indices[i]);
406 }
407 ASSERT_EQ(i, set_indices.size());
408 }
409
TEST(BitVectorUnittest,IterateSetBitsClear)410 TEST(BitVectorUnittest, IterateSetBitsClear) {
411 BitVector bv;
412 for (uint32_t i = 0; i < 12345; ++i) {
413 if (i % 7 == 0 || i % 13 == 0) {
414 bv.AppendTrue();
415 } else {
416 bv.AppendFalse();
417 }
418 }
419
420 for (auto it = bv.IterateSetBits(); it; it.Next()) {
421 if (it.index() % 15 == 0) {
422 it.Clear();
423 }
424 }
425
426 // Go through the iterator manually and check it has updated
427 // to not have every 15th bit set.
428 uint32_t count = 0;
429 for (uint32_t i = 0; i < 12345; ++i) {
430 bool is_set = i % 15 != 0 && (i % 7 == 0 || i % 13 == 0);
431
432 ASSERT_EQ(bv.IsSet(i), is_set);
433 ASSERT_EQ(bv.CountSetBits(i), count);
434
435 if (is_set) {
436 ASSERT_EQ(bv.IndexOfNthSet(count++), i);
437 }
438 }
439 }
440
TEST(BitVectorUnittest,IterateSetBitsStartsCorrectly)441 TEST(BitVectorUnittest, IterateSetBitsStartsCorrectly) {
442 BitVector bv;
443 bv.AppendFalse();
444 bv.AppendTrue();
445
446 auto it = bv.IterateSetBits();
447 ASSERT_TRUE(it);
448 ASSERT_EQ(it.index(), 1u);
449 ASSERT_TRUE(it.IsSet());
450
451 it.Next();
452 ASSERT_FALSE(it);
453 }
454
TEST(BitVectorUnittest,IntersectRange)455 TEST(BitVectorUnittest, IntersectRange) {
456 BitVector bv = BitVector::Range(1, 20, [](uint32_t t) { return t % 2 == 0; });
457 BitVector intersected = bv.IntersectRange(3, 10);
458
459 ASSERT_EQ(intersected.IndexOfNthSet(0), 4u);
460 ASSERT_EQ(intersected.CountSetBits(), 3u);
461 }
462
TEST(BitVectorUnittest,IntersectRangeFromStart)463 TEST(BitVectorUnittest, IntersectRangeFromStart) {
464 BitVector bv = BitVector::Range(1, 20, [](uint32_t t) { return t % 2 == 0; });
465 BitVector intersected = bv.IntersectRange(0, 10);
466
467 ASSERT_EQ(intersected.IndexOfNthSet(0), 2u);
468 ASSERT_EQ(intersected.CountSetBits(), 4u);
469 }
470
TEST(BitVectorUnittest,IntersectRange2)471 TEST(BitVectorUnittest, IntersectRange2) {
472 BitVector bv{true, false, true, true, false, true};
473 BitVector intersected = bv.IntersectRange(2, 4);
474
475 ASSERT_EQ(intersected.IndexOfNthSet(0), 2u);
476 }
477
TEST(BitVectorUnittest,IntersectRangeAfterWord)478 TEST(BitVectorUnittest, IntersectRangeAfterWord) {
479 BitVector bv =
480 BitVector::Range(64 + 1, 64 + 20, [](uint32_t t) { return t % 2 == 0; });
481 BitVector intersected = bv.IntersectRange(64 + 3, 64 + 10);
482
483 ASSERT_EQ(intersected.IndexOfNthSet(0), 64 + 4u);
484 ASSERT_EQ(intersected.CountSetBits(), 3u);
485 }
486
TEST(BitVectorUnittest,IntersectRangeSetBitsBeforeRange)487 TEST(BitVectorUnittest, IntersectRangeSetBitsBeforeRange) {
488 BitVector bv = BitVector::Range(10, 30, [](uint32_t t) { return t < 15; });
489 BitVector intersected = bv.IntersectRange(16, 50);
490
491 ASSERT_FALSE(intersected.CountSetBits());
492 }
493
TEST(BitVectorUnittest,IntersectRangeSetBitOnBoundary)494 TEST(BitVectorUnittest, IntersectRangeSetBitOnBoundary) {
495 BitVector bv = BitVector(10, false);
496 bv.Set(5);
497 BitVector intersected = bv.IntersectRange(5, 20);
498
499 ASSERT_EQ(intersected.CountSetBits(), 1u);
500 ASSERT_EQ(intersected.IndexOfNthSet(0), 5u);
501 }
502
TEST(BitVectorUnittest,IntersectRangeStressTest)503 TEST(BitVectorUnittest, IntersectRangeStressTest) {
504 BitVector bv =
505 BitVector::Range(65, 1024 + 1, [](uint32_t t) { return t % 2 == 0; });
506 BitVector intersected = bv.IntersectRange(30, 500);
507
508 ASSERT_EQ(intersected.IndexOfNthSet(0), 66u);
509 ASSERT_EQ(intersected.CountSetBits(), 217u);
510 }
511
TEST(BitVectorUnittest,Range)512 TEST(BitVectorUnittest, Range) {
513 BitVector bv = BitVector::Range(1, 9, [](uint32_t t) { return t % 3 == 0; });
514 ASSERT_EQ(bv.size(), 9u);
515
516 ASSERT_FALSE(bv.IsSet(0));
517 ASSERT_TRUE(bv.IsSet(3));
518 ASSERT_TRUE(bv.IsSet(6));
519
520 ASSERT_EQ(bv.CountSetBits(), 2u);
521 }
522
TEST(BitVectorUnittest,RangeStressTest)523 TEST(BitVectorUnittest, RangeStressTest) {
524 BitVector bv =
525 BitVector::Range(1, 1025, [](uint32_t t) { return t % 3 == 0; });
526 ASSERT_EQ(bv.size(), 1025u);
527 ASSERT_FALSE(bv.IsSet(0));
528 for (uint32_t i = 1; i < 1025; ++i) {
529 ASSERT_EQ(i % 3 == 0, bv.IsSet(i));
530 }
531 ASSERT_EQ(bv.CountSetBits(), 341u);
532 }
533
TEST(BitVectorUnittest,BuilderSkip)534 TEST(BitVectorUnittest, BuilderSkip) {
535 BitVector::Builder builder(128);
536
537 builder.Skip(127);
538 builder.Append(1);
539
540 BitVector bv = std::move(builder).Build();
541 ASSERT_EQ(bv.size(), 128u);
542
543 ASSERT_FALSE(bv.IsSet(10));
544 ASSERT_FALSE(bv.IsSet(126));
545 ASSERT_TRUE(bv.IsSet(127));
546 }
547
TEST(BitVectorUnittest,BuilderBitsInCompleteWordsUntilFull)548 TEST(BitVectorUnittest, BuilderBitsInCompleteWordsUntilFull) {
549 BitVector::Builder builder(128 + 1);
550
551 ASSERT_EQ(builder.BitsInCompleteWordsUntilFull(), 128u);
552 }
553
TEST(BitVectorUnittest,BuilderBitsUntilWordBoundaryOrFull)554 TEST(BitVectorUnittest, BuilderBitsUntilWordBoundaryOrFull) {
555 BitVector::Builder builder(41);
556
557 ASSERT_EQ(builder.BitsUntilWordBoundaryOrFull(), 41u);
558 }
559
TEST(BitVectorUnittest,Builder)560 TEST(BitVectorUnittest, Builder) {
561 BitVector::Builder builder(128);
562
563 // 100100011010001010110011110001001 as a hex literal.
564 builder.AppendWord(0x123456789);
565 builder.AppendWord(0xFF);
566
567 BitVector bv = std::move(builder).Build();
568 ASSERT_EQ(bv.size(), 128u);
569
570 ASSERT_TRUE(bv.IsSet(0));
571 ASSERT_FALSE(bv.IsSet(1));
572 ASSERT_FALSE(bv.IsSet(2));
573 }
574
TEST(BitVectorUnittest,BuilderCountSetBits)575 TEST(BitVectorUnittest, BuilderCountSetBits) {
576 // 16 words and 1 bit
577 BitVector::Builder builder(1025);
578
579 // 100100011010001010110011110001001 as a hex literal, with 15 set bits.
580 uint64_t word = 0x123456789;
581 for (uint32_t i = 0; i < 16; ++i) {
582 builder.AppendWord(word);
583 }
584 builder.Append(1);
585 BitVector bv = std::move(builder).Build();
586
587 ASSERT_EQ(bv.CountSetBits(500), 120u);
588 ASSERT_EQ(bv.CountSetBits(), 16 * 15 + 1u);
589 }
590
TEST(BitVectorUnittest,BuilderStressTest)591 TEST(BitVectorUnittest, BuilderStressTest) {
592 // Space for 128 words and 1 bit
593 uint32_t size = 8 * 1024 + 1;
594 BitVector::Builder builder(size);
595
596 // 15 full words + 40 bits
597 for (uint32_t i = 0; i < 1000; ++i) {
598 builder.Append(1);
599 }
600 ASSERT_EQ(builder.BitsUntilFull(), size - 1000);
601
602 // 24 bits to hit word boundary. We filled 16 words now.
603 for (uint32_t i = 0; i < 24; ++i) {
604 builder.Append(0);
605 }
606 ASSERT_EQ(builder.BitsUntilFull(), size - 1024);
607 ASSERT_EQ(builder.BitsUntilWordBoundaryOrFull(), 0u);
608
609 // 100100011010001010110011110001001 as a hex literal, with 15 set bits.
610 uint64_t word = 0x123456789;
611
612 // Add all of the remaining words.
613 ASSERT_EQ(builder.BitsInCompleteWordsUntilFull(), (128 - 16) * 64u);
614 ASSERT_EQ(builder.BitsUntilFull(), (128 - 16) * 64u + 1);
615 for (uint32_t i = 0; i < (128 - 16); ++i) {
616 builder.AppendWord(word);
617 }
618
619 ASSERT_EQ(builder.BitsUntilWordBoundaryOrFull(), 0u);
620 ASSERT_EQ(builder.BitsUntilFull(), 1u);
621
622 // One last bit.
623 builder.Append(1);
624
625 BitVector bv = std::move(builder).Build();
626
627 ASSERT_EQ(bv.CountSetBits(), 2681u);
628 ASSERT_EQ(bv.size(), 8u * 1024u + 1u);
629
630 ASSERT_TRUE(bv.IsSet(0));
631 ASSERT_FALSE(bv.IsSet(1000));
632
633 ASSERT_TRUE(bv.IsSet(1024));
634 ASSERT_FALSE(bv.IsSet(1025));
635
636 ASSERT_TRUE(bv.IsSet(8 * 1024));
637 }
638
TEST(BitVectorUnittest,Not)639 TEST(BitVectorUnittest, Not) {
640 BitVector bv(10);
641 bv.Set(2);
642
643 BitVector not_bv = bv.Not();
644 EXPECT_FALSE(not_bv.IsSet(2));
645 EXPECT_EQ(not_bv.CountSetBits(), 9u);
646 }
647
TEST(BitVectorUnittest,QueryStressTest)648 TEST(BitVectorUnittest, QueryStressTest) {
649 BitVector bv;
650 std::vector<bool> bool_vec;
651 std::vector<uint32_t> int_vec;
652
653 static constexpr uint32_t kCount = 4096;
654 std::minstd_rand0 rand;
655 for (uint32_t i = 0; i < kCount; ++i) {
656 bool res = rand() % 2u;
657 if (res) {
658 bv.AppendTrue();
659 } else {
660 bv.AppendFalse();
661 }
662 bool_vec.push_back(res);
663 if (res)
664 int_vec.emplace_back(i);
665 }
666
667 auto all_it = bv.IterateAllBits();
668 for (uint32_t i = 0; i < kCount; ++i) {
669 uint32_t count = static_cast<uint32_t>(std::count(
670 bool_vec.begin(), bool_vec.begin() + static_cast<int32_t>(i), true));
671 ASSERT_EQ(bv.IsSet(i), bool_vec[i]);
672 ASSERT_EQ(bv.CountSetBits(i), count);
673
674 ASSERT_TRUE(all_it);
675 ASSERT_EQ(all_it.IsSet(), bool_vec[i]);
676 ASSERT_EQ(all_it.index(), i);
677 all_it.Next();
678 }
679 ASSERT_FALSE(all_it);
680
681 auto set_it = bv.IterateSetBits();
682 for (uint32_t i = 0; i < int_vec.size(); ++i) {
683 ASSERT_EQ(bv.IndexOfNthSet(i), int_vec[i]);
684
685 ASSERT_TRUE(set_it);
686 ASSERT_EQ(set_it.IsSet(), true);
687 ASSERT_EQ(set_it.index(), int_vec[i]);
688 set_it.Next();
689 }
690 ASSERT_FALSE(set_it);
691 }
692
693 } // namespace
694 } // namespace trace_processor
695 } // namespace perfetto
696