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 <cstdint>
21 #include <random>
22 #include <utility>
23 #include <vector>
24
25 #include "perfetto/protozero/scattered_heap_buffer.h"
26 #include "test/gtest_and_gmock.h"
27
28 #include "protos/perfetto/trace_processor/serialization.pbzero.h"
29
30 namespace perfetto::trace_processor {
31 namespace {
32 using testing::ElementsAre;
33 using testing::IsEmpty;
34 using testing::UnorderedElementsAre;
35
TEST(BitVectorUnittest,CreateAllTrue)36 TEST(BitVectorUnittest, CreateAllTrue) {
37 BitVector bv(2049, true);
38
39 // Ensure that a selection of interesting bits are set.
40 ASSERT_TRUE(bv.IsSet(0));
41 ASSERT_TRUE(bv.IsSet(1));
42 ASSERT_TRUE(bv.IsSet(511));
43 ASSERT_TRUE(bv.IsSet(512));
44 ASSERT_TRUE(bv.IsSet(2047));
45 ASSERT_TRUE(bv.IsSet(2048));
46 }
47
TEST(BitVectorUnittest,CreateAllFalse)48 TEST(BitVectorUnittest, CreateAllFalse) {
49 BitVector bv(2049, false);
50
51 // Ensure that a selection of interesting bits are cleared.
52 ASSERT_FALSE(bv.IsSet(0));
53 ASSERT_FALSE(bv.IsSet(1));
54 ASSERT_FALSE(bv.IsSet(511));
55 ASSERT_FALSE(bv.IsSet(512));
56 ASSERT_FALSE(bv.IsSet(2047));
57 ASSERT_FALSE(bv.IsSet(2048));
58 }
59
TEST(BitVectorUnittest,Set)60 TEST(BitVectorUnittest, Set) {
61 BitVector bv(2049, false);
62 bv.Set(0);
63 bv.Set(1);
64 bv.Set(511);
65 bv.Set(512);
66 bv.Set(2047);
67
68 // Ensure the bits we touched are set.
69 ASSERT_TRUE(bv.IsSet(0));
70 ASSERT_TRUE(bv.IsSet(1));
71 ASSERT_TRUE(bv.IsSet(511));
72 ASSERT_TRUE(bv.IsSet(512));
73 ASSERT_TRUE(bv.IsSet(2047));
74
75 // Ensure that a selection of other interestinng bits are
76 // still cleared.
77 ASSERT_FALSE(bv.IsSet(2));
78 ASSERT_FALSE(bv.IsSet(63));
79 ASSERT_FALSE(bv.IsSet(64));
80 ASSERT_FALSE(bv.IsSet(510));
81 ASSERT_FALSE(bv.IsSet(513));
82 ASSERT_FALSE(bv.IsSet(1023));
83 ASSERT_FALSE(bv.IsSet(1024));
84 ASSERT_FALSE(bv.IsSet(2046));
85 ASSERT_FALSE(bv.IsSet(2048));
86 ASSERT_FALSE(bv.IsSet(2048));
87 }
88
TEST(BitVectorUnittest,Clear)89 TEST(BitVectorUnittest, Clear) {
90 BitVector bv(2049, true);
91 bv.Clear(0);
92 bv.Clear(1);
93 bv.Clear(511);
94 bv.Clear(512);
95 bv.Clear(2047);
96
97 // Ensure the bits we touched are cleared.
98 ASSERT_FALSE(bv.IsSet(0));
99 ASSERT_FALSE(bv.IsSet(1));
100 ASSERT_FALSE(bv.IsSet(511));
101 ASSERT_FALSE(bv.IsSet(512));
102 ASSERT_FALSE(bv.IsSet(2047));
103
104 // Ensure that a selection of other interestinng bits are
105 // still set.
106 ASSERT_TRUE(bv.IsSet(2));
107 ASSERT_TRUE(bv.IsSet(63));
108 ASSERT_TRUE(bv.IsSet(64));
109 ASSERT_TRUE(bv.IsSet(510));
110 ASSERT_TRUE(bv.IsSet(513));
111 ASSERT_TRUE(bv.IsSet(1023));
112 ASSERT_TRUE(bv.IsSet(1024));
113 ASSERT_TRUE(bv.IsSet(2046));
114 ASSERT_TRUE(bv.IsSet(2048));
115 }
116
TEST(BitVectorUnittest,AppendToEmpty)117 TEST(BitVectorUnittest, AppendToEmpty) {
118 BitVector bv;
119 bv.AppendTrue();
120 bv.AppendFalse();
121
122 ASSERT_EQ(bv.size(), 2u);
123 ASSERT_TRUE(bv.IsSet(0));
124 ASSERT_FALSE(bv.IsSet(1));
125 }
126
TEST(BitVectorUnittest,AppendToExisting)127 TEST(BitVectorUnittest, AppendToExisting) {
128 BitVector bv(2046, false);
129 bv.AppendTrue();
130 bv.AppendFalse();
131 bv.AppendTrue();
132 bv.AppendTrue();
133
134 ASSERT_EQ(bv.size(), 2050u);
135 ASSERT_TRUE(bv.IsSet(2046));
136 ASSERT_FALSE(bv.IsSet(2047));
137 ASSERT_TRUE(bv.IsSet(2048));
138 ASSERT_TRUE(bv.IsSet(2049));
139 }
140
TEST(BitVectorUnittest,CountSetBits)141 TEST(BitVectorUnittest, CountSetBits) {
142 BitVector bv(2049, false);
143 bv.Set(0);
144 bv.Set(1);
145 bv.Set(511);
146 bv.Set(512);
147 bv.Set(2047);
148 bv.Set(2048);
149
150 ASSERT_EQ(bv.CountSetBits(), 6u);
151
152 ASSERT_EQ(bv.CountSetBits(0), 0u);
153 ASSERT_EQ(bv.CountSetBits(1), 1u);
154 ASSERT_EQ(bv.CountSetBits(2), 2u);
155 ASSERT_EQ(bv.CountSetBits(3), 2u);
156 ASSERT_EQ(bv.CountSetBits(511), 2u);
157 ASSERT_EQ(bv.CountSetBits(512), 3u);
158 ASSERT_EQ(bv.CountSetBits(1023), 4u);
159 ASSERT_EQ(bv.CountSetBits(1024), 4u);
160 ASSERT_EQ(bv.CountSetBits(2047), 4u);
161 ASSERT_EQ(bv.CountSetBits(2048), 5u);
162 ASSERT_EQ(bv.CountSetBits(2049), 6u);
163 }
164
TEST(BitVectorUnittest,IndexOfNthSet)165 TEST(BitVectorUnittest, IndexOfNthSet) {
166 BitVector bv(2050, false);
167 bv.Set(0);
168 bv.Set(1);
169 bv.Set(511);
170 bv.Set(512);
171 bv.Set(2047);
172 bv.Set(2048);
173
174 ASSERT_EQ(bv.IndexOfNthSet(0), 0u);
175 ASSERT_EQ(bv.IndexOfNthSet(1), 1u);
176 ASSERT_EQ(bv.IndexOfNthSet(2), 511u);
177 ASSERT_EQ(bv.IndexOfNthSet(3), 512u);
178 ASSERT_EQ(bv.IndexOfNthSet(4), 2047u);
179 ASSERT_EQ(bv.IndexOfNthSet(5), 2048u);
180 }
181
TEST(BitVectorUnittest,Resize)182 TEST(BitVectorUnittest, Resize) {
183 BitVector bv(1, false);
184
185 bv.Resize(2, true);
186 ASSERT_EQ(bv.size(), 2u);
187 ASSERT_EQ(bv.IsSet(1), true);
188
189 bv.Resize(2049, false);
190 ASSERT_EQ(bv.size(), 2049u);
191 ASSERT_EQ(bv.IsSet(2), false);
192 ASSERT_EQ(bv.IsSet(2047), false);
193 ASSERT_EQ(bv.IsSet(2048), false);
194
195 // Set these two bits; the first should be preserved and the
196 // second should disappear.
197 bv.Set(512);
198 bv.Set(513);
199
200 bv.Resize(513, false);
201 ASSERT_EQ(bv.size(), 513u);
202 ASSERT_EQ(bv.IsSet(1), true);
203 ASSERT_EQ(bv.IsSet(512), true);
204 ASSERT_EQ(bv.CountSetBits(), 2u);
205
206 // When we resize up, we need to be sure that the set bit from
207 // before we resized down is not still present as a garbage bit.
208 bv.Resize(514, false);
209 ASSERT_EQ(bv.size(), 514u);
210 ASSERT_EQ(bv.IsSet(513), false);
211 ASSERT_EQ(bv.CountSetBits(), 2u);
212 }
213
TEST(BitVectorUnittest,ResizeHasCorrectCount)214 TEST(BitVectorUnittest, ResizeHasCorrectCount) {
215 BitVector bv(1, false);
216 ASSERT_EQ(bv.CountSetBits(), 0u);
217
218 bv.Resize(1024, true);
219 ASSERT_EQ(bv.CountSetBits(), 1023u);
220 }
221
TEST(BitVectorUnittest,AppendAfterResizeDown)222 TEST(BitVectorUnittest, AppendAfterResizeDown) {
223 BitVector bv(2049, false);
224 bv.Set(2048);
225 ASSERT_TRUE(bv.IsSet(2048));
226 bv.Resize(2048);
227 ASSERT_EQ(bv.size(), 2048u);
228 bv.AppendFalse();
229 ASSERT_EQ(bv.size(), 2049u);
230 ASSERT_FALSE(bv.IsSet(2048));
231 ASSERT_EQ(bv.CountSetBits(), 0u);
232 }
233
TEST(BitVectorUnittest,UpdateSetBits)234 TEST(BitVectorUnittest, UpdateSetBits) {
235 BitVector bv(6, false);
236 bv.Set(1);
237 bv.Set(2);
238 bv.Set(4);
239
240 BitVector picker(3u, true);
241 picker.Clear(1);
242
243 bv.UpdateSetBits(picker);
244
245 ASSERT_TRUE(bv.IsSet(1));
246 ASSERT_FALSE(bv.IsSet(2));
247 ASSERT_TRUE(bv.IsSet(4));
248 }
249
TEST(BitVectorUnittest,UpdateSetBitsSmallerPicker)250 TEST(BitVectorUnittest, UpdateSetBitsSmallerPicker) {
251 BitVector bv(6, false);
252 bv.Set(1);
253 bv.Set(2);
254 bv.Set(4);
255
256 BitVector picker(2u, true);
257 picker.Clear(1);
258
259 bv.UpdateSetBits(picker);
260
261 ASSERT_TRUE(bv.IsSet(1));
262 ASSERT_FALSE(bv.IsSet(2));
263 ASSERT_FALSE(bv.IsSet(4));
264 }
265
TEST(BitVectorUnittest,UpdateSetBitsWordBoundary)266 TEST(BitVectorUnittest, UpdateSetBitsWordBoundary) {
267 BitVector bv(65, true);
268
269 BitVector picker(65u, true);
270 picker.Clear(64);
271
272 bv.UpdateSetBits(picker);
273
274 ASSERT_FALSE(bv.IsSet(64));
275 }
276
TEST(BitVectorUnittest,UpdateSetBitsStress)277 TEST(BitVectorUnittest, UpdateSetBitsStress) {
278 static constexpr uint32_t kCount = 21903;
279 std::minstd_rand0 rand;
280
281 BitVector bv;
282 std::bitset<kCount> bv_std_lib;
283 for (uint32_t i = 0; i < kCount; ++i) {
284 bool res = rand() % 2u;
285 if (res) {
286 bv.AppendTrue();
287 } else {
288 bv.AppendFalse();
289 }
290 bv_std_lib[i] = res;
291 }
292
293 BitVector picker;
294 for (uint32_t i = 0; i < bv_std_lib.count(); ++i) {
295 bool res = rand() % 2u;
296 if (res) {
297 picker.AppendTrue();
298 } else {
299 picker.AppendFalse();
300 }
301 }
302 bv.UpdateSetBits(picker);
303
304 ASSERT_EQ(bv.size(), kCount);
305
306 uint32_t set_bit_i = 0;
307 for (uint32_t i = 0; i < kCount; ++i) {
308 if (bv_std_lib.test(i)) {
309 ASSERT_EQ(bv.IsSet(i), picker.IsSet(set_bit_i++));
310 } else {
311 ASSERT_FALSE(bv.IsSet(i));
312 }
313 }
314 }
315
TEST(BitVectorUnittest,SelectBitsSimple)316 TEST(BitVectorUnittest, SelectBitsSimple) {
317 BitVector bv = {true, false, true, false, true, true, true};
318 BitVector mask = {true, false, true, true, false, false, true};
319 bv.SelectBits(mask);
320
321 ASSERT_EQ(bv.size(), 4u);
322 ASSERT_EQ(bv.IsSet(0), true);
323 ASSERT_EQ(bv.IsSet(1), true);
324 ASSERT_EQ(bv.IsSet(2), false);
325 ASSERT_EQ(bv.IsSet(3), true);
326 ASSERT_EQ(bv.CountSetBits(), 3u);
327 }
328
TEST(BitVectorUnittest,SelectBitsSmallerMain)329 TEST(BitVectorUnittest, SelectBitsSmallerMain) {
330 BitVector bv = {true, false, true, false};
331 BitVector mask = {true, false, true, true, false, false, true};
332 bv.SelectBits(mask);
333
334 ASSERT_EQ(bv.size(), 3u);
335 ASSERT_EQ(bv.IsSet(0), true);
336 ASSERT_EQ(bv.IsSet(1), true);
337 ASSERT_EQ(bv.IsSet(2), false);
338 ASSERT_EQ(bv.CountSetBits(), 2u);
339 }
340
TEST(BitVectorUnittest,SelectBitsLarge)341 TEST(BitVectorUnittest, SelectBitsLarge) {
342 BitVector bv = BitVector::RangeForTesting(
343 0, 813, [](uint32_t idx) { return idx % 7 == 0; });
344 BitVector mask = BitVector::RangeForTesting(
345 0, 813, [](uint32_t idx) { return idx % 3 == 0; });
346 bv.SelectBits(mask);
347
348 BitVector expected = BitVector::RangeForTesting(
349 0, 271u, [](uint32_t idx) { return (idx * 3) % 7 == 0; });
350
351 ASSERT_EQ(bv.size(), 271u);
352 for (uint32_t i = 0; i < expected.size(); ++i) {
353 ASSERT_EQ(expected.IsSet(i), bv.IsSet(i)) << "Index " << i;
354 ASSERT_EQ(expected.CountSetBits(i), bv.CountSetBits(i)) << "Index " << i;
355 }
356 ASSERT_EQ(expected.CountSetBits(), bv.CountSetBits());
357 }
358
TEST(BitVectorUnittest,SelectBitsLargeSmallerMain)359 TEST(BitVectorUnittest, SelectBitsLargeSmallerMain) {
360 BitVector bv = BitVector::RangeForTesting(
361 0, 279, [](uint32_t idx) { return idx % 7 == 0; });
362 BitVector mask = BitVector::RangeForTesting(
363 0, 813, [](uint32_t idx) { return idx % 3 == 0; });
364 bv.SelectBits(mask);
365
366 BitVector expected = BitVector::RangeForTesting(
367 0, 93, [](uint32_t idx) { return (idx * 3) % 7 == 0; });
368
369 ASSERT_EQ(bv.size(), 93u);
370 for (uint32_t i = 0; i < expected.size(); ++i) {
371 ASSERT_EQ(expected.IsSet(i), bv.IsSet(i)) << "Index " << i;
372 ASSERT_EQ(expected.CountSetBits(i), bv.CountSetBits(i)) << "Index " << i;
373 }
374 ASSERT_EQ(expected.CountSetBits(), bv.CountSetBits());
375 }
376
TEST(BitVectorUnittest,SelectBitsDense)377 TEST(BitVectorUnittest, SelectBitsDense) {
378 BitVector bv =
379 BitVector::RangeForTesting(0, 279, [](uint32_t) { return true; });
380 BitVector mask =
381 BitVector::RangeForTesting(0, 279, [](uint32_t idx) { return idx < 80; });
382 bv.SelectBits(mask);
383
384 BitVector expected =
385 BitVector::RangeForTesting(0, 80, [](uint32_t) { return true; });
386
387 ASSERT_EQ(bv.size(), 80u);
388 for (uint32_t i = 0; i < expected.size(); ++i) {
389 ASSERT_EQ(expected.IsSet(i), bv.IsSet(i)) << "Index " << i;
390 ASSERT_EQ(expected.CountSetBits(i), bv.CountSetBits(i)) << "Index " << i;
391 }
392 ASSERT_EQ(expected.CountSetBits(), bv.CountSetBits());
393 }
394
TEST(BitVectorUnittest,SelectBitsEnd)395 TEST(BitVectorUnittest, SelectBitsEnd) {
396 BitVector bv = BitVector::RangeForTesting(
397 0, 279, [](uint32_t idx) { return idx % 7 == 0; });
398 BitVector mask = BitVector::RangeForTesting(
399 0, 813, [](uint32_t idx) { return idx % 3 == 0; });
400 bv.SelectBits(mask);
401
402 BitVector expected = BitVector::RangeForTesting(
403 0, 93, [](uint32_t idx) { return (idx * 3) % 7 == 0; });
404
405 ASSERT_EQ(bv.size(), 93u);
406 for (uint32_t i = 0; i < expected.size(); ++i) {
407 ASSERT_EQ(expected.IsSet(i), bv.IsSet(i)) << "Index " << i;
408 ASSERT_EQ(expected.CountSetBits(i), bv.CountSetBits(i)) << "Index " << i;
409 }
410 ASSERT_EQ(expected.CountSetBits(), bv.CountSetBits());
411 }
412
TEST(BitVectorUnittest,SelectBitsOob)413 TEST(BitVectorUnittest, SelectBitsOob) {
414 BitVector bv = BitVector::RangeForTesting(
415 0, 512, [](uint32_t idx) { return idx % 7 == 0; });
416 BitVector mask = BitVector(512, true);
417 bv.SelectBits(mask);
418
419 BitVector expected = BitVector::RangeForTesting(
420 0, 512, [](uint32_t idx) { return idx % 7 == 0; });
421
422 ASSERT_EQ(bv.size(), 512u);
423 for (uint32_t i = 0; i < expected.size(); ++i) {
424 ASSERT_EQ(expected.IsSet(i), bv.IsSet(i)) << "Index " << i;
425 ASSERT_EQ(expected.CountSetBits(i), bv.CountSetBits(i)) << "Index " << i;
426 }
427 ASSERT_EQ(expected.CountSetBits(), bv.CountSetBits());
428 }
429
TEST(BitVectorUnittest,IntersectRange)430 TEST(BitVectorUnittest, IntersectRange) {
431 BitVector bv =
432 BitVector::RangeForTesting(1, 20, [](uint32_t t) { return t % 2 == 0; });
433 BitVector intersected = bv.IntersectRange(3, 10);
434
435 ASSERT_EQ(intersected.IndexOfNthSet(0), 4u);
436 ASSERT_EQ(intersected.CountSetBits(), 3u);
437 }
438
TEST(BitVectorUnittest,IntersectRangeFromStart)439 TEST(BitVectorUnittest, IntersectRangeFromStart) {
440 BitVector bv =
441 BitVector::RangeForTesting(1, 20, [](uint32_t t) { return t % 2 == 0; });
442 BitVector intersected = bv.IntersectRange(0, 10);
443
444 ASSERT_EQ(intersected.IndexOfNthSet(0), 2u);
445 ASSERT_EQ(intersected.CountSetBits(), 4u);
446 }
447
TEST(BitVectorUnittest,IntersectRange2)448 TEST(BitVectorUnittest, IntersectRange2) {
449 BitVector bv{true, false, true, true, false, true};
450 BitVector intersected = bv.IntersectRange(2, 4);
451
452 ASSERT_EQ(intersected.IndexOfNthSet(0), 2u);
453 }
454
TEST(BitVectorUnittest,IntersectRangeAfterWord)455 TEST(BitVectorUnittest, IntersectRangeAfterWord) {
456 BitVector bv = BitVector::RangeForTesting(
457 64 + 1, 64 + 20, [](uint32_t t) { return t % 2 == 0; });
458 BitVector intersected = bv.IntersectRange(64 + 3, 64 + 10);
459
460 ASSERT_EQ(intersected.IndexOfNthSet(0), 64 + 4u);
461 ASSERT_EQ(intersected.CountSetBits(), 3u);
462 }
463
TEST(BitVectorUnittest,IntersectRangeSetBitsBeforeRange)464 TEST(BitVectorUnittest, IntersectRangeSetBitsBeforeRange) {
465 BitVector bv =
466 BitVector::RangeForTesting(10, 30, [](uint32_t t) { return t < 15; });
467 BitVector intersected = bv.IntersectRange(16, 50);
468
469 ASSERT_FALSE(intersected.CountSetBits());
470 }
471
TEST(BitVectorUnittest,IntersectRangeSetBitOnBoundary)472 TEST(BitVectorUnittest, IntersectRangeSetBitOnBoundary) {
473 BitVector bv = BitVector(10, false);
474 bv.Set(5);
475 BitVector intersected = bv.IntersectRange(5, 20);
476
477 ASSERT_EQ(intersected.CountSetBits(), 1u);
478 ASSERT_EQ(intersected.IndexOfNthSet(0), 5u);
479 }
480
TEST(BitVectorUnittest,IntersectRangeStressTest)481 TEST(BitVectorUnittest, IntersectRangeStressTest) {
482 BitVector bv = BitVector::RangeForTesting(
483 65, 1024 + 1, [](uint32_t t) { return t % 2 == 0; });
484 BitVector intersected = bv.IntersectRange(30, 500);
485
486 ASSERT_EQ(intersected.IndexOfNthSet(0), 66u);
487 ASSERT_EQ(intersected.CountSetBits(), 217u);
488 }
489
TEST(BitVectorUnittest,IntersectRangeAppendFalse)490 TEST(BitVectorUnittest, IntersectRangeAppendFalse) {
491 BitVector bv(70u, true);
492 BitVector out = bv.IntersectRange(10, 12u);
493 out.Resize(70u);
494
495 ASSERT_TRUE(out.IsSet(10u));
496 ASSERT_TRUE(out.IsSet(11u));
497 ASSERT_FALSE(out.IsSet(12u));
498 ASSERT_FALSE(out.IsSet(60u));
499 ASSERT_FALSE(out.IsSet(69u));
500 }
501
TEST(BitVectorUnittest,Range)502 TEST(BitVectorUnittest, Range) {
503 BitVector bv =
504 BitVector::RangeForTesting(1, 9, [](uint32_t t) { return t % 3 == 0; });
505 ASSERT_EQ(bv.size(), 9u);
506
507 ASSERT_FALSE(bv.IsSet(0));
508 ASSERT_TRUE(bv.IsSet(3));
509 ASSERT_TRUE(bv.IsSet(6));
510
511 ASSERT_EQ(bv.CountSetBits(), 2u);
512 }
513
TEST(BitVectorUnittest,RangeStressTest)514 TEST(BitVectorUnittest, RangeStressTest) {
515 BitVector bv = BitVector::RangeForTesting(
516 1, 1025, [](uint32_t t) { return t % 3 == 0; });
517 ASSERT_EQ(bv.size(), 1025u);
518 ASSERT_FALSE(bv.IsSet(0));
519 for (uint32_t i = 1; i < 1025; ++i) {
520 ASSERT_EQ(i % 3 == 0, bv.IsSet(i));
521 }
522 ASSERT_EQ(bv.CountSetBits(), 341u);
523 }
524
TEST(BitVectorUnittest,BuilderSkip)525 TEST(BitVectorUnittest, BuilderSkip) {
526 BitVector::Builder builder(128, 127);
527 builder.Append(1);
528
529 BitVector bv = std::move(builder).Build();
530 ASSERT_EQ(bv.size(), 128u);
531
532 ASSERT_FALSE(bv.IsSet(10));
533 ASSERT_FALSE(bv.IsSet(126));
534 ASSERT_TRUE(bv.IsSet(127));
535 }
536
TEST(BitVectorUnittest,BuilderSkipAll)537 TEST(BitVectorUnittest, BuilderSkipAll) {
538 BitVector::Builder builder(128, 128);
539 BitVector bv = std::move(builder).Build();
540
541 ASSERT_EQ(bv.size(), 128u);
542 ASSERT_EQ(bv.CountSetBits(), 0u);
543 }
544
TEST(BitVectorUnittest,BuilderBitsInCompleteWordsUntilFull)545 TEST(BitVectorUnittest, BuilderBitsInCompleteWordsUntilFull) {
546 BitVector::Builder builder(128 + 1);
547
548 ASSERT_EQ(builder.BitsInCompleteWordsUntilFull(), 128u);
549 }
550
TEST(BitVectorUnittest,BuilderBitsUntilWordBoundaryOrFull)551 TEST(BitVectorUnittest, BuilderBitsUntilWordBoundaryOrFull) {
552 BitVector::Builder builder(41);
553
554 ASSERT_EQ(builder.BitsUntilWordBoundaryOrFull(), 41u);
555 }
556
TEST(BitVectorUnittest,Builder)557 TEST(BitVectorUnittest, Builder) {
558 BitVector::Builder builder(128);
559
560 // 100100011010001010110011110001001 as a hex literal.
561 builder.AppendWord(0x123456789);
562 builder.AppendWord(0xFF);
563
564 BitVector bv = std::move(builder).Build();
565 ASSERT_EQ(bv.size(), 128u);
566
567 ASSERT_TRUE(bv.IsSet(0));
568 ASSERT_FALSE(bv.IsSet(1));
569 ASSERT_FALSE(bv.IsSet(2));
570 }
571
TEST(BitVectorUnittest,BuilderCountSetBits)572 TEST(BitVectorUnittest, BuilderCountSetBits) {
573 // 16 words and 1 bit
574 BitVector::Builder builder(1025);
575
576 // 100100011010001010110011110001001 as a hex literal, with 15 set bits.
577 uint64_t word = 0x123456789;
578 for (uint32_t i = 0; i < 16; ++i) {
579 builder.AppendWord(word);
580 }
581 builder.Append(1);
582 BitVector bv = std::move(builder).Build();
583
584 ASSERT_EQ(bv.CountSetBits(500), 120u);
585 ASSERT_EQ(bv.CountSetBits(), 16 * 15 + 1u);
586 }
587
TEST(BitVectorUnittest,BuilderStressTest)588 TEST(BitVectorUnittest, BuilderStressTest) {
589 // Space for 128 words and 1 bit
590 uint32_t size = 8 * 1024 + 1;
591 BitVector::Builder builder(size);
592
593 // 15 full words + 40 bits
594 for (uint32_t i = 0; i < 1000; ++i) {
595 builder.Append(1);
596 }
597 ASSERT_EQ(builder.BitsUntilFull(), size - 1000);
598
599 // 24 bits to hit word boundary. We filled 16 words now.
600 for (uint32_t i = 0; i < 24; ++i) {
601 builder.Append(0);
602 }
603 ASSERT_EQ(builder.BitsUntilFull(), size - 1024);
604 ASSERT_EQ(builder.BitsUntilWordBoundaryOrFull(), 0u);
605
606 // 100100011010001010110011110001001 as a hex literal, with 15 set bits.
607 uint64_t word = 0x123456789;
608
609 // Add all of the remaining words.
610 ASSERT_EQ(builder.BitsInCompleteWordsUntilFull(), (128 - 16) * 64u);
611 ASSERT_EQ(builder.BitsUntilFull(), (128 - 16) * 64u + 1);
612 for (uint32_t i = 0; i < (128 - 16); ++i) {
613 builder.AppendWord(word);
614 }
615
616 ASSERT_EQ(builder.BitsUntilWordBoundaryOrFull(), 0u);
617 ASSERT_EQ(builder.BitsUntilFull(), 1u);
618
619 // One last bit.
620 builder.Append(1);
621
622 BitVector bv = std::move(builder).Build();
623
624 ASSERT_EQ(bv.CountSetBits(), 2681u);
625 ASSERT_EQ(bv.size(), 8u * 1024u + 1u);
626
627 ASSERT_TRUE(bv.IsSet(0));
628 ASSERT_FALSE(bv.IsSet(1000));
629
630 ASSERT_TRUE(bv.IsSet(1024));
631 ASSERT_FALSE(bv.IsSet(1025));
632
633 ASSERT_TRUE(bv.IsSet(8 * 1024));
634 }
635
TEST(BitVectorUnittest,FromSortedIndexVectorEmpty)636 TEST(BitVectorUnittest, FromSortedIndexVectorEmpty) {
637 std::vector<int64_t> indices{};
638 BitVector bv = BitVector::FromSortedIndexVector(indices);
639
640 ASSERT_EQ(bv.size(), 0u);
641 }
642
TEST(BitVectorUnittest,FromSortedIndexVector)643 TEST(BitVectorUnittest, FromSortedIndexVector) {
644 std::vector<int64_t> indices{0, 100, 200, 2000};
645 BitVector bv = BitVector::FromSortedIndexVector(indices);
646
647 ASSERT_EQ(bv.size(), 2001u);
648 ASSERT_EQ(bv.CountSetBits(), 4u);
649 ASSERT_TRUE(bv.IsSet(0));
650 ASSERT_TRUE(bv.IsSet(100));
651 ASSERT_TRUE(bv.IsSet(200));
652 ASSERT_TRUE(bv.IsSet(2000));
653 }
654
TEST(BitVectorUnittest,FromSortedIndexVectorStressTestLargeValues)655 TEST(BitVectorUnittest, FromSortedIndexVectorStressTestLargeValues) {
656 std::vector<int64_t> indices{0, 1 << 2, 1 << 10, 1 << 20, 1 << 30};
657 BitVector bv = BitVector::FromSortedIndexVector(indices);
658
659 ASSERT_EQ(bv.size(), (1 << 30) + 1u);
660 ASSERT_EQ(bv.CountSetBits(), 5u);
661 ASSERT_TRUE(bv.IsSet(0));
662 ASSERT_TRUE(bv.IsSet(1 << 2));
663 ASSERT_TRUE(bv.IsSet(1 << 10));
664 ASSERT_TRUE(bv.IsSet(1 << 20));
665 ASSERT_TRUE(bv.IsSet(1 << 30));
666 }
667
TEST(BitVectorUnittest,FromUnsortedIndexVectorEmpty)668 TEST(BitVectorUnittest, FromUnsortedIndexVectorEmpty) {
669 std::vector<uint32_t> indices{};
670 BitVector bv = BitVector::FromUnsortedIndexVector(indices);
671
672 ASSERT_EQ(bv.size(), 0u);
673 }
674
TEST(BitVectorUnittest,FromUnsortedIndexVector)675 TEST(BitVectorUnittest, FromUnsortedIndexVector) {
676 std::vector<uint32_t> indices{0, 2000, 200, 100};
677 BitVector bv = BitVector::FromUnsortedIndexVector(indices);
678
679 ASSERT_EQ(bv.size(), 2001u);
680 ASSERT_EQ(bv.CountSetBits(), 4u);
681 ASSERT_TRUE(bv.IsSet(0));
682 ASSERT_TRUE(bv.IsSet(100));
683 ASSERT_TRUE(bv.IsSet(200));
684 ASSERT_TRUE(bv.IsSet(2000));
685 }
686
TEST(BitVectorUnittest,FromUnsortedIndexVectorStressTestLargeValues)687 TEST(BitVectorUnittest, FromUnsortedIndexVectorStressTestLargeValues) {
688 std::vector<uint32_t> indices{0, 1 << 30, 1 << 10, 1 << 2, 1 << 20};
689 BitVector bv = BitVector::FromUnsortedIndexVector(indices);
690
691 ASSERT_EQ(bv.size(), (1 << 30) + 1u);
692 ASSERT_EQ(bv.CountSetBits(), 5u);
693 ASSERT_TRUE(bv.IsSet(0));
694 ASSERT_TRUE(bv.IsSet(1 << 2));
695 ASSERT_TRUE(bv.IsSet(1 << 10));
696 ASSERT_TRUE(bv.IsSet(1 << 20));
697 ASSERT_TRUE(bv.IsSet(1 << 30));
698 }
699
TEST(BitVectorUnittest,Not)700 TEST(BitVectorUnittest, Not) {
701 BitVector bv(10);
702 bv.Set(2);
703 bv.Not();
704
705 EXPECT_FALSE(bv.IsSet(2));
706 EXPECT_EQ(bv.CountSetBits(), 9u);
707 EXPECT_THAT(bv.GetSetBitIndices(),
708 UnorderedElementsAre(0u, 1u, 3u, 4u, 5u, 6u, 7u, 8u, 9u));
709 }
710
TEST(BitVectorUnittest,NotBig)711 TEST(BitVectorUnittest, NotBig) {
712 BitVector bv = BitVector::RangeForTesting(
713 0, 1026, [](uint32_t i) { return i % 5 == 0; });
714 bv.Not();
715
716 EXPECT_EQ(bv.CountSetBits(), 820u);
717 }
718
TEST(BitVectorUnittest,NotAppendAfter)719 TEST(BitVectorUnittest, NotAppendAfter) {
720 BitVector bv(30);
721 bv.Not();
722 bv.AppendFalse();
723
724 ASSERT_FALSE(bv.IsSet(30));
725 }
726
TEST(BitVectorUnittest,Or)727 TEST(BitVectorUnittest, Or) {
728 BitVector bv{1, 1, 0, 0};
729 BitVector bv_second{1, 0, 1, 0};
730 bv.Or(bv_second);
731
732 ASSERT_EQ(bv.CountSetBits(), 3u);
733 ASSERT_TRUE(bv.Set(0));
734 ASSERT_TRUE(bv.Set(1));
735 ASSERT_TRUE(bv.Set(2));
736 }
737
TEST(BitVectorUnittest,OrBig)738 TEST(BitVectorUnittest, OrBig) {
739 BitVector bv = BitVector::RangeForTesting(
740 0, 1025, [](uint32_t i) { return i % 5 == 0; });
741 BitVector bv_sec = BitVector::RangeForTesting(
742 0, 1025, [](uint32_t i) { return i % 3 == 0; });
743 bv.Or(bv_sec);
744
745 BitVector bv_or = BitVector::RangeForTesting(
746 0, 1025, [](uint32_t i) { return i % 5 == 0 || i % 3 == 0; });
747
748 ASSERT_EQ(bv.CountSetBits(), bv_or.CountSetBits());
749 }
750
TEST(BitVectorUnittest,QueryStressTest)751 TEST(BitVectorUnittest, QueryStressTest) {
752 BitVector bv;
753 std::vector<bool> bool_vec;
754 std::vector<uint32_t> int_vec;
755
756 static constexpr uint32_t kCount = 4096;
757 std::minstd_rand0 rand;
758 for (uint32_t i = 0; i < kCount; ++i) {
759 bool res = rand() % 2u;
760 if (res) {
761 bv.AppendTrue();
762 } else {
763 bv.AppendFalse();
764 }
765 bool_vec.push_back(res);
766 if (res)
767 int_vec.emplace_back(i);
768 }
769 }
770
TEST(BitVectorUnittest,GetSetBitIndices)771 TEST(BitVectorUnittest, GetSetBitIndices) {
772 BitVector bv = {true, false, true, false, true, true, false, false};
773 ASSERT_THAT(bv.GetSetBitIndices(), ElementsAre(0u, 2u, 4u, 5u));
774 }
775
TEST(BitVectorUnittest,GetSetBitIndicesIntersectRange)776 TEST(BitVectorUnittest, GetSetBitIndicesIntersectRange) {
777 BitVector bv(130u, true);
778 BitVector out = bv.IntersectRange(10, 12);
779 ASSERT_THAT(out.GetSetBitIndices(), ElementsAre(10, 11));
780 }
781
TEST(BitVectorUnittest,UpdateSetBitsGetSetBitIndices)782 TEST(BitVectorUnittest, UpdateSetBitsGetSetBitIndices) {
783 BitVector bv(130u, true);
784 bv.UpdateSetBits(BitVector(60u));
785 ASSERT_THAT(bv.GetSetBitIndices(), IsEmpty());
786 }
787
TEST(BitVectorUnittest,SerializeSimple)788 TEST(BitVectorUnittest, SerializeSimple) {
789 BitVector bv{1, 0, 1, 0, 1, 0, 1};
790 protozero::HeapBuffered<protos::pbzero::SerializedColumn::BitVector> msg;
791 bv.Serialize(msg.get());
792 auto buffer = msg.SerializeAsArray();
793
794 protos::pbzero::SerializedColumn::BitVector::Decoder decoder(buffer.data(),
795 buffer.size());
796 ASSERT_EQ(decoder.size(), 7u);
797 }
798
TEST(BitVectorUnittest,SerializeDeserializeSimple)799 TEST(BitVectorUnittest, SerializeDeserializeSimple) {
800 BitVector bv{1, 0, 1, 0, 1, 0, 1};
801 protozero::HeapBuffered<protos::pbzero::SerializedColumn::BitVector> msg;
802 bv.Serialize(msg.get());
803 auto buffer = msg.SerializeAsArray();
804
805 protos::pbzero::SerializedColumn::BitVector::Decoder decoder(buffer.data(),
806 buffer.size());
807
808 BitVector des;
809 des.Deserialize(decoder);
810
811 ASSERT_EQ(des.size(), 7u);
812 ASSERT_EQ(des.CountSetBits(), 4u);
813
814 ASSERT_TRUE(des.IsSet(0));
815 ASSERT_TRUE(des.IsSet(2));
816 ASSERT_TRUE(des.IsSet(4));
817 ASSERT_TRUE(des.IsSet(6));
818 }
819
820 } // namespace
821 } // namespace perfetto::trace_processor
822