LLVM  14.0.0git
Classes | Public Types | Public Member Functions | List of all members
llvm::CoalescingBitVector< IndexT > Class Template Reference

A bitvector that, under the hood, relies on an IntervalMap to coalesce elements into intervals. More...

#include "llvm/ADT/CoalescingBitVector.h"

Classes

class  const_iterator
 

Public Types

using Allocator = typename MapT::Allocator
 

Public Member Functions

 CoalescingBitVector (Allocator &Alloc)
 Construct by passing in a CoalescingBitVector<IndexT>::Allocator reference. More...
 
void clear ()
 Clear all the bits. More...
 
bool empty () const
 Check whether no bits are set. More...
 
unsigned count () const
 Count the number of set bits. More...
 
void set (IndexT Index)
 Set the bit at Index. More...
 
void set (const ThisT &Other)
 Set the bits set in Other. More...
 
void set (std::initializer_list< IndexT > Indices)
 Set the bits at Indices. Used for testing, primarily. More...
 
bool test (IndexT Index) const
 Check whether the bit at Index is set. More...
 
void test_and_set (IndexT Index)
 Set the bit at Index. Supports setting an already-set bit. More...
 
void reset (IndexT Index)
 Reset the bit at Index. Supports resetting an already-unset bit. More...
 
void operator|= (const ThisT &RHS)
 Set union. More...
 
void operator&= (const ThisT &RHS)
 Set intersection. More...
 
void intersectWithComplement (const ThisT &Other)
 Reset all bits present in Other. More...
 
bool operator== (const ThisT &RHS) const
 
bool operator!= (const ThisT &RHS) const
 
const_iterator begin () const
 
const_iterator end () const
 
const_iterator find (IndexT Index) const
 Return an iterator pointing to the first set bit AT, OR AFTER, Index. More...
 
iterator_range< const_iteratorhalf_open_range (IndexT Start, IndexT End) const
 Return a range iterator which iterates over all of the set bits in the half-open range [Start, End). More...
 
void print (raw_ostream &OS) const
 
LLVM_DUMP_METHOD void dump () const
 
Copy/move constructors and assignment operators.
 CoalescingBitVector (const ThisT &Other)
 
ThisToperator= (const ThisT &Other)
 
 CoalescingBitVector (ThisT &&Other)=delete
 
ThisToperator= (ThisT &&Other)=delete
 

Detailed Description

template<typename IndexT>
class llvm::CoalescingBitVector< IndexT >

A bitvector that, under the hood, relies on an IntervalMap to coalesce elements into intervals.

Good for representing sets which predominantly contain contiguous ranges. Bad for representing sets with lots of gaps between elements.

Compared to SparseBitVector, CoalescingBitVector offers more predictable performance for non-sequential find() operations.

Template Parameters
IndexT- The type of the index into the bitvector.

Definition at line 37 of file CoalescingBitVector.h.

Member Typedef Documentation

◆ Allocator

template<typename IndexT >
using llvm::CoalescingBitVector< IndexT >::Allocator = typename MapT::Allocator

Definition at line 51 of file CoalescingBitVector.h.

Constructor & Destructor Documentation

◆ CoalescingBitVector() [1/3]

template<typename IndexT >
llvm::CoalescingBitVector< IndexT >::CoalescingBitVector ( Allocator Alloc)
inline

Construct by passing in a CoalescingBitVector<IndexT>::Allocator reference.

Definition at line 55 of file CoalescingBitVector.h.

◆ CoalescingBitVector() [2/3]

template<typename IndexT >
llvm::CoalescingBitVector< IndexT >::CoalescingBitVector ( const ThisT Other)
inline

Definition at line 61 of file CoalescingBitVector.h.

References Other, and llvm::CoalescingBitVector< IndexT >::set().

◆ CoalescingBitVector() [3/3]

template<typename IndexT >
llvm::CoalescingBitVector< IndexT >::CoalescingBitVector ( ThisT &&  Other)
delete

Member Function Documentation

◆ begin()

template<typename IndexT >
const_iterator llvm::CoalescingBitVector< IndexT >::begin ( ) const
inline

◆ clear()

template<typename IndexT >
void llvm::CoalescingBitVector< IndexT >::clear ( )
inline

◆ count()

template<typename IndexT >
unsigned llvm::CoalescingBitVector< IndexT >::count ( ) const
inline

Count the number of set bits.

Definition at line 84 of file CoalescingBitVector.h.

References llvm::IntervalMap< KeyT, ValT, N, Traits >::begin(), and llvm::tgtok::Bits.

◆ dump()

template<typename IndexT >
LLVM_DUMP_METHOD void llvm::CoalescingBitVector< IndexT >::dump ( ) const
inline

◆ empty()

template<typename IndexT >
bool llvm::CoalescingBitVector< IndexT >::empty ( ) const
inline

Check whether no bits are set.

Definition at line 81 of file CoalescingBitVector.h.

References llvm::IntervalMap< KeyT, ValT, N, Traits >::empty().

◆ end()

template<typename IndexT >
const_iterator llvm::CoalescingBitVector< IndexT >::end ( ) const
inline

Definition at line 347 of file CoalescingBitVector.h.

Referenced by llvm::CoalescingBitVector< IndexT >::find().

◆ find()

template<typename IndexT >
const_iterator llvm::CoalescingBitVector< IndexT >::find ( IndexT  Index) const
inline

Return an iterator pointing to the first set bit AT, OR AFTER, Index.

If no such set bit exists, return end(). This is like std::lower_bound. This has worst-case logarithmic performance (roughly O(log(gaps between contiguous ranges))).

Definition at line 353 of file CoalescingBitVector.h.

References llvm::CoalescingBitVector< IndexT >::end(), llvm::IntervalMap< KeyT, ValT, N, Traits >::end(), llvm::IntervalMap< KeyT, ValT, N, Traits >::find(), and Index.

◆ half_open_range()

template<typename IndexT >
iterator_range<const_iterator> llvm::CoalescingBitVector< IndexT >::half_open_range ( IndexT  Start,
IndexT  End 
) const
inline

Return a range iterator which iterates over all of the set bits in the half-open range [Start, End).

Definition at line 364 of file CoalescingBitVector.h.

◆ intersectWithComplement()

template<typename IndexT >
void llvm::CoalescingBitVector< IndexT >::intersectWithComplement ( const ThisT Other)
inline

Reset all bits present in Other.

Definition at line 187 of file CoalescingBitVector.h.

References assert(), llvm::IntervalMap< KeyT, ValT, N, Traits >::find(), and Other.

◆ operator!=()

template<typename IndexT >
bool llvm::CoalescingBitVector< IndexT >::operator!= ( const ThisT RHS) const
inline

◆ operator&=()

template<typename IndexT >
void llvm::CoalescingBitVector< IndexT >::operator&= ( const ThisT RHS)
inline

Set intersection.

Definition at line 176 of file CoalescingBitVector.h.

References llvm::CoalescingBitVector< IndexT >::clear().

◆ operator=() [1/2]

template<typename IndexT >
ThisT& llvm::CoalescingBitVector< IndexT >::operator= ( const ThisT Other)
inline

◆ operator=() [2/2]

template<typename IndexT >
ThisT& llvm::CoalescingBitVector< IndexT >::operator= ( ThisT &&  Other)
delete

◆ operator==()

template<typename IndexT >
bool llvm::CoalescingBitVector< IndexT >::operator== ( const ThisT RHS) const
inline

◆ operator|=()

template<typename IndexT >
void llvm::CoalescingBitVector< IndexT >::operator|= ( const ThisT RHS)
inline

Set union.

If RHS is guaranteed to not overlap with this, set may be a faster alternative.

Definition at line 158 of file CoalescingBitVector.h.

References llvm::IntervalMap< KeyT, ValT, N, Traits >::begin().

◆ print()

template<typename IndexT >
void llvm::CoalescingBitVector< IndexT >::print ( raw_ostream OS) const
inline

◆ reset()

template<typename IndexT >
void llvm::CoalescingBitVector< IndexT >::reset ( IndexT  Index)
inline

Reset the bit at Index. Supports resetting an already-unset bit.

Definition at line 134 of file CoalescingBitVector.h.

References llvm::IntervalMap< KeyT, ValT, N, Traits >::end(), llvm::IntervalMap< KeyT, ValT, N, Traits >::find(), and Index.

◆ set() [1/3]

template<typename IndexT >
void llvm::CoalescingBitVector< IndexT >::set ( const ThisT Other)
inline

Set the bits set in Other.

This method does /not/ support setting already-set bits, see set for the rationale. For a safe set union operation, use operator|=.

Definition at line 106 of file CoalescingBitVector.h.

References Other.

◆ set() [2/3]

template<typename IndexT >
void llvm::CoalescingBitVector< IndexT >::set ( IndexT  Index)
inline

Set the bit at Index.

This method does /not/ support setting a bit that has already been set, for efficiency reasons. If possible, restructure your code to not set the same bit multiple times, or use test_and_set.

Definition at line 96 of file CoalescingBitVector.h.

References assert(), Index, and llvm::CoalescingBitVector< IndexT >::test().

Referenced by llvm::CoalescingBitVector< IndexT >::CoalescingBitVector(), llvm::CoalescingBitVector< IndexT >::operator=(), llvm::CoalescingBitVector< IndexT >::set(), and llvm::CoalescingBitVector< IndexT >::test_and_set().

◆ set() [3/3]

template<typename IndexT >
void llvm::CoalescingBitVector< IndexT >::set ( std::initializer_list< IndexT >  Indices)
inline

Set the bits at Indices. Used for testing, primarily.

Definition at line 113 of file CoalescingBitVector.h.

References Index, and llvm::CoalescingBitVector< IndexT >::set().

◆ test()

template<typename IndexT >
bool llvm::CoalescingBitVector< IndexT >::test ( IndexT  Index) const
inline

◆ test_and_set()

template<typename IndexT >
void llvm::CoalescingBitVector< IndexT >::test_and_set ( IndexT  Index)
inline

Set the bit at Index. Supports setting an already-set bit.

Definition at line 128 of file CoalescingBitVector.h.

References Index, llvm::CoalescingBitVector< IndexT >::set(), and llvm::CoalescingBitVector< IndexT >::test().


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