Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/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
2.71M
  explicit SparseBitVectorElement(unsigned Idx) {
64
2.71M
    ElementIndex = Idx;
65
2.71M
    memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
66
2.71M
  }
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
508k
  BitWord word(unsigned Idx) const {
84
508k
    assert(Idx < BITWORDS_PER_ELEMENT);
85
508k
    return Bits[Idx];
86
508k
  }
87
88
199M
  unsigned index() const {
89
199M
    return ElementIndex;
90
199M
  }
91
92
490k
  bool empty() const {
93
896k
    for (unsigned i = 0; 
i < BITWORDS_PER_ELEMENT896k
;
++i405k
)
94
705k
      
if (705k
Bits[i]705k
)
95
299k
        return false;
96
191k
    return true;
97
490k
  }
98
99
33.3M
  void set(unsigned Idx) {
100
33.3M
    Bits[Idx / BITWORD_SIZE] |= 1L << (Idx % BITWORD_SIZE);
101
33.3M
  }
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
490k
  void reset(unsigned Idx) {
113
490k
    Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE));
114
490k
  }
115
116
54.0M
  bool test(unsigned Idx) const {
117
54.0M
    return Bits[Idx / BITWORD_SIZE] & (1L << (Idx % BITWORD_SIZE));
118
54.0M
  }
119
120
64.6k
  size_type count() const {
121
64.6k
    unsigned NumBits = 0;
122
194k
    for (unsigned i = 0; 
i < BITWORDS_PER_ELEMENT194k
;
++i129k
)
123
129k
      NumBits += countPopulation(Bits[i]);
124
64.6k
    return NumBits;
125
64.6k
  }
126
127
  /// find_first - Returns the index of the first set bit.
128
454k
  int find_first() const {
129
534k
    for (unsigned i = 0; 
i < BITWORDS_PER_ELEMENT534k
;
++i79.9k
)
130
534k
      
if (534k
Bits[i] != 0534k
)
131
454k
        return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
132
0
    
llvm_unreachable0
("Illegal empty element");
133
454k
  }
134
135
  /// find_last - Returns the index of the last set bit.
136
128
  int find_last() const {
137
255
    for (unsigned I = 0; 
I < BITWORDS_PER_ELEMENT255
;
++I127
) {
138
255
      unsigned Idx = BITWORDS_PER_ELEMENT - I - 1;
139
255
      if (Bits[Idx] != 0)
140
128
        return Idx * BITWORD_SIZE + BITWORD_SIZE -
141
128
               countLeadingZeros(Bits[Idx]) - 1;
142
255
    }
143
0
    
llvm_unreachable0
("Illegal empty element");
144
128
  }
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
485k
  int find_next(unsigned Curr) const {
149
485k
    if (Curr >= BITS_PER_ELEMENT)
150
0
      return -1;
151
485k
152
485k
    unsigned WordPos = Curr / BITWORD_SIZE;
153
485k
    unsigned BitPos = Curr % BITWORD_SIZE;
154
485k
    BitWord Copy = Bits[WordPos];
155
485k
    assert(WordPos <= BITWORDS_PER_ELEMENT
156
485k
           && "Word Position outside of element");
157
485k
158
485k
    // Mask off previous bits.
159
485k
    Copy &= ~0UL << BitPos;
160
485k
161
485k
    if (Copy != 0)
162
10.5k
      return WordPos * BITWORD_SIZE + countTrailingZeros(Copy);
163
485k
164
485k
    // Check subsequent words.
165
778k
    
for (unsigned i = WordPos+1; 474k
i < BITWORDS_PER_ELEMENT778k
;
++i304k
)
166
352k
      
if (352k
Bits[i] != 0352k
)
167
47.9k
        return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
168
426k
    return -1;
169
485k
  }
170
171
  // Union this element with RHS and return true if this one changed.
172
311k
  bool unionWith(const SparseBitVectorElement &RHS) {
173
311k
    bool changed = false;
174
935k
    for (unsigned i = 0; 
i < BITWORDS_PER_ELEMENT935k
;
++i623k
) {
175
623k
      BitWord old = changed ? 
039.7k
:
Bits[i]583k
;
176
623k
177
623k
      Bits[i] |= RHS.Bits[i];
178
623k
      if (
!changed && 623k
old != Bits[i]583k
)
179
67.4k
        changed = true;
180
623k
    }
181
311k
    return changed;
182
311k
  }
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_ELEMENT0
;
++i0
) {
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
244
                     bool &BecameZero) {
197
244
    bool changed = false;
198
244
    bool allzero = true;
199
244
200
244
    BecameZero = false;
201
732
    for (unsigned i = 0; 
i < BITWORDS_PER_ELEMENT732
;
++i488
) {
202
488
      BitWord old = changed ? 
056
:
Bits[i]432
;
203
488
204
488
      Bits[i] &= RHS.Bits[i];
205
488
      if (Bits[i] != 0)
206
231
        allzero = false;
207
488
208
488
      if (
!changed && 488
old != Bits[i]432
)
209
56
        changed = true;
210
488
    }
211
244
    BecameZero = allzero;
212
244
    return changed;
213
244
  }
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
581
                               bool &BecameZero) {
220
581
    bool changed = false;
221
581
    bool allzero = true;
222
581
223
581
    BecameZero = false;
224
1.74k
    for (unsigned i = 0; 
i < BITWORDS_PER_ELEMENT1.74k
;
++i1.16k
) {
225
1.16k
      BitWord old = changed ? 
0580
:
Bits[i]582
;
226
1.16k
227
1.16k
      Bits[i] &= ~RHS.Bits[i];
228
1.16k
      if (Bits[i] != 0)
229
144
        allzero = false;
230
1.16k
231
1.16k
      if (
!changed && 1.16k
old != Bits[i]582
)
232
580
        changed = true;
233
1.16k
    }
234
581
    BecameZero = allzero;
235
581
    return changed;
236
581
  }
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
90.3M
  ElementListIter FindLowerBound(unsigned ElementIndex) {
271
90.3M
272
90.3M
    if (
Elements.empty()90.3M
) {
273
0
      CurrElementIter = Elements.begin();
274
0
      return Elements.begin();
275
0
    }
276
90.3M
277
90.3M
    // Make sure our current iterator is valid.
278
90.3M
    
if (90.3M
CurrElementIter == Elements.end()90.3M
)
279
1.84M
      --CurrElementIter;
280
90.3M
281
90.3M
    // Search from our current iterator, either backwards or forwards,
282
90.3M
    // depending on what element we are looking for.
283
90.3M
    ElementListIter ElementIter = CurrElementIter;
284
90.3M
    if (
CurrElementIter->index() == ElementIndex90.3M
) {
285
82.4M
      return ElementIter;
286
90.3M
    } else 
if (7.89M
CurrElementIter->index() > ElementIndex7.89M
) {
287
7.74M
      while (ElementIter != Elements.begin()
288
4.02M
             && ElementIter->index() > ElementIndex)
289
3.52M
        --ElementIter;
290
7.89M
    } else {
291
9.22M
      while (ElementIter != Elements.end() &&
292
7.13M
             ElementIter->index() < ElementIndex)
293
5.55M
        ++ElementIter;
294
7.89M
    }
295
7.89M
    CurrElementIter = ElementIter;
296
7.89M
    return ElementIter;
297
90.3M
  }
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
5.81M
    void AdvanceToFirstNonZero() {
321
5.81M
      if (AtEnd)
322
2.89M
        return;
323
2.92M
      
if (2.92M
BitVector->Elements.empty()2.92M
) {
324
2.57M
        AtEnd = true;
325
2.57M
        return;
326
2.57M
      }
327
341k
      Iter = BitVector->Elements.begin();
328
341k
      BitNumber = Iter->index() * ElementSize;
329
341k
      unsigned BitPos = Iter->find_first();
330
341k
      BitNumber += BitPos;
331
341k
      WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
332
341k
      Bits = Iter->word(WordNumber);
333
341k
      Bits >>= BitPos % BITWORD_SIZE;
334
341k
    }
335
336
    // Move our iterator to the next non-zero bit.
337
1.43M
    void AdvanceToNextNonZero() {
338
1.43M
      if (AtEnd)
339
0
        return;
340
1.43M
341
4.96M
      
while (1.43M
Bits && 4.96M
!(Bits & 1)4.47M
) {
342
3.53M
        Bits >>= 1;
343
3.53M
        BitNumber += 1;
344
3.53M
      }
345
1.43M
346
1.43M
      // See if we ran out of Bits in this word.
347
1.43M
      if (
!Bits1.43M
) {
348
485k
        int NextSetBitNumber = Iter->find_next(BitNumber % ElementSize) ;
349
485k
        // If we ran out of set bits in this element, move to next element.
350
485k
        if (
NextSetBitNumber == -1 || 485k
(BitNumber % ElementSize == 0)58.4k
) {
351
430k
          ++Iter;
352
430k
          WordNumber = 0;
353
430k
354
430k
          // We may run out of elements in the bitmap.
355
430k
          if (
Iter == BitVector->Elements.end()430k
) {
356
318k
            AtEnd = true;
357
318k
            return;
358
318k
          }
359
430k
          // Set up for next non-zero word in bitmap.
360
112k
          BitNumber = Iter->index() * ElementSize;
361
112k
          NextSetBitNumber = Iter->find_first();
362
112k
          BitNumber += NextSetBitNumber;
363
112k
          WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
364
112k
          Bits = Iter->word(WordNumber);
365
112k
          Bits >>= NextSetBitNumber % BITWORD_SIZE;
366
485k
        } else {
367
54.5k
          WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE;
368
54.5k
          Bits = Iter->word(WordNumber);
369
54.5k
          Bits >>= NextSetBitNumber % BITWORD_SIZE;
370
54.5k
          BitNumber = Iter->index() * ElementSize;
371
54.5k
          BitNumber += NextSetBitNumber;
372
54.5k
        }
373
485k
      }
374
1.43M
    }
375
376
  public:
377
    SparseBitVectorIterator() = default;
378
379
    SparseBitVectorIterator(const SparseBitVector<ElementSize> *RHS,
380
5.81M
                            bool end = false):BitVector(RHS) {
381
5.81M
      Iter = BitVector->Elements.begin();
382
5.81M
      BitNumber = 0;
383
5.81M
      Bits = 0;
384
5.81M
      WordNumber = ~0;
385
5.81M
      AtEnd = end;
386
5.81M
      AdvanceToFirstNonZero();
387
5.81M
    }
388
389
    // Preincrement.
390
1.43M
    inline SparseBitVectorIterator& operator++() {
391
1.43M
      ++BitNumber;
392
1.43M
      Bits >>= 1;
393
1.43M
      AdvanceToNextNonZero();
394
1.43M
      return *this;
395
1.43M
    }
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.45M
    unsigned operator*() const {
406
1.45M
      return BitNumber;
407
1.45M
    }
408
409
4.45M
    bool operator==(const SparseBitVectorIterator &RHS) const {
410
4.45M
      // If they are both at the end, ignore the rest of the fields.
411
4.45M
      if (
AtEnd && 4.45M
RHS.AtEnd2.90M
)
412
2.90M
        return true;
413
4.45M
      // Otherwise they are the same if they have the same bit number and
414
4.45M
      // bitmap.
415
1.55M
      
return AtEnd == RHS.AtEnd && 1.55M
RHS.BitNumber == BitNumber0
;
416
4.45M
    }
417
418
4.27M
    bool operator!=(const SparseBitVectorIterator &RHS) const {
419
4.27M
      return !(*this == RHS);
420
4.27M
    }
421
  };
422
423
public:
424
  using iterator = SparseBitVectorIterator;
425
426
755k
  SparseBitVector() {
427
755k
    CurrElementIter = Elements.begin();
428
755k
  }
429
430
  // SparseBitVector copy ctor.
431
28.5M
  SparseBitVector(const SparseBitVector &RHS) {
432
28.5M
    ElementListConstIter ElementIter = RHS.Elements.begin();
433
28.9M
    while (
ElementIter != RHS.Elements.end()28.9M
) {
434
434k
      Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter));
435
434k
      ++ElementIter;
436
434k
    }
437
28.5M
438
28.5M
    CurrElementIter = Elements.begin ();
439
28.5M
  }
440
441
29.2M
  ~SparseBitVector() = default;
442
443
  // Clear.
444
1.18M
  void clear() {
445
1.18M
    Elements.clear();
446
1.18M
  }
447
448
  // Assignment
449
39.3k
  SparseBitVector& operator=(const SparseBitVector& RHS) {
450
39.3k
    if (this == &RHS)
451
1
      return *this;
452
39.3k
453
39.3k
    Elements.clear();
454
39.3k
455
39.3k
    ElementListConstIter ElementIter = RHS.Elements.begin();
456
82.7k
    while (
ElementIter != RHS.Elements.end()82.7k
) {
457
43.3k
      Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter));
458
43.3k
      ++ElementIter;
459
43.3k
    }
460
39.3k
461
39.3k
    CurrElementIter = Elements.begin ();
462
39.3k
463
39.3k
    return *this;
464
39.3k
  }
465
466
  // Test, Reset, and Set a bit in the bitmap.
467
158M
  bool test(unsigned Idx) {
468
158M
    if (Elements.empty())
469
99.3M
      return false;
470
158M
471
58.9M
    unsigned ElementIndex = Idx / ElementSize;
472
58.9M
    ElementListIter ElementIter = FindLowerBound(ElementIndex);
473
58.9M
474
58.9M
    // If we can't find an element that is supposed to contain this bit, there
475
58.9M
    // is nothing more to do.
476
58.9M
    if (ElementIter == Elements.end() ||
477
57.0M
        ElementIter->index() != ElementIndex)
478
4.84M
      return false;
479
54.0M
    return ElementIter->test(Idx % ElementSize);
480
158M
  }
481
482
2.12M
  void reset(unsigned Idx) {
483
2.12M
    if (Elements.empty())
484
1.62M
      return;
485
2.12M
486
490k
    unsigned ElementIndex = Idx / ElementSize;
487
490k
    ElementListIter ElementIter = FindLowerBound(ElementIndex);
488
490k
489
490k
    // If we can't find an element that is supposed to contain this bit, there
490
490k
    // is nothing more to do.
491
490k
    if (ElementIter == Elements.end() ||
492
490k
        ElementIter->index() != ElementIndex)
493
0
      return;
494
490k
    ElementIter->reset(Idx % ElementSize);
495
490k
496
490k
    // When the element is zeroed out, delete it.
497
490k
    if (
ElementIter->empty()490k
) {
498
191k
      ++CurrElementIter;
499
191k
      Elements.erase(ElementIter);
500
191k
    }
501
2.12M
  }
502
503
33.3M
  void set(unsigned Idx) {
504
33.3M
    unsigned ElementIndex = Idx / ElementSize;
505
33.3M
    ElementListIter ElementIter;
506
33.3M
    if (
Elements.empty()33.3M
) {
507
2.41M
      ElementIter = Elements.emplace(Elements.end(), ElementIndex);
508
33.3M
    } else {
509
30.9M
      ElementIter = FindLowerBound(ElementIndex);
510
30.9M
511
30.9M
      if (ElementIter == Elements.end() ||
512
30.9M
          
ElementIter->index() != ElementIndex30.7M
) {
513
302k
        // We may have hit the beginning of our SparseBitVector, in which case,
514
302k
        // we may need to insert right after this element, which requires moving
515
302k
        // the current iterator forward one, because insert does insert before.
516
302k
        if (ElementIter != Elements.end() &&
517
101k
            ElementIter->index() < ElementIndex)
518
5.39k
          ++ElementIter;
519
302k
        ElementIter = Elements.emplace(ElementIter, ElementIndex);
520
302k
      }
521
30.9M
    }
522
33.3M
    CurrElementIter = ElementIter;
523
33.3M
524
33.3M
    ElementIter->set(Idx % ElementSize);
525
33.3M
  }
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
341k
  bool operator|=(const SparseBitVector &RHS) {
554
341k
    if (this == &RHS)
555
1
      return false;
556
341k
557
341k
    bool changed = false;
558
341k
    ElementListIter Iter1 = Elements.begin();
559
341k
    ElementListConstIter Iter2 = RHS.Elements.begin();
560
341k
561
341k
    // If RHS is empty, we are done
562
341k
    if (RHS.Elements.empty())
563
0
      return false;
564
341k
565
703k
    
while (341k
Iter2 != RHS.Elements.end()703k
) {
566
361k
      if (
Iter1 == Elements.end() || 361k
Iter1->index() > Iter2->index()330k
) {
567
32.5k
        Elements.insert(Iter1, *Iter2);
568
32.5k
        ++Iter2;
569
32.5k
        changed = true;
570
361k
      } else 
if (328k
Iter1->index() == Iter2->index()328k
) {
571
311k
        changed |= Iter1->unionWith(*Iter2);
572
311k
        ++Iter1;
573
311k
        ++Iter2;
574
328k
      } else {
575
17.1k
        ++Iter1;
576
17.1k
      }
577
361k
    }
578
341k
    CurrElementIter = Elements.begin();
579
341k
    return changed;
580
341k
  }
581
582
  // Intersect our bitmap with the RHS and return true if ours changed.
583
247
  bool operator&=(const SparseBitVector &RHS) {
584
247
    if (this == &RHS)
585
1
      return false;
586
247
587
246
    bool changed = false;
588
246
    ElementListIter Iter1 = Elements.begin();
589
246
    ElementListConstIter Iter2 = RHS.Elements.begin();
590
246
591
246
    // Check if both bitmaps are empty.
592
246
    if (
Elements.empty() && 246
RHS.Elements.empty()0
)
593
0
      return false;
594
246
595
246
    // Loop through, intersecting as we go, erasing elements when necessary.
596
507
    
while (246
Iter2 != RHS.Elements.end()507
) {
597
262
      if (
Iter1 == Elements.end()262
) {
598
1
        CurrElementIter = Elements.begin();
599
1
        return changed;
600
1
      }
601
262
602
261
      
if (261
Iter1->index() > Iter2->index()261
) {
603
1
        ++Iter2;
604
261
      } else 
if (260
Iter1->index() == Iter2->index()260
) {
605
244
        bool BecameZero;
606
244
        changed |= Iter1->intersectWith(*Iter2, BecameZero);
607
244
        if (
BecameZero244
) {
608
13
          ElementListIter IterTmp = Iter1;
609
13
          ++Iter1;
610
13
          Elements.erase(IterTmp);
611
244
        } else {
612
231
          ++Iter1;
613
231
        }
614
244
        ++Iter2;
615
260
      } else {
616
16
        ElementListIter IterTmp = Iter1;
617
16
        ++Iter1;
618
16
        Elements.erase(IterTmp);
619
16
        changed = true;
620
16
      }
621
262
    }
622
245
    
if (245
Iter1 != Elements.end()245
) {
623
1
      Elements.erase(Iter1, Elements.end());
624
1
      changed = true;
625
1
    }
626
245
    CurrElementIter = Elements.begin();
627
245
    return changed;
628
247
  }
629
630
  // Intersect our bitmap with the complement of the RHS and return true
631
  // if ours changed.
632
489k
  bool intersectWithComplement(const SparseBitVector &RHS) {
633
489k
    if (
this == &RHS489k
) {
634
3
      if (
!empty()3
) {
635
2
        clear();
636
2
        return true;
637
2
      }
638
1
      return false;
639
3
    }
640
489k
641
489k
    bool changed = false;
642
489k
    ElementListIter Iter1 = Elements.begin();
643
489k
    ElementListConstIter Iter2 = RHS.Elements.begin();
644
489k
645
489k
    // If either our bitmap or RHS is empty, we are done
646
489k
    if (
Elements.empty() || 489k
RHS.Elements.empty()6.11k
)
647
488k
      return false;
648
489k
649
489k
    // Loop through, intersecting as we go, erasing elements when necessary.
650
1.16k
    
while (580
Iter2 != RHS.Elements.end()1.16k
) {
651
581
      if (
Iter1 == Elements.end()581
) {
652
0
        CurrElementIter = Elements.begin();
653
0
        return changed;
654
0
      }
655
581
656
581
      
if (581
Iter1->index() > Iter2->index()581
) {
657
0
        ++Iter2;
658
581
      } else 
if (581
Iter1->index() == Iter2->index()581
) {
659
581
        bool BecameZero;
660
581
        changed |= Iter1->intersectWithComplement(*Iter2, BecameZero);
661
581
        if (
BecameZero581
) {
662
437
          ElementListIter IterTmp = Iter1;
663
437
          ++Iter1;
664
437
          Elements.erase(IterTmp);
665
581
        } else {
666
144
          ++Iter1;
667
144
        }
668
581
        ++Iter2;
669
0
      } else {
670
0
        ++Iter1;
671
0
      }
672
581
    }
673
580
    CurrElementIter = Elements.begin();
674
580
    return changed;
675
489k
  }
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
69
  bool intersects(const SparseBitVector<ElementSize> &RHS) const {
740
69
    ElementListConstIter Iter1 = Elements.begin();
741
69
    ElementListConstIter Iter2 = RHS.Elements.begin();
742
69
743
69
    // Check if both bitmaps are empty.
744
69
    if (
Elements.empty() && 69
RHS.Elements.empty()0
)
745
0
      return false;
746
69
747
69
    // Loop through, intersecting stopping when we hit bits in common.
748
69
    
while (69
Iter2 != RHS.Elements.end()69
) {
749
0
      if (Iter1 == Elements.end())
750
0
        return false;
751
0
752
0
      
if (0
Iter1->index() > Iter2->index()0
) {
753
0
        ++Iter2;
754
0
      } else 
if (0
Iter1->index() == Iter2->index()0
) {
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
69
    return false;
764
69
  }
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
139
  int find_first() const {
776
139
    if (Elements.empty())
777
4
      return -1;
778
135
    const SparseBitVectorElement<ElementSize> &First = *(Elements.begin());
779
135
    return (First.index() * ElementSize) + First.find_first();
780
139
  }
781
782
  // Return the last set bit in the bitmap.  Return -1 if no bits are set.
783
250
  int find_last() const {
784
250
    if (Elements.empty())
785
122
      return -1;
786
128
    const SparseBitVectorElement<ElementSize> &Last = *(Elements.rbegin());
787
128
    return (Last.index() * ElementSize) + Last.find_last();
788
250
  }
789
790
  // Return true if the SparseBitVector is empty
791
16.2M
  bool empty() const {
792
16.2M
    return Elements.empty();
793
16.2M
  }
794
795
59.6k
  unsigned count() const {
796
59.6k
    unsigned BitCount = 0;
797
59.6k
    for (ElementListConstIter Iter = Elements.begin();
798
124k
         Iter != Elements.end();
799
64.6k
         ++Iter)
800
64.6k
      BitCount += Iter->count();
801
59.6k
802
59.6k
    return BitCount;
803
59.6k
  }
804
805
2.92M
  iterator begin() const {
806
2.92M
    return iterator(this);
807
2.92M
  }
808
809
2.89M
  iterator end() const {
810
2.89M
    return iterator(this, true);
811
2.89M
  }
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