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