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:41

Templates

unsigned int ElementSize = 128

Method Overview

• public SparseBitVectorElement<ElementSize>(unsigned int Idx)
• public llvm::SparseBitVectorElement::size_type count() const
• public bool empty() const
• public int find_first() const
• public int find_last() const
• public int find_next(unsigned int Curr) const
• public unsigned int index() const
• public bool intersectWith(const SparseBitVectorElement<ElementSize> & RHS, bool & BecameZero)
• public void intersectWithComplement(const SparseBitVectorElement<ElementSize> & RHS1, const SparseBitVectorElement<ElementSize> & RHS2, bool & BecameZero)
• public bool intersectWithComplement(const SparseBitVectorElement<ElementSize> & RHS, bool & BecameZero)
• public bool intersects(const SparseBitVectorElement<ElementSize> & RHS) const
• public void reset(unsigned int Idx)
• public void set(unsigned int Idx)
• public bool test(unsigned int Idx) const
• public bool test_and_set(unsigned int Idx)
• public bool unionWith(const SparseBitVectorElement<ElementSize> & RHS)
• public llvm::SparseBitVectorElement::BitWord word(unsigned int Idx) const

Methods

¶SparseBitVectorElement<ElementSize>(
    unsigned int Idx)

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

Parameters

unsigned int Idx

¶llvm::SparseBitVectorElement::size_type count()
    const

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

¶bool empty() const

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

¶int find_first() const

Description

find_first - Returns the index of the first set bit.

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

¶int find_last() const

Description

find_last - Returns the index of the last set bit.

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

¶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:147

Parameters

unsigned int Curr

¶unsigned int index() const

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

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

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

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:239

Parameters

const SparseBitVectorElement<ElementSize>& RHS1

const SparseBitVectorElement<ElementSize>& RHS2

bool& BecameZero

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

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

Parameters

const SparseBitVectorElement<ElementSize>& RHS

bool& BecameZero

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

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

Parameters

const SparseBitVectorElement<ElementSize>& RHS

¶void reset(unsigned int Idx)

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

Parameters

unsigned int Idx

¶void set(unsigned int Idx)

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

Parameters

unsigned int Idx

¶bool test(unsigned int Idx) const

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

Parameters

unsigned int Idx

¶bool test_and_set(unsigned int Idx)

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

Parameters

unsigned int Idx

¶bool unionWith(
    const SparseBitVectorElement<ElementSize>&
        RHS)

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

Parameters

const SparseBitVectorElement<ElementSize>& RHS

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

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

Parameters

unsigned int Idx