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 
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 first_free_i = 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(first_free_i) && index >= first_free_i)
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  /// @warning You @b must force defragmentation after swapping the index
273  /// order to maintain monotonicity of the index map.
274  /// @return The new index of the element, or -1 if there was an error
275  GA_Index reorder(GA_Offset data_offset, GA_Index new_order);
276 
277  /// @{
278  /// Swap the order of the two specified (ordered, not transient) data
279  /// offsets.
280  /// @warning You @b must force defragmentation after swapping the index
281  /// order to maintain monotonicity of the index map.
282  /// @return True on success, false on failure.
283  bool swapOrderByOffset(GA_Offset offset1, GA_Offset offset2);
284  bool swapOrderByIndex(GA_Index order1, GA_Index order2);
285  /// @}
286 
287  /// A trivial map is one where offsetFromIndex(i) == i for all elements.
288  /// That is, the offsets are in order and there are no vacancies.
290  bool isTrivialMap() const
291  {
292  GA_Size noff = offsetSize();
293  GA_Size nind = indexSize();
294  if (nind != noff)
295  return false;
296  // NOTE: We don't need to check myFirstFreeIndex, because
297  // if it's valid, offsetSize() > indexSize().
298  // NOTE: It *must* be threadsafe to call isTrivial() and
299  // compactIndices() at the same time, and compactIndices() calls
300  // GA_OffsetList::changeSize() on a non-trivial list, so
301  // GA_OffsetList::isTrivial() *must* return false, no matter
302  // what goes on in GA_OffsetList::changeSize().
303  return myOffsetFromIndex.isTrivial();
304  }
305 
307  bool isMonotonicMap() const
308  {
309  return myMonotonic;
310  }
311 
312  /// Class which compares the elements at two indices
313  /// Example: @code
314  /// class SortReverse : public GA_IndexMap::IndexCompare
315  /// {
316  /// SortReverse() {}
317  /// ~SortReverse() {}
318  /// bool initialize(const GA_IndexMap &map)
319  /// {
320  /// myOrder = new GA_Index[map.offsetSize()];
321  /// for (GA_Iterator it(GA_Range(map)); !it.atEnd();
322  /// ++it)
323  /// {
324  /// myOrder[it.getOffset()] =
325  /// map.indexFromOffset(it.getOffset());
326  /// }
327  /// }
328  /// int compare(const GA_IndexMap&, GA_Offset a, GA_Offset b)
329  /// {
330  /// if (myOrder[a] > myOrder[b])
331  /// return -1;
332  /// if (myOrder[a] < myOrder[b])
333  /// return 1;
334  /// return 0;
335  /// }
336  /// void finish(const GA_IndexMap &)
337  /// {
338  /// delete [] myOrder;
339  /// }
340  /// };
341  /// @endcode
343  {
344  public:
346  virtual ~IndexCompare() {}
347 
348  /// Called prior to the sort. If the method returns false, the
349  /// sort is aborted. If the sort is aborted, the finish() method
350  /// will @b not be called.
351  virtual bool initialize(const GA_IndexMap &map) = 0;
352 
353  /// Compare two elements using strcmp() semantics
354  virtual int compare(const GA_IndexMap &map,
355  GA_Offset item1,
356  GA_Offset item2) = 0;
357 
358  /// Called after the sort is complete. At this point, the index
359  /// will be ordered according to the sort.
360  virtual void finish(const GA_IndexMap &map) = 0;
361  };
362 
363  /// Convenience class which can be used to sort an index map based on an
364  /// attribute value. The attribute should either provide an AIFTuple or
365  /// AIFStringTuple interface. If neither interfaces are provided, this
366  /// class won't do any sorting.
367  /// Example: @code
368  /// GA_Detail &gdp;
369  /// GA_IndexMap &points = gdp.getIndexMap(GA_ATTRIB_POINT);
370  ///
371  /// // Sort by P.z
372  /// GA_IndexMap::AttributeCompare cmpPz(points, "P", 2);
373  /// points.sortIndices(cmpPz);
374  /// @endcode
376  {
377  public:
378  /// Sort the index map based on the values in the attribute. For
379  /// tuple attributes, compare the value for the given index.
380  AttributeCompare(const GA_Attribute *attribute, int tuple_index=0);
381  /// Construct given an index map and an attribute name
382  AttributeCompare(const GA_IndexMap &map,
383  const char *attribute_name,
384  int tuple_index=0);
385  /// Destructor
386  ~AttributeCompare() override;
387 
388  /// @{
389  /// Methods defined on IndexCompare
390  bool initialize(const GA_IndexMap &map) override;
391  int compare(const GA_IndexMap &map,
392  GA_Offset item1, GA_Offset item2) override;
393  void finish(const GA_IndexMap &map) override;
394  /// @}
395 
396  protected:
397  const GA_Attribute *getAttribute() const
398  { return myAttribute; }
399  const GA_AIFTuple *getAIFTuple() const
400  { return myTuple; }
402  { return mySTuple; }
403  int getTupleIndex() const
404  { return myIndex; }
405  bool getIsFloat() const
406  { return myFloat; }
407  private:
408  const GA_Attribute *myAttribute;
409  const GA_AIFTuple *myTuple;
410  const GA_AIFStringTuple *mySTuple;
411  int myIndex;
412  bool myFloat;
413  };
414 
415  /// Sort the index order using a comparator
416  bool sortIndices(IndexCompare &compare, bool stable=true);
417 
418  /// Sort a selection of elements
419  bool sortIndices(IndexCompare &compare, const GA_Range &range,
420  bool stable=true);
421 
422  /// Sort an array of GA_Offset data according to a comparator
423  bool sortOffsetArray(GA_OffsetArray &offsets, IndexCompare &compare,
424  bool stable=true) 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_LOAD) == GA_INVALID_INDEX && that.myFirstFreeIndex.load(SYS_MEMORY_ORDER_LOAD) == 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_LOAD 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_LOAD));
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_LOAD), 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.
GLenum GLint * range
Definition: glcorearb.h:1925
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:475
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:307
#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:399
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: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: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
CompareResults OIIO_API compare(const ImageBuf &A, const ImageBuf &B, float failthresh, float warnthresh, ROI roi={}, int nthreads=0)
GLdouble n
Definition: glcorearb.h:2008
GLintptr offset
Definition: glcorearb.h:665
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:401
#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
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: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:397
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:179
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:290
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:103
GLuint index
Definition: glcorearb.h:786
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: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
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)
type
Definition: core.h:1059
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: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:653
GLenum src
Definition: glcorearb.h:1793