Coverage Report

Created: 2018-09-19 20:53

/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.91M
  explicit SparseBitVectorElement(unsigned Idx) {
64
1.91M
    ElementIndex = Idx;
65
1.91M
    memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
66
1.91M
  }
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
361k
  BitWord word(unsigned Idx) const {
84
361k
    assert(Idx < BITWORDS_PER_ELEMENT);
85
361k
    return Bits[Idx];
86
361k
  }
87
88
137M
  unsigned index() const {
89
137M
    return ElementIndex;
90
137M
  }
91
92
385k
  bool empty() const {
93
682k
    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; 
++i297k
)
94
541k
      if (Bits[i])
95
243k
        return false;
96
385k
    
return true141k
;
97
385k
  }
98
99
22.8M
  void set(unsigned Idx) {
100
22.8M
    Bits[Idx / BITWORD_SIZE] |= 1L << (Idx % BITWORD_SIZE);
101
22.8M
  }
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
385k
  void reset(unsigned Idx) {
113
385k
    Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE));
114
385k
  }
115
116
37.6M
  bool test(unsigned Idx) const {
117
37.6M
    return Bits[Idx / BITWORD_SIZE] & (1L << (Idx % BITWORD_SIZE));
118
37.6M
  }
119
120
60.7k
  size_type count() const {
121
60.7k
    unsigned NumBits = 0;
122
182k
    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; 
++i121k
)
123
121k
      NumBits += countPopulation(Bits[i]);
124
60.7k
    return NumBits;
125
60.7k
  }
126
127
  /// find_first - Returns the index of the first set bit.
128
320k
  int find_first() const {
129
394k
    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; 
++i74.7k
)
130
394k
      if (Bits[i] != 0)
131
320k
        return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
132
320k
    
llvm_unreachable0
("Illegal empty element");
133
320k
  }
134
135
  /// find_last - Returns the index of the last set bit.
136
231
  int find_last() const {
137
462
    for (unsigned I = 0; I < BITWORDS_PER_ELEMENT; 
++I231
) {
138
462
      unsigned Idx = BITWORDS_PER_ELEMENT - I - 1;
139
462
      if (Bits[Idx] != 0)
140
231
        return Idx * BITWORD_SIZE + BITWORD_SIZE -
141
231
               countLeadingZeros(Bits[Idx]) - 1;
142
462
    }
143
231
    
llvm_unreachable0
("Illegal empty element");
144
231
  }
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
337k
  int find_next(unsigned Curr) const {
149
337k
    if (Curr >= BITS_PER_ELEMENT)
150
0
      return -1;
151
337k
152
337k
    unsigned WordPos = Curr / BITWORD_SIZE;
153
337k
    unsigned BitPos = Curr % BITWORD_SIZE;
154
337k
    BitWord Copy = Bits[WordPos];
155
337k
    assert(WordPos <= BITWORDS_PER_ELEMENT
156
337k
           && "Word Position outside of element");
157
337k
158
337k
    // Mask off previous bits.
159
337k
    Copy &= ~0UL << BitPos;
160
337k
161
337k
    if (Copy != 0)
162
8.96k
      return WordPos * BITWORD_SIZE + countTrailingZeros(Copy);
163
328k
164
328k
    // Check subsequent words.
165
515k
    
for (unsigned i = WordPos+1; 328k
i < BITWORDS_PER_ELEMENT;
++i187k
)
166
225k
      if (Bits[i] != 0)
167
37.5k
        return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
168
328k
    
return -1290k
;
169
328k
  }
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; 
++i704k
) {
175
704k
      BitWord old = changed ? 
046.9k
:
Bits[i]657k
;
176
704k
177
704k
      Bits[i] |= RHS.Bits[i];
178
704k
      if (!changed && 
old != Bits[i]657k
)
179
86.6k
        changed = true;
180
704k
    }
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
0
                     bool &BecameZero) {
197
0
    bool changed = false;
198
0
    bool allzero = true;
199
0
200
0
    BecameZero = false;
201
0
    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
202
0
      BitWord old = changed ? 0 : Bits[i];
203
0
204
0
      Bits[i] &= RHS.Bits[i];
205
0
      if (Bits[i] != 0)
206
0
        allzero = false;
207
0
208
0
      if (!changed && old != Bits[i])
209
0
        changed = true;
210
0
    }
211
0
    BecameZero = allzero;
212
0
    return changed;
213
0
  }
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
0
                               bool &BecameZero) {
220
0
    bool changed = false;
221
0
    bool allzero = true;
222
0
223
0
    BecameZero = false;
224
0
    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
225
0
      BitWord old = changed ? 0 : Bits[i];
226
0
227
0
      Bits[i] &= ~RHS.Bits[i];
228
0
      if (Bits[i] != 0)
229
0
        allzero = false;
230
0
231
0
      if (!changed && old != Bits[i])
232
0
        changed = true;
233
0
    }
234
0
    BecameZero = allzero;
235
0
    return changed;
236
0
  }
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
  // Pointer to our current Element.
265
  ElementListIter CurrElementIter;
266
  ElementList Elements;
267
268
  // This is like std::lower_bound, except we do linear searching from the
269
  // current position.
270
62.2M
  ElementListIter FindLowerBound(unsigned ElementIndex) {
271
62.2M
272
62.2M
    if (Elements.empty()) {
273
0
      CurrElementIter = Elements.begin();
274
0
      return Elements.begin();
275
0
    }
276
62.2M
277
62.2M
    // Make sure our current iterator is valid.
278
62.2M
    if (CurrElementIter == Elements.end())
279
1.18M
      --CurrElementIter;
280
62.2M
281
62.2M
    // Search from our current iterator, either backwards or forwards,
282
62.2M
    // depending on what element we are looking for.
283
62.2M
    ElementListIter ElementIter = CurrElementIter;
284
62.2M
    if (CurrElementIter->index() == ElementIndex) {
285
57.1M
      return ElementIter;
286
57.1M
    } else 
if (5.05M
CurrElementIter->index() > ElementIndex5.05M
) {
287
5.10M
      while (ElementIter != Elements.begin()
288
5.10M
             && 
ElementIter->index() > ElementIndex2.72M
)
289
2.41M
        --ElementIter;
290
2.68M
    } else {
291
6.10M
      while (ElementIter != Elements.end() &&
292
6.10M
             
ElementIter->index() < ElementIndex4.77M
)
293
3.72M
        ++ElementIter;
294
2.37M
    }
295
62.2M
    CurrElementIter = ElementIter;
296
5.05M
    return ElementIter;
297
62.2M
  }
298
299
  // Iterator to walk set bits in the bitmap.  This iterator is a lot uglier
300
  // than it would be, in order to be efficient.
301
  class SparseBitVectorIterator {
302
  private:
303
    bool AtEnd;
304
305
    const SparseBitVector<ElementSize> *BitVector = nullptr;
306
307
    // Current element inside of bitmap.
308
    ElementListConstIter Iter;
309
310
    // Current bit number inside of our bitmap.
311
    unsigned BitNumber;
312
313
    // Current word number inside of our element.
314
    unsigned WordNumber;
315
316
    // Current bits from the element.
317
    typename SparseBitVectorElement<ElementSize>::BitWord Bits;
318
319
    // Move our iterator to the first non-zero bit in the bitmap.
320
42.1M
    void AdvanceToFirstNonZero() {
321
42.1M
      if (AtEnd)
322
21.0M
        return;
323
21.0M
      if (BitVector->Elements.empty()) {
324
20.8M
        AtEnd = true;
325
20.8M
        return;
326
20.8M
      }
327
258k
      Iter = BitVector->Elements.begin();
328
258k
      BitNumber = Iter->index() * ElementSize;
329
258k
      unsigned BitPos = Iter->find_first();
330
258k
      BitNumber += BitPos;
331
258k
      WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
332
258k
      Bits = Iter->word(WordNumber);
333
258k
      Bits >>= BitPos % BITWORD_SIZE;
334
258k
    }
335
336
    // Move our iterator to the next non-zero bit.
337
994k
    void AdvanceToNextNonZero() {
338
994k
      if (AtEnd)
339
0
        return;
340
994k
341
3.14M
      
while (994k
Bits &&
!(Bits & 1)2.81M
) {
342
2.15M
        Bits >>= 1;
343
2.15M
        BitNumber += 1;
344
2.15M
      }
345
994k
346
994k
      // See if we ran out of Bits in this word.
347
994k
      if (!Bits) {
348
337k
        int NextSetBitNumber = Iter->find_next(BitNumber % ElementSize) ;
349
337k
        // If we ran out of set bits in this element, move to next element.
350
337k
        if (NextSetBitNumber == -1 || 
(BitNumber % ElementSize == 0)46.4k
) {
351
295k
          ++Iter;
352
295k
          WordNumber = 0;
353
295k
354
295k
          // We may run out of elements in the bitmap.
355
295k
          if (Iter == BitVector->Elements.end()) {
356
233k
            AtEnd = true;
357
233k
            return;
358
233k
          }
359
61.5k
          // Set up for next non-zero word in bitmap.
360
61.5k
          BitNumber = Iter->index() * ElementSize;
361
61.5k
          NextSetBitNumber = Iter->find_first();
362
61.5k
          BitNumber += NextSetBitNumber;
363
61.5k
          WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
364
61.5k
          Bits = Iter->word(WordNumber);
365
61.5k
          Bits >>= NextSetBitNumber % BITWORD_SIZE;
366
61.5k
        } else {
367
41.6k
          WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE;
368
41.6k
          Bits = Iter->word(WordNumber);
369
41.6k
          Bits >>= NextSetBitNumber % BITWORD_SIZE;
370
41.6k
          BitNumber = Iter->index() * ElementSize;
371
41.6k
          BitNumber += NextSetBitNumber;
372
41.6k
        }
373
337k
      }
374
994k
    }
375
376
  public:
377
    SparseBitVectorIterator() = default;
378
379
    SparseBitVectorIterator(const SparseBitVector<ElementSize> *RHS,
380
42.1M
                            bool end = false):BitVector(RHS) {
381
42.1M
      Iter = BitVector->Elements.begin();
382
42.1M
      BitNumber = 0;
383
42.1M
      Bits = 0;
384
42.1M
      WordNumber = ~0;
385
42.1M
      AtEnd = end;
386
42.1M
      AdvanceToFirstNonZero();
387
42.1M
    }
388
389
    // Preincrement.
390
994k
    inline SparseBitVectorIterator& operator++() {
391
994k
      ++BitNumber;
392
994k
      Bits >>= 1;
393
994k
      AdvanceToNextNonZero();
394
994k
      return *this;
395
994k
    }
396
397
    // Postincrement.
398
    inline SparseBitVectorIterator operator++(int) {
399
      SparseBitVectorIterator tmp = *this;
400
      ++*this;
401
      return tmp;
402
    }
403
404
    // Return the current set bit number.
405
1.15M
    unsigned operator*() const {
406
1.15M
      return BitNumber;
407
1.15M
    }
408
409
22.1M
    bool operator==(const SparseBitVectorIterator &RHS) const {
410
22.1M
      // If they are both at the end, ignore the rest of the fields.
411
22.1M
      if (AtEnd && 
RHS.AtEnd21.0M
)
412
21.0M
        return true;
413
1.12M
      // Otherwise they are the same if they have the same bit number and
414
1.12M
      // bitmap.
415
1.12M
      return AtEnd == RHS.AtEnd && 
RHS.BitNumber == BitNumber0
;
416
1.12M
    }
417
418
21.9M
    bool operator!=(const SparseBitVectorIterator &RHS) const {
419
21.9M
      return !(*this == RHS);
420
21.9M
    }
421
  };
422
423
public:
424
  using iterator = SparseBitVectorIterator;
425
426
6.40M
  SparseBitVector() {
427
6.40M
    CurrElementIter = Elements.begin();
428
6.40M
  }
429
430
  // SparseBitVector copy ctor.
431
21.2M
  SparseBitVector(const SparseBitVector &RHS) {
432
21.2M
    ElementListConstIter ElementIter = RHS.Elements.begin();
433
21.5M
    while (ElementIter != RHS.Elements.end()) {
434
272k
      Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter));
435
272k
      ++ElementIter;
436
272k
    }
437
21.2M
438
21.2M
    CurrElementIter = Elements.begin ();
439
21.2M
  }
440
441
27.6M
  ~SparseBitVector() = default;
442
443
  // Clear.
444
6.47M
  void clear() {
445
6.47M
    Elements.clear();
446
6.47M
  }
447
448
  // Assignment
449
3.00M
  SparseBitVector& operator=(const SparseBitVector& RHS) {
450
3.00M
    if (this == &RHS)
451
0
      return *this;
452
3.00M
453
3.00M
    Elements.clear();
454
3.00M
455
3.00M
    ElementListConstIter ElementIter = RHS.Elements.begin();
456
3.05M
    while (ElementIter != RHS.Elements.end()) {
457
47.0k
      Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter));
458
47.0k
      ++ElementIter;
459
47.0k
    }
460
3.00M
461
3.00M
    CurrElementIter = Elements.begin ();
462
3.00M
463
3.00M
    return *this;
464
3.00M
  }
465
466
  // Test, Reset, and Set a bit in the bitmap.
467
107M
  bool test(unsigned Idx) {
468
107M
    if (Elements.empty())
469
66.5M
      return false;
470
40.7M
471
40.7M
    unsigned ElementIndex = Idx / ElementSize;
472
40.7M
    ElementListIter ElementIter = FindLowerBound(ElementIndex);
473
40.7M
474
40.7M
    // If we can't find an element that is supposed to contain this bit, there
475
40.7M
    // is nothing more to do.
476
40.7M
    if (ElementIter == Elements.end() ||
477
40.7M
        
ElementIter->index() != ElementIndex39.5M
)
478
3.11M
      return false;
479
37.6M
    return ElementIter->test(Idx % ElementSize);
480
37.6M
  }
481
482
1.31M
  void reset(unsigned Idx) {
483
1.31M
    if (Elements.empty())
484
931k
      return;
485
385k
486
385k
    unsigned ElementIndex = Idx / ElementSize;
487
385k
    ElementListIter ElementIter = FindLowerBound(ElementIndex);
488
385k
489
385k
    // If we can't find an element that is supposed to contain this bit, there
490
385k
    // is nothing more to do.
491
385k
    if (ElementIter == Elements.end() ||
492
385k
        ElementIter->index() != ElementIndex)
493
0
      return;
494
385k
    ElementIter->reset(Idx % ElementSize);
495
385k
496
385k
    // When the element is zeroed out, delete it.
497
385k
    if (ElementIter->empty()) {
498
141k
      ++CurrElementIter;
499
141k
      Elements.erase(ElementIter);
500
141k
    }
501
385k
  }
502
503
22.8M
  void set(unsigned Idx) {
504
22.8M
    unsigned ElementIndex = Idx / ElementSize;
505
22.8M
    ElementListIter ElementIter;
506
22.8M
    if (Elements.empty()) {
507
1.73M
      ElementIter = Elements.emplace(Elements.end(), ElementIndex);
508
21.0M
    } else {
509
21.0M
      ElementIter = FindLowerBound(ElementIndex);
510
21.0M
511
21.0M
      if (ElementIter == Elements.end() ||
512
21.0M
          
ElementIter->index() != ElementIndex20.9M
) {
513
172k
        // We may have hit the beginning of our SparseBitVector, in which case,
514
172k
        // we may need to insert right after this element, which requires moving
515
172k
        // the current iterator forward one, because insert does insert before.
516
172k
        if (ElementIter != Elements.end() &&
517
172k
            
ElementIter->index() < ElementIndex53.0k
)
518
3.37k
          ++ElementIter;
519
172k
        ElementIter = Elements.emplace(ElementIter, ElementIndex);
520
172k
      }
521
21.0M
    }
522
22.8M
    CurrElementIter = ElementIter;
523
22.8M
524
22.8M
    ElementIter->set(Idx % ElementSize);
525
22.8M
  }
526
527
  bool test_and_set(unsigned Idx) {
528
    bool old = test(Idx);
529
    if (!old) {
530
      set(Idx);
531
      return true;
532
    }
533
    return false;
534
  }
535
536
  bool operator!=(const SparseBitVector &RHS) const {
537
    return !(*this == RHS);
538
  }
539
540
  bool operator==(const SparseBitVector &RHS) const {
541
    ElementListConstIter Iter1 = Elements.begin();
542
    ElementListConstIter Iter2 = RHS.Elements.begin();
543
544
    for (; Iter1 != Elements.end() && Iter2 != RHS.Elements.end();
545
         ++Iter1, ++Iter2) {
546
      if (*Iter1 != *Iter2)
547
        return false;
548
    }
549
    return Iter1 == Elements.end() && Iter2 == RHS.Elements.end();
550
  }
551
552
  // Union our bitmap with the RHS and return true if we changed.
553
385k
  bool operator|=(const SparseBitVector &RHS) {
554
385k
    if (this == &RHS)
555
0
      return false;
556
385k
557
385k
    bool changed = false;
558
385k
    ElementListIter Iter1 = Elements.begin();
559
385k
    ElementListConstIter Iter2 = RHS.Elements.begin();
560
385k
561
385k
    // If RHS is empty, we are done
562
385k
    if (RHS.Elements.empty())
563
0
      return false;
564
385k
565
788k
    
while (385k
Iter2 != RHS.Elements.end()) {
566
403k
      if (Iter1 == Elements.end() || 
Iter1->index() > Iter2->index()368k
) {
567
35.5k
        Elements.insert(Iter1, *Iter2);
568
35.5k
        ++Iter2;
569
35.5k
        changed = true;
570
367k
      } else if (Iter1->index() == Iter2->index()) {
571
352k
        changed |= Iter1->unionWith(*Iter2);
572
352k
        ++Iter1;
573
352k
        ++Iter2;
574
352k
      } else {
575
15.7k
        ++Iter1;
576
15.7k
      }
577
403k
    }
578
385k
    CurrElementIter = Elements.begin();
579
385k
    return changed;
580
385k
  }
581
582
  // Intersect our bitmap with the RHS and return true if ours changed.
583
0
  bool operator&=(const SparseBitVector &RHS) {
584
0
    if (this == &RHS)
585
0
      return false;
586
0
587
0
    bool changed = false;
588
0
    ElementListIter Iter1 = Elements.begin();
589
0
    ElementListConstIter Iter2 = RHS.Elements.begin();
590
0
591
0
    // Check if both bitmaps are empty.
592
0
    if (Elements.empty() && RHS.Elements.empty())
593
0
      return false;
594
0
595
0
    // Loop through, intersecting as we go, erasing elements when necessary.
596
0
    while (Iter2 != RHS.Elements.end()) {
597
0
      if (Iter1 == Elements.end()) {
598
0
        CurrElementIter = Elements.begin();
599
0
        return changed;
600
0
      }
601
0
602
0
      if (Iter1->index() > Iter2->index()) {
603
0
        ++Iter2;
604
0
      } else if (Iter1->index() == Iter2->index()) {
605
0
        bool BecameZero;
606
0
        changed |= Iter1->intersectWith(*Iter2, BecameZero);
607
0
        if (BecameZero) {
608
0
          ElementListIter IterTmp = Iter1;
609
0
          ++Iter1;
610
0
          Elements.erase(IterTmp);
611
0
        } else {
612
0
          ++Iter1;
613
0
        }
614
0
        ++Iter2;
615
0
      } else {
616
0
        ElementListIter IterTmp = Iter1;
617
0
        ++Iter1;
618
0
        Elements.erase(IterTmp);
619
0
        changed = true;
620
0
      }
621
0
    }
622
0
    if (Iter1 != Elements.end()) {
623
0
      Elements.erase(Iter1, Elements.end());
624
0
      changed = true;
625
0
    }
626
0
    CurrElementIter = Elements.begin();
627
0
    return changed;
628
0
  }
629
630
  // Intersect our bitmap with the complement of the RHS and return true
631
  // if ours changed.
632
2.87M
  bool intersectWithComplement(const SparseBitVector &RHS) {
633
2.87M
    if (this == &RHS) {
634
0
      if (!empty()) {
635
0
        clear();
636
0
        return true;
637
0
      }
638
0
      return false;
639
0
    }
640
2.87M
641
2.87M
    bool changed = false;
642
2.87M
    ElementListIter Iter1 = Elements.begin();
643
2.87M
    ElementListConstIter Iter2 = RHS.Elements.begin();
644
2.87M
645
2.87M
    // If either our bitmap or RHS is empty, we are done
646
2.87M
    if (Elements.empty() || 
RHS.Elements.empty()0
)
647
2.87M
      return false;
648
0
649
0
    // Loop through, intersecting as we go, erasing elements when necessary.
650
0
    while (Iter2 != RHS.Elements.end()) {
651
0
      if (Iter1 == Elements.end()) {
652
0
        CurrElementIter = Elements.begin();
653
0
        return changed;
654
0
      }
655
0
656
0
      if (Iter1->index() > Iter2->index()) {
657
0
        ++Iter2;
658
0
      } else if (Iter1->index() == Iter2->index()) {
659
0
        bool BecameZero;
660
0
        changed |= Iter1->intersectWithComplement(*Iter2, BecameZero);
661
0
        if (BecameZero) {
662
0
          ElementListIter IterTmp = Iter1;
663
0
          ++Iter1;
664
0
          Elements.erase(IterTmp);
665
0
        } else {
666
0
          ++Iter1;
667
0
        }
668
0
        ++Iter2;
669
0
      } else {
670
0
        ++Iter1;
671
0
      }
672
0
    }
673
0
    CurrElementIter = Elements.begin();
674
0
    return changed;
675
0
  }
676
677
  bool intersectWithComplement(const SparseBitVector<ElementSize> *RHS) const {
678
    return intersectWithComplement(*RHS);
679
  }
680
681
  //  Three argument version of intersectWithComplement.
682
  //  Result of RHS1 & ~RHS2 is stored into this bitmap.
683
  void intersectWithComplement(const SparseBitVector<ElementSize> &RHS1,
684
                               const SparseBitVector<ElementSize> &RHS2)
685
  {
686
    if (this == &RHS1) {
687
      intersectWithComplement(RHS2);
688
      return;
689
    } else if (this == &RHS2) {
690
      SparseBitVector RHS2Copy(RHS2);
691
      intersectWithComplement(RHS1, RHS2Copy);
692
      return;
693
    }
694
695
    Elements.clear();
696
    CurrElementIter = Elements.begin();
697
    ElementListConstIter Iter1 = RHS1.Elements.begin();
698
    ElementListConstIter Iter2 = RHS2.Elements.begin();
699
700
    // If RHS1 is empty, we are done
701
    // If RHS2 is empty, we still have to copy RHS1
702
    if (RHS1.Elements.empty())
703
      return;
704
705
    // Loop through, intersecting as we go, erasing elements when necessary.
706
    while (Iter2 != RHS2.Elements.end()) {
707
      if (Iter1 == RHS1.Elements.end())
708
        return;
709
710
      if (Iter1->index() > Iter2->index()) {
711
        ++Iter2;
712
      } else if (Iter1->index() == Iter2->index()) {
713
        bool BecameZero = false;
714
        Elements.emplace_back(Iter1->index());
715
        Elements.back().intersectWithComplement(*Iter1, *Iter2, BecameZero);
716
        if (BecameZero)
717
          Elements.pop_back();
718
        ++Iter1;
719
        ++Iter2;
720
      } else {
721
        Elements.push_back(*Iter1++);
722
      }
723
    }
724
725
    // copy the remaining elements
726
    std::copy(Iter1, RHS1.Elements.end(), std::back_inserter(Elements));
727
  }
728
729
  void intersectWithComplement(const SparseBitVector<ElementSize> *RHS1,
730
                               const SparseBitVector<ElementSize> *RHS2) {
731
    intersectWithComplement(*RHS1, *RHS2);
732
  }
733
734
  bool intersects(const SparseBitVector<ElementSize> *RHS) const {
735
    return intersects(*RHS);
736
  }
737
738
  // Return true if we share any bits in common with RHS
739
32
  bool intersects(const SparseBitVector<ElementSize> &RHS) const {
740
32
    ElementListConstIter Iter1 = Elements.begin();
741
32
    ElementListConstIter Iter2 = RHS.Elements.begin();
742
32
743
32
    // Check if both bitmaps are empty.
744
32
    if (Elements.empty() && 
RHS.Elements.empty()0
)
745
0
      return false;
746
32
747
32
    // Loop through, intersecting stopping when we hit bits in common.
748
32
    while (Iter2 != RHS.Elements.end()) {
749
0
      if (Iter1 == Elements.end())
750
0
        return false;
751
0
752
0
      if (Iter1->index() > Iter2->index()) {
753
0
        ++Iter2;
754
0
      } else if (Iter1->index() == Iter2->index()) {
755
0
        if (Iter1->intersects(*Iter2))
756
0
          return true;
757
0
        ++Iter1;
758
0
        ++Iter2;
759
0
      } else {
760
0
        ++Iter1;
761
0
      }
762
0
    }
763
32
    return false;
764
32
  }
765
766
  // Return true iff all bits set in this SparseBitVector are
767
  // also set in RHS.
768
  bool contains(const SparseBitVector<ElementSize> &RHS) const {
769
    SparseBitVector<ElementSize> Result(*this);
770
    Result &= RHS;
771
    return (Result == RHS);
772
  }
773
774
  // Return the first set bit in the bitmap.  Return -1 if no bits are set.
775
79
  int find_first() const {
776
79
    if (Elements.empty())
777
2
      return -1;
778
77
    const SparseBitVectorElement<ElementSize> &First = *(Elements.begin());
779
77
    return (First.index() * ElementSize) + First.find_first();
780
77
  }
781
782
  // Return the last set bit in the bitmap.  Return -1 if no bits are set.
783
462
  int find_last() const {
784
462
    if (Elements.empty())
785
231
      return -1;
786
231
    const SparseBitVectorElement<ElementSize> &Last = *(Elements.rbegin());
787
231
    return (Last.index() * ElementSize) + Last.find_last();
788
231
  }
789
790
  // Return true if the SparseBitVector is empty
791
10.3M
  bool empty() const {
792
10.3M
    return Elements.empty();
793
10.3M
  }
794
795
55.8k
  unsigned count() const {
796
55.8k
    unsigned BitCount = 0;
797
55.8k
    for (ElementListConstIter Iter = Elements.begin();
798
116k
         Iter != Elements.end();
799
60.7k
         ++Iter)
800
60.7k
      BitCount += Iter->count();
801
55.8k
802
55.8k
    return BitCount;
803
55.8k
  }
804
805
21.0M
  iterator begin() const {
806
21.0M
    return iterator(this);
807
21.0M
  }
808
809
21.0M
  iterator end() const {
810
21.0M
    return iterator(this, true);
811
21.0M
  }
812
};
813
814
// Convenience functions to allow Or and And without dereferencing in the user
815
// code.
816
817
template <unsigned ElementSize>
818
inline bool operator |=(SparseBitVector<ElementSize> &LHS,
819
                        const SparseBitVector<ElementSize> *RHS) {
820
  return LHS |= *RHS;
821
}
822
823
template <unsigned ElementSize>
824
inline bool operator |=(SparseBitVector<ElementSize> *LHS,
825
                        const SparseBitVector<ElementSize> &RHS) {
826
  return LHS->operator|=(RHS);
827
}
828
829
template <unsigned ElementSize>
830
inline bool operator &=(SparseBitVector<ElementSize> *LHS,
831
                        const SparseBitVector<ElementSize> &RHS) {
832
  return LHS->operator&=(RHS);
833
}
834
835
template <unsigned ElementSize>
836
inline bool operator &=(SparseBitVector<ElementSize> &LHS,
837
                        const SparseBitVector<ElementSize> *RHS) {
838
  return LHS &= *RHS;
839
}
840
841
// Convenience functions for infix union, intersection, difference operators.
842
843
template <unsigned ElementSize>
844
inline SparseBitVector<ElementSize>
845
operator|(const SparseBitVector<ElementSize> &LHS,
846
          const SparseBitVector<ElementSize> &RHS) {
847
  SparseBitVector<ElementSize> Result(LHS);
848
  Result |= RHS;
849
  return Result;
850
}
851
852
template <unsigned ElementSize>
853
inline SparseBitVector<ElementSize>
854
operator&(const SparseBitVector<ElementSize> &LHS,
855
          const SparseBitVector<ElementSize> &RHS) {
856
  SparseBitVector<ElementSize> Result(LHS);
857
  Result &= RHS;
858
  return Result;
859
}
860
861
template <unsigned ElementSize>
862
inline SparseBitVector<ElementSize>
863
operator-(const SparseBitVector<ElementSize> &LHS,
864
          const SparseBitVector<ElementSize> &RHS) {
865
  SparseBitVector<ElementSize> Result;
866
  Result.intersectWithComplement(LHS, RHS);
867
  return Result;
868
}
869
870
// Dump a SparseBitVector to a stream
871
template <unsigned ElementSize>
872
void dump(const SparseBitVector<ElementSize> &LHS, raw_ostream &out) {
873
  out << "[";
874
875
  typename SparseBitVector<ElementSize>::iterator bi = LHS.begin(),
876
    be = LHS.end();
877
  if (bi != be) {
878
    out << *bi;
879
    for (++bi; bi != be; ++bi) {
880
      out << " " << *bi;
881
    }
882
  }
883
  out << "]\n";
884
}
885
886
} // end namespace llvm
887
888
#endif // LLVM_ADT_SPARSEBITVECTOR_H