7#ifndef PXR_BASE_TF_BITS_H
8#define PXR_BASE_TF_BITS_H
11#include "pxr/base/tf/api.h"
24PXR_NAMESPACE_OPEN_SCOPE
53 enum Mode { All, AllSet, AllUnset };
62 size_t operator()(
TfBits const &bits)
const {
73 size_t operator()(
TfBits const &bits)
const {
95 TfBits(
size_t num,
size_t first,
size_t last)
103 }
else if (first == 0 && last >= (num - 1)) {
107 for (
size_t i = first; i <= last; ++i)
117 _numSet .Store(rhs._numSet.Load());
118 _firstSet .Store(rhs._firstSet.Load());
119 _lastSet .Store(rhs._lastSet.Load());
120 _numWords = rhs._numWords;
121 _bits = _Alloc(_numWords);
124 for (
size_t i = 0; i < _numWords; ++i)
125 _bits[i] = rhs._bits[i];
139 _Free(_bits, _numWords);
152 if (_numWords != rhs._numWords) {
153 _Free(_bits, _numWords);
154 _bits = _Alloc(rhs._numWords);
158 _numSet .Store(rhs._numSet.Load());
159 _firstSet .Store(rhs._firstSet.Load());
160 _lastSet .Store(rhs._lastSet.Load());
161 _numWords = rhs._numWords;
164 for (
size_t i = 0; i < _numWords; ++i)
165 _bits[i] = rhs._bits[i];
187 if (_bits && _num == num)
190 _Free(_bits, _numWords);
194 _firstSet .Store(-1);
196 _numWords = (num + 63) >> 6;
197 _bits = _Alloc(_numWords);
203 _bits[_numWords - 1] = 0;
217 size_t numWordsToCopy =
TfMin(temp._numWords, _numWords);
219 for(
size_t i=0; i<numWordsToCopy; ++i)
220 temp._bits[i] = _bits[i];
227 temp._ClearTrailingBits();
231 temp._numSet.Store(-1);
232 temp._firstSet.Store(-1);
233 temp._lastSet.Store(-1);
240 temp._numSet.Store(_numSet.Load());
241 const size_t firstSet = _firstSet.Load();
242 temp._firstSet.Store(firstSet < _num ? firstSet : num);
243 const size_t lastSet = _lastSet.Load();
244 temp._lastSet.Store(lastSet < _num ? lastSet : num);
266 std::swap(_num, rhs._num);
270 _numSet.NonAtomicSwap(rhs._numSet);
271 _firstSet.NonAtomicSwap(rhs._firstSet);
272 _lastSet.NonAtomicSwap(rhs._lastSet);
274 if (_numWords == 1 && rhs._numWords == 1) {
281 std::swap(_inlineData, rhs._inlineData);
283 }
else if (_numWords == 1) {
292 rhs._inlineData = _inlineData;
293 rhs._bits = &rhs._inlineData;
295 }
else if (rhs._numWords == 1) {
304 _inlineData = rhs._inlineData;
305 _bits = &_inlineData;
313 std::swap(_bits, rhs._bits);
319 std::swap(_numWords, rhs._numWords);
332 memset(_bits, 0x00, _numWords << 3);
334 _firstSet.Store(_num);
335 _lastSet.Store(_num);
342 memset(_bits, 0xff, _numWords << 3);
345 _lastSet.Store(_num > 0 ? _num-1 : 0);
348 _ClearTrailingBits();
357 uint64_t mask = UINT64_C(1) << (index & 63);
359 if (_bits[index >> 6] & mask)
361 const size_t numSet = _numSet.Load();
362 TF_AXIOM(numSet ==
size_t(-1) || numSet > 0);
364 if (numSet !=
size_t(-1))
366 if (index == _firstSet.Load())
368 if (index == _lastSet.Load())
371 _bits[index >> 6] ^= mask;
381 uint64_t mask = UINT64_C(1) << (index & 63);
383 if (!(_bits[index >> 6] & mask))
385 const size_t numSet = _numSet.Load();
386 TF_AXIOM(numSet ==
size_t(-1) || numSet < _num);
388 if (numSet !=
size_t(-1))
390 if (index < _firstSet.Load())
391 _firstSet.Store(index);
392 const size_t lastSet = _lastSet.Load();
393 if (index > lastSet || lastSet == _num)
394 _lastSet.Store(index);
396 _bits[index >> 6] |= mask;
416 return _bits[index >> 6] & (UINT64_C(1) << (index & 63));
424 if (ARCH_UNLIKELY(index >= _num)) {
428 size_t startBit = index & 63;
431 if (_bits[index >> 6] & (UINT64_C(1) << startBit))
434 return _FindNextSet(index, startBit);
442 if (ARCH_UNLIKELY(index >= _num)) {
446 size_t startBit = index & 63;
449 if (_bits[index >> 6] & (UINT64_C(1) << startBit))
452 return _FindPrevSet(index, startBit);
460 if (ARCH_UNLIKELY(index >= _num)) {
464 size_t startBit = index & 63;
467 if (!(_bits[index >> 6] & (UINT64_C(1) << startBit)))
470 return _FindNextUnset(index, startBit);
493 size_t firstSet = _firstSet.Load();
494 if (firstSet ==
size_t(-1)) {
496 _firstSet.Store(firstSet);
508 size_t lastSet = _lastSet.Load();
509 if (lastSet ==
size_t(-1)) {
512 _lastSet.Store(lastSet);
523 size_t numSet = _numSet.Load();
524 if (numSet ==
size_t(-1)) {
525 numSet = _CountNumSet();
526 _numSet.Store(numSet);
575 size_t memUsed =
sizeof(
TfBits);
579 memUsed += _numWords << 3;
613 return !(*
this == rhs);
706 if (firstSet < _num && rhsFirstSet < _num)
708 firstSet =
TfMax(firstSet, rhsFirstSet);
711 if (firstSet <= lastSet)
713 size_t offset = firstSet >> 6;
714 size_t numWords = (lastSet >> 6) + 1 - offset;
717 uint64_t *p0 = _bits + offset;
718 uint64_t *p1 = rhs._bits + offset;
720 for(
size_t n=numWords; n>0; n--)
723 if (uint64_t word = *p0)
756 if (firstSet < rhsFirstSet || lastSet > rhsLastSet ||
757 firstSet > rhsLastSet || lastSet < rhsFirstSet ||
761 size_t offset = firstSet >> 6;
762 size_t numWords = (lastSet >> 6) + 1 - offset;
765 uint64_t *p0 = _bits + offset;
766 uint64_t *p1 = rhs._bits + offset;
768 for(
size_t n=numWords; n>0; n--)
771 if (uint64_t word = *p0)
801 using iterator_category = std::forward_iterator_tag;
802 using value_type =
const size_t;
803 using reference =
const size_t &;
804 using pointer =
const size_t *;
805 using difference_type =
const size_t;
808 : _bits(NULL), _index(0) {}
810 reference operator*()
const {
return dereference(); }
811 pointer operator->()
const {
return &(dereference()); }
813 const_iterator& operator++() {
818 const_iterator operator++(
int) {
819 const_iterator r(*
this);
824 bool operator==(
const const_iterator& rhs)
const {
828 bool operator!=(
const const_iterator& rhs)
const {
838 const TfBits *bits,
size_t index)
839 : _bits(bits), _index(index) {}
841 bool equal(
const const_iterator &rhs)
const {
842 return _bits == rhs._bits && _index == rhs._index;
849 _index = _bits->FindNextSet(_index);
850 else if (mode == AllUnset)
851 _index = _bits->FindNextUnset(_index);
854 const size_t &dereference()
const {
868 typedef const_iterator iterator;
870 const_iterator begin()
const {
874 else if (mode == AllUnset)
877 return const_iterator(_bits, start);
880 const_iterator end()
const {
881 return const_iterator(_bits, _bits->
GetSize());
887 return begin() == end();
902 using AllView = View<All>;
903 using AllSetView = View<AllSet>;
904 using AllUnsetView = View<AllUnset>;
930 size_t _CountNumSet()
const;
936 size_t _FindNextSet(
size_t index,
size_t startBit)
const;
942 size_t _FindPrevSet(
size_t index,
size_t startBit)
const;
948 size_t _FindNextUnset(
size_t index,
size_t startBit)
const;
953 void _ClearTrailingBits();
958 void _Or(
const TfBits &rhs);
965 uint64_t *_Alloc(
size_t numWords)
973 return new uint64_t[numWords];
977 static void _Free(uint64_t *data,
size_t numWords)
993 class _RelaxedAtomicSize_t
996 _RelaxedAtomicSize_t()
1000 explicit _RelaxedAtomicSize_t(
size_t n)
1005 _n.fetch_add(1, std::memory_order_relaxed);
1009 _n.fetch_sub(1, std::memory_order_relaxed);
1012 size_t Load()
const {
1013 return _n.load(std::memory_order_relaxed);
1016 void Store(
size_t n) {
1017 _n.store(n, std::memory_order_relaxed);
1023 void NonAtomicSwap(_RelaxedAtomicSize_t &other) {
1024 const size_t n = _n.load(std::memory_order_relaxed);
1025 const size_t o = other._n.load(std::memory_order_relaxed);
1026 _n.store(o, std::memory_order_relaxed);
1027 other._n.store(n, std::memory_order_relaxed);
1031 std::atomic<size_t> _n;
1038 mutable _RelaxedAtomicSize_t _numSet;
1041 mutable _RelaxedAtomicSize_t _firstSet;
1042 mutable _RelaxedAtomicSize_t _lastSet;
1051 uint64_t _inlineData;
1056struct Tf_ShouldIterateOverCopy<
TfBits::AllView > :
1062struct Tf_ShouldIterateOverCopy<
TfBits::AllSetView > :
1068struct Tf_ShouldIterateOverCopy<
TfBits::AllUnsetView > :
1077PXR_NAMESPACE_CLOSE_SCOPE
Low-level utilities for informing users of various internal and external diagnostic conditions.
A simple iterator adapter for STL containers.
bool IsEmpty() const
Return true, if the view is empty.
Fast bit array that keeps track of the number of bits set and can find the next set in a timely manne...
TfBits(size_t num, size_t first, size_t last)
Constructs a fixed size bit array, with a range of bits set.
void SetAll()
Sets all bits to one.
TF_API TfBits & operator^=(const TfBits &rhs)
Xors these bits with the rhs bits.
size_t GetSize() const
Returns the size of the bit array, ie.
size_t FindNextUnset(size_t index) const
Finds the next unset bit that has a higher or equal index than index.
bool AreAllSet() const
Returns true, if all the bits in this bit array are set.
TF_API TfBits & Complement()
Flips all bits.
TF_API bool operator==(const TfBits &rhs) const
Returns true if this == rhs.
TF_API std::string GetAsStringRightToLeft() const
Returns a string representing the bits for debugging with bits ordered from right to left with increa...
TfBits(TfBits &&rhs)
Move constructor.
bool Contains(const TfBits &rhs) const
Returns true if this bit array contains rhs by computing: (rhs - this).GetNumSet() == 0.
bool IsAnySet() const
Returns true, if there is at least a single set bit.
TfBits operator|(const TfBits &rhs) const
Returns these bits or'ed with rhs.
TfBits(size_t num=0)
Constructs a fixed size bit array, clears all bits.
void Clear(size_t index)
Clears bit # index to zero.
TfBits operator&(const TfBits &rhs) const
Returns these bits and'ed with rhs.
bool AreContiguouslySet() const
Returns true if the set bits in this bit array are contiguous.
AllUnsetView GetAllUnsetView() const
Returns an iteratable view for the bits that steps over all unset bits.
void Swap(TfBits &rhs)
Provides a fast swap.
size_t GetLastSet() const
Returns the index of the last bit set in the bit array.
TF_API void OrSubset(const TfBits &rhs)
Combines two differently sized TfBits using an or operator.
void Set(size_t index)
Sets bit # index to one.
TF_API std::string GetAsStringLeftToRight() const
Returns a string representing the bits for debugging with bits ordered from left to right with increa...
bool IsSet(size_t index) const
Returns true, if bit # index is set.
bool HasNonEmptyDifference(const TfBits &rhs) const
Returns true if the result of an asymmetric set different is non-zero.
bool operator!=(const TfBits &rhs) const
Returns true if this != rhs.
bool IsEmpty() const
Returns true if this bit array is empty, i.e.
TF_API TfBits & operator&=(const TfBits &rhs)
Ands these bits with the rhs bits.
void Assign(size_t index, bool val)
Assigns val to bit # index.
size_t GetFirstSet() const
Returns the index of the first bit set in the bit array.
TF_API TfBits & operator|=(const TfBits &rhs)
Ors these bits with the rhs bits.
void ClearAll()
Clears all bits to zero.
bool IsAnyUnset() const
Returns true, if there is at least a single unset bit.
void ResizeKeepContent(size_t num)
Resizes the size of the bit array while keeping the content.
TfBits operator^(const TfBits &rhs) const
Returns these bits xor'ed with rhs.
TF_API size_t GetHash() const
Returns a hash for this instance.
size_t GetAllocatedSize() const
Returns the amount of memory this object holds on to.
TF_API TfBits & operator-=(const TfBits &rhs)
Removes all bits in the rhs bits from these bits.
AllSetView GetAllSetView() const
Returns an iteratable view for the bits that steps over all set bits.
size_t FindPrevSet(size_t index) const
Finds the prev set bit that has a lower or equal index than index.
TfBits & operator=(const TfBits &rhs)
Assignment operator.
bool HasNonEmptyIntersection(const TfBits &rhs) const
Returns true if the result of the intersection with rhs would be non-zero.
void Resize(size_t num)
Resizes the bit array, however, the bits are left uninitialized.
TfBits & operator=(TfBits &&rhs)
Move assignment operator.
AllView GetAllView() const
Returns an iteratable view for the bits that steps over all bits.
TfBits(const TfBits &rhs)
Copy-constructs a fixed size bit array.
bool AreAllUnset() const
Returns true, if all the bits in this bit array are unset.
size_t FindNextSet(size_t index) const
Finds the next set bit that has a higher or equal index than index.
bool operator[](size_t index) const
Returns bit at index.
size_t GetNumSet() const
Returns the number of bits currently set in this array.
static size_t Combine(Args &&... args)
Produce a hash code by combining the hash codes of several objects.
GF_API std::ostream & operator<<(std::ostream &, const GfBBox3d &)
Output a GfBBox3d using the format [(range) matrix zeroArea].
T TfMax(const T &v1, const T &v2)
Returns the larger of the two given values.
T TfMin(const T &v1, const T &v2)
Returns the smaller of the two given values.
#define TF_AXIOM(cond)
Aborts if the condition cond is not met.
A hash functor for TfBits that is faster than Hash.
A file containing basic constants and definitions.