contrib/compiler-rt/lib/sanitizer_common/sanitizer_bitvector.h

   1 //===-- sanitizer_bitvector.h -----------------------------------*- C++ -*-===//
   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 // Specializer BitVector implementation.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef SANITIZER_BITVECTOR_H
  15 #define SANITIZER_BITVECTOR_H
  16
  17 #include "sanitizer_common.h"
  18
  19 namespace __sanitizer {
  20
  21 // Fixed size bit vector based on a single basic integer.
  22 template <class basic_int_t = uptr>
  23 class BasicBitVector {
  24  public:
  25   enum SizeEnum : uptr { kSize = sizeof(basic_int_t) * 8 };
  26
  27   uptr size() const { return kSize; }
  28   // No CTOR.
  29   void clear() { bits_ = 0; }
  30   void setAll() { bits_ = ~(basic_int_t)0; }
  31   bool empty() const { return bits_ == 0; }
  32
  33   // Returns true if the bit has changed from 0 to 1.
  34   bool setBit(uptr idx) {
  35     basic_int_t old = bits_;
  36     bits_ |= mask(idx);
  37     return bits_ != old;
  38   }
  39
  40   // Returns true if the bit has changed from 1 to 0.
  41   bool clearBit(uptr idx) {
  42     basic_int_t old = bits_;
  43     bits_ &= ~mask(idx);
  44     return bits_ != old;
  45   }
  46
  47   bool getBit(uptr idx) const { return (bits_ & mask(idx)) != 0; }
  48
  49   uptr getAndClearFirstOne() {
  50     CHECK(!empty());
  51     uptr idx = LeastSignificantSetBitIndex(bits_);
  52     clearBit(idx);
  53     return idx;
  54   }
  55
  56   // Do "this |= v" and return whether new bits have been added.
  57   bool setUnion(const BasicBitVector &v) {
  58     basic_int_t old = bits_;
  59     bits_ |= v.bits_;
  60     return bits_ != old;
  61   }
  62
  63   // Do "this &= v" and return whether any bits have been removed.
  64   bool setIntersection(const BasicBitVector &v) {
  65     basic_int_t old = bits_;
  66     bits_ &= v.bits_;
  67     return bits_ != old;
  68   }
  69
  70   // Do "this &= ~v" and return whether any bits have been removed.
  71   bool setDifference(const BasicBitVector &v) {
  72     basic_int_t old = bits_;
  73     bits_ &= ~v.bits_;
  74     return bits_ != old;
  75   }
  76
  77   void copyFrom(const BasicBitVector &v) { bits_ = v.bits_; }
  78
  79   // Returns true if 'this' intersects with 'v'.
  80   bool intersectsWith(const BasicBitVector &v) const {
  81     return (bits_ & v.bits_) != 0;
  82   }
  83
  84   // for (BasicBitVector<>::Iterator it(bv); it.hasNext();) {
  85   //   uptr idx = it.next();
  86   //   use(idx);
  87   // }
  88   class Iterator {
  89    public:
  90     Iterator() { }
  91     explicit Iterator(const BasicBitVector &bv) : bv_(bv) {}
  92     bool hasNext() const { return !bv_.empty(); }
  93     uptr next() { return bv_.getAndClearFirstOne(); }
  94     void clear() { bv_.clear(); }
  95    private:
  96     BasicBitVector bv_;
  97   };
  98
  99  private:
 100   basic_int_t mask(uptr idx) const {
 101     CHECK_LT(idx, size());
 102     return (basic_int_t)1UL << idx;
 103   }
 104   basic_int_t bits_;
 105 };
 106
 107 // Fixed size bit vector of (kLevel1Size*BV::kSize**2) bits.
 108 // The implementation is optimized for better performance on
 109 // sparse bit vectors, i.e. the those with few set bits.
 110 template <uptr kLevel1Size = 1, class BV = BasicBitVector<> >
 111 class TwoLevelBitVector {
 112   // This is essentially a 2-level bit vector.
 113   // Set bit in the first level BV indicates that there are set bits
 114   // in the corresponding BV of the second level.
 115   // This structure allows O(kLevel1Size) time for clear() and empty(),
 116   // as well fast handling of sparse BVs.
 117  public:
 118   enum SizeEnum : uptr { kSize = BV::kSize * BV::kSize * kLevel1Size };
 119   // No CTOR.
 120
 121   uptr size() const { return kSize; }
 122
 123   void clear() {
 124     for (uptr i = 0; i < kLevel1Size; i++)
 125       l1_[i].clear();
 126   }
 127
 128   void setAll() {
 129     for (uptr i0 = 0; i0 < kLevel1Size; i0++) {
 130       l1_[i0].setAll();
 131       for (uptr i1 = 0; i1 < BV::kSize; i1++)
 132         l2_[i0][i1].setAll();
 133     }
 134   }
 135
 136   bool empty() const {
 137     for (uptr i = 0; i < kLevel1Size; i++)
 138       if (!l1_[i].empty())
 139         return false;
 140     return true;
 141   }
 142
 143   // Returns true if the bit has changed from 0 to 1.
 144   bool setBit(uptr idx) {
 145     check(idx);
 146     uptr i0 = idx0(idx);
 147     uptr i1 = idx1(idx);
 148     uptr i2 = idx2(idx);
 149     if (!l1_[i0].getBit(i1)) {
 150       l1_[i0].setBit(i1);
 151       l2_[i0][i1].clear();
 152     }
 153     bool res = l2_[i0][i1].setBit(i2);
 154     // Printf("%s: %zd => %zd %zd %zd; %d\n", __func__,
 155     // idx, i0, i1, i2, res);
 156     return res;
 157   }
 158
 159   bool clearBit(uptr idx) {
 160     check(idx);
 161     uptr i0 = idx0(idx);
 162     uptr i1 = idx1(idx);
 163     uptr i2 = idx2(idx);
 164     bool res = false;
 165     if (l1_[i0].getBit(i1)) {
 166       res = l2_[i0][i1].clearBit(i2);
 167       if (l2_[i0][i1].empty())
 168         l1_[i0].clearBit(i1);
 169     }
 170     return res;
 171   }
 172
 173   bool getBit(uptr idx) const {
 174     check(idx);
 175     uptr i0 = idx0(idx);
 176     uptr i1 = idx1(idx);
 177     uptr i2 = idx2(idx);
 178     // Printf("%s: %zd => %zd %zd %zd\n", __func__, idx, i0, i1, i2);
 179     return l1_[i0].getBit(i1) && l2_[i0][i1].getBit(i2);
 180   }
 181
 182   uptr getAndClearFirstOne() {
 183     for (uptr i0 = 0; i0 < kLevel1Size; i0++) {
 184       if (l1_[i0].empty()) continue;
 185       uptr i1 = l1_[i0].getAndClearFirstOne();
 186       uptr i2 = l2_[i0][i1].getAndClearFirstOne();
 187       if (!l2_[i0][i1].empty())
 188         l1_[i0].setBit(i1);
 189       uptr res = i0 * BV::kSize * BV::kSize + i1 * BV::kSize + i2;
 190       // Printf("getAndClearFirstOne: %zd %zd %zd => %zd\n", i0, i1, i2, res);
 191       return res;
 192     }
 193     CHECK(0);
 194     return 0;
 195   }
 196
 197   // Do "this |= v" and return whether new bits have been added.
 198   bool setUnion(const TwoLevelBitVector &v) {
 199     bool res = false;
 200     for (uptr i0 = 0; i0 < kLevel1Size; i0++) {
 201       BV t = v.l1_[i0];
 202       while (!t.empty()) {
 203         uptr i1 = t.getAndClearFirstOne();
 204         if (l1_[i0].setBit(i1))
 205           l2_[i0][i1].clear();
 206         if (l2_[i0][i1].setUnion(v.l2_[i0][i1]))
 207           res = true;
 208       }
 209     }
 210     return res;
 211   }
 212
 213   // Do "this &= v" and return whether any bits have been removed.
 214   bool setIntersection(const TwoLevelBitVector &v) {
 215     bool res = false;
 216     for (uptr i0 = 0; i0 < kLevel1Size; i0++) {
 217       if (l1_[i0].setIntersection(v.l1_[i0]))
 218         res = true;
 219       if (!l1_[i0].empty()) {
 220         BV t = l1_[i0];
 221         while (!t.empty()) {
 222           uptr i1 = t.getAndClearFirstOne();
 223           if (l2_[i0][i1].setIntersection(v.l2_[i0][i1]))
 224             res = true;
 225           if (l2_[i0][i1].empty())
 226             l1_[i0].clearBit(i1);
 227         }
 228       }
 229     }
 230     return res;
 231   }
 232
 233   // Do "this &= ~v" and return whether any bits have been removed.
 234   bool setDifference(const TwoLevelBitVector &v) {
 235     bool res = false;
 236     for (uptr i0 = 0; i0 < kLevel1Size; i0++) {
 237       BV t = l1_[i0];
 238       t.setIntersection(v.l1_[i0]);
 239       while (!t.empty()) {
 240         uptr i1 = t.getAndClearFirstOne();
 241         if (l2_[i0][i1].setDifference(v.l2_[i0][i1]))
 242           res = true;
 243         if (l2_[i0][i1].empty())
 244           l1_[i0].clearBit(i1);
 245       }
 246     }
 247     return res;
 248   }
 249
 250   void copyFrom(const TwoLevelBitVector &v) {
 251     clear();
 252     setUnion(v);
 253   }
 254
 255   // Returns true if 'this' intersects with 'v'.
 256   bool intersectsWith(const TwoLevelBitVector &v) const {
 257     for (uptr i0 = 0; i0 < kLevel1Size; i0++) {
 258       BV t = l1_[i0];
 259       t.setIntersection(v.l1_[i0]);
 260       while (!t.empty()) {
 261         uptr i1 = t.getAndClearFirstOne();
 262         if (!v.l1_[i0].getBit(i1)) continue;
 263         if (l2_[i0][i1].intersectsWith(v.l2_[i0][i1]))
 264           return true;
 265       }
 266     }
 267     return false;
 268   }
 269
 270   // for (TwoLevelBitVector<>::Iterator it(bv); it.hasNext();) {
 271   //   uptr idx = it.next();
 272   //   use(idx);
 273   // }
 274   class Iterator {
 275    public:
 276     Iterator() { }
 277     explicit Iterator(const TwoLevelBitVector &bv) : bv_(bv), i0_(0), i1_(0) {
 278       it1_.clear();
 279       it2_.clear();
 280     }
 281
 282     bool hasNext() const {
 283       if (it1_.hasNext()) return true;
 284       for (uptr i = i0_; i < kLevel1Size; i++)
 285         if (!bv_.l1_[i].empty()) return true;
 286       return false;
 287     }
 288
 289     uptr next() {
 290       // Printf("++++: %zd %zd; %d %d; size %zd\n", i0_, i1_, it1_.hasNext(),
 291       //       it2_.hasNext(), kSize);
 292       if (!it1_.hasNext() && !it2_.hasNext()) {
 293         for (; i0_ < kLevel1Size; i0_++) {
 294           if (bv_.l1_[i0_].empty()) continue;
 295           it1_ = typename BV::Iterator(bv_.l1_[i0_]);
 296           // Printf("+i0: %zd %zd; %d %d; size %zd\n", i0_, i1_, it1_.hasNext(),
 297           //   it2_.hasNext(), kSize);
 298           break;
 299         }
 300       }
 301       if (!it2_.hasNext()) {
 302         CHECK(it1_.hasNext());
 303         i1_ = it1_.next();
 304         it2_ = typename BV::Iterator(bv_.l2_[i0_][i1_]);
 305         // Printf("++i1: %zd %zd; %d %d; size %zd\n", i0_, i1_, it1_.hasNext(),
 306         //       it2_.hasNext(), kSize);
 307       }
 308       CHECK(it2_.hasNext());
 309       uptr i2 = it2_.next();
 310       uptr res = i0_ * BV::kSize * BV::kSize + i1_ * BV::kSize + i2;
 311       // Printf("+ret: %zd %zd; %d %d; size %zd; res: %zd\n", i0_, i1_,
 312       //       it1_.hasNext(), it2_.hasNext(), kSize, res);
 313       if (!it1_.hasNext() && !it2_.hasNext())
 314         i0_++;
 315       return res;
 316     }
 317
 318    private:
 319     const TwoLevelBitVector &bv_;
 320     uptr i0_, i1_;
 321     typename BV::Iterator it1_, it2_;
 322   };
 323
 324  private:
 325   void check(uptr idx) const { CHECK_LE(idx, size()); }
 326
 327   uptr idx0(uptr idx) const {
 328     uptr res = idx / (BV::kSize * BV::kSize);
 329     CHECK_LE(res, kLevel1Size);
 330     return res;
 331   }
 332
 333   uptr idx1(uptr idx) const {
 334     uptr res = (idx / BV::kSize) % BV::kSize;
 335     CHECK_LE(res, BV::kSize);
 336     return res;
 337   }
 338
 339   uptr idx2(uptr idx) const {
 340     uptr res = idx % BV::kSize;
 341     CHECK_LE(res, BV::kSize);
 342     return res;
 343   }
 344
 345   BV l1_[kLevel1Size];
 346   BV l2_[kLevel1Size][BV::kSize];
 347 };
 348
 349 } // namespace __sanitizer
 350
 351 #endif // SANITIZER_BITVECTOR_H