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