1 //===-- sanitizer_bitvector.h -----------------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Specializer BitVector implementation.
12 //===----------------------------------------------------------------------===//
14 #ifndef SANITIZER_BITVECTOR_H
15 #define SANITIZER_BITVECTOR_H
17 #include "sanitizer_common.h"
19 namespace __sanitizer {
21 // Fixed size bit vector based on a single basic integer.
22 template <class basic_int_t = uptr>
23 class BasicBitVector {
25 enum SizeEnum : uptr { kSize = sizeof(basic_int_t) * 8 };
27 uptr size() const { return kSize; }
29 void clear() { bits_ = 0; }
30 void setAll() { bits_ = ~(basic_int_t)0; }
31 bool empty() const { return bits_ == 0; }
33 // Returns true if the bit has changed from 0 to 1.
34 bool setBit(uptr idx) {
35 basic_int_t old = bits_;
40 // Returns true if the bit has changed from 1 to 0.
41 bool clearBit(uptr idx) {
42 basic_int_t old = bits_;
47 bool getBit(uptr idx) const { return (bits_ & mask(idx)) != 0; }
49 uptr getAndClearFirstOne() {
51 uptr idx = LeastSignificantSetBitIndex(bits_);
56 // Do "this |= v" and return whether new bits have been added.
57 bool setUnion(const BasicBitVector &v) {
58 basic_int_t old = bits_;
63 // Do "this &= v" and return whether any bits have been removed.
64 bool setIntersection(const BasicBitVector &v) {
65 basic_int_t old = bits_;
70 // Do "this &= ~v" and return whether any bits have been removed.
71 bool setDifference(const BasicBitVector &v) {
72 basic_int_t old = bits_;
77 void copyFrom(const BasicBitVector &v) { bits_ = v.bits_; }
79 // Returns true if 'this' intersects with 'v'.
80 bool intersectsWith(const BasicBitVector &v) const {
81 return (bits_ & v.bits_) != 0;
84 // for (BasicBitVector<>::Iterator it(bv); it.hasNext();) {
85 // uptr idx = it.next();
91 explicit Iterator(const BasicBitVector &bv) : bv_(bv) {}
92 bool hasNext() const { return !bv_.empty(); }
93 uptr next() { return bv_.getAndClearFirstOne(); }
94 void clear() { bv_.clear(); }
100 basic_int_t mask(uptr idx) const {
101 CHECK_LT(idx, size());
102 return (basic_int_t)1UL << idx;
107 // Fixed size bit vector of (kLevel1Size*BV::kSize**2) bits.
108 // The implementation is optimized for better performance on
109 // sparse bit vectors, i.e. the those with few set bits.
110 template <uptr kLevel1Size = 1, class BV = BasicBitVector<> >
111 class TwoLevelBitVector {
112 // This is essentially a 2-level bit vector.
113 // Set bit in the first level BV indicates that there are set bits
114 // in the corresponding BV of the second level.
115 // This structure allows O(kLevel1Size) time for clear() and empty(),
116 // as well fast handling of sparse BVs.
118 enum SizeEnum : uptr { kSize = BV::kSize * BV::kSize * kLevel1Size };
121 uptr size() const { return kSize; }
124 for (uptr i = 0; i < kLevel1Size; i++)
129 for (uptr i0 = 0; i0 < kLevel1Size; i0++) {
131 for (uptr i1 = 0; i1 < BV::kSize; i1++)
132 l2_[i0][i1].setAll();
137 for (uptr i = 0; i < kLevel1Size; i++)
143 // Returns true if the bit has changed from 0 to 1.
144 bool setBit(uptr idx) {
149 if (!l1_[i0].getBit(i1)) {
153 bool res = l2_[i0][i1].setBit(i2);
154 // Printf("%s: %zd => %zd %zd %zd; %d\n", __func__,
155 // idx, i0, i1, i2, res);
159 bool clearBit(uptr idx) {
165 if (l1_[i0].getBit(i1)) {
166 res = l2_[i0][i1].clearBit(i2);
167 if (l2_[i0][i1].empty())
168 l1_[i0].clearBit(i1);
173 bool getBit(uptr idx) const {
178 // Printf("%s: %zd => %zd %zd %zd\n", __func__, idx, i0, i1, i2);
179 return l1_[i0].getBit(i1) && l2_[i0][i1].getBit(i2);
182 uptr getAndClearFirstOne() {
183 for (uptr i0 = 0; i0 < kLevel1Size; i0++) {
184 if (l1_[i0].empty()) continue;
185 uptr i1 = l1_[i0].getAndClearFirstOne();
186 uptr i2 = l2_[i0][i1].getAndClearFirstOne();
187 if (!l2_[i0][i1].empty())
189 uptr res = i0 * BV::kSize * BV::kSize + i1 * BV::kSize + i2;
190 // Printf("getAndClearFirstOne: %zd %zd %zd => %zd\n", i0, i1, i2, res);
197 // Do "this |= v" and return whether new bits have been added.
198 bool setUnion(const TwoLevelBitVector &v) {
200 for (uptr i0 = 0; i0 < kLevel1Size; i0++) {
203 uptr i1 = t.getAndClearFirstOne();
204 if (l1_[i0].setBit(i1))
206 if (l2_[i0][i1].setUnion(v.l2_[i0][i1]))
213 // Do "this &= v" and return whether any bits have been removed.
214 bool setIntersection(const TwoLevelBitVector &v) {
216 for (uptr i0 = 0; i0 < kLevel1Size; i0++) {
217 if (l1_[i0].setIntersection(v.l1_[i0]))
219 if (!l1_[i0].empty()) {
222 uptr i1 = t.getAndClearFirstOne();
223 if (l2_[i0][i1].setIntersection(v.l2_[i0][i1]))
225 if (l2_[i0][i1].empty())
226 l1_[i0].clearBit(i1);
233 // Do "this &= ~v" and return whether any bits have been removed.
234 bool setDifference(const TwoLevelBitVector &v) {
236 for (uptr i0 = 0; i0 < kLevel1Size; i0++) {
238 t.setIntersection(v.l1_[i0]);
240 uptr i1 = t.getAndClearFirstOne();
241 if (l2_[i0][i1].setDifference(v.l2_[i0][i1]))
243 if (l2_[i0][i1].empty())
244 l1_[i0].clearBit(i1);
250 void copyFrom(const TwoLevelBitVector &v) {
255 // Returns true if 'this' intersects with 'v'.
256 bool intersectsWith(const TwoLevelBitVector &v) const {
257 for (uptr i0 = 0; i0 < kLevel1Size; i0++) {
259 t.setIntersection(v.l1_[i0]);
261 uptr i1 = t.getAndClearFirstOne();
262 if (!v.l1_[i0].getBit(i1)) continue;
263 if (l2_[i0][i1].intersectsWith(v.l2_[i0][i1]))
270 // for (TwoLevelBitVector<>::Iterator it(bv); it.hasNext();) {
271 // uptr idx = it.next();
277 explicit Iterator(const TwoLevelBitVector &bv) : bv_(bv), i0_(0), i1_(0) {
282 bool hasNext() const {
283 if (it1_.hasNext()) return true;
284 for (uptr i = i0_; i < kLevel1Size; i++)
285 if (!bv_.l1_[i].empty()) return true;
290 // Printf("++++: %zd %zd; %d %d; size %zd\n", i0_, i1_, it1_.hasNext(),
291 // it2_.hasNext(), kSize);
292 if (!it1_.hasNext() && !it2_.hasNext()) {
293 for (; i0_ < kLevel1Size; i0_++) {
294 if (bv_.l1_[i0_].empty()) continue;
295 it1_ = typename BV::Iterator(bv_.l1_[i0_]);
296 // Printf("+i0: %zd %zd; %d %d; size %zd\n", i0_, i1_, it1_.hasNext(),
297 // it2_.hasNext(), kSize);
301 if (!it2_.hasNext()) {
302 CHECK(it1_.hasNext());
304 it2_ = typename BV::Iterator(bv_.l2_[i0_][i1_]);
305 // Printf("++i1: %zd %zd; %d %d; size %zd\n", i0_, i1_, it1_.hasNext(),
306 // it2_.hasNext(), kSize);
308 CHECK(it2_.hasNext());
309 uptr i2 = it2_.next();
310 uptr res = i0_ * BV::kSize * BV::kSize + i1_ * BV::kSize + i2;
311 // Printf("+ret: %zd %zd; %d %d; size %zd; res: %zd\n", i0_, i1_,
312 // it1_.hasNext(), it2_.hasNext(), kSize, res);
313 if (!it1_.hasNext() && !it2_.hasNext())
319 const TwoLevelBitVector &bv_;
321 typename BV::Iterator it1_, it2_;
325 void check(uptr idx) const { CHECK_LE(idx, size()); }
327 uptr idx0(uptr idx) const {
328 uptr res = idx / (BV::kSize * BV::kSize);
329 CHECK_LE(res, kLevel1Size);
333 uptr idx1(uptr idx) const {
334 uptr res = (idx / BV::kSize) % BV::kSize;
335 CHECK_LE(res, BV::kSize);
339 uptr idx2(uptr idx) const {
340 uptr res = idx % BV::kSize;
341 CHECK_LE(res, BV::kSize);
346 BV l2_[kLevel1Size][BV::kSize];
349 } // namespace __sanitizer
351 #endif // SANITIZER_BITVECTOR_H