All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
bits.h
1//
2// Copyright 2024 Pixar
3//
4// Licensed under the terms set forth in the LICENSE.txt file available at
5// https://openusd.org/license.
6//
7#ifndef PXR_BASE_TF_BITS_H
8#define PXR_BASE_TF_BITS_H
9
10#include "pxr/base/arch/hints.h"
11#include "pxr/base/tf/api.h"
12#include "pxr/base/tf/hash.h"
13#include "pxr/base/tf/tf.h"
14#include "pxr/base/tf/hash.h"
17
18#include <atomic>
19#include <cstdint>
20#include <cstring>
21#include <iosfwd>
22#include <type_traits>
23
24PXR_NAMESPACE_OPEN_SCOPE
25
48class TfBits
49{
50public:
51
52 // View and iterator modes: All bits, all set bits, all unset bits.
53 enum Mode { All, AllSet, AllUnset };
54
61 struct Hash {
62 size_t operator()(TfBits const &bits) const {
63 return bits.GetHash();
64 }
65 };
66
72 struct FastHash {
73 size_t operator()(TfBits const &bits) const {
74 return TfHash::Combine(
75 bits.GetSize(),
76 bits.GetFirstSet(),
77 bits.GetLastSet(),
78 bits.GetNumSet());
79 }
80 };
81
82
85 explicit TfBits(size_t num=0)
86 {
87 _bits = NULL;
88 _numWords = 0;
89 Resize(num);
90 ClearAll();
91 }
92
95 TfBits(size_t num, size_t first, size_t last)
96 {
97 _bits = NULL;
98 _numWords = 0;
99 Resize(num);
100
101 if (num == 0) {
102 ClearAll();
103 } else if (first == 0 && last >= (num - 1)) {
104 SetAll();
105 } else {
106 ClearAll();
107 for (size_t i = first; i <= last; ++i)
108 Set(i);
109 }
110 }
111
114 TfBits(const TfBits &rhs)
115 {
116 _num = rhs._num;
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);
122
123 // This loop turns out to be faster than a memcpy.
124 for (size_t i = 0; i < _numWords; ++i)
125 _bits[i] = rhs._bits[i];
126 }
127
130 TfBits(TfBits &&rhs) : TfBits(0)
131 {
132 Swap(rhs);
133 }
134
138 {
139 _Free(_bits, _numWords);
140 }
141
145 {
146 // Early bail out.
147 if (this == &rhs) {
148 return *this;
149 }
150
151 // Avoid free-ing and reallocing if we have the same size
152 if (_numWords != rhs._numWords) {
153 _Free(_bits, _numWords);
154 _bits = _Alloc(rhs._numWords);
155 }
156
157 _num = rhs._num;
158 _numSet .Store(rhs._numSet.Load());
159 _firstSet .Store(rhs._firstSet.Load());
160 _lastSet .Store(rhs._lastSet.Load());
161 _numWords = rhs._numWords;
162
163 // This loop turns out to be faster than a memcpy.
164 for (size_t i = 0; i < _numWords; ++i)
165 _bits[i] = rhs._bits[i];
166
167 return (*this);
168 }
169
173 {
174 if (this == &rhs)
175 return *this;
176
177 Swap(rhs);
178
179 return *this;
180 }
181
185 void Resize(size_t num)
186 {
187 if (_bits && _num == num)
188 return;
189
190 _Free(_bits, _numWords);
191
192 _num = num;
193 _numSet .Store(-1);
194 _firstSet .Store(-1);
195 _lastSet .Store(-1);
196 _numWords = (num + 63) >> 6;
197 _bits = _Alloc(_numWords);
198
199 // By definition, the unused, trailing bits always needs to be
200 // initialized to 0 and all operations can assume they are 0.
201
202 if (_numWords)
203 _bits[_numWords - 1] = 0;
204 }
205
208 void ResizeKeepContent(size_t num)
209 {
210 if (num == _num)
211 return;
212
213 //XXX: We could try to be fancy and not re-allocate in certain cases.
214 TfBits temp(num);
215
216 // Figure out how much to copy.
217 size_t numWordsToCopy = TfMin(temp._numWords, _numWords);
218
219 for(size_t i=0; i<numWordsToCopy; ++i)
220 temp._bits[i] = _bits[i];
221
222 // Since we copy whole words above, we may need to clear out some
223 // trailing bits that have been copied when they shouldn't have.
224
225 if (num < _num) {
226
227 temp._ClearTrailingBits();
228
229 // Since we just have written directly to the _bits[] array, all
230 // cached information is invalid, so we need to mark it as such.
231 temp._numSet.Store(-1);
232 temp._firstSet.Store(-1);
233 temp._lastSet.Store(-1);
234
235 } else {
236
237 // Since in this case the bit array became bigger, we can keep the
238 // cached information. Need to be careful to keep the end markers
239 // as end markers.
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);
245 }
246
247 // Swap out our content /w the resized bits and delete the old one
248 // when exiting this scope.
249 Swap(temp);
250 }
251
256 TF_API
257 void OrSubset(const TfBits &rhs);
258
261 void Swap(TfBits &rhs)
262 {
263 if (this == &rhs)
264 return;
265
266 std::swap(_num, rhs._num);
267
268 // Because Swap is a mutating operation, we do not require atomic
269 // updates to the set-bits members.
270 _numSet.NonAtomicSwap(rhs._numSet);
271 _firstSet.NonAtomicSwap(rhs._firstSet);
272 _lastSet.NonAtomicSwap(rhs._lastSet);
273
274 if (_numWords == 1 && rhs._numWords == 1) {
275
276 // Both sides use inline storage.
277 //
278 // We can just swap the inline data. Both _bits & rhs._bits will
279 // already point their respective inline storage.
280
281 std::swap(_inlineData, rhs._inlineData);
282
283 } else if (_numWords == 1) {
284
285 // 'this' uses inline storage; 'rhs' uses heap-allocated storage.
286 //
287 // Transfer rhs's heap-allocated data to ourself and copy our inline
288 // data to rhs. We leave our _inlineData unchanged as it is now
289 // essentially garbage.
290
291 _bits = rhs._bits;
292 rhs._inlineData = _inlineData;
293 rhs._bits = &rhs._inlineData;
294
295 } else if (rhs._numWords == 1) {
296
297 // 'rhs' uses inline storage; 'this' uses heap-allocated storage.
298 //
299 // Transfer our heap-allocated data to rhs and copy rhs's inline
300 // data to our inline storage. We leave rhs._inlineData unchanged
301 // as it is now essentially garbage.
302
303 rhs._bits = _bits;
304 _inlineData = rhs._inlineData;
305 _bits = &_inlineData;
306
307 } else {
308
309 // Both sides use heap-allocated storage.
310 //
311 // We can just swap the _bits pointers and ignore _inlineData.
312
313 std::swap(_bits, rhs._bits);
314
315 }
316
317 // Swap _numWords only after swapping data. Otherwise, reasoning about
318 // whose _bits & _inlineData to update gets confusing.
319 std::swap(_numWords, rhs._numWords);
320 }
321
322 // Swap overload for unqualified calls in generic code.
323 //
324 friend void swap(TfBits &lhs, TfBits &rhs) {
325 lhs.Swap(rhs);
326 }
327
330 void ClearAll()
331 {
332 memset(_bits, 0x00, _numWords << 3);
333 _numSet.Store(0);
334 _firstSet.Store(_num);
335 _lastSet.Store(_num);
336 }
337
340 void SetAll()
341 {
342 memset(_bits, 0xff, _numWords << 3);
343 _numSet.Store(_num);
344 _firstSet.Store(0);
345 _lastSet.Store(_num > 0 ? _num-1 : 0);
346
347 // Clear out unused bits...
348 _ClearTrailingBits();
349 }
350
353 void Clear(size_t index)
354 {
355 TF_AXIOM(index < _num);
356
357 uint64_t mask = UINT64_C(1) << (index & 63);
358
359 if (_bits[index >> 6] & mask)
360 {
361 const size_t numSet = _numSet.Load();
362 TF_AXIOM(numSet == size_t(-1) || numSet > 0);
363
364 if (numSet != size_t(-1))
365 _numSet.Decrement();
366 if (index == _firstSet.Load())
367 _firstSet.Store(-1);
368 if (index == _lastSet.Load())
369 _lastSet.Store(-1);
370
371 _bits[index >> 6] ^= mask;
372 }
373 }
374
377 void Set(size_t index)
378 {
379 TF_AXIOM(index < _num);
380
381 uint64_t mask = UINT64_C(1) << (index & 63);
382
383 if (!(_bits[index >> 6] & mask))
384 {
385 const size_t numSet = _numSet.Load();
386 TF_AXIOM(numSet == size_t(-1) || numSet < _num);
387
388 if (numSet != size_t(-1))
389 _numSet.Increment();
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);
395
396 _bits[index >> 6] |= mask;
397 }
398 }
399
402 void Assign(size_t index, bool val)
403 {
404 if (val)
405 Set(index);
406 else
407 Clear(index);
408 }
409
412 bool IsSet(size_t index) const
413 {
414 TF_AXIOM(index < _num);
415
416 return _bits[index >> 6] & (UINT64_C(1) << (index & 63));
417 }
418
422 size_t FindNextSet(size_t index) const
423 {
424 if (ARCH_UNLIKELY(index >= _num)) {
425 return _num;
426 }
427
428 size_t startBit = index & 63;
429
430 // Early out for bit set...
431 if (_bits[index >> 6] & (UINT64_C(1) << startBit))
432 return index;
433
434 return _FindNextSet(index, startBit);
435 }
436
440 size_t FindPrevSet(size_t index) const
441 {
442 if (ARCH_UNLIKELY(index >= _num)) {
443 return _num;
444 }
445
446 size_t startBit = index & 63;
447
448 // Early out for bit set...
449 if (_bits[index >> 6] & (UINT64_C(1) << startBit))
450 return index;
451
452 return _FindPrevSet(index, startBit);
453 }
454
458 size_t FindNextUnset(size_t index) const
459 {
460 if (ARCH_UNLIKELY(index >= _num)) {
461 return _num;
462 }
463
464 size_t startBit = index & 63;
465
466 // Early out for bit set...
467 if (!(_bits[index >> 6] & (UINT64_C(1) << startBit)))
468 return index;
469
470 return _FindNextUnset(index, startBit);
471 }
472
475 size_t GetSize() const
476 {
477 return _num;
478 }
479
482 bool IsEmpty() const
483 {
484 return _num == 0;
485 }
486
490 size_t GetFirstSet() const
491 {
492 // See comment at top of this file on why this is thread safe.
493 size_t firstSet = _firstSet.Load();
494 if (firstSet == size_t(-1)) {
495 firstSet = FindNextSet(0);
496 _firstSet.Store(firstSet);
497 }
498
499 return firstSet;
500 }
501
505 size_t GetLastSet() const
506 {
507 // See comment at top of this file on why this is thread safe.
508 size_t lastSet = _lastSet.Load();
509 if (lastSet == size_t(-1)) {
510 // Also works if _num is 0.
511 lastSet = FindPrevSet(_num-1);
512 _lastSet.Store(lastSet);
513 }
514
515 return lastSet;
516 }
517
520 size_t GetNumSet() const
521 {
522 // See comment at top of this file on why this is thread safe.
523 size_t numSet = _numSet.Load();
524 if (numSet == size_t(-1)) {
525 numSet = _CountNumSet();
526 _numSet.Store(numSet);
527 }
528
529 return numSet;
530 }
531
534 bool AreAllSet() const
535 {
536 // Note that "not IsAnyUnset();" is not cached because FindNextUnset(0);
537 // isn't. Therefore we use GetNumSet() which is cached.
538 return GetNumSet() == GetSize();
539 }
540
543 bool AreAllUnset() const
544 {
545 return !IsAnySet();
546 }
547
550 bool IsAnySet() const
551 {
552 return GetFirstSet() < GetSize();
553 }
554
557 bool IsAnyUnset() const
558 {
559 return !AreAllSet();
560 }
561
567 {
568 return GetNumSet() == GetLastSet() - GetFirstSet() + 1;
569 }
570
573 size_t GetAllocatedSize() const
574 {
575 size_t memUsed = sizeof(TfBits);
576
577 // Note that up to 64 bits are inlined, cf. _Alloc();
578 if (_numWords > 1)
579 memUsed += _numWords << 3;
580
581 return memUsed;
582 }
583
586 TF_API
587 size_t GetHash() const;
588
592 TF_API
593 std::string GetAsStringLeftToRight() const;
594
598 TF_API
599 std::string GetAsStringRightToLeft() const;
600
603
606 TF_API
607 bool operator==(const TfBits &rhs) const;
608
611 bool operator!=(const TfBits &rhs) const
612 {
613 return !(*this == rhs);
614 }
615
620 TF_API
622
625 TfBits operator&(const TfBits &rhs) const
626 {
627 TfBits r(*this);
628 r &= rhs;
629 return r;
630 }
631
636 TF_API
638
641 TfBits operator|(const TfBits &rhs) const
642 {
643 TfBits r(*this);
644 r |= rhs;
645 return r;
646 }
647
653 TF_API
655
658 TfBits operator^(const TfBits &rhs) const
659 {
660 TfBits r(*this);
661 r ^= rhs;
662 return r;
663 }
664
670 TF_API
672
677 TF_API
679
682 bool operator[](size_t index) const
683 {
684 return IsSet(index);
685 }
686
688
689
696 bool HasNonEmptyIntersection(const TfBits &rhs) const
697 {
698 TF_AXIOM(_num == rhs._num);
699
700 // Limit the bit operations to where we have bits set in both of
701 // the two sets.
702 size_t firstSet = GetFirstSet();
703 size_t rhsFirstSet = rhs.GetFirstSet();
704
705 // Nothing to compare if either set is empty.
706 if (firstSet < _num && rhsFirstSet < _num)
707 {
708 firstSet = TfMax(firstSet, rhsFirstSet);
709 size_t lastSet = TfMin(GetLastSet(), rhs.GetLastSet());
710
711 if (firstSet <= lastSet)
712 {
713 size_t offset = firstSet >> 6;
714 size_t numWords = (lastSet >> 6) + 1 - offset;
715
716 // Have to compare the bits.
717 uint64_t *p0 = _bits + offset;
718 uint64_t *p1 = rhs._bits + offset;
719
720 for(size_t n=numWords; n>0; n--)
721 {
722 // Note: This assumes trailing bits in last word to be zero.
723 if (uint64_t word = *p0)
724 if (word & *p1)
725 return true;
726 p0++;
727 p1++;
728 }
729 }
730 }
731
732 return false;
733 }
734
740 bool HasNonEmptyDifference(const TfBits &rhs) const
741 {
742 TF_AXIOM(_num == rhs._num);
743
744 // Limit the bit operations to where we have bits set in the first set.
745 size_t firstSet = GetFirstSet();
746
747 // The difference is empty if the first set is empty.
748 if (firstSet < _num)
749 {
750 size_t lastSet = GetLastSet();
751 size_t rhsFirstSet = rhs.GetFirstSet();
752 size_t rhsLastSet = rhs.GetLastSet();
753
754 // Check for trivial non-empty difference (we know that the first
755 // set is not empty).
756 if (firstSet < rhsFirstSet || lastSet > rhsLastSet ||
757 firstSet > rhsLastSet || lastSet < rhsFirstSet ||
758 GetNumSet() > rhs.GetNumSet())
759 return true;
760
761 size_t offset = firstSet >> 6;
762 size_t numWords = (lastSet >> 6) + 1 - offset;
763
764 // Have to compare the bits.
765 uint64_t *p0 = _bits + offset;
766 uint64_t *p1 = rhs._bits + offset;
767
768 for(size_t n=numWords; n>0; n--)
769 {
770 // Note: This assumes trailing bits in last word to be the same.
771 if (uint64_t word = *p0)
772 if (word & ~*p1)
773 return true;
774 p0++;
775 p1++;
776 }
777 }
778
779 return false;
780 }
781
787 bool Contains(const TfBits &rhs) const
788 {
789 return !rhs.HasNonEmptyDifference(*this);
790 }
791
794 template <Mode mode>
795 class View
796 {
797 public:
798 class const_iterator
799 {
800 public:
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;
806
807 const_iterator()
808 : _bits(NULL), _index(0) {}
809
810 reference operator*() const { return dereference(); }
811 pointer operator->() const { return &(dereference()); }
812
813 const_iterator& operator++() {
814 increment();
815 return *this;
816 }
817
818 const_iterator operator++(int) {
819 const_iterator r(*this);
820 increment();
821 return r;
822 }
823
824 bool operator==(const const_iterator& rhs) const {
825 return equal(rhs);
826 }
827
828 bool operator!=(const const_iterator& rhs) const {
829 return !equal(rhs);
830 }
831
832 private:
833
834 friend class View;
835
836 // Ctor.
837 const_iterator(
838 const TfBits *bits, size_t index)
839 : _bits(bits), _index(index) {}
840
841 bool equal(const const_iterator &rhs) const {
842 return _bits == rhs._bits && _index == rhs._index;
843 }
844
845 void increment() {
846 ++_index;
847
848 if (mode == AllSet)
849 _index = _bits->FindNextSet(_index);
850 else if (mode == AllUnset)
851 _index = _bits->FindNextUnset(_index);
852 }
853
854 const size_t &dereference() const {
855 return _index;
856 }
857
858 private:
859
860 // The bits being iterated over.
861 const TfBits *_bits;
862
863 // The index.
864 size_t _index;
865 };
866
867 // Support for TF_FOR_ALL.
868 typedef const_iterator iterator;
869
870 const_iterator begin() const {
871 size_t start = 0;
872 if (mode == AllSet)
873 start = _bits->GetFirstSet();
874 else if (mode == AllUnset)
875 start = _bits->FindNextUnset(0);
876
877 return const_iterator(_bits, start);
878 }
879
880 const_iterator end() const {
881 return const_iterator(_bits, _bits->GetSize());
882 }
883
886 bool IsEmpty() const {
887 return begin() == end();
888 }
889
890 private:
891
892 // The TfBits can create new views.
893 friend class TfBits;
894
895 // Ctor.
896 View(const TfBits *bits)
897 : _bits(bits) {}
898
899 const TfBits *_bits;
900 };
901
902 using AllView = View<All>;
903 using AllSetView = View<AllSet>;
904 using AllUnsetView = View<AllUnset>;
905
909 return AllView(this);
910 }
911
915 return AllSetView(this);
916 }
917
921 return AllUnsetView(this);
922 }
923
924// -----------------------------------------------------------------------------
925
926private:
927
928 // This counts the number of set bits.
929 TF_API
930 size_t _CountNumSet() const;
931
932 // This is a helper method for FindNextSet so that we don't have to inline
933 // the whole method. This gives us the best compromise for speed and code
934 // size.
935 TF_API
936 size_t _FindNextSet(size_t index, size_t startBit) const;
937
938 // This is a helper method for FindPrevSet so that we don't have to inline
939 // the whole method. This gives us the best compromise for speed and code
940 // size.
941 TF_API
942 size_t _FindPrevSet(size_t index, size_t startBit) const;
943
944 // This is a helper method for FindNextUnset so that we don't have to inline
945 // the whole method. This gives us the best compromise for speed and code
946 // size.
947 TF_API
948 size_t _FindNextUnset(size_t index, size_t startBit) const;
949
950 // This is a helper method that clear out unused bits in the last word of
951 // the bit array.
952 TF_API
953 void _ClearTrailingBits();
954
955 // Helper that performs the or operation on these bits where rhs must have
956 // same or less # of bits.
957 TF_API
958 void _Or(const TfBits &rhs);
959
960 // Allocates the bits array with \p numWords words.
961 // If \p numWords is 0, NULL is returned. If \p numWords is 1, inline
962 // data will be used (to avoid an extra malloc).
963 // Returned memory must be freed with _Free().
964
965 uint64_t *_Alloc(size_t numWords)
966 {
967 if (!numWords)
968 return NULL;
969
970 if (numWords == 1)
971 return &_inlineData;
972
973 return new uint64_t[numWords];
974 }
975
976 // Frees data allocated with _Alloc().
977 static void _Free(uint64_t *data, size_t numWords)
978 {
979 if (numWords > 1)
980 delete [] data;
981 }
982
983private:
984
985 // # of bits in this array.
986 size_t _num;
987
988 // Wrapper class for lazily-initialized size_t members.
989 //
990 // These members only require relaxed ordering and we want to avoid
991 // unintentionally scribbling mfence all over the place with the
992 // sequentially consistent std::atomic operator=(size_t).
993 class _RelaxedAtomicSize_t
994 {
995 public:
996 _RelaxedAtomicSize_t()
997 : _n{}
998 {}
999
1000 explicit _RelaxedAtomicSize_t(size_t n)
1001 : _n{n}
1002 {}
1003
1004 void Increment() {
1005 _n.fetch_add(1, std::memory_order_relaxed);
1006 }
1007
1008 void Decrement() {
1009 _n.fetch_sub(1, std::memory_order_relaxed);
1010 }
1011
1012 size_t Load() const {
1013 return _n.load(std::memory_order_relaxed);
1014 }
1015
1016 void Store(size_t n) {
1017 _n.store(n, std::memory_order_relaxed);
1018 }
1019
1020 // Note, it's not possible to do an atomic swap of two memory
1021 // locations. Provide a non-atomic swap operation to be used when
1022 // no concurrent operations may be taking place. See TfBits::Swap.
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);
1028 }
1029
1030 private:
1031 std::atomic<size_t> _n;
1032 };
1033
1034 // See comment at top of this file on why the usage of _numSet, _firstSet
1035 // and _lastSet is thread safe.
1036
1037 // # of bits set in this array (set to size_t(-1) when invalid).
1038 mutable _RelaxedAtomicSize_t _numSet;
1039
1040 // Cached first and last set bits (set to size_t(-1) when invalid).
1041 mutable _RelaxedAtomicSize_t _firstSet;
1042 mutable _RelaxedAtomicSize_t _lastSet;
1043
1044 // Size in uint64_t of the bits array.
1045 size_t _numWords;
1046
1047 // Pointer to the actual data.
1048 uint64_t *_bits;
1049
1050 // Data used if _num <= 64.
1051 uint64_t _inlineData;
1052};
1053
1054// Specialize this template so TfIterator knows to retain a copy when iterating.
1055template<>
1056struct Tf_ShouldIterateOverCopy< TfBits::AllView > :
1057 std::true_type
1058{
1059};
1060
1061template<>
1062struct Tf_ShouldIterateOverCopy< TfBits::AllSetView > :
1063 std::true_type
1064{
1065};
1066
1067template<>
1068struct Tf_ShouldIterateOverCopy< TfBits::AllUnsetView > :
1069 std::true_type
1070{
1071};
1072
1074// \ingroup group_tf_DebuggingOutput
1075TF_API std::ostream & operator<<(std::ostream &out, const TfBits & bits);
1076
1077PXR_NAMESPACE_CLOSE_SCOPE
1078
1079#endif
Low-level utilities for informing users of various internal and external diagnostic conditions.
A simple iterator adapter for STL containers.
Iterator support.
Definition: bits.h:796
bool IsEmpty() const
Return true, if the view is empty.
Definition: bits.h:886
Fast bit array that keeps track of the number of bits set and can find the next set in a timely manne...
Definition: bits.h:49
TfBits(size_t num, size_t first, size_t last)
Constructs a fixed size bit array, with a range of bits set.
Definition: bits.h:95
void SetAll()
Sets all bits to one.
Definition: bits.h:340
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.
Definition: bits.h:475
size_t FindNextUnset(size_t index) const
Finds the next unset bit that has a higher or equal index than index.
Definition: bits.h:458
bool AreAllSet() const
Returns true, if all the bits in this bit array are set.
Definition: bits.h:534
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.
Definition: bits.h:130
bool Contains(const TfBits &rhs) const
Returns true if this bit array contains rhs by computing: (rhs - this).GetNumSet() == 0.
Definition: bits.h:787
bool IsAnySet() const
Returns true, if there is at least a single set bit.
Definition: bits.h:550
TfBits operator|(const TfBits &rhs) const
Returns these bits or'ed with rhs.
Definition: bits.h:641
TfBits(size_t num=0)
Constructs a fixed size bit array, clears all bits.
Definition: bits.h:85
void Clear(size_t index)
Clears bit # index to zero.
Definition: bits.h:353
TfBits operator&(const TfBits &rhs) const
Returns these bits and'ed with rhs.
Definition: bits.h:625
bool AreContiguouslySet() const
Returns true if the set bits in this bit array are contiguous.
Definition: bits.h:566
AllUnsetView GetAllUnsetView() const
Returns an iteratable view for the bits that steps over all unset bits.
Definition: bits.h:920
void Swap(TfBits &rhs)
Provides a fast swap.
Definition: bits.h:261
size_t GetLastSet() const
Returns the index of the last bit set in the bit array.
Definition: bits.h:505
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.
Definition: bits.h:377
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.
Definition: bits.h:412
bool HasNonEmptyDifference(const TfBits &rhs) const
Returns true if the result of an asymmetric set different is non-zero.
Definition: bits.h:740
bool operator!=(const TfBits &rhs) const
Returns true if this != rhs.
Definition: bits.h:611
bool IsEmpty() const
Returns true if this bit array is empty, i.e.
Definition: bits.h:482
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.
Definition: bits.h:402
size_t GetFirstSet() const
Returns the index of the first bit set in the bit array.
Definition: bits.h:490
TF_API TfBits & operator|=(const TfBits &rhs)
Ors these bits with the rhs bits.
void ClearAll()
Clears all bits to zero.
Definition: bits.h:330
bool IsAnyUnset() const
Returns true, if there is at least a single unset bit.
Definition: bits.h:557
void ResizeKeepContent(size_t num)
Resizes the size of the bit array while keeping the content.
Definition: bits.h:208
TfBits operator^(const TfBits &rhs) const
Returns these bits xor'ed with rhs.
Definition: bits.h:658
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.
Definition: bits.h:573
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.
Definition: bits.h:914
size_t FindPrevSet(size_t index) const
Finds the prev set bit that has a lower or equal index than index.
Definition: bits.h:440
TfBits & operator=(const TfBits &rhs)
Assignment operator.
Definition: bits.h:144
bool HasNonEmptyIntersection(const TfBits &rhs) const
Returns true if the result of the intersection with rhs would be non-zero.
Definition: bits.h:696
void Resize(size_t num)
Resizes the bit array, however, the bits are left uninitialized.
Definition: bits.h:185
~TfBits()
Destructor.
Definition: bits.h:137
TfBits & operator=(TfBits &&rhs)
Move assignment operator.
Definition: bits.h:172
AllView GetAllView() const
Returns an iteratable view for the bits that steps over all bits.
Definition: bits.h:908
TfBits(const TfBits &rhs)
Copy-constructs a fixed size bit array.
Definition: bits.h:114
bool AreAllUnset() const
Returns true, if all the bits in this bit array are unset.
Definition: bits.h:543
size_t FindNextSet(size_t index) const
Finds the next set bit that has a higher or equal index than index.
Definition: bits.h:422
bool operator[](size_t index) const
Returns bit at index.
Definition: bits.h:682
size_t GetNumSet() const
Returns the number of bits currently set in this array.
Definition: bits.h:520
static size_t Combine(Args &&... args)
Produce a hash code by combining the hash codes of several objects.
Definition: hash.h:475
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.
Definition: tf.h:61
T TfMin(const T &v1, const T &v2)
Returns the smaller of the two given values.
Definition: tf.h:55
#define TF_AXIOM(cond)
Aborts if the condition cond is not met.
Definition: diagnostic.h:193
Compiler hints.
A hash functor for TfBits that is faster than Hash.
Definition: bits.h:72
Hash for TfBits.
Definition: bits.h:61
A file containing basic constants and definitions.