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"

Inheritance diagram for llvm::SparseBitVectorElement< ElementSize >:

[legend]

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

Public Member Functions
	SparseBitVectorElement (unsigned Idx)
bool	operator== (const SparseBitVectorElement &RHS) const
bool	operator!= (const SparseBitVectorElement &RHS) const
BitWord	word (unsigned Idx) const
unsigned	index () const
bool	empty () const
void	set (unsigned Idx)
bool	test_and_set (unsigned Idx)
void	reset (unsigned Idx)
bool	test (unsigned Idx) const
size_type	count () const
int	find_first () const
	find_first - Returns the index of the first set bit.
int	find_last () const
	find_last - Returns the index of the last set bit.
int	find_next (unsigned Curr) const
	find_next - Returns the index of the next set bit starting from the "Curr" bit.
bool	unionWith (const SparseBitVectorElement &RHS)
bool	intersects (const SparseBitVectorElement &RHS) const
bool	intersectWith (const SparseBitVectorElement &RHS, bool &BecameZero)
bool	intersectWithComplement (const SparseBitVectorElement &RHS, bool &BecameZero)
void	intersectWithComplement (const SparseBitVectorElement &RHS1, const SparseBitVectorElement &RHS2, bool &BecameZero)

Detailed Description

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 43 of file SparseBitVector.h.

Member Typedef Documentation

◆ BitWord

template<unsigned ElementSize = 128>

using llvm::SparseBitVectorElement< ElementSize >::BitWord = unsigned long

Definition at line 45 of file SparseBitVector.h.

◆ size_type

template<unsigned ElementSize = 128>

using llvm::SparseBitVectorElement< ElementSize >::size_type = unsigned

Definition at line 46 of file SparseBitVector.h.

Member Enumeration Documentation

◆ anonymous enum

template<unsigned ElementSize = 128>

anonymous enum

Enumerator
BITWORD_SIZE
BITWORDS_PER_ELEMENT
BITS_PER_ELEMENT

Definition at line 47 of file SparseBitVector.h.

Constructor & Destructor Documentation

◆ SparseBitVectorElement()

template<unsigned ElementSize = 128>

llvm::SparseBitVectorElement< ElementSize >::SparseBitVectorElement ( unsigned Idx )

inlineexplicit

Definition at line 64 of file SparseBitVector.h.

References BITWORDS_PER_ELEMENT.

Member Function Documentation

◆ count()

template<unsigned ElementSize = 128>

size_type llvm::SparseBitVectorElement< ElementSize >::count ( ) const

inline

Definition at line 121 of file SparseBitVector.h.

References llvm::popcount().

◆ empty()

template<unsigned ElementSize = 128>

bool llvm::SparseBitVectorElement< ElementSize >::empty ( ) const

inline

Definition at line 93 of file SparseBitVector.h.

References BITWORDS_PER_ELEMENT.

◆ find_first()

template<unsigned ElementSize = 128>

int llvm::SparseBitVectorElement< ElementSize >::find_first ( ) const

inline

find_first - Returns the index of the first set bit.

Definition at line 129 of file SparseBitVector.h.

References BITWORD_SIZE, BITWORDS_PER_ELEMENT, llvm::countr_zero(), and llvm_unreachable.

◆ find_last()

template<unsigned ElementSize = 128>

int llvm::SparseBitVectorElement< ElementSize >::find_last ( ) const

inline

find_last - Returns the index of the last set bit.

Definition at line 137 of file SparseBitVector.h.

References BITWORD_SIZE, BITWORDS_PER_ELEMENT, llvm::countl_zero(), I, and llvm_unreachable.

◆ find_next()

template<unsigned ElementSize = 128>

int llvm::SparseBitVectorElement< ElementSize >::find_next ( unsigned Curr ) const

inline

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.

Definition at line 149 of file SparseBitVector.h.

References assert(), BITS_PER_ELEMENT, BITWORD_SIZE, BITWORDS_PER_ELEMENT, and llvm::countr_zero().

◆ index()

template<unsigned ElementSize = 128>

unsigned llvm::SparseBitVectorElement< ElementSize >::index ( ) const

inline

Definition at line 89 of file SparseBitVector.h.

◆ intersects()

template<unsigned ElementSize = 128>

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

inline

Definition at line 186 of file SparseBitVector.h.

References BITWORDS_PER_ELEMENT, and RHS.

◆ intersectWith()

template<unsigned ElementSize = 128>

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

inline

Definition at line 196 of file SparseBitVector.h.

References BITWORDS_PER_ELEMENT, and RHS.

◆ intersectWithComplement() [1/2]

template<unsigned ElementSize = 128>

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

inline

Definition at line 219 of file SparseBitVector.h.

References BITWORDS_PER_ELEMENT, and RHS.

◆ intersectWithComplement() [2/2]

template<unsigned ElementSize = 128>

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

inline

Definition at line 241 of file SparseBitVector.h.

References BITWORDS_PER_ELEMENT.

◆ operator!=()

template<unsigned ElementSize = 128>

bool llvm::SparseBitVectorElement< ElementSize >::operator!= ( const SparseBitVectorElement< ElementSize > & RHS ) const

inline

Definition at line 79 of file SparseBitVector.h.

References RHS.

◆ operator==()

template<unsigned ElementSize = 128>

bool llvm::SparseBitVectorElement< ElementSize >::operator== ( const SparseBitVectorElement< ElementSize > & RHS ) const

inline

Definition at line 70 of file SparseBitVector.h.

References BITWORDS_PER_ELEMENT, and RHS.

◆ reset()

template<unsigned ElementSize = 128>

void llvm::SparseBitVectorElement< ElementSize >::reset ( unsigned Idx )

inline

Definition at line 113 of file SparseBitVector.h.

References BITWORD_SIZE.

◆ set()

template<unsigned ElementSize = 128>

void llvm::SparseBitVectorElement< ElementSize >::set ( unsigned Idx )

inline

Definition at line 100 of file SparseBitVector.h.

References BITWORD_SIZE.

Referenced by test_and_set().

◆ test()

template<unsigned ElementSize = 128>

bool llvm::SparseBitVectorElement< ElementSize >::test ( unsigned Idx ) const

inline

Definition at line 117 of file SparseBitVector.h.

References BITWORD_SIZE.

◆ test_and_set()

template<unsigned ElementSize = 128>

bool llvm::SparseBitVectorElement< ElementSize >::test_and_set ( unsigned Idx )

inline

Definition at line 104 of file SparseBitVector.h.

References set(), and test.

◆ unionWith()

template<unsigned ElementSize = 128>

bool llvm::SparseBitVectorElement< ElementSize >::unionWith ( const SparseBitVectorElement< ElementSize > & RHS )

inline

Definition at line 173 of file SparseBitVector.h.

References BITWORDS_PER_ELEMENT, and RHS.

◆ word()

template<unsigned ElementSize = 128>

BitWord llvm::SparseBitVectorElement< ElementSize >::word ( unsigned Idx ) const

inline

Definition at line 84 of file SparseBitVector.h.

References assert(), and BITWORDS_PER_ELEMENT.

The documentation for this struct was generated from the following file:

include/llvm/ADT/SparseBitVector.h

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ BitWord

◆ size_type

Member Enumeration Documentation

◆ anonymous enum

Constructor & Destructor Documentation

◆ SparseBitVectorElement()

Member Function Documentation

◆ 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()