LLVM: llvm::SparseBitVectorElement< ElementSize > Struct Template Reference

LLVM API Documentation

#include <SparseBitVector.h>

Inheritance diagram for llvm::SparseBitVectorElement< ElementSize >:

Inheritance graph

Collaboration diagram for llvm::SparseBitVectorElement< ElementSize >:

Collaboration graph

List of all members.

Public Types
enum	{ BITWORD_SIZE = sizeof(BitWord) * CHAR_BIT, BITWORDS_PER_ELEMENT = (ElementSize + BITWORD_SIZE - 1) / BITWORD_SIZE, BITS_PER_ELEMENT = ElementSize }
typedef unsigned long	BitWord
typedef unsigned	size_type
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_next (unsigned Curr) const
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)
Friends
struct	ilist_sentinel_traits< SparseBitVectorElement >

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

Member Typedef Documentation

template<unsigned ElementSize = 128>

typedef unsigned long llvm::SparseBitVectorElement< ElementSize >::BitWord

Definition at line 47 of file SparseBitVector.h.

template<unsigned ElementSize = 128>

typedef unsigned llvm::SparseBitVectorElement< ElementSize >::size_type

Definition at line 48 of file SparseBitVector.h.

Member Enumeration Documentation

template<unsigned ElementSize = 128>

anonymous enum

Enumerator:

BITWORD_SIZE
BITWORDS_PER_ELEMENT
BITS_PER_ELEMENT

Definition at line 49 of file SparseBitVector.h.

Constructor & Destructor Documentation

template<unsigned ElementSize = 128>

llvm::SparseBitVectorElement< ElementSize >::SparseBitVectorElement ( unsigned Idx ) [inline, explicit]

Definition at line 67 of file SparseBitVector.h.

References llvm::tgtok::Bits, llvm::SparseBitVectorElement< ElementSize >::BITWORDS_PER_ELEMENT, and llvm::LibFunc::memset.

Member Function Documentation

template<unsigned ElementSize = 128>

size_type llvm::SparseBitVectorElement< ElementSize >::count ( ) const [inline]

Definition at line 124 of file SparseBitVector.h.

References llvm::tgtok::Bits, llvm::SparseBitVectorElement< ElementSize >::BITWORDS_PER_ELEMENT, llvm::CountPopulation_32(), llvm::CountPopulation_64(), and llvm_unreachable.

template<unsigned ElementSize = 128>

bool llvm::SparseBitVectorElement< ElementSize >::empty ( ) const [inline]

Definition at line 96 of file SparseBitVector.h.

References llvm::tgtok::Bits, and llvm::SparseBitVectorElement< ElementSize >::BITWORDS_PER_ELEMENT.

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

References llvm::tgtok::Bits, llvm::SparseBitVectorElement< ElementSize >::BITWORD_SIZE, llvm::SparseBitVectorElement< ElementSize >::BITWORDS_PER_ELEMENT, llvm::countTrailingZeros(), and llvm_unreachable.

Referenced by llvm::SparseBitVector< ElementSize >::find_first().

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

References llvm::tgtok::Bits, llvm::SparseBitVectorElement< ElementSize >::BITS_PER_ELEMENT, llvm::SparseBitVectorElement< ElementSize >::BITWORD_SIZE, llvm::SparseBitVectorElement< ElementSize >::BITWORDS_PER_ELEMENT, llvm::countTrailingZeros(), and llvm_unreachable.

template<unsigned ElementSize = 128>

unsigned llvm::SparseBitVectorElement< ElementSize >::index ( ) const [inline]

Definition at line 92 of file SparseBitVector.h.

Referenced by llvm::SparseBitVector< ElementSize >::find_first().

template<unsigned ElementSize = 128>

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

Definition at line 198 of file SparseBitVector.h.

References llvm::tgtok::Bits, and llvm::SparseBitVectorElement< ElementSize >::BITWORDS_PER_ELEMENT.

template<unsigned ElementSize = 128>

bool llvm::SparseBitVectorElement< ElementSize >::intersectWith	(	const SparseBitVectorElement< ElementSize > &	RHS,
		bool &	BecameZero
	)		`[inline]`

Definition at line 208 of file SparseBitVector.h.

References llvm::tgtok::Bits, and llvm::SparseBitVectorElement< ElementSize >::BITWORDS_PER_ELEMENT.

template<unsigned ElementSize = 128>

bool llvm::SparseBitVectorElement< ElementSize >::intersectWithComplement	(	const SparseBitVectorElement< ElementSize > &	RHS,
		bool &	BecameZero
	)		`[inline]`

Definition at line 230 of file SparseBitVector.h.

References llvm::tgtok::Bits, and llvm::SparseBitVectorElement< ElementSize >::BITWORDS_PER_ELEMENT.

Referenced by llvm::SparseBitVector< ElementSize >::intersectWithComplement().

template<unsigned ElementSize = 128>

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

Definition at line 251 of file SparseBitVector.h.

References llvm::tgtok::Bits, and llvm::SparseBitVectorElement< ElementSize >::BITWORDS_PER_ELEMENT.

template<unsigned ElementSize = 128>

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

Definition at line 82 of file SparseBitVector.h.

template<unsigned ElementSize = 128>

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

Definition at line 73 of file SparseBitVector.h.

References llvm::tgtok::Bits, and llvm::SparseBitVectorElement< ElementSize >::BITWORDS_PER_ELEMENT.

template<unsigned ElementSize = 128>

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

Definition at line 116 of file SparseBitVector.h.

References llvm::tgtok::Bits, and llvm::SparseBitVectorElement< ElementSize >::BITWORD_SIZE.

template<unsigned ElementSize = 128>

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

Definition at line 103 of file SparseBitVector.h.

References llvm::tgtok::Bits, and llvm::SparseBitVectorElement< ElementSize >::BITWORD_SIZE.

template<unsigned ElementSize = 128>

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

Definition at line 120 of file SparseBitVector.h.

References llvm::tgtok::Bits, and llvm::SparseBitVectorElement< ElementSize >::BITWORD_SIZE.

Referenced by llvm::SparseBitVectorElement< ElementSize >::test_and_set().

template<unsigned ElementSize = 128>

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

Definition at line 107 of file SparseBitVector.h.

References llvm::SparseBitVectorElement< ElementSize >::test().

template<unsigned ElementSize = 128>

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

Definition at line 185 of file SparseBitVector.h.

References llvm::tgtok::Bits, and llvm::SparseBitVectorElement< ElementSize >::BITWORDS_PER_ELEMENT.

template<unsigned ElementSize = 128>

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

Definition at line 87 of file SparseBitVector.h.

References llvm::tgtok::Bits, and llvm::SparseBitVectorElement< ElementSize >::BITWORDS_PER_ELEMENT.

Friends And Related Function Documentation

template<unsigned ElementSize = 128>

friend struct ilist_sentinel_traits< SparseBitVectorElement > [friend]

Definition at line 60 of file SparseBitVector.h.

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

SparseBitVector.h