libsanitizer/sanitizer_common/sanitizer_bitvector.h

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