TfCompressedBits Class Reference

Fast, compressed bit array which is capable of performing logical operations without first decompressing the internal data representation. More...

#include <compressedBits.h>

Classes
struct	FastHash
struct	Hash
class	View
class	View< TfCompressedBits::Mode::Platforms >

Public Types
enum	Mode { Mode::All, Mode::AllSet, Mode::AllUnset, Mode::Platforms }
enum	ComplementTagType { ComplementTag }
typedef View< Mode::All >	AllView
typedef View< Mode::AllSet >	AllSetView
typedef View< Mode::AllUnset >	AllUnsetView
typedef View< Mode::Platforms >	PlatformsView

Public Member Functions
	TfCompressedBits (size_t num=0)
	TfCompressedBits (size_t num, size_t first, size_t last)
	TfCompressedBits (const TfCompressedBits &rhs)
	TfCompressedBits (const TfCompressedBits &rhs, ComplementTagType)
TF_API	TfCompressedBits (const TfBits &bits)
	TfCompressedBits (TfCompressedBits &&rhs)
	~TfCompressedBits ()
TfCompressedBits &	operator= (const TfCompressedBits &rhs)
TfCompressedBits &	operator= (TfCompressedBits &&rhs)
void	ResizeKeepContents (size_t num)
void	Swap (TfCompressedBits &rhs)
void	ClearAll ()
void	SetAll ()
void	Clear (size_t index)
void	Set (size_t index)
void	SetRange (size_t first, size_t last)
void	Append (size_t num, bool value)
void	Assign (size_t index, bool value)
void	ShiftRight (size_t bits)
void	ShiftLeft (size_t bits)
bool	IsSet (size_t index) const
size_t	FindNthSet (size_t nth) const
size_t	FindNextSet (size_t index) const
size_t	FindPrevSet (size_t index) const
size_t	FindNextUnset (size_t index) const
void	Count (size_t *numSet, size_t *maxGap) const
size_t	GetSize () const
bool	IsEmpty () const
size_t	GetFirstSet () const
size_t	GetLastSet () const
size_t	GetNumSet () const
size_t	GetNumPlatforms () const
size_t	GetNumSetPlatforms () const
size_t	GetNumUnsetPlatforms () 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
TF_API std::string	GetAsRLEString () const
bool	HasNonEmptyIntersection (const TfCompressedBits &rhs) const
bool	HasNonEmptyDifference (const TfCompressedBits &rhs) const
bool	Contains (const TfCompressedBits &rhs) const
TF_API void	Decompress (TfBits *bits) const
AllView	GetAllView () const
AllSetView	GetAllSetView () const
AllUnsetView	GetAllUnsetView () const
PlatformsView	GetPlatformsView () const
Operators
bool	operator== (const TfCompressedBits &rhs) const
bool	operator!= (const TfCompressedBits &rhs) const
TfCompressedBits &	operator&= (const TfCompressedBits &rhs)
TfCompressedBits	operator& (const TfCompressedBits &rhs) const
TfCompressedBits &	operator|= (const TfCompressedBits &rhs)
TfCompressedBits	operator| (const TfCompressedBits &rhs) const
TfCompressedBits &	operator^= (const TfCompressedBits &rhs)
TfCompressedBits	operator^ (const TfCompressedBits &rhs) const
TfCompressedBits &	operator-= (const TfCompressedBits &rhs)
TfCompressedBits	operator- (const TfCompressedBits &rhs) const
TfCompressedBits &	Complement ()
bool	operator[] (size_t index) const
TfCompressedBits &	operator>>= (size_t bits)
TfCompressedBits	operator>> (size_t bits) const
TfCompressedBits &	operator<<= (size_t bits)
TfCompressedBits	operator<< (size_t bits) const

Static Public Member Functions
static TF_API TfCompressedBits	FromString (const std::string &source)
static const TfCompressedBits &	GetEmpty ()

Detailed Description

Fast, compressed bit array which is capable of performing logical operations without first decompressing the internal data representation.

The internal data compression is based on a form of RLE, where words are used to indicate the number of bits set to the same value. Each subsequent word denotes that the bit value has changed and a "runningBit" is set internally, in order to denote the bit value for the first word.

Internally, a bitset like this:

111000101000

Will be represented as:

1 331113

i.e., the running bit is '1', and there are 3 of those, followed by 3 zeroes, followed by 1 one, followed by 1 zero, followed by 1 one, followed by three zeroes. Each word is called a "platform".

Compressed bits are very fast when used for logical operations (conjugate, and, or, xor, etc.), and when iterated over. Contains and Overlaps are also very fast. The representation is lightweight in memory and hence very cache efficient.

Whenever indexing, setting and resetting of seemingly random bits is a requirement, however, TfBits will perform better, since finding a specific bit requires a linear search.

Definition at line 61 of file compressedBits.h.

Member Typedef Documentation

typedef View<Mode::AllSet> TfCompressedBits::AllSetView

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

Definition at line 1404 of file compressedBits.h.

typedef View<Mode::AllUnset> TfCompressedBits::AllUnsetView

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

Definition at line 1409 of file compressedBits.h.

typedef View<Mode::All> TfCompressedBits::AllView

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

Definition at line 1395 of file compressedBits.h.

typedef View<Mode::Platforms> TfCompressedBits::PlatformsView

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

Definition at line 1414 of file compressedBits.h.

Member Enumeration Documentation

enum TfCompressedBits::ComplementTagType

Copy-construct a fixed sized bit array, from the complement of the rhs bitset.

Enumerator
ComplementTag

Definition at line 375 of file compressedBits.h.

enum TfCompressedBits::Mode

strong

Enumerator
All
AllSet
AllUnset
Platforms

Definition at line 275 of file compressedBits.h.

Constructor & Destructor Documentation

TfCompressedBits::TfCompressedBits ( size_t  num = 0 )

inlineexplicit

Constructs a fixed size bit array, clears all bits.

Definition at line 321 of file compressedBits.h.

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

inlineexplicit

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

Definition at line 329 of file compressedBits.h.

TfCompressedBits::TfCompressedBits ( const TfCompressedBits &  rhs )

inline

Copy-constructs a fixed size bit array.

Definition at line 367 of file compressedBits.h.

TfCompressedBits::TfCompressedBits ( const TfCompressedBits &  rhs, ComplementTagType    )

inline

Definition at line 376 of file compressedBits.h.

TF_API TfCompressedBits::TfCompressedBits ( const TfBits &  bits )

explicit

Construct a TfCompressedBits array from a TfBits array.

TfCompressedBits::TfCompressedBits ( TfCompressedBits &&  rhs )

inline

Move Constructor

Definition at line 392 of file compressedBits.h.

TfCompressedBits::~TfCompressedBits ( )

inline

Destructor

Definition at line 403 of file compressedBits.h.

Member Function Documentation

void TfCompressedBits::Append ( size_t  num, bool  value  )

inline

Append a number of bits with the given value to this bitset. This also increases the size of the bitset by the number of bits added.

Definition at line 547 of file compressedBits.h.

bool TfCompressedBits::AreAllSet ( ) const

inline

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

Definition at line 897 of file compressedBits.h.

bool TfCompressedBits::AreAllUnset ( ) const

inline

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

Definition at line 903 of file compressedBits.h.

bool TfCompressedBits::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 923 of file compressedBits.h.

void TfCompressedBits::Assign ( size_t  index, bool  value  )

inline

Assigns val to bit # index.

Definition at line 571 of file compressedBits.h.

void TfCompressedBits::Clear ( size_t  index )

inline

Clears bit # index to zero.

Note: This is a slow operation on TfCompressedBits!

Definition at line 511 of file compressedBits.h.

void TfCompressedBits::ClearAll ( )

inline

Clears all bits to zero.

Definition at line 485 of file compressedBits.h.

TfCompressedBits& TfCompressedBits::Complement ( )

inline

Flips all bits.

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

Definition at line 1223 of file compressedBits.h.

bool TfCompressedBits::Contains ( const TfCompressedBits &  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 1376 of file compressedBits.h.

void TfCompressedBits::Count ( size_t *  numSet, size_t *  maxGap  ) const

inline

Count the bits set, and also return the largest gap between bits.

Definition at line 792 of file compressedBits.h.

TF_API void TfCompressedBits::Decompress

(

TfBits *

bits

)

const

Decompress the bits into a TfBits array.

size_t TfCompressedBits::FindNextSet ( size_t  index ) const

inline

Find the next bit set that is higher or equal to index. If no more set bits are found, index returns 'GetSize()'.

Note: This is a slow operation on TfCompressedBits. Please, use an iterator if possible. Iterators are fast!

Definition at line 725 of file compressedBits.h.

size_t TfCompressedBits::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()'.

Note: This is a slow operation on TfCompressedBits. Please, use an iterator if possible. Iterators are fast!

Definition at line 774 of file compressedBits.h.

size_t TfCompressedBits::FindNthSet ( size_t  nth ) const

inline

Returns the index of the n-th bit set in this bit set.

This function counts the set bits up to the nth bit, and returns the index of that n-th set bit. If there are less than nth bits set, returns GetSize().

Note: This operation is slower than using an iterator. For forward or reverse iteration, use the iterator instead.

Definition at line 691 of file compressedBits.h.

size_t TfCompressedBits::FindPrevSet ( 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()'.

Note: This is a slow operation on TfCompressedBits. Please, use an iterator if possible. Iterators are fast!

Definition at line 747 of file compressedBits.h.

static TF_API TfCompressedBits TfCompressedBits::FromString ( const std::string &  source )

static

Returns a bitset constructed from the supplied string representation.

The string representation can be either a RLE encoded bitset, such as '1x5-0x5-1x100', or a string of zeros and ones, such as '1111100000'. Note that whitespace anywhere in the string representation is ignored.

Any character other than whitespace, a digit, 'x' or '-' in the string representation is considered invalid. Invalid string representations will return an empty bitset. An empty string representation (or a string purely comprised of whitespace), however, is considered a valid representation describing an empty bitset.

size_t TfCompressedBits::GetAllocatedSize ( ) const

inline

Returns the amount of memory this object holds on to.

Definition at line 934 of file compressedBits.h.

TfCompressedBits::AllSetView TfCompressedBits::GetAllSetView ( ) const

inline

Definition at line 1922 of file compressedBits.h.

TfCompressedBits::AllUnsetView TfCompressedBits::GetAllUnsetView ( ) const

inline

Definition at line 1928 of file compressedBits.h.

TfCompressedBits::AllView TfCompressedBits::GetAllView ( ) const

inline

Definition at line 1916 of file compressedBits.h.

TF_API std::string TfCompressedBits::GetAsRLEString

(

)

const

Returns a string representing the bits for debugging with bits represented in run-length encoding form.

TF_API std::string TfCompressedBits::GetAsStringLeftToRight

(

)

const

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

TF_API std::string TfCompressedBits::GetAsStringRightToLeft

(

)

const

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

static const TfCompressedBits& TfCompressedBits::GetEmpty ( )

inlinestatic

Returns an empty TfBits.

Definition at line 1382 of file compressedBits.h.

size_t TfCompressedBits::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 827 of file compressedBits.h.

TF_API size_t TfCompressedBits::GetHash

(

)

const

Returns a hash for this instance.

size_t TfCompressedBits::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 838 of file compressedBits.h.

size_t TfCompressedBits::GetNumPlatforms ( ) const

inline

Returns the number of platforms (zeros or ones) in this bitset.

Definition at line 865 of file compressedBits.h.

size_t TfCompressedBits::GetNumSet ( ) const

inline

Returns the number of bits currently set in this array.

Definition at line 855 of file compressedBits.h.

size_t TfCompressedBits::GetNumSetPlatforms ( ) const

inline

Returns the number of set (ones) platforms in this bitset.

Definition at line 875 of file compressedBits.h.

size_t TfCompressedBits::GetNumUnsetPlatforms ( ) const

inline

Returns the number of unset (zeros) platforms in this bitset.

Definition at line 886 of file compressedBits.h.

TfCompressedBits::PlatformsView TfCompressedBits::GetPlatformsView ( ) const

inline

Definition at line 1934 of file compressedBits.h.

size_t TfCompressedBits::GetSize ( ) const

inline

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

Definition at line 814 of file compressedBits.h.

bool TfCompressedBits::HasNonEmptyDifference ( const TfCompressedBits &  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 1320 of file compressedBits.h.

bool TfCompressedBits::HasNonEmptyIntersection ( const TfCompressedBits &  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 1277 of file compressedBits.h.

bool TfCompressedBits::IsAnySet ( ) const

inline

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

Definition at line 909 of file compressedBits.h.

bool TfCompressedBits::IsAnyUnset ( ) const

inline

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

Definition at line 915 of file compressedBits.h.

bool TfCompressedBits::IsEmpty ( ) const

inline

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

Definition at line 820 of file compressedBits.h.

bool TfCompressedBits::IsSet ( size_t  index ) const

inline

Returns true, if bit # index is set.

Note: This is a slow operation on TfCompressedBits. Please, use an iterator if possible. Iterators are fast!

Definition at line 673 of file compressedBits.h.

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

inline

Returns true if this != rhs.

Definition at line 1015 of file compressedBits.h.

TfCompressedBits TfCompressedBits::operator& ( const TfCompressedBits &  rhs ) const

inline

Returns these bits and'ed with rhs.

Definition at line 1066 of file compressedBits.h.

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

inline

Ands these bits with the rhs bits.

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

Definition at line 1023 of file compressedBits.h.

TfCompressedBits TfCompressedBits::operator- ( const TfCompressedBits &  rhs ) const

inline

Returns bits with all the bits in rhs removed from these bits.

Definition at line 1213 of file compressedBits.h.

TfCompressedBits& TfCompressedBits::operator-= ( const TfCompressedBits &  rhs )

inline

Removes all bits in the rhs bits from these bits.

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

Definition at line 1167 of file compressedBits.h.

TfCompressedBits TfCompressedBits::operator<< ( size_t  bits ) const

inline

Returns bits shifted to the left.

Definition at line 1262 of file compressedBits.h.

TfCompressedBits& TfCompressedBits::operator<<= ( size_t  bits )

inline

Shifts to the left (see ShiftLeft)

Definition at line 1255 of file compressedBits.h.

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

inline

Assignment operator

Definition at line 407 of file compressedBits.h.

TfCompressedBits& TfCompressedBits::operator= ( TfCompressedBits &&  rhs )

inline

Move assignment operator.

Definition at line 421 of file compressedBits.h.

bool TfCompressedBits::operator== ( const TfCompressedBits &  rhs ) const

inline

Returns true if this == rhs.

Definition at line 987 of file compressedBits.h.

TfCompressedBits TfCompressedBits::operator>> ( size_t  bits ) const

inline

Returns bits shifted to the right.

Definition at line 1247 of file compressedBits.h.

TfCompressedBits& TfCompressedBits::operator>>= ( size_t  bits )

inline

Shifts to the right (see ShiftRight)

Definition at line 1240 of file compressedBits.h.

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

inline

Returns bit at index.

Note: This is a slow operation on TfCompressedBits!

Definition at line 1234 of file compressedBits.h.

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

inline

Returns these bits xor'ed with rhs.

Definition at line 1156 of file compressedBits.h.

TfCompressedBits& TfCompressedBits::operator^= ( const TfCompressedBits &  rhs )

inline

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.

Definition at line 1134 of file compressedBits.h.

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

inline

Returns these bits or'ed with the rhs.

Definition at line 1123 of file compressedBits.h.

TfCompressedBits& TfCompressedBits::operator|= ( const TfCompressedBits &  rhs )

inline

Ors these bits with the rhs bits.

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

Definition at line 1076 of file compressedBits.h.

void TfCompressedBits::ResizeKeepContents ( size_t  num )

inline

Resize the bitset, while keeping the contents, unless trimmed.

Definition at line 438 of file compressedBits.h.

void TfCompressedBits::Set ( size_t  index )

inline

Sets bit # index to zero.

Note: This is a slow operation on TfCompressedBits!

Definition at line 525 of file compressedBits.h.

void TfCompressedBits::SetAll ( )

inline

Sets all bits to one.

Definition at line 497 of file compressedBits.h.

void TfCompressedBits::SetRange ( size_t  first, size_t  last  )

inline

Sets the bit within the range of first and last.

Note: This is a slow operation on TfCompressedBits!

Definition at line 538 of file compressedBits.h.

void TfCompressedBits::ShiftLeft ( size_t  bits )

inline

Shift this bitset a given number of bits to the left, and extend the right with zeroes.

Definition at line 615 of file compressedBits.h.

void TfCompressedBits::ShiftRight ( size_t  bits )

inline

Shift this bitset a given number of bits to the right, and extend to the left with zeroes.

Definition at line 582 of file compressedBits.h.

void TfCompressedBits::Swap ( TfCompressedBits &  rhs )

inline

Provides a fast swap.

Definition at line 477 of file compressedBits.h.

---

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

• pxr/base/tf/compressedBits.h