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