Coverage Report

Created: 2019-07-24 05:18

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