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