HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
GA_OffsetList.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_OffsetList.h ( GA Library, C++)
7  *
8  * COMMENTS: Class to store a list of offsets/indices based on the
9  * GA_Offset/GA_Index types.
10  */
11 
12 #ifndef __GA_OffsetList__
13 #define __GA_OffsetList__
14 
15 #include "GA_API.h"
16 
17 #include "GA_Types.h"
18 
19 #include <UT/UT_ArrayHelp.h>
20 #include <UT/UT_Array.h>
21 #include <UT/UT_VectorTypes.h>
22 
23 #include <SYS/SYS_AtomicInt.h>
24 #include <SYS/SYS_Inline.h>
25 #include <SYS/SYS_Math.h>
26 #include <SYS/SYS_Types.h>
27 
28 class GA_Defragment;
29 class GA_LoadMap;
30 class GA_SaveMap;
31 class GA_IndexMap;
32 class UT_JSONParser;
33 class UT_JSONWriter;
34 class UT_MemoryCounter;
35 
36 #define GA_OFFSETLIST_VERBOSE_DEBUG 0
37 
38 // Forward declaration of subclass for use in superclass
39 template<typename FromType,typename ToType,typename INT_TYPE>
41 
42 /// GA_OffsetList implements an array of GA_Offsets.
43 /// Copy-on-write is used to reduce memory usage and make the copying of a
44 /// GA_OffsetList an inexpensive operation.
45 ///
46 /// See also: @ref JSON-GA_OffsetList
47 template <typename FromType, typename ToType, typename INT_TYPE=exint>
49 {
50 protected:
51  // These friend declarations are needed for accessing data in related types.
52  template<typename FromType2,typename ToType2,typename INT_TYPE2>
53  friend class GA_ListTypeRef;
54  template<typename FromType2,typename ToType2,typename INT_TYPE2>
55  friend class GA_ListType;
56 public:
57  typedef INT_TYPE theIntType;
58 protected:
59 
61 
62  // The shareable data stored in a GA_OffsetList
64  {
65  public:
66  static ListTypeData *allocate(exint capacity)
67  {
68  // NOTE: We should really try to fix the cases where we're
69  // allocating this with capacity zero, but we have to
70  // validate that it's safe to switch it to trivial instead,
71  // given the comment in changeSize() about it needing to be
72  // safe to call GA_IndexMap::compactIndices() and
73  // GA_IndexMap::isTrivial() at the same time, and needing
74  // for isTrivial() to return false.
75  //UT_ASSERT_MSG_P(capacity >= 1, "Why are we allocating something empty?");
76  exint bytes = sizeof(ListTypeData) + sizeof(INT_TYPE)*capacity;
77  ListTypeData *data = (ListTypeData *)malloc(bytes);
78  data->myRefCount.relaxedStore(1);
79  data->myCapacity = capacity;
80 #if GA_OFFSETLIST_VERBOSE_DEBUG
81  printf("Allocating %p with ref count 1 and capacity %d\n", data, int(capacity));
82  fflush(stdout);
83 #endif
84  return data;
85  }
86  ListTypeData *reallocate(exint new_capacity)
87  {
88  // See NOTE above about fixing cases where we're allocating this
89  // with capacity zero.
90  //UT_ASSERT_MSG_P(new_capacity >= 1, "Why are we allocating something empty?");
91  UT_ASSERT_P(myRefCount.relaxedLoad() == 1);
92 
93  ListTypeData *that = (ListTypeData *)realloc(this, sizeof(ListTypeData) + sizeof(INT_TYPE)*new_capacity);
94  // NOTE: this may no longer be valid, so we can't use it after this point.
95 
96 #if GA_OFFSETLIST_VERBOSE_DEBUG
97  printf("Reallocating %p to %p with ref count %d from capacity %d to %d\n", this, that, int(that->myRefCount.relaxedLoad()), int(that->myCapacity), int(new_capacity));
98  fflush(stdout);
99 #endif
100 
101  that->myCapacity = new_capacity;
102  return that;
103  }
105  {
106  UT_ASSERT_P(myRefCount.relaxedLoad() == 1);
107  if (myCapacity >= mincapacity)
108  return this;
109 
110  mincapacity = SYSmax(mincapacity, UTbumpAlloc(myCapacity));
111  ListTypeData *that = reallocate(mincapacity);
112  // NOTE: this may no longer be valid, so we can't use it after this point.
113  return that;
114  }
116  {
117  UT_ASSERT_P(myRefCount.relaxedLoad() == 1);
118  if (myCapacity == new_capacity)
119  return this;
120 
121  ListTypeData *that = reallocate(new_capacity);
122  // NOTE: this may no longer be valid, so we can't use it after this point.
123  return that;
124  }
125  ListTypeData *copy(exint size,exint new_capacity) const
126  {
127  ListTypeData *that = allocate(new_capacity);
128  INT_TYPE *dest = that->getRawData();
129  const INT_TYPE *src = getRawData();
130  if (new_capacity < size)
131  size = new_capacity;
132  for (exint i = 0; i < size; ++i)
133  dest[i] = src[i];
134  return that;
135  }
136 
137  // methods to manage sharing
138  void ref() const
139  {
140 #if GA_OFFSETLIST_VERBOSE_DEBUG
141  exint new_count =
142 #endif
143  myRefCount.add(1);
144 #if GA_OFFSETLIST_VERBOSE_DEBUG
145  printf("Incrementing ref of %p with capacity %d from %d to %d\n", this, int(myCapacity), int(new_count-1), int(new_count));
146  fflush(stdout);
147  if (new_count < 0)
148  {
149  printf("!!! ERROR: NEGATIVE REF COUNT INCREMENTED on %p !!!", this);
150  fflush(stdout);
151  }
152 #endif
153  }
154  void unref()
155  {
156  exint new_count = myRefCount.add(-1);
157 #if GA_OFFSETLIST_VERBOSE_DEBUG
158  printf("Decrementing ref of %p with capacity %d from %d to %d\n", this, int(myCapacity), int(new_count+1), int(new_count));
159  fflush(stdout);
160  if (new_count < 0)
161  {
162  printf("!!! ERROR: NEGATIVE REF COUNT DECREMENTED on %p !!!", this);
163  fflush(stdout);
164  }
165 #endif
166  UT_ASSERT_P(new_count >= 0);
167  if (new_count == 0)
168  {
169  free(this);
170  }
171  }
172  bool isShared() const
173  { return myRefCount.relaxedLoad() != 1; }
174 
176  int64 getMemoryUsage(bool inclusive) const
177  { return (inclusive ? sizeof(*this) : 0) + sizeof(INT_TYPE)*myCapacity; }
178 
179  void countMemory(UT_MemoryCounter &counter, bool inclusive) const;
180 
183  { return myCapacity; }
184 
185  bool isTrivial(exint size) const
186  {
187  if (size > 1)
188  {
189  const INT_TYPE *start = getRawData();
190  const INT_TYPE offset = start[0];
191  for (INT_TYPE i = 1; i < size; i++)
192  {
193  if (start[i] != offset+i)
194  return false;
195  }
196  }
197  return true;
198  }
199 
200  bool isAscending(exint size) const
201  {
202  if (size > 1)
203  {
204  const INT_TYPE *data = getRawData();
205  INT_TYPE prev = data[0];
206  for (exint i = 1; i < size; i++)
207  {
208  INT_TYPE cur = data[i];
209  if (cur < prev)
210  return false;
211  prev = cur;
212  }
213  }
214  return true;
215  }
216 
217  // Set the entries...
218  // in a bizarre way whose motivations I don't really understand.
219  // Maybe someday I'll clean up the changing of size/capacity for GA_ListType.
220  ListTypeData *setEntries(GA_Size sz, exint old_size, bool doresize=true);
221 
222  // adding and removing elements
223  FromType insert(FromType index, ToType value, FromType size);
224  FromType multipleInsert(FromType index, GA_Size count, FromType size);
225  FromType remove(FromType i, FromType size)
226  {
227  if (i < FromType(0) || i >= size)
228  return FromType(-1);
229 
230  INT_TYPE *start = getRawData();
231  for (FromType j = i+1; j < size; ++j)
232  {
233  start[j-1] = start[j];
234  }
235  return i;
236  }
237  FromType findAndRemove(ToType v, FromType size)
238  {
239  INT_TYPE *array = getRawData();
240  INT_TYPE *p = array;
241  const INT_TYPE *end = array + size;
242  for (; p != end; ++p)
243  {
244  if (ToType(*p) == v)
245  {
246  FromType idx(p - array);
247  for (FromType j = idx+1; j < size; ++j)
248  {
249  array[j-1] = array[j];
250  }
251  return idx;
252  }
253  }
254  return FromType(-1);
255  }
256  GA_Size removeAll(ToType v, FromType size)
257  {
258  INT_TYPE *start = getRawData();
259  const INT_TYPE *src = start;
260  const INT_TYPE *end = start + size;
261  INT_TYPE *dest = start;
262  for (; src != end; ++src)
263  {
264  if (*src != INT_TYPE(v))
265  {
266  if (dest != src)
267  *dest = *src;
268  ++dest;
269  }
270  }
271  return dest-start;
272  }
273  FromType find(ToType v, FromType s, FromType size) const
274  {
275  const INT_TYPE *array = getRawData();
276  const INT_TYPE *p = array + s;
277  const INT_TYPE *end = array + size;
278  for (; p != end; ++p)
279  {
280  if (ToType(*p) == v)
281  return FromType(p - array);
282  }
283  return FromType(-1);
284  }
285  FromType findSorted(ToType v, FromType s, FromType size) const;
286 
287  // basic accessors
289  INT_TYPE &operator()(exint index)
290  {
291  return ((INT_TYPE *)(this+1))[index];
292  }
294  const INT_TYPE &operator()(exint index) const
295  {
296  return ((const INT_TYPE *)(this+1))[index];
297  }
299  void set(FromType index, ToType value)
300  { (*this)(index) = value; }
302  ToType get(FromType index) const
303  { return ToType((*this)(index)); }
304 
305  void constant(ToType value, FromType size)
306  {
307  INT_TYPE *start = getRawData();
308  for (INT_TYPE i = 0; i < INT_TYPE(size); ++i)
309  start[i] = INT_TYPE(value);
310  }
311 
312  template<typename S>
313  void set(const S *data, exint size, ToType offset)
314  {
315  UT_ASSERT_P(myCapacity >= size);
316  INT_TYPE *array = getRawData();
317  if (offset == ToType(0))
318  {
319  for (exint i = 0; i < size; ++i)
320  array[i] = ToType(data[i]);
321  }
322  else
323  {
324  for (exint i = 0; i < size; ++i)
325  array[i] = ToType(data[i]) + offset;
326  }
327  }
328  template<typename S>
329  void copyAdd(FromType destindex, const S *values, GA_Size srcindex, GA_Size n, ToType offset)
330  {
331  INT_TYPE *array = getRawData();
332  for (GA_Size i = 0; i < n; ++i)
333  array[i + destindex] = values[i + srcindex] + offset;
334  }
335  template<typename S>
336  void copyAdd(FromType destindex, const GA_ListTypeRef<FromType, ToType, S> &values, FromType srcindex, GA_Size n, ToType offset)
337  {
338  INT_TYPE *array = getRawData();
339  if (values.isTrivial())
340  {
341  ToType combined = values.myTrivialOffset + GA_Size(srcindex) + offset;
342  for (GA_Size i = 0; i < n; ++i)
343  array[i + destindex] = combined + i;
344  }
345  else
346  {
347  const S *src = values.myData->getRawData();
348  for (GA_Size i = 0; i < n; ++i)
349  array[i + destindex] = src[i + srcindex] + offset;
350  }
351  }
352 
353  void cycle(GA_Size howMany, FromType size)
354  {
355  // This looks silly, I know, but I didn't want to have to
356  // verify that UT_Array::cycle goes in the same direction
357  // as std::rotate, and cycle has some edge case handling,
358  // e.g. for negative values.
359  UT_Array<INT_TYPE> array;
360  array.unsafeShareData(getRawData(), size);
361  array.cycle(howMany);
362  array.unsafeClearData();
363  }
364  void reverse(FromType size)
365  {
366  INT_TYPE *array = getRawData();
367  std::reverse(array, array+size);
368  }
369 
370  void sortAscending(FromType size)
371  {
372  INT_TYPE *array = getRawData();
373  std::sort(array, array+size, std::less<INT_TYPE>());
374  }
375 
376  FromType sortAndRemoveDuplicates(FromType size)
377  {
378  if (size <= FromType(1))
379  return size;
380 
381  INT_TYPE *array = getRawData();
382  INT_TYPE *end = array + size;
383  std::sort(array, end, std::less<INT_TYPE>());
384 
385  // Sorted remove duplicates
386  const INT_TYPE *src = array+1;
387  INT_TYPE *dest = array+1;
388  INT_TYPE prev = array[0];
389  for (; src != end; ++src)
390  {
391  INT_TYPE cur = *src;
392  if (cur != prev)
393  {
394  if (dest != src)
395  *dest = cur;
396  prev = cur;
397  ++dest;
398  }
399  }
400  return FromType(dest-array);
401  }
402 
403  FromType findInRange(FromType start, FromType end, ToType search) const
404  {
405  const INT_TYPE *array = getRawData();
406  for ( ; start < end; start++)
407  {
408  if (ToType(array[start]) == search)
409  return start;
410  }
411  return end;
412  }
413  FromType findInRangeNotEqual(FromType start, FromType end, ToType search) const
414  {
415  const INT_TYPE *array = getRawData();
416  for ( ; start < end; start++)
417  {
418  if (ToType(array[start]) != search)
419  return start;
420  }
421  return end;
422  }
423 
424  FromType findValidInRange(FromType start, FromType end) const
425  {
426  const INT_TYPE *array = getRawData();
427  for ( ; start < end; start++)
428  {
429  if (GAisValid(GA_Size(array[start])))
430  return start;
431  }
432  return end;
433  }
434  FromType findInvalidInRange(FromType start, FromType end) const
435  {
436  const INT_TYPE *array = getRawData();
437  for ( ; start < end; start++)
438  {
439  if (!GAisValid(GA_Size(array[start])))
440  return start;
441  }
442  return end;
443  }
444 
446  const INT_TYPE *getRawData() const
447  {
448  return (const INT_TYPE *)(this+1);
449  }
451  INT_TYPE *getRawData()
452  {
453  return (INT_TYPE *)(this+1);
454  }
455 
456  private:
457  // We use a SYS_AtomicCounter to avoid losing references when multiple
458  // threads add and remove references to the shared values
459  mutable SYS_AtomicCounter myRefCount;
460  exint myCapacity;
461  };
462 
463 public:
464  /// Default constructor
466  explicit GA_ListTypeRef()
467  {
468  // Unlike in subclass, leave the data uninitialized until assigned,
469  // because this class doesn't need to own its data.
470  }
471 
472  /// Copy constructor
475 #if GA_OFFSETLIST_VERBOSE_DEBUG
476  {
477  if (!src.isTrivial())
478  {
479  printf("%p listref copy constructor with data %p from %p\n", this, src.myData, &src);
480  fflush(stdout);
481  }
482  // NOTE: I'm assuming that it's expected that myIsFlagSet will be copied.
483  memcpy(this, &src, sizeof(*this));
484  }
485 #else
486  = default;
487 #endif
488 
489  /// Move constructor
492 #if GA_OFFSETLIST_VERBOSE_DEBUG
493  {
494  if (!src.isTrivial())
495  {
496  printf("%p listref move constructor with data %p from %p\n", this, src.myData, &src);
497  fflush(stdout);
498  }
499  memcpy(this, &src, sizeof(*this));
500  }
501 #else
502  = default;
503 #endif
504 private:
505  /// Move constructor from subclass owning myData is forbidden
507  {
508  UT_ASSERT_MSG(0,"GA_ListTypeRef cannot be move-constructed from GA_ListType, because the data will be invalid momentarily.");
509  }
510 public:
511 
512  /// Trivial list constructor
514  GA_ListTypeRef(ToType startvalue, GA_Size size, bool flag_set=false)
515  {
516  myIsTrivial = true;
517  myTrivialOffset = startvalue;
518  myIsFlagSet = flag_set;
519  mySize = size;
520  }
521 
522  /// Destructor
524  ~GA_ListTypeRef() = default;
525 
526  /// Copy assignment operator
528  GA_ListTypeRef &operator=(const GA_ListTypeRef &src)
529 #if GA_OFFSETLIST_VERBOSE_DEBUG
530  {
531  if (!src.isTrivial())
532  {
533  printf("%p listref copy constructor with data %p from %p\n", this, src.myData, &src);
534  fflush(stdout);
535  }
536  // NOTE: I'm assuming that it's expected that myIsFlagSet will be copied.
537  memcpy(this, &src, sizeof(*this));
538  return *this;
539  }
540 #else
541  = default;
542 #endif
543 
544  /// Move assignment operator
546  GA_ListTypeRef &operator=(GA_ListTypeRef &&src)
547 #if GA_OFFSETLIST_VERBOSE_DEBUG
548  {
549  if (!src.isTrivial())
550  {
551  printf("%p listref move constructor with data %p from %p\n", this, src.myData, &src);
552  fflush(stdout);
553  }
554  // NOTE: I'm assuming that it's expected that myIsFlagSet will be copied.
555  memcpy(this, &src, sizeof(*this));
556  return *this;
557  }
558 #else
559  = default;
560 #endif
561 private:
562  /// Move constructor from subclass owning myData is forbidden
564  {
565  UT_ASSERT_MSG(0,"GA_ListTypeRef cannot be move-assigned from GA_ListType, because the data will be invalid momentarily.");
566  return *this;
567  }
568 public:
569 
570  /// clear removes all of the entries
572  void clear()
573  {
574  // NOTE: Subclass clear will unref myData if non-trivial.
575  myIsTrivial = true;
576  // NOTE: DON'T set myIsFlagSet, since it's independent of whether
577  // this list is clear.
578  myTrivialOffset = 0;
579  mySize = 0;
580  }
581 
582  /// Makes the list a trivial list with the specified start value and size
584  void setTrivial(ToType startvalue, GA_Size size)
585  {
586  UT_ASSERT(size >= 0);
587  myIsTrivial = true;
588  myTrivialOffset = startvalue;
589  mySize = size;
590  }
591 
592  /// Makes the list a trivial list with the specified start value and size,
593  /// and also sets the extra flag.
595  void setTrivial(ToType startvalue, GA_Size size, bool flag)
596  {
597  UT_ASSERT(size >= 0);
598  myIsTrivial = true;
599  myTrivialOffset = startvalue;
600  mySize = size;
601  myIsFlagSet = flag;
602  }
603 
604  /// Returns the allocated capacity of the list
607  {
608  return isTrivial() ? 0 : myData->capacity();
609  }
610  /// Returns the number of used elements in the list (always <= capacity())
612  FromType entries() const
613  { return size(); }
614  /// Returns the number of used elements in the list (always <= capacity())
616  FromType size() const
617  {
618  return FromType(mySize);
619  }
620  /// Check whether this offset list is stored in a compact
621  /// (non-allocated) form.
622  /// NOTE: It *must* be threadsafe to call this while hardening
623  /// a non-trivial list and get false as a return value.
624  /// GA_IndexMap::compactIndices() may be called at the same
625  /// time as GA_IndexMap::isTrivial(), and this *must*
626  /// return false, no matter what the race.
628  bool isTrivial() const { return myIsTrivial != 0; }
630  bool getExtraFlag() const { return myIsFlagSet != 0; }
632  void setExtraFlag(bool v) { myIsFlagSet = v; }
633 
634  // Returns true iff this and that are either both trivial and equal
635  // or if both are not trivial and share the same ListTypeData pointer.
636  // This does not fully check for equality!
637  bool isSame(const GA_ListTypeRef &that) const
638  {
639  if (isTrivial())
640  {
641  return (that.isTrivial() &&
642  (mySize == that.mySize) &&
643  (myTrivialOffset == that.myTrivialOffset));
644  }
645  return (myData == that.myData);
646  }
647 
648  /// Identifies whether the data is in ascending order
649  bool isAscending() const;
650 
651  /// Linearly search for the specified entry. Returns the index of first
652  /// matching element found, -1 otherwise. An optional starting index can
653  /// be specified in s.
654  FromType find(ToType value, FromType s = FromType(0)) const;
655 
656  /// Find the target in a sorted list.
657  FromType findSorted(ToType value, FromType s=FromType(0)) const;
658 
659  /// Get the the value at the index
661  ToType get(FromType index) const
662  {
663  UT_ASSERT_P(index >= FromType(0) && index < size());
664  return isTrivial()
665  ? ToType(GA_Size(index)+myTrivialOffset)
666  : myData->get(index);
667  }
668 
669  /// Returns the start, assuming this list is trivial.
671  ToType trivialStart() const
672  {
673  UT_ASSERT_P(isTrivial());
674  return ToType(myTrivialOffset);
675  }
676 
677  /// Test a sub-block for equality with another list
678  bool isEqual(const GA_ListTypeRef &other,
679  FromType start, FromType end) const;
680 
681  /// Return the value of the last element
682  ToType last() const
683  {
684  exint last_index = mySize-1;
685  return isTrivial()
686  ? ToType(myTrivialOffset+last_index)
687  : myData->get(FromType(last_index));
688  }
689 
690  /// Convenience () operator to access the list entries
692  ToType operator()(FromType i) const { return get(i); }
693 
695  ToType operator[](FromType i) const { return get(i); }
696 
697  /// Finds the first instance of the search pattern in the given
698  /// range. Returns end if not found.
699  FromType findInRange(FromType start, FromType end, ToType search) const
700  {
701  if (isTrivial())
702  {
703  FromType matchingindex = FromType(GA_Size(search) - GA_Size(myTrivialOffset));
704  if (matchingindex >= start && matchingindex < end)
705  return matchingindex;
706  // No match.
707  return end;
708  }
709  return myData->findInRange(start, end, search);
710  }
711  FromType findInRangeNotEqual(FromType start, FromType end, ToType search) const
712  {
713  if (isTrivial())
714  {
715  FromType matchingindex = FromType(GA_Size(search) - GA_Size(myTrivialOffset));
716  // start is always a match. If not, start+1 is.
717  if (matchingindex != start)
718  return start;
719  start += 1;
720  if (start > end)
721  return end;
722  return start;
723  }
724  return myData->findInRangeNotEqual(start, end, search);
725  }
726  FromType findValidInRange(FromType start, FromType end) const
727  {
728  if (isTrivial())
729  {
730  // NOTE: We can have trivial lists with negative offsets!
731  // If we have a valid trivial offset, everything matches.
732  if (GAisValid(myTrivialOffset))
733  return start;
734  if (GAisValid(ToType(GA_Size(start)) + ToType(myTrivialOffset)))
735  return start;
736  return SYSmin(end, FromType(-GA_Size(myTrivialOffset)));
737  }
738  return myData->findValidInRange(start, end);
739  }
740  FromType findInvalidInRange(FromType start, FromType end) const
741  {
742  if (isTrivial())
743  {
744  // NOTE: We can have trivial lists with negative offsets!
745  // If we have a valid trivial offset or start, nothing matches.
746  if (GAisValid(myTrivialOffset))
747  return end;
748  if (GAisValid(ToType(GA_Size(start)) + ToType(myTrivialOffset)))
749  return end;
750  return start;
751  }
752  return myData->findInvalidInRange(start, end);
753  }
754 
755  /// Calls a functor (e.g. a lambda) for each entry, only checking
756  /// for triviality once, to reduce overhead.
757  template<typename FUNCTOR>
759  void forEach(FUNCTOR &&functor) const
760  {
761  if (myIsTrivial)
762  {
763  ToType value(myTrivialOffset);
764  const ToType end(value + mySize);
765  for (; value != end; ++value)
766  {
767  functor(value);
768  }
769  }
770  else
771  {
772  const INT_TYPE *data = myData->getRawData();
773  const INT_TYPE *const end = data + mySize;
774  for (; data != end; ++data)
775  {
776  functor(ToType(*data));
777  }
778  }
779  }
780 
781  /// @note It's likely more efficient to use @c forEach() than iterators
782  template <typename LIST_T>
784  public std::iterator<std::random_access_iterator_tag,
785  ToType, FromType>
786  {
787  public:
788  using reference = ToType;
789 
791  : myList(nullptr)
792  , myCurrent(-1)
793  {
794  }
795 
796  template <typename EIT>
798  : myList(src.myList)
799  , myCurrent(src.myCurrent)
800  {
801  }
803  {
804  return myList->get(myCurrent);
805  }
806  reference item() const
807  {
808  return myList->get(myCurrent);
809  }
810  reference operator[](FromType n) const
811  {
812  return myList->get(myCurrent+n);
813  }
815  {
816  ++myCurrent;
817  return *this;
818  }
820  {
821  base_iterator tmp = *this;
822  ++myCurrent;
823  return tmp;
824  }
826  {
827  --myCurrent;
828  return *this;
829  }
831  {
832  base_iterator tmp = *this;
833  --myCurrent;
834  return tmp;
835  }
837  {
838  myCurrent += n;
839  return *this;
840  }
841  base_iterator operator+(FromType n) const
842  {
843  return base_iterator(myList, myCurrent+n);
844  }
846  { return (*this) += (-n); }
847  base_iterator operator-(FromType n) const
848  { return (*this) + (-n); }
849  template <typename LT>
850  bool operator==(const base_iterator<LT> &r) const
851  { return r.myCurrent == myCurrent; }
852  template <typename LT>
853  bool operator!=(const base_iterator<LT> &r) const
854  { return r.myCurrent != myCurrent; }
855 
856  #define CMP_OP(OP) \
857  template <typename LT> \
858  bool operator OP(const base_iterator<LT> &r) const { \
859  return myCurrent OP r.myCurrent; \
860  }
861  CMP_OP(<)
862  CMP_OP(>)
863  CMP_OP(<=)
864  CMP_OP(>=)
865  #undef CMP_OP
866  template <typename LT>
867  FromType operator-(const base_iterator<LT> &r) const
868  { return (myCurrent - r.myCurrent); }
869  protected:
870  friend class GA_ListTypeRef<FromType, ToType, INT_TYPE>;
871  base_iterator(LIST_T *list, FromType c)
872  : myList(list)
873  , myCurrent(c)
874  {
875  }
876  private:
877  LIST_T *myList;
878  FromType myCurrent;
879  };
880  using iterator = base_iterator<this_type>;
881  using const_iterator = base_iterator<const this_type>;
882 
883  /// @{
884  /// @note It's likely more efficient to use @c forEach() than iterators
885  iterator begin() { return iterator(this, FromType(0)); }
886  iterator end() { return iterator(this, size()); }
887  const_iterator begin() const { return const_iterator(this, FromType(0)); }
888  const_iterator end() const { return const_iterator(this, size()); }
889  /// @}
890 
891  /// Report memory usage (includes all shared memory)
893  int64 getMemoryUsage(bool inclusive) const
894  {
895  return (inclusive ? sizeof(*this) : 0) + (!isTrivial() ? myData->getMemoryUsage(true) : 0);
896  }
897 
899  const INT_TYPE *getArray() const
900  {
901  return !isTrivial() ? myData->getRawData() : nullptr;
902  }
904  INT_TYPE *getArray()
905  {
906  return !isTrivial() ? myData->getRawData() : nullptr;
907  }
908 
909 protected:
910  static const intptr_t POINTER_MASK = ~0x1;
911  static const intptr_t TRIVIAL_MASK = 0x1;
912  static const intptr_t FLAG_MASK = 0x1;
913 #ifndef SESI_LITTLE_ENDIAN
914 #error "Make sure the bitfields in the union work on big endian platforms!"
915 #endif
916  union {
917  ListTypeData *myData;
918  struct {
919  // NOTE: myTrivialOffset must be signed to support
920  // GA_INVALID_OFFSET and GA_INVALID_INDEX, but
921  // mySize can be unsigned.
922  int64 myIsTrivial:1;
923  int64 myTrivialOffset:63;
924  // Make sure that this flag doesn't overlap with the
925  // pointer, so that it doesn't need to be considered
926  // when reading/writing myData. myIsTrivial
927  // can overlap with myData, because it's
928  // mutually exclusive with using myData.
929  uint64 myIsFlagSet:1;
930  uint64 mySize:63;
931  };
932  };
933 };
934 
935 template <typename FromType, typename ToType, typename INT_TYPE=exint>
936 class GA_API GA_ListType : public GA_ListTypeRef<FromType, ToType, INT_TYPE>
937 {
938 private:
939  // These friend declarations are needed for accessing data in related types.
940  template<typename FromType2,typename ToType2,typename INT_TYPE2>
941  friend class GA_ListTypeRef;
942  template<typename FromType2,typename ToType2,typename INT_TYPE2>
943  friend class GA_ListType;
944 
946 protected:
947  using Base::myData;
948  using Base::myIsTrivial;
949  using Base::myTrivialOffset;
950  using Base::myIsFlagSet;
951  using Base::mySize;
952  using Base::POINTER_MASK;
953  using Base::TRIVIAL_MASK;
954  using Base::FLAG_MASK;
955  // I don't know why one build machine running GCC 4.8 needed
956  // "ListTypeData =" and the other didn't, but I've put it here
957  // anyway, because it should keep everyone happy.
958  using ListTypeData = typename Base::ListTypeData;
959 public:
960  using Base::get;
961  using Base::isTrivial;
962  using Base::size;
963  using Base::capacity;
964  using typename Base::theIntType;
965 public:
966  /// Default constructor
968  explicit GA_ListType()
969  : Base()
970  {
971  myIsTrivial = true;
972  myTrivialOffset = 0;
973  myIsFlagSet = false;
974  mySize = 0;
975  }
976 
977  /// Copy constructor
980  : Base()
981  {
982  if (!src.isTrivial())
983  {
984 #if GA_OFFSETLIST_VERBOSE_DEBUG
985  printf("%p adding reference to %p (orig reference by list %p) in copy constructor\n", this, src.myData, &src);
986  fflush(stdout);
987 #endif
988  src.myData->ref();
989  }
990  // NOTE: I'm assuming that it's expected that myIsFlagSet will be copied.
991  Base::operator=(src);
992  }
993 
994  /// Move constructor
997  : Base()
998  {
999 #if GA_OFFSETLIST_VERBOSE_DEBUG
1000  if (!src.isTrivial())
1001  {
1002  printf("%p stealing reference to %p (orig reference by list %p) in move constructor\n", this, src.myData, &src);
1003  fflush(stdout);
1004  }
1005 #endif
1006  Base::operator=(src);
1007  src.myIsTrivial = true;
1008  }
1009 
1010  /// Copy constructor from GA_ListTypeRef.
1011  /// Although it may seem strange to have this at all, it should be
1012  /// safe, since the destination does take (shared) ownership of any
1013  /// non-trivial data. There should be a GA_ListType somewhere else
1014  /// that already owns this.
1016  explicit GA_ListType(const Base &src)
1017  : Base()
1018  {
1019  if (!src.isTrivial())
1020  {
1021 #if GA_OFFSETLIST_VERBOSE_DEBUG
1022  printf("%p adding reference to %p (orig reference by listref %p) in list(listref) type conversion constructor\n", this, src.myData, &src);
1023  fflush(stdout);
1024 #endif
1025  src.myData->ref();
1026  UT_ASSERT_MSG_P(src.myData->isShared(), "Something should have already owned this data.");
1027  }
1028  // NOTE: I'm assuming that it's expected that myIsFlagSet will be copied.
1029  Base::operator=(src);
1030  }
1031 
1032  /// Trivial list constructor
1034  GA_ListType(ToType startvalue, GA_Size size, bool flag_set=false)
1035  : Base(startvalue, size, flag_set)
1036  {}
1037 
1038  // This will construct a GA_ListType by copying a portion of the array.
1039  GA_ListType(const UT_Array<ToType> &src, FromType start=FromType(0), FromType end=FromType(-1));
1040 
1041  /// Destructor
1044  {
1045  if (!isTrivial())
1046  {
1047 #if GA_OFFSETLIST_VERBOSE_DEBUG
1048  printf("%p removing reference to %p in desctructor\n", this, myData);
1049  fflush(stdout);
1050 #endif
1051  myData->unref();
1052  }
1053  }
1054 
1055  /// Copy assignment operator
1058  {
1059  if (!isTrivial())
1060  {
1061 #if GA_OFFSETLIST_VERBOSE_DEBUG
1062  printf("%p removing reference to %p in copy assignment operator\n", this, myData);
1063  fflush(stdout);
1064 #endif
1065  myData->unref();
1066  }
1067  if (!src.isTrivial())
1068  {
1069 #if GA_OFFSETLIST_VERBOSE_DEBUG
1070  printf("%p adding reference to %p (orig reference by list %p) in copy assignment operator\n", this, src.myData, &src);
1071  fflush(stdout);
1072 #endif
1073  src.myData->ref();
1074  }
1075  // NOTE: I'm assuming that it's expected that myIsFlagSet will be copied.
1076  Base::operator=(src);
1077  return *this;
1078  }
1079 
1080  /// Move assignment operator
1083  {
1084  if (!isTrivial())
1085  {
1086 #if GA_OFFSETLIST_VERBOSE_DEBUG
1087  printf("%p removing reference to %p in move assignment operator\n", this, myData);
1088  fflush(stdout);
1089 #endif
1090  myData->unref();
1091  }
1092 #if GA_OFFSETLIST_VERBOSE_DEBUG
1093  if (!src.isTrivial())
1094  {
1095  printf("%p stealing reference to %p (orig reference by list %p) in move assignment operator\n", this, src.myData, &src);
1096  fflush(stdout);
1097  }
1098 #endif
1099  // NOTE: I'm assuming that it's expected that myIsFlagSet will be copied.
1100  Base::operator=(src);
1101  src.myIsTrivial = true;
1102  return *this;
1103  }
1104 
1105  /// Copy assignment operator from GA_ListTypeRef.
1106  /// Although it may seem strange to have this at all, it should be
1107  /// safe, since the destination does take (shared) ownership of any
1108  /// non-trivial data. There should be a GA_ListType somewhere else
1109  /// that already owns this.
1112  {
1113  if (!isTrivial())
1114  {
1115 #if GA_OFFSETLIST_VERBOSE_DEBUG
1116  printf("%p removing reference to %p in copy-from-listref assignment operator\n", this, myData);
1117  fflush(stdout);
1118 #endif
1119  myData->unref();
1120  }
1121  if (!src.isTrivial())
1122  {
1123 #if GA_OFFSETLIST_VERBOSE_DEBUG
1124  printf("%p adding reference to %p (orig reference by listref %p) in copy-from-listref assignment operator\n", this, src.myData, &src);
1125  fflush(stdout);
1126 #endif
1127  src.myData->ref();
1128  UT_ASSERT_MSG_P(src.myData->isShared(), "Something should have already owned this data.");
1129  }
1130  // NOTE: I'm assuming that it's expected that myIsFlagSet will be copied.
1131  Base::operator=(src);
1132  return *this;
1133  }
1134 
1135  /// Count memory usage using a UT_MemoryCounter in order to count
1136  /// shared memory correctly.
1137  /// If inclusive is true, the size of this object is counted,
1138  /// else only memory owned by this object is counted.
1139  /// If this is pointed to by the calling object, inclusive should be true.
1140  /// If this is contained in the calling object, inclusive should be false.
1141  /// (Its memory was already counted in the size of the calling object.)
1142  void countMemory(UT_MemoryCounter &counter, bool inclusive) const;
1143 
1144  /// clear removes all of the entries
1146  void clear()
1147  {
1148  if (!isTrivial())
1149  {
1150 #if GA_OFFSETLIST_VERBOSE_DEBUG
1151  printf("%p removing reference to %p in clear function\n", this, myData);
1152  fflush(stdout);
1153 #endif
1154  myData->unref();
1155  }
1156  myIsTrivial = true;
1157  // NOTE: DON'T set myIsFlagSet, since it's independent of whether
1158  // this list is clear.
1159  myTrivialOffset = 0;
1160  mySize = 0;
1161  }
1162 
1163  /// Identifies whether the data is a trivial mapping and if so,
1164  /// eliminates storage for the map.
1165  void computeTrivial();
1166 
1167  /// Makes the list a trivial list with the specified start value and size
1168  void setTrivial(ToType startvalue, GA_Size size)
1169  {
1170  UT_ASSERT(size >= 0);
1171  if (!isTrivial())
1172  {
1173 #if GA_OFFSETLIST_VERBOSE_DEBUG
1174  printf("%p removing reference to %p in setTrivial(start,size)\n", this, myData);
1175  fflush(stdout);
1176 #endif
1177  myData->unref();
1178  myIsTrivial = true;
1179  }
1180  myTrivialOffset = startvalue;
1181  mySize = size;
1182  }
1183 
1184  /// Makes the list a trivial list with the specified start value and size,
1185  /// and also sets the extra flag.
1186  void setTrivial(ToType startvalue, GA_Size size, bool flag)
1187  {
1188  UT_ASSERT(size >= 0);
1189  if (!isTrivial())
1190  {
1191 #if GA_OFFSETLIST_VERBOSE_DEBUG
1192  printf("%p removing reference to %p in setTrivial(start,size,flag)\n", this, myData);
1193  fflush(stdout);
1194 #endif
1195  myData->unref();
1196  myIsTrivial = true;
1197  }
1198  myTrivialOffset = startvalue;
1199  mySize = size;
1200  myIsFlagSet = flag;
1201  }
1202 
1203  /// Set the number of entries - if the number is smaller than the current
1204  /// entries, the capacity may be decreased. If doresize is false,
1205  /// only the number of entries is changed, not the size.
1206  void setEntries(FromType sz, bool doresize=true);
1207  /// Reserve capacity for a number of entries (prevents reallocation as
1208  /// elements are appended).
1209  /// This does nothing if the list is currently trivial.
1210  void reserve(FromType mincapacity); // Reserve capacity
1211 
1212  /// If trivial, this sets the size to the minimum of the current size and new_capacity.
1213  /// If not trivial, this sets the capacity to new_capacity, (also correctly decreasing
1214  /// the size if currently greater than new_capacity.)
1215  void changeSize(FromType new_capacity);
1216 
1217  /// Add a single entry (may grow array)
1218  FromType append(ToType value)
1219  {
1220  if (isTrivial())
1221  {
1222  if (!mySize)
1223  {
1225  mySize = 1;
1226  return FromType(0);
1227  }
1228  if (value == ToType(myTrivialOffset) + mySize)
1229  {
1230  ++mySize;
1231  return FromType(mySize-1);
1232  }
1233  }
1234  harden(mySize+1);
1235  myData->set(FromType(mySize), value);
1236  ++mySize;
1237  return FromType(mySize-1);
1238  }
1239 
1240  /// Append all the entries from the source list. The offset will be added
1241  /// to each value in the source list.
1242  void append(const GA_ListType &src);
1243 
1244  /// Insert a single entry (may grow array)
1245  FromType insert(FromType i, ToType value);
1246 
1247  /// Insert count entries at the given index (may grow array). The new
1248  /// entries will be uninitialized.
1249  FromType multipleInsert(FromType i, GA_Size count);
1250 
1251  /// Remove the entry at the given offset
1252  FromType remove(FromType i);
1253  /// Find an entry and remove it from the list
1254  FromType findAndRemove(ToType i);
1255  /// Alias for remove to match UT array types
1256  FromType removeIndex(FromType i) { return remove(i); }
1257  /// Remove all matching entries from the list
1258  GA_Size removeAll(ToType i);
1259  /// Remove the last entry
1260  void removeLast()
1261  {
1262  UT_ASSERT_P(mySize > 0);
1263  --mySize;
1264  }
1265 
1266  /// Sort entries into ascending order
1267  void sortAscending();
1268 
1269  /// Sort entries into ascending order and remove duplicates
1270  void sortAndRemoveDuplicates();
1271 
1272  /// Set the index to the value
1273  void set(FromType index, ToType value)
1274  {
1275  UT_ASSERT_P(index >= FromType(0) && index < FromType(mySize));
1276  if (isTrivial())
1277  {
1278  if (myTrivialOffset+GA_Size(index) == GA_Size(value))
1279  return;
1280  if (mySize==1)
1281  {
1282  myTrivialOffset = GA_Size(value);
1283  return;
1284  }
1285  }
1286 
1287  harden();
1288  myData->set(index, value);
1289  }
1290 
1291  template<typename S>
1292  void set(const S *data, exint size, ToType offset)
1293  {
1294  clear();
1295 
1296  if (size == 0)
1297  return;
1298 
1299  // Check for triviality first
1300  ToType first = ToType(data[0]);
1301  bool istrivial = true;
1302  for (int64 i = 1; i < size; ++i)
1303  {
1304  if (ToType(data[i]) != first + ToType(i))
1305  {
1306  istrivial = false;
1307  break;
1308  }
1309  }
1310 
1311  if (istrivial)
1312  setTrivial(first+offset, FromType(size));
1313  else
1314  {
1316  ListTypeData *newdata = ListTypeData::allocate(size);
1317  UT_ASSERT_P((intptr_t(newdata) & TRIVIAL_MASK) == 0);
1318  newdata->set(data, size, offset);
1319  mySize = size;
1320  myData = newdata;
1321  }
1322  }
1323 
1324  void copyAdd(FromType destindex, const int *values, GA_Size srcindex, GA_Size n, ToType offset)
1325  {
1326  if (isTrivial())
1327  {
1328  bool ismatch = true;
1329  for (GA_Size i = 0; i < n; ++i)
1330  {
1331  if (myTrivialOffset + GA_Size(destindex) + i != values[srcindex + i] + GA_Size(offset))
1332  {
1333  ismatch = false;
1334  break;
1335  }
1336  }
1337  if (ismatch)
1338  return;
1339  }
1340  harden();
1341  myData->copyAdd(destindex, values, srcindex, n, offset);
1342  }
1343  void copyAdd(FromType destindex, const GA_ListTypeRef<FromType, ToType> &values, FromType srcindex, GA_Size n, ToType offset)
1344  {
1345  if (isTrivial())
1346  {
1347  if (values.isTrivial() && myTrivialOffset + destindex == values.myTrivialOffset + srcindex)
1348  return;
1349 
1350  bool ismatch = true;
1351  for (GA_Size i = 0; i < n; ++i)
1352  {
1353  if (myTrivialOffset + GA_Size(destindex) + i != GA_Size(values(srcindex + i)) + GA_Size(offset))
1354  {
1355  ismatch = false;
1356  break;
1357  }
1358  }
1359  if (ismatch)
1360  return;
1361  }
1362  harden();
1363  myData->copyAdd(destindex, values, srcindex, n, offset);
1364  }
1365  void setTrivialRange(FromType startindex, ToType startvalue, GA_Size nelements)
1366  {
1367  FromType endindex = startindex + nelements;
1368  if (isTrivial())
1369  {
1370  if (startindex == FromType(0) && nelements >= mySize)
1371  {
1372  myTrivialOffset = startvalue;
1373  mySize = nelements;
1374  return;
1375  }
1376  if (myTrivialOffset+GA_Size(startindex) == GA_Size(startvalue))
1377  {
1378  if (endindex > FromType(mySize))
1379  mySize = endindex;
1380  return;
1381  }
1382  }
1383  else if (startindex == FromType(0) && nelements >= mySize)
1384  {
1385  setTrivial(startvalue, nelements);
1386  return;
1387  }
1388 
1389  exint new_size = SYSmax(exint(endindex), exint(mySize));
1390  harden(new_size);
1391  mySize = new_size;
1393  for (GA_Size i = 0; i < nelements; ++i)
1394  data->set(startindex + i, startvalue + i);
1395  }
1396 
1397  /// Set all entries to a constant value
1398  void constant(ToType value);
1399 
1400  /// Cyclically shift the entire array by howMany
1401  void cycle(GA_Size howMany);
1402 
1403  /// Reverse the entire array
1404  void reverse();
1405 
1406  void harden()
1407  {
1408  if (isTrivial())
1409  {
1412  UT_ASSERT_P((intptr_t(data) & TRIVIAL_MASK) == 0);
1413  INT_TYPE *array = data->getRawData();
1414  for (exint i = 0; i < exint(mySize); i++)
1415  array[i] = ToType(myTrivialOffset+i);
1416 #if GA_OFFSETLIST_VERBOSE_DEBUG
1417  printf("%p taking ownership of new %p in harden()\n", this, data);
1418  fflush(stdout);
1419 #endif
1420  myData = data;
1421  }
1422  else if (myData->isShared())
1423  {
1424  // ensure we have a ListTypeData and that isn't referenced by
1425  // any other GA_ListType
1427 #if GA_OFFSETLIST_VERBOSE_DEBUG
1428  printf("%p removing reference to %p in harden(), and taking ownership of new %p\n", this, myData, data);
1429  fflush(stdout);
1430 #endif
1431  myData->unref();
1432 
1433  // NOTE: DO NOT set myData to NULL, even temporarily, because it
1434  // *must* be threadsafe to call isTrivial() while hardening
1435  // a non-trivial list and get false as a return value.
1436  // GA_IndexMap::compactIndices() may be called at the same
1437  // time as GA_IndexMap::isTrivial(), and isTrivial() *must*
1438  // return false, no matter what the race.
1439  myData = data;
1440  }
1441  UT_ASSERT_P(!isTrivial() && !myData->isShared());
1442  }
1443 
1444  void harden(exint mincapacity)
1445  {
1446  if (isTrivial())
1447  {
1449  ListTypeData *data = ListTypeData::allocate(mincapacity);
1450  UT_ASSERT_P((intptr_t(data) & TRIVIAL_MASK) == 0);
1451  INT_TYPE *array = data->getRawData();
1452  if (mincapacity < mySize)
1453  mySize = mincapacity;
1454  for (exint i = 0; i < exint(mySize); i++)
1455  array[i] = ToType(myTrivialOffset+i);
1456 #if GA_OFFSETLIST_VERBOSE_DEBUG
1457  printf("%p taking ownership of new %p in harden(mincapacity)\n", this, data);
1458  fflush(stdout);
1459 #endif
1460  myData = data;
1461  }
1462  else if (myData->isShared())
1463  {
1464  // ensure we have a ListTypeData and that isn't referenced by
1465  // any other GA_ListType
1466  ListTypeData *data = myData->copy(mySize, mincapacity);
1467 #if GA_OFFSETLIST_VERBOSE_DEBUG
1468  printf("%p removing reference to %p in harden(mincapacity), and taking ownership of new %p\n", this, myData, data);
1469  fflush(stdout);
1470 #endif
1471  myData->unref();
1472 
1473  // NOTE: DO NOT set myData to NULL, even temporarily, because it
1474  // *must* be threadsafe to call isTrivial() while hardening
1475  // a non-trivial list and get false as a return value.
1476  // GA_IndexMap::compactIndices() may be called at the same
1477  // time as GA_IndexMap::isTrivial(), and isTrivial() *must*
1478  // return false, no matter what the race.
1479  myData = data;
1480 
1481  if (mincapacity < mySize)
1482  mySize = mincapacity;
1483  }
1484  else if (mincapacity > myData->capacity())
1485  {
1486 #if GA_OFFSETLIST_VERBOSE_DEBUG
1487  printf("%p bumping capacity of %p, current capacity = %d in harden(mincapacity=%d)\n", this, myData, int(mincapacity), int(myData->capacity()));
1488 #endif
1489  myData = myData->bumpCapacity(mincapacity);
1490 #if GA_OFFSETLIST_VERBOSE_DEBUG
1491  printf(" now %p new capacity = %d\n", myData, int(myData->capacity()));
1492  fflush(stdout);
1493 #endif
1494  }
1495  UT_ASSERT_P(!isTrivial() && !myData->isShared());
1496  }
1497 
1498  /// WARNING: PLEASE DO NOT CALL THIS UNLESS YOU KNOW WHAT YOU'RE DOING!
1499  /// IF YOU'RE UNSURE, YOU DON'T NEED TO CALL THIS!
1500  /// Only call this if it's necessary to copy a GA_ListType and share
1501  /// its ownership in some way that doesn't correctly update the
1502  /// ref count for non-trivial lists.
1503  /// (This was added for GA_PrimitiveList to represent a GA_OffsetList
1504  /// with a UT_FixedVector<int64,2>.)
1505  void incDataRef()
1506  {
1507  if (!isTrivial())
1508  {
1509 #if GA_OFFSETLIST_VERBOSE_DEBUG
1510  printf("%p adding reference to %p in incDataRef()\n", this, myData);
1511  fflush(stdout);
1512 #endif
1513  myData->ref();
1514  }
1515  }
1516 };
1517 
1518 
1519 // A list of offsets. The index type is still specified as a template
1520 // parameter.
1521 template <typename FromType, typename INT_TYPE=exint>
1522 class GA_API GA_OffsetListType : public GA_ListType<FromType, GA_Offset, INT_TYPE>
1523 {
1524 private:
1525  // Shorthand for the base class
1527  using Base::myData;
1528  using Base::myIsFlagSet;
1529  using Base::myIsTrivial;
1530  using Base::myTrivialOffset;
1531  using Base::mySize;
1532 public:
1533  using Base::clear;
1534  using Base::get;
1535  using Base::isTrivial;
1536  using Base::set;
1537  using Base::size;
1538  using typename Base::theIntType;
1539 
1540  // Default c-tor
1541  explicit GA_OffsetListType() : Base() {}
1542  // Copy c-tor
1544  : Base(src) {}
1546  : Base(src) {}
1547  // A GA_OffsetArray is a UT_Array of offsets. The UT_Array doesn't have
1548  // paged storage, nor COW semantics, it's just a flat list of offsets.
1549  // This will construct a GA_OffsetListType by copying a portion of the array.
1550  GA_OffsetListType(const UT_ValArray<GA_Offset> &src, FromType start=FromType(0), FromType end=FromType(-1))
1551  : Base(src, start, end) {}
1552 
1553  /// Copy assignment operator
1555  GA_OffsetListType &operator=(const GA_OffsetListType &src) = default;
1556 
1557  /// Move assignment operator
1559  GA_OffsetListType &operator=(GA_OffsetListType &&src) = default;
1560 
1561  /// Copy assignment operator from GA_ListTypeRef.
1562  /// Although it may seem strange to have this at all, it should be
1563  /// safe, since the destination does take (shared) ownership of any
1564  /// non-trivial data. There should be a GA_OffsetListType somewhere else
1565  /// that already owns this.
1568  {
1569  Base::operator=(src);
1570  return *this;
1571  }
1572 
1573  /// @{
1574  /// Swap offset values for defragmentation process. When defragmenting,
1575  /// offsets will move. This method will update all references to offsets
1576  /// to their new values. This returns the number of values updated.
1577  GA_Size swapOffsetValues(const GA_Defragment &defrag);
1578  /// @}
1579 
1580  /// @section JSON-GA_OffsetList JSON Schema: GA_OffsetList
1581  /// @code
1582  /// {
1583  /// "name" : "GA_OffsetList",
1584  /// "description" : "An array of offsets/indicies",
1585  /// "type" : "array",
1586  /// "items" : "integer",
1587  /// }
1588  /// @endcode
1589  /// @see @ref JSON_FileFormat
1590 
1591  /// Save the offsets by doing the mapping to the points in the save map
1592  bool jsonPointArray(UT_JSONWriter &w, const GA_SaveMap &save) const;
1593  /// Save the offsets by doing the mapping to the vertices in the save map
1594  bool jsonVertexArray(UT_JSONWriter &w, const GA_SaveMap &save) const;
1595  /// Save the offsets by doing the mapping to the primitives in the save map
1596  bool jsonPrimitiveArray(UT_JSONWriter &w, const GA_SaveMap &save) const;
1597 
1598  /// Load a point list from a JSON stream
1599  bool jsonPointArray(UT_JSONParser &p, const GA_LoadMap &load);
1600  /// Load a vertex list from a JSON stream
1601  bool jsonVertexArray(UT_JSONParser &p, const GA_LoadMap &load);
1602  /// Load a primitive list from a JSON stream
1603  bool jsonPrimitiveArray(UT_JSONParser &p, const GA_LoadMap &load);
1604 
1605  /// Generic load given a load offset
1606  bool jsonLoad(UT_JSONParser &p, GA_Offset load_offset);
1607  /// Load, appending to the current offset list without initial clear
1608  bool jsonLoadAppend(UT_JSONParser &p, GA_Offset load_offset);
1609  /// Generic load from a JSON stream saved by index that maps the ordered
1610  /// index to an offset.
1611  bool jsonLoadByIndex(UT_JSONParser &p, const GA_IndexMap &index_map,
1612  GA_Index load_offset);
1613  /// Load from a JSON stream saved by index, mapping the ordered index to
1614  /// an offset and appending to the current offset list without an initial
1615  /// clear.
1616  bool jsonLoadAppendByIndex(UT_JSONParser &p,
1617  const GA_IndexMap &index_map,
1618  GA_Index load_offset);
1619 
1620 private:
1621  bool jsonSaveTranslatedArray(
1622  UT_JSONWriter &w,
1623  const GA_SaveMap &save,
1624  GA_AttributeOwner xlate) const;
1625 };
1626 
1627 /// GA_OffsetList is a map from index to offset
1629 
1630 /// GA_OffsetListRef is like GA_OffsetList, except that it doesn't own
1631 /// its data. It's useful for making a temporary copy of a GA_OffsetList
1632 /// that isn't going to be changing during the lifetime of the copy,
1633 /// to avoid having to ref and unref myData, among a few related speedups.
1635 
1636 #endif
1637 
SYS_FORCE_INLINE void clear()
clear removes all of the entries
const_iterator begin() const
A class to manage an ordered array which has fixed offset handles.
Definition: GA_IndexMap.h:63
SYS_FORCE_INLINE INT_TYPE * getArray()
ListTypeData * myData
SYS_FORCE_INLINE GA_ListType()
Default constructor.
#define SYSmax(a, b)
Definition: SYS_Math.h:1367
GLint first
Definition: glcorearb.h:404
FromType multipleInsert(FromType i, GA_Size count)
reference operator*() const
void reverse()
Reverse the entire array.
SYS_FORCE_INLINE GA_ListType(const GA_ListType &src)
Copy constructor.
void harden(exint mincapacity)
base_iterator operator++(int)
const_iterator end() const
void copyAdd(FromType destindex, const GA_ListTypeRef< FromType, ToType, S > &values, FromType srcindex, GA_Size n, ToType offset)
SYS_FORCE_INLINE GA_ListType(ToType startvalue, GA_Size size, bool flag_set=false)
Trivial list constructor.
FromType append(ToType value)
Add a single entry (may grow array)
Used to pass options and map offset values during saving.
Definition: GA_SaveMap.h:48
FromType findInRange(FromType start, FromType end, ToType search) const
SYS_FORCE_INLINE ToType operator[](FromType i) const
bool operator!=(const base_iterator< LT > &r) const
SYS_FORCE_INLINE void set(FromType index, ToType value)
void copyAdd(FromType destindex, const int *values, GA_Size srcindex, GA_Size n, ToType offset)
SYS_FORCE_INLINE void setTrivial(ToType startvalue, GA_Size size)
Makes the list a trivial list with the specified start value and size.
iterator begin()
GA_OffsetListType(const GA_OffsetListType &src)
void sortAndRemoveDuplicates()
Sort entries into ascending order and remove duplicates.
const GLdouble * v
Definition: glcorearb.h:836
GA_OffsetListType< GA_Size > GA_OffsetList
GA_OffsetList is a map from index to offset.
GLuint start
Definition: glcorearb.h:474
bool GAisValid(GA_Size v)
Definition: GA_Types.h:625
FromType findInRangeNotEqual(FromType start, FromType end, ToType search) const
SYS_FORCE_INLINE int64 getMemoryUsage(bool inclusive) const
base_iterator & operator--()
void constant(ToType value)
Set all entries to a constant value.
base_iterator & operator+=(FromType n)
ListTypeData * reallocate(exint new_capacity)
Definition: GA_OffsetList.h:86
void copyAdd(FromType destindex, const GA_ListTypeRef< FromType, ToType > &values, FromType srcindex, GA_Size n, ToType offset)
SYS_FORCE_INLINE bool getExtraFlag() const
void reserve(FromType mincapacity)
#define CMP_OP(OP)
void setTrivial(ToType startvalue, GA_Size size)
Makes the list a trivial list with the specified start value and size.
FromType findInRangeNotEqual(FromType start, FromType end, ToType search) const
void setTrivialRange(FromType startindex, ToType startvalue, GA_Size nelements)
void reverse(FromType size)
base_iterator operator-(FromType n) const
JSON reader class which handles parsing of JSON or bJSON files.
Definition: UT_JSONParser.h:75
base_iterator< const this_type > const_iterator
#define GA_API
Definition: GA_API.h:12
base_iterator< this_type > iterator
INT_TYPE theIntType
Definition: GA_OffsetList.h:57
Class which writes ASCII or binary JSON streams.
Definition: UT_JSONWriter.h:32
FromType findInvalidInRange(FromType start, FromType end) const
typename Base::ListTypeData ListTypeData
GA_ListTypeRef< GA_Size, GA_Offset > GA_OffsetListRef
SYS_FORCE_INLINE GA_ListType & operator=(const Base &src)
FromType findValidInRange(FromType start, FromType end) const
void unsafeClearData()
Definition: UT_Array.h:864
png_uint_32 i
Definition: png.h:2877
SYS_FORCE_INLINE GA_ListType & operator=(const GA_ListType &src)
Copy assignment operator.
SYS_FORCE_INLINE void forEach(FUNCTOR &&functor) const
exint GA_Size
Defines the bit width for index and offset types in GA.
Definition: GA_Types.h:211
SYS_FORCE_INLINE GA_ListTypeRef()
Default constructor.
GLsizeiptr size
Definition: glcorearb.h:663
bool operator==(const base_iterator< LT > &r) const
SYS_FORCE_INLINE int64 getMemoryUsage(bool inclusive) const
Report memory usage (includes all shared memory)
FromType operator-(const base_iterator< LT > &r) const
void set(FromType index, ToType value)
Set the index to the value.
GA_Size GA_Offset
Definition: GA_Types.h:617
GA_OffsetListType(const GA_ListTypeRef< FromType, GA_Offset, INT_TYPE > &src)
SYS_FORCE_INLINE INT_TYPE * getRawData()
long long int64
Definition: SYS_Types.h:107
SYS_FORCE_INLINE bool isTrivial() const
GLdouble n
Definition: glcorearb.h:2007
ListTypeData * setCapacity(exint new_capacity)
unsigned long long uint64
Definition: SYS_Types.h:108
void removeLast()
Remove the last entry.
void computeTrivial()
SYS_FORCE_INLINE INT_TYPE & operator()(exint index)
SYS_FORCE_INLINE GA_ListType(const Base &src)
bool isAscending(exint size) const
FromType findAndRemove(ToType i)
Find an entry and remove it from the list.
base_iterator(const base_iterator< EIT > &src)
int64 exint
Definition: SYS_Types.h:116
void cycle(GA_Size howMany)
Cyclically shift the entire array by howMany.
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:125
base_iterator & operator++()
iterator end()
FromType findValidInRange(FromType start, FromType end) const
GLuint GLuint end
Definition: glcorearb.h:474
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
SYS_FORCE_INLINE GA_ListType & operator=(GA_ListType &&src)
Move assignment operator.
void countMemory(UT_MemoryCounter &counter, bool inclusive) const
static const intptr_t POINTER_MASK
ListTypeData * copy(exint size, exint new_capacity) const
SYS_FORCE_INLINE GA_ListTypeRef(ToType startvalue, GA_Size size, bool flag_set=false)
Trivial list constructor.
GLintptr offset
Definition: glcorearb.h:664
SYS_FORCE_INLINE const INT_TYPE & operator()(exint index) const
friend class GA_ListType
Definition: GA_OffsetList.h:55
void changeSize(FromType new_capacity)
Options during loading.
Definition: GA_LoadMap.h:42
GLenum GLsizei GLsizei GLint * values
Definition: glcorearb.h:1601
Defragmentation of IndexMaps.
Definition: GA_Defragment.h:45
GA_Size removeAll(ToType v, FromType size)
GLboolean * data
Definition: glcorearb.h:130
FromType findAndRemove(ToType v, FromType size)
SYS_FORCE_INLINE const INT_TYPE * getRawData() const
GA_Size GA_Index
Define the strictness of GA_Offset/GA_Index.
Definition: GA_Types.h:611
void unsafeShareData(UT_Array< T > &src)
Definition: UT_Array.h:846
base_iterator(LIST_T *list, FromType c)
void cycle(exint howMany)
Cyclically shifts the entire array by howMany.
Definition: UT_ArrayImpl.h:646
SYS_FORCE_INLINE ToType operator()(FromType i) const
Convenience () operator to access the list entries.
GLint GLsizei count
Definition: glcorearb.h:404
bool isSame(const GA_ListTypeRef &that) const
ToType last() const
Return the value of the last element.
GA_Size removeAll(ToType i)
Remove all matching entries from the list.
SYS_FORCE_INLINE GA_Size capacity() const
Returns the allocated capacity of the list.
void sortAscending(FromType size)
GLsizei const GLfloat * value
Definition: glcorearb.h:823
GA_AttributeOwner
Definition: GA_Types.h:33
SYS_FORCE_INLINE GA_ListType(GA_ListType &&src)
Move constructor.
base_iterator operator+(FromType n) const
#define UT_ASSERT_MSG(ZZ, MM)
Definition: UT_Assert.h:129
typedef int
Definition: png.h:1175
FromType insert(FromType i, ToType value)
Insert a single entry (may grow array)
base_iterator operator--(int)
static const intptr_t TRIVIAL_MASK
SYS_FORCE_INLINE void setExtraFlag(bool v)
void setTrivial(ToType startvalue, GA_Size size, bool flag)
SYS_FORCE_INLINE void setTrivial(ToType startvalue, GA_Size size, bool flag)
GLuint index
Definition: glcorearb.h:785
reference operator[](FromType n) const
void setEntries(FromType sz, bool doresize=true)
SYS_FORCE_INLINE GA_Size capacity() const
void set(const S *data, exint size, ToType offset)
FromType findInvalidInRange(FromType start, FromType end) const
FromType findInRange(FromType start, FromType end, ToType search) const
SYS_FORCE_INLINE ToType get(FromType index) const
Get the the value at the index.
FromType sortAndRemoveDuplicates(FromType size)
FromType find(ToType v, FromType s, FromType size) const
GA_OffsetListType(const UT_ValArray< GA_Offset > &src, FromType start=FromType(0), FromType end=FromType(-1))
GLubyte GLubyte GLubyte GLubyte w
Definition: glcorearb.h:856
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:126
void cycle(GA_Size howMany, FromType size)
GLboolean r
Definition: glcorearb.h:1221
SYS_FORCE_INLINE GA_OffsetListType & operator=(const GA_ListTypeRef< FromType, GA_Offset, INT_TYPE > &src)
SYS_FORCE_INLINE ToType trivialStart() const
Returns the start, assuming this list is trivial.
#define FLAG_MASK
SYS_FORCE_INLINE void relaxedStore(T val)
Definition: SYS_AtomicInt.h:67
SYS_FORCE_INLINE ~GA_ListType()
Destructor.
png_infop png_uint_32 flag
Definition: png.h:2242
FromType removeIndex(FromType i)
Alias for remove to match UT array types.
void constant(ToType value, FromType size)
UT_ASSERT_COMPILETIME(BRAY_EVENT_MAXFLAGS<=32)
#define SYSmin(a, b)
Definition: SYS_Math.h:1368
void sortAscending()
Sort entries into ascending order.
void copyAdd(FromType destindex, const S *values, GA_Size srcindex, GA_Size n, ToType offset)
void set(const S *data, exint size, ToType offset)
SYS_FORCE_INLINE void clear()
clear removes all of the entries
static ListTypeData * allocate(exint capacity)
Definition: GA_OffsetList.h:66
SYS_FORCE_INLINE GA_ListTypeRef & operator=(const GA_ListTypeRef &src)=default
Copy assignment operator.
void incDataRef()
bool isTrivial(exint size) const
SYS_FORCE_INLINE FromType size() const
Returns the number of used elements in the list (always <= capacity())
#define UT_ASSERT_MSG_P(ZZ, MM)
Definition: UT_Assert.h:128
SYS_FORCE_INLINE const INT_TYPE * getArray() const
GLenum src
Definition: glcorearb.h:1792
base_iterator & operator-=(FromType n)
SYS_FORCE_INLINE FromType entries() const
Returns the number of used elements in the list (always <= capacity())
ListTypeData * bumpCapacity(exint mincapacity)