1//===- llvm/ADT/BitVector.h - 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 BitVector class.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_ADT_BITVECTOR_H
15#define LLVM_ADT_BITVECTOR_H
16
17#include "llvm/Support/MathExtras.h"
18#include <algorithm>
19#include <cassert>
20#include <climits>
21#include <cstdint>
22#include <cstdlib>
23#include <cstring>
24
25namespace llvm {
26
27class BitVector {
28  typedef unsigned long BitWord;
29
30  enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * CHAR_BIT };
31
32  static_assert(BITWORD_SIZE == 64 || BITWORD_SIZE == 32,
33                "Unsupported word size");
34
35  BitWord  *Bits;        // Actual bits.
36  unsigned Size;         // Size of bitvector in bits.
37  unsigned Capacity;     // Number of BitWords allocated in the Bits array.
38
39public:
40  typedef unsigned size_type;
41  // Encapsulation of a single bit.
42  class reference {
43    friend class BitVector;
44
45    BitWord *WordRef;
46    unsigned BitPos;
47
48    reference();  // Undefined
49
50  public:
51    reference(BitVector &b, unsigned Idx) {
52      WordRef = &b.Bits[Idx / BITWORD_SIZE];
53      BitPos = Idx % BITWORD_SIZE;
54    }
55
56    reference(const reference&) = default;
57
58    reference &operator=(reference t) {
59      *this = bool(t);
60      return *this;
61    }
62
63    reference& operator=(bool t) {
64      if (t)
65        *WordRef |= BitWord(1) << BitPos;
66      else
67        *WordRef &= ~(BitWord(1) << BitPos);
68      return *this;
69    }
70
71    operator bool() const {
72      return ((*WordRef) & (BitWord(1) << BitPos)) != 0;
73    }
74  };
75
76
77  /// BitVector default ctor - Creates an empty bitvector.
78  BitVector() : Size(0), Capacity(0) {
79    Bits = nullptr;
80  }
81
82  /// BitVector ctor - Creates a bitvector of specified number of bits. All
83  /// bits are initialized to the specified value.
84  explicit BitVector(unsigned s, bool t = false) : Size(s) {
85    Capacity = NumBitWords(s);
86    Bits = (BitWord *)std::malloc(Capacity * sizeof(BitWord));
87    init_words(Bits, Capacity, t);
88    if (t)
89      clear_unused_bits();
90  }
91
92  /// BitVector copy ctor.
93  BitVector(const BitVector &RHS) : Size(RHS.size()) {
94    if (Size == 0) {
95      Bits = nullptr;
96      Capacity = 0;
97      return;
98    }
99
100    Capacity = NumBitWords(RHS.size());
101    Bits = (BitWord *)std::malloc(Capacity * sizeof(BitWord));
102    std::memcpy(Bits, RHS.Bits, Capacity * sizeof(BitWord));
103  }
104
105  BitVector(BitVector &&RHS)
106    : Bits(RHS.Bits), Size(RHS.Size), Capacity(RHS.Capacity) {
107    RHS.Bits = nullptr;
108    RHS.Size = RHS.Capacity = 0;
109  }
110
111  ~BitVector() {
112    std::free(Bits);
113  }
114
115  /// empty - Tests whether there are no bits in this bitvector.
116  bool empty() const { return Size == 0; }
117
118  /// size - Returns the number of bits in this bitvector.
119  size_type size() const { return Size; }
120
121  /// count - Returns the number of bits which are set.
122  size_type count() const {
123    unsigned NumBits = 0;
124    for (unsigned i = 0; i < NumBitWords(size()); ++i)
125      NumBits += countPopulation(Bits[i]);
126    return NumBits;
127  }
128
129  /// any - Returns true if any bit is set.
130  bool any() const {
131    for (unsigned i = 0; i < NumBitWords(size()); ++i)
132      if (Bits[i] != 0)
133        return true;
134    return false;
135  }
136
137  /// all - Returns true if all bits are set.
138  bool all() const {
139    for (unsigned i = 0; i < Size / BITWORD_SIZE; ++i)
140      if (Bits[i] != ~0UL)
141        return false;
142
143    // If bits remain check that they are ones. The unused bits are always zero.
144    if (unsigned Remainder = Size % BITWORD_SIZE)
145      return Bits[Size / BITWORD_SIZE] == (1UL << Remainder) - 1;
146
147    return true;
148  }
149
150  /// none - Returns true if none of the bits are set.
151  bool none() const {
152    return !any();
153  }
154
155  /// find_first - Returns the index of the first set bit, -1 if none
156  /// of the bits are set.
157  int find_first() const {
158    for (unsigned i = 0; i < NumBitWords(size()); ++i)
159      if (Bits[i] != 0)
160        return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
161    return -1;
162  }
163
164  /// find_next - Returns the index of the next set bit following the
165  /// "Prev" bit. Returns -1 if the next set bit is not found.
166  int find_next(unsigned Prev) const {
167    ++Prev;
168    if (Prev >= Size)
169      return -1;
170
171    unsigned WordPos = Prev / BITWORD_SIZE;
172    unsigned BitPos = Prev % BITWORD_SIZE;
173    BitWord Copy = Bits[WordPos];
174    // Mask off previous bits.
175    Copy &= ~0UL << BitPos;
176
177    if (Copy != 0)
178      return WordPos * BITWORD_SIZE + countTrailingZeros(Copy);
179
180    // Check subsequent words.
181    for (unsigned i = WordPos+1; i < NumBitWords(size()); ++i)
182      if (Bits[i] != 0)
183        return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
184    return -1;
185  }
186
187  /// clear - Clear all bits.
188  void clear() {
189    Size = 0;
190  }
191
192  /// resize - Grow or shrink the bitvector.
193  void resize(unsigned N, bool t = false) {
194    if (N > Capacity * BITWORD_SIZE) {
195      unsigned OldCapacity = Capacity;
196      grow(N);
197      init_words(&Bits[OldCapacity], (Capacity-OldCapacity), t);
198    }
199
200    // Set any old unused bits that are now included in the BitVector. This
201    // may set bits that are not included in the new vector, but we will clear
202    // them back out below.
203    if (N > Size)
204      set_unused_bits(t);
205
206    // Update the size, and clear out any bits that are now unused
207    unsigned OldSize = Size;
208    Size = N;
209    if (t || N < OldSize)
210      clear_unused_bits();
211  }
212
213  void reserve(unsigned N) {
214    if (N > Capacity * BITWORD_SIZE)
215      grow(N);
216  }
217
218  // Set, reset, flip
219  BitVector &set() {
220    init_words(Bits, Capacity, true);
221    clear_unused_bits();
222    return *this;
223  }
224
225  BitVector &set(unsigned Idx) {
226    assert(Bits && "Bits never allocated");
227    Bits[Idx / BITWORD_SIZE] |= BitWord(1) << (Idx % BITWORD_SIZE);
228    return *this;
229  }
230
231  /// set - Efficiently set a range of bits in [I, E)
232  BitVector &set(unsigned I, unsigned E) {
233    assert(I <= E && "Attempted to set backwards range!");
234    assert(E <= size() && "Attempted to set out-of-bounds range!");
235
236    if (I == E) return *this;
237
238    if (I / BITWORD_SIZE == E / BITWORD_SIZE) {
239      BitWord EMask = 1UL << (E % BITWORD_SIZE);
240      BitWord IMask = 1UL << (I % BITWORD_SIZE);
241      BitWord Mask = EMask - IMask;
242      Bits[I / BITWORD_SIZE] |= Mask;
243      return *this;
244    }
245
246    BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE);
247    Bits[I / BITWORD_SIZE] |= PrefixMask;
248    I = alignTo(I, BITWORD_SIZE);
249
250    for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE)
251      Bits[I / BITWORD_SIZE] = ~0UL;
252
253    BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1;
254    if (I < E)
255      Bits[I / BITWORD_SIZE] |= PostfixMask;
256
257    return *this;
258  }
259
260  BitVector &reset() {
261    init_words(Bits, Capacity, false);
262    return *this;
263  }
264
265  BitVector &reset(unsigned Idx) {
266    Bits[Idx / BITWORD_SIZE] &= ~(BitWord(1) << (Idx % BITWORD_SIZE));
267    return *this;
268  }
269
270  /// reset - Efficiently reset a range of bits in [I, E)
271  BitVector &reset(unsigned I, unsigned E) {
272    assert(I <= E && "Attempted to reset backwards range!");
273    assert(E <= size() && "Attempted to reset out-of-bounds range!");
274
275    if (I == E) return *this;
276
277    if (I / BITWORD_SIZE == E / BITWORD_SIZE) {
278      BitWord EMask = 1UL << (E % BITWORD_SIZE);
279      BitWord IMask = 1UL << (I % BITWORD_SIZE);
280      BitWord Mask = EMask - IMask;
281      Bits[I / BITWORD_SIZE] &= ~Mask;
282      return *this;
283    }
284
285    BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE);
286    Bits[I / BITWORD_SIZE] &= ~PrefixMask;
287    I = alignTo(I, BITWORD_SIZE);
288
289    for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE)
290      Bits[I / BITWORD_SIZE] = 0UL;
291
292    BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1;
293    if (I < E)
294      Bits[I / BITWORD_SIZE] &= ~PostfixMask;
295
296    return *this;
297  }
298
299  BitVector &flip() {
300    for (unsigned i = 0; i < NumBitWords(size()); ++i)
301      Bits[i] = ~Bits[i];
302    clear_unused_bits();
303    return *this;
304  }
305
306  BitVector &flip(unsigned Idx) {
307    Bits[Idx / BITWORD_SIZE] ^= BitWord(1) << (Idx % BITWORD_SIZE);
308    return *this;
309  }
310
311  // Indexing.
312  reference operator[](unsigned Idx) {
313    assert (Idx < Size && "Out-of-bounds Bit access.");
314    return reference(*this, Idx);
315  }
316
317  bool operator[](unsigned Idx) const {
318    assert (Idx < Size && "Out-of-bounds Bit access.");
319    BitWord Mask = BitWord(1) << (Idx % BITWORD_SIZE);
320    return (Bits[Idx / BITWORD_SIZE] & Mask) != 0;
321  }
322
323  bool test(unsigned Idx) const {
324    return (*this)[Idx];
325  }
326
327  /// Test if any common bits are set.
328  bool anyCommon(const BitVector &RHS) const {
329    unsigned ThisWords = NumBitWords(size());
330    unsigned RHSWords  = NumBitWords(RHS.size());
331    for (unsigned i = 0, e = std::min(ThisWords, RHSWords); i != e; ++i)
332      if (Bits[i] & RHS.Bits[i])
333        return true;
334    return false;
335  }
336
337  // Comparison operators.
338  bool operator==(const BitVector &RHS) const {
339    unsigned ThisWords = NumBitWords(size());
340    unsigned RHSWords  = NumBitWords(RHS.size());
341    unsigned i;
342    for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
343      if (Bits[i] != RHS.Bits[i])
344        return false;
345
346    // Verify that any extra words are all zeros.
347    if (i != ThisWords) {
348      for (; i != ThisWords; ++i)
349        if (Bits[i])
350          return false;
351    } else if (i != RHSWords) {
352      for (; i != RHSWords; ++i)
353        if (RHS.Bits[i])
354          return false;
355    }
356    return true;
357  }
358
359  bool operator!=(const BitVector &RHS) const {
360    return !(*this == RHS);
361  }
362
363  /// Intersection, union, disjoint union.
364  BitVector &operator&=(const BitVector &RHS) {
365    unsigned ThisWords = NumBitWords(size());
366    unsigned RHSWords  = NumBitWords(RHS.size());
367    unsigned i;
368    for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
369      Bits[i] &= RHS.Bits[i];
370
371    // Any bits that are just in this bitvector become zero, because they aren't
372    // in the RHS bit vector.  Any words only in RHS are ignored because they
373    // are already zero in the LHS.
374    for (; i != ThisWords; ++i)
375      Bits[i] = 0;
376
377    return *this;
378  }
379
380  /// reset - Reset bits that are set in RHS. Same as *this &= ~RHS.
381  BitVector &reset(const BitVector &RHS) {
382    unsigned ThisWords = NumBitWords(size());
383    unsigned RHSWords  = NumBitWords(RHS.size());
384    unsigned i;
385    for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
386      Bits[i] &= ~RHS.Bits[i];
387    return *this;
388  }
389
390  /// test - Check if (This - RHS) is zero.
391  /// This is the same as reset(RHS) and any().
392  bool test(const BitVector &RHS) const {
393    unsigned ThisWords = NumBitWords(size());
394    unsigned RHSWords  = NumBitWords(RHS.size());
395    unsigned i;
396    for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
397      if ((Bits[i] & ~RHS.Bits[i]) != 0)
398        return true;
399
400    for (; i != ThisWords ; ++i)
401      if (Bits[i] != 0)
402        return true;
403
404    return false;
405  }
406
407  BitVector &operator|=(const BitVector &RHS) {
408    if (size() < RHS.size())
409      resize(RHS.size());
410    for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i)
411      Bits[i] |= RHS.Bits[i];
412    return *this;
413  }
414
415  BitVector &operator^=(const BitVector &RHS) {
416    if (size() < RHS.size())
417      resize(RHS.size());
418    for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i)
419      Bits[i] ^= RHS.Bits[i];
420    return *this;
421  }
422
423  // Assignment operator.
424  const BitVector &operator=(const BitVector &RHS) {
425    if (this == &RHS) return *this;
426
427    Size = RHS.size();
428    unsigned RHSWords = NumBitWords(Size);
429    if (Size <= Capacity * BITWORD_SIZE) {
430      if (Size)
431        std::memcpy(Bits, RHS.Bits, RHSWords * sizeof(BitWord));
432      clear_unused_bits();
433      return *this;
434    }
435
436    // Grow the bitvector to have enough elements.
437    Capacity = RHSWords;
438    assert(Capacity > 0 && "negative capacity?");
439    BitWord *NewBits = (BitWord *)std::malloc(Capacity * sizeof(BitWord));
440    std::memcpy(NewBits, RHS.Bits, Capacity * sizeof(BitWord));
441
442    // Destroy the old bits.
443    std::free(Bits);
444    Bits = NewBits;
445
446    return *this;
447  }
448
449  const BitVector &operator=(BitVector &&RHS) {
450    if (this == &RHS) return *this;
451
452    std::free(Bits);
453    Bits = RHS.Bits;
454    Size = RHS.Size;
455    Capacity = RHS.Capacity;
456
457    RHS.Bits = nullptr;
458    RHS.Size = RHS.Capacity = 0;
459
460    return *this;
461  }
462
463  void swap(BitVector &RHS) {
464    std::swap(Bits, RHS.Bits);
465    std::swap(Size, RHS.Size);
466    std::swap(Capacity, RHS.Capacity);
467  }
468
469  //===--------------------------------------------------------------------===//
470  // Portable bit mask operations.
471  //===--------------------------------------------------------------------===//
472  //
473  // These methods all operate on arrays of uint32_t, each holding 32 bits. The
474  // fixed word size makes it easier to work with literal bit vector constants
475  // in portable code.
476  //
477  // The LSB in each word is the lowest numbered bit.  The size of a portable
478  // bit mask is always a whole multiple of 32 bits.  If no bit mask size is
479  // given, the bit mask is assumed to cover the entire BitVector.
480
481  /// setBitsInMask - Add '1' bits from Mask to this vector. Don't resize.
482  /// This computes "*this |= Mask".
483  void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
484    applyMask<true, false>(Mask, MaskWords);
485  }
486
487  /// clearBitsInMask - Clear any bits in this vector that are set in Mask.
488  /// Don't resize. This computes "*this &= ~Mask".
489  void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
490    applyMask<false, false>(Mask, MaskWords);
491  }
492
493  /// setBitsNotInMask - Add a bit to this vector for every '0' bit in Mask.
494  /// Don't resize.  This computes "*this |= ~Mask".
495  void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
496    applyMask<true, true>(Mask, MaskWords);
497  }
498
499  /// clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask.
500  /// Don't resize.  This computes "*this &= Mask".
501  void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
502    applyMask<false, true>(Mask, MaskWords);
503  }
504
505private:
506  unsigned NumBitWords(unsigned S) const {
507    return (S + BITWORD_SIZE-1) / BITWORD_SIZE;
508  }
509
510  // Set the unused bits in the high words.
511  void set_unused_bits(bool t = true) {
512    //  Set high words first.
513    unsigned UsedWords = NumBitWords(Size);
514    if (Capacity > UsedWords)
515      init_words(&Bits[UsedWords], (Capacity-UsedWords), t);
516
517    //  Then set any stray high bits of the last used word.
518    unsigned ExtraBits = Size % BITWORD_SIZE;
519    if (ExtraBits) {
520      BitWord ExtraBitMask = ~0UL << ExtraBits;
521      if (t)
522        Bits[UsedWords-1] |= ExtraBitMask;
523      else
524        Bits[UsedWords-1] &= ~ExtraBitMask;
525    }
526  }
527
528  // Clear the unused bits in the high words.
529  void clear_unused_bits() {
530    set_unused_bits(false);
531  }
532
533  void grow(unsigned NewSize) {
534    Capacity = std::max(NumBitWords(NewSize), Capacity * 2);
535    assert(Capacity > 0 && "realloc-ing zero space");
536    Bits = (BitWord *)std::realloc(Bits, Capacity * sizeof(BitWord));
537
538    clear_unused_bits();
539  }
540
541  void init_words(BitWord *B, unsigned NumWords, bool t) {
542    memset(B, 0 - (int)t, NumWords*sizeof(BitWord));
543  }
544
545  template<bool AddBits, bool InvertMask>
546  void applyMask(const uint32_t *Mask, unsigned MaskWords) {
547    static_assert(BITWORD_SIZE % 32 == 0, "Unsupported BitWord size.");
548    MaskWords = std::min(MaskWords, (size() + 31) / 32);
549    const unsigned Scale = BITWORD_SIZE / 32;
550    unsigned i;
551    for (i = 0; MaskWords >= Scale; ++i, MaskWords -= Scale) {
552      BitWord BW = Bits[i];
553      // This inner loop should unroll completely when BITWORD_SIZE > 32.
554      for (unsigned b = 0; b != BITWORD_SIZE; b += 32) {
555        uint32_t M = *Mask++;
556        if (InvertMask) M = ~M;
557        if (AddBits) BW |=   BitWord(M) << b;
558        else         BW &= ~(BitWord(M) << b);
559      }
560      Bits[i] = BW;
561    }
562    for (unsigned b = 0; MaskWords; b += 32, --MaskWords) {
563      uint32_t M = *Mask++;
564      if (InvertMask) M = ~M;
565      if (AddBits) Bits[i] |=   BitWord(M) << b;
566      else         Bits[i] &= ~(BitWord(M) << b);
567    }
568    if (AddBits)
569      clear_unused_bits();
570  }
571
572public:
573  /// Return the size (in bytes) of the bit vector.
574  size_t getMemorySize() const { return Capacity * sizeof(BitWord); }
575};
576
577static inline size_t capacity_in_bytes(const BitVector &X) {
578  return X.getMemorySize();
579}
580
581} // end namespace llvm
582
583namespace std {
584  /// Implement std::swap in terms of BitVector swap.
585  inline void
586  swap(llvm::BitVector &LHS, llvm::BitVector &RHS) {
587    LHS.swap(RHS);
588  }
589} // end namespace std
590
591#endif // LLVM_ADT_BITVECTOR_H
592