HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
GA_DataBitArray.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: GA_DataBitArray.h ( GA Library, C++)
7  *
8  * COMMENTS: A very simple array used to store attribute data. Some areas
9  * of the array may be "vacant".
10  */
11 
12 #ifndef __GA_DataBitArray__
13 #define __GA_DataBitArray__
14 
15 #include "GA_API.h"
16 #include "GA_Types.h"
17 
18 #include <UT/UT_Array.h>
19 
20 #include <SYS/SYS_Align.h>
21 #include <SYS/SYS_AtomicInt.h>
22 #include <SYS/SYS_Types.h>
23 
24 #include <iosfwd>
25 #include <stddef.h>
26 
27 
28 class GA_Defragment;
29 class GA_LoadMap;
30 class GA_MergeMap;
31 class GA_MergeOffsetMap;
32 class GA_Range;
33 class UT_IStream;
34 class UT_JSONWriter;
35 class UT_JSONParser;
36 class UT_JSONValue;
37 class UT_MemoryCounter;
38 class UT_Options;
39 
40 /// @brief An array of bits.
41 ///
42 /// GA_DataBitArray provides an efficient way of storing bit arrays.
43 ///
44 /// There are basic operations on the array.
45 ///
46 /// See also: @ref JSON-GA_DataBitArray
47 ///
49 {
50 public:
52  ~GA_DataBitArray();
53 
54  /// Change the size of the array
55  void setArraySize(GA_Offset size);
56 
57  /// Query the size of the array
58  GA_Offset getArraySize() const { return mySize; }
59 
60  /// Clear all entries to the default value
61  void clear();
62 
63  /// Clear a specific offset to the default
64  void clearOffset(GA_Offset off, GA_Offset num);
65 
66  /// Set all entries to the given value
67  void makeConstant(bool value);
68 
69  /// Try to compress all pages overlapping the specified offset range.
70  void tryCompressAllPages(GA_Offset start_offset = GA_Offset(0),
71  GA_Offset end_offset = GA_INVALID_OFFSET);
72 
73  /// Harden all pages overlapping the specified offset range.
74  void hardenAllPages(GA_Offset start_offset = GA_Offset(0),
75  GA_Offset end_offset = GA_INVALID_OFFSET);
76 
77  /// Report memory usage
78  int64 getMemoryUsage(bool inclusive) const;
79 
80  /// Count memory usage using a UT_MemoryCounter in order to count
81  /// shared memory correctly.
82  /// If inclusive is true, the size of this object is counted,
83  /// else only memory owned by this object is counted.
84  /// If this is pointed to by the calling object, inclusive should be true.
85  /// If this is contained in the calling object, inclusive should be false.
86  /// (Its memory was already counted in the size of the calling object.)
87  void countMemory(UT_MemoryCounter &counter, bool inclusive) const;
88 
89  /// Copy bit array from the source. This will change the size
90  /// of the array if the source size is different.
91  bool copyFrom(const GA_DataBitArray &src);
92 
93  /// mergeGrowArrayAndCopy() is called to grow the data array while
94  /// appending or copying data from the source (non-interleaved merge).
95  /// The array is resized to the new destination capacity (as defined by
96  /// the map) and the data from the source array is copied over into the
97  /// newly allocated area.
98  void mergeGrowArrayAndCopy(const GA_MergeMap &map,
99  GA_AttributeOwner owner,
100  const GA_DataBitArray &src);
101 
102  GA_Size countSetBits(GA_Offset start, GA_Offset end) const;
103  /// Query the length of repeated bit values starting from 'start' until
104  /// 'end' or a change in bit values.
105  void getConstantSpan(GA_Offset start, GA_Offset end, GA_Size &size, bool &value) const;
106 
107  /// Access data from the array
109  bool get(GA_Offset idx) const
110  {
111  GA_PageNum pagenum = GAgetPageNum(idx);
112 
113  const Page *page = myPages(pagenum);
114  if (isPageConstant(page))
115  return getPageCVal(page);
116 
117  GA_PageOff pi = GAgetPageOff(idx);
118  int i = getWordOffset(pi);
119  int j = getBitOffset(pi);
120  // NOTE: The "& 1" always results in either 0 or 1, so "!=0" isn't necessary.
121  // VC++ would normally give a warning, but it seems to know about this one.
122  return (page->asBitWord()[i] >> j) & 1;
123  }
124  /// Test if any bit in the range is set
125  bool isAnySet(const GA_Range &range) const;
126 
127  /// Set the value at a particular index
128  void set(GA_Offset di, bool val)
129  {
130  GA_PageNum pagenum = GAgetPageNum(di);
131  Page *page = myPages(pagenum);
132  if (isPageConstant(page))
133  {
134  // Avoid creating a page if we are just setting it to the constant value
135  bool cvalue = getPageCVal(page);
136  if (cvalue == val)
137  return;
138  page = new Page(cvalue);
139  myPages(pagenum) = page;
140  }
141  else if (page->isShared())
142  {
143  Page *oldpage = page;
144  page = page->copy();
145  myPages(pagenum) = page;
146  oldpage->unref();
147  }
148 
149  GA_PageOff pi = GAgetPageOff(di);
150  int i = getWordOffset(pi);
151  BitWord &d = page->asBitWord()[i];
152 
153  int j = getBitOffset(pi);
154  // NOTE: The typecast on the 1 is so that if BitWord ever becomes 64 bits,
155  // there won't be any undefined behaviour.
156  BitWord mask = ((BitWord)1 << j);
157  if (val)
158  d |= mask;
159  else
160  d &= ~mask;
161  }
162  /// Set the value at a particular index
163  template<bool VALUE>
164  void set(GA_Offset di)
165  {
166  GA_PageNum pagenum = GAgetPageNum(di);
167  Page *page = myPages(pagenum);
168  if (isPageConstant(page))
169  {
170  // Avoid creating a page if we are just setting it to the constant value
171  bool cvalue = getPageCVal(page);
172  if (cvalue == VALUE)
173  return;
174  page = new Page(cvalue);
175  myPages(pagenum) = page;
176  }
177  else if (page->isShared())
178  {
179  Page *oldpage = page;
180  page = page->copy();
181  myPages(pagenum) = page;
182  oldpage->unref();
183  }
184 
185  GA_PageOff pi = GAgetPageOff(di);
186  int i = getWordOffset(pi);
187  BitWord &d = page->asBitWord()[i];
188 
189  int j = getBitOffset(pi);
190  // NOTE: The typecast on the 1 is so that if BitWord ever becomes 64 bits,
191  // there won't be any undefined behaviour.
192  BitWord mask = ((BitWord)1 << j);
193  if (VALUE)
194  d |= mask;
195  else
196  d &= ~mask;
197  }
199  { set(di, src.get(si)); }
200  void set(const GA_Range &it, bool val);
201  void set(GA_Offset span_start, GA_Offset span_end, bool val);
202  void set(const GA_Range &it, const GA_DataBitArray &src);
203  void set(const GA_Range &it, const GA_DataBitArray &src, const GA_Range &sit);
204  void set(const GA_DataBitArray &src, const GA_Range &sit,
205  const GA_MergeOffsetMap &map);
206 
207  /// @{
208  /// Interface for defragmentation
209  void defragment(const GA_Defragment &defrag);
210  /// @}
211 
212  /// Toggle the value at a particular index
213  bool toggle(GA_Offset idx);
214  void toggle(const GA_Range &it);
215 
216  /// Page accelerated full group operations
217  void andEqual(const GA_DataBitArray &src);
218  void xorEqual(const GA_DataBitArray &src);
219  void orEqual(const GA_DataBitArray &src);
220  void subEqual(const GA_DataBitArray &src);
221  void toggleAll(GA_Size numelements);
222 
223  /// A special method for loading group data from geo files.
224  bool loadGroupBitArrayH9(UT_IStream &is);
225  bool saveGroupBitArrayH9(std::ostream &os, int binary,
226  const GA_Range &it) const;
227 
228  /// @section JSON-GA_DataBitArray JSON Schema: GA_DataBitArray
229  /// jsonSave() will save the array to a JSON stream. There are multiple
230  /// ways to store a bit-array.
231  /// @code
232  /// {
233  /// "name" : "GA_DataBitArray",
234  /// "description" : "A array bits",
235  /// "type" : "orderedmap",
236  /// "properties" : [
237  /// "boolRLE": {
238  /// "type" : "array",
239  /// "items" : [ "integer", "boolean" ]
240  /// "optional" : true,
241  /// "description": "A run length encoded bit array stored as a
242  /// count/bool pair where the 'bool' value is
243  /// repeated 'count' times.",
244  /// }
245  /// "i8": {
246  /// "type" : "array",
247  /// "items" : "integer",
248  /// "description" : "A array of 0/1, not very efficient",
249  /// "optional" : true,
250  /// }
251  /// ]
252  /// }
253  /// @endcode
254  /// @see @ref JSON_FileFormat
255  bool jsonSave(UT_JSONWriter &w, const GA_Range &it,
256  const UT_Options *options) const;
257 
258  /// Load from a JSON stream
259  bool jsonLoad(UT_JSONParser &p, const GA_LoadMap &map,
260  GA_AttributeOwner owner);
261  /// Load from a JSON value
262  bool jsonLoad(UT_JSONParser &p, const UT_JSONValue &v,
263  const GA_LoadMap &map, GA_AttributeOwner owner);
264 
265  /// We want a bit pattern the size of a pointer whose every bit
266  /// but the last is set.
267  static constexpr uintptr_t BIT_PAGE_PTR_MASK = ~((uintptr_t)1);
268 
270  { return isPageConstant(myPages(pageid)); }
271 
273  { return getPageCVal(myPages(pageid)); }
274 
275  void tryCompressPage(GA_PageNum pageid);
276  void makePageConstant(GA_PageNum pageid, bool value);
277 
278 private:
279  // A reference counted page of GA_PAGE_SIZE bits
280  class GA_API Page
281  {
282  public:
283  Page(bool def_val);
284  ~Page();
285 
286  using BitWord = uint64;
287  static constexpr uint64 BITS_PER_WORD = sizeof(BitWord)*8;
288 
289  int64 getMemoryUsage(bool inclusive) const
290  { return inclusive ? sizeof(*this) : 0; }
291 
292  void countMemory(UT_MemoryCounter &counter, bool inclusive) const;
293 
294  // methods to manage sharing
296  void ref() const { myRefCount.add(1); }
298  void unref() { if(myRefCount.add(-1) == 0) delete this; }
300  bool isShared() const { return myRefCount.relaxedLoad() != 1; }
301  Page *copy() const;
302 
303  /// Data accessors
304  /// @{
306  const BitWord *asBitWord() const { return myData; }
308  BitWord *asBitWord() { return myData; }
309  /// @}
310 
311  private:
312  Page(const BitWord *data);
313 
314  mutable SYS_AtomicCounter myRefCount;
315 
316  // This should be 16byte aligned
317  SYS_ALIGN16 BitWord myData[GA_PAGE_SIZE / BITS_PER_WORD];
318  };
319 
320  using BitWord = Page::BitWord;
321  static constexpr GA_Size BITS_PER_WORD = Page::BITS_PER_WORD;
322  static constexpr GA_Size BITS_PER_WORD_MASK = BITS_PER_WORD-1;
323  /// 64 = 2^6
324  static constexpr uint64 BITS_PER_WORD_SHIFT = 3+3;
325 
326  SYS_FORCE_INLINE bool isPageConstant(const Page *ppage) const
327  { return !(((uintptr_t)ppage) & BIT_PAGE_PTR_MASK); }
328 
329  SYS_FORCE_INLINE bool getPageCVal(const Page *ppage) const
330  {
331  UT_ASSERT_P(isPageConstant(ppage));
332  return uintptr_t(ppage) & 1;
333  }
334 
335  /// Functions for making bit masks from a start bit (inclusive)
336  /// to an end bit (exclusive, though *must* be < BITS_PER_WORD)
337  /// NOTE: The typecasts are in case ga_BitWord ever becomes 64-bit.
338  /// @{
339  static SYS_FORCE_INLINE BitWord
340  startBitsMask(GA_Size end_bit)
341  {
342  return ((BitWord)1<<end_bit) - 1;
343  }
344  static SYS_FORCE_INLINE BitWord
345  middleBitsMask(GA_Size start_bit,GA_Size end_bit)
346  {
347  return ((BitWord)1<<end_bit) - ((BitWord)1<<start_bit);
348  }
349  static SYS_FORCE_INLINE BitWord
350  endBitsMask(GA_Size start_bit)
351  {
352  return 0 - ((BitWord)1<<start_bit);
353  }
354 
356  getWordOffset(GA_Size offset)
357  {
358  SYS_STATIC_ASSERT((uint64(1) << BITS_PER_WORD_SHIFT) == BITS_PER_WORD);
359  return offset >> BITS_PER_WORD_SHIFT;
360  }
361 
363  getWordCount(GA_Size nbits)
364  {
365  return (nbits + BITS_PER_WORD - 1) >> BITS_PER_WORD_SHIFT;
366  }
367 
369  getBitOffset(GA_Size offset)
370  {
371  return offset & BITS_PER_WORD_MASK;
372  }
373  /// @}
374 
375  void reallocPageTable(GA_Offset size);
376  Page *harden(GA_PageNum pageid);
377 
378  bool myDefault;
379  UT_Array<Page *> myPages;
380  GA_Offset mySize;
381 };
382 
383 #endif
GLenum GLint * range
Definition: glew.h:3500
SYS_FORCE_INLINE bool getPageCVal(GA_PageNum pageid) const
GA_Offset getArraySize() const
Query the size of the array.
#define SYS_STATIC_ASSERT(expr)
GLsizeiptr size
Definition: glew.h:1681
GLenum src
Definition: glew.h:2410
GLenum GLint ref
Definition: glew.h:1845
SYS_FORCE_INLINE bool get(GA_Offset idx) const
Access data from the array.
GA_Size GA_PageOff
Definition: GA_Types.h:643
GLuint const GLfloat * val
Definition: glew.h:2794
The merge map keeps track of information when merging details.
Definition: GA_MergeMap.h:53
JSON reader class which handles parsing of JSON or bJSON files.
Definition: UT_JSONParser.h:76
#define GA_API
Definition: GA_API.h:12
Class which writes ASCII or binary JSON streams.
Definition: UT_JSONWriter.h:34
const GLdouble * v
Definition: glew.h:1391
GLenum GLint GLuint mask
Definition: glew.h:1845
unsigned long long uint64
Definition: SYS_Types.h:117
exint GA_Size
Defines the bit width for index and offset types in GA.
Definition: GA_Types.h:233
GA_PageOff GAgetPageOff(GA_Offset v)
Definition: GA_Types.h:658
#define GA_INVALID_OFFSET
Definition: GA_Types.h:676
A range of elements in an index-map.
Definition: GA_Range.h:42
GA_Size GA_Offset
Definition: GA_Types.h:639
void set(GA_Offset di, bool val)
Set the value at a particular index.
GLint GLenum GLsizei GLint GLsizei const void * data
Definition: glew.h:1379
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:134
const GLuint GLenum const void * binary
Definition: glew.h:3502
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
GLubyte GLubyte GLubyte GLubyte w
Definition: glew.h:1890
GLuint GLuint end
Definition: glew.h:1253
Keeps track of offset mapping when merging index lists.
#define SYS_ALIGN16
Definition: SYS_Align.h:100
void set(GA_Offset di, const GA_DataBitArray &src, GA_Offset si)
long long int64
Definition: SYS_Types.h:116
Options during loading.
Definition: GA_LoadMap.h:42
Defragmentation of IndexMaps.
Definition: GA_Defragment.h:45
#define GA_PAGE_SIZE
Definition: GA_Types.h:222
GLuint start
Definition: glew.h:1253
GLfloat GLfloat p
Definition: glew.h:16321
GA_AttributeOwner
Definition: GA_Types.h:33
A map of string to various well defined value types.
Definition: UT_Options.h:84
GLuint counter
Definition: glew.h:2740
GLuint num
Definition: glew.h:2690
GA_Size GA_PageNum
Definition: GA_Types.h:642
OIIO_API bool copy(string_view from, string_view to, std::string &err)
void set(GA_Offset di)
Set the value at a particular index.
SYS_FORCE_INLINE bool isPageConstant(GA_PageNum pageid) const
Class to store JSON objects as C++ objects.
Definition: UT_JSONValue.h:77
constexpr T pi()
Pi constant taken from Boost to match old behaviour.
Definition: Math.h:108
An array of bits.
GLsizei const GLfloat * value
Definition: glew.h:1849
GA_PageNum GAgetPageNum(GA_Offset v)
Definition: GA_Types.h:654
GLintptr offset
Definition: glew.h:1682