Coverage Report

Created: 2019-02-15 18:59

/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.10M
  explicit SparseBitVectorElement(unsigned Idx) {
63
2.10M
    ElementIndex = Idx;
64
2.10M
    memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
65
2.10M
  }
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
400k
  BitWord word(unsigned Idx) const {
83
400k
    assert(Idx < BITWORDS_PER_ELEMENT);
84
400k
    return Bits[Idx];
85
400k
  }
86
87
162M
  unsigned index() const {
88
162M
    return ElementIndex;
89
162M
  }
90
91
416k
  bool empty() const {
92
747k
    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; 
++i330k
)
93
590k
      if (Bits[i])
94
259k
        return false;
95
416k
    
return true157k
;
96
416k
  }
97
98
26.5M
  void set(unsigned Idx) {
99
26.5M
    Bits[Idx / BITWORD_SIZE] |= 1L << (Idx % BITWORD_SIZE);
100
26.5M
  }
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
416k
  void reset(unsigned Idx) {
112
416k
    Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE));
113
416k
  }
114
115
44.0M
  bool test(unsigned Idx) const {
116
44.0M
    return Bits[Idx / BITWORD_SIZE] & (1L << (Idx % BITWORD_SIZE));
117
44.0M
  }
118
119
136k
  size_type count() const {
120
136k
    unsigned NumBits = 0;
121
410k
    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; 
++i273k
)
122
273k
      NumBits += countPopulation(Bits[i]);
123
136k
    return NumBits;
124
136k
  }
125
126
  /// find_first - Returns the index of the first set bit.
127
353k
  int find_first() const {
128
427k
    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; 
++i73.5k
)
129
427k
      if (Bits[i] != 0)
130
353k
        return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
131
353k
    
llvm_unreachable0
("Illegal empty element");
132
353k
  }
133
134
  /// find_last - Returns the index of the last set bit.
135
370
  int find_last() const {
136
739
    for (unsigned I = 0; I < BITWORDS_PER_ELEMENT; 
++I369
) {
137
739
      unsigned Idx = BITWORDS_PER_ELEMENT - I - 1;
138
739
      if (Bits[Idx] != 0)
139
370
        return Idx * BITWORD_SIZE + BITWORD_SIZE -
140
370
               countLeadingZeros(Bits[Idx]) - 1;
141
739
    }
142
370
    
llvm_unreachable0
("Illegal empty element");
143
370
  }
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
375k
  int find_next(unsigned Curr) const {
148
375k
    if (Curr >= BITS_PER_ELEMENT)
149
0
      return -1;
150
375k
151
375k
    unsigned WordPos = Curr / BITWORD_SIZE;
152
375k
    unsigned BitPos = Curr % BITWORD_SIZE;
153
375k
    BitWord Copy = Bits[WordPos];
154
375k
    assert(WordPos <= BITWORDS_PER_ELEMENT
155
375k
           && "Word Position outside of element");
156
375k
157
375k
    // Mask off previous bits.
158
375k
    Copy &= ~0UL << BitPos;
159
375k
160
375k
    if (Copy != 0)
161
8.54k
      return WordPos * BITWORD_SIZE + countTrailingZeros(Copy);
162
366k
163
366k
    // Check subsequent words.
164
584k
    
for (unsigned i = WordPos+1; 366k
i < BITWORDS_PER_ELEMENT;
++i217k
)
165
260k
      if (Bits[i] != 0)
166
42.7k
        return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
167
366k
    
return -1324k
;
168
366k
  }
169
170
  // Union this element with RHS and return true if this one changed.
171
352k
  bool unionWith(const SparseBitVectorElement &RHS) {
172
352k
    bool changed = false;
173
1.05M
    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; 
++i705k
) {
174
705k
      BitWord old = changed ? 
047.0k
:
Bits[i]658k
;
175
705k
176
705k
      Bits[i] |= RHS.Bits[i];
177
705k
      if (!changed && 
old != Bits[i]658k
)
178
86.6k
        changed = true;
179
705k
    }
180
352k
    return changed;
181
352k
  }
182
183
  // Return true if we have any bits in common with RHS
184
0
  bool intersects(const SparseBitVectorElement &RHS) const {
185
0
    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
186
0
      if (RHS.Bits[i] & Bits[i])
187
0
        return true;
188
0
    }
189
0
    return false;
190
0
  }
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
227
                     bool &BecameZero) {
196
227
    bool changed = false;
197
227
    bool allzero = true;
198
227
199
227
    BecameZero = false;
200
681
    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; 
++i454
) {
201
454
      BitWord old = changed ? 
048
:
Bits[i]406
;
202
454
203
454
      Bits[i] &= RHS.Bits[i];
204
454
      if (Bits[i] != 0)
205
219
        allzero = false;
206
454
207
454
      if (!changed && 
old != Bits[i]406
)
208
48
        changed = true;
209
454
    }
210
227
    BecameZero = allzero;
211
227
    return changed;
212
227
  }
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
623
                               bool &BecameZero) {
219
623
    bool changed = false;
220
623
    bool allzero = true;
221
623
222
623
    BecameZero = false;
223
1.86k
    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; 
++i1.24k
) {
224
1.24k
      BitWord old = changed ? 
0622
:
Bits[i]624
;
225
1.24k
226
1.24k
      Bits[i] &= ~RHS.Bits[i];
227
1.24k
      if (Bits[i] != 0)
228
202
        allzero = false;
229
1.24k
230
1.24k
      if (!changed && 
old != Bits[i]624
)
231
622
        changed = true;
232
1.24k
    }
233
623
    BecameZero = allzero;
234
623
    return changed;
235
623
  }
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
72.7M
  ElementListIter FindLowerBoundImpl(unsigned ElementIndex) const {
272
72.7M
273
72.7M
    // We cache a non-const iterator so we're forced to resort to const_cast to
274
72.7M
    // get the begin/end in the case where 'this' is const. To avoid duplication
275
72.7M
    // of code with the only difference being whether the const cast is present
276
72.7M
    // 'this' is always const in this particular function and we sort out the
277
72.7M
    // difference in FindLowerBound and FindLowerBoundConst.
278
72.7M
    ElementListIter Begin =
279
72.7M
        const_cast<SparseBitVector<ElementSize> *>(this)->Elements.begin();
280
72.7M
    ElementListIter End =
281
72.7M
        const_cast<SparseBitVector<ElementSize> *>(this)->Elements.end();
282
72.7M
283
72.7M
    if (Elements.empty()) {
284
0
      CurrElementIter = Begin;
285
0
      return CurrElementIter;
286
0
    }
287
72.7M
288
72.7M
    // Make sure our current iterator is valid.
289
72.7M
    if (CurrElementIter == End)
290
1.41M
      --CurrElementIter;
291
72.7M
292
72.7M
    // Search from our current iterator, either backwards or forwards,
293
72.7M
    // depending on what element we are looking for.
294
72.7M
    ElementListIter ElementIter = CurrElementIter;
295
72.7M
    if (CurrElementIter->index() == ElementIndex) {
296
66.3M
      return ElementIter;
297
66.3M
    } else 
if (6.39M
CurrElementIter->index() > ElementIndex6.39M
) {
298
6.71M
      while (ElementIter != Begin
299
6.71M
             && 
ElementIter->index() > ElementIndex3.97M
)
300
3.39M
        --ElementIter;
301
3.32M
    } else {
302
8.01M
      while (ElementIter != End &&
303
8.01M
             
ElementIter->index() < ElementIndex6.44M
)
304
4.94M
        ++ElementIter;
305
3.07M
    }
306
72.7M
    CurrElementIter = ElementIter;
307
6.39M
    return ElementIter;
308
72.7M
  }
309
47.7M
  ElementListConstIter FindLowerBoundConst(unsigned ElementIndex) const {
310
47.7M
    return FindLowerBoundImpl(ElementIndex);
311
47.7M
  }
312
25.0M
  ElementListIter FindLowerBound(unsigned ElementIndex) {
313
25.0M
    return FindLowerBoundImpl(ElementIndex);
314
25.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
38.8M
    void AdvanceToFirstNonZero() {
338
38.8M
      if (AtEnd)
339
19.4M
        return;
340
19.4M
      if (BitVector->Elements.empty()) {
341
19.1M
        AtEnd = true;
342
19.1M
        return;
343
19.1M
      }
344
297k
      Iter = BitVector->Elements.begin();
345
297k
      BitNumber = Iter->index() * ElementSize;
346
297k
      unsigned BitPos = Iter->find_first();
347
297k
      BitNumber += BitPos;
348
297k
      WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
349
297k
      Bits = Iter->word(WordNumber);
350
297k
      Bits >>= BitPos % BITWORD_SIZE;
351
297k
    }
352
353
    // Move our iterator to the next non-zero bit.
354
1.09M
    void AdvanceToNextNonZero() {
355
1.09M
      if (AtEnd)
356
0
        return;
357
1.09M
358
3.28M
      
while (1.09M
Bits &&
!(Bits & 1)2.91M
) {
359
2.19M
        Bits >>= 1;
360
2.19M
        BitNumber += 1;
361
2.19M
      }
362
1.09M
363
1.09M
      // See if we ran out of Bits in this word.
364
1.09M
      if (!Bits) {
365
375k
        int NextSetBitNumber = Iter->find_next(BitNumber % ElementSize) ;
366
375k
        // If we ran out of set bits in this element, move to next element.
367
375k
        if (NextSetBitNumber == -1 || 
(BitNumber % ElementSize == 0)51.2k
) {
368
328k
          ++Iter;
369
328k
          WordNumber = 0;
370
328k
371
328k
          // We may run out of elements in the bitmap.
372
328k
          if (Iter == BitVector->Elements.end()) {
373
272k
            AtEnd = true;
374
272k
            return;
375
272k
          }
376
56.4k
          // Set up for next non-zero word in bitmap.
377
56.4k
          BitNumber = Iter->index() * ElementSize;
378
56.4k
          NextSetBitNumber = Iter->find_first();
379
56.4k
          BitNumber += NextSetBitNumber;
380
56.4k
          WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
381
56.4k
          Bits = Iter->word(WordNumber);
382
56.4k
          Bits >>= NextSetBitNumber % BITWORD_SIZE;
383
56.4k
        } else {
384
46.5k
          WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE;
385
46.5k
          Bits = Iter->word(WordNumber);
386
46.5k
          Bits >>= NextSetBitNumber % BITWORD_SIZE;
387
46.5k
          BitNumber = Iter->index() * ElementSize;
388
46.5k
          BitNumber += NextSetBitNumber;
389
46.5k
        }
390
375k
      }
391
1.09M
    }
392
393
  public:
394
    SparseBitVectorIterator() = default;
395
396
    SparseBitVectorIterator(const SparseBitVector<ElementSize> *RHS,
397
38.8M
                            bool end = false):BitVector(RHS) {
398
38.8M
      Iter = BitVector->Elements.begin();
399
38.8M
      BitNumber = 0;
400
38.8M
      Bits = 0;
401
38.8M
      WordNumber = ~0;
402
38.8M
      AtEnd = end;
403
38.8M
      AdvanceToFirstNonZero();
404
38.8M
    }
405
406
    // Preincrement.
407
1.09M
    inline SparseBitVectorIterator& operator++() {
408
1.09M
      ++BitNumber;
409
1.09M
      Bits >>= 1;
410
1.09M
      AdvanceToNextNonZero();
411
1.09M
      return *this;
412
1.09M
    }
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
1.25M
    unsigned operator*() const {
423
1.25M
      return BitNumber;
424
1.25M
    }
425
426
20.6M
    bool operator==(const SparseBitVectorIterator &RHS) const {
427
20.6M
      // If they are both at the end, ignore the rest of the fields.
428
20.6M
      if (AtEnd && 
RHS.AtEnd19.4M
)
429
19.4M
        return true;
430
1.22M
      // Otherwise they are the same if they have the same bit number and
431
1.22M
      // bitmap.
432
1.22M
      return AtEnd == RHS.AtEnd && 
RHS.BitNumber == BitNumber0
;
433
1.22M
    }
434
435
20.4M
    bool operator!=(const SparseBitVectorIterator &RHS) const {
436
20.4M
      return !(*this == RHS);
437
20.4M
    }
438
  };
439
440
public:
441
  using iterator = SparseBitVectorIterator;
442
443
7.61M
  SparseBitVector() : Elements(), CurrElementIter(Elements.begin()) {}
444
445
  SparseBitVector(const SparseBitVector &RHS)
446
16.7M
      : Elements(RHS.Elements), CurrElementIter(Elements.begin()) {}
447
  SparseBitVector(SparseBitVector &&RHS)
448
8.95M
      : Elements(std::move(RHS.Elements)), CurrElementIter(Elements.begin()) {}
449
450
  // Clear.
451
9.29M
  void clear() {
452
9.29M
    Elements.clear();
453
9.29M
  }
454
455
  // Assignment
456
43.8k
  SparseBitVector& operator=(const SparseBitVector& RHS) {
457
43.8k
    if (this == &RHS)
458
1
      return *this;
459
43.8k
460
43.8k
    Elements = RHS.Elements;
461
43.8k
    CurrElementIter = Elements.begin();
462
43.8k
    return *this;
463
43.8k
  }
464
4.23M
  SparseBitVector &operator=(SparseBitVector &&RHS) {
465
4.23M
    Elements = std::move(RHS.Elements);
466
4.23M
    CurrElementIter = Elements.begin();
467
4.23M
    return *this;
468
4.23M
  }
469
470
  // Test, Reset, and Set a bit in the bitmap.
471
128M
  bool test(unsigned Idx) const {
472
128M
    if (Elements.empty())
473
80.7M
      return false;
474
47.7M
475
47.7M
    unsigned ElementIndex = Idx / ElementSize;
476
47.7M
    ElementListConstIter ElementIter = FindLowerBoundConst(ElementIndex);
477
47.7M
478
47.7M
    // If we can't find an element that is supposed to contain this bit, there
479
47.7M
    // is nothing more to do.
480
47.7M
    if (ElementIter == Elements.end() ||
481
47.7M
        
ElementIter->index() != ElementIndex46.2M
)
482
3.66M
      return false;
483
44.0M
    return ElementIter->test(Idx % ElementSize);
484
44.0M
  }
485
486
1.37M
  void reset(unsigned Idx) {
487
1.37M
    if (Elements.empty())
488
954k
      return;
489
416k
490
416k
    unsigned ElementIndex = Idx / ElementSize;
491
416k
    ElementListIter ElementIter = FindLowerBound(ElementIndex);
492
416k
493
416k
    // If we can't find an element that is supposed to contain this bit, there
494
416k
    // is nothing more to do.
495
416k
    if (ElementIter == Elements.end() ||
496
416k
        ElementIter->index() != ElementIndex)
497
0
      return;
498
416k
    ElementIter->reset(Idx % ElementSize);
499
416k
500
416k
    // When the element is zeroed out, delete it.
501
416k
    if (ElementIter->empty()) {
502
157k
      ++CurrElementIter;
503
157k
      Elements.erase(ElementIter);
504
157k
    }
505
416k
  }
506
507
26.5M
  void set(unsigned Idx) {
508
26.5M
    unsigned ElementIndex = Idx / ElementSize;
509
26.5M
    ElementListIter ElementIter;
510
26.5M
    if (Elements.empty()) {
511
1.92M
      ElementIter = Elements.emplace(Elements.end(), ElementIndex);
512
24.6M
    } else {
513
24.6M
      ElementIter = FindLowerBound(ElementIndex);
514
24.6M
515
24.6M
      if (ElementIter == Elements.end() ||
516
24.6M
          
ElementIter->index() != ElementIndex24.5M
) {
517
184k
        // We may have hit the beginning of our SparseBitVector, in which case,
518
184k
        // we may need to insert right after this element, which requires moving
519
184k
        // the current iterator forward one, because insert does insert before.
520
184k
        if (ElementIter != Elements.end() &&
521
184k
            
ElementIter->index() < ElementIndex58.5k
)
522
6.36k
          ++ElementIter;
523
184k
        ElementIter = Elements.emplace(ElementIter, ElementIndex);
524
184k
      }
525
24.6M
    }
526
26.5M
    CurrElementIter = ElementIter;
527
26.5M
528
26.5M
    ElementIter->set(Idx % ElementSize);
529
26.5M
  }
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
385k
  bool operator|=(const SparseBitVector &RHS) {
558
385k
    if (this == &RHS)
559
1
      return false;
560
385k
561
385k
    bool changed = false;
562
385k
    ElementListIter Iter1 = Elements.begin();
563
385k
    ElementListConstIter Iter2 = RHS.Elements.begin();
564
385k
565
385k
    // If RHS is empty, we are done
566
385k
    if (RHS.Elements.empty())
567
0
      return false;
568
385k
569
789k
    
while (385k
Iter2 != RHS.Elements.end()) {
570
404k
      if (Iter1 == Elements.end() || 
Iter1->index() > Iter2->index()369k
) {
571
35.8k
        Elements.insert(Iter1, *Iter2);
572
35.8k
        ++Iter2;
573
35.8k
        changed = true;
574
368k
      } else if (Iter1->index() == Iter2->index()) {
575
352k
        changed |= Iter1->unionWith(*Iter2);
576
352k
        ++Iter1;
577
352k
        ++Iter2;
578
352k
      } else {
579
15.7k
        ++Iter1;
580
15.7k
      }
581
404k
    }
582
385k
    CurrElementIter = Elements.begin();
583
385k
    return changed;
584
385k
  }
585
586
  // Intersect our bitmap with the RHS and return true if ours changed.
587
234
  bool operator&=(const SparseBitVector &RHS) {
588
234
    if (this == &RHS)
589
1
      return false;
590
233
591
233
    bool changed = false;
592
233
    ElementListIter Iter1 = Elements.begin();
593
233
    ElementListConstIter Iter2 = RHS.Elements.begin();
594
233
595
233
    // Check if both bitmaps are empty.
596
233
    if (Elements.empty() && 
RHS.Elements.empty()4
)
597
0
      return false;
598
233
599
233
    // Loop through, intersecting as we go, erasing elements when necessary.
600
462
    
while (233
Iter2 != RHS.Elements.end()) {
601
234
      if (Iter1 == Elements.end()) {
602
5
        CurrElementIter = Elements.begin();
603
5
        return changed;
604
5
      }
605
229
606
229
      if (Iter1->index() > Iter2->index()) {
607
1
        ++Iter2;
608
228
      } else if (Iter1->index() == Iter2->index()) {
609
227
        bool BecameZero;
610
227
        changed |= Iter1->intersectWith(*Iter2, BecameZero);
611
227
        if (BecameZero) {
612
8
          ElementListIter IterTmp = Iter1;
613
8
          ++Iter1;
614
8
          Elements.erase(IterTmp);
615
219
        } else {
616
219
          ++Iter1;
617
219
        }
618
227
        ++Iter2;
619
227
      } else {
620
1
        ElementListIter IterTmp = Iter1;
621
1
        ++Iter1;
622
1
        Elements.erase(IterTmp);
623
1
        changed = true;
624
1
      }
625
229
    }
626
233
    
if (228
Iter1 != Elements.end()228
) {
627
1
      Elements.erase(Iter1, Elements.end());
628
1
      changed = true;
629
1
    }
630
228
    CurrElementIter = Elements.begin();
631
228
    return changed;
632
233
  }
633
634
  // Intersect our bitmap with the complement of the RHS and return true
635
  // if ours changed.
636
2.78M
  bool intersectWithComplement(const SparseBitVector &RHS) {
637
2.78M
    if (this == &RHS) {
638
3
      if (!empty()) {
639
2
        clear();
640
2
        return true;
641
2
      }
642
1
      return false;
643
1
    }
644
2.78M
645
2.78M
    bool changed = false;
646
2.78M
    ElementListIter Iter1 = Elements.begin();
647
2.78M
    ElementListConstIter Iter2 = RHS.Elements.begin();
648
2.78M
649
2.78M
    // If either our bitmap or RHS is empty, we are done
650
2.78M
    if (Elements.empty() || 
RHS.Elements.empty()6.70k
)
651
2.78M
      return false;
652
622
653
622
    // Loop through, intersecting as we go, erasing elements when necessary.
654
1.24k
    
while (622
Iter2 != RHS.Elements.end()) {
655
623
      if (Iter1 == Elements.end()) {
656
0
        CurrElementIter = Elements.begin();
657
0
        return changed;
658
0
      }
659
623
660
623
      if (Iter1->index() > Iter2->index()) {
661
0
        ++Iter2;
662
623
      } else if (Iter1->index() == Iter2->index()) {
663
623
        bool BecameZero;
664
623
        changed |= Iter1->intersectWithComplement(*Iter2, BecameZero);
665
623
        if (BecameZero) {
666
421
          ElementListIter IterTmp = Iter1;
667
421
          ++Iter1;
668
421
          Elements.erase(IterTmp);
669
421
        } else {
670
202
          ++Iter1;
671
202
        }
672
623
        ++Iter2;
673
623
      } else {
674
0
        ++Iter1;
675
0
      }
676
623
    }
677
622
    CurrElementIter = Elements.begin();
678
622
    return changed;
679
622
  }
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
93
  bool intersects(const SparseBitVector<ElementSize> &RHS) const {
744
93
    ElementListConstIter Iter1 = Elements.begin();
745
93
    ElementListConstIter Iter2 = RHS.Elements.begin();
746
93
747
93
    // Check if both bitmaps are empty.
748
93
    if (Elements.empty() && 
RHS.Elements.empty()0
)
749
0
      return false;
750
93
751
93
    // Loop through, intersecting stopping when we hit bits in common.
752
93
    while (Iter2 != RHS.Elements.end()) {
753
0
      if (Iter1 == Elements.end())
754
0
        return false;
755
0
756
0
      if (Iter1->index() > Iter2->index()) {
757
0
        ++Iter2;
758
0
      } else if (Iter1->index() == Iter2->index()) {
759
0
        if (Iter1->intersects(*Iter2))
760
0
          return true;
761
0
        ++Iter1;
762
0
        ++Iter2;
763
0
      } else {
764
0
        ++Iter1;
765
0
      }
766
0
    }
767
93
    return false;
768
93
  }
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
146
  int find_first() const {
780
146
    if (Elements.empty())
781
7
      return -1;
782
139
    const SparseBitVectorElement<ElementSize> &First = *(Elements.begin());
783
139
    return (First.index() * ElementSize) + First.find_first();
784
139
  }
785
786
  // Return the last set bit in the bitmap.  Return -1 if no bits are set.
787
734
  int find_last() const {
788
734
    if (Elements.empty())
789
364
      return -1;
790
370
    const SparseBitVectorElement<ElementSize> &Last = *(Elements.rbegin());
791
370
    return (Last.index() * ElementSize) + Last.find_last();
792
370
  }
793
794
  // Return true if the SparseBitVector is empty
795
11.9M
  bool empty() const {
796
11.9M
    return Elements.empty();
797
11.9M
  }
798
799
131k
  unsigned count() const {
800
131k
    unsigned BitCount = 0;
801
131k
    for (ElementListConstIter Iter = Elements.begin();
802
268k
         Iter != Elements.end();
803
136k
         ++Iter)
804
136k
      BitCount += Iter->count();
805
131k
806
131k
    return BitCount;
807
131k
  }
808
809
19.4M
  iterator begin() const {
810
19.4M
    return iterator(this);
811
19.4M
  }
812
813
19.4M
  iterator end() const {
814
19.4M
    return iterator(this, true);
815
19.4M
  }
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