Fast bit array that keeps track of the number of bits set and can find the next set in a timely manner. More...

#include <bits.h>

Classes
struct	FastHash

struct	Hash

class	View

Public Types
enum	Mode { All, AllSet, AllUnset }

using	AllView = View< All >

using	AllSetView = View< AllSet >

using	AllUnsetView = View< AllUnset >

Public Member Functions
	TfBits (size_t num=0)

	TfBits (size_t num, size_t first, size_t last)

	TfBits (const TfBits &rhs)

	TfBits (TfBits &&rhs)

	~TfBits ()

TfBits &	operator= (const TfBits &rhs)

TfBits &	operator= (TfBits &&rhs)

void	Resize (size_t num)

void	ResizeKeepContent (size_t num)

TF_API void	OrSubset (const TfBits &rhs)

void	Swap (TfBits &rhs)

void	ClearAll ()

void	SetAll ()

void	Clear (size_t index)

void	Set (size_t index)

void	Assign (size_t index, bool val)

bool	IsSet (size_t index) const

size_t	FindNextSet (size_t index) const

size_t	FindPrevSet (size_t index) const

size_t	FindNextUnset (size_t index) const

size_t	GetSize () const

bool	IsEmpty () const

size_t	GetFirstSet () const

size_t	GetLastSet () const

size_t	GetNumSet () const

bool	AreAllSet () const

bool	AreAllUnset () const

bool	IsAnySet () const

bool	IsAnyUnset () const

bool	AreContiguouslySet () const

size_t	GetAllocatedSize () const

TF_API size_t	GetHash () const

TF_API std::string	GetAsStringLeftToRight () const

TF_API std::string	GetAsStringRightToLeft () const

bool	HasNonEmptyIntersection (const TfBits &rhs) const

bool	HasNonEmptyDifference (const TfBits &rhs) const

bool	Contains (const TfBits &rhs) const

AllView	GetAllView () const

AllSetView	GetAllSetView () const

AllUnsetView	GetAllUnsetView () const

Operators
TF_API bool	operator== (const TfBits &rhs) const

bool	operator!= (const TfBits &rhs) const

TF_API TfBits &	operator&= (const TfBits &rhs)

TfBits	operator& (const TfBits &rhs) const

TF_API TfBits &	operator\|= (const TfBits &rhs)

TfBits	operator\| (const TfBits &rhs) const

TF_API TfBits &	operator^= (const TfBits &rhs)

TfBits	operator^ (const TfBits &rhs) const

TF_API TfBits &	operator-= (const TfBits &rhs)

TF_API TfBits &	Complement ()

bool	operator[] (size_t index) const

Friends
void	swap (TfBits &lhs, TfBits &rhs)

Detailed Description

Fast bit array that keeps track of the number of bits set and can find the next set in a timely manner.

Note about thread safety in this class:

TfBits supports only the most basic thread safety guarantee: multiple threads may safely call const methods concurrently. A thread must not invoke any non-const method on a TfBits object while any other thread is accessing it.

There are certain members in this class that are mutable and modified in const methods. However, since they are updated without being read and all threads would update them with the same values in the case of a race condition, the worst thing that can happen is redundant computation.

Successive access to these members will result in read only access patterns.

All occurances are marked.

Definition at line 48 of file bits.h.

Member Typedef Documentation

using TfBits::AllSetView = View<AllSet>

Definition at line 903 of file bits.h.

using TfBits::AllUnsetView = View<AllUnset>

Definition at line 904 of file bits.h.

using TfBits::AllView = View<All>

Definition at line 902 of file bits.h.

Member Enumeration Documentation

enum TfBits::Mode

Enumerator
All
AllSet
AllUnset

Definition at line 53 of file bits.h.

Constructor & Destructor Documentation

TfBits::TfBits ( size_t num = 0 )

inlineexplicit

Constructs a fixed size bit array, clears all bits.

Definition at line 85 of file bits.h.

TfBits::TfBits	(	size_t	num,
		size_t	first,
		size_t	last
	)

inline

Constructs a fixed size bit array, with a range of bits set.

Definition at line 95 of file bits.h.

TfBits::TfBits ( const TfBits & rhs )

inline

Copy-constructs a fixed size bit array.

Definition at line 114 of file bits.h.

TfBits::TfBits ( TfBits && rhs )

inline

Move constructor.

Definition at line 130 of file bits.h.

TfBits::~TfBits ( )

inline

Destructor

Definition at line 137 of file bits.h.

Member Function Documentation

bool TfBits::AreAllSet ( ) const

inline

Returns true, if all the bits in this bit array are set.

Definition at line 534 of file bits.h.

bool TfBits::AreAllUnset ( ) const

inline

Returns true, if all the bits in this bit array are unset.

Definition at line 543 of file bits.h.

bool TfBits::AreContiguouslySet ( ) const

inline

Returns true if the set bits in this bit array are contiguous.

Note: This returns false if there are no set bits.

Definition at line 566 of file bits.h.

void TfBits::Assign	(	size_t	index,
		bool	val
	)

inline

Assigns val to bit # index.

Definition at line 402 of file bits.h.

void TfBits::Clear ( size_t index )

inline

Clears bit # index to zero.

Definition at line 353 of file bits.h.

void TfBits::ClearAll ( )

inline

Clears all bits to zero.

Definition at line 330 of file bits.h.

TF_API TfBits& TfBits::Complement ( )

Flips all bits.

The resulting bit set is the complement of this bit set.

bool TfBits::Contains ( const TfBits & rhs ) const

inline

Returns true if this bit array contains rhs by computing: (rhs - this).GetNumSet() == 0.

Ie. it will return true if all bits of rhs are also set in this.

Definition at line 787 of file bits.h.

size_t TfBits::FindNextSet ( size_t index ) const

inline

Finds the next set bit that has a higher or equal index than index. If no more set bits are found, index returns 'GetSize()'.

Definition at line 422 of file bits.h.

size_t TfBits::FindNextUnset ( size_t index ) const

inline

Finds the next unset bit that has a higher or equal index than index. If no more set bits are found, index returns 'GetSize()'.

Definition at line 458 of file bits.h.

size_t TfBits::FindPrevSet ( size_t index ) const

inline

Finds the prev set bit that has a lower or equal index than index. If no more set bits are found, index returns 'GetSize()'.

Definition at line 440 of file bits.h.

size_t TfBits::GetAllocatedSize ( ) const

inline

Returns the amount of memory this object holds on to.

Definition at line 573 of file bits.h.

AllSetView TfBits::GetAllSetView ( ) const

inline

Returns an iteratable view for the bits that steps over all set bits.

Definition at line 914 of file bits.h.

AllUnsetView TfBits::GetAllUnsetView ( ) const

inline

Returns an iteratable view for the bits that steps over all unset bits.

Definition at line 920 of file bits.h.

AllView TfBits::GetAllView ( ) const

inline

Returns an iteratable view for the bits that steps over all bits.

Definition at line 908 of file bits.h.

TF_API std::string TfBits::GetAsStringLeftToRight ( ) const

Returns a string representing the bits for debugging with bits ordered from left to right with increasing indices.

TF_API std::string TfBits::GetAsStringRightToLeft ( ) const

Returns a string representing the bits for debugging with bits ordered from right to left with increasing indices.

size_t TfBits::GetFirstSet ( ) const

inline

Returns the index of the first bit set in the bit array. If no bits are set, the return value is 'GetSize()'.

Definition at line 490 of file bits.h.

TF_API size_t TfBits::GetHash ( ) const

Returns a hash for this instance.

size_t TfBits::GetLastSet ( ) const

inline

Returns the index of the last bit set in the bit array. If no bits are set, the return value is 'GetSize()'.

Definition at line 505 of file bits.h.

size_t TfBits::GetNumSet ( ) const

inline

Returns the number of bits currently set in this array.

Definition at line 520 of file bits.h.

size_t TfBits::GetSize ( ) const

inline

Returns the size of the bit array, ie. the # of bits it can hold.

Definition at line 475 of file bits.h.

bool TfBits::HasNonEmptyDifference ( const TfBits & rhs ) const

inline

Returns true if the result of an asymmetric set different is non-zero. This is the equivalent to computing: return (this - rhs).GetNumSet() != 0 but avoids creating temporary copies.

Definition at line 740 of file bits.h.

bool TfBits::HasNonEmptyIntersection ( const TfBits & rhs ) const

inline

Returns true if the result of the intersection with rhs would be non-zero.

This method can be used for efficiency because it doesn't perform the full AND operation on a copy, and it can return early.

Definition at line 696 of file bits.h.

bool TfBits::IsAnySet ( ) const

inline

Returns true, if there is at least a single set bit.

Definition at line 550 of file bits.h.

bool TfBits::IsAnyUnset ( ) const

inline

Returns true, if there is at least a single unset bit.

Definition at line 557 of file bits.h.

bool TfBits::IsEmpty ( ) const

inline

Returns true if this bit array is empty, i.e. it is of size zero.

Definition at line 482 of file bits.h.

bool TfBits::IsSet ( size_t index ) const

inline

Returns true, if bit # index is set.

Definition at line 412 of file bits.h.

bool TfBits::operator!= ( const TfBits & rhs ) const

inline

Returns true if this != rhs.

Definition at line 611 of file bits.h.

TfBits TfBits::operator& ( const TfBits & rhs ) const

inline

Returns these bits and'ed with rhs.

Definition at line 625 of file bits.h.

TF_API TfBits& TfBits::operator&= ( const TfBits & rhs )

Ands these bits with the rhs bits.

The resulting bit set is the intersection of the two bit sets.

TF_API TfBits& TfBits::operator-= ( const TfBits & rhs )

Removes all bits in the rhs bits from these bits.

The resulting bit set is the asymmetric set difference of the two bit sets.

TfBits& TfBits::operator= ( const TfBits & rhs )

inline

Assignment operator

Definition at line 144 of file bits.h.

TfBits& TfBits::operator= ( TfBits && rhs )

inline

Move assignment operator.

Definition at line 172 of file bits.h.

TF_API bool TfBits::operator== ( const TfBits & rhs ) const

Returns true if this == rhs.

bool TfBits::operator[] ( size_t index ) const

inline

Returns bit at index.

Definition at line 682 of file bits.h.

TfBits TfBits::operator^ ( const TfBits & rhs ) const

inline

Returns these bits xor'ed with rhs.

Definition at line 658 of file bits.h.

TF_API TfBits& TfBits::operator^= ( const TfBits & rhs )

Xors these bits with the rhs bits.

The resulting bit set is the union of the two bit sets minus the intersection of the two bit sets.

TfBits TfBits::operator| ( const TfBits & rhs ) const

inline

Returns these bits or'ed with rhs.

Definition at line 641 of file bits.h.

TF_API TfBits& TfBits::operator|= ( const TfBits & rhs )

Ors these bits with the rhs bits.

The resulting bit set is the union of the two bit sets.

TF_API void TfBits::OrSubset ( const TfBits & rhs )

Combines two differently sized TfBits using an or operator. This can be used if GetSize() >= rhs.GetSize(). This is more efficient than padding rhs to the correct size beforehand.

void TfBits::Resize ( size_t num )

inline

Resizes the bit array, however, the bits are left uninitialized. So you most likely want to call ClearAll(); or SetAll();.

Definition at line 185 of file bits.h.

void TfBits::ResizeKeepContent ( size_t num )

inline

Resizes the size of the bit array while keeping the content.

Definition at line 208 of file bits.h.

void TfBits::Set ( size_t index )

inline

Sets bit # index to one.

Definition at line 377 of file bits.h.

void TfBits::SetAll ( )

inline

Sets all bits to one.

Definition at line 340 of file bits.h.

void TfBits::Swap ( TfBits & rhs )

inline

Provides a fast swap.

Definition at line 261 of file bits.h.

Friends And Related Function Documentation

void swap	(	TfBits &	lhs,
		TfBits &	rhs
	)

friend

Definition at line 324 of file bits.h.

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

pxr/base/tf/bits.h

Classes

Public Types

Public Member Functions

Friends

Detailed Description

Member Typedef Documentation

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation