12d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines//===-- sanitizer_bitvector.h -----------------------------------*- C++ -*-===// 22d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 32d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// The LLVM Compiler Infrastructure 42d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 52d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// This file is distributed under the University of Illinois Open Source 62d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// License. See LICENSE.TXT for details. 72d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 82d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines//===----------------------------------------------------------------------===// 92d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// Specializer BitVector implementation. 112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines//===----------------------------------------------------------------------===// 132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#ifndef SANITIZER_BITVECTOR_H 152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#define SANITIZER_BITVECTOR_H 162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include "sanitizer_common.h" 182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesnamespace __sanitizer { 202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// Fixed size bit vector based on a single basic integer. 222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate <class basic_int_t = uptr> 232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesclass BasicBitVector { 242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines public: 252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines enum SizeEnum { kSize = sizeof(basic_int_t) * 8 }; 262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr size() const { return kSize; } 282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // No CTOR. 292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void clear() { bits_ = 0; } 302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void setAll() { bits_ = ~(basic_int_t)0; } 312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool empty() const { return bits_ == 0; } 322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Returns true if the bit has changed from 0 to 1. 342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool setBit(uptr idx) { 352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines basic_int_t old = bits_; 362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bits_ |= mask(idx); 372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return bits_ != old; 382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Returns true if the bit has changed from 1 to 0. 412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool clearBit(uptr idx) { 422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines basic_int_t old = bits_; 432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bits_ &= ~mask(idx); 442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return bits_ != old; 452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool getBit(uptr idx) const { return (bits_ & mask(idx)) != 0; } 482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr getAndClearFirstOne() { 502d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK(!empty()); 512d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr idx = LeastSignificantSetBitIndex(bits_); 522d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines clearBit(idx); 532d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return idx; 542d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 552d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 562d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Do "this |= v" and return whether new bits have been added. 572d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool setUnion(const BasicBitVector &v) { 582d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines basic_int_t old = bits_; 592d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bits_ |= v.bits_; 602d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return bits_ != old; 612d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 622d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 632d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Do "this &= v" and return whether any bits have been removed. 642d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool setIntersection(const BasicBitVector &v) { 652d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines basic_int_t old = bits_; 662d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bits_ &= v.bits_; 672d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return bits_ != old; 682d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 692d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 702d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Do "this &= ~v" and return whether any bits have been removed. 712d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool setDifference(const BasicBitVector &v) { 722d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines basic_int_t old = bits_; 732d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bits_ &= ~v.bits_; 742d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return bits_ != old; 752d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 762d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 772d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void copyFrom(const BasicBitVector &v) { bits_ = v.bits_; } 782d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 792d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Returns true if 'this' intersects with 'v'. 802d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool intersectsWith(const BasicBitVector &v) const { 812d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return (bits_ & v.bits_) != 0; 822d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 832d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 842d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // for (BasicBitVector<>::Iterator it(bv); it.hasNext();) { 852d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // uptr idx = it.next(); 862d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // use(idx); 872d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // } 882d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines class Iterator { 892d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines public: 902d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Iterator() { } 912d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines explicit Iterator(const BasicBitVector &bv) : bv_(bv) {} 922d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool hasNext() const { return !bv_.empty(); } 932d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr next() { return bv_.getAndClearFirstOne(); } 942d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void clear() { bv_.clear(); } 952d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines private: 962d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines BasicBitVector bv_; 972d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines }; 982d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 992d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines private: 1002d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines basic_int_t mask(uptr idx) const { 1012d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK_LT(idx, size()); 1022d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return (basic_int_t)1UL << idx; 1032d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1042d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines basic_int_t bits_; 1052d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines}; 1062d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1072d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// Fixed size bit vector of (kLevel1Size*BV::kSize**2) bits. 1082d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// The implementation is optimized for better performance on 1092d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// sparse bit vectors, i.e. the those with few set bits. 1102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate <uptr kLevel1Size = 1, class BV = BasicBitVector<> > 1112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesclass TwoLevelBitVector { 1122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // This is essentially a 2-level bit vector. 1132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Set bit in the first level BV indicates that there are set bits 1142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // in the corresponding BV of the second level. 1152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // This structure allows O(kLevel1Size) time for clear() and empty(), 1162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // as well fast handling of sparse BVs. 1172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines public: 1182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines enum SizeEnum { kSize = BV::kSize * BV::kSize * kLevel1Size }; 1192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // No CTOR. 1202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr size() const { return kSize; } 1222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void clear() { 1242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < kLevel1Size; i++) 1252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines l1_[i].clear(); 1262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void setAll() { 1292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i0 = 0; i0 < kLevel1Size; i0++) { 1302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines l1_[i0].setAll(); 1312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i1 = 0; i1 < BV::kSize; i1++) 1322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines l2_[i0][i1].setAll(); 1332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool empty() const { 1372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < kLevel1Size; i++) 1382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (!l1_[i].empty()) 1392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return false; 1402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return true; 1412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Returns true if the bit has changed from 0 to 1. 1442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool setBit(uptr idx) { 1452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines check(idx); 1462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr i0 = idx0(idx); 1472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr i1 = idx1(idx); 1482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr i2 = idx2(idx); 1492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (!l1_[i0].getBit(i1)) { 1502d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines l1_[i0].setBit(i1); 1512d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines l2_[i0][i1].clear(); 1522d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1532d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool res = l2_[i0][i1].setBit(i2); 1542d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Printf("%s: %zd => %zd %zd %zd; %d\n", __func__, 1552d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // idx, i0, i1, i2, res); 1562d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return res; 1572d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1582d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1592d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool clearBit(uptr idx) { 1602d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines check(idx); 1612d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr i0 = idx0(idx); 1622d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr i1 = idx1(idx); 1632d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr i2 = idx2(idx); 1642d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool res = false; 1652d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (l1_[i0].getBit(i1)) { 1662d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines res = l2_[i0][i1].clearBit(i2); 1672d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (l2_[i0][i1].empty()) 1682d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines l1_[i0].clearBit(i1); 1692d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1702d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return res; 1712d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1722d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1732d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool getBit(uptr idx) const { 1742d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines check(idx); 1752d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr i0 = idx0(idx); 1762d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr i1 = idx1(idx); 1772d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr i2 = idx2(idx); 1782d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Printf("%s: %zd => %zd %zd %zd\n", __func__, idx, i0, i1, i2); 1792d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return l1_[i0].getBit(i1) && l2_[i0][i1].getBit(i2); 1802d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1812d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1822d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr getAndClearFirstOne() { 1832d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i0 = 0; i0 < kLevel1Size; i0++) { 1842d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (l1_[i0].empty()) continue; 1852d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr i1 = l1_[i0].getAndClearFirstOne(); 1862d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr i2 = l2_[i0][i1].getAndClearFirstOne(); 1872d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (!l2_[i0][i1].empty()) 1882d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines l1_[i0].setBit(i1); 1892d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr res = i0 * BV::kSize * BV::kSize + i1 * BV::kSize + i2; 1902d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Printf("getAndClearFirstOne: %zd %zd %zd => %zd\n", i0, i1, i2, res); 1912d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return res; 1922d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1932d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK(0); 1942d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return 0; 1952d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1962d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1972d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Do "this |= v" and return whether new bits have been added. 1982d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool setUnion(const TwoLevelBitVector &v) { 1992d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool res = false; 2002d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i0 = 0; i0 < kLevel1Size; i0++) { 2012d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines BV t = v.l1_[i0]; 2022d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines while (!t.empty()) { 2032d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr i1 = t.getAndClearFirstOne(); 2042d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (l1_[i0].setBit(i1)) 2052d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines l2_[i0][i1].clear(); 2062d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (l2_[i0][i1].setUnion(v.l2_[i0][i1])) 2072d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines res = true; 2082d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2092d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return res; 2112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Do "this &= v" and return whether any bits have been removed. 2142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool setIntersection(const TwoLevelBitVector &v) { 2152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool res = false; 2162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i0 = 0; i0 < kLevel1Size; i0++) { 2172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (l1_[i0].setIntersection(v.l1_[i0])) 2182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines res = true; 2192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (!l1_[i0].empty()) { 2202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines BV t = l1_[i0]; 2212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines while (!t.empty()) { 2222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr i1 = t.getAndClearFirstOne(); 2232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (l2_[i0][i1].setIntersection(v.l2_[i0][i1])) 2242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines res = true; 2252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (l2_[i0][i1].empty()) 2262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines l1_[i0].clearBit(i1); 2272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return res; 2312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Do "this &= ~v" and return whether any bits have been removed. 2342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool setDifference(const TwoLevelBitVector &v) { 2352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool res = false; 2362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i0 = 0; i0 < kLevel1Size; i0++) { 2372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines BV t = l1_[i0]; 2382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines t.setIntersection(v.l1_[i0]); 2392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines while (!t.empty()) { 2402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr i1 = t.getAndClearFirstOne(); 2412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (l2_[i0][i1].setDifference(v.l2_[i0][i1])) 2422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines res = true; 2432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (l2_[i0][i1].empty()) 2442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines l1_[i0].clearBit(i1); 2452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return res; 2482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2502d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void copyFrom(const TwoLevelBitVector &v) { 2512d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines clear(); 2522d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines setUnion(v); 2532d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2542d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2552d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Returns true if 'this' intersects with 'v'. 2562d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool intersectsWith(const TwoLevelBitVector &v) const { 2572d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i0 = 0; i0 < kLevel1Size; i0++) { 2582d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines BV t = l1_[i0]; 2592d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines t.setIntersection(v.l1_[i0]); 2602d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines while (!t.empty()) { 2612d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr i1 = t.getAndClearFirstOne(); 2622d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (!v.l1_[i0].getBit(i1)) continue; 2632d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (l2_[i0][i1].intersectsWith(v.l2_[i0][i1])) 2642d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return true; 2652d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2662d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2672d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return false; 2682d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2692d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2702d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // for (TwoLevelBitVector<>::Iterator it(bv); it.hasNext();) { 2712d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // uptr idx = it.next(); 2722d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // use(idx); 2732d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // } 2742d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines class Iterator { 2752d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines public: 2762d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Iterator() { } 2772d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines explicit Iterator(const TwoLevelBitVector &bv) : bv_(bv), i0_(0), i1_(0) { 2782d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines it1_.clear(); 2792d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines it2_.clear(); 2802d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2812d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2822d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool hasNext() const { 2832d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (it1_.hasNext()) return true; 2842d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = i0_; i < kLevel1Size; i++) 2852d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (!bv_.l1_[i].empty()) return true; 2862d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return false; 2872d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2882d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2892d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr next() { 2902d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Printf("++++: %zd %zd; %d %d; size %zd\n", i0_, i1_, it1_.hasNext(), 2912d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // it2_.hasNext(), kSize); 2922d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (!it1_.hasNext() && !it2_.hasNext()) { 2932d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (; i0_ < kLevel1Size; i0_++) { 2942d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (bv_.l1_[i0_].empty()) continue; 2952d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines it1_ = typename BV::Iterator(bv_.l1_[i0_]); 2962d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Printf("+i0: %zd %zd; %d %d; size %zd\n", i0_, i1_, it1_.hasNext(), 2972d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // it2_.hasNext(), kSize); 2982d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines break; 2992d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3002d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3012d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (!it2_.hasNext()) { 3022d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK(it1_.hasNext()); 3032d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines i1_ = it1_.next(); 3042d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines it2_ = typename BV::Iterator(bv_.l2_[i0_][i1_]); 3052d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Printf("++i1: %zd %zd; %d %d; size %zd\n", i0_, i1_, it1_.hasNext(), 3062d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // it2_.hasNext(), kSize); 3072d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3082d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK(it2_.hasNext()); 3092d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr i2 = it2_.next(); 3102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr res = i0_ * BV::kSize * BV::kSize + i1_ * BV::kSize + i2; 3112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Printf("+ret: %zd %zd; %d %d; size %zd; res: %zd\n", i0_, i1_, 3122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // it1_.hasNext(), it2_.hasNext(), kSize, res); 3132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (!it1_.hasNext() && !it2_.hasNext()) 3142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines i0_++; 3152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return res; 3162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines private: 3192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines const TwoLevelBitVector &bv_; 3202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr i0_, i1_; 3212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines typename BV::Iterator it1_, it2_; 3222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines }; 3232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines private: 3252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void check(uptr idx) const { CHECK_LE(idx, size()); } 3262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr idx0(uptr idx) const { 3282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr res = idx / (BV::kSize * BV::kSize); 3292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK_LE(res, kLevel1Size); 3302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return res; 3312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr idx1(uptr idx) const { 3342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr res = (idx / BV::kSize) % BV::kSize; 3352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK_LE(res, BV::kSize); 3362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return res; 3372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr idx2(uptr idx) const { 3402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr res = idx % BV::kSize; 3412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK_LE(res, BV::kSize); 3422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return res; 3432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines BV l1_[kLevel1Size]; 3462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines BV l2_[kLevel1Size][BV::kSize]; 3472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines}; 3482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} // namespace __sanitizer 3502d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3512d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#endif // SANITIZER_BITVECTOR_H 352