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_iterator >	half_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)

ThisT &	operator= (const ThisT &Other)

	CoalescingBitVector (ThisT &&Other)=delete

ThisT &	operator= (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

Definition at line 62 of file CoalescingBitVector.h.

References llvm::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

Definition at line 346 of file CoalescingBitVector.h.

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

◆ clear()

template<typename IndexT >

void llvm::CoalescingBitVector< IndexT >::clear ( )

inline

Clear all the bits.

Definition at line 79 of file CoalescingBitVector.h.

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

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

◆ count()

template<typename IndexT >

unsigned llvm::CoalescingBitVector< IndexT >::count ( ) const

inline

Count the number of set bits.

Definition at line 85 of file CoalescingBitVector.h.

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

◆ dump()

template<typename IndexT >

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

inline

Definition at line 389 of file CoalescingBitVector.h.

References llvm::dbgs(), and llvm::CoalescingBitVector< IndexT >::print().

◆ 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

Definition at line 348 of file CoalescingBitVector.h.

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

◆ 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

Definition at line 233 of file CoalescingBitVector.h.

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

◆ 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

Definition at line 67 of file CoalescingBitVector.h.

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

◆ 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

Definition at line 219 of file CoalescingBitVector.h.

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

Referenced by llvm::CoalescingBitVector< IndexT >::operator!=().

◆ 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

Definition at line 376 of file CoalescingBitVector.h.

References llvm::IntervalMap< KeyT, ValT, N, Traits >::begin(), llvm::IntervalMap< KeyT, ValT, N, Traits >::end(), End, and OS.

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

◆ 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

Check whether the bit at Index is set.

Definition at line 120 of file CoalescingBitVector.h.

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

◆ 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:

include/llvm/ADT/CoalescingBitVector.h

Classes

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ Allocator

Constructor & Destructor Documentation

◆ CoalescingBitVector() [1/3]

◆ CoalescingBitVector() [2/3]

◆ CoalescingBitVector() [3/3]

Member Function Documentation

◆ begin()

◆ clear()

◆ count()

◆ dump()

◆ empty()

◆ end()

◆ find()

◆ half_open_range()

◆ intersectWithComplement()

◆ operator!=()

◆ operator&=()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ operator|=()

◆ print()

◆ reset()

◆ set() [1/3]

◆ set() [2/3]

◆ set() [3/3]

◆ test()

◆ test_and_set()