LLVM API Documentation

llvm::SparseBitVectorElement< ElementSize > Struct Template Reference

#include <SparseBitVector.h>

Inheritance diagram for llvm::SparseBitVectorElement< ElementSize >:
[legend]
Collaboration diagram for llvm::SparseBitVectorElement< ElementSize >:
[legend]

List of all members.

Public Types

enum  { BITWORD_SIZE = sizeof(BitWord) * 8, BITWORDS_PER_ELEMENT = (ElementSize + BITWORD_SIZE - 1) / BITWORD_SIZE, BITS_PER_ELEMENT = ElementSize }
typedef unsigned long BitWord

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
unsigned 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)
uint64_t getHashValue () const

Friends

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

Member Typedef Documentation

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

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

Constructor & Destructor Documentation

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

Definition at line 64 of file SparseBitVector.h.

References llvm::SparseBitVectorElement< ElementSize >::BITWORDS_PER_ELEMENT, and llvm::Intrinsic::memset.

Member Function Documentation

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

Definition at line 70 of file SparseBitVector.h.

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

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

Definition at line 79 of file SparseBitVector.h.

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

Definition at line 84 of file SparseBitVector.h.

References llvm::SparseBitVectorElement< ElementSize >::BITWORDS_PER_ELEMENT.

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

Definition at line 89 of file SparseBitVector.h.

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

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

Definition at line 93 of file SparseBitVector.h.

References llvm::SparseBitVectorElement< ElementSize >::BITWORDS_PER_ELEMENT.

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

Definition at line 100 of file SparseBitVector.h.

References llvm::SparseBitVectorElement< ElementSize >::BITWORD_SIZE, Idx, and L.

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

Definition at line 104 of file SparseBitVector.h.

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

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

Definition at line 113 of file SparseBitVector.h.

References llvm::SparseBitVectorElement< ElementSize >::BITWORD_SIZE, and L.

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

Definition at line 117 of file SparseBitVector.h.

References llvm::SparseBitVectorElement< ElementSize >::BITWORD_SIZE, and L.

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

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

Definition at line 121 of file SparseBitVector.h.

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

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

References llvm::SparseBitVectorElement< ElementSize >::BITWORD_SIZE, llvm::SparseBitVectorElement< ElementSize >::BITWORDS_PER_ELEMENT, llvm::CountTrailingZeros_32(), and llvm::CountTrailingZeros_64().

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

References llvm::SparseBitVectorElement< ElementSize >::BITS_PER_ELEMENT, llvm::SparseBitVectorElement< ElementSize >::BITWORD_SIZE, llvm::SparseBitVectorElement< ElementSize >::BITWORDS_PER_ELEMENT, llvm::CountTrailingZeros_32(), llvm::CountTrailingZeros_64(), and L.

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

Definition at line 186 of file SparseBitVector.h.

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

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

Definition at line 199 of file SparseBitVector.h.

References llvm::SparseBitVectorElement< ElementSize >::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 209 of file SparseBitVector.h.

References llvm::SparseBitVectorElement< ElementSize >::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 231 of file SparseBitVector.h.

References llvm::SparseBitVectorElement< ElementSize >::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 252 of file SparseBitVector.h.

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

template<unsigned ElementSize = 128>
uint64_t llvm::SparseBitVectorElement< ElementSize >::getHashValue (  )  const [inline]

Definition at line 267 of file SparseBitVector.h.

References llvm::SparseBitVectorElement< ElementSize >::BITWORDS_PER_ELEMENT.

Friends And Related Function Documentation

template<unsigned ElementSize = 128>
friend class ilist_sentinel_traits< SparseBitVectorElement > [friend]

Definition at line 57 of file SparseBitVector.h.

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

Generated on Thu Nov 5 23:47:31 2009 for LLVM by Doxygen1.5.6
Copyright © 2003-2007 University of Illinois at Urbana-Champaign. All Rights Reserved.