1276789Sdim//===-- sanitizer_bitvector.h -----------------------------------*- C++ -*-===// 2276789Sdim// 3276789Sdim// The LLVM Compiler Infrastructure 4276789Sdim// 5276789Sdim// This file is distributed under the University of Illinois Open Source 6276789Sdim// License. See LICENSE.TXT for details. 7276789Sdim// 8276789Sdim//===----------------------------------------------------------------------===// 9276789Sdim// 10276789Sdim// Specializer BitVector implementation. 11276789Sdim// 12276789Sdim//===----------------------------------------------------------------------===// 13276789Sdim 14276789Sdim#ifndef SANITIZER_BITVECTOR_H 15276789Sdim#define SANITIZER_BITVECTOR_H 16276789Sdim 17276789Sdim#include "sanitizer_common.h" 18276789Sdim 19276789Sdimnamespace __sanitizer { 20276789Sdim 21276789Sdim// Fixed size bit vector based on a single basic integer. 22276789Sdimtemplate <class basic_int_t = uptr> 23276789Sdimclass BasicBitVector { 24276789Sdim public: 25276789Sdim enum SizeEnum { kSize = sizeof(basic_int_t) * 8 }; 26276789Sdim 27276789Sdim uptr size() const { return kSize; } 28276789Sdim // No CTOR. 29276789Sdim void clear() { bits_ = 0; } 30276789Sdim void setAll() { bits_ = ~(basic_int_t)0; } 31276789Sdim bool empty() const { return bits_ == 0; } 32276789Sdim 33276789Sdim // Returns true if the bit has changed from 0 to 1. 34276789Sdim bool setBit(uptr idx) { 35276789Sdim basic_int_t old = bits_; 36276789Sdim bits_ |= mask(idx); 37276789Sdim return bits_ != old; 38276789Sdim } 39276789Sdim 40276789Sdim // Returns true if the bit has changed from 1 to 0. 41276789Sdim bool clearBit(uptr idx) { 42276789Sdim basic_int_t old = bits_; 43276789Sdim bits_ &= ~mask(idx); 44276789Sdim return bits_ != old; 45276789Sdim } 46276789Sdim 47276789Sdim bool getBit(uptr idx) const { return (bits_ & mask(idx)) != 0; } 48276789Sdim 49276789Sdim uptr getAndClearFirstOne() { 50276789Sdim CHECK(!empty()); 51276789Sdim uptr idx = LeastSignificantSetBitIndex(bits_); 52276789Sdim clearBit(idx); 53276789Sdim return idx; 54276789Sdim } 55276789Sdim 56276789Sdim // Do "this |= v" and return whether new bits have been added. 57276789Sdim bool setUnion(const BasicBitVector &v) { 58276789Sdim basic_int_t old = bits_; 59276789Sdim bits_ |= v.bits_; 60276789Sdim return bits_ != old; 61276789Sdim } 62276789Sdim 63276789Sdim // Do "this &= v" and return whether any bits have been removed. 64276789Sdim bool setIntersection(const BasicBitVector &v) { 65276789Sdim basic_int_t old = bits_; 66276789Sdim bits_ &= v.bits_; 67276789Sdim return bits_ != old; 68276789Sdim } 69276789Sdim 70276789Sdim // Do "this &= ~v" and return whether any bits have been removed. 71276789Sdim bool setDifference(const BasicBitVector &v) { 72276789Sdim basic_int_t old = bits_; 73276789Sdim bits_ &= ~v.bits_; 74276789Sdim return bits_ != old; 75276789Sdim } 76276789Sdim 77276789Sdim void copyFrom(const BasicBitVector &v) { bits_ = v.bits_; } 78276789Sdim 79276789Sdim // Returns true if 'this' intersects with 'v'. 80276789Sdim bool intersectsWith(const BasicBitVector &v) const { 81276789Sdim return (bits_ & v.bits_) != 0; 82276789Sdim } 83276789Sdim 84276789Sdim // for (BasicBitVector<>::Iterator it(bv); it.hasNext();) { 85276789Sdim // uptr idx = it.next(); 86276789Sdim // use(idx); 87276789Sdim // } 88276789Sdim class Iterator { 89276789Sdim public: 90276789Sdim Iterator() { } 91276789Sdim explicit Iterator(const BasicBitVector &bv) : bv_(bv) {} 92276789Sdim bool hasNext() const { return !bv_.empty(); } 93276789Sdim uptr next() { return bv_.getAndClearFirstOne(); } 94276789Sdim void clear() { bv_.clear(); } 95276789Sdim private: 96276789Sdim BasicBitVector bv_; 97276789Sdim }; 98276789Sdim 99276789Sdim private: 100276789Sdim basic_int_t mask(uptr idx) const { 101276789Sdim CHECK_LT(idx, size()); 102276789Sdim return (basic_int_t)1UL << idx; 103276789Sdim } 104276789Sdim basic_int_t bits_; 105276789Sdim}; 106276789Sdim 107276789Sdim// Fixed size bit vector of (kLevel1Size*BV::kSize**2) bits. 108276789Sdim// The implementation is optimized for better performance on 109276789Sdim// sparse bit vectors, i.e. the those with few set bits. 110276789Sdimtemplate <uptr kLevel1Size = 1, class BV = BasicBitVector<> > 111276789Sdimclass TwoLevelBitVector { 112276789Sdim // This is essentially a 2-level bit vector. 113276789Sdim // Set bit in the first level BV indicates that there are set bits 114276789Sdim // in the corresponding BV of the second level. 115276789Sdim // This structure allows O(kLevel1Size) time for clear() and empty(), 116276789Sdim // as well fast handling of sparse BVs. 117276789Sdim public: 118276789Sdim enum SizeEnum { kSize = BV::kSize * BV::kSize * kLevel1Size }; 119276789Sdim // No CTOR. 120276789Sdim 121276789Sdim uptr size() const { return kSize; } 122276789Sdim 123276789Sdim void clear() { 124276789Sdim for (uptr i = 0; i < kLevel1Size; i++) 125276789Sdim l1_[i].clear(); 126276789Sdim } 127276789Sdim 128276789Sdim void setAll() { 129276789Sdim for (uptr i0 = 0; i0 < kLevel1Size; i0++) { 130276789Sdim l1_[i0].setAll(); 131276789Sdim for (uptr i1 = 0; i1 < BV::kSize; i1++) 132276789Sdim l2_[i0][i1].setAll(); 133276789Sdim } 134276789Sdim } 135276789Sdim 136276789Sdim bool empty() const { 137276789Sdim for (uptr i = 0; i < kLevel1Size; i++) 138276789Sdim if (!l1_[i].empty()) 139276789Sdim return false; 140276789Sdim return true; 141276789Sdim } 142276789Sdim 143276789Sdim // Returns true if the bit has changed from 0 to 1. 144276789Sdim bool setBit(uptr idx) { 145276789Sdim check(idx); 146276789Sdim uptr i0 = idx0(idx); 147276789Sdim uptr i1 = idx1(idx); 148276789Sdim uptr i2 = idx2(idx); 149276789Sdim if (!l1_[i0].getBit(i1)) { 150276789Sdim l1_[i0].setBit(i1); 151276789Sdim l2_[i0][i1].clear(); 152276789Sdim } 153276789Sdim bool res = l2_[i0][i1].setBit(i2); 154276789Sdim // Printf("%s: %zd => %zd %zd %zd; %d\n", __func__, 155276789Sdim // idx, i0, i1, i2, res); 156276789Sdim return res; 157276789Sdim } 158276789Sdim 159276789Sdim bool clearBit(uptr idx) { 160276789Sdim check(idx); 161276789Sdim uptr i0 = idx0(idx); 162276789Sdim uptr i1 = idx1(idx); 163276789Sdim uptr i2 = idx2(idx); 164276789Sdim bool res = false; 165276789Sdim if (l1_[i0].getBit(i1)) { 166276789Sdim res = l2_[i0][i1].clearBit(i2); 167276789Sdim if (l2_[i0][i1].empty()) 168276789Sdim l1_[i0].clearBit(i1); 169276789Sdim } 170276789Sdim return res; 171276789Sdim } 172276789Sdim 173276789Sdim bool getBit(uptr idx) const { 174276789Sdim check(idx); 175276789Sdim uptr i0 = idx0(idx); 176276789Sdim uptr i1 = idx1(idx); 177276789Sdim uptr i2 = idx2(idx); 178276789Sdim // Printf("%s: %zd => %zd %zd %zd\n", __func__, idx, i0, i1, i2); 179276789Sdim return l1_[i0].getBit(i1) && l2_[i0][i1].getBit(i2); 180276789Sdim } 181276789Sdim 182276789Sdim uptr getAndClearFirstOne() { 183276789Sdim for (uptr i0 = 0; i0 < kLevel1Size; i0++) { 184276789Sdim if (l1_[i0].empty()) continue; 185276789Sdim uptr i1 = l1_[i0].getAndClearFirstOne(); 186276789Sdim uptr i2 = l2_[i0][i1].getAndClearFirstOne(); 187276789Sdim if (!l2_[i0][i1].empty()) 188276789Sdim l1_[i0].setBit(i1); 189276789Sdim uptr res = i0 * BV::kSize * BV::kSize + i1 * BV::kSize + i2; 190276789Sdim // Printf("getAndClearFirstOne: %zd %zd %zd => %zd\n", i0, i1, i2, res); 191276789Sdim return res; 192276789Sdim } 193276789Sdim CHECK(0); 194276789Sdim return 0; 195276789Sdim } 196276789Sdim 197276789Sdim // Do "this |= v" and return whether new bits have been added. 198276789Sdim bool setUnion(const TwoLevelBitVector &v) { 199276789Sdim bool res = false; 200276789Sdim for (uptr i0 = 0; i0 < kLevel1Size; i0++) { 201276789Sdim BV t = v.l1_[i0]; 202276789Sdim while (!t.empty()) { 203276789Sdim uptr i1 = t.getAndClearFirstOne(); 204276789Sdim if (l1_[i0].setBit(i1)) 205276789Sdim l2_[i0][i1].clear(); 206276789Sdim if (l2_[i0][i1].setUnion(v.l2_[i0][i1])) 207276789Sdim res = true; 208276789Sdim } 209276789Sdim } 210276789Sdim return res; 211276789Sdim } 212276789Sdim 213276789Sdim // Do "this &= v" and return whether any bits have been removed. 214276789Sdim bool setIntersection(const TwoLevelBitVector &v) { 215276789Sdim bool res = false; 216276789Sdim for (uptr i0 = 0; i0 < kLevel1Size; i0++) { 217276789Sdim if (l1_[i0].setIntersection(v.l1_[i0])) 218276789Sdim res = true; 219276789Sdim if (!l1_[i0].empty()) { 220276789Sdim BV t = l1_[i0]; 221276789Sdim while (!t.empty()) { 222276789Sdim uptr i1 = t.getAndClearFirstOne(); 223276789Sdim if (l2_[i0][i1].setIntersection(v.l2_[i0][i1])) 224276789Sdim res = true; 225276789Sdim if (l2_[i0][i1].empty()) 226276789Sdim l1_[i0].clearBit(i1); 227276789Sdim } 228276789Sdim } 229276789Sdim } 230276789Sdim return res; 231276789Sdim } 232276789Sdim 233276789Sdim // Do "this &= ~v" and return whether any bits have been removed. 234276789Sdim bool setDifference(const TwoLevelBitVector &v) { 235276789Sdim bool res = false; 236276789Sdim for (uptr i0 = 0; i0 < kLevel1Size; i0++) { 237276789Sdim BV t = l1_[i0]; 238276789Sdim t.setIntersection(v.l1_[i0]); 239276789Sdim while (!t.empty()) { 240276789Sdim uptr i1 = t.getAndClearFirstOne(); 241276789Sdim if (l2_[i0][i1].setDifference(v.l2_[i0][i1])) 242276789Sdim res = true; 243276789Sdim if (l2_[i0][i1].empty()) 244276789Sdim l1_[i0].clearBit(i1); 245276789Sdim } 246276789Sdim } 247276789Sdim return res; 248276789Sdim } 249276789Sdim 250276789Sdim void copyFrom(const TwoLevelBitVector &v) { 251276789Sdim clear(); 252276789Sdim setUnion(v); 253276789Sdim } 254276789Sdim 255276789Sdim // Returns true if 'this' intersects with 'v'. 256276789Sdim bool intersectsWith(const TwoLevelBitVector &v) const { 257276789Sdim for (uptr i0 = 0; i0 < kLevel1Size; i0++) { 258276789Sdim BV t = l1_[i0]; 259276789Sdim t.setIntersection(v.l1_[i0]); 260276789Sdim while (!t.empty()) { 261276789Sdim uptr i1 = t.getAndClearFirstOne(); 262276789Sdim if (!v.l1_[i0].getBit(i1)) continue; 263276789Sdim if (l2_[i0][i1].intersectsWith(v.l2_[i0][i1])) 264276789Sdim return true; 265276789Sdim } 266276789Sdim } 267276789Sdim return false; 268276789Sdim } 269276789Sdim 270276789Sdim // for (TwoLevelBitVector<>::Iterator it(bv); it.hasNext();) { 271276789Sdim // uptr idx = it.next(); 272276789Sdim // use(idx); 273276789Sdim // } 274276789Sdim class Iterator { 275276789Sdim public: 276276789Sdim Iterator() { } 277276789Sdim explicit Iterator(const TwoLevelBitVector &bv) : bv_(bv), i0_(0), i1_(0) { 278276789Sdim it1_.clear(); 279276789Sdim it2_.clear(); 280276789Sdim } 281276789Sdim 282276789Sdim bool hasNext() const { 283276789Sdim if (it1_.hasNext()) return true; 284276789Sdim for (uptr i = i0_; i < kLevel1Size; i++) 285276789Sdim if (!bv_.l1_[i].empty()) return true; 286276789Sdim return false; 287276789Sdim } 288276789Sdim 289276789Sdim uptr next() { 290276789Sdim // Printf("++++: %zd %zd; %d %d; size %zd\n", i0_, i1_, it1_.hasNext(), 291276789Sdim // it2_.hasNext(), kSize); 292276789Sdim if (!it1_.hasNext() && !it2_.hasNext()) { 293276789Sdim for (; i0_ < kLevel1Size; i0_++) { 294276789Sdim if (bv_.l1_[i0_].empty()) continue; 295276789Sdim it1_ = typename BV::Iterator(bv_.l1_[i0_]); 296276789Sdim // Printf("+i0: %zd %zd; %d %d; size %zd\n", i0_, i1_, it1_.hasNext(), 297276789Sdim // it2_.hasNext(), kSize); 298276789Sdim break; 299276789Sdim } 300276789Sdim } 301276789Sdim if (!it2_.hasNext()) { 302276789Sdim CHECK(it1_.hasNext()); 303276789Sdim i1_ = it1_.next(); 304276789Sdim it2_ = typename BV::Iterator(bv_.l2_[i0_][i1_]); 305276789Sdim // Printf("++i1: %zd %zd; %d %d; size %zd\n", i0_, i1_, it1_.hasNext(), 306276789Sdim // it2_.hasNext(), kSize); 307276789Sdim } 308276789Sdim CHECK(it2_.hasNext()); 309276789Sdim uptr i2 = it2_.next(); 310276789Sdim uptr res = i0_ * BV::kSize * BV::kSize + i1_ * BV::kSize + i2; 311276789Sdim // Printf("+ret: %zd %zd; %d %d; size %zd; res: %zd\n", i0_, i1_, 312276789Sdim // it1_.hasNext(), it2_.hasNext(), kSize, res); 313276789Sdim if (!it1_.hasNext() && !it2_.hasNext()) 314276789Sdim i0_++; 315276789Sdim return res; 316276789Sdim } 317276789Sdim 318276789Sdim private: 319276789Sdim const TwoLevelBitVector &bv_; 320276789Sdim uptr i0_, i1_; 321276789Sdim typename BV::Iterator it1_, it2_; 322276789Sdim }; 323276789Sdim 324276789Sdim private: 325276789Sdim void check(uptr idx) const { CHECK_LE(idx, size()); } 326276789Sdim 327276789Sdim uptr idx0(uptr idx) const { 328276789Sdim uptr res = idx / (BV::kSize * BV::kSize); 329276789Sdim CHECK_LE(res, kLevel1Size); 330276789Sdim return res; 331276789Sdim } 332276789Sdim 333276789Sdim uptr idx1(uptr idx) const { 334276789Sdim uptr res = (idx / BV::kSize) % BV::kSize; 335276789Sdim CHECK_LE(res, BV::kSize); 336276789Sdim return res; 337276789Sdim } 338276789Sdim 339276789Sdim uptr idx2(uptr idx) const { 340276789Sdim uptr res = idx % BV::kSize; 341276789Sdim CHECK_LE(res, BV::kSize); 342276789Sdim return res; 343276789Sdim } 344276789Sdim 345276789Sdim BV l1_[kLevel1Size]; 346276789Sdim BV l2_[kLevel1Size][BV::kSize]; 347276789Sdim}; 348276789Sdim 349276789Sdim} // namespace __sanitizer 350276789Sdim 351276789Sdim#endif // SANITIZER_BITVECTOR_H 352