1 //===-- sanitizer_bitvector_test.cc ---------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file is a part of Sanitizer runtime.
11 // Tests for sanitizer_bitvector.h.
13 //===----------------------------------------------------------------------===//
14 #include "sanitizer_common/sanitizer_bitvector.h"
16 #include "sanitizer_test_utils.h"
18 #include "gtest/gtest.h"
24 using namespace __sanitizer;
28 // Check the 'bv' == 's' and that the indexes go in increasing order.
29 // Also check the BV::Iterator
31 static void CheckBV(const BV &bv, const set<uptr> &s) {
35 uptr last_idx = bv.size();
37 for (typename BV::Iterator it(bv); it.hasNext();) {
40 if (last_idx != bv.size())
41 EXPECT_LT(last_idx, idx);
43 EXPECT_TRUE(s.count(idx));
45 EXPECT_EQ(count, s.size());
49 uptr idx = t.getAndClearFirstOne();
50 if (last_idx != bv.size())
51 EXPECT_LT(last_idx, idx);
53 EXPECT_TRUE(t_s.erase(idx));
55 EXPECT_TRUE(t_s.empty());
59 void Print(const BV &bv) {
63 uptr idx = t.getAndClearFirstOne();
64 fprintf(stderr, "%zd ", idx);
66 fprintf(stderr, "\n");
69 void Print(const set<uptr> &s) {
70 for (set<uptr>::iterator it = s.begin(); it != s.end(); ++it) {
71 fprintf(stderr, "%zd ", *it);
73 fprintf(stderr, "\n");
77 void TestBitVector(uptr expected_size) {
79 EXPECT_EQ(expected_size, BV::kSize);
81 EXPECT_TRUE(bv.empty());
83 EXPECT_FALSE(bv.empty());
84 EXPECT_FALSE(bv.getBit(4));
85 EXPECT_FALSE(bv.getBit(6));
86 EXPECT_TRUE(bv.getBit(5));
88 EXPECT_FALSE(bv.getBit(5));
93 for (uptr it = 0; it < 1000; it++) {
94 uptr bit = ((uptr)my_rand() % bv.size());
95 EXPECT_EQ(bv.getBit(bit), s.count(bit) == 1);
96 switch (my_rand() % 2) {
98 EXPECT_EQ(bv.setBit(bit), s.insert(bit).second);
101 size_t old_size = s.size();
103 EXPECT_EQ(bv.clearBit(bit), old_size > s.size());
106 EXPECT_EQ(bv.getBit(bit), s.count(bit) == 1);
109 vector<uptr>bits(bv.size());
110 // Test setUnion, setIntersection, setDifference,
111 // intersectsWith, and getAndClearFirstOne.
112 for (uptr it = 0; it < 30; it++) {
114 for (size_t j = 0; j < bits.size(); j++) bits[j] = j;
115 random_shuffle(bits.begin(), bits.end());
116 set<uptr> s, s1, t_s;
119 uptr n_bits = ((uptr)my_rand() % bv.size()) + 1;
120 uptr n_bits1 = (uptr)my_rand() % (bv.size() / 2);
121 EXPECT_TRUE(n_bits > 0 && n_bits <= bv.size());
122 EXPECT_TRUE(n_bits1 < bv.size() / 2);
123 for (uptr i = 0; i < n_bits; i++) {
128 for (uptr i = 0; i < n_bits1; i++) {
129 bv1.setBit(bits[bv.size() / 2 + i]);
130 s1.insert(bits[bv.size() / 2 + i]);
135 set_intersection(s.begin(), s.end(), s1.begin(), s1.end(),
136 back_insert_iterator<vector<uptr> >(vec));
137 EXPECT_EQ(bv.intersectsWith(bv1), !vec.empty());
142 t_s.insert(s1.begin(), s1.end());
143 EXPECT_EQ(t_bv.setUnion(bv1), s.size() != t_s.size());
147 t_s = set<uptr>(vec.begin(), vec.end());
149 EXPECT_EQ(t_bv.setIntersection(bv1), s.size() != t_s.size());
154 set_difference(s.begin(), s.end(), s1.begin(), s1.end(),
155 back_insert_iterator<vector<uptr> >(vec));
156 t_s = set<uptr>(vec.begin(), vec.end());
158 EXPECT_EQ(t_bv.setDifference(bv1), s.size() != t_s.size());
163 TEST(SanitizerCommon, BasicBitVector) {
164 TestBitVector<BasicBitVector<u8> >(8);
165 TestBitVector<BasicBitVector<u16> >(16);
166 TestBitVector<BasicBitVector<> >(SANITIZER_WORDSIZE);
169 TEST(SanitizerCommon, TwoLevelBitVector) {
170 uptr ws = SANITIZER_WORDSIZE;
171 TestBitVector<TwoLevelBitVector<1, BasicBitVector<u8> > >(8 * 8);
172 TestBitVector<TwoLevelBitVector<> >(ws * ws);
173 TestBitVector<TwoLevelBitVector<2> >(ws * ws * 2);
174 TestBitVector<TwoLevelBitVector<3> >(ws * ws * 3);
175 TestBitVector<TwoLevelBitVector<3, BasicBitVector<u16> > >(16 * 16 * 3);