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