Coverage Report

Created: 2019-03-22 08:08

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