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 25using namespace __sanitizer; 26using namespace std; 27 28 29// Check the 'bv' == 's' and that the indexes go in increasing order. 30// Also check the BV::Iterator 31template <class BV> 32static 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 59template <class BV> 60void 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 70void 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 77template <class BV> 78void 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 165TEST(SanitizerCommon, BasicBitVector) { 166 TestBitVector<BasicBitVector<u8> >(8); 167 TestBitVector<BasicBitVector<u16> >(16); 168 TestBitVector<BasicBitVector<> >(SANITIZER_WORDSIZE); 169} 170 171TEST(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