LLVM 19.0.0git
Public Types | Public Member Functions | List of all members
llvm::SparseBitVectorElement< ElementSize > Struct Template Reference

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 >:
Inheritance graph
[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 42 of file SparseBitVector.h.

Member Typedef Documentation

◆ BitWord

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

Definition at line 44 of file SparseBitVector.h.

◆ size_type

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

Definition at line 45 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 46 of file SparseBitVector.h.

Constructor & Destructor Documentation

◆ SparseBitVectorElement()

template<unsigned ElementSize = 128>
llvm::SparseBitVectorElement< ElementSize >::SparseBitVectorElement ( unsigned  Idx)
inlineexplicit

Member Function Documentation

◆ count()

template<unsigned ElementSize = 128>
size_type llvm::SparseBitVectorElement< ElementSize >::count ( ) const
inline

◆ empty()

template<unsigned ElementSize = 128>
bool llvm::SparseBitVectorElement< ElementSize >::empty ( ) const
inline

◆ find_first()

template<unsigned ElementSize = 128>
int llvm::SparseBitVectorElement< ElementSize >::find_first ( ) const
inline

◆ find_last()

template<unsigned ElementSize = 128>
int llvm::SparseBitVectorElement< ElementSize >::find_last ( ) const
inline

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

References assert(), llvm::SparseBitVectorElement< ElementSize >::BITS_PER_ELEMENT, llvm::SparseBitVectorElement< ElementSize >::BITWORD_SIZE, llvm::SparseBitVectorElement< ElementSize >::BITWORDS_PER_ELEMENT, and llvm::countr_zero().

◆ index()

template<unsigned ElementSize = 128>
unsigned llvm::SparseBitVectorElement< ElementSize >::index ( ) const
inline

Definition at line 88 of file SparseBitVector.h.

◆ intersects()

template<unsigned ElementSize = 128>
bool llvm::SparseBitVectorElement< ElementSize >::intersects ( const SparseBitVectorElement< ElementSize > &  RHS) const
inline

◆ intersectWith()

template<unsigned ElementSize = 128>
bool llvm::SparseBitVectorElement< ElementSize >::intersectWith ( const SparseBitVectorElement< ElementSize > &  RHS,
bool BecameZero 
)
inline

◆ intersectWithComplement() [1/2]

template<unsigned ElementSize = 128>
bool llvm::SparseBitVectorElement< ElementSize >::intersectWithComplement ( const SparseBitVectorElement< ElementSize > &  RHS,
bool BecameZero 
)
inline

◆ intersectWithComplement() [2/2]

template<unsigned ElementSize = 128>
void llvm::SparseBitVectorElement< ElementSize >::intersectWithComplement ( const SparseBitVectorElement< ElementSize > &  RHS1,
const SparseBitVectorElement< ElementSize > &  RHS2,
bool BecameZero 
)
inline

◆ operator!=()

template<unsigned ElementSize = 128>
bool llvm::SparseBitVectorElement< ElementSize >::operator!= ( const SparseBitVectorElement< ElementSize > &  RHS) const
inline

Definition at line 78 of file SparseBitVector.h.

References RHS.

◆ operator==()

template<unsigned ElementSize = 128>
bool llvm::SparseBitVectorElement< ElementSize >::operator== ( const SparseBitVectorElement< ElementSize > &  RHS) const
inline

◆ reset()

template<unsigned ElementSize = 128>
void llvm::SparseBitVectorElement< ElementSize >::reset ( unsigned  Idx)
inline

◆ set()

template<unsigned ElementSize = 128>
void llvm::SparseBitVectorElement< ElementSize >::set ( unsigned  Idx)
inline

◆ test()

template<unsigned ElementSize = 128>
bool llvm::SparseBitVectorElement< ElementSize >::test ( unsigned  Idx) const
inline

◆ test_and_set()

template<unsigned ElementSize = 128>
bool llvm::SparseBitVectorElement< ElementSize >::test_and_set ( unsigned  Idx)
inline

Definition at line 103 of file SparseBitVector.h.

References Idx, llvm::SparseBitVectorElement< ElementSize >::set(), and test.

◆ unionWith()

template<unsigned ElementSize = 128>
bool llvm::SparseBitVectorElement< ElementSize >::unionWith ( const SparseBitVectorElement< ElementSize > &  RHS)
inline

◆ word()

template<unsigned ElementSize = 128>
BitWord llvm::SparseBitVectorElement< ElementSize >::word ( unsigned  Idx) const
inline

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