BitVector.h revision ae9f3a3b7c915f725aef5a7250e88eaeddda03c6 
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 <cstdlib>
21#include <cstring>
22
23namespace llvm {
24
25class BitVector {
26  typedef unsigned long BitWord;
27
28  enum { BITWORD_SIZE = sizeof(BitWord) * 8 };
29
30  BitWord  *Bits;        // Actual bits.
31  unsigned Size;         // Size of bitvector in bits.
32  unsigned Capacity;     // Size of allocated memory in BitWord.
33
34public:
35  // Encapsulation of a single bit.
36  class reference {
37    friend class BitVector;
38
39    BitWord *WordRef;
40    unsigned BitPos;
41
42    reference();  // Undefined
43
44  public:
45    reference(BitVector &b, unsigned Idx) {
46      WordRef = &b.Bits[Idx / BITWORD_SIZE];
47      BitPos = Idx % BITWORD_SIZE;
48    }
49
50    ~reference() {}
51
52    reference& operator=(bool t) {
53      if (t)
54        *WordRef |= 1L << BitPos;
55      else
56        *WordRef &= ~(1L << BitPos);
57      return *this;
58    }
59
60    operator bool() const {
61      return ((*WordRef) & (1L << BitPos)) ? true : false;
62    }
63  };
64
65
66  /// BitVector default ctor - Creates an empty bitvector.
67  BitVector() : Size(0), Capacity(0) {
68    Bits = NULL;
69  }
70
71  /// BitVector ctor - Creates a bitvector of specified number of bits. All
72  /// bits are initialized to the specified value.
73  explicit BitVector(unsigned s, bool t = false) : Size(s) {
74    Capacity = NumBitWords(s);
75    Bits = new BitWord[Capacity];
76    init_words(Bits, Capacity, t);
77    if (t)
78      clear_unused_bits();
79  }
80
81  /// BitVector copy ctor.
82  BitVector(const BitVector &RHS) : Size(RHS.size()) {
83    if (Size == 0) {
84      Bits = NULL;
85      Capacity = 0;
86      return;
87    }
88
89    Capacity = NumBitWords(RHS.size());
90    Bits = new BitWord[Capacity];
91    std::copy(RHS.Bits, &RHS.Bits[Capacity], Bits);
92  }
93
94  ~BitVector() {
95    delete[] Bits;
96  }
97
98  /// size - Returns the number of bits in this bitvector.
99  unsigned size() const { return Size; }
100
101  /// count - Returns the number of bits which are set.
102  unsigned count() const {
103    unsigned NumBits = 0;
104    for (unsigned i = 0; i < NumBitWords(size()); ++i)
105      if (sizeof(BitWord) == 4)
106        NumBits += CountPopulation_32(Bits[i]);
107      else if (sizeof(BitWord) == 8)
108        NumBits += CountPopulation_64(Bits[i]);
109      else
110        assert(0 && "Unsupported!");
111    return NumBits;
112  }
113
114  /// any - Returns true if any bit is set.
115  bool any() const {
116    for (unsigned i = 0; i < NumBitWords(size()); ++i)
117      if (Bits[i] != 0)
118        return true;
119    return false;
120  }
121
122  /// none - Returns true if none of the bits are set.
123  bool none() const {
124    return !any();
125  }
126
127  /// find_first - Returns the index of the first set bit, -1 if none
128  /// of the bits are set.
129  int find_first() const {
130    for (unsigned i = 0; i < NumBitWords(size()); ++i)
131      if (Bits[i] != 0) {
132        if (sizeof(BitWord) == 4)
133          return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]);
134        else if (sizeof(BitWord) == 8)
135          return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]);
136        else
137          assert(0 && "Unsupported!");
138      }
139    return -1;
140  }
141
142  /// find_next - Returns the index of the next set bit following the
143  /// "Prev" bit. Returns -1 if the next set bit is not found.
144  int find_next(unsigned Prev) const {
145    ++Prev;
146    if (Prev >= Size)
147      return -1;
148
149    unsigned WordPos = Prev / BITWORD_SIZE;
150    unsigned BitPos = Prev % BITWORD_SIZE;
151    BitWord Copy = Bits[WordPos];
152    // Mask off previous bits.
153    Copy &= ~0L << BitPos;
154
155    if (Copy != 0) {
156      if (sizeof(BitWord) == 4)
157        return WordPos * BITWORD_SIZE + CountTrailingZeros_32(Copy);
158      else if (sizeof(BitWord) == 8)
159        return WordPos * BITWORD_SIZE + CountTrailingZeros_64(Copy);
160      else
161        assert(0 && "Unsupported!");
162    }
163
164    // Check subsequent words.
165    for (unsigned i = WordPos+1; i < NumBitWords(size()); ++i)
166      if (Bits[i] != 0) {
167        if (sizeof(BitWord) == 4)
168          return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]);
169        else if (sizeof(BitWord) == 8)
170          return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]);
171        else
172          assert(0 && "Unsupported!");
173      }
174    return -1;
175  }
176
177  /// clear - Clear all bits.
178  void clear() {
179    Size = 0;
180  }
181
182  /// resize - Grow or shrink the bitvector.
183  void resize(unsigned N, bool t = false) {
184    if (N > Capacity * BITWORD_SIZE) {
185      unsigned OldCapacity = Capacity;
186      grow(N);
187      init_words(&Bits[OldCapacity], (Capacity-OldCapacity), t);
188    }
189
190    // Set any old unused bits that are now included in the BitVector. This
191    // may set bits that are not included in the new vector, but we will clear
192    // them back out below.
193    if (N > Size)
194      set_unused_bits(t);
195
196    // Update the size, and clear out any bits that are now unused
197    unsigned OldSize = Size;
198    Size = N;
199    if (t || N < OldSize)
200      clear_unused_bits();
201  }
202
203  void reserve(unsigned N) {
204    if (N > Capacity * BITWORD_SIZE)
205      grow(N);
206  }
207
208  // Set, reset, flip
209  BitVector &set() {
210    init_words(Bits, Capacity, true);
211    clear_unused_bits();
212    return *this;
213  }
214
215  BitVector &set(unsigned Idx) {
216    Bits[Idx / BITWORD_SIZE] |= 1L << (Idx % BITWORD_SIZE);
217    return *this;
218  }
219
220  BitVector &reset() {
221    init_words(Bits, Capacity, false);
222    return *this;
223  }
224
225  BitVector &reset(unsigned Idx) {
226    Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE));
227    return *this;
228  }
229
230  BitVector &flip() {
231    for (unsigned i = 0; i < NumBitWords(size()); ++i)
232      Bits[i] = ~Bits[i];
233    clear_unused_bits();
234    return *this;
235  }
236
237  BitVector &flip(unsigned Idx) {
238    Bits[Idx / BITWORD_SIZE] ^= 1L << (Idx % BITWORD_SIZE);
239    return *this;
240  }
241
242  // No argument flip.
243  BitVector operator~() const {
244    return BitVector(*this).flip();
245  }
246
247  // Indexing.
248  reference operator[](unsigned Idx) {
249    assert (Idx < Size && "Out-of-bounds Bit access.");
250    return reference(*this, Idx);
251  }
252
253  bool operator[](unsigned Idx) const {
254    assert (Idx < Size && "Out-of-bounds Bit access.");
255    BitWord Mask = 1L << (Idx % BITWORD_SIZE);
256    return (Bits[Idx / BITWORD_SIZE] & Mask) != 0;
257  }
258
259  bool test(unsigned Idx) const {
260    return (*this)[Idx];
261  }
262
263  // Comparison operators.
264  bool operator==(const BitVector &RHS) const {
265    unsigned ThisWords = NumBitWords(size());
266    unsigned RHSWords  = NumBitWords(RHS.size());
267    unsigned i;
268    for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
269      if (Bits[i] != RHS.Bits[i])
270        return false;
271
272    // Verify that any extra words are all zeros.
273    if (i != ThisWords) {
274      for (; i != ThisWords; ++i)
275        if (Bits[i])
276          return false;
277    } else if (i != RHSWords) {
278      for (; i != RHSWords; ++i)
279        if (RHS.Bits[i])
280          return false;
281    }
282    return true;
283  }
284
285  bool operator!=(const BitVector &RHS) const {
286    return !(*this == RHS);
287  }
288
289  // Intersection, union, disjoint union.
290  BitVector operator&=(const BitVector &RHS) {
291    unsigned ThisWords = NumBitWords(size());
292    unsigned RHSWords  = NumBitWords(RHS.size());
293    unsigned i;
294    for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
295      Bits[i] &= RHS.Bits[i];
296
297    // Any bits that are just in this bitvector become zero, because they aren't
298    // in the RHS bit vector.  Any words only in RHS are ignored because they
299    // are already zero in the LHS.
300    for (; i != ThisWords; ++i)
301      Bits[i] = 0;
302
303    return *this;
304  }
305
306  BitVector operator|=(const BitVector &RHS) {
307    assert(Size == RHS.Size && "Illegal operation!");
308    for (unsigned i = 0; i < NumBitWords(size()); ++i)
309      Bits[i] |= RHS.Bits[i];
310    return *this;
311  }
312
313  BitVector operator^=(const BitVector &RHS) {
314    assert(Size == RHS.Size && "Illegal operation!");
315    for (unsigned i = 0; i < NumBitWords(size()); ++i)
316      Bits[i] ^= RHS.Bits[i];
317    return *this;
318  }
319
320  // Assignment operator.
321  const BitVector &operator=(const BitVector &RHS) {
322    if (this == &RHS) return *this;
323
324    Size = RHS.size();
325    unsigned RHSWords = NumBitWords(Size);
326    if (Size <= Capacity * BITWORD_SIZE) {
327      std::copy(RHS.Bits, &RHS.Bits[RHSWords], Bits);
328      clear_unused_bits();
329      return *this;
330    }
331
332    // Grow the bitvector to have enough elements.
333    Capacity = RHSWords;
334    BitWord *NewBits = new BitWord[Capacity];
335    std::copy(RHS.Bits, &RHS.Bits[RHSWords], NewBits);
336
337    // Destroy the old bits.
338    delete[] Bits;
339    Bits = NewBits;
340
341    return *this;
342  }
343
344private:
345  unsigned NumBitWords(unsigned S) const {
346    return (S + BITWORD_SIZE-1) / BITWORD_SIZE;
347  }
348
349  // Set the unused bits in the high words.
350  void set_unused_bits(bool t = true) {
351    //  Set high words first.
352    unsigned UsedWords = NumBitWords(Size);
353    if (Capacity > UsedWords)
354      init_words(&Bits[UsedWords], (Capacity-UsedWords), t);
355
356    //  Then set any stray high bits of the last used word.
357    unsigned ExtraBits = Size % BITWORD_SIZE;
358    if (ExtraBits) {
359      Bits[UsedWords-1] &= ~(~0L << ExtraBits);
360      Bits[UsedWords-1] |= (0 - (BitWord)t) << ExtraBits;
361    }
362  }
363
364  // Clear the unused bits in the high words.
365  void clear_unused_bits() {
366    set_unused_bits(false);
367  }
368
369  void grow(unsigned NewSize) {
370    unsigned OldCapacity = Capacity;
371    Capacity = NumBitWords(NewSize);
372    BitWord *NewBits = new BitWord[Capacity];
373
374    // Copy the old bits over.
375    if (OldCapacity != 0)
376      std::copy(Bits, &Bits[OldCapacity], NewBits);
377
378    // Destroy the old bits.
379    delete[] Bits;
380    Bits = NewBits;
381
382    clear_unused_bits();
383  }
384
385  void init_words(BitWord *B, unsigned NumWords, bool t) {
386    memset(B, 0 - (int)t, NumWords*sizeof(BitWord));
387  }
388};
389
390inline BitVector operator&(const BitVector &LHS, const BitVector &RHS) {
391  BitVector Result(LHS);
392  Result &= RHS;
393  return Result;
394}
395
396inline BitVector operator|(const BitVector &LHS, const BitVector &RHS) {
397  BitVector Result(LHS);
398  Result |= RHS;
399  return Result;
400}
401
402inline BitVector operator^(const BitVector &LHS, const BitVector &RHS) {
403  BitVector Result(LHS);
404  Result ^= RHS;
405  return Result;
406}
407
408} // End llvm namespace
409#endif
410