1 //===-- sanitizer_bitvector.h -----------------------------------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // Specializer BitVector implementation.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef SANITIZER_BITVECTOR_H
15 #define SANITIZER_BITVECTOR_H
16 
17 #include "sanitizer_common.h"
18 
19 namespace __sanitizer {
20 
21 // Fixed size bit vector based on a single basic integer.
22 template <class basic_int_t = uptr>
23 class BasicBitVector {
24  public:
25   enum SizeEnum { kSize = sizeof(basic_int_t) * 8 };
26 
size()27   uptr size() const { return kSize; }
28   // No CTOR.
clear()29   void clear() { bits_ = 0; }
setAll()30   void setAll() { bits_ = ~(basic_int_t)0; }
empty()31   bool empty() const { return bits_ == 0; }
32 
33   // Returns true if the bit has changed from 0 to 1.
setBit(uptr idx)34   bool setBit(uptr idx) {
35     basic_int_t old = bits_;
36     bits_ |= mask(idx);
37     return bits_ != old;
38   }
39 
40   // Returns true if the bit has changed from 1 to 0.
clearBit(uptr idx)41   bool clearBit(uptr idx) {
42     basic_int_t old = bits_;
43     bits_ &= ~mask(idx);
44     return bits_ != old;
45   }
46 
getBit(uptr idx)47   bool getBit(uptr idx) const { return (bits_ & mask(idx)) != 0; }
48 
getAndClearFirstOne()49   uptr getAndClearFirstOne() {
50     CHECK(!empty());
51     uptr idx = LeastSignificantSetBitIndex(bits_);
52     clearBit(idx);
53     return idx;
54   }
55 
56   // Do "this |= v" and return whether new bits have been added.
setUnion(const BasicBitVector & v)57   bool setUnion(const BasicBitVector &v) {
58     basic_int_t old = bits_;
59     bits_ |= v.bits_;
60     return bits_ != old;
61   }
62 
63   // Do "this &= v" and return whether any bits have been removed.
setIntersection(const BasicBitVector & v)64   bool setIntersection(const BasicBitVector &v) {
65     basic_int_t old = bits_;
66     bits_ &= v.bits_;
67     return bits_ != old;
68   }
69 
70   // Do "this &= ~v" and return whether any bits have been removed.
setDifference(const BasicBitVector & v)71   bool setDifference(const BasicBitVector &v) {
72     basic_int_t old = bits_;
73     bits_ &= ~v.bits_;
74     return bits_ != old;
75   }
76 
copyFrom(const BasicBitVector & v)77   void copyFrom(const BasicBitVector &v) { bits_ = v.bits_; }
78 
79   // Returns true if 'this' intersects with 'v'.
intersectsWith(const BasicBitVector & v)80   bool intersectsWith(const BasicBitVector &v) const {
81     return (bits_ & v.bits_) != 0;
82   }
83 
84   // for (BasicBitVector<>::Iterator it(bv); it.hasNext();) {
85   //   uptr idx = it.next();
86   //   use(idx);
87   // }
88   class Iterator {
89    public:
Iterator()90     Iterator() { }
Iterator(const BasicBitVector & bv)91     explicit Iterator(const BasicBitVector &bv) : bv_(bv) {}
hasNext()92     bool hasNext() const { return !bv_.empty(); }
next()93     uptr next() { return bv_.getAndClearFirstOne(); }
clear()94     void clear() { bv_.clear(); }
95    private:
96     BasicBitVector bv_;
97   };
98 
99  private:
mask(uptr idx)100   basic_int_t mask(uptr idx) const {
101     CHECK_LT(idx, size());
102     return (basic_int_t)1UL << idx;
103   }
104   basic_int_t bits_;
105 };
106 
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.
117  public:
118   enum SizeEnum { kSize = BV::kSize * BV::kSize * kLevel1Size };
119   // No CTOR.
120 
size()121   uptr size() const { return kSize; }
122 
clear()123   void clear() {
124     for (uptr i = 0; i < kLevel1Size; i++)
125       l1_[i].clear();
126   }
127 
setAll()128   void setAll() {
129     for (uptr i0 = 0; i0 < kLevel1Size; i0++) {
130       l1_[i0].setAll();
131       for (uptr i1 = 0; i1 < BV::kSize; i1++)
132         l2_[i0][i1].setAll();
133     }
134   }
135 
empty()136   bool empty() const {
137     for (uptr i = 0; i < kLevel1Size; i++)
138       if (!l1_[i].empty())
139         return false;
140     return true;
141   }
142 
143   // Returns true if the bit has changed from 0 to 1.
setBit(uptr idx)144   bool setBit(uptr idx) {
145     check(idx);
146     uptr i0 = idx0(idx);
147     uptr i1 = idx1(idx);
148     uptr i2 = idx2(idx);
149     if (!l1_[i0].getBit(i1)) {
150       l1_[i0].setBit(i1);
151       l2_[i0][i1].clear();
152     }
153     bool res = l2_[i0][i1].setBit(i2);
154     // Printf("%s: %zd => %zd %zd %zd; %d\n", __func__,
155     // idx, i0, i1, i2, res);
156     return res;
157   }
158 
clearBit(uptr idx)159   bool clearBit(uptr idx) {
160     check(idx);
161     uptr i0 = idx0(idx);
162     uptr i1 = idx1(idx);
163     uptr i2 = idx2(idx);
164     bool res = false;
165     if (l1_[i0].getBit(i1)) {
166       res = l2_[i0][i1].clearBit(i2);
167       if (l2_[i0][i1].empty())
168         l1_[i0].clearBit(i1);
169     }
170     return res;
171   }
172 
getBit(uptr idx)173   bool getBit(uptr idx) const {
174     check(idx);
175     uptr i0 = idx0(idx);
176     uptr i1 = idx1(idx);
177     uptr i2 = idx2(idx);
178     // Printf("%s: %zd => %zd %zd %zd\n", __func__, idx, i0, i1, i2);
179     return l1_[i0].getBit(i1) && l2_[i0][i1].getBit(i2);
180   }
181 
getAndClearFirstOne()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())
188         l1_[i0].setBit(i1);
189       uptr res = i0 * BV::kSize * BV::kSize + i1 * BV::kSize + i2;
190       // Printf("getAndClearFirstOne: %zd %zd %zd => %zd\n", i0, i1, i2, res);
191       return res;
192     }
193     CHECK(0);
194     return 0;
195   }
196 
197   // Do "this |= v" and return whether new bits have been added.
setUnion(const TwoLevelBitVector & v)198   bool setUnion(const TwoLevelBitVector &v) {
199     bool res = false;
200     for (uptr i0 = 0; i0 < kLevel1Size; i0++) {
201       BV t = v.l1_[i0];
202       while (!t.empty()) {
203         uptr i1 = t.getAndClearFirstOne();
204         if (l1_[i0].setBit(i1))
205           l2_[i0][i1].clear();
206         if (l2_[i0][i1].setUnion(v.l2_[i0][i1]))
207           res = true;
208       }
209     }
210     return res;
211   }
212 
213   // Do "this &= v" and return whether any bits have been removed.
setIntersection(const TwoLevelBitVector & v)214   bool setIntersection(const TwoLevelBitVector &v) {
215     bool res = false;
216     for (uptr i0 = 0; i0 < kLevel1Size; i0++) {
217       if (l1_[i0].setIntersection(v.l1_[i0]))
218         res = true;
219       if (!l1_[i0].empty()) {
220         BV t = l1_[i0];
221         while (!t.empty()) {
222           uptr i1 = t.getAndClearFirstOne();
223           if (l2_[i0][i1].setIntersection(v.l2_[i0][i1]))
224             res = true;
225           if (l2_[i0][i1].empty())
226             l1_[i0].clearBit(i1);
227         }
228       }
229     }
230     return res;
231   }
232 
233   // Do "this &= ~v" and return whether any bits have been removed.
setDifference(const TwoLevelBitVector & v)234   bool setDifference(const TwoLevelBitVector &v) {
235     bool res = false;
236     for (uptr i0 = 0; i0 < kLevel1Size; i0++) {
237       BV t = l1_[i0];
238       t.setIntersection(v.l1_[i0]);
239       while (!t.empty()) {
240         uptr i1 = t.getAndClearFirstOne();
241         if (l2_[i0][i1].setDifference(v.l2_[i0][i1]))
242           res = true;
243         if (l2_[i0][i1].empty())
244           l1_[i0].clearBit(i1);
245       }
246     }
247     return res;
248   }
249 
copyFrom(const TwoLevelBitVector & v)250   void copyFrom(const TwoLevelBitVector &v) {
251     clear();
252     setUnion(v);
253   }
254 
255   // Returns true if 'this' intersects with 'v'.
intersectsWith(const TwoLevelBitVector & v)256   bool intersectsWith(const TwoLevelBitVector &v) const {
257     for (uptr i0 = 0; i0 < kLevel1Size; i0++) {
258       BV t = l1_[i0];
259       t.setIntersection(v.l1_[i0]);
260       while (!t.empty()) {
261         uptr i1 = t.getAndClearFirstOne();
262         if (!v.l1_[i0].getBit(i1)) continue;
263         if (l2_[i0][i1].intersectsWith(v.l2_[i0][i1]))
264           return true;
265       }
266     }
267     return false;
268   }
269 
270   // for (TwoLevelBitVector<>::Iterator it(bv); it.hasNext();) {
271   //   uptr idx = it.next();
272   //   use(idx);
273   // }
274   class Iterator {
275    public:
Iterator()276     Iterator() { }
Iterator(const TwoLevelBitVector & bv)277     explicit Iterator(const TwoLevelBitVector &bv) : bv_(bv), i0_(0), i1_(0) {
278       it1_.clear();
279       it2_.clear();
280     }
281 
hasNext()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;
286       return false;
287     }
288 
next()289     uptr next() {
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);
298           break;
299         }
300       }
301       if (!it2_.hasNext()) {
302         CHECK(it1_.hasNext());
303         i1_ = it1_.next();
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);
307       }
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())
314         i0_++;
315       return res;
316     }
317 
318    private:
319     const TwoLevelBitVector &bv_;
320     uptr i0_, i1_;
321     typename BV::Iterator it1_, it2_;
322   };
323 
324  private:
check(uptr idx)325   void check(uptr idx) const { CHECK_LE(idx, size()); }
326 
idx0(uptr idx)327   uptr idx0(uptr idx) const {
328     uptr res = idx / (BV::kSize * BV::kSize);
329     CHECK_LE(res, kLevel1Size);
330     return res;
331   }
332 
idx1(uptr idx)333   uptr idx1(uptr idx) const {
334     uptr res = (idx / BV::kSize) % BV::kSize;
335     CHECK_LE(res, BV::kSize);
336     return res;
337   }
338 
idx2(uptr idx)339   uptr idx2(uptr idx) const {
340     uptr res = idx % BV::kSize;
341     CHECK_LE(res, BV::kSize);
342     return res;
343   }
344 
345   BV l1_[kLevel1Size];
346   BV l2_[kLevel1Size][BV::kSize];
347 };
348 
349 } // namespace __sanitizer
350 
351 #endif // SANITIZER_BITVECTOR_H
352