1//===-- sanitizer_bitvector_test.cpp --------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file is a part of Sanitizer runtime.
10// Tests for sanitizer_bitvector.h.
11//
12//===----------------------------------------------------------------------===//
13#include "sanitizer_common/sanitizer_bitvector.h"
14
15#include "sanitizer_test_utils.h"
16
17#include "gtest/gtest.h"
18
19#include <algorithm>
20#include <vector>
21#include <random>
22#include <set>
23
24using namespace __sanitizer;
25using namespace std;
26
27
28// Check the 'bv' == 's' and that the indexes go in increasing order.
29// Also check the BV::Iterator
30template <class BV>
31static void CheckBV(const BV &bv, const set<uptr> &s) {
32 BV t;
33 t.copyFrom(bv);
34 set<uptr> t_s(s);
35 uptr last_idx = bv.size();
36 uptr count = 0;
37 for (typename BV::Iterator it(bv); it.hasNext();) {
38 uptr idx = it.next();
39 count++;
40 if (last_idx != bv.size())
41 EXPECT_LT(last_idx, idx);
42 last_idx = idx;
43 EXPECT_TRUE(s.count(idx));
44 }
45 EXPECT_EQ(count, s.size());
46
47 last_idx = bv.size();
48 while (!t.empty()) {
49 uptr idx = t.getAndClearFirstOne();
50 if (last_idx != bv.size())
51 EXPECT_LT(last_idx, idx);
52 last_idx = idx;
53 EXPECT_TRUE(t_s.erase(idx));
54 }
55 EXPECT_TRUE(t_s.empty());
56}
57
58template <class BV>
59void Print(const BV &bv) {
60 BV t;
61 t.copyFrom(bv);
62 while (!t.empty()) {
63 uptr idx = t.getAndClearFirstOne();
64 fprintf(stderr, "%lu ", idx);
65 }
66 fprintf(stderr, "\n");
67}
68
69void Print(const set<uptr> &s) {
70 for (set<uptr>::iterator it = s.begin(); it != s.end(); ++it) {
71#if defined(_WIN64)
72 fprintf(stderr, "%llu ", *it);
73#else
74 fprintf(stderr, "%lu ", (unsigned long)*it);
75#endif
76 }
77 fprintf(stderr, "\n");
78}
79
80template <class BV>
81void TestBitVector(uptr expected_size) {
82 std::mt19937 r;
83 BV bv, bv1, t_bv;
84 EXPECT_EQ(expected_size, BV::kSize);
85 bv.clear();
86 EXPECT_TRUE(bv.empty());
87 bv.setBit(5);
88 EXPECT_FALSE(bv.empty());
89 EXPECT_FALSE(bv.getBit(4));
90 EXPECT_FALSE(bv.getBit(6));
91 EXPECT_TRUE(bv.getBit(5));
92 bv.clearBit(5);
93 EXPECT_FALSE(bv.getBit(5));
94
95 // test random bits
96 bv.clear();
97 set<uptr> s;
98 for (uptr it = 0; it < 1000; it++) {
99 uptr bit = ((uptr)my_rand() % bv.size());
100 EXPECT_EQ(bv.getBit(bit), s.count(bit) == 1);
101 switch (my_rand() % 2) {
102 case 0:
103 EXPECT_EQ(bv.setBit(bit), s.insert(bit).second);
104 break;
105 case 1:
106 size_t old_size = s.size();
107 s.erase(bit);
108 EXPECT_EQ(bv.clearBit(bit), old_size > s.size());
109 break;
110 }
111 EXPECT_EQ(bv.getBit(bit), s.count(bit) == 1);
112 }
113
114 vector<uptr>bits(bv.size());
115 // Test setUnion, setIntersection, setDifference,
116 // intersectsWith, and getAndClearFirstOne.
117 for (uptr it = 0; it < 30; it++) {
118 // iota
119 for (size_t j = 0; j < bits.size(); j++) bits[j] = j;
120 std::shuffle(bits.begin(), bits.end(), r);
121 set<uptr> s, s1, t_s;
122 bv.clear();
123 bv1.clear();
124 uptr n_bits = ((uptr)my_rand() % bv.size()) + 1;
125 uptr n_bits1 = (uptr)my_rand() % (bv.size() / 2);
126 EXPECT_TRUE(n_bits > 0 && n_bits <= bv.size());
127 EXPECT_TRUE(n_bits1 < bv.size() / 2);
128 for (uptr i = 0; i < n_bits; i++) {
129 bv.setBit(bits[i]);
130 s.insert(bits[i]);
131 }
132 CheckBV(bv, s);
133 for (uptr i = 0; i < n_bits1; i++) {
134 bv1.setBit(bits[bv.size() / 2 + i]);
135 s1.insert(bits[bv.size() / 2 + i]);
136 }
137 CheckBV(bv1, s1);
138
139 vector<uptr> vec;
140 set_intersection(s.begin(), s.end(), s1.begin(), s1.end(),
141 back_insert_iterator<vector<uptr> >(vec));
142 EXPECT_EQ(bv.intersectsWith(bv1), !vec.empty());
143
144 // setUnion
145 t_s = s;
146 t_bv.copyFrom(bv);
147 t_s.insert(s1.begin(), s1.end());
148 EXPECT_EQ(t_bv.setUnion(bv1), s.size() != t_s.size());
149 CheckBV(t_bv, t_s);
150
151 // setIntersection
152 t_s = set<uptr>(vec.begin(), vec.end());
153 t_bv.copyFrom(bv);
154 EXPECT_EQ(t_bv.setIntersection(bv1), s.size() != t_s.size());
155 CheckBV(t_bv, t_s);
156
157 // setDifference
158 vec.clear();
159 set_difference(s.begin(), s.end(), s1.begin(), s1.end(),
160 back_insert_iterator<vector<uptr> >(vec));
161 t_s = set<uptr>(vec.begin(), vec.end());
162 t_bv.copyFrom(bv);
163 EXPECT_EQ(t_bv.setDifference(bv1), s.size() != t_s.size());
164 CheckBV(t_bv, t_s);
165 }
166}
167
168TEST(SanitizerCommon, BasicBitVector) {
169 TestBitVector<BasicBitVector<u8> >(expected_size: 8);
170 TestBitVector<BasicBitVector<u16> >(expected_size: 16);
171 TestBitVector<BasicBitVector<> >(SANITIZER_WORDSIZE);
172}
173
174TEST(SanitizerCommon, TwoLevelBitVector) {
175 uptr ws = SANITIZER_WORDSIZE;
176 TestBitVector<TwoLevelBitVector<1, BasicBitVector<u8> > >(expected_size: 8 * 8);
177 TestBitVector<TwoLevelBitVector<> >(expected_size: ws * ws);
178 TestBitVector<TwoLevelBitVector<2> >(expected_size: ws * ws * 2);
179 TestBitVector<TwoLevelBitVector<3> >(expected_size: ws * ws * 3);
180 TestBitVector<TwoLevelBitVector<3, BasicBitVector<u16> > >(expected_size: 16 * 16 * 3);
181}
182

source code of compiler-rt/lib/sanitizer_common/tests/sanitizer_bitvector_test.cpp