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