1 //===- llvm/ADT/BitVector.h - Bit vectors -----------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the BitVector class.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_ADT_BITVECTOR_H
15 #define LLVM_ADT_BITVECTOR_H
17 #include "llvm/Support/MathExtras.h"
28 typedef unsigned long BitWord;
30 enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * CHAR_BIT };
32 static_assert(BITWORD_SIZE == 64 || BITWORD_SIZE == 32,
33 "Unsupported word size");
35 BitWord *Bits; // Actual bits.
36 unsigned Size; // Size of bitvector in bits.
37 unsigned Capacity; // Number of BitWords allocated in the Bits array.
40 typedef unsigned size_type;
41 // Encapsulation of a single bit.
43 friend class BitVector;
48 reference(); // Undefined
51 reference(BitVector &b, unsigned Idx) {
52 WordRef = &b.Bits[Idx / BITWORD_SIZE];
53 BitPos = Idx % BITWORD_SIZE;
56 reference(const reference&) = default;
58 reference &operator=(reference t) {
63 reference& operator=(bool t) {
65 *WordRef |= BitWord(1) << BitPos;
67 *WordRef &= ~(BitWord(1) << BitPos);
71 operator bool() const {
72 return ((*WordRef) & (BitWord(1) << BitPos)) != 0;
77 /// BitVector default ctor - Creates an empty bitvector.
78 BitVector() : Size(0), Capacity(0) {
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);
92 /// BitVector copy ctor.
93 BitVector(const BitVector &RHS) : Size(RHS.size()) {
100 Capacity = NumBitWords(RHS.size());
101 Bits = (BitWord *)std::malloc(Capacity * sizeof(BitWord));
102 std::memcpy(Bits, RHS.Bits, Capacity * sizeof(BitWord));
105 BitVector(BitVector &&RHS)
106 : Bits(RHS.Bits), Size(RHS.Size), Capacity(RHS.Capacity) {
108 RHS.Size = RHS.Capacity = 0;
115 /// empty - Tests whether there are no bits in this bitvector.
116 bool empty() const { return Size == 0; }
118 /// size - Returns the number of bits in this bitvector.
119 size_type size() const { return Size; }
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]);
129 /// any - Returns true if any bit is set.
131 for (unsigned i = 0; i < NumBitWords(size()); ++i)
137 /// all - Returns true if all bits are set.
139 for (unsigned i = 0; i < Size / BITWORD_SIZE; ++i)
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;
150 /// none - Returns true if none of the bits are set.
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)
160 return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
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 {
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;
178 return WordPos * BITWORD_SIZE + countTrailingZeros(Copy);
180 // Check subsequent words.
181 for (unsigned i = WordPos+1; i < NumBitWords(size()); ++i)
183 return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
187 /// clear - Clear all bits.
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;
197 init_words(&Bits[OldCapacity], (Capacity-OldCapacity), t);
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.
206 // Update the size, and clear out any bits that are now unused
207 unsigned OldSize = Size;
209 if (t || N < OldSize)
213 void reserve(unsigned N) {
214 if (N > Capacity * BITWORD_SIZE)
220 init_words(Bits, Capacity, true);
225 BitVector &set(unsigned Idx) {
226 assert(Bits && "Bits never allocated");
227 Bits[Idx / BITWORD_SIZE] |= BitWord(1) << (Idx % BITWORD_SIZE);
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!");
236 if (I == E) return *this;
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;
246 BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE);
247 Bits[I / BITWORD_SIZE] |= PrefixMask;
248 I = alignTo(I, BITWORD_SIZE);
250 for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE)
251 Bits[I / BITWORD_SIZE] = ~0UL;
253 BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1;
255 Bits[I / BITWORD_SIZE] |= PostfixMask;
261 init_words(Bits, Capacity, false);
265 BitVector &reset(unsigned Idx) {
266 Bits[Idx / BITWORD_SIZE] &= ~(BitWord(1) << (Idx % BITWORD_SIZE));
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!");
275 if (I == E) return *this;
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;
285 BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE);
286 Bits[I / BITWORD_SIZE] &= ~PrefixMask;
287 I = alignTo(I, BITWORD_SIZE);
289 for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE)
290 Bits[I / BITWORD_SIZE] = 0UL;
292 BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1;
294 Bits[I / BITWORD_SIZE] &= ~PostfixMask;
300 for (unsigned i = 0; i < NumBitWords(size()); ++i)
306 BitVector &flip(unsigned Idx) {
307 Bits[Idx / BITWORD_SIZE] ^= BitWord(1) << (Idx % BITWORD_SIZE);
312 reference operator[](unsigned Idx) {
313 assert (Idx < Size && "Out-of-bounds Bit access.");
314 return reference(*this, Idx);
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;
323 bool test(unsigned Idx) const {
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])
337 // Comparison operators.
338 bool operator==(const BitVector &RHS) const {
339 unsigned ThisWords = NumBitWords(size());
340 unsigned RHSWords = NumBitWords(RHS.size());
342 for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
343 if (Bits[i] != RHS.Bits[i])
346 // Verify that any extra words are all zeros.
347 if (i != ThisWords) {
348 for (; i != ThisWords; ++i)
351 } else if (i != RHSWords) {
352 for (; i != RHSWords; ++i)
359 bool operator!=(const BitVector &RHS) const {
360 return !(*this == RHS);
363 /// Intersection, union, disjoint union.
364 BitVector &operator&=(const BitVector &RHS) {
365 unsigned ThisWords = NumBitWords(size());
366 unsigned RHSWords = NumBitWords(RHS.size());
368 for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
369 Bits[i] &= RHS.Bits[i];
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)
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());
385 for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
386 Bits[i] &= ~RHS.Bits[i];
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());
396 for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
397 if ((Bits[i] & ~RHS.Bits[i]) != 0)
400 for (; i != ThisWords ; ++i)
407 BitVector &operator|=(const BitVector &RHS) {
408 if (size() < RHS.size())
410 for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i)
411 Bits[i] |= RHS.Bits[i];
415 BitVector &operator^=(const BitVector &RHS) {
416 if (size() < RHS.size())
418 for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i)
419 Bits[i] ^= RHS.Bits[i];
423 // Assignment operator.
424 const BitVector &operator=(const BitVector &RHS) {
425 if (this == &RHS) return *this;
428 unsigned RHSWords = NumBitWords(Size);
429 if (Size <= Capacity * BITWORD_SIZE) {
431 std::memcpy(Bits, RHS.Bits, RHSWords * sizeof(BitWord));
436 // Grow the bitvector to have enough elements.
438 assert(Capacity > 0 && "negative capacity?");
439 BitWord *NewBits = (BitWord *)std::malloc(Capacity * sizeof(BitWord));
440 std::memcpy(NewBits, RHS.Bits, Capacity * sizeof(BitWord));
442 // Destroy the old bits.
449 const BitVector &operator=(BitVector &&RHS) {
450 if (this == &RHS) return *this;
455 Capacity = RHS.Capacity;
458 RHS.Size = RHS.Capacity = 0;
463 void swap(BitVector &RHS) {
464 std::swap(Bits, RHS.Bits);
465 std::swap(Size, RHS.Size);
466 std::swap(Capacity, RHS.Capacity);
469 //===--------------------------------------------------------------------===//
470 // Portable bit mask operations.
471 //===--------------------------------------------------------------------===//
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
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.
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);
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);
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);
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);
506 unsigned NumBitWords(unsigned S) const {
507 return (S + BITWORD_SIZE-1) / BITWORD_SIZE;
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);
517 // Then set any stray high bits of the last used word.
518 unsigned ExtraBits = Size % BITWORD_SIZE;
520 BitWord ExtraBitMask = ~0UL << ExtraBits;
522 Bits[UsedWords-1] |= ExtraBitMask;
524 Bits[UsedWords-1] &= ~ExtraBitMask;
528 // Clear the unused bits in the high words.
529 void clear_unused_bits() {
530 set_unused_bits(false);
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));
541 void init_words(BitWord *B, unsigned NumWords, bool t) {
542 memset(B, 0 - (int)t, NumWords*sizeof(BitWord));
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;
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);
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);
573 /// Return the size (in bytes) of the bit vector.
574 size_t getMemorySize() const { return Capacity * sizeof(BitWord); }
577 static inline size_t capacity_in_bytes(const BitVector &X) {
578 return X.getMemorySize();
581 } // end namespace llvm
584 /// Implement std::swap in terms of BitVector swap.
586 swap(llvm::BitVector &LHS, llvm::BitVector &RHS) {
589 } // end namespace std
591 #endif // LLVM_ADT_BITVECTOR_H