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 <random>
20
21 #include "src/trace_processor/containers/bit_vector_iterators.h"
22 #include "test/gtest_and_gmock.h"
23
24 namespace perfetto {
25 namespace trace_processor {
26 namespace {
27
TEST(BitVectorUnittest,CreateAllTrue)28 TEST(BitVectorUnittest, CreateAllTrue) {
29 BitVector bv(2049, true);
30
31 // Ensure that a selection of interesting bits are set.
32 ASSERT_TRUE(bv.IsSet(0));
33 ASSERT_TRUE(bv.IsSet(1));
34 ASSERT_TRUE(bv.IsSet(511));
35 ASSERT_TRUE(bv.IsSet(512));
36 ASSERT_TRUE(bv.IsSet(2047));
37 ASSERT_TRUE(bv.IsSet(2048));
38 }
39
TEST(BitVectorUnittest,CreateAllFalse)40 TEST(BitVectorUnittest, CreateAllFalse) {
41 BitVector bv(2049, false);
42
43 // Ensure that a selection of interesting bits are cleared.
44 ASSERT_FALSE(bv.IsSet(0));
45 ASSERT_FALSE(bv.IsSet(1));
46 ASSERT_FALSE(bv.IsSet(511));
47 ASSERT_FALSE(bv.IsSet(512));
48 ASSERT_FALSE(bv.IsSet(2047));
49 ASSERT_FALSE(bv.IsSet(2048));
50 }
51
TEST(BitVectorUnittest,Set)52 TEST(BitVectorUnittest, Set) {
53 BitVector bv(2049, false);
54 bv.Set(0);
55 bv.Set(1);
56 bv.Set(511);
57 bv.Set(512);
58 bv.Set(2047);
59
60 // Ensure the bits we touched are set.
61 ASSERT_TRUE(bv.IsSet(0));
62 ASSERT_TRUE(bv.IsSet(1));
63 ASSERT_TRUE(bv.IsSet(511));
64 ASSERT_TRUE(bv.IsSet(512));
65 ASSERT_TRUE(bv.IsSet(2047));
66
67 // Ensure that a selection of other interestinng bits are
68 // still cleared.
69 ASSERT_FALSE(bv.IsSet(2));
70 ASSERT_FALSE(bv.IsSet(63));
71 ASSERT_FALSE(bv.IsSet(64));
72 ASSERT_FALSE(bv.IsSet(510));
73 ASSERT_FALSE(bv.IsSet(513));
74 ASSERT_FALSE(bv.IsSet(1023));
75 ASSERT_FALSE(bv.IsSet(1024));
76 ASSERT_FALSE(bv.IsSet(2046));
77 ASSERT_FALSE(bv.IsSet(2048));
78 ASSERT_FALSE(bv.IsSet(2048));
79 }
80
TEST(BitVectorUnittest,Clear)81 TEST(BitVectorUnittest, Clear) {
82 BitVector bv(2049, true);
83 bv.Clear(0);
84 bv.Clear(1);
85 bv.Clear(511);
86 bv.Clear(512);
87 bv.Clear(2047);
88
89 // Ensure the bits we touched are cleared.
90 ASSERT_FALSE(bv.IsSet(0));
91 ASSERT_FALSE(bv.IsSet(1));
92 ASSERT_FALSE(bv.IsSet(511));
93 ASSERT_FALSE(bv.IsSet(512));
94 ASSERT_FALSE(bv.IsSet(2047));
95
96 // Ensure that a selection of other interestinng bits are
97 // still set.
98 ASSERT_TRUE(bv.IsSet(2));
99 ASSERT_TRUE(bv.IsSet(63));
100 ASSERT_TRUE(bv.IsSet(64));
101 ASSERT_TRUE(bv.IsSet(510));
102 ASSERT_TRUE(bv.IsSet(513));
103 ASSERT_TRUE(bv.IsSet(1023));
104 ASSERT_TRUE(bv.IsSet(1024));
105 ASSERT_TRUE(bv.IsSet(2046));
106 ASSERT_TRUE(bv.IsSet(2048));
107 }
108
TEST(BitVectorUnittest,AppendToEmpty)109 TEST(BitVectorUnittest, AppendToEmpty) {
110 BitVector bv;
111 bv.AppendTrue();
112 bv.AppendFalse();
113
114 ASSERT_EQ(bv.size(), 2u);
115 ASSERT_TRUE(bv.IsSet(0));
116 ASSERT_FALSE(bv.IsSet(1));
117 }
118
TEST(BitVectorUnittest,AppendToExisting)119 TEST(BitVectorUnittest, AppendToExisting) {
120 BitVector bv(2046, false);
121 bv.AppendTrue();
122 bv.AppendFalse();
123 bv.AppendTrue();
124 bv.AppendTrue();
125
126 ASSERT_EQ(bv.size(), 2050u);
127 ASSERT_TRUE(bv.IsSet(2046));
128 ASSERT_FALSE(bv.IsSet(2047));
129 ASSERT_TRUE(bv.IsSet(2048));
130 ASSERT_TRUE(bv.IsSet(2049));
131 }
132
TEST(BitVectorUnittest,GetNumBitsSet)133 TEST(BitVectorUnittest, GetNumBitsSet) {
134 BitVector bv(2049, false);
135 bv.Set(0);
136 bv.Set(1);
137 bv.Set(511);
138 bv.Set(512);
139 bv.Set(2047);
140 bv.Set(2048);
141
142 ASSERT_EQ(bv.GetNumBitsSet(), 6u);
143
144 ASSERT_EQ(bv.GetNumBitsSet(0), 0u);
145 ASSERT_EQ(bv.GetNumBitsSet(1), 1u);
146 ASSERT_EQ(bv.GetNumBitsSet(2), 2u);
147 ASSERT_EQ(bv.GetNumBitsSet(3), 2u);
148 ASSERT_EQ(bv.GetNumBitsSet(511), 2u);
149 ASSERT_EQ(bv.GetNumBitsSet(512), 3u);
150 ASSERT_EQ(bv.GetNumBitsSet(1023), 4u);
151 ASSERT_EQ(bv.GetNumBitsSet(1024), 4u);
152 ASSERT_EQ(bv.GetNumBitsSet(2047), 4u);
153 ASSERT_EQ(bv.GetNumBitsSet(2048), 5u);
154 ASSERT_EQ(bv.GetNumBitsSet(2049), 6u);
155 }
156
TEST(BitVectorUnittest,IndexOfNthSet)157 TEST(BitVectorUnittest, IndexOfNthSet) {
158 BitVector bv(2050, false);
159 bv.Set(0);
160 bv.Set(1);
161 bv.Set(511);
162 bv.Set(512);
163 bv.Set(2047);
164 bv.Set(2048);
165
166 ASSERT_EQ(bv.IndexOfNthSet(0), 0u);
167 ASSERT_EQ(bv.IndexOfNthSet(1), 1u);
168 ASSERT_EQ(bv.IndexOfNthSet(2), 511u);
169 ASSERT_EQ(bv.IndexOfNthSet(3), 512u);
170 ASSERT_EQ(bv.IndexOfNthSet(4), 2047u);
171 ASSERT_EQ(bv.IndexOfNthSet(5), 2048u);
172 }
173
TEST(BitVectorUnittest,Resize)174 TEST(BitVectorUnittest, Resize) {
175 BitVector bv(1, false);
176
177 bv.Resize(2, true);
178 ASSERT_EQ(bv.size(), 2u);
179 ASSERT_EQ(bv.IsSet(1), true);
180
181 bv.Resize(2049, false);
182 ASSERT_EQ(bv.size(), 2049u);
183 ASSERT_EQ(bv.IsSet(2), false);
184 ASSERT_EQ(bv.IsSet(2047), false);
185 ASSERT_EQ(bv.IsSet(2048), false);
186
187 // Set these two bits; the first should be preserved and the
188 // second should disappear.
189 bv.Set(512);
190 bv.Set(513);
191
192 bv.Resize(513, false);
193 ASSERT_EQ(bv.size(), 513u);
194 ASSERT_EQ(bv.IsSet(1), true);
195 ASSERT_EQ(bv.IsSet(512), true);
196 ASSERT_EQ(bv.GetNumBitsSet(), 2u);
197
198 // When we resize up, we need to be sure that the set bit from
199 // before we resized down is not still present as a garbage bit.
200 bv.Resize(514, false);
201 ASSERT_EQ(bv.size(), 514u);
202 ASSERT_EQ(bv.IsSet(513), false);
203 ASSERT_EQ(bv.GetNumBitsSet(), 2u);
204 }
205
TEST(BitVectorUnittest,ResizeHasCorrectCount)206 TEST(BitVectorUnittest, ResizeHasCorrectCount) {
207 BitVector bv(1, false);
208 ASSERT_EQ(bv.GetNumBitsSet(), 0u);
209
210 bv.Resize(1024, true);
211 ASSERT_EQ(bv.GetNumBitsSet(), 1023u);
212 }
213
TEST(BitVectorUnittest,AppendAfterResizeDown)214 TEST(BitVectorUnittest, AppendAfterResizeDown) {
215 BitVector bv(2049, false);
216 bv.Set(2048);
217
218 bv.Resize(2048);
219 bv.AppendFalse();
220 ASSERT_EQ(bv.IsSet(2048), false);
221 ASSERT_EQ(bv.GetNumBitsSet(), 0u);
222 }
223
TEST(BitVectorUnittest,UpdateSetBits)224 TEST(BitVectorUnittest, UpdateSetBits) {
225 BitVector bv(6, false);
226 bv.Set(1);
227 bv.Set(2);
228 bv.Set(4);
229
230 BitVector picker(3u, true);
231 picker.Clear(1);
232
233 bv.UpdateSetBits(picker);
234
235 ASSERT_TRUE(bv.IsSet(1));
236 ASSERT_FALSE(bv.IsSet(2));
237 ASSERT_TRUE(bv.IsSet(4));
238 }
239
TEST(BitVectorUnittest,UpdateSetBitsSmallerPicker)240 TEST(BitVectorUnittest, UpdateSetBitsSmallerPicker) {
241 BitVector bv(6, false);
242 bv.Set(1);
243 bv.Set(2);
244 bv.Set(4);
245
246 BitVector picker(2u, true);
247 picker.Clear(1);
248
249 bv.UpdateSetBits(picker);
250
251 ASSERT_TRUE(bv.IsSet(1));
252 ASSERT_FALSE(bv.IsSet(2));
253 ASSERT_FALSE(bv.IsSet(4));
254 }
255
TEST(BitVectorUnittest,IterateAllBitsConst)256 TEST(BitVectorUnittest, IterateAllBitsConst) {
257 BitVector bv;
258 for (uint32_t i = 0; i < 12345; ++i) {
259 if (i % 7 == 0 || i % 13 == 0) {
260 bv.AppendTrue();
261 } else {
262 bv.AppendFalse();
263 }
264 }
265
266 uint32_t i = 0;
267 for (auto it = bv.IterateAllBits(); it; it.Next(), ++i) {
268 ASSERT_EQ(it.IsSet(), i % 7 == 0 || i % 13 == 0);
269 ASSERT_EQ(it.index(), i);
270 }
271 }
272
TEST(BitVectorUnittest,IterateAllBitsSet)273 TEST(BitVectorUnittest, IterateAllBitsSet) {
274 BitVector bv;
275 for (uint32_t i = 0; i < 12345; ++i) {
276 if (i % 7 == 0 || i % 13 == 0) {
277 bv.AppendTrue();
278 } else {
279 bv.AppendFalse();
280 }
281 }
282
283 // Unset every 15th bit.
284 for (auto it = bv.IterateAllBits(); it; it.Next()) {
285 if (it.index() % 15 == 0) {
286 it.Set();
287 }
288 }
289
290 // Go through the iterator manually and check it has updated
291 // to not have every 15th bit set.
292 uint32_t count = 0;
293 for (uint32_t i = 0; i < 12345; ++i) {
294 bool is_set = i % 15 == 0 || i % 7 == 0 || i % 13 == 0;
295
296 ASSERT_EQ(bv.IsSet(i), is_set);
297 ASSERT_EQ(bv.GetNumBitsSet(i), count);
298
299 if (is_set) {
300 ASSERT_EQ(bv.IndexOfNthSet(count++), i);
301 }
302 }
303 }
304
TEST(BitVectorUnittest,IterateAllBitsClear)305 TEST(BitVectorUnittest, IterateAllBitsClear) {
306 BitVector bv;
307 for (uint32_t i = 0; i < 12345; ++i) {
308 if (i % 7 == 0 || i % 13 == 0) {
309 bv.AppendTrue();
310 } else {
311 bv.AppendFalse();
312 }
313 }
314
315 // Unset every 15th bit.
316 for (auto it = bv.IterateAllBits(); it; it.Next()) {
317 if (it.index() % 15 == 0) {
318 it.Clear();
319 }
320 }
321
322 // Go through the iterator manually and check it has updated
323 // to not have every 15th bit set.
324 uint32_t count = 0;
325 for (uint32_t i = 0; i < 12345; ++i) {
326 bool is_set = i % 15 != 0 && (i % 7 == 0 || i % 13 == 0);
327
328 ASSERT_EQ(bv.IsSet(i), is_set);
329 ASSERT_EQ(bv.GetNumBitsSet(i), count);
330
331 if (is_set) {
332 ASSERT_EQ(bv.IndexOfNthSet(count++), i);
333 }
334 }
335 }
336
TEST(BitVectorUnittest,IterateSetBitsConst)337 TEST(BitVectorUnittest, IterateSetBitsConst) {
338 BitVector bv;
339 std::vector<uint32_t> set_indices;
340 for (uint32_t i = 0; i < 12345; ++i) {
341 if (i % 7 == 0 || i % 13 == 0) {
342 bv.AppendTrue();
343 set_indices.emplace_back(i);
344 } else {
345 bv.AppendFalse();
346 }
347 }
348
349 uint32_t i = 0;
350 for (auto it = bv.IterateSetBits(); it; it.Next(), ++i) {
351 ASSERT_EQ(it.IsSet(), true);
352 ASSERT_EQ(it.index(), set_indices[i]);
353 }
354 ASSERT_EQ(i, set_indices.size());
355 }
356
TEST(BitVectorUnittest,IterateSetBitsClear)357 TEST(BitVectorUnittest, IterateSetBitsClear) {
358 BitVector bv;
359 for (uint32_t i = 0; i < 12345; ++i) {
360 if (i % 7 == 0 || i % 13 == 0) {
361 bv.AppendTrue();
362 } else {
363 bv.AppendFalse();
364 }
365 }
366
367 for (auto it = bv.IterateSetBits(); it; it.Next()) {
368 if (it.index() % 15 == 0) {
369 it.Clear();
370 }
371 }
372
373 // Go through the iterator manually and check it has updated
374 // to not have every 15th bit set.
375 uint32_t count = 0;
376 for (uint32_t i = 0; i < 12345; ++i) {
377 bool is_set = i % 15 != 0 && (i % 7 == 0 || i % 13 == 0);
378
379 ASSERT_EQ(bv.IsSet(i), is_set);
380 ASSERT_EQ(bv.GetNumBitsSet(i), count);
381
382 if (is_set) {
383 ASSERT_EQ(bv.IndexOfNthSet(count++), i);
384 }
385 }
386 }
387
TEST(BitVectorUnittest,IterateSetBitsStartsCorrectly)388 TEST(BitVectorUnittest, IterateSetBitsStartsCorrectly) {
389 BitVector bv;
390 bv.AppendFalse();
391 bv.AppendTrue();
392
393 auto it = bv.IterateSetBits();
394 ASSERT_TRUE(it);
395 ASSERT_EQ(it.index(), 1u);
396 ASSERT_TRUE(it.IsSet());
397
398 it.Next();
399 ASSERT_FALSE(it);
400 }
401
TEST(BitVectorUnittest,Range)402 TEST(BitVectorUnittest, Range) {
403 BitVector bv =
404 BitVector::Range(1, 1025, [](uint32_t t) { return t % 3 == 0; });
405
406 ASSERT_FALSE(bv.IsSet(0));
407 for (uint32_t i = 1; i < 1025; ++i) {
408 ASSERT_EQ(i % 3 == 0, bv.IsSet(i));
409 }
410 ASSERT_EQ(bv.size(), 1025u);
411 ASSERT_EQ(bv.GetNumBitsSet(), 341u);
412 }
413
TEST(BitVectorUnittest,QueryStressTest)414 TEST(BitVectorUnittest, QueryStressTest) {
415 BitVector bv;
416 std::vector<bool> bool_vec;
417 std::vector<uint32_t> int_vec;
418
419 static constexpr uint32_t kCount = 4096;
420 std::minstd_rand0 rand;
421 for (uint32_t i = 0; i < kCount; ++i) {
422 bool res = rand() % 2u;
423 if (res) {
424 bv.AppendTrue();
425 } else {
426 bv.AppendFalse();
427 }
428 bool_vec.push_back(res);
429 if (res)
430 int_vec.emplace_back(i);
431 }
432
433 auto all_it = bv.IterateAllBits();
434 for (uint32_t i = 0; i < kCount; ++i) {
435 uint32_t count = static_cast<uint32_t>(std::count(
436 bool_vec.begin(), bool_vec.begin() + static_cast<int32_t>(i), true));
437 ASSERT_EQ(bv.IsSet(i), bool_vec[i]);
438 ASSERT_EQ(bv.GetNumBitsSet(i), count);
439
440 ASSERT_TRUE(all_it);
441 ASSERT_EQ(all_it.IsSet(), bool_vec[i]);
442 ASSERT_EQ(all_it.index(), i);
443 all_it.Next();
444 }
445 ASSERT_FALSE(all_it);
446
447 auto set_it = bv.IterateSetBits();
448 for (uint32_t i = 0; i < int_vec.size(); ++i) {
449 ASSERT_EQ(bv.IndexOfNthSet(i), int_vec[i]);
450
451 ASSERT_TRUE(set_it);
452 ASSERT_EQ(set_it.IsSet(), true);
453 ASSERT_EQ(set_it.index(), int_vec[i]);
454 set_it.Next();
455 }
456 ASSERT_FALSE(set_it);
457 }
458
459 } // namespace
460 } // namespace trace_processor
461 } // namespace perfetto
462