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 <set> 23 24 using namespace __sanitizer; 25 using namespace std; 26 27 28 // Check the 'bv' == 's' and that the indexes go in increasing order. 29 // Also check the BV::Iterator 30 template <class BV> 31 static 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 58 template <class BV> 59 void Print(const BV &bv) { 60 BV t; 61 t.copyFrom(bv); 62 while (!t.empty()) { 63 uptr idx = t.getAndClearFirstOne(); 64 fprintf(stderr, "%zd ", idx); 65 } 66 fprintf(stderr, "\n"); 67 } 68 69 void Print(const set<uptr> &s) { 70 for (set<uptr>::iterator it = s.begin(); it != s.end(); ++it) { 71 fprintf(stderr, "%zd ", *it); 72 } 73 fprintf(stderr, "\n"); 74 } 75 76 template <class BV> 77 void TestBitVector(uptr expected_size) { 78 BV bv, bv1, t_bv; 79 EXPECT_EQ(expected_size, BV::kSize); 80 bv.clear(); 81 EXPECT_TRUE(bv.empty()); 82 bv.setBit(5); 83 EXPECT_FALSE(bv.empty()); 84 EXPECT_FALSE(bv.getBit(4)); 85 EXPECT_FALSE(bv.getBit(6)); 86 EXPECT_TRUE(bv.getBit(5)); 87 bv.clearBit(5); 88 EXPECT_FALSE(bv.getBit(5)); 89 90 // test random bits 91 bv.clear(); 92 set<uptr> s; 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) { 97 case 0: 98 EXPECT_EQ(bv.setBit(bit), s.insert(bit).second); 99 break; 100 case 1: 101 size_t old_size = s.size(); 102 s.erase(bit); 103 EXPECT_EQ(bv.clearBit(bit), old_size > s.size()); 104 break; 105 } 106 EXPECT_EQ(bv.getBit(bit), s.count(bit) == 1); 107 } 108 109 vector<uptr>bits(bv.size()); 110 // Test setUnion, setIntersection, setDifference, 111 // intersectsWith, and getAndClearFirstOne. 112 for (uptr it = 0; it < 30; it++) { 113 // iota 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; 117 bv.clear(); 118 bv1.clear(); 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++) { 124 bv.setBit(bits[i]); 125 s.insert(bits[i]); 126 } 127 CheckBV(bv, s); 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]); 131 } 132 CheckBV(bv1, s1); 133 134 vector<uptr> vec; 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()); 138 139 // setUnion 140 t_s = s; 141 t_bv.copyFrom(bv); 142 t_s.insert(s1.begin(), s1.end()); 143 EXPECT_EQ(t_bv.setUnion(bv1), s.size() != t_s.size()); 144 CheckBV(t_bv, t_s); 145 146 // setIntersection 147 t_s = set<uptr>(vec.begin(), vec.end()); 148 t_bv.copyFrom(bv); 149 EXPECT_EQ(t_bv.setIntersection(bv1), s.size() != t_s.size()); 150 CheckBV(t_bv, t_s); 151 152 // setDifference 153 vec.clear(); 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()); 157 t_bv.copyFrom(bv); 158 EXPECT_EQ(t_bv.setDifference(bv1), s.size() != t_s.size()); 159 CheckBV(t_bv, t_s); 160 } 161 } 162 163 TEST(SanitizerCommon, BasicBitVector) { 164 TestBitVector<BasicBitVector<u8> >(8); 165 TestBitVector<BasicBitVector<u16> >(16); 166 TestBitVector<BasicBitVector<> >(SANITIZER_WORDSIZE); 167 } 168 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); 176 } 177
