HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
GA_Defragment.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_Defragment.h ( GA Library, C++)
7  *
8  * COMMENTS:
9  */
10 
11 #ifndef __GA_Defragment__
12 #define __GA_Defragment__
13 
14 #include "GA_API.h"
15 #include "GA_IndexMap.h"
16 #include "GA_OffsetList.h"
17 #include "GA_Types.h"
18 
19 #include <UT/UT_Array.h>
20 #include <SYS/SYS_Inline.h>
21 
22 #include <stddef.h>
23 
24 
25 class UT_Options;
26 
27 
28 /// @brief Defragmentation of IndexMaps
29 ///
30 /// Defragmentation consists of two stages
31 /// - Analyzing the index map and computing the swaps/exchanges
32 /// - Application of the swaps
33 /// When applying the swaps, there are two operations which need to be done
34 /// - When an offset is swapped, all attributes need to have their data
35 /// swapped.
36 /// - When an offset is swapped, any reference to the old offset needs to be
37 /// updated to the new offset. For example, primitive store offsets into the
38 /// vertex index map. When these offsets get moved, primitives need to
39 /// update their reference. The detail's topology management automatically
40 /// updates references.
41 ///
42 /// NOTE: Ranges being moved can *only* overlap if the move is from a higher
43 /// address to a lower address!
44 ///
46 {
47 public:
48  GA_Defragment();
49  ~GA_Defragment();
50 
51  enum STRATEGY
52  {
53  /// Defragment so that the offsets will match the ordered index
54  /// This will also remove any holes in the index map.
56 
57  /// Default strategy
58  DEFRAG_DEFAULT = DEFRAG_TO_ORDER
59  };
60 
61  enum OPERATION
62  {
63  MOVE_A_TO_B, // Move data from A to B (can only be overlapping if A > B)
64  SWAP_AB, // Swap data at A and B (can't be overlapping!)
65  };
66 
67  const GA_IndexMap &getIndexMap() const { return *myIndexMap; }
68  GA_AttributeOwner getOwner() const { return myIndexMap->getOwner(); }
69 
70  /// Clear all information
71  void clear();
72 
73  /// Create a defragmentation operation using various strategies
74  /// Options include
75  /// - @c bool force [off] @n
76  /// Force defragmenting to occur.
77  /// - @c occupancy [0.75] @n
78  /// Defragment when the ratio of occupied indices to index capacity is
79  /// beyond this threshold.
80  /// - @c bool sortvertex [off] @n
81  /// When defragmenting vertices, sort the vertices by primitive reference
82  /// order. This will optimize primitive vertex traversal, but add cost
83  /// to defragmenting.
84  void create(const GA_IndexMap &map,
85  STRATEGY strategy=DEFRAG_DEFAULT,
86  const UT_Options *options=NULL);
87 
88  /// Check if there are any swaps to perform
89  bool isEmpty() const
90  { return getSwapCount() == 0; }
91 
92  /// Test to see if an offset will move during the swapping
94  bool hasOffsetChanged(GA_Offset old_offset) const
95  { return mapOffset(old_offset) != old_offset; }
96 
97  /// Given the old offset, return the new offset.
99  GA_Offset mapOffset(GA_Offset old_offset) const
100  { return myOffsetMap(old_offset); }
101 
102  /// Return number of offsets stored in the map
103  GA_Offset getOffsetMapEntries() const { return myOffsetMap.entries(); }
104 
105  /// Return the maximum offset @b after the defragmentation is complete
106  GA_Offset getMaxOccupiedOffset() const { return myMaxOffset; }
107 
108  /// Class to hold information about a swap.
109  /// Move entries from [a, a+n-1] to [b, b+n-1]
110  /// Swap entries in the range [a, a+n-1] with [b, b+n-1]
111  class swapInfo
112  {
113  public:
115  : myA(a)
116  , myB(b)
117  , myN(n)
118  , myOp(op)
119  { }
121  : myA(i.myA)
122  , myB(i.myB)
123  , myN(i.myN)
124  , myOp(i.myOp)
125  { }
128  {
129  myA = i.myA;
130  myB = i.myB;
131  myN = i.myN;
132  myOp = i.myOp;
133  return *this;
134  }
135  bool operator==(const swapInfo &i) const
136  {
137  return myA == i.myA && myB == i.myB && myN == i.myN && myOp == i.myOp;
138  }
139 
140  GA_Offset getA() const { return myA; }
141  GA_Offset getB() const { return myB; }
142  GA_Size getN() const { return myN; }
143  OPERATION getOp() const { return myOp; }
144 
145  bool operator<(const swapInfo &cmp) const
146  {
147  if (myOp != cmp.myOp)
148  {
149  return myOp == MOVE_A_TO_B;
150  }
151  return myB < cmp.myB;
152  }
153  int compare(const swapInfo &cmp) const
154  {
155  if (*this == cmp)
156  return 0;
157  return *this < cmp ? -1 : 1;
158  }
159 
160  static int qsortCompare(const swapInfo *a, const swapInfo *b)
161  {
162  return a->compare(*b);
163  }
164 
165  private:
166  GA_Offset myA, myB;
167  GA_Size myN;
168  OPERATION myOp;
169  };
170  /// Class to iterate over all defrag operations. For example: @code
171  /// for (const_iterator it = frag.begin(); !it.atEnd(); ++it) {
172  /// switch (it.getOp()) {
173  /// case MOVE_A_TO_B:
174  /// moveRange(it.getA(), it.getB(), it.getN());
175  /// case SWAP_AB:
176  /// swapRange(it.getA(), it.getB(), it.getN());
177  /// }
178  /// }
179  /// @endcode
181  {
182  public:
184  : myFrag(NULL)
185  , myCurr(0)
186  , myA(GA_INVALID_OFFSET)
187  , myB(GA_INVALID_OFFSET)
188  , myN(0)
189  , myOp(MOVE_A_TO_B)
190  { }
192  : myFrag(src.myFrag)
193  , myCurr(src.myCurr)
194  , myA(src.myA)
195  , myB(src.myB)
196  , myN(src.myN)
197  , myOp(src.myOp)
198  { }
200  { }
201 
202  /// Get the swap ranges
203  GA_Offset getA() const { return myA; }
204  GA_Offset getB() const { return myB; }
205  GA_Size getN() const { return myN; }
206  OPERATION getOp() const { return myOp; }
207 
209  {
210  myFrag = src.myFrag;
211  myCurr = src.myCurr;
212  myA = src.myA;
213  myB = src.myB;
214  myN = src.myN;
215  myOp = src.myOp;
216  return *this;
217  }
218  bool operator==(const const_iterator &src) const
219  {
220  if (atEnd() && src.atEnd())
221  return true;
222  return myFrag == src.myFrag && myCurr == src.myCurr;
223  }
224  bool atEnd() const
225  {
226  return (!myFrag) || (myCurr >= myFrag->getSwapCount());
227  }
228  void advance()
229  {
230  myCurr++;
231  loadFromSwap();
232  }
233  void rewind()
234  {
235  myCurr = 0;
236  myA = GA_Offset(0);
237  myB = GA_Offset(0);
238  myN = 0;
239  loadFromSwap();
240  }
241  const_iterator &operator++() { advance(); return *this; }
242  const_iterator &operator++(int) { advance(); return *this; }
243 
244  private:
245  void loadFromSwap()
246  {
247  if (myCurr < myFrag->getSwapCount())
248  {
250  &s = myFrag->getSwap(myCurr);
251  myA = s.getA();
252  myB = s.getB();
253  myN = s.getN();
254  myOp = s.getOp();
255  }
256  }
257  /// Get the current swap information
258  const GA_Defragment::swapInfo &getSwap() const
259  { return myFrag->getSwap(myCurr); }
260  const_iterator(const GA_Defragment &frag)
261  : myFrag(&frag)
262  {
263  rewind();
264  }
265  const GA_Defragment *myFrag;
266  GA_Size myCurr;
267  GA_Offset myA, myB;
268  GA_Size myN;
269  OPERATION myOp;
270  friend class GA_Defragment;
271  };
272 
273  const_iterator begin() const { return const_iterator(*this); }
274  const_iterator end() const { return const_iterator(); }
275 
276  static bool shouldIndexMapBeDefragmented(
277  const GA_IndexMap &map,
278  const UT_Options *options);
279 private:
280  GA_Size getSwapCount() const { return mySwaps.entries(); }
281  const swapInfo &getSwap(GA_Size i) const { return mySwaps(i); }
282  /// Build the list of moves and swaps to make (mySwaps)
283  void packToIndexOrder(const UT_Options *options);
284 
285  /// Map, from offsets to indices, that describes the arrangement of data to be defragmented
286  const GA_IndexMap *myIndexMap;
287  /// List of move and swap operations to be made in order to defragment the data
288  UT_Array<swapInfo> mySwaps;
289  GA_OffsetListType<GA_Offset> myOffsetMap; // Map from old to new offset
290  GA_Offset myMaxOffset; // Maximum offset after defrag
291 };
292 
293 #endif
294 
int compare(const swapInfo &cmp) const
A class to manage an ordered array which has fixed offset handles.
Definition: GA_IndexMap.h:63
const_iterator begin() const
GA_Offset getB() const
swapInfo(GA_Size a, GA_Size b, GA_Size n, OPERATION op)
const_iterator & operator++(int)
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
bool operator<(const swapInfo &cmp) const
#define GA_API
Definition: GA_API.h:12
GA_AttributeOwner getOwner() const
Definition: GA_Defragment.h:68
bool isEmpty() const
Check if there are any swaps to perform.
Definition: GA_Defragment.h:89
png_uint_32 i
Definition: png.h:2877
exint GA_Size
Defines the bit width for index and offset types in GA.
Definition: GA_Types.h:211
SYS_FORCE_INLINE bool hasOffsetChanged(GA_Offset old_offset) const
Test to see if an offset will move during the swapping.
Definition: GA_Defragment.h:94
const_iterator(const const_iterator &src)
#define GA_INVALID_OFFSET
Definition: GA_Types.h:654
GA_Size GA_Offset
Definition: GA_Types.h:617
GLdouble n
Definition: glcorearb.h:2007
const GA_IndexMap & getIndexMap() const
Definition: GA_Defragment.h:67
const_iterator & operator=(const const_iterator &src)
OPERATION getOp() const
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
int strategy
Definition: png.h:2009
const_iterator & operator++()
swapInfo(const swapInfo &i)
Defragmentation of IndexMaps.
Definition: GA_Defragment.h:45
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
GA_Offset getOffsetMapEntries() const
Return number of offsets stored in the map.
int cmp(T a, T b)
Definition: ImathFun.h:119
const_iterator end() const
GA_AttributeOwner
Definition: GA_Types.h:33
A map of string to various well defined value types.
Definition: UT_Options.h:42
GA_Offset getA() const
Get the swap ranges.
GA_Size getN() const
swapInfo & operator=(const swapInfo &i)
GA_Offset getA() const
GA_Offset getMaxOccupiedOffset() const
Return the maximum offset after the defragmentation is complete.
static bool shouldIndexMapBeDefragmented(const GA_IndexMap &map, const UT_Options *options)
static int qsortCompare(const swapInfo *a, const swapInfo *b)
bool operator==(const swapInfo &i) const
bool operator==(const const_iterator &src) const
SYS_FORCE_INLINE GA_Offset mapOffset(GA_Offset old_offset) const
Given the old offset, return the new offset.
Definition: GA_Defragment.h:99
GLenum src
Definition: glcorearb.h:1792