HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_BitArray.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: BitArray.h
7  *
8  * COMMENTS:
9  *
10  */
11 
12 #ifndef _UT_BitArray_
13 #define _UT_BitArray_
14 
15 #include "UT_API.h"
16 #include "UT_Assert.h"
17 #include <SYS/SYS_Deprecated.h>
18 #include <SYS/SYS_Types.h>
19 #include <SYS/SYS_BitUtil.h>
20 #include <iosfwd>
21 #include <iterator>
22 
23 class UT_IStream;
24 
25 
26 //
27 // This class implements a one dimensional array of bits.
28 //
30 public:
31  typedef uint64 BlockType;
32 
33  UT_BitArray();
34  UT_BitArray(const UT_BitArray &src);
35  UT_BitArray(UT_BitArray &&src) noexcept;
36  explicit UT_BitArray(exint size);
37  ~UT_BitArray();
38 
39  void insert(exint index, bool value);
40  void append(bool value) { insert(myBitCount, value); }
41  void remove(exint index);
42 
43  // Cyclically shift the entire array by shift_offset.
44  void cycle(exint shift_offset);
45 
46  exint size() const { return myBitCount; }
47  void setSize(exint new_size);
48 
49  void clear() { setSize(0); }
50 
51  SYS_DEPRECATED(14.0)
52  exint getSize() const { return size(); }
53 
54  SYS_DEPRECATED(14.0)
55  void resize(exint size) { setSize(size); }
56 
57  const BlockType *data() const { return myBits; }
58 
59  exint numBitsSet() const;
60  exint numBitsClear() const;
61 
62  bool allBitsSet() const;
63  bool allBitsClear() const;
64 
65  inline bool getBit(exint index) const;
66 
67  inline bool setBit(exint index, bool value);// Returns previous bit value.
68  inline bool toggleBit(exint index); // Returns previous bit value.
69 
70  inline bool getBitFast(exint index) const;
71  inline void setBitFast(exint index, bool value);
72  inline void toggleBitFast(exint index);
73 
74  void setBits(exint index, exint nbits, bool value);
75  void toggleBits(exint index, exint nbits);
76 
77  void setAllBits(bool value);
78  void toggleAllBits();
79 
80  // I/O methods:
81  int save(std::ostream &os, bool binary = false) const;
82  bool load(UT_IStream &is);
83 
84  /// Iterate over set bits
85  ///
86  /// eg. for (i = bits.iterateInit(); i >= 0; i = bits.iterateNext(i))
87  /// ... do something with bits(i)
88  ///
89  // @{
90  exint iterateInit() const; // Initialize traversal
91  exint iterateNext(exint current_bit) const; // Find next set bit
92 
93  // Deprecated. Don't use.
94  // SYS_DEPRECATED(15.0)
95  void iterateInit(exint &i) const { i = iterateInit(); }
96  // @}
97 
98 
99  /// Find first or last bit in the array. The functions will return -1 if
100  /// no bits are set (i.e. equivalent to allBitsClear())
101  exint findFirstBit() const;
102  exint findLastBit() const;
103 
104  // operators
105 
106  bool operator()(exint index) const { return getBit(index); }
107  bool operator[](exint index) const { return getBit(index); }
108  UT_BitArray &operator&=(const UT_BitArray &in_map); // and | intersection
109  UT_BitArray &operator|=(const UT_BitArray &in_map); // or | union
110  UT_BitArray &operator^=(const UT_BitArray &in_map); // exclusive or
111  UT_BitArray &operator-=(const UT_BitArray &in_map); // minus
112  UT_BitArray &operator=(const UT_BitArray &in_map); // assignment
113  UT_BitArray &operator=(UT_BitArray &&src); // move assignment
114  bool operator==(const UT_BitArray &in_map) const; // compare
115  bool operator!=(const UT_BitArray &in_map) const
116  { return !(*this == in_map); }
117 
118  void swap(UT_BitArray &other);
119 
120  /// Returns whether there are any intersections between the two arrays
121  bool intersects(const UT_BitArray &in_map) const;
122 
123  int64 getMemoryUsage(bool inclusive=true) const
124  {
125  int64 mem = inclusive ? sizeof(*this) : 0;
126  mem += myWordCount*sizeof(BlockType);
127  return mem;
128  }
129 
130  uint computeHash() const;
131 
132  /// Iterate over bits that are turned on
133  class iterator
134  {
135  public:
136  using iterator_category = std::forward_iterator_tag;
137  using value_type = exint;
138  using difference_type = std::ptrdiff_t;
139  using pointer = value_type*;
141 
143  : myArray(NULL)
144  , myIndex(0)
145  , mySize(0)
146  {}
148  {}
149 
150  /// Get the current iteration state
151  exint getBit() const { return myIndex; }
152  exint operator*() const { return myIndex; }
153 
154  /// @{
155  /// Standard iterator interface
156  bool operator==(const iterator &i) const
157  {
158  return myArray == i.myArray
159  && myIndex == i.myIndex
160  && mySize == i.mySize;
161  }
162  bool operator!=(const iterator &i) const
163  {
164  return !(*this == i);
165  }
166  bool atEnd() const
167  {
168  return myIndex >= mySize;
169  }
170  iterator &operator++() { advance(); return *this; }
171  /// @}
172 
173  void rewind()
174  {
175  if (myArray)
176  {
177  myIndex = myArray->iterateInit();
178  if (myIndex < 0)
179  myIndex = mySize;
180  }
181  }
182  void advance()
183  {
184  myIndex = myArray->iterateNext(myIndex);
185  if (myIndex < 0)
186  myIndex = mySize;
187  }
188  private:
189  iterator(const UT_BitArray *array, bool end)
190  : myArray(array)
191  , mySize(array->size())
192  {
193  if (end)
194  myIndex = mySize;
195  else
196  {
197  rewind();
198  }
199  }
200  const UT_BitArray *myArray;
201  exint myIndex;
202  exint mySize;
203  friend class UT_BitArray;
204  };
206 
207  iterator begin() const { return iterator(this, false); }
208  iterator end() const { return iterator(this, true); }
209 
210  void unsafeShareData(BlockType *bits, exint bit_count)
211  {
212  myBits = bits;
213  myBitCount = bit_count;
214  myWordCount = numWords(bit_count);
215  }
216 
218  {
219  myBits = nullptr;
220  myBitCount = 0;
221  myWordCount = 0;
222  }
223 
224  // returns the number of words required for the given number of bits
225  static inline exint
226  numWords(exint size_in_bits)
227  {
228  return (size_in_bits + (myBitsPerWord - 1)) / myBitsPerWord;
229  }
230 
231 private:
232  static const int myBitsPerWord = sizeof(BlockType)*8;
233  static const int myWordShift = SYS_LOG2F(myBitsPerWord);
234  static const int myWordMask = (1 << myWordShift) - 1;
235 
236  BlockType *myBits;
237  exint myBitCount;
238  exint myWordCount;
239 
240 private:
241  exint iterateFromWord(uint64 word_index) const;
242  void swapBlocks32(BlockType *blocks, exint nb_blocks) const;
243  void clearTopWord();
244 
245  // returns the word number in which the given bit would be
246  static inline exint
247  indexWord(exint bit)
248  {
249  return (bit >> myWordShift);
250  }
251 
252  // returns the position in word 'indexWord(bit)' where the given bit is
253  static inline BlockType
254  indexBit(exint bit)
255  {
256  return (BlockType(1) << (bit & myWordMask));
257  }
258 
259  void outTo(std::ostream &os) const;
260  friend std::ostream &operator<<(std::ostream &os, const UT_BitArray &map)
261  {
262  map.outTo(os);
263  return os;
264  }
265 };
266 
267 /// Overload for custom formatting of a UT_BitArray. with UTformat.
268 UT_API size_t
269 format(char *buffer, size_t bufsize, const UT_BitArray &b);
270 
271 // Inline methods
272 inline bool
274 {
275  BlockType *word;
276 
277  if( index < 0 || index >= myBitCount )
278  {
279  UT_ASSERT_P( index >= 0 && index < myBitCount );
280  return false;
281  }
282 
283  word = myBits + indexWord(index);
284  return ((*word & indexBit(index)) != 0);
285 }
286 
287 inline bool
289 {
290  BlockType *word;
291  BlockType mask;
292  BlockType previous;
293 
294  if( index < 0 || index >= myBitCount )
295  {
296  UT_ASSERT_P( index >= 0 && index < myBitCount );
297  return false;
298  }
299 
300  word = myBits + indexWord(index);
301  mask = indexBit(index);
302  previous = *word & mask;
303 
304  if( value ) *word |= mask;
305  else *word &= ~mask;
306 
307  return (previous != 0);
308 }
309 
310 inline bool
312 {
313  BlockType *word;
314  BlockType mask;
315  BlockType previous;
316 
317  if( index < 0 || index >= myBitCount )
318  {
319  UT_ASSERT_P( index >= 0 && index < myBitCount );
320  return false;
321  }
322 
323  word = myBits + indexWord(index);
324  mask = indexBit(index);
325  previous = *word & mask;
326 
327  *word ^= mask;
328 
329  return (previous != 0);
330 }
331 
332 inline bool
334 {
335  UT_ASSERT_P( index >= 0 && index < myBitCount );
336  BlockType word = myBits[indexWord(index)];
337  int bit = index & myWordMask;
338  return (word >> bit) & BlockType(1);
339 }
340 
341 inline void
343 {
344  UT_ASSERT_P( index >= 0 && index < myBitCount );
345  BlockType &word = myBits[indexWord(index)];
346  int bit = index & myWordMask;
347  word = (BlockType(value) << bit) | (word & ~(BlockType(1) << bit));
348 }
349 
350 inline void
352 {
353  UT_ASSERT_P( index >= 0 && index < myBitCount );
354  BlockType &word = myBits[indexWord(index)];
355  int bit = index & myWordMask;
356  word ^= (BlockType(1) << bit);
357 }
358 
360 UT_BitArray::iterateFromWord(uint64 word_index) const
361 {
362  for (; word_index < myWordCount; word_index++)
363  {
364  if (myBits[word_index])
365  {
366  exint bit_index = SYSfirstBitSet(myBits[word_index]);
367  UT_ASSERT_P(bit_index + (word_index << myWordShift) < size());
368  return bit_index + (word_index << myWordShift);
369  }
370  }
371 
372  return -1;
373 }
374 
375 
376 inline exint
378 {
379  return iterateFromWord(0);
380 }
381 
382 inline exint
383 UT_BitArray::iterateNext(exint current_bit) const
384 {
385  // Negative values imply search from the beginning.
386  if (current_bit < 0)
387  return iterateFromWord(0);
388 
389  // finish searching the current word
390  if (current_bit >= (myBitCount - 1))
391  return -1;
392 
393  int bit_index = current_bit & myWordMask;
394  exint word_index = current_bit >> myWordShift;
395  BlockType *word = &myBits[word_index];
396 
397  bit_index = SYSnextBitSet(*word, bit_index);
398  if (bit_index >= 0)
399  {
400  UT_ASSERT_P(bit_index + (word_index << myWordShift) < size());
401  return bit_index + (word_index << myWordShift);
402  }
403  word_index++;
404 
405  return iterateFromWord(word_index);
406 }
407 
408 
409 #endif
int64 getMemoryUsage(bool inclusive=true) const
Definition: UT_BitArray.h:123
GLenum GLuint GLsizei bufsize
Definition: glcorearb.h:1818
bool getBit(exint index) const
Definition: UT_BitArray.h:273
#define SYS_DEPRECATED(__V__)
bool getBitFast(exint index) const
Definition: UT_BitArray.h:333
void
Definition: png.h:1083
iterator begin() const
Definition: UT_BitArray.h:207
bool toggleBit(exint index)
Definition: UT_BitArray.h:311
OrtDmlDeviceFilter & operator^=(OrtDmlDeviceFilter &a, OrtDmlDeviceFilter b)
const GLuint GLenum const void * binary
Definition: glcorearb.h:1924
exint iterateNext(exint current_bit) const
Definition: UT_BitArray.h:383
int64 exint
Definition: SYS_Types.h:125
void swap(T &lhs, T &rhs)
Definition: pugixml.cpp:7172
iterator end() const
Definition: UT_BitArray.h:208
bool operator!=(const iterator &i) const
Definition: UT_BitArray.h:162
#define UT_API
Definition: UT_API.h:14
bool operator[](exint index) const
Definition: UT_BitArray.h:107
unsigned long long uint64
Definition: SYS_Types.h:117
OIIO_FORCEINLINE vbool4 insert(const vbool4 &a, bool val)
Helper: substitute val for a[i].
Definition: simd.h:3436
#define SYS_LOG2F(x)
Definition: SYS_BitUtil.h:299
bool operator==(const BaseDimensions< T > &a, const BaseDimensions< Y > &b)
Definition: Dimensions.h:137
void unsafeClearData()
Definition: UT_BitArray.h:217
Definition: core.h:760
std::ptrdiff_t difference_type
Definition: UT_BitArray.h:138
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:155
void toggleBitFast(exint index)
Definition: UT_BitArray.h:351
iterator & operator++()
Definition: UT_BitArray.h:170
GLuint GLuint end
Definition: glcorearb.h:475
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
bool operator==(const iterator &i) const
Definition: UT_BitArray.h:156
GLint GLuint mask
Definition: glcorearb.h:124
void unsafeShareData(BlockType *bits, exint bit_count)
Definition: UT_BitArray.h:210
void setBitFast(exint index, bool value)
Definition: UT_BitArray.h:342
exint size() const
Definition: UT_BitArray.h:46
long long int64
Definition: SYS_Types.h:116
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1222
Iterate over bits that are turned on.
Definition: UT_BitArray.h:133
const BlockType * data() const
Definition: UT_BitArray.h:57
friend std::ostream & operator<<(std::ostream &os, const UT_BitArray &map)
Definition: UT_BitArray.h:260
bool setBit(exint index, bool value)
Definition: UT_BitArray.h:288
static exint numWords(exint size_in_bits)
Definition: UT_BitArray.h:226
iterator const_iterator
Definition: UT_BitArray.h:205
void iterateInit(exint &i) const
Definition: UT_BitArray.h:95
bool operator!=(const UT_BitArray &in_map) const
Definition: UT_BitArray.h:115
GLsizeiptr size
Definition: glcorearb.h:664
OrtDmlDeviceFilter & operator&=(OrtDmlDeviceFilter &a, OrtDmlDeviceFilter b)
value_type * pointer
Definition: UT_BitArray.h:139
void clear()
Definition: UT_BitArray.h:49
ImageBuf OIIO_API resize(const ImageBuf &src, string_view filtername="", float filterwidth=0.0f, ROI roi={}, int nthreads=0)
exint getBit() const
Get the current iteration state.
Definition: UT_BitArray.h:151
UT_API size_t format(char *buffer, size_t bufsize, const UT_BitArray &b)
Overload for custom formatting of a UT_BitArray. with UTformat.
LeafData & operator=(const LeafData &)=delete
GLuint index
Definition: glcorearb.h:786
exint operator*() const
Definition: UT_BitArray.h:152
exint iterateInit() const
Definition: UT_BitArray.h:377
IMATH_HOSTDEVICE IMATH_CONSTEXPR14 bool intersects(const Box< Vec3< T >> &b, const Line3< T > &r, Vec3< T > &ip) IMATH_NOEXCEPT
Definition: ImathBoxAlgo.h:642
OIIO_FORCEINLINE const vint4 & operator-=(vint4 &a, const vint4 &b)
Definition: simd.h:4392
bool operator()(exint index) const
Definition: UT_BitArray.h:106
Definition: core.h:1131
std::forward_iterator_tag iterator_category
Definition: UT_BitArray.h:136
unsigned int uint
Definition: SYS_Types.h:45
bool atEnd() const
Definition: UT_BitArray.h:166
OrtDmlDeviceFilter & operator|=(OrtDmlDeviceFilter &a, OrtDmlDeviceFilter b)
uint64 BlockType
Definition: UT_BitArray.h:31
value_type & reference
Definition: UT_BitArray.h:140
GLenum src
Definition: glcorearb.h:1793