diff options
author | Owen Anderson <resistor@mac.com> | 2012-10-15 22:05:27 +0000 |
---|---|---|
committer | Owen Anderson <resistor@mac.com> | 2012-10-15 22:05:27 +0000 |
commit | 3a1c35afbd02b012690c35ec827424c27792ec3f (patch) | |
tree | 53d42d594e371ca2dd5fd6e4ea8bcf8321e902c1 /include | |
parent | fb9ebbf236974beac31705eaeb9f50ab585af6ab (diff) | |
download | llvm-3a1c35afbd02b012690c35ec827424c27792ec3f.tar.gz llvm-3a1c35afbd02b012690c35ec827424c27792ec3f.tar.bz2 llvm-3a1c35afbd02b012690c35ec827424c27792ec3f.tar.xz |
Add range-based set()/reset() to BitVector. These allow fast setting/resetting of ranges of bits, particularly useful when dealing with very large BitVector's.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165984 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'include')
-rw-r--r-- | include/llvm/ADT/BitVector.h | 56 | ||||
-rw-r--r-- | include/llvm/ADT/SmallBitVector.h | 30 |
2 files changed, 86 insertions, 0 deletions
diff --git a/include/llvm/ADT/BitVector.h b/include/llvm/ADT/BitVector.h index 26ec346b18..4523828d45 100644 --- a/include/llvm/ADT/BitVector.h +++ b/include/llvm/ADT/BitVector.h @@ -237,6 +237,34 @@ public: return *this; } + /// set - Efficiently set a range of bits in [I, E) + BitVector &set(unsigned I, unsigned E) { + assert(I <= E && "Attempted to set backwards range!"); + assert(E <= size() && "Attempted to set out-of-bounds range!"); + + if (I == E) return *this; + + if (I / BITWORD_SIZE == (E-1) / BITWORD_SIZE) { + BitWord EMask = 1 << (E % BITWORD_SIZE); + BitWord IMask = 1 << (I % BITWORD_SIZE); + BitWord Mask = EMask - IMask; + Bits[I / BITWORD_SIZE] |= Mask; + return *this; + } + + BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE); + Bits[I / BITWORD_SIZE] |= PrefixMask; + I = RoundUpToAlignment(I, BITWORD_SIZE); + + for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE) + Bits[I / BITWORD_SIZE] = ~0UL; + + BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1; + Bits[I / BITWORD_SIZE] |= PostfixMask; + + return *this; + } + BitVector &reset() { init_words(Bits, Capacity, false); return *this; @@ -247,6 +275,34 @@ public: return *this; } + /// reset - Efficiently reset a range of bits in [I, E) + BitVector &reset(unsigned I, unsigned E) { + assert(I <= E && "Attempted to reset backwards range!"); + assert(E <= size() && "Attempted to reset out-of-bounds range!"); + + if (I == E) return *this; + + if (I / BITWORD_SIZE == (E-1) / BITWORD_SIZE) { + BitWord EMask = 1 << (E % BITWORD_SIZE); + BitWord IMask = 1 << (I % BITWORD_SIZE); + BitWord Mask = EMask - IMask; + Bits[I / BITWORD_SIZE] &= ~Mask; + return *this; + } + + BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE); + Bits[I / BITWORD_SIZE] &= ~PrefixMask; + I = RoundUpToAlignment(I, BITWORD_SIZE); + + for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE) + Bits[I / BITWORD_SIZE] = 0UL; + + BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1; + Bits[I / BITWORD_SIZE] &= ~PostfixMask; + + return *this; + } + BitVector &flip() { for (unsigned i = 0; i < NumBitWords(size()); ++i) Bits[i] = ~Bits[i]; diff --git a/include/llvm/ADT/SmallBitVector.h b/include/llvm/ADT/SmallBitVector.h index 7a645e0c72..fba1d12542 100644 --- a/include/llvm/ADT/SmallBitVector.h +++ b/include/llvm/ADT/SmallBitVector.h @@ -300,6 +300,21 @@ public: return *this; } + /// set - Efficiently set a range of bits in [I, E) + SmallBitVector &set(unsigned I, unsigned E) { + assert(I <= E && "Attempted to set backwards range!"); + assert(E <= size() && "Attempted to set out-of-bounds range!"); + if (I == E) return *this; + if (isSmall()) { + uintptr_t EMask = 1 << E; + uintptr_t IMask = 1 << I; + uintptr_t Mask = EMask - IMask; + setSmallBits(getSmallBits() | Mask); + } else + getPointer()->set(I, E); + return *this; + } + SmallBitVector &reset() { if (isSmall()) setSmallBits(0); @@ -316,6 +331,21 @@ public: return *this; } + /// reset - Efficiently reset a range of bits in [I, E) + SmallBitVector &reset(unsigned I, unsigned E) { + assert(I <= E && "Attempted to reset backwards range!"); + assert(E <= size() && "Attempted to reset out-of-bounds range!"); + if (I == E) return *this; + if (isSmall()) { + uintptr_t EMask = 1 << E; + uintptr_t IMask = 1 << I; + uintptr_t Mask = EMask - IMask; + setSmallBits(getSmallBits() & ~Mask); + } else + getPointer()->reset(I, E); + return *this; + } + SmallBitVector &flip() { if (isSmall()) setSmallBits(~getSmallBits()); |