HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
GA_IndexMap.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_IndexMap.h ( GA Library, C++)
7  *
8  * COMMENTS: The index map maintains a mapping of the ordered index of a
9  * geometric element to its data offset (and vice versa).
10  *
11  * The index map also maintains the list of elements
12  *
13  */
14 
15 #pragma once
16 
17 #ifndef __GA_IndexMap__
18 #define __GA_IndexMap__
19 
20 #include "GA_API.h"
21 #include "GA_Range.h"
22 #include "GA_Types.h"
23 #include "GA_OffsetList.h"
24 
25 #include <UT/UT_Assert.h>
26 #include <UT/UT_NonCopyable.h>
27 
28 #include <SYS/SYS_AtomicInt.h>
29 #include <SYS/SYS_Inline.h>
30 #include <SYS/SYS_MemoryOrder.h>
31 #include <SYS/SYS_Types.h>
32 
33 
34 class GA_AIFStringTuple;
35 class GA_AIFTuple;
36 class GA_Attribute;
37 class GA_Defragment;
38 class GA_Detail;
39 class GA_MergeMap;
40 class GA_MergeOffsetMap;
41 class UT_MemoryCounter;
42 
43 
44 /// @brief A class to manage an ordered array which has fixed offset handles
45 ///
46 /// The GA_Detail keeps an @b ordered list of elements (points, vertices etc.)
47 /// maintained by this class. Each ordered element (named "index") also has a
48 /// fixed @b offset. The offset remains constant as elements are added/removed
49 /// from the detail. The offset is used for indexing into
50 /// * The attribute arrays
51 /// * Groups
52 /// * Primitive lists
53 /// etc.
54 /// Since the offset is not mutable, as elements are added and deleted,
55 /// vacancies become available in the attribute arrays. These vacancies
56 /// may then be filled as new elements get allocated.
57 ///
58 /// This class (GA_IndexMap) keeps track of the vacancies and the order of
59 /// elements.
60 ///
61 /// During some operations, temporary elements are also created. This class
62 /// maintains temporary elements too.
64 {
65 public:
67  ~GA_IndexMap();
68 
69  /// Access the detail this index map belongs to
70  GA_Detail &getDetail() const { return myDetail; }
71  /// What type of element is stored in the index
72  GA_AttributeOwner getOwner() const { return myOwner; }
73 
74  /// Report the memory used (includes all shared memory)
75  int64 getMemoryUsage(bool inclusive) const;
76 
77  /// Count memory usage using a UT_MemoryCounter in order to count
78  /// shared memory correctly.
79  /// If inclusive is true, the size of this object is counted,
80  /// else only memory owned by this object is counted.
81  /// If this is pointed to by the calling object, inclusive should be true.
82  /// If this is contained in the calling object, inclusive should be false.
83  /// (Its memory was already counted in the size of the calling object.)
84  void countMemory(UT_MemoryCounter &counter, bool inclusive) const;
85 
86  /// The capacity for offsets. Attribute arrays must be able to store
87  /// at least this much storage.
89  GA_Offset getOffsetCapacity() const { return myOffsetCapacity; }
90 
91  /// This is an exclusive upper bound when iterating over offsets.
92  /// Every active or temporary offset in this index map will be
93  /// strictly less than this.
94  /// It is always guaranteed that:
95  /// myMaxOccupiedOffset < offsetSize() <= getOffsetCapacity()
98  { return myIndexFromOffset.entries(); }
99 
100  /// Return number of elements in the list.
101  /// This indexSize() is always <= the offsetSize()
104  { return myIndexCount; }
105 
106  /// When accessing the map functions (i.e. mapping from order to data
107  /// offsets), the map may be compacted. This is a potentially expensive
108  /// operation and should be avoided if possible.
109 
110  /// Given an ordered index, this returns the fixed @b offset associated
111  /// with the index.
112  /// @b NOTE: Calling the offsetFromIndex() function may invoke internal data
113  /// modifications (i.e. these operations may be mutable). These
114  /// operations are potentially expensive and should be avoided if possible.
115  /// @see findOffsetInIndices(), findNextOffsetInIndices()
117  GA_Offset offsetFromIndex(GA_Index ordered_index) const
118  {
119  UT_ASSERT_P(GAisValid(ordered_index) &&
120  ordered_index < myIndexCount);
121 
122  // If the list is trivial, it will never need compacting,
123  // so we avoid checking myFirstFreeIndex. operator() checks
124  // isTrivial() anyway, and the compiler seems to avoid checking
125  // it twice.
126  if (myOffsetFromIndex.isTrivial())
127  return myOffsetFromIndex(ordered_index);
128 
129  // NOTE: We could avoid compactIndices() when
130  // ordered_index < firstFreeIndex, but we would still have to
131  // at least read-lock when accessing myOffsetFromIndex,
132  // since compactIndices calls changeSize on myOffsetFromIndex.
133  compactIndicesIfNeeded();
134  UT_ASSERT_P(ordered_index < myOffsetFromIndex.entries());
135 
136  return myOffsetFromIndex(ordered_index);
137  }
138 
139  /// Given an element offset, this returns the ordered @b index.
140  /// @b NOTE: Calling the indexFromOffset() function may invoke internal data
141  /// modifications (i.e. these operations may be mutable). These
142  /// operations are potentially expensive and should be avoided if possible.
143  /// @see findIndexInOffsets()
145  GA_Index indexFromOffset(GA_Offset data_offset) const
146  {
147  UT_ASSERT_P(GAisValid(data_offset) &&
148  data_offset <= myMaxOccupiedOffset);
149 
150  // If the list is trivial, it will never need compacting,
151  // so we avoid checking myFirstFreeIndex. operator() checks
152  // isTrivial() anyway, and the compiler seems to avoid checking
153  // it twice.
154  if (myIndexFromOffset.isTrivial())
155  return myIndexFromOffset(data_offset);
156 
157  // If we have holes in the *indices*, we need to compactIndices()
158  // NOTE: SYS_MEMORY_ORDER_LOAD is to force no speculative reads
159  // in later code occurring before the call to load.
160  GA_Index firstFreeIndex = myFirstFreeIndex.load(SYS_MEMORY_ORDER_LOAD);
161  // NOTE: It is safe to access myIndexFromOffset, because it doesn't
162  // get resized by compactIndices().
163  GA_Index index = myIndexFromOffset(data_offset);
164  if (GAisValid(firstFreeIndex) && index >= firstFreeIndex)
165  {
166  compactIndices();
167  index = myIndexFromOffset(data_offset);
168  }
169 
170  UT_ASSERT_P(GAisValid(index));
171  return index;
172  }
173 
174  /// Obtain offset of the element with the last index.
175  /// Returns GA_INVALID_OFFSET if empty.
176  /// NOTE: The offset will never be a temporary element, since
177  /// temporary elements have no indices.
180  {
181  if (isMonotonicMap() && myTempCount == 0)
182  {
183  // NOTE: Since there are no temporaries and the map is monotonic,
184  // the maximum occupied offset is the offset of the element
185  // with the last index.
186  return myMaxOccupiedOffset;
187  }
188 
189  UT_ASSERT_MSG(isMonotonicMap(),
190  "Why is GA_IndexMap::lastOffset() being called between"
191  "sorting and defragmenting the offsets? It's almost"
192  "certainly a recipe for disaster.");
193  GA_Index n = indexSize();
194  if (n > 0)
195  return offsetFromIndex(n - 1);
196  else
197  return GA_INVALID_OFFSET;
198  }
199 
200  /// This is a helpful class for getting the range of elements
201  /// created after such a Marker is declared. For example,
202  ///
203  /// GA_IndexMap::Marker marker(gdp->getPointMap());
204  /// ... // Some code that creates points
205  /// for (GA_Iterator it(marker.getRange()); !it.atEnd(); ++it)
206  /// ... // Do something to each created point
207  ///
208  /// NOTE: The code doing the creating can't delete elements from
209  /// the index map before adding any new elements.
210  class Marker
211  {
212  public:
213  Marker(const GA_IndexMap &indexmap)
214  : myIndexMap(indexmap)
215  , myBegin(getOffset())
216  {}
217 
218  /// Returns a GA_Range of (non-temporary) elements
219  /// added after the creation of this Marker, so long as
220  /// no elements that were already in the GA_IndexMap
221  /// were deleted before adding any new elements.
222  /// All non-temporary elements between getBegin() and
223  /// getEnd() are in the range.
225  { return GA_Range(myIndexMap, getBegin(), getEnd()); }
226 
227  /// Returns the lower-bound on the beginning of the range
228  GA_Offset getBegin() const { return myBegin; }
229  /// Returns the upper-bound on the end of the range
230  GA_Offset getEnd() const { return getOffset(); }
231 
232  private:
233  GA_Offset getOffset() const
234  { return myIndexMap.lastOffset() + 1; }
235 
236  private:
237  const GA_IndexMap &myIndexMap;
238  const GA_Offset myBegin;
239  };
240 
241  /// Returns a copy of our offset from index list, first ensuring
242  /// it is up to date. Note this is a copy so will not remain
243  /// in sync.
245  {
246  compactIndicesIfNeeded();
247  // NOTE: This returns a copy, though if the GA_OffsetList is non-trivial,
248  // the copy will reference the internal list.
249  return *reinterpret_cast<GA_OffsetList *>(&myOffsetFromIndex);
250  }
251 
252  /// Given an ordered index, this returns the fixed @b offset associated
253  /// with the index. This method may do an O(N) search for the result, but
254  /// is guaranteed to be const.
255  /// It's primarily designed for use in GA_RTIIndex.
256  GA_Offset findOffsetInIndices(GA_Index ordered_index) const;
257  /// Given an offset, this skips the @b step ordered index and returns the
258  /// next fixed @b offset. This method may do an O(N) search for the
259  /// result, but is guaranteed to be const.
260  /// It's primarily designed for use in GA_RTIIndex.
261  GA_Offset findNextOffsetInIndices(GA_Offset data_offset,
262  GA_Index step) const;
263 
264  /// Non-compacting method to find the true order of the given data_offset.
265  /// This method may need to search the non-compact mapping for holes, and
266  /// so sequential calls can easily result in O(n^2) behaviour.
267  GA_Index findIndexInOffsets(GA_Offset data_offset) const;
268 
269  /// Reorder an element. The index of the element at the given data offset
270  /// will be changed to the new order (provided that the ordered position is
271  /// in a valid range).
272  /// @return The new index of the element, or -1 if there was an error
273  GA_Index reorder(GA_Offset data_offset, GA_Index new_order);
274 
275  /// @{
276  /// Swap the order of the two specified (ordered, not transient) data
277  /// offsets.
278  /// @warning You @b must force defragmentation after swapping the index
279  /// order to maintain monotonicity of the index map.
280  /// @return True on success, false on failure.
281  bool swapOrderByOffset(GA_Offset offset1, GA_Offset offset2);
282  bool swapOrderByIndex(GA_Index order1, GA_Index order2);
283  /// @}
284 
285  /// A trivial map is one where offsetFromIndex(i) == i for all elements.
286  /// That is, the offsets are in order and there are no vacancies.
288  bool isTrivialMap() const
289  {
290  GA_Size noff = offsetSize();
291  GA_Size nind = indexSize();
292  if (nind != noff)
293  return false;
294  // NOTE: We don't need to check myFirstFreeIndex, because
295  // if it's valid, offsetSize() > indexSize().
296  // NOTE: It *must* be threadsafe to call isTrivial() and
297  // compactIndices() at the same time, and compactIndices() calls
298  // GA_OffsetList::changeSize() on a non-trivial list, so
299  // GA_OffsetList::isTrivial() *must* return false, no matter
300  // what goes on in GA_OffsetList::changeSize().
301  return myOffsetFromIndex.isTrivial();
302  }
303 
305  bool isMonotonicMap() const
306  {
307  return myMonotonic;
308  }
309 
310  /// Class which compares the elements at two indices
311  /// Example: @code
312  /// class SortReverse : public GA_IndexMap::IndexCompare
313  /// {
314  /// SortReverse() {}
315  /// ~SortReverse() {}
316  /// bool initialize(const GA_IndexMap &map)
317  /// {
318  /// myOrder = new GA_Index[map.offsetSize()];
319  /// for (GA_Iterator it(GA_Range(map)); !it.atEnd();
320  /// ++it)
321  /// {
322  /// myOrder[it.getOffset()] =
323  /// map.indexFromOffset(it.getOffset());
324  /// }
325  /// }
326  /// int compare(const GA_IndexMap&, GA_Offset a, GA_Offset b)
327  /// {
328  /// if (myOrder[a] > myOrder[b])
329  /// return -1;
330  /// if (myOrder[a] < myOrder[b])
331  /// return 1;
332  /// return 0;
333  /// }
334  /// void finish(const GA_IndexMap &)
335  /// {
336  /// delete [] myOrder;
337  /// }
338  /// };
339  /// @endcode
341  {
342  public:
344  virtual ~IndexCompare() {}
345 
346  /// Called prior to the sort. If the method returns false, the
347  /// sort is aborted. If the sort is aborted, the finish() method
348  /// will @b not be called.
349  virtual bool initialize(const GA_IndexMap &map) = 0;
350 
351  /// Compare two elements using strcmp() semantics
352  virtual int compare(const GA_IndexMap &map,
353  GA_Offset item1,
354  GA_Offset item2) = 0;
355 
356  /// Called after the sort is complete. At this point, the index
357  /// will be ordered according to the sort.
358  virtual void finish(const GA_IndexMap &map) = 0;
359  };
360 
361  /// Convenience class which can be used to sort an index map based on an
362  /// attribute value. The attribute should either provide an AIFTuple or
363  /// AIFStringTuple interface. If neither interfaces are provided, this
364  /// class won't do any sorting.
365  /// Example: @code
366  /// GA_Detail &gdp;
367  /// GA_IndexMap &points = gdp.getIndexMap(GA_ATTRIB_POINT);
368  ///
369  /// // Sort by P.z
370  /// GA_IndexMap::AttributeCompare cmpPz(points, "P", 2);
371  /// points.sortIndices(cmpPz);
372  /// @endcode
374  {
375  public:
376  /// Sort the index map based on the values in the attribute. For
377  /// tuple attributes, compare the value for the given index.
378  AttributeCompare(const GA_Attribute *attribute, int tuple_index=0);
379  /// Construct given an index map and an attribute name
380  AttributeCompare(const GA_IndexMap &map,
381  const char *attribute_name,
382  int tuple_index=0);
383  /// Destructor
384  virtual ~AttributeCompare();
385 
386  /// @{
387  /// Methods defined on IndexCompare
388  virtual bool initialize(const GA_IndexMap &map);
389  virtual int compare(const GA_IndexMap &map,
390  GA_Offset item1, GA_Offset item2);
391  virtual void finish(const GA_IndexMap &map);
392  /// @}
393 
394  protected:
395  const GA_Attribute *getAttribute() const
396  { return myAttribute; }
397  const GA_AIFTuple *getAIFTuple() const
398  { return myTuple; }
400  { return mySTuple; }
401  int getTupleIndex() const
402  { return myIndex; }
403  bool getIsFloat() const
404  { return myFloat; }
405  private:
406  const GA_Attribute *myAttribute;
407  const GA_AIFTuple *myTuple;
408  const GA_AIFStringTuple *mySTuple;
409  int myIndex;
410  bool myFloat;
411  };
412 
413  /// Sort the index order using a comparator
414  bool sortIndices(IndexCompare &compare, bool stable=true);
415 
416  /// Sort a selection of elements
417  bool sortIndices(IndexCompare &compare, const GA_Range &range,
418  bool stable=true);
419 
420  /// Sort an array of GA_Offset data according to a comparator
421  bool sortOffsetArray(GA_OffsetArray &offsets, IndexCompare &compare,
422  bool stable=true) const;
423 
424  /// @{
425  /// Shift/cycle elements in the list.
427  bool cycleIndices(GA_Size offset, const GA_Range &range);
428  /// @}
429 
430  /// @{
431  /// Reverse a selection of elements
432  bool reverseIndices();
433  bool reverseIndices(const GA_Range &range);
434  /// @}
435 
436  //------------------------------------------------------------
437  // List management
438  /// Add a new element to the list, returning the data offset of the new
439  /// element.
441  /// Add new elements to the list, returning the first offset of the
442  /// contiguous block
443  GA_Offset addElementBlock(GA_Size nelements);
444  /// Returns the start offset that the next call to addElementBlock
445  /// would return, (assuming it doesn't exceed the hard limit.)
447  /// Delete an element from the list by specifying the order
448  void destroyIndex(GA_Index where);
449  /// Delete an element from the list by the data offset
450  void destroyOffset(GA_Offset where);
451 
452  /// Returns whether the offset is in the valid range of offsets for this
453  /// index map.
455  { return GAisValid(offset) && offset < offsetSize(); }
456 
457  /// Returns true if the specified offset is not in use (i.e. vacant)
458  /// NOTE: Inactive != Vacant. There are temporaries.
459  bool isOffsetVacant(GA_Offset offset) const;
460 
461  /// Returns true if the specified offset is referenced by an ordered element
462  /// No bounds checking is done.
464  { return GAisValid(myIndexFromOffset(offset)); }
465 
466 
467  /// Returns the first offset in [start, end) which is inactive.
468  /// If none are inactive, return end.
469  /// No bounds checking is done.
472  { return myIndexFromOffset.findInvalidInRange(start, end); }
473  /// Returns the first offset in [start, end) which is active
474  /// If none are vacant, return end.
475  /// No bounds checking is done.
478  { return myIndexFromOffset.findValidInRange(start, end); }
479 
480  /// Returns true if the specified offset is referenced by an ordered element
482  { return isOffsetInRange(offset) &&
483  isOffsetActiveFast(offset); }
484 
485  /// Returns true if the specified offset is being used for a temporary
486  /// element.
487  /// @see GA_WorkVertexBuffer
488  bool isOffsetTransient(GA_Offset offset) const;
489 
490  /// Calls functor on every active offset in this index map.
491  template<typename FUNCTOR>
493  void forEachOffset(FUNCTOR &&functor) const
494  {
495  if (isTrivialMap())
496  {
497  const GA_Offset end = GA_Offset(GA_Size(myIndexCount));
498  for (GA_Offset off(0); off != end; ++off)
499  {
500  functor(off);
501  }
502  }
503  else
504  {
505  const GA_Offset veryend(myMaxOccupiedOffset+1);
506  GA_Offset off(0);
507  while (true)
508  {
509  off = findActiveOffset(off, veryend);
510  GA_Offset end = findInactiveOffset(off, veryend);
511  if (off == end)
512  break;
513  do
514  {
515  functor(off);
516  ++off;
517  } while (off != end);
518  }
519  }
520  }
521 
522  /// Calls functor on every active offset in this index map,
523  /// until functor returns false for some element.
524  template<typename FUNCTOR>
526  void forEachOffsetBreak(FUNCTOR &&functor) const
527  {
528  if (isTrivialMap())
529  {
530  const GA_Offset end = GA_Offset(GA_Size(myIndexCount));
531  for (GA_Offset off(0); off != end; ++off)
532  {
533  if (!functor(off))
534  return;
535  }
536  }
537  else
538  {
539  const GA_Offset veryend(myMaxOccupiedOffset+1);
540  GA_Offset off(0);
541  while (true)
542  {
543  off = findActiveOffset(off, veryend);
544  GA_Offset end = findInactiveOffset(off, veryend);
545  if (off == end)
546  break;
547  do
548  {
549  if (!functor(off))
550  return;
551  ++off;
552  } while (off != end);
553  }
554  }
555  }
556 
557  /// @private Clear the index map
558  /// @param clear_capacity If true, the offset capacity value
559  /// is reset to zero. Else, it is left unchanged.
560  void clear(bool clear_capacity);
561 
562  /// @private Allocate a temporary element
563  /// @see GA_WorkVertexBuffer
564  GA_Offset addTemporary();
565 
566  /// @private
567  /// Query the number of temporary elements
568  GA_Size getTempCount() const { return myTempCount; }
569 
570  /// @private Method called by detail during merge operation
571  void merge(GA_MergeMap &map);
572  /// @private Method called to initialize the merge offset maps
573  void mergeInitOffsetMap(GA_MergeMap &map, GA_MergeOffsetMap &omap);
574 
575  /// @private Used by GA_RTIOffset to skip over vacancies. Skips to first
576  /// non-vacant/non-temporary element.
577  void skipToFirstActive(GA_Offset &curr, GA_Offset end,
578  bool fwd=true) const;
579  /// @private Used by GA_RTIOffset to extract a contiguous range
580  /// of offsets. Stops at first vacant or temporary element.
581  void extractActiveRange(GA_Offset &curr, GA_Offset end,
582  bool fwd=true) const;
583 
584  /// @private Used by GA_RTIOffsetComplete to skip over vacancies (but
585  /// including temporaries).
586  void skipToFirstOccupied(GA_Offset &curr, GA_Offset end) const;
587  /// @private Used by GA_RTOffsetComplete to extract a contiguous range of
588  /// occupied (includes active and temporaries).
589  void extractOccupiedRange(GA_Offset &curr, GA_Offset end) const;
590 
591  /// @private Used by GA_RTIIndex to extract a contiguous ordered range of
592  /// offsets. Stops at first vacant, temporary, or out of order element.
593  void extractActiveOrderedRange(GA_Offset &curr, GA_Offset end) const;
594 
595  /// @private - Used only by GA_Detail
596  void defragment(const GA_Defragment &defrag);
597 
598  /// @private - Possibly decrease the getOffsetCapacity()/offsetSize() due to
599  /// deletions
600  void shrinkOffsets();
601 
602  /// @private - defragment to make this a trivial map
603  void makeMonotonic();
604 
605  /// @private - access to internal offset from index array used in
606  /// defragmenting.
607  const GA_ListType<GA_Offset, GA_Index> &getIndexFromOffsetMap() const
608  { return myIndexFromOffset; }
609 
610  /// Returns true iff the index maps are trivial and equal, or
611  /// non-trivial and share the exact same data. This does not
612  /// fully check for equality!
613  bool isSame(const GA_IndexMap &that) const
614  {
615  if (this == &that)
616  return true;
617 
618  // This shouldn't be called while defragmenting or sorting
619  UT_ASSERT_P(myMonotonic && that.myMonotonic);
620 
621  // Detail index maps are all the same
622  if (myOwner == GA_ATTRIB_DETAIL)
623  {
624  UT_ASSERT_P(myIndexCount == 1);
625  return (that.myOwner == GA_ATTRIB_DETAIL);
626  }
627 
628  // Check index count first, for speedy false,
629  // then check for same index->offset, next most likely false,
630  // then change count, and everything else.
631  // Assume false if indices not compacted or temporaries present,
632  // for simplicity, and we also don't need to check offset->index
633  // that way.
634  // NOTE: For some reason, detail index maps may have different
635  // change counts, even though they're always the same.
636  return (myIndexCount == that.myIndexCount) &&
637  myOffsetFromIndex.isSame(that.myOffsetFromIndex) &&
638  myOwner == that.myOwner &&
639  myOffsetCapacity == that.myOffsetCapacity &&
640  myFreeHead == that.myFreeHead &&
641  myFreeTrailerBase == that.myFreeTrailerBase &&
642  myMaxOccupiedOffset == that.myMaxOccupiedOffset &&
643  myMaxTouchedOffset == that.myMaxTouchedOffset &&
644  myFirstFreeIndex.load(SYS_MEMORY_ORDER_LOAD) == GA_INVALID_INDEX && that.myFirstFreeIndex.load(SYS_MEMORY_ORDER_LOAD) == GA_INVALID_INDEX &&
645  myTempCount == 0 && that.myTempCount == 0;
646  }
647 
648  /// This is used as a quick check in defragmentation, in case
649  /// this index map is actually defragmented, but not trivial
650  /// for some reason.
652  {
653  if (!isTrivialMap() &&
654  GA_Size(indexSize()) == GA_Size(offsetSize()) &&
655  isMonotonicMap())
656  {
657  myIndexFromOffset.setTrivial(GA_Index(0), offsetSize());
658  myOffsetFromIndex.setTrivial(GA_Offset(0), indexSize());
659  }
660  }
661 
662 private:
663  /// @private Used by merging to copy the data from the source
664  void copyFrom(const GA_IndexMap &src);
665 
666  /// Compact the ordered list. This removes any temporary vacancies in the
667  /// ordered list.
668  void compactIndices() const;
669 
670  /// Compact the ordered list if necessary, and avoid locking unless
671  /// compacting is necessary.
672  void compactIndicesIfNeeded() const
673  {
674  // If we have holes in the *indices*, we need to compactIndices()
675  // NOTE: SYS_MEMORY_ORDER_LOAD is to force no speculative reads
676  // in later code occurring before the call to load.
677  GA_Index firstFreeIndex(myFirstFreeIndex.load(SYS_MEMORY_ORDER_LOAD));
678  if (GAisValid(firstFreeIndex))
679  compactIndices();
680  UT_ASSERT_P(GA_Index(myFirstFreeIndex.relaxedLoad()) == GA_INVALID_INDEX);
681  }
682 
683  /// Compact the ordered list if necessary, and avoid locking unless
684  /// compacting is necessary.
685  void compactIndicesIfNeeded()
686  {
687  // If we have holes in the *indices*, we need to compactIndices()
688  // NOTE: Since we're non-const, we can use relaxedLoad().
689  // WARNING: If this function is ever made non-private, consider
690  // changing this to load(SYS_MEMORY_ORDER_LOAD), since
691  // we may get a non-const GA_IndexMap from a detail that
692  // we have multiple threads writing to.
693  GA_Index firstFreeIndex(myFirstFreeIndex.relaxedLoad());
694  if (GAisValid(firstFreeIndex))
695  compactIndices();
696  UT_ASSERT_P(GA_Index(myFirstFreeIndex.relaxedLoad()) == GA_INVALID_INDEX);
697  }
698 
699  /// Prune any entries in the free list greater than or equal to the
700  /// supplied upper bound.
701  void pruneFreeList(GA_Offset upper_bound);
702 
703  /// Element initialization code in common between addTemporary
704  /// and addElementBlock
705  void initElementBlock(GA_Offset startoff, GA_Offset nelements);
706 
707  /// Delete the element at the given offset
708  void destroyElement(GA_Offset offset);
709 
710  /// Compute whether we're trivial or not. If we are trivial, then this
711  /// operation may eliminate storage for maps.
712  void computeTrivial();
713 
714  /// Compute whether the map is monotonic or not
715  bool computeMonotonic();
716 
717 private:
718  /// Owner of this index map
719  GA_Detail &myDetail;
720 
721  /// Index->Offset map
722  mutable GA_OffsetListType<GA_Index> myOffsetFromIndex;
723 
724  /// Offset->Index map
725  mutable GA_ListType<GA_Offset, GA_Index> myIndexFromOffset;
726 
727  /// Capacity of attributes in myDetail. This can be larger than
728  /// myIndexFromOffset.entries(), and gets bumpAlloc'd to avoid having
729  /// to set the capacity of a large number of attributes too often.
730  GA_Offset myOffsetCapacity;
731 
732  /// This is the offset of the head of the linked list of free offsets
733  /// for use when adding temporary elements.
734  GA_Offset myFreeHead;
735 
736  /// myFreeTrailerBase is used to track a block of free offsets at the end
737  /// of the offsets. It may not be optimal (i.e. it may not be
738  /// myMaxOccupiedOffset+1) if there are offsets stuck in the linked-list
739  /// after myMaxOccupiedOffset. It can take O(n) time to check for them,
740  /// so we don't always when deleting.
741  GA_Offset myFreeTrailerBase;
742 
743  /// myMaxOccupiedOffset is the largest offset that is used, whether by
744  /// an ordered or temporary element.
745  GA_Offset myMaxOccupiedOffset;
746 
747  /// myMaxTouchedOffset is the largest offset that has, at some point,
748  /// been used, but it is always strictly less than myOffsetCapacity.
749  GA_Offset myMaxTouchedOffset;
750 
751  /// When an element is deleted, instead of shifting down all of
752  /// myOffsetFromIndex immediately, we wait until someone queries it before
753  /// calling compactIndices(). If nothing has been deleted, myFirstFreeIndex
754  /// is GA_INVALID_INDEX. Otherwise, it refers to the lowest (former) index
755  /// of a freed element.
756  mutable SYS_AtomicCounter myFirstFreeIndex;
757 
758  /// The number of temporary elements in the index map.
759  GA_Size myTempCount;
760 
761  /// The true count of indices, i.e. myOffsetFromIndex.entries() minus
762  /// the number of holes.
763  GA_Index myIndexCount;
764 
765  /// The type of element this index map is for (point, vertex, prim, detail)
766  GA_AttributeOwner myOwner;
767 
768  /// This is true if the offset corresponding with any index is always
769  /// greater than the offset corresponding with a lower index, i.e.
770  /// if the offsets are monotone increasing.
771  /// The ONLY case where this is false is immediately before defragmentation
772  /// inside of a GA_IndexMap function, so users of GA_IndexMap, apart from
773  /// the GA_Detail::defragment and GA_Defragment code, *can* rely on the
774  /// index map being monotone increasing.
775  bool myMonotonic;
776 
777  /// NOTE: These are friends so that they can call compactIndicesIfNeeded.
778  friend class GA_Detail;
779  friend class GU_DetailHandleRef;
780 
781  /// NOTE: This friend is so that GA_AttributeSet::replace can call copyFrom.
782  friend class GA_AttributeSet;
783 };
784 
785 #endif
A class to manage an ordered array which has fixed offset handles.
Definition: GA_IndexMap.h:63
GA_AttributeOwner getOwner() const
What type of element is stored in the index.
Definition: GA_IndexMap.h:72
bool isOffsetActiveFast(GA_Offset offset) const
Definition: GA_IndexMap.h:463
Definition of a geometry attribute.
Definition: GA_Attribute.h:189
GA_Offset nextNewElementOffset() const
void destroyOffset(GA_Offset where)
Delete an element from the list by the data offset.
GLenum GLint * range
Definition: glcorearb.h:1924
virtual void finish(const GA_IndexMap &map)=0
bool sortIndices(IndexCompare &compare, bool stable=true)
Sort the index order using a comparator.
SYS_FORCE_INLINE GA_Offset getOffsetCapacity() const
Definition: GA_IndexMap.h:89
bool cycleIndices(GA_Size offset)
GLuint start
Definition: glcorearb.h:474
bool GAisValid(GA_Size v)
Definition: GA_Types.h:625
bool isOffsetVacant(GA_Offset offset) const
The merge map keeps track of information when merging details.
Definition: GA_MergeMap.h:53
SYS_FORCE_INLINE bool isMonotonicMap() const
Definition: GA_IndexMap.h:305
#define GA_API
Definition: GA_API.h:12
SYS_FORCE_INLINE void forEachOffset(FUNCTOR &&functor) const
Calls functor on every active offset in this index map.
Definition: GA_IndexMap.h:493
const GA_AIFTuple * getAIFTuple() const
Definition: GA_IndexMap.h:397
GA_Detail & getDetail() const
Access the detail this index map belongs to.
Definition: GA_IndexMap.h:70
exint GA_Size
Defines the bit width for index and offset types in GA.
Definition: GA_Types.h:211
SYS_FORCE_INLINE GA_Index indexFromOffset(GA_Offset data_offset) const
Definition: GA_IndexMap.h:145
GA_Offset getBegin() const
Returns the lower-bound on the beginning of the range.
Definition: GA_IndexMap.h:228
#define GA_INVALID_OFFSET
Definition: GA_Types.h:654
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:101
SYS_FORCE_INLINE GA_Offset findActiveOffset(GA_Offset start, GA_Offset end) const
Definition: GA_IndexMap.h:477
A range of elements in an index-map.
Definition: GA_Range.h:42
GLuint GLsizei const GLuint const GLintptr * offsets
Definition: glcorearb.h:2620
GA_Size GA_Offset
Definition: GA_Types.h:617
long long int64
Definition: SYS_Types.h:100
GLdouble n
Definition: glcorearb.h:2007
bool isOffsetTransient(GA_Offset offset) const
Marker(const GA_IndexMap &indexmap)
Definition: GA_IndexMap.h:213
const GA_AIFStringTuple * getAIFStringTuple() const
Definition: GA_IndexMap.h:399
T load(SYS_MemoryOrder order=SYS_MEMORY_ORDER_SEQ_CST) const
GLuint GLuint end
Definition: glcorearb.h:474
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
GLintptr offset
Definition: glcorearb.h:664
bool sortOffsetArray(GA_OffsetArray &offsets, IndexCompare &compare, bool stable=true) const
Sort an array of GA_Offset data according to a comparator.
Keeps track of offset mapping when merging index lists.
bool isSame(const GA_IndexMap &that) const
Definition: GA_IndexMap.h:613
SYS_FORCE_INLINE GA_Offset findInactiveOffset(GA_Offset start, GA_Offset end) const
Definition: GA_IndexMap.h:471
Defragmentation of IndexMaps.
Definition: GA_Defragment.h:45
const GA_Attribute * getAttribute() const
Definition: GA_IndexMap.h:395
OPENVDB_API void initialize()
Global registration of basic types.
Definition: logging.h:316
SYS_FORCE_INLINE GA_Offset lastOffset() const
Definition: GA_IndexMap.h:179
GA_Size GA_Index
Define the strictness of GA_Offset/GA_Index.
Definition: GA_Types.h:611
SYS_FORCE_INLINE bool isTrivialMap() const
Definition: GA_IndexMap.h:288
GA_AttributeOwner
Definition: GA_Types.h:33
virtual int compare(const GA_IndexMap &map, GA_Offset item1, GA_Offset item2)=0
Compare two elements using strcmp() semantics.
bool isOffsetActive(GA_Offset offset) const
Returns true if the specified offset is referenced by an ordered element.
Definition: GA_IndexMap.h:481
SYS_FORCE_INLINE GA_Index indexSize() const
Definition: GA_IndexMap.h:103
GLuint index
Definition: glcorearb.h:785
bool reverseIndices()
SYS_FORCE_INLINE GA_Offset offsetFromIndex(GA_Index ordered_index) const
Definition: GA_IndexMap.h:117
void destroyIndex(GA_Index where)
Delete an element from the list by specifying the order.
GA_Offset addElement()
Definition: GA_IndexMap.h:440
#define GA_INVALID_INDEX
Definition: GA_Types.h:653
GLint GLint GLsizei GLint GLenum GLenum type
Definition: glcorearb.h:107
Container class for all geometry.
Definition: GA_Detail.h:96
bool isOffsetInRange(GA_Offset offset) const
Definition: GA_IndexMap.h:454
virtual bool initialize(const GA_IndexMap &map)=0
GA_Offset addElementBlock(GA_Size nelements)
SYS_FORCE_INLINE void forEachOffsetBreak(FUNCTOR &&functor) const
Definition: GA_IndexMap.h:526
Generic Attribute Interface class to access an attribute as a tuple.
Definition: GA_AIFTuple.h:32
#define UT_ASSERT_MSG(ZZ, MM)
Definition: UT_Assert.h:105
GA_Range getRange() const
Definition: GA_IndexMap.h:224
GA_OffsetList getOffsetFromIndexList() const
Definition: GA_IndexMap.h:244
GA_Offset getEnd() const
Returns the upper-bound on the end of the range.
Definition: GA_IndexMap.h:230
SYS_FORCE_INLINE GA_Offset offsetSize() const
Definition: GA_IndexMap.h:97
Generic Attribute Interface class to work with string indices directly, rather than string values...
void checkTrivial()
Definition: GA_IndexMap.h:651
GLenum src
Definition: glcorearb.h:1792