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