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