• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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>
CheckBV(const BV & bv,const set<uptr> & s)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>
Print(const BV & 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 
Print(const set<uptr> & s)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>
TestBitVector(uptr expected_size)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 
TEST(SanitizerCommon,BasicBitVector)163 TEST(SanitizerCommon, BasicBitVector) {
164   TestBitVector<BasicBitVector<u8> >(8);
165   TestBitVector<BasicBitVector<u16> >(16);
166   TestBitVector<BasicBitVector<> >(SANITIZER_WORDSIZE);
167 }
168 
TEST(SanitizerCommon,TwoLevelBitVector)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