class CoalescingBitVector

Declaration

template <typename IndexT>
class CoalescingBitVector { /* full declaration omitted */ };

Description

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.

Declared at: llvm/include/llvm/ADT/CoalescingBitVector.h:38

Templates

IndexT
- The type of the index into the bitvector.

Member Variables

private llvm::CoalescingBitVector::Allocator* Alloc
private llvm::CoalescingBitVector::MapT Intervals

Method Overview

  • public CoalescingBitVector<IndexT>(const llvm::CoalescingBitVector::ThisT & Other)
  • public CoalescingBitVector<IndexT>(llvm::CoalescingBitVector::ThisT && Other)
  • public CoalescingBitVector<IndexT>(llvm::CoalescingBitVector::Allocator & Alloc)
  • public llvm::CoalescingBitVector::const_iterator begin() const
  • public void clear()
  • public unsigned int count() const
  • public void dump() const
  • public bool empty() const
  • public llvm::CoalescingBitVector::const_iterator end() const
  • public llvm::CoalescingBitVector::const_iterator find(IndexT Index) const
  • private void getNonOverlappingParts(IndexT Start, IndexT Stop, const SmallVectorImpl<llvm::CoalescingBitVector::IntervalT> & Overlaps, SmallVectorImpl<llvm::CoalescingBitVector::IntervalT> & NonOverlappingParts)
  • private bool getOverlaps(const llvm::CoalescingBitVector::ThisT & Other, SmallVectorImpl<llvm::CoalescingBitVector::IntervalT> & Overlaps) const
  • public iterator_range<llvm::CoalescingBitVector::const_iterator> half_open_range(IndexT Start, IndexT End) const
  • private void insert(IndexT Start, IndexT End)
  • public void intersectWithComplement(const llvm::CoalescingBitVector::ThisT & Other)
  • public void print(llvm::raw_ostream & OS) const
  • public void reset(IndexT Index)
  • public void set(std::initializer_list<IndexT> Indices)
  • public void set(const llvm::CoalescingBitVector::ThisT & Other)
  • public void set(IndexT Index)
  • public bool test(IndexT Index) const
  • public void test_and_set(IndexT Index)

Methods

CoalescingBitVector<IndexT>(
    const llvm::CoalescingBitVector::ThisT& Other)

Description

@ {

Declared at: llvm/include/llvm/ADT/CoalescingBitVector.h:62

Parameters

const llvm::CoalescingBitVector::ThisT& Other

CoalescingBitVector<IndexT>(
    llvm::CoalescingBitVector::ThisT&& Other)

Declared at: llvm/include/llvm/ADT/CoalescingBitVector.h:73

Parameters

llvm::CoalescingBitVector::ThisT&& Other

CoalescingBitVector<IndexT>(
    llvm::CoalescingBitVector::Allocator& Alloc)

Description

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

Declared at: llvm/include/llvm/ADT/CoalescingBitVector.h:56

Parameters

llvm::CoalescingBitVector::Allocator& Alloc

llvm::CoalescingBitVector::const_iterator begin()
    const

Declared at: llvm/include/llvm/ADT/CoalescingBitVector.h:346

void clear()

Description

Clear all the bits.

Declared at: llvm/include/llvm/ADT/CoalescingBitVector.h:79

unsigned int count() const

Description

Count the number of set bits.

Declared at: llvm/include/llvm/ADT/CoalescingBitVector.h:85

void dump() const

Declared at: llvm/include/llvm/ADT/CoalescingBitVector.h:389

bool empty() const

Description

Check whether no bits are set.

Declared at: llvm/include/llvm/ADT/CoalescingBitVector.h:82

llvm::CoalescingBitVector::const_iterator end()
    const

Declared at: llvm/include/llvm/ADT/CoalescingBitVector.h:348

llvm::CoalescingBitVector::const_iterator find(
    IndexT Index) const

Description

Return an iterator pointing to the first set bit AT, OR AFTER, \p 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))).

Declared at: llvm/include/llvm/ADT/CoalescingBitVector.h:354

Parameters

IndexT Index

void getNonOverlappingParts(
    IndexT Start,
    IndexT Stop,
    const SmallVectorImpl<
        llvm::CoalescingBitVector::IntervalT>&
        Overlaps,
    SmallVectorImpl<
        llvm::CoalescingBitVector::IntervalT>&
        NonOverlappingParts)

Description

Given the set of overlaps between this and some other bitvector, and an interval [Start, Stop] from that bitvector, determine the portions of the interval which do not overlap with this.

Declared at: llvm/include/llvm/ADT/CoalescingBitVector.h:419

Parameters

IndexT Start
IndexT Stop
const SmallVectorImpl< llvm::CoalescingBitVector::IntervalT>& Overlaps
SmallVectorImpl< llvm::CoalescingBitVector::IntervalT>& NonOverlappingParts

bool getOverlaps(
    const llvm::CoalescingBitVector::ThisT& Other,
    SmallVectorImpl<
        llvm::CoalescingBitVector::IntervalT>&
        Overlaps) const

Description

Record the overlaps between \p this and \p Other in \p Overlaps. Return true if there is any overlap.

Declared at: llvm/include/llvm/ADT/CoalescingBitVector.h:403

Parameters

const llvm::CoalescingBitVector::ThisT& Other
SmallVectorImpl< llvm::CoalescingBitVector::IntervalT>& Overlaps

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

Description

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

Declared at: llvm/include/llvm/ADT/CoalescingBitVector.h:365

Parameters

IndexT Start
IndexT End

void insert(IndexT Start, IndexT End)

Declared at: llvm/include/llvm/ADT/CoalescingBitVector.h:399

Parameters

IndexT Start
IndexT End

void intersectWithComplement(
    const llvm::CoalescingBitVector::ThisT& Other)

Description

Reset all bits present in \p Other.

Declared at: llvm/include/llvm/ADT/CoalescingBitVector.h:188

Parameters

const llvm::CoalescingBitVector::ThisT& Other

void print(llvm::raw_ostream& OS) const

Declared at: llvm/include/llvm/ADT/CoalescingBitVector.h:376

Parameters

llvm::raw_ostream& OS

void reset(IndexT Index)

Description

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

Declared at: llvm/include/llvm/ADT/CoalescingBitVector.h:135

Parameters

IndexT Index

void set(std::initializer_list<IndexT> Indices)

Description

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

Declared at: llvm/include/llvm/ADT/CoalescingBitVector.h:114

Parameters

std::initializer_list<IndexT> Indices

void set(
    const llvm::CoalescingBitVector::ThisT& Other)

Description

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

Declared at: llvm/include/llvm/ADT/CoalescingBitVector.h:107

Parameters

const llvm::CoalescingBitVector::ThisT& Other

void set(IndexT Index)

Description

Set the bit at \p 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 \ref test_and_set.

Declared at: llvm/include/llvm/ADT/CoalescingBitVector.h:97

Parameters

IndexT Index

bool test(IndexT Index) const

Description

Check whether the bit at \p Index is set.

Declared at: llvm/include/llvm/ADT/CoalescingBitVector.h:120

Parameters

IndexT Index

void test_and_set(IndexT Index)

Description

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

Declared at: llvm/include/llvm/ADT/CoalescingBitVector.h:129

Parameters

IndexT Index