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
19namespace __sanitizer {
20
21// Fixed size bit vector based on a single basic integer.
22template <class basic_int_t = uptr>
23class BasicBitVector {
24 public:
25  enum SizeEnum { kSize = sizeof(basic_int_t) * 8 };
26
27  uptr size() const { return kSize; }
28  // No CTOR.
29  void clear() { bits_ = 0; }
30  void setAll() { bits_ = ~(basic_int_t)0; }
31  bool empty() const { return bits_ == 0; }
32
33  // Returns true if the bit has changed from 0 to 1.
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.
41  bool clearBit(uptr idx) {
42    basic_int_t old = bits_;
43    bits_ &= ~mask(idx);
44    return bits_ != old;
45  }
46
47  bool getBit(uptr idx) const { return (bits_ & mask(idx)) != 0; }
48
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.
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.
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.
71  bool setDifference(const BasicBitVector &v) {
72    basic_int_t old = bits_;
73    bits_ &= ~v.bits_;
74    return bits_ != old;
75  }
76
77  void copyFrom(const BasicBitVector &v) { bits_ = v.bits_; }
78
79  // Returns true if 'this' intersects with '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:
90    Iterator() { }
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(); }
95   private:
96    BasicBitVector bv_;
97  };
98
99 private:
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.
110template <uptr kLevel1Size = 1, class BV = BasicBitVector<> >
111class 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
121  uptr size() const { return kSize; }
122
123  void clear() {
124    for (uptr i = 0; i < kLevel1Size; i++)
125      l1_[i].clear();
126  }
127
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
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.
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
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
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
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.
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.
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.
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
250  void copyFrom(const TwoLevelBitVector &v) {
251    clear();
252    setUnion(v);
253  }
254
255  // Returns true if 'this' intersects with '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:
276    Iterator() { }
277    explicit Iterator(const TwoLevelBitVector &bv) : bv_(bv), i0_(0), i1_(0) {
278      it1_.clear();
279      it2_.clear();
280    }
281
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
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:
325  void check(uptr idx) const { CHECK_LE(idx, size()); }
326
327  uptr idx0(uptr idx) const {
328    uptr res = idx / (BV::kSize * BV::kSize);
329    CHECK_LE(res, kLevel1Size);
330    return res;
331  }
332
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
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