Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/include/llvm/ADT/SmallBitVector.h
Line
Count
Source (jump to first uncovered line)
1
//===- llvm/ADT/SmallBitVector.h - 'Normally small' bit vectors -*- 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 implements the SmallBitVector class.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#ifndef LLVM_ADT_SMALLBITVECTOR_H
15
#define LLVM_ADT_SMALLBITVECTOR_H
16
17
#include "llvm/ADT/BitVector.h"
18
#include "llvm/ADT/iterator_range.h"
19
#include "llvm/Support/MathExtras.h"
20
#include <algorithm>
21
#include <cassert>
22
#include <climits>
23
#include <cstddef>
24
#include <cstdint>
25
#include <limits>
26
#include <utility>
27
28
namespace llvm {
29
30
/// This is a 'bitvector' (really, a variable-sized bit array), optimized for
31
/// the case when the array is small. It contains one pointer-sized field, which
32
/// is directly used as a plain collection of bits when possible, or as a
33
/// pointer to a larger heap-allocated array when necessary. This allows normal
34
/// "small" cases to be fast without losing generality for large inputs.
35
class SmallBitVector {
36
  // TODO: In "large" mode, a pointer to a BitVector is used, leading to an
37
  // unnecessary level of indirection. It would be more efficient to use a
38
  // pointer to memory containing size, allocation size, and the array of bits.
39
  uintptr_t X = 1;
40
41
  enum {
42
    // The number of bits in this class.
43
    NumBaseBits = sizeof(uintptr_t) * CHAR_BIT,
44
45
    // One bit is used to discriminate between small and large mode. The
46
    // remaining bits are used for the small-mode representation.
47
    SmallNumRawBits = NumBaseBits - 1,
48
49
    // A few more bits are used to store the size of the bit set in small mode.
50
    // Theoretically this is a ceil-log2. These bits are encoded in the most
51
    // significant bits of the raw bits.
52
    SmallNumSizeBits = (NumBaseBits == 32 ? 5 :
53
                        NumBaseBits == 64 ? 6 :
54
                        SmallNumRawBits),
55
56
    // The remaining bits are used to store the actual set in small mode.
57
    SmallNumDataBits = SmallNumRawBits - SmallNumSizeBits
58
  };
59
60
  static_assert(NumBaseBits == 64 || NumBaseBits == 32,
61
                "Unsupported word size");
62
63
public:
64
  using size_type = unsigned;
65
66
  // Encapsulation of a single bit.
67
  class reference {
68
    SmallBitVector &TheVector;
69
    unsigned BitPos;
70
71
  public:
72
148M
    reference(SmallBitVector &b, unsigned Idx) : TheVector(b), BitPos(Idx) {}
73
74
    reference(const reference&) = default;
75
76
0
    reference& operator=(reference t) {
77
0
      *this = bool(t);
78
0
      return *this;
79
0
    }
80
81
89.8M
    reference& operator=(bool t) {
82
89.8M
      if (t)
83
2.80M
        TheVector.set(BitPos);
84
89.8M
      else
85
87.0M
        TheVector.reset(BitPos);
86
89.8M
      return *this;
87
89.8M
    }
88
89
58.1M
    operator bool() const {
90
58.1M
      return const_cast<const SmallBitVector &>(TheVector).operator[](BitPos);
91
58.1M
    }
92
  };
93
94
private:
95
654M
  bool isSmall() const {
96
654M
    return X & uintptr_t(1);
97
654M
  }
98
99
294M
  BitVector *getPointer() const {
100
294M
    assert(!isSmall());
101
294M
    return reinterpret_cast<BitVector *>(X);
102
294M
  }
103
104
11.7M
  void switchToSmall(uintptr_t NewSmallBits, size_t NewSize) {
105
11.7M
    X = 1;
106
11.7M
    setSmallSize(NewSize);
107
11.7M
    setSmallBits(NewSmallBits);
108
11.7M
  }
109
110
587k
  void switchToLarge(BitVector *BV) {
111
587k
    X = reinterpret_cast<uintptr_t>(BV);
112
587k
    assert(!isSmall() && "Tried to use an unaligned pointer");
113
587k
  }
114
115
  // Return all the bits used for the "small" representation; this includes
116
  // bits for the size as well as the element bits.
117
891M
  uintptr_t getSmallRawBits() const {
118
891M
    assert(isSmall());
119
891M
    return X >> 1;
120
891M
  }
121
122
199M
  void setSmallRawBits(uintptr_t NewRawBits) {
123
199M
    assert(isSmall());
124
199M
    X = (NewRawBits << 1) | uintptr_t(1);
125
199M
  }
126
127
  // Return the size.
128
651M
  size_t getSmallSize() const { return getSmallRawBits() >> SmallNumDataBits; }
129
130
66.7M
  void setSmallSize(size_t Size) {
131
66.7M
    setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits));
132
66.7M
  }
133
134
  // Return the element bits.
135
239M
  uintptr_t getSmallBits() const {
136
239M
    return getSmallRawBits() & ~(~uintptr_t(0) << getSmallSize());
137
239M
  }
138
139
132M
  void setSmallBits(uintptr_t NewBits) {
140
132M
    setSmallRawBits((NewBits & ~(~uintptr_t(0) << getSmallSize())) |
141
132M
                    (getSmallSize() << SmallNumDataBits));
142
132M
  }
143
144
public:
145
  /// Creates an empty bitvector.
146
18.0M
  SmallBitVector() = default;
147
148
  /// Creates a bitvector of specified number of bits. All bits are initialized
149
  /// to the specified value.
150
8.28M
  explicit SmallBitVector(unsigned s, bool t = false) {
151
8.28M
    if (s <= SmallNumDataBits)
152
8.28M
      
switchToSmall(t ? 8.28M
~uintptr_t(0)146k
:
08.14M
, s);
153
8.28M
    else
154
923
      switchToLarge(new BitVector(s, t));
155
8.28M
  }
156
157
  /// SmallBitVector copy ctor.
158
191k
  SmallBitVector(const SmallBitVector &RHS) {
159
191k
    if (RHS.isSmall())
160
191k
      X = RHS.X;
161
191k
    else
162
5
      switchToLarge(new BitVector(*RHS.getPointer()));
163
191k
  }
164
165
16.3M
  SmallBitVector(SmallBitVector &&RHS) : X(RHS.X) {
166
16.3M
    RHS.X = 1;
167
16.3M
  }
168
169
42.8M
  ~SmallBitVector() {
170
42.8M
    if (!isSmall())
171
587k
      delete getPointer();
172
42.8M
  }
173
174
  using const_set_bits_iterator = const_set_bits_iterator_impl<SmallBitVector>;
175
  using set_iterator = const_set_bits_iterator;
176
177
4.40M
  const_set_bits_iterator set_bits_begin() const {
178
4.40M
    return const_set_bits_iterator(*this);
179
4.40M
  }
180
181
4.40M
  const_set_bits_iterator set_bits_end() const {
182
4.40M
    return const_set_bits_iterator(*this, -1);
183
4.40M
  }
184
185
4.40M
  iterator_range<const_set_bits_iterator> set_bits() const {
186
4.40M
    return make_range(set_bits_begin(), set_bits_end());
187
4.40M
  }
188
189
  /// Tests whether there are no bits in this bitvector.
190
161k
  bool empty() const {
191
161k
    return isSmall() ? 
getSmallSize() == 0161k
:
getPointer()->empty()4
;
192
161k
  }
193
194
  /// Returns the number of bits in this bitvector.
195
290M
  size_t size() const {
196
290M
    return isSmall() ? 
getSmallSize()141M
:
getPointer()->size()148M
;
197
290M
  }
198
199
  /// Returns the number of bits which are set.
200
2.63M
  size_type count() const {
201
2.63M
    if (
isSmall()2.63M
) {
202
2.00M
      uintptr_t Bits = getSmallBits();
203
2.00M
      return countPopulation(Bits);
204
2.00M
    }
205
626k
    return getPointer()->count();
206
2.63M
  }
207
208
  /// Returns true if any bit is set.
209
65.7k
  bool any() const {
210
65.7k
    if (isSmall())
211
65.6k
      return getSmallBits() != 0;
212
4
    return getPointer()->any();
213
65.7k
  }
214
215
  /// Returns true if all bits are set.
216
4.22k
  bool all() const {
217
4.22k
    if (isSmall())
218
4.22k
      return getSmallBits() == (uintptr_t(1) << getSmallSize()) - 1;
219
4
    return getPointer()->all();
220
4.22k
  }
221
222
  /// Returns true if none of the bits are set.
223
  bool none() const {
224
    if (isSmall())
225
      return getSmallBits() == 0;
226
    return getPointer()->none();
227
  }
228
229
  /// Returns the index of the first set bit, -1 if none of the bits are set.
230
15.4M
  int find_first() const {
231
15.4M
    if (
isSmall()15.4M
) {
232
11.8M
      uintptr_t Bits = getSmallBits();
233
11.8M
      if (Bits == 0)
234
78.1k
        return -1;
235
11.8M
      return countTrailingZeros(Bits);
236
11.8M
    }
237
3.61M
    return getPointer()->find_first();
238
15.4M
  }
239
240
  int find_last() const {
241
    if (isSmall()) {
242
      uintptr_t Bits = getSmallBits();
243
      if (Bits == 0)
244
        return -1;
245
      return NumBaseBits - countLeadingZeros(Bits);
246
    }
247
    return getPointer()->find_last();
248
  }
249
250
  /// Returns the index of the first unset bit, -1 if all of the bits are set.
251
  int find_first_unset() const {
252
    if (isSmall()) {
253
      if (count() == getSmallSize())
254
        return -1;
255
256
      uintptr_t Bits = getSmallBits();
257
      return countTrailingOnes(Bits);
258
    }
259
    return getPointer()->find_first_unset();
260
  }
261
262
  int find_last_unset() const {
263
    if (isSmall()) {
264
      if (count() == getSmallSize())
265
        return -1;
266
267
      uintptr_t Bits = getSmallBits();
268
      return NumBaseBits - countLeadingOnes(Bits);
269
    }
270
    return getPointer()->find_last_unset();
271
  }
272
273
  /// Returns the index of the next set bit following the "Prev" bit.
274
  /// Returns -1 if the next set bit is not found.
275
12.8M
  int find_next(unsigned Prev) const {
276
12.8M
    if (
isSmall()12.8M
) {
277
10.1M
      uintptr_t Bits = getSmallBits();
278
10.1M
      // Mask off previous bits.
279
10.1M
      Bits &= ~uintptr_t(0) << (Prev + 1);
280
10.1M
      if (
Bits == 0 || 10.1M
Prev + 1 >= getSmallSize()3.20M
)
281
6.99M
        return -1;
282
3.20M
      return countTrailingZeros(Bits);
283
10.1M
    }
284
2.70M
    return getPointer()->find_next(Prev);
285
12.8M
  }
286
287
  /// Returns the index of the next unset bit following the "Prev" bit.
288
  /// Returns -1 if the next unset bit is not found.
289
  int find_next_unset(unsigned Prev) const {
290
    if (isSmall()) {
291
      ++Prev;
292
      uintptr_t Bits = getSmallBits();
293
      // Mask in previous bits.
294
      uintptr_t Mask = (1 << Prev) - 1;
295
      Bits |= Mask;
296
297
      if (Bits == ~uintptr_t(0) || Prev + 1 >= getSmallSize())
298
        return -1;
299
      return countTrailingOnes(Bits);
300
    }
301
    return getPointer()->find_next_unset(Prev);
302
  }
303
304
  /// find_prev - Returns the index of the first set bit that precedes the
305
  /// the bit at \p PriorTo.  Returns -1 if all previous bits are unset.
306
  int find_prev(unsigned PriorTo) const {
307
    if (isSmall()) {
308
      if (PriorTo == 0)
309
        return -1;
310
311
      --PriorTo;
312
      uintptr_t Bits = getSmallBits();
313
      Bits &= maskTrailingOnes<uintptr_t>(PriorTo + 1);
314
      if (Bits == 0)
315
        return -1;
316
317
      return NumBaseBits - countLeadingZeros(Bits) - 1;
318
    }
319
    return getPointer()->find_prev(PriorTo);
320
  }
321
322
  /// Clear all bits.
323
3.42M
  void clear() {
324
3.42M
    if (!isSmall())
325
2
      delete getPointer();
326
3.42M
    switchToSmall(0, 0);
327
3.42M
  }
328
329
  /// Grow or shrink the bitvector.
330
106M
  void resize(unsigned N, bool t = false) {
331
106M
    if (
!isSmall()106M
) {
332
50.9M
      getPointer()->resize(N, t);
333
106M
    } else 
if (55.5M
SmallNumDataBits >= N55.5M
) {
334
54.9M
      uintptr_t NewBits = t ? 
~uintptr_t(0) << getSmallSize()54
:
054.9M
;
335
54.9M
      setSmallSize(N);
336
54.9M
      setSmallBits(NewBits | getSmallBits());
337
55.5M
    } else {
338
586k
      BitVector *BV = new BitVector(N, t);
339
586k
      uintptr_t OldBits = getSmallBits();
340
6.44M
      for (size_t i = 0, e = getSmallSize(); 
i != e6.44M
;
++i5.85M
)
341
5.85M
        (*BV)[i] = (OldBits >> i) & 1;
342
55.5M
      switchToLarge(BV);
343
55.5M
    }
344
106M
  }
345
346
0
  void reserve(unsigned N) {
347
0
    if (isSmall()) {
348
0
      if (N > SmallNumDataBits) {
349
0
        uintptr_t OldBits = getSmallRawBits();
350
0
        size_t SmallSize = getSmallSize();
351
0
        BitVector *BV = new BitVector(SmallSize);
352
0
        for (size_t i = 0; i < SmallSize; ++i)
353
0
          if ((OldBits >> i) & 1)
354
0
            BV->set(i);
355
0
        BV->reserve(N);
356
0
        switchToLarge(BV);
357
0
      }
358
0
    } else {
359
0
      getPointer()->reserve(N);
360
0
    }
361
0
  }
362
363
  // Set, reset, flip
364
  SmallBitVector &set() {
365
    if (isSmall())
366
      setSmallBits(~uintptr_t(0));
367
    else
368
      getPointer()->set();
369
    return *this;
370
  }
371
372
25.2M
  SmallBitVector &set(unsigned Idx) {
373
25.2M
    if (
isSmall()25.2M
) {
374
21.9M
      assert(Idx <= static_cast<unsigned>(
375
21.9M
                        std::numeric_limits<uintptr_t>::digits) &&
376
21.9M
             "undefined behavior");
377
21.9M
      setSmallBits(getSmallBits() | (uintptr_t(1) << Idx));
378
21.9M
    }
379
25.2M
    else
380
3.36M
      getPointer()->set(Idx);
381
25.2M
    return *this;
382
25.2M
  }
383
384
  /// Efficiently set a range of bits in [I, E)
385
160k
  SmallBitVector &set(unsigned I, unsigned E) {
386
160k
    assert(I <= E && "Attempted to set backwards range!");
387
160k
    assert(E <= size() && "Attempted to set out-of-bounds range!");
388
160k
    if (
I == E160k
)
return *this0
;
389
160k
    
if (160k
isSmall()160k
) {
390
160k
      uintptr_t EMask = ((uintptr_t)1) << E;
391
160k
      uintptr_t IMask = ((uintptr_t)1) << I;
392
160k
      uintptr_t Mask = EMask - IMask;
393
160k
      setSmallBits(getSmallBits() | Mask);
394
160k
    } else
395
99
      getPointer()->set(I, E);
396
160k
    return *this;
397
160k
  }
398
399
324k
  SmallBitVector &reset() {
400
324k
    if (isSmall())
401
322k
      setSmallBits(0);
402
324k
    else
403
1.85k
      getPointer()->reset();
404
324k
    return *this;
405
324k
  }
406
407
88.0M
  SmallBitVector &reset(unsigned Idx) {
408
88.0M
    if (isSmall())
409
40.5M
      setSmallBits(getSmallBits() & ~(uintptr_t(1) << Idx));
410
88.0M
    else
411
47.4M
      getPointer()->reset(Idx);
412
88.0M
    return *this;
413
88.0M
  }
414
415
  /// Efficiently reset a range of bits in [I, E)
416
219k
  SmallBitVector &reset(unsigned I, unsigned E) {
417
219k
    assert(I <= E && "Attempted to reset backwards range!");
418
219k
    assert(E <= size() && "Attempted to reset out-of-bounds range!");
419
219k
    if (
I == E219k
)
return *this0
;
420
219k
    
if (219k
isSmall()219k
) {
421
219k
      uintptr_t EMask = ((uintptr_t)1) << E;
422
219k
      uintptr_t IMask = ((uintptr_t)1) << I;
423
219k
      uintptr_t Mask = EMask - IMask;
424
219k
      setSmallBits(getSmallBits() & ~Mask);
425
219k
    } else
426
3
      getPointer()->reset(I, E);
427
219k
    return *this;
428
219k
  }
429
430
77.7k
  SmallBitVector &flip() {
431
77.7k
    if (isSmall())
432
77.7k
      setSmallBits(~getSmallBits());
433
77.7k
    else
434
3
      getPointer()->flip();
435
77.7k
    return *this;
436
77.7k
  }
437
438
  SmallBitVector &flip(unsigned Idx) {
439
    if (isSmall())
440
      setSmallBits(getSmallBits() ^ (uintptr_t(1) << Idx));
441
    else
442
      getPointer()->flip(Idx);
443
    return *this;
444
  }
445
446
  // No argument flip.
447
0
  SmallBitVector operator~() const {
448
0
    return SmallBitVector(*this).flip();
449
0
  }
450
451
  // Indexing.
452
148M
  reference operator[](unsigned Idx) {
453
148M
    assert(Idx < size() && "Out-of-bounds Bit access.");
454
148M
    return reference(*this, Idx);
455
148M
  }
456
457
59.9M
  bool operator[](unsigned Idx) const {
458
59.9M
    assert(Idx < size() && "Out-of-bounds Bit access.");
459
59.9M
    if (isSmall())
460
24.7M
      return ((getSmallBits() >> Idx) & 1) != 0;
461
35.1M
    return getPointer()->operator[](Idx);
462
59.9M
  }
463
464
1.17k
  bool test(unsigned Idx) const {
465
1.17k
    return (*this)[Idx];
466
1.17k
  }
467
468
  /// Test if any common bits are set.
469
  bool anyCommon(const SmallBitVector &RHS) const {
470
    if (isSmall() && RHS.isSmall())
471
      return (getSmallBits() & RHS.getSmallBits()) != 0;
472
    if (!isSmall() && !RHS.isSmall())
473
      return getPointer()->anyCommon(*RHS.getPointer());
474
475
    for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
476
      if (test(i) && RHS.test(i))
477
        return true;
478
    return false;
479
  }
480
481
  // Comparison operators.
482
233k
  bool operator==(const SmallBitVector &RHS) const {
483
233k
    if (size() != RHS.size())
484
0
      return false;
485
233k
    
if (233k
isSmall()233k
)
486
231k
      return getSmallBits() == RHS.getSmallBits();
487
233k
    else
488
1.80k
      return *getPointer() == *RHS.getPointer();
489
233k
  }
490
491
233k
  bool operator!=(const SmallBitVector &RHS) const {
492
233k
    return !(*this == RHS);
493
233k
  }
494
495
  // Intersection, union, disjoint union.
496
349
  SmallBitVector &operator&=(const SmallBitVector &RHS) {
497
349
    resize(std::max(size(), RHS.size()));
498
349
    if (isSmall())
499
349
      setSmallBits(getSmallBits() & RHS.getSmallBits());
500
0
    else 
if (0
!RHS.isSmall()0
)
501
0
      getPointer()->operator&=(*RHS.getPointer());
502
0
    else {
503
0
      SmallBitVector Copy = RHS;
504
0
      Copy.resize(size());
505
0
      getPointer()->operator&=(*Copy.getPointer());
506
0
    }
507
349
    return *this;
508
349
  }
509
510
  /// Reset bits that are set in RHS. Same as *this &= ~RHS.
511
  SmallBitVector &reset(const SmallBitVector &RHS) {
512
    if (isSmall() && RHS.isSmall())
513
      setSmallBits(getSmallBits() & ~RHS.getSmallBits());
514
    else if (!isSmall() && !RHS.isSmall())
515
      getPointer()->reset(*RHS.getPointer());
516
    else
517
      for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
518
        if (RHS.test(i))
519
          reset(i);
520
521
    return *this;
522
  }
523
524
  /// Check if (This - RHS) is zero. This is the same as reset(RHS) and any().
525
40
  bool test(const SmallBitVector &RHS) const {
526
40
    if (
isSmall() && 40
RHS.isSmall()8
)
527
4
      return (getSmallBits() & ~RHS.getSmallBits()) != 0;
528
36
    
if (36
!isSmall() && 36
!RHS.isSmall()32
)
529
30
      return getPointer()->test(*RHS.getPointer());
530
36
531
6
    unsigned i, e;
532
206
    for (i = 0, e = std::min(size(), RHS.size()); 
i != e206
;
++i200
)
533
202
      
if (202
test(i) && 202
!RHS.test(i)102
)
534
2
        return true;
535
6
536
4
    
for (e = size(); 4
i != e4
;
++i0
)
537
1
      
if (1
test(i)1
)
538
1
        return true;
539
4
540
3
    return false;
541
40
  }
542
543
3.25M
  SmallBitVector &operator|=(const SmallBitVector &RHS) {
544
3.25M
    resize(std::max(size(), RHS.size()));
545
3.25M
    if (isSmall())
546
2.68M
      setSmallBits(getSmallBits() | RHS.getSmallBits());
547
571k
    else 
if (571k
!RHS.isSmall()571k
)
548
386k
      getPointer()->operator|=(*RHS.getPointer());
549
184k
    else {
550
184k
      SmallBitVector Copy = RHS;
551
184k
      Copy.resize(size());
552
184k
      getPointer()->operator|=(*Copy.getPointer());
553
184k
    }
554
3.25M
    return *this;
555
3.25M
  }
556
557
  SmallBitVector &operator^=(const SmallBitVector &RHS) {
558
    resize(std::max(size(), RHS.size()));
559
    if (isSmall())
560
      setSmallBits(getSmallBits() ^ RHS.getSmallBits());
561
    else if (!RHS.isSmall())
562
      getPointer()->operator^=(*RHS.getPointer());
563
    else {
564
      SmallBitVector Copy = RHS;
565
      Copy.resize(size());
566
      getPointer()->operator^=(*Copy.getPointer());
567
    }
568
    return *this;
569
  }
570
571
  SmallBitVector &operator<<=(unsigned N) {
572
    if (isSmall())
573
      setSmallBits(getSmallBits() << N);
574
    else
575
      getPointer()->operator<<=(N);
576
    return *this;
577
  }
578
579
  SmallBitVector &operator>>=(unsigned N) {
580
    if (isSmall())
581
      setSmallBits(getSmallBits() >> N);
582
    else
583
      getPointer()->operator>>=(N);
584
    return *this;
585
  }
586
587
  // Assignment operator.
588
457k
  const SmallBitVector &operator=(const SmallBitVector &RHS) {
589
457k
    if (
isSmall()457k
) {
590
453k
      if (RHS.isSmall())
591
453k
        X = RHS.X;
592
453k
      else
593
0
        switchToLarge(new BitVector(*RHS.getPointer()));
594
457k
    } else {
595
3.56k
      if (!RHS.isSmall())
596
3.56k
        *getPointer() = *RHS.getPointer();
597
0
      else {
598
0
        delete getPointer();
599
0
        X = RHS.X;
600
0
      }
601
3.56k
    }
602
457k
    return *this;
603
457k
  }
604
605
  const SmallBitVector &operator=(SmallBitVector &&RHS) {
606
    if (this != &RHS) {
607
      clear();
608
      swap(RHS);
609
    }
610
    return *this;
611
  }
612
613
0
  void swap(SmallBitVector &RHS) {
614
0
    std::swap(X, RHS.X);
615
0
  }
616
617
  /// Add '1' bits from Mask to this vector. Don't resize.
618
  /// This computes "*this |= Mask".
619
  void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
620
    if (isSmall())
621
      applyMask<true, false>(Mask, MaskWords);
622
    else
623
      getPointer()->setBitsInMask(Mask, MaskWords);
624
  }
625
626
  /// Clear any bits in this vector that are set in Mask. Don't resize.
627
  /// This computes "*this &= ~Mask".
628
0
  void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
629
0
    if (isSmall())
630
0
      applyMask<false, false>(Mask, MaskWords);
631
0
    else
632
0
      getPointer()->clearBitsInMask(Mask, MaskWords);
633
0
  }
634
635
  /// Add a bit to this vector for every '0' bit in Mask. Don't resize.
636
  /// This computes "*this |= ~Mask".
637
  void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
638
    if (isSmall())
639
      applyMask<true, true>(Mask, MaskWords);
640
    else
641
      getPointer()->setBitsNotInMask(Mask, MaskWords);
642
  }
643
644
  /// Clear a bit in this vector for every '0' bit in Mask. Don't resize.
645
  /// This computes "*this &= Mask".
646
  void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
647
    if (isSmall())
648
      applyMask<false, true>(Mask, MaskWords);
649
    else
650
      getPointer()->clearBitsNotInMask(Mask, MaskWords);
651
  }
652
653
private:
654
  template <bool AddBits, bool InvertMask>
655
0
  void applyMask(const uint32_t *Mask, unsigned MaskWords) {
656
0
    assert(MaskWords <= sizeof(uintptr_t) && "Mask is larger than base!");
657
0
    uintptr_t M = Mask[0];
658
0
    if (NumBaseBits == 64)
659
0
      M |= uint64_t(Mask[1]) << 32;
660
0
    if (InvertMask)
661
0
      M = ~M;
662
0
    if (AddBits)
663
0
      setSmallBits(getSmallBits() | M);
664
0
    else
665
0
      setSmallBits(getSmallBits() & ~M);
666
0
  }
Unexecuted instantiation: void llvm::SmallBitVector::applyMask<true, true>(unsigned int const*, unsigned int)
Unexecuted instantiation: void llvm::SmallBitVector::applyMask<false, true>(unsigned int const*, unsigned int)
Unexecuted instantiation: void llvm::SmallBitVector::applyMask<false, false>(unsigned int const*, unsigned int)
667
};
668
669
inline SmallBitVector
670
0
operator&(const SmallBitVector &LHS, const SmallBitVector &RHS) {
671
0
  SmallBitVector Result(LHS);
672
0
  Result &= RHS;
673
0
  return Result;
674
0
}
675
676
inline SmallBitVector
677
2.53k
operator|(const SmallBitVector &LHS, const SmallBitVector &RHS) {
678
2.53k
  SmallBitVector Result(LHS);
679
2.53k
  Result |= RHS;
680
2.53k
  return Result;
681
2.53k
}
682
683
inline SmallBitVector
684
0
operator^(const SmallBitVector &LHS, const SmallBitVector &RHS) {
685
0
  SmallBitVector Result(LHS);
686
0
  Result ^= RHS;
687
0
  return Result;
688
0
}
689
690
} // end namespace llvm
691
692
namespace std {
693
694
/// Implement std::swap in terms of BitVector swap.
695
inline void
696
0
swap(llvm::SmallBitVector &LHS, llvm::SmallBitVector &RHS) {
697
0
  LHS.swap(RHS);
698
0
}
699
700
} // end namespace std
701
702
#endif // LLVM_ADT_SMALLBITVECTOR_H