Coverage Report

Created: 2018-11-16 02:38

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/ADT/SparseBitVector.h
Line
Count
Source (jump to first uncovered line)
1
//===- llvm/ADT/SparseBitVector.h - Efficient Sparse BitVector --*- 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
// This file defines the SparseBitVector class.  See the doxygen comment for
11
// SparseBitVector for more details on the algorithm used.
12
//
13
//===----------------------------------------------------------------------===//
14
15
#ifndef LLVM_ADT_SPARSEBITVECTOR_H
16
#define LLVM_ADT_SPARSEBITVECTOR_H
17
18
#include "llvm/Support/ErrorHandling.h"
19
#include "llvm/Support/MathExtras.h"
20
#include "llvm/Support/raw_ostream.h"
21
#include <cassert>
22
#include <climits>
23
#include <cstring>
24
#include <iterator>
25
#include <list>
26
27
namespace llvm {
28
29
/// SparseBitVector is an implementation of a bitvector that is sparse by only
30
/// storing the elements that have non-zero bits set.  In order to make this
31
/// fast for the most common cases, SparseBitVector is implemented as a linked
32
/// list of SparseBitVectorElements.  We maintain a pointer to the last
33
/// SparseBitVectorElement accessed (in the form of a list iterator), in order
34
/// to make multiple in-order test/set constant time after the first one is
35
/// executed.  Note that using vectors to store SparseBitVectorElement's does
36
/// not work out very well because it causes insertion in the middle to take
37
/// enormous amounts of time with a large amount of bits.  Other structures that
38
/// have better worst cases for insertion in the middle (various balanced trees,
39
/// etc) do not perform as well in practice as a linked list with this iterator
40
/// kept up to date.  They are also significantly more memory intensive.
41
42
template <unsigned ElementSize = 128> struct SparseBitVectorElement {
43
public:
44
  using BitWord = unsigned long;
45
  using size_type = unsigned;
46
  enum {
47
    BITWORD_SIZE = sizeof(BitWord) * CHAR_BIT,
48
    BITWORDS_PER_ELEMENT = (ElementSize + BITWORD_SIZE - 1) / BITWORD_SIZE,
49
    BITS_PER_ELEMENT = ElementSize
50
  };
51
52
private:
53
  // Index of Element in terms of where first bit starts.
54
  unsigned ElementIndex;
55
  BitWord Bits[BITWORDS_PER_ELEMENT];
56
57
  SparseBitVectorElement() {
58
    ElementIndex = ~0U;
59
    memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
60
  }
61
62
public:
63
1.96M
  explicit SparseBitVectorElement(unsigned Idx) {
64
1.96M
    ElementIndex = Idx;
65
1.96M
    memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
66
1.96M
  }
67
68
  // Comparison.
69
  bool operator==(const SparseBitVectorElement &RHS) const {
70
    if (ElementIndex != RHS.ElementIndex)
71
      return false;
72
    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
73
      if (Bits[i] != RHS.Bits[i])
74
        return false;
75
    return true;
76
  }
77
78
  bool operator!=(const SparseBitVectorElement &RHS) const {
79
    return !(*this == RHS);
80
  }
81
82
  // Return the bits that make up word Idx in our element.
83
403k
  BitWord word(unsigned Idx) const {
84
403k
    assert(Idx < BITWORDS_PER_ELEMENT);
85
403k
    return Bits[Idx];
86
403k
  }
87
88
138M
  unsigned index() const {
89
138M
    return ElementIndex;
90
138M
  }
91
92
393k
  bool empty() const {
93
701k
    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; 
++i307k
)
94
555k
      if (Bits[i])
95
248k
        return false;
96
393k
    
return true145k
;
97
393k
  }
98
99
22.9M
  void set(unsigned Idx) {
100
22.9M
    Bits[Idx / BITWORD_SIZE] |= 1L << (Idx % BITWORD_SIZE);
101
22.9M
  }
102
103
  bool test_and_set(unsigned Idx) {
104
    bool old = test(Idx);
105
    if (!old) {
106
      set(Idx);
107
      return true;
108
    }
109
    return false;
110
  }
111
112
393k
  void reset(unsigned Idx) {
113
393k
    Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE));
114
393k
  }
115
116
37.8M
  bool test(unsigned Idx) const {
117
37.8M
    return Bits[Idx / BITWORD_SIZE] & (1L << (Idx % BITWORD_SIZE));
118
37.8M
  }
119
120
136k
  size_type count() const {
121
136k
    unsigned NumBits = 0;
122
410k
    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; 
++i273k
)
123
273k
      NumBits += countPopulation(Bits[i]);
124
136k
    return NumBits;
125
136k
  }
126
127
  /// find_first - Returns the index of the first set bit.
128
362k
  int find_first() const {
129
437k
    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; 
++i74.8k
)
130
437k
      if (Bits[i] != 0)
131
362k
        return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
132
362k
    
llvm_unreachable0
("Illegal empty element");
133
362k
  }
134
135
  /// find_last - Returns the index of the last set bit.
136
346
  int find_last() const {
137
691
    for (unsigned I = 0; I < BITWORDS_PER_ELEMENT; 
++I345
) {
138
691
      unsigned Idx = BITWORDS_PER_ELEMENT - I - 1;
139
691
      if (Bits[Idx] != 0)
140
346
        return Idx * BITWORD_SIZE + BITWORD_SIZE -
141
346
               countLeadingZeros(Bits[Idx]) - 1;
142
691
    }
143
346
    
llvm_unreachable0
("Illegal empty element");
144
346
  }
145
146
  /// find_next - Returns the index of the next set bit starting from the
147
  /// "Curr" bit. Returns -1 if the next set bit is not found.
148
378k
  int find_next(unsigned Curr) const {
149
378k
    if (Curr >= BITS_PER_ELEMENT)
150
0
      return -1;
151
378k
152
378k
    unsigned WordPos = Curr / BITWORD_SIZE;
153
378k
    unsigned BitPos = Curr % BITWORD_SIZE;
154
378k
    BitWord Copy = Bits[WordPos];
155
378k
    assert(WordPos <= BITWORDS_PER_ELEMENT
156
378k
           && "Word Position outside of element");
157
378k
158
378k
    // Mask off previous bits.
159
378k
    Copy &= ~0UL << BitPos;
160
378k
161
378k
    if (Copy != 0)
162
9.03k
      return WordPos * BITWORD_SIZE + countTrailingZeros(Copy);
163
369k
164
369k
    // Check subsequent words.
165
599k
    
for (unsigned i = WordPos+1; 369k
i < BITWORDS_PER_ELEMENT;
++i230k
)
166
267k
      if (Bits[i] != 0)
167
37.0k
        return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
168
369k
    
return -1332k
;
169
369k
  }
170
171
  // Union this element with RHS and return true if this one changed.
172
352k
  bool unionWith(const SparseBitVectorElement &RHS) {
173
352k
    bool changed = false;
174
1.05M
    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; 
++i705k
) {
175
705k
      BitWord old = changed ? 
047.2k
:
Bits[i]658k
;
176
705k
177
705k
      Bits[i] |= RHS.Bits[i];
178
705k
      if (!changed && 
old != Bits[i]658k
)
179
86.9k
        changed = true;
180
705k
    }
181
352k
    return changed;
182
352k
  }
183
184
  // Return true if we have any bits in common with RHS
185
0
  bool intersects(const SparseBitVectorElement &RHS) const {
186
0
    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
187
0
      if (RHS.Bits[i] & Bits[i])
188
0
        return true;
189
0
    }
190
0
    return false;
191
0
  }
192
193
  // Intersect this Element with RHS and return true if this one changed.
194
  // BecameZero is set to true if this element became all-zero bits.
195
  bool intersectWith(const SparseBitVectorElement &RHS,
196
219
                     bool &BecameZero) {
197
219
    bool changed = false;
198
219
    bool allzero = true;
199
219
200
219
    BecameZero = false;
201
657
    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; 
++i438
) {
202
438
      BitWord old = changed ? 
050
:
Bits[i]388
;
203
438
204
438
      Bits[i] &= RHS.Bits[i];
205
438
      if (Bits[i] != 0)
206
211
        allzero = false;
207
438
208
438
      if (!changed && 
old != Bits[i]388
)
209
50
        changed = true;
210
438
    }
211
219
    BecameZero = allzero;
212
219
    return changed;
213
219
  }
214
215
  // Intersect this Element with the complement of RHS and return true if this
216
  // one changed.  BecameZero is set to true if this element became all-zero
217
  // bits.
218
  bool intersectWithComplement(const SparseBitVectorElement &RHS,
219
619
                               bool &BecameZero) {
220
619
    bool changed = false;
221
619
    bool allzero = true;
222
619
223
619
    BecameZero = false;
224
1.85k
    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; 
++i1.23k
) {
225
1.23k
      BitWord old = changed ? 
0618
:
Bits[i]620
;
226
1.23k
227
1.23k
      Bits[i] &= ~RHS.Bits[i];
228
1.23k
      if (Bits[i] != 0)
229
205
        allzero = false;
230
1.23k
231
1.23k
      if (!changed && 
old != Bits[i]620
)
232
618
        changed = true;
233
1.23k
    }
234
619
    BecameZero = allzero;
235
619
    return changed;
236
619
  }
237
238
  // Three argument version of intersectWithComplement that intersects
239
  // RHS1 & ~RHS2 into this element
240
  void intersectWithComplement(const SparseBitVectorElement &RHS1,
241
                               const SparseBitVectorElement &RHS2,
242
                               bool &BecameZero) {
243
    bool allzero = true;
244
245
    BecameZero = false;
246
    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
247
      Bits[i] = RHS1.Bits[i] & ~RHS2.Bits[i];
248
      if (Bits[i] != 0)
249
        allzero = false;
250
    }
251
    BecameZero = allzero;
252
  }
253
};
254
255
template <unsigned ElementSize = 128>
256
class SparseBitVector {
257
  using ElementList = std::list<SparseBitVectorElement<ElementSize>>;
258
  using ElementListIter = typename ElementList::iterator;
259
  using ElementListConstIter = typename ElementList::const_iterator;
260
  enum {
261
    BITWORD_SIZE = SparseBitVectorElement<ElementSize>::BITWORD_SIZE
262
  };
263
264
  ElementList Elements;
265
  // Pointer to our current Element. This has no visible effect on the external
266
  // state of a SparseBitVector, it's just used to improve performance in the
267
  // common case of testing/modifying bits with similar indices.
268
  mutable ElementListIter CurrElementIter;
269
270
  // This is like std::lower_bound, except we do linear searching from the
271
  // current position.
272
62.5M
  ElementListIter FindLowerBoundImpl(unsigned ElementIndex) const {
273
62.5M
274
62.5M
    // We cache a non-const iterator so we're forced to resort to const_cast to
275
62.5M
    // get the begin/end in the case where 'this' is const. To avoid duplication
276
62.5M
    // of code with the only difference being whether the const cast is present
277
62.5M
    // 'this' is always const in this particular function and we sort out the
278
62.5M
    // difference in FindLowerBound and FindLowerBoundConst.
279
62.5M
    ElementListIter Begin =
280
62.5M
        const_cast<SparseBitVector<ElementSize> *>(this)->Elements.begin();
281
62.5M
    ElementListIter End =
282
62.5M
        const_cast<SparseBitVector<ElementSize> *>(this)->Elements.end();
283
62.5M
284
62.5M
    if (Elements.empty()) {
285
0
      CurrElementIter = Begin;
286
0
      return CurrElementIter;
287
0
    }
288
62.5M
289
62.5M
    // Make sure our current iterator is valid.
290
62.5M
    if (CurrElementIter == End)
291
1.15M
      --CurrElementIter;
292
62.5M
293
62.5M
    // Search from our current iterator, either backwards or forwards,
294
62.5M
    // depending on what element we are looking for.
295
62.5M
    ElementListIter ElementIter = CurrElementIter;
296
62.5M
    if (CurrElementIter->index() == ElementIndex) {
297
57.5M
      return ElementIter;
298
57.5M
    } else 
if (4.98M
CurrElementIter->index() > ElementIndex4.98M
) {
299
5.04M
      while (ElementIter != Begin
300
5.04M
             && 
ElementIter->index() > ElementIndex2.68M
)
301
2.39M
        --ElementIter;
302
2.64M
    } else {
303
6.01M
      while (ElementIter != End &&
304
6.01M
             
ElementIter->index() < ElementIndex4.70M
)
305
3.67M
        ++ElementIter;
306
2.33M
    }
307
62.5M
    CurrElementIter = ElementIter;
308
4.98M
    return ElementIter;
309
62.5M
  }
310
40.9M
  ElementListConstIter FindLowerBoundConst(unsigned ElementIndex) const {
311
40.9M
    return FindLowerBoundImpl(ElementIndex);
312
40.9M
  }
313
21.5M
  ElementListIter FindLowerBound(unsigned ElementIndex) {
314
21.5M
    return FindLowerBoundImpl(ElementIndex);
315
21.5M
  }
316
317
  // Iterator to walk set bits in the bitmap.  This iterator is a lot uglier
318
  // than it would be, in order to be efficient.
319
  class SparseBitVectorIterator {
320
  private:
321
    bool AtEnd;
322
323
    const SparseBitVector<ElementSize> *BitVector = nullptr;
324
325
    // Current element inside of bitmap.
326
    ElementListConstIter Iter;
327
328
    // Current bit number inside of our bitmap.
329
    unsigned BitNumber;
330
331
    // Current word number inside of our element.
332
    unsigned WordNumber;
333
334
    // Current bits from the element.
335
    typename SparseBitVectorElement<ElementSize>::BitWord Bits;
336
337
    // Move our iterator to the first non-zero bit in the bitmap.
338
42.9M
    void AdvanceToFirstNonZero() {
339
42.9M
      if (AtEnd)
340
21.4M
        return;
341
21.4M
      if (BitVector->Elements.empty()) {
342
21.1M
        AtEnd = true;
343
21.1M
        return;
344
21.1M
      }
345
300k
      Iter = BitVector->Elements.begin();
346
300k
      BitNumber = Iter->index() * ElementSize;
347
300k
      unsigned BitPos = Iter->find_first();
348
300k
      BitNumber += BitPos;
349
300k
      WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
350
300k
      Bits = Iter->word(WordNumber);
351
300k
      Bits >>= BitPos % BITWORD_SIZE;
352
300k
    }
353
354
    // Move our iterator to the next non-zero bit.
355
1.09M
    void AdvanceToNextNonZero() {
356
1.09M
      if (AtEnd)
357
0
        return;
358
1.09M
359
3.25M
      
while (1.09M
Bits &&
!(Bits & 1)2.87M
) {
360
2.15M
        Bits >>= 1;
361
2.15M
        BitNumber += 1;
362
2.15M
      }
363
1.09M
364
1.09M
      // See if we ran out of Bits in this word.
365
1.09M
      if (!Bits) {
366
378k
        int NextSetBitNumber = Iter->find_next(BitNumber % ElementSize) ;
367
378k
        // If we ran out of set bits in this element, move to next element.
368
378k
        if (NextSetBitNumber == -1 || 
(BitNumber % ElementSize == 0)46.0k
) {
369
337k
          ++Iter;
370
337k
          WordNumber = 0;
371
337k
372
337k
          // We may run out of elements in the bitmap.
373
337k
          if (Iter == BitVector->Elements.end()) {
374
275k
            AtEnd = true;
375
275k
            return;
376
275k
          }
377
61.6k
          // Set up for next non-zero word in bitmap.
378
61.6k
          BitNumber = Iter->index() * ElementSize;
379
61.6k
          NextSetBitNumber = Iter->find_first();
380
61.6k
          BitNumber += NextSetBitNumber;
381
61.6k
          WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
382
61.6k
          Bits = Iter->word(WordNumber);
383
61.6k
          Bits >>= NextSetBitNumber % BITWORD_SIZE;
384
61.6k
        } else {
385
41.2k
          WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE;
386
41.2k
          Bits = Iter->word(WordNumber);
387
41.2k
          Bits >>= NextSetBitNumber % BITWORD_SIZE;
388
41.2k
          BitNumber = Iter->index() * ElementSize;
389
41.2k
          BitNumber += NextSetBitNumber;
390
41.2k
        }
391
378k
      }
392
1.09M
    }
393
394
  public:
395
    SparseBitVectorIterator() = default;
396
397
    SparseBitVectorIterator(const SparseBitVector<ElementSize> *RHS,
398
42.9M
                            bool end = false):BitVector(RHS) {
399
42.9M
      Iter = BitVector->Elements.begin();
400
42.9M
      BitNumber = 0;
401
42.9M
      Bits = 0;
402
42.9M
      WordNumber = ~0;
403
42.9M
      AtEnd = end;
404
42.9M
      AdvanceToFirstNonZero();
405
42.9M
    }
406
407
    // Preincrement.
408
1.09M
    inline SparseBitVectorIterator& operator++() {
409
1.09M
      ++BitNumber;
410
1.09M
      Bits >>= 1;
411
1.09M
      AdvanceToNextNonZero();
412
1.09M
      return *this;
413
1.09M
    }
414
415
    // Postincrement.
416
    inline SparseBitVectorIterator operator++(int) {
417
      SparseBitVectorIterator tmp = *this;
418
      ++*this;
419
      return tmp;
420
    }
421
422
    // Return the current set bit number.
423
1.25M
    unsigned operator*() const {
424
1.25M
      return BitNumber;
425
1.25M
    }
426
427
22.6M
    bool operator==(const SparseBitVectorIterator &RHS) const {
428
22.6M
      // If they are both at the end, ignore the rest of the fields.
429
22.6M
      if (AtEnd && 
RHS.AtEnd21.4M
)
430
21.4M
        return true;
431
1.23M
      // Otherwise they are the same if they have the same bit number and
432
1.23M
      // bitmap.
433
1.23M
      return AtEnd == RHS.AtEnd && 
RHS.BitNumber == BitNumber0
;
434
1.23M
    }
435
436
22.4M
    bool operator!=(const SparseBitVectorIterator &RHS) const {
437
22.4M
      return !(*this == RHS);
438
22.4M
    }
439
  };
440
441
public:
442
  using iterator = SparseBitVectorIterator;
443
444
7.77M
  SparseBitVector() : Elements(), CurrElementIter(Elements.begin()) {}
445
446
  SparseBitVector(const SparseBitVector &RHS)
447
15.8M
      : Elements(RHS.Elements), CurrElementIter(Elements.begin()) {}
448
  SparseBitVector(SparseBitVector &&RHS)
449
9.24M
      : Elements(std::move(RHS.Elements)), CurrElementIter(Elements.begin()) {}
450
451
  // Clear.
452
9.35M
  void clear() {
453
9.35M
    Elements.clear();
454
9.35M
  }
455
456
  // Assignment
457
44.0k
  SparseBitVector& operator=(const SparseBitVector& RHS) {
458
44.0k
    if (this == &RHS)
459
1
      return *this;
460
44.0k
461
44.0k
    Elements = RHS.Elements;
462
44.0k
    CurrElementIter = Elements.begin();
463
44.0k
    return *this;
464
44.0k
  }
465
4.26M
  SparseBitVector &operator=(SparseBitVector &&RHS) {
466
4.26M
    Elements = std::move(RHS.Elements);
467
4.26M
    CurrElementIter = Elements.begin();
468
4.26M
    return *this;
469
4.26M
  }
470
471
  // Test, Reset, and Set a bit in the bitmap.
472
107M
  bool test(unsigned Idx) const {
473
107M
    if (Elements.empty())
474
66.5M
      return false;
475
40.9M
476
40.9M
    unsigned ElementIndex = Idx / ElementSize;
477
40.9M
    ElementListConstIter ElementIter = FindLowerBoundConst(ElementIndex);
478
40.9M
479
40.9M
    // If we can't find an element that is supposed to contain this bit, there
480
40.9M
    // is nothing more to do.
481
40.9M
    if (ElementIter == Elements.end() ||
482
40.9M
        
ElementIter->index() != ElementIndex39.7M
)
483
3.05M
      return false;
484
37.8M
    return ElementIter->test(Idx % ElementSize);
485
37.8M
  }
486
487
1.42M
  void reset(unsigned Idx) {
488
1.42M
    if (Elements.empty())
489
1.02M
      return;
490
393k
491
393k
    unsigned ElementIndex = Idx / ElementSize;
492
393k
    ElementListIter ElementIter = FindLowerBound(ElementIndex);
493
393k
494
393k
    // If we can't find an element that is supposed to contain this bit, there
495
393k
    // is nothing more to do.
496
393k
    if (ElementIter == Elements.end() ||
497
393k
        ElementIter->index() != ElementIndex)
498
0
      return;
499
393k
    ElementIter->reset(Idx % ElementSize);
500
393k
501
393k
    // When the element is zeroed out, delete it.
502
393k
    if (ElementIter->empty()) {
503
145k
      ++CurrElementIter;
504
145k
      Elements.erase(ElementIter);
505
145k
    }
506
393k
  }
507
508
22.9M
  void set(unsigned Idx) {
509
22.9M
    unsigned ElementIndex = Idx / ElementSize;
510
22.9M
    ElementListIter ElementIter;
511
22.9M
    if (Elements.empty()) {
512
1.79M
      ElementIter = Elements.emplace(Elements.end(), ElementIndex);
513
21.2M
    } else {
514
21.2M
      ElementIter = FindLowerBound(ElementIndex);
515
21.2M
516
21.2M
      if (ElementIter == Elements.end() ||
517
21.2M
          
ElementIter->index() != ElementIndex21.0M
) {
518
171k
        // We may have hit the beginning of our SparseBitVector, in which case,
519
171k
        // we may need to insert right after this element, which requires moving
520
171k
        // the current iterator forward one, because insert does insert before.
521
171k
        if (ElementIter != Elements.end() &&
522
171k
            
ElementIter->index() < ElementIndex52.8k
)
523
3.14k
          ++ElementIter;
524
171k
        ElementIter = Elements.emplace(ElementIter, ElementIndex);
525
171k
      }
526
21.2M
    }
527
22.9M
    CurrElementIter = ElementIter;
528
22.9M
529
22.9M
    ElementIter->set(Idx % ElementSize);
530
22.9M
  }
531
532
  bool test_and_set(unsigned Idx) {
533
    bool old = test(Idx);
534
    if (!old) {
535
      set(Idx);
536
      return true;
537
    }
538
    return false;
539
  }
540
541
  bool operator!=(const SparseBitVector &RHS) const {
542
    return !(*this == RHS);
543
  }
544
545
  bool operator==(const SparseBitVector &RHS) const {
546
    ElementListConstIter Iter1 = Elements.begin();
547
    ElementListConstIter Iter2 = RHS.Elements.begin();
548
549
    for (; Iter1 != Elements.end() && Iter2 != RHS.Elements.end();
550
         ++Iter1, ++Iter2) {
551
      if (*Iter1 != *Iter2)
552
        return false;
553
    }
554
    return Iter1 == Elements.end() && Iter2 == RHS.Elements.end();
555
  }
556
557
  // Union our bitmap with the RHS and return true if we changed.
558
386k
  bool operator|=(const SparseBitVector &RHS) {
559
386k
    if (this == &RHS)
560
1
      return false;
561
386k
562
386k
    bool changed = false;
563
386k
    ElementListIter Iter1 = Elements.begin();
564
386k
    ElementListConstIter Iter2 = RHS.Elements.begin();
565
386k
566
386k
    // If RHS is empty, we are done
567
386k
    if (RHS.Elements.empty())
568
0
      return false;
569
386k
570
791k
    
while (386k
Iter2 != RHS.Elements.end()) {
571
404k
      if (Iter1 == Elements.end() || 
Iter1->index() > Iter2->index()369k
) {
572
36.0k
        Elements.insert(Iter1, *Iter2);
573
36.0k
        ++Iter2;
574
36.0k
        changed = true;
575
368k
      } else if (Iter1->index() == Iter2->index()) {
576
352k
        changed |= Iter1->unionWith(*Iter2);
577
352k
        ++Iter1;
578
352k
        ++Iter2;
579
352k
      } else {
580
15.7k
        ++Iter1;
581
15.7k
      }
582
404k
    }
583
386k
    CurrElementIter = Elements.begin();
584
386k
    return changed;
585
386k
  }
586
587
  // Intersect our bitmap with the RHS and return true if ours changed.
588
226
  bool operator&=(const SparseBitVector &RHS) {
589
226
    if (this == &RHS)
590
1
      return false;
591
225
592
225
    bool changed = false;
593
225
    ElementListIter Iter1 = Elements.begin();
594
225
    ElementListConstIter Iter2 = RHS.Elements.begin();
595
225
596
225
    // Check if both bitmaps are empty.
597
225
    if (Elements.empty() && 
RHS.Elements.empty()4
)
598
0
      return false;
599
225
600
225
    // Loop through, intersecting as we go, erasing elements when necessary.
601
446
    
while (225
Iter2 != RHS.Elements.end()) {
602
226
      if (Iter1 == Elements.end()) {
603
5
        CurrElementIter = Elements.begin();
604
5
        return changed;
605
5
      }
606
221
607
221
      if (Iter1->index() > Iter2->index()) {
608
1
        ++Iter2;
609
220
      } else if (Iter1->index() == Iter2->index()) {
610
219
        bool BecameZero;
611
219
        changed |= Iter1->intersectWith(*Iter2, BecameZero);
612
219
        if (BecameZero) {
613
8
          ElementListIter IterTmp = Iter1;
614
8
          ++Iter1;
615
8
          Elements.erase(IterTmp);
616
211
        } else {
617
211
          ++Iter1;
618
211
        }
619
219
        ++Iter2;
620
219
      } else {
621
1
        ElementListIter IterTmp = Iter1;
622
1
        ++Iter1;
623
1
        Elements.erase(IterTmp);
624
1
        changed = true;
625
1
      }
626
221
    }
627
225
    
if (220
Iter1 != Elements.end()220
) {
628
1
      Elements.erase(Iter1, Elements.end());
629
1
      changed = true;
630
1
    }
631
220
    CurrElementIter = Elements.begin();
632
220
    return changed;
633
225
  }
634
635
  // Intersect our bitmap with the complement of the RHS and return true
636
  // if ours changed.
637
2.90M
  bool intersectWithComplement(const SparseBitVector &RHS) {
638
2.90M
    if (this == &RHS) {
639
3
      if (!empty()) {
640
2
        clear();
641
2
        return true;
642
2
      }
643
1
      return false;
644
1
    }
645
2.90M
646
2.90M
    bool changed = false;
647
2.90M
    ElementListIter Iter1 = Elements.begin();
648
2.90M
    ElementListConstIter Iter2 = RHS.Elements.begin();
649
2.90M
650
2.90M
    // If either our bitmap or RHS is empty, we are done
651
2.90M
    if (Elements.empty() || 
RHS.Elements.empty()6.36k
)
652
2.90M
      return false;
653
618
654
618
    // Loop through, intersecting as we go, erasing elements when necessary.
655
1.23k
    
while (618
Iter2 != RHS.Elements.end()) {
656
619
      if (Iter1 == Elements.end()) {
657
0
        CurrElementIter = Elements.begin();
658
0
        return changed;
659
0
      }
660
619
661
619
      if (Iter1->index() > Iter2->index()) {
662
0
        ++Iter2;
663
619
      } else if (Iter1->index() == Iter2->index()) {
664
619
        bool BecameZero;
665
619
        changed |= Iter1->intersectWithComplement(*Iter2, BecameZero);
666
619
        if (BecameZero) {
667
414
          ElementListIter IterTmp = Iter1;
668
414
          ++Iter1;
669
414
          Elements.erase(IterTmp);
670
414
        } else {
671
205
          ++Iter1;
672
205
        }
673
619
        ++Iter2;
674
619
      } else {
675
0
        ++Iter1;
676
0
      }
677
619
    }
678
618
    CurrElementIter = Elements.begin();
679
618
    return changed;
680
618
  }
681
682
  bool intersectWithComplement(const SparseBitVector<ElementSize> *RHS) const {
683
    return intersectWithComplement(*RHS);
684
  }
685
686
  //  Three argument version of intersectWithComplement.
687
  //  Result of RHS1 & ~RHS2 is stored into this bitmap.
688
  void intersectWithComplement(const SparseBitVector<ElementSize> &RHS1,
689
                               const SparseBitVector<ElementSize> &RHS2)
690
  {
691
    if (this == &RHS1) {
692
      intersectWithComplement(RHS2);
693
      return;
694
    } else if (this == &RHS2) {
695
      SparseBitVector RHS2Copy(RHS2);
696
      intersectWithComplement(RHS1, RHS2Copy);
697
      return;
698
    }
699
700
    Elements.clear();
701
    CurrElementIter = Elements.begin();
702
    ElementListConstIter Iter1 = RHS1.Elements.begin();
703
    ElementListConstIter Iter2 = RHS2.Elements.begin();
704
705
    // If RHS1 is empty, we are done
706
    // If RHS2 is empty, we still have to copy RHS1
707
    if (RHS1.Elements.empty())
708
      return;
709
710
    // Loop through, intersecting as we go, erasing elements when necessary.
711
    while (Iter2 != RHS2.Elements.end()) {
712
      if (Iter1 == RHS1.Elements.end())
713
        return;
714
715
      if (Iter1->index() > Iter2->index()) {
716
        ++Iter2;
717
      } else if (Iter1->index() == Iter2->index()) {
718
        bool BecameZero = false;
719
        Elements.emplace_back(Iter1->index());
720
        Elements.back().intersectWithComplement(*Iter1, *Iter2, BecameZero);
721
        if (BecameZero)
722
          Elements.pop_back();
723
        ++Iter1;
724
        ++Iter2;
725
      } else {
726
        Elements.push_back(*Iter1++);
727
      }
728
    }
729
730
    // copy the remaining elements
731
    std::copy(Iter1, RHS1.Elements.end(), std::back_inserter(Elements));
732
  }
733
734
  void intersectWithComplement(const SparseBitVector<ElementSize> *RHS1,
735
                               const SparseBitVector<ElementSize> *RHS2) {
736
    intersectWithComplement(*RHS1, *RHS2);
737
  }
738
739
  bool intersects(const SparseBitVector<ElementSize> *RHS) const {
740
    return intersects(*RHS);
741
  }
742
743
  // Return true if we share any bits in common with RHS
744
90
  bool intersects(const SparseBitVector<ElementSize> &RHS) const {
745
90
    ElementListConstIter Iter1 = Elements.begin();
746
90
    ElementListConstIter Iter2 = RHS.Elements.begin();
747
90
748
90
    // Check if both bitmaps are empty.
749
90
    if (Elements.empty() && 
RHS.Elements.empty()0
)
750
0
      return false;
751
90
752
90
    // Loop through, intersecting stopping when we hit bits in common.
753
90
    while (Iter2 != RHS.Elements.end()) {
754
0
      if (Iter1 == Elements.end())
755
0
        return false;
756
0
757
0
      if (Iter1->index() > Iter2->index()) {
758
0
        ++Iter2;
759
0
      } else if (Iter1->index() == Iter2->index()) {
760
0
        if (Iter1->intersects(*Iter2))
761
0
          return true;
762
0
        ++Iter1;
763
0
        ++Iter2;
764
0
      } else {
765
0
        ++Iter1;
766
0
      }
767
0
    }
768
90
    return false;
769
90
  }
770
771
  // Return true iff all bits set in this SparseBitVector are
772
  // also set in RHS.
773
  bool contains(const SparseBitVector<ElementSize> &RHS) const {
774
    SparseBitVector<ElementSize> Result(*this);
775
    Result &= RHS;
776
    return (Result == RHS);
777
  }
778
779
  // Return the first set bit in the bitmap.  Return -1 if no bits are set.
780
137
  int find_first() const {
781
137
    if (Elements.empty())
782
6
      return -1;
783
131
    const SparseBitVectorElement<ElementSize> &First = *(Elements.begin());
784
131
    return (First.index() * ElementSize) + First.find_first();
785
131
  }
786
787
  // Return the last set bit in the bitmap.  Return -1 if no bits are set.
788
686
  int find_last() const {
789
686
    if (Elements.empty())
790
340
      return -1;
791
346
    const SparseBitVectorElement<ElementSize> &Last = *(Elements.rbegin());
792
346
    return (Last.index() * ElementSize) + Last.find_last();
793
346
  }
794
795
  // Return true if the SparseBitVector is empty
796
11.8M
  bool empty() const {
797
11.8M
    return Elements.empty();
798
11.8M
  }
799
800
132k
  unsigned count() const {
801
132k
    unsigned BitCount = 0;
802
132k
    for (ElementListConstIter Iter = Elements.begin();
803
268k
         Iter != Elements.end();
804
136k
         ++Iter)
805
136k
      BitCount += Iter->count();
806
132k
807
132k
    return BitCount;
808
132k
  }
809
810
21.4M
  iterator begin() const {
811
21.4M
    return iterator(this);
812
21.4M
  }
813
814
21.4M
  iterator end() const {
815
21.4M
    return iterator(this, true);
816
21.4M
  }
817
};
818
819
// Convenience functions to allow Or and And without dereferencing in the user
820
// code.
821
822
template <unsigned ElementSize>
823
inline bool operator |=(SparseBitVector<ElementSize> &LHS,
824
                        const SparseBitVector<ElementSize> *RHS) {
825
  return LHS |= *RHS;
826
}
827
828
template <unsigned ElementSize>
829
inline bool operator |=(SparseBitVector<ElementSize> *LHS,
830
                        const SparseBitVector<ElementSize> &RHS) {
831
  return LHS->operator|=(RHS);
832
}
833
834
template <unsigned ElementSize>
835
inline bool operator &=(SparseBitVector<ElementSize> *LHS,
836
                        const SparseBitVector<ElementSize> &RHS) {
837
  return LHS->operator&=(RHS);
838
}
839
840
template <unsigned ElementSize>
841
inline bool operator &=(SparseBitVector<ElementSize> &LHS,
842
                        const SparseBitVector<ElementSize> *RHS) {
843
  return LHS &= *RHS;
844
}
845
846
// Convenience functions for infix union, intersection, difference operators.
847
848
template <unsigned ElementSize>
849
inline SparseBitVector<ElementSize>
850
operator|(const SparseBitVector<ElementSize> &LHS,
851
          const SparseBitVector<ElementSize> &RHS) {
852
  SparseBitVector<ElementSize> Result(LHS);
853
  Result |= RHS;
854
  return Result;
855
}
856
857
template <unsigned ElementSize>
858
inline SparseBitVector<ElementSize>
859
operator&(const SparseBitVector<ElementSize> &LHS,
860
          const SparseBitVector<ElementSize> &RHS) {
861
  SparseBitVector<ElementSize> Result(LHS);
862
  Result &= RHS;
863
  return Result;
864
}
865
866
template <unsigned ElementSize>
867
inline SparseBitVector<ElementSize>
868
operator-(const SparseBitVector<ElementSize> &LHS,
869
          const SparseBitVector<ElementSize> &RHS) {
870
  SparseBitVector<ElementSize> Result;
871
  Result.intersectWithComplement(LHS, RHS);
872
  return Result;
873
}
874
875
// Dump a SparseBitVector to a stream
876
template <unsigned ElementSize>
877
void dump(const SparseBitVector<ElementSize> &LHS, raw_ostream &out) {
878
  out << "[";
879
880
  typename SparseBitVector<ElementSize>::iterator bi = LHS.begin(),
881
    be = LHS.end();
882
  if (bi != be) {
883
    out << *bi;
884
    for (++bi; bi != be; ++bi) {
885
      out << " " << *bi;
886
    }
887
  }
888
  out << "]\n";
889
}
890
891
} // end namespace llvm
892
893
#endif // LLVM_ADT_SPARSEBITVECTOR_H