struct SparseBitVectorElement

Declaration

template <unsigned int ElementSize = 128>
struct SparseBitVectorElement { /* full declaration omitted */ };

Description

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.

Declared at: llvm/include/llvm/ADT/SparseBitVector.h:42

Templates

unsigned int ElementSize = 128

Member Variables

private unsigned int ElementIndex
private llvm::SparseBitVectorElement::BitWord [BITWORDS_PER_ELEMENT] Bits

Method Overview

Methods

SparseBitVectorElement<ElementSize>(
    unsigned int Idx)

Declared at: llvm/include/llvm/ADT/SparseBitVector.h:63

Parameters

unsigned int Idx

SparseBitVectorElement<ElementSize>()

Declared at: llvm/include/llvm/ADT/SparseBitVector.h:57

llvm::SparseBitVectorElement::size_type count()
    const

Declared at: llvm/include/llvm/ADT/SparseBitVector.h:120

bool empty() const

Declared at: llvm/include/llvm/ADT/SparseBitVector.h:92

int find_first() const

Description

find_first - Returns the index of the first set bit.

Declared at: llvm/include/llvm/ADT/SparseBitVector.h:128

int find_last() const

Description

find_last - Returns the index of the last set bit.

Declared at: llvm/include/llvm/ADT/SparseBitVector.h:136

int find_next(unsigned int Curr) const

Description

find_next - Returns the index of the next set bit starting from the "Curr" bit. Returns -1 if the next set bit is not found.

Declared at: llvm/include/llvm/ADT/SparseBitVector.h:148

Parameters

unsigned int Curr

unsigned int index() const

Declared at: llvm/include/llvm/ADT/SparseBitVector.h:88

bool intersectWith(const SparseBitVectorElement<
                       ElementSize>& RHS,
                   bool& BecameZero)

Declared at: llvm/include/llvm/ADT/SparseBitVector.h:195

Parameters

const SparseBitVectorElement<ElementSize>& RHS
bool& BecameZero

bool intersectWithComplement(
    const SparseBitVectorElement<ElementSize>&
        RHS,
    bool& BecameZero)

Declared at: llvm/include/llvm/ADT/SparseBitVector.h:218

Parameters

const SparseBitVectorElement<ElementSize>& RHS
bool& BecameZero

void intersectWithComplement(
    const SparseBitVectorElement<ElementSize>&
        RHS1,
    const SparseBitVectorElement<ElementSize>&
        RHS2,
    bool& BecameZero)

Declared at: llvm/include/llvm/ADT/SparseBitVector.h:240

Parameters

const SparseBitVectorElement<ElementSize>& RHS1
const SparseBitVectorElement<ElementSize>& RHS2
bool& BecameZero

bool intersects(
    const SparseBitVectorElement<ElementSize>&
        RHS) const

Declared at: llvm/include/llvm/ADT/SparseBitVector.h:185

Parameters

const SparseBitVectorElement<ElementSize>& RHS

void reset(unsigned int Idx)

Declared at: llvm/include/llvm/ADT/SparseBitVector.h:112

Parameters

unsigned int Idx

void set(unsigned int Idx)

Declared at: llvm/include/llvm/ADT/SparseBitVector.h:99

Parameters

unsigned int Idx

bool test(unsigned int Idx) const

Declared at: llvm/include/llvm/ADT/SparseBitVector.h:116

Parameters

unsigned int Idx

bool test_and_set(unsigned int Idx)

Declared at: llvm/include/llvm/ADT/SparseBitVector.h:103

Parameters

unsigned int Idx

bool unionWith(
    const SparseBitVectorElement<ElementSize>&
        RHS)

Declared at: llvm/include/llvm/ADT/SparseBitVector.h:172

Parameters

const SparseBitVectorElement<ElementSize>& RHS

llvm::SparseBitVectorElement::BitWord word(
    unsigned int Idx) const

Declared at: llvm/include/llvm/ADT/SparseBitVector.h:83

Parameters

unsigned int Idx