lib/sanitizer_common/tests/sanitizer_bitvector_test.cc

   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 }