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)
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)
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)
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
llvm::CoalescingBitVector::const_iterator begin()
const
Declared at: llvm/include/llvm/ADT/CoalescingBitVector.h:346
¶void clear()
void clear()
Description
Clear all the bits.
Declared at: llvm/include/llvm/ADT/CoalescingBitVector.h:79
¶unsigned int count() const
unsigned int count() const
Description
Count the number of set bits.
Declared at: llvm/include/llvm/ADT/CoalescingBitVector.h:85
¶void dump() const
void dump() const
Declared at: llvm/include/llvm/ADT/CoalescingBitVector.h:389
¶bool empty() const
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
llvm::CoalescingBitVector::const_iterator end()
const
Declared at: llvm/include/llvm/ADT/CoalescingBitVector.h:348
¶llvm::CoalescingBitVector::const_iterator find(
IndexT Index) const
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)
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
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
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)
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)
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
void print(llvm::raw_ostream& OS) const
Declared at: llvm/include/llvm/ADT/CoalescingBitVector.h:376
Parameters
¶void reset(IndexT Index)
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)
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)
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)
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
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)
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