LLVM: llvm::SparseBitVectorElement< ElementSize > Struct Template Reference (original) (raw)
SparseBitVector is an implementation of a bitvector that is sparse by only storing the elements that have non-zero bits set. More...
#include "[llvm/ADT/SparseBitVector.h](SparseBitVector%5F8h%5Fsource.html)"
| Public Types | |
|---|---|
| enum | { BITWORD_SIZE = sizeof(BitWord) * CHAR_BIT , BITWORDS_PER_ELEMENT = (ElementSize + BITWORD_SIZE - 1) / BITWORD_SIZE , BITS_PER_ELEMENT = ElementSize } |
| using | BitWord = unsigned long |
| using | size_type = unsigned |
template<unsigned ElementSize = 128>
struct llvm::SparseBitVectorElement< ElementSize >
SparseBitVector is an implementation of a bitvector that is sparse by only storing the elements that have non-zero bits set.
In order to make this fast for the most common cases, SparseBitVector is implemented as a linked list of SparseBitVectorElements. We maintain a pointer to the last SparseBitVectorElement accessed (in the form of a list iterator), in order to make multiple in-order test/set constant time after the first one is executed. Note that using vectors to store SparseBitVectorElement's does not work out very well because it causes insertion in the middle to take enormous amounts of time with a large amount of bits. Other structures that have better worst cases for insertion in the middle (various balanced trees, etc) do not perform as well in practice as a linked list with this iterator kept up to date. They are also significantly more memory intensive.
Definition at line 42 of file SparseBitVector.h.
◆ BitWord
◆ size_type
◆ anonymous enum
| Enumerator |
|---|
| BITWORD_SIZE |
| BITWORDS_PER_ELEMENT |
| BITS_PER_ELEMENT |
Definition at line 46 of file SparseBitVector.h.
◆ count()
◆ empty()
◆ find_first()
◆ find_last()
◆ find_next()
◆ index()
◆ intersects()
◆ intersectWith()
◆ intersectWithComplement() [1/2]
◆ intersectWithComplement() [2/2]
◆ operator!=()
◆ operator==()
◆ reset()
◆ set()
◆ test()
◆ test_and_set()
◆ unionWith()
◆ word()
The documentation for this struct was generated from the following file:
- include/llvm/ADT/SparseBitVector.h