libsanitizer/sanitizer_common/sanitizer_bitvector.h

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