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 : uptr { kSize = sizeof(basic_int_t) * 8 }; 24 size()25 uptr size() const { return kSize; } 26 // No CTOR. clear()27 void clear() { bits_ = 0; } setAll()28 void setAll() { bits_ = ~(basic_int_t)0; } empty()29 bool empty() const { return bits_ == 0; } 30 31 // Returns true if the bit has changed from 0 to 1. setBit(uptr idx)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. clearBit(uptr idx)39 bool clearBit(uptr idx) { 40 basic_int_t old = bits_; 41 bits_ &= ~mask(idx); 42 return bits_ != old; 43 } 44 getBit(uptr idx)45 bool getBit(uptr idx) const { return (bits_ & mask(idx)) != 0; } 46 getAndClearFirstOne()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. setUnion(const BasicBitVector & v)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. setIntersection(const BasicBitVector & v)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. setDifference(const BasicBitVector & v)69 bool setDifference(const BasicBitVector &v) { 70 basic_int_t old = bits_; 71 bits_ &= ~v.bits_; 72 return bits_ != old; 73 } 74 copyFrom(const BasicBitVector & v)75 void copyFrom(const BasicBitVector &v) { bits_ = v.bits_; } 76 77 // Returns true if 'this' intersects with 'v'. intersectsWith(const BasicBitVector & 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: Iterator()88 Iterator() { } Iterator(const BasicBitVector & bv)89 explicit Iterator(const BasicBitVector &bv) : bv_(bv) {} hasNext()90 bool hasNext() const { return !bv_.empty(); } next()91 uptr next() { return bv_.getAndClearFirstOne(); } clear()92 void clear() { bv_.clear(); } 93 private: 94 BasicBitVector bv_; 95 }; 96 97 private: mask(uptr idx)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 : uptr { kSize = BV::kSize * BV::kSize * kLevel1Size }; 117 // No CTOR. 118 size()119 uptr size() const { return kSize; } 120 clear()121 void clear() { 122 for (uptr i = 0; i < kLevel1Size; i++) 123 l1_[i].clear(); 124 } 125 setAll()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 empty()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. setBit(uptr idx)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 clearBit(uptr idx)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 getBit(uptr idx)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 getAndClearFirstOne()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. setUnion(const TwoLevelBitVector & v)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. setIntersection(const TwoLevelBitVector & v)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. setDifference(const TwoLevelBitVector & v)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 copyFrom(const TwoLevelBitVector & v)248 void copyFrom(const TwoLevelBitVector &v) { 249 clear(); 250 setUnion(v); 251 } 252 253 // Returns true if 'this' intersects with 'v'. intersectsWith(const TwoLevelBitVector & 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: Iterator()274 Iterator() { } Iterator(const TwoLevelBitVector & bv)275 explicit Iterator(const TwoLevelBitVector &bv) : bv_(bv), i0_(0), i1_(0) { 276 it1_.clear(); 277 it2_.clear(); 278 } 279 hasNext()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 next()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: check(uptr idx)323 void check(uptr idx) const { CHECK_LE(idx, size()); } 324 idx0(uptr idx)325 uptr idx0(uptr idx) const { 326 uptr res = idx / (BV::kSize * BV::kSize); 327 CHECK_LE(res, kLevel1Size); 328 return res; 329 } 330 idx1(uptr idx)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 idx2(uptr idx)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 350