LLVM 20.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.
 
void clear ()
 Clear all the bits.
 
bool empty () const
 Check whether no bits are set.
 
unsigned count () const
 Count the number of set bits.
 
void set (IndexT Index)
 Set the bit at Index.
 
void set (const ThisT &Other)
 Set the bits set in Other.
 
void set (std::initializer_list< IndexT > Indices)
 Set the bits at Indices. Used for testing, primarily.
 
bool test (IndexT Index) const
 Check whether the bit at Index is set.
 
void test_and_set (IndexT Index)
 Set the bit at Index. Supports setting an already-set bit.
 
void reset (IndexT Index)
 Reset the bit at Index. Supports resetting an already-unset bit.
 
void operator|= (const ThisT &RHS)
 Set union.
 
void operator&= (const ThisT &RHS)
 Set intersection.
 
void intersectWithComplement (const ThisT &Other)
 Reset all bits present in Other.
 
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.
 
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).
 
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 38 of file CoalescingBitVector.h.

Member Typedef Documentation

◆ Allocator

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

Definition at line 52 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 56 of file CoalescingBitVector.h.

◆ CoalescingBitVector() [2/3]

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

◆ 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

◆ 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 82 of file CoalescingBitVector.h.

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

◆ end()

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

◆ 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 354 of file CoalescingBitVector.h.

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

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

◆ 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 365 of file CoalescingBitVector.h.

References llvm::CoalescingBitVector< IndexT >::const_iterator::advanceToLowerBound(), assert(), llvm::CoalescingBitVector< IndexT >::end(), End, and llvm::CoalescingBitVector< IndexT >::find().

◆ intersectWithComplement()

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

Reset all bits present in Other.

Definition at line 188 of file CoalescingBitVector.h.

References assert(), llvm::IntervalMap< KeyT, ValT, N, Traits >::find(), and llvm::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 177 of file CoalescingBitVector.h.

References llvm::CoalescingBitVector< IndexT >::clear(), and RHS.

◆ 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 159 of file CoalescingBitVector.h.

References End, and RHS.

◆ 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 135 of file CoalescingBitVector.h.

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

◆ 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 107 of file CoalescingBitVector.h.

References End, and llvm::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 97 of file CoalescingBitVector.h.

References assert(), and 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 114 of file CoalescingBitVector.h.

References 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 129 of file CoalescingBitVector.h.

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


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