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.
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; }
629 
630  /// Synonym for isClosed()
632  bool getExtraFlag() const { return myIsFlagSet != 0; }
633  /// Synonym for getExtraFlag()
635  bool isClosed() const { return myIsFlagSet != 0; }
636  /// Synonym for setClosed(bool)
638  void setExtraFlag(bool v) { myIsFlagSet = v; }
639  /// Synonym for setExtraFlag(bool)
641  void setClosed(bool v) { myIsFlagSet = v; }
642 
643  /// Returns true iff this and that are either both trivial and equal
644  /// or if both are not trivial and share the same ListTypeData pointer.
645  /// This does not fully check for equality!
646  bool isSame(const GA_ListTypeRef &that) const
647  {
648  if (isTrivial())
649  {
650  return (that.isTrivial() &&
651  (mySize == that.mySize) &&
652  (myTrivialOffset == that.myTrivialOffset));
653  }
654  return (myData == that.myData);
655  }
656 
657  /// Identifies whether the data is in ascending order
658  bool isAscending() const;
659 
660  /// Linearly search for the specified entry. Returns the index of first
661  /// matching element found, -1 otherwise. An optional starting index can
662  /// be specified in s.
663  FromType find(ToType value, FromType s = FromType(0)) const;
664 
665  /// Find the target in a sorted list.
666  FromType findSorted(ToType value, FromType s=FromType(0)) const;
667 
668  /// Get the the value at the index
670  ToType get(FromType index) const
671  {
672  UT_ASSERT_P(index >= FromType(0) && index < size());
673  return isTrivial()
674  ? ToType(GA_Size(index)+myTrivialOffset)
675  : myData->get(index);
676  }
677 
678  /// Returns the start, assuming this list is trivial.
680  ToType trivialStart() const
681  {
682  UT_ASSERT_P(isTrivial());
683  return ToType(myTrivialOffset);
684  }
685 
686  /// Test a sub-block for equality with another list
687  bool isEqual(const GA_ListTypeRef &other,
688  FromType start, FromType end) const;
689 
690  /// Return the value of the last element
691  ToType last() const
692  {
693  exint last_index = mySize-1;
694  return isTrivial()
695  ? ToType(myTrivialOffset+last_index)
696  : myData->get(FromType(last_index));
697  }
698 
699  /// Convenience () operator to access the list entries
701  ToType operator()(FromType i) const { return get(i); }
702 
704  ToType operator[](FromType i) const { return get(i); }
705 
706  /// Finds the first instance of the search pattern in the given
707  /// range. Returns end if not found.
708  FromType findInRange(FromType start, FromType end, ToType search) const
709  {
710  if (isTrivial())
711  {
712  FromType matchingindex = FromType(GA_Size(search) - GA_Size(myTrivialOffset));
713  if (matchingindex >= start && matchingindex < end)
714  return matchingindex;
715  // No match.
716  return end;
717  }
718  return myData->findInRange(start, end, search);
719  }
720  FromType findInRangeNotEqual(FromType start, FromType end, ToType search) const
721  {
722  if (isTrivial())
723  {
724  FromType matchingindex = FromType(GA_Size(search) - GA_Size(myTrivialOffset));
725  // start is always a match. If not, start+1 is.
726  if (matchingindex != start)
727  return start;
728  start += 1;
729  if (start > end)
730  return end;
731  return start;
732  }
733  return myData->findInRangeNotEqual(start, end, search);
734  }
735  FromType findValidInRange(FromType start, FromType end) const
736  {
737  if (isTrivial())
738  {
739  // NOTE: We can have trivial lists with negative offsets!
740  // If we have a valid trivial offset, everything matches.
741  if (GAisValid(myTrivialOffset))
742  return start;
743  if (GAisValid(ToType(GA_Size(start)) + ToType(myTrivialOffset)))
744  return start;
745  return SYSmin(end, FromType(-GA_Size(myTrivialOffset)));
746  }
747  return myData->findValidInRange(start, end);
748  }
749  FromType findInvalidInRange(FromType start, FromType end) const
750  {
751  if (isTrivial())
752  {
753  // NOTE: We can have trivial lists with negative offsets!
754  // If we have a valid trivial offset or start, nothing matches.
755  if (GAisValid(myTrivialOffset))
756  return end;
757  if (GAisValid(ToType(GA_Size(start)) + ToType(myTrivialOffset)))
758  return end;
759  return start;
760  }
761  return myData->findInvalidInRange(start, end);
762  }
763 
764  /// Calls a functor (e.g. a lambda) for each entry, only checking
765  /// for triviality once, to reduce overhead.
766  template<typename FUNCTOR>
768  void forEach(FUNCTOR &&functor) const
769  {
770  if (myIsTrivial)
771  {
772  ToType value(myTrivialOffset);
773  const ToType end(value + mySize);
774  for (; value != end; ++value)
775  {
776  functor(value);
777  }
778  }
779  else
780  {
781  const INT_TYPE *data = myData->getRawData();
782  const INT_TYPE *const end = data + mySize;
783  for (; data != end; ++data)
784  {
785  functor(ToType(*data));
786  }
787  }
788  }
789 
790  /// @note It's likely more efficient to use @c forEach() than iterators
791  template <typename LIST_T>
793  public std::iterator<std::random_access_iterator_tag,
794  ToType, FromType>
795  {
796  public:
797  using reference = ToType;
798 
800  : myList(nullptr)
801  , myCurrent(-1)
802  {
803  }
804 
805  template <typename EIT>
807  : myList(src.myList)
808  , myCurrent(src.myCurrent)
809  {
810  }
812  {
813  return myList->get(myCurrent);
814  }
815  reference item() const
816  {
817  return myList->get(myCurrent);
818  }
819  reference operator[](FromType n) const
820  {
821  return myList->get(myCurrent+n);
822  }
824  {
825  ++myCurrent;
826  return *this;
827  }
829  {
830  base_iterator tmp = *this;
831  ++myCurrent;
832  return tmp;
833  }
835  {
836  --myCurrent;
837  return *this;
838  }
840  {
841  base_iterator tmp = *this;
842  --myCurrent;
843  return tmp;
844  }
846  {
847  myCurrent += n;
848  return *this;
849  }
850  base_iterator operator+(FromType n) const
851  {
852  return base_iterator(myList, myCurrent+n);
853  }
855  { return (*this) += (-n); }
856  base_iterator operator-(FromType n) const
857  { return (*this) + (-n); }
858  template <typename LT>
859  bool operator==(const base_iterator<LT> &r) const
860  { return r.myCurrent == myCurrent; }
861  template <typename LT>
862  bool operator!=(const base_iterator<LT> &r) const
863  { return r.myCurrent != myCurrent; }
864 
865  #define CMP_OP(OP) \
866  template <typename LT> \
867  bool operator OP(const base_iterator<LT> &r) const { \
868  return myCurrent OP r.myCurrent; \
869  }
870  CMP_OP(<)
871  CMP_OP(>)
872  CMP_OP(<=)
873  CMP_OP(>=)
874  #undef CMP_OP
875  template <typename LT>
876  FromType operator-(const base_iterator<LT> &r) const
877  { return (myCurrent - r.myCurrent); }
878  protected:
879  friend class GA_ListTypeRef<FromType, ToType, INT_TYPE>;
880  base_iterator(LIST_T *list, FromType c)
881  : myList(list)
882  , myCurrent(c)
883  {
884  }
885  private:
886  LIST_T *myList;
887  FromType myCurrent;
888  };
889  using iterator = base_iterator<this_type>;
890  using const_iterator = base_iterator<const this_type>;
891 
892  /// @{
893  /// @note It's likely more efficient to use @c forEach() than iterators
894  iterator begin() { return iterator(this, FromType(0)); }
895  iterator end() { return iterator(this, size()); }
896  const_iterator begin() const { return const_iterator(this, FromType(0)); }
897  const_iterator end() const { return const_iterator(this, size()); }
898  /// @}
899 
900  /// Report memory usage (includes all shared memory)
902  int64 getMemoryUsage(bool inclusive) const
903  {
904  return (inclusive ? sizeof(*this) : 0) + (!isTrivial() ? myData->getMemoryUsage(true) : 0);
905  }
906 
908  const INT_TYPE *getArray() const
909  {
910  return !isTrivial() ? myData->getRawData() : nullptr;
911  }
913  INT_TYPE *getArray()
914  {
915  return !isTrivial() ? myData->getRawData() : nullptr;
916  }
917 
918 protected:
919  static const intptr_t POINTER_MASK = ~0x1;
920  static const intptr_t TRIVIAL_MASK = 0x1;
921  static const intptr_t FLAG_MASK = 0x1;
922 #ifndef SESI_LITTLE_ENDIAN
923 #error "Make sure the bitfields in the union work on big endian platforms!"
924 #endif
925  union {
926  ListTypeData *myData;
927  struct {
928  // NOTE: myTrivialOffset must be signed to support
929  // GA_INVALID_OFFSET and GA_INVALID_INDEX, but
930  // mySize can be unsigned.
931  int64 myIsTrivial:1;
932  int64 myTrivialOffset:63;
933  // Make sure that this flag doesn't overlap with the
934  // pointer, so that it doesn't need to be considered
935  // when reading/writing myData. myIsTrivial
936  // can overlap with myData, because it's
937  // mutually exclusive with using myData.
938  uint64 myIsFlagSet:1;
939  uint64 mySize:63;
940  };
941  };
942 };
943 
944 template <typename FromType, typename ToType, typename INT_TYPE=exint>
945 class GA_API GA_ListType : public GA_ListTypeRef<FromType, ToType, INT_TYPE>
946 {
947 private:
948  // These friend declarations are needed for accessing data in related types.
949  template<typename FromType2,typename ToType2,typename INT_TYPE2>
950  friend class GA_ListTypeRef;
951  template<typename FromType2,typename ToType2,typename INT_TYPE2>
952  friend class GA_ListType;
953 
955 protected:
956  using Base::myData;
957  using Base::myIsTrivial;
958  using Base::myTrivialOffset;
959  using Base::myIsFlagSet;
960  using Base::mySize;
961  using Base::POINTER_MASK;
962  using Base::TRIVIAL_MASK;
963  using Base::FLAG_MASK;
964  // I don't know why one build machine running GCC 4.8 needed
965  // "ListTypeData =" and the other didn't, but I've put it here
966  // anyway, because it should keep everyone happy.
967  using ListTypeData = typename Base::ListTypeData;
968 public:
969  using Base::get;
970  using Base::isTrivial;
971  using Base::size;
972  using Base::capacity;
973  using typename Base::theIntType;
974 public:
975  /// Default constructor
977  explicit GA_ListType()
978  : Base()
979  {
980  myIsTrivial = true;
981  myTrivialOffset = 0;
982  myIsFlagSet = false;
983  mySize = 0;
984  }
985 
986  /// Copy constructor
989  : Base()
990  {
991  if (!src.isTrivial())
992  {
993 #if GA_OFFSETLIST_VERBOSE_DEBUG
994  printf("%p adding reference to %p (orig reference by list %p) in copy constructor\n", this, src.myData, &src);
995  fflush(stdout);
996 #endif
997  src.myData->ref();
998  }
999  // NOTE: I'm assuming that it's expected that myIsFlagSet will be copied.
1000  Base::operator=(src);
1001  }
1002 
1003  /// Move constructor
1006  : Base()
1007  {
1008 #if GA_OFFSETLIST_VERBOSE_DEBUG
1009  if (!src.isTrivial())
1010  {
1011  printf("%p stealing reference to %p (orig reference by list %p) in move constructor\n", this, src.myData, &src);
1012  fflush(stdout);
1013  }
1014 #endif
1015  Base::operator=(src);
1016  src.myIsTrivial = true;
1017  }
1018 
1019  /// Copy constructor from GA_ListTypeRef.
1020  /// Although it may seem strange to have this at all, it should be
1021  /// safe, since the destination does take (shared) ownership of any
1022  /// non-trivial data. There should be a GA_ListType somewhere else
1023  /// that already owns this.
1025  explicit GA_ListType(const Base &src)
1026  : Base()
1027  {
1028  if (!src.isTrivial())
1029  {
1030 #if GA_OFFSETLIST_VERBOSE_DEBUG
1031  printf("%p adding reference to %p (orig reference by listref %p) in list(listref) type conversion constructor\n", this, src.myData, &src);
1032  fflush(stdout);
1033 #endif
1034  src.myData->ref();
1035  UT_ASSERT_MSG_P(src.myData->isShared(), "Something should have already owned this data.");
1036  }
1037  // NOTE: I'm assuming that it's expected that myIsFlagSet will be copied.
1038  Base::operator=(src);
1039  }
1040 
1041  /// Trivial list constructor
1043  GA_ListType(ToType startvalue, GA_Size size, bool flag_set=false)
1044  : Base(startvalue, size, flag_set)
1045  {}
1046 
1047  // This will construct a GA_ListType by copying a portion of the array.
1048  GA_ListType(const UT_Array<ToType> &src, FromType start=FromType(0), FromType end=FromType(-1));
1049 
1050  /// Destructor
1053  {
1054  if (!isTrivial())
1055  {
1056 #if GA_OFFSETLIST_VERBOSE_DEBUG
1057  printf("%p removing reference to %p in desctructor\n", this, myData);
1058  fflush(stdout);
1059 #endif
1060  myData->unref();
1061  }
1062  }
1063 
1064  /// Copy assignment operator
1067  {
1068  if (!isTrivial())
1069  {
1070 #if GA_OFFSETLIST_VERBOSE_DEBUG
1071  printf("%p removing reference to %p in copy assignment operator\n", this, myData);
1072  fflush(stdout);
1073 #endif
1074  myData->unref();
1075  }
1076  if (!src.isTrivial())
1077  {
1078 #if GA_OFFSETLIST_VERBOSE_DEBUG
1079  printf("%p adding reference to %p (orig reference by list %p) in copy assignment operator\n", this, src.myData, &src);
1080  fflush(stdout);
1081 #endif
1082  src.myData->ref();
1083  }
1084  // NOTE: I'm assuming that it's expected that myIsFlagSet will be copied.
1085  Base::operator=(src);
1086  return *this;
1087  }
1088 
1089  /// Move assignment operator
1092  {
1093  if (!isTrivial())
1094  {
1095 #if GA_OFFSETLIST_VERBOSE_DEBUG
1096  printf("%p removing reference to %p in move assignment operator\n", this, myData);
1097  fflush(stdout);
1098 #endif
1099  myData->unref();
1100  }
1101 #if GA_OFFSETLIST_VERBOSE_DEBUG
1102  if (!src.isTrivial())
1103  {
1104  printf("%p stealing reference to %p (orig reference by list %p) in move assignment operator\n", this, src.myData, &src);
1105  fflush(stdout);
1106  }
1107 #endif
1108  // NOTE: I'm assuming that it's expected that myIsFlagSet will be copied.
1109  Base::operator=(src);
1110  src.myIsTrivial = true;
1111  return *this;
1112  }
1113 
1114  /// Copy assignment operator from GA_ListTypeRef.
1115  /// Although it may seem strange to have this at all, it should be
1116  /// safe, since the destination does take (shared) ownership of any
1117  /// non-trivial data. There should be a GA_ListType somewhere else
1118  /// that already owns this.
1121  {
1122  if (!isTrivial())
1123  {
1124 #if GA_OFFSETLIST_VERBOSE_DEBUG
1125  printf("%p removing reference to %p in copy-from-listref assignment operator\n", this, myData);
1126  fflush(stdout);
1127 #endif
1128  myData->unref();
1129  }
1130  if (!src.isTrivial())
1131  {
1132 #if GA_OFFSETLIST_VERBOSE_DEBUG
1133  printf("%p adding reference to %p (orig reference by listref %p) in copy-from-listref assignment operator\n", this, src.myData, &src);
1134  fflush(stdout);
1135 #endif
1136  src.myData->ref();
1137  UT_ASSERT_MSG_P(src.myData->isShared(), "Something should have already owned this data.");
1138  }
1139  // NOTE: I'm assuming that it's expected that myIsFlagSet will be copied.
1140  Base::operator=(src);
1141  return *this;
1142  }
1143 
1144  /// Count memory usage using a UT_MemoryCounter in order to count
1145  /// shared memory correctly.
1146  /// If inclusive is true, the size of this object is counted,
1147  /// else only memory owned by this object is counted.
1148  /// If this is pointed to by the calling object, inclusive should be true.
1149  /// If this is contained in the calling object, inclusive should be false.
1150  /// (Its memory was already counted in the size of the calling object.)
1151  void countMemory(UT_MemoryCounter &counter, bool inclusive) const;
1152 
1153  /// clear removes all of the entries
1155  void clear()
1156  {
1157  if (!isTrivial())
1158  {
1159 #if GA_OFFSETLIST_VERBOSE_DEBUG
1160  printf("%p removing reference to %p in clear function\n", this, myData);
1161  fflush(stdout);
1162 #endif
1163  myData->unref();
1164  }
1165  myIsTrivial = true;
1166  // NOTE: DON'T set myIsFlagSet, since it's independent of whether
1167  // this list is clear.
1168  myTrivialOffset = 0;
1169  mySize = 0;
1170  }
1171 
1172  /// Identifies whether the data is a trivial mapping and if so,
1173  /// eliminates storage for the map.
1174  void computeTrivial();
1175 
1176  /// Makes the list a trivial list with the specified start value and size
1177  void setTrivial(ToType startvalue, GA_Size size)
1178  {
1179  UT_ASSERT(size >= 0);
1180  if (!isTrivial())
1181  {
1182 #if GA_OFFSETLIST_VERBOSE_DEBUG
1183  printf("%p removing reference to %p in setTrivial(start,size)\n", this, myData);
1184  fflush(stdout);
1185 #endif
1186  myData->unref();
1187  myIsTrivial = true;
1188  }
1189  myTrivialOffset = startvalue;
1190  mySize = size;
1191  }
1192 
1193  /// Makes the list a trivial list with the specified start value and size,
1194  /// and also sets the extra flag.
1195  void setTrivial(ToType startvalue, GA_Size size, bool flag)
1196  {
1197  UT_ASSERT(size >= 0);
1198  if (!isTrivial())
1199  {
1200 #if GA_OFFSETLIST_VERBOSE_DEBUG
1201  printf("%p removing reference to %p in setTrivial(start,size,flag)\n", this, myData);
1202  fflush(stdout);
1203 #endif
1204  myData->unref();
1205  myIsTrivial = true;
1206  }
1207  myTrivialOffset = startvalue;
1208  mySize = size;
1209  myIsFlagSet = flag;
1210  }
1211 
1212  /// Set the number of entries - if the number is smaller than the current
1213  /// entries, the capacity may be decreased. If doresize is false,
1214  /// only the number of entries is changed, not the size.
1215  void setEntries(FromType sz, bool doresize=true);
1216  /// Reserve capacity for a number of entries (prevents reallocation as
1217  /// elements are appended).
1218  /// This does nothing if the list is currently trivial.
1219  void reserve(FromType mincapacity); // Reserve capacity
1220 
1221  /// If trivial, this sets the size to the minimum of the current size and new_capacity.
1222  /// If not trivial, this sets the capacity to new_capacity, (also correctly decreasing
1223  /// the size if currently greater than new_capacity.)
1224  void changeSize(FromType new_capacity);
1225 
1226  /// Add a single entry (may grow array)
1227  FromType append(ToType value)
1228  {
1229  if (isTrivial())
1230  {
1231  if (!mySize)
1232  {
1234  mySize = 1;
1235  return FromType(0);
1236  }
1237  if (value == ToType(myTrivialOffset) + mySize)
1238  {
1239  ++mySize;
1240  return FromType(mySize-1);
1241  }
1242  }
1243  harden(mySize+1);
1244  myData->set(FromType(mySize), value);
1245  ++mySize;
1246  return FromType(mySize-1);
1247  }
1248 
1249  /// Append all the entries from the source list. The offset will be added
1250  /// to each value in the source list.
1252 
1253  /// Insert a single entry (may grow array)
1254  FromType insert(FromType i, ToType value);
1255 
1256  /// Insert count entries at the given index (may grow array). The new
1257  /// entries will be uninitialized.
1258  FromType multipleInsert(FromType i, GA_Size count);
1259 
1260  /// Remove the entry at the given offset
1261  FromType remove(FromType i);
1262  /// Find an entry and remove it from the list
1263  FromType findAndRemove(ToType i);
1264  /// Alias for remove to match UT array types
1265  FromType removeIndex(FromType i) { return remove(i); }
1266  /// Remove all matching entries from the list
1267  GA_Size removeAll(ToType i);
1268  /// Remove the last entry
1269  void removeLast()
1270  {
1271  UT_ASSERT_P(mySize > 0);
1272  --mySize;
1273  }
1274 
1275  /// Sort entries into ascending order
1276  void sortAscending();
1277 
1278  /// Sort entries into ascending order and remove duplicates
1279  void sortAndRemoveDuplicates();
1280 
1281  /// Set the index to the value
1282  void set(FromType index, ToType value)
1283  {
1284  UT_ASSERT_P(index >= FromType(0) && index < FromType(mySize));
1285  if (isTrivial())
1286  {
1287  if (myTrivialOffset+GA_Size(index) == GA_Size(value))
1288  return;
1289  if (mySize==1)
1290  {
1291  myTrivialOffset = GA_Size(value);
1292  return;
1293  }
1294  }
1295 
1296  harden();
1297  myData->set(index, value);
1298  }
1299 
1300  template<typename S>
1301  void set(const S *data, exint size, ToType offset)
1302  {
1303  clear();
1304 
1305  if (size == 0)
1306  return;
1307 
1308  // Check for triviality first
1309  ToType first = ToType(data[0]);
1310  bool istrivial = true;
1311  for (int64 i = 1; i < size; ++i)
1312  {
1313  if (ToType(data[i]) != first + ToType(i))
1314  {
1315  istrivial = false;
1316  break;
1317  }
1318  }
1319 
1320  if (istrivial)
1321  setTrivial(first+offset, FromType(size));
1322  else
1323  {
1325  ListTypeData *newdata = ListTypeData::allocate(size);
1326  UT_ASSERT_P((intptr_t(newdata) & TRIVIAL_MASK) == 0);
1327  newdata->set(data, size, offset);
1328  mySize = size;
1329  myData = newdata;
1330  }
1331  }
1332 
1333  void copyAdd(FromType destindex, const int *values, GA_Size srcindex, GA_Size n, ToType offset)
1334  {
1335  if (isTrivial())
1336  {
1337  bool ismatch = true;
1338  for (GA_Size i = 0; i < n; ++i)
1339  {
1340  if (myTrivialOffset + GA_Size(destindex) + i != values[srcindex + i] + GA_Size(offset))
1341  {
1342  ismatch = false;
1343  break;
1344  }
1345  }
1346  if (ismatch)
1347  return;
1348  }
1349  harden();
1350  myData->copyAdd(destindex, values, srcindex, n, offset);
1351  }
1352  void copyAdd(FromType destindex, const GA_ListTypeRef<FromType, ToType> &values, FromType srcindex, GA_Size n, ToType offset)
1353  {
1354  if (isTrivial())
1355  {
1356  if (values.isTrivial() && myTrivialOffset + destindex == values.myTrivialOffset + srcindex)
1357  return;
1358 
1359  bool ismatch = true;
1360  for (GA_Size i = 0; i < n; ++i)
1361  {
1362  if (myTrivialOffset + GA_Size(destindex) + i != GA_Size(values(srcindex + i)) + GA_Size(offset))
1363  {
1364  ismatch = false;
1365  break;
1366  }
1367  }
1368  if (ismatch)
1369  return;
1370  }
1371  harden();
1372  myData->copyAdd(destindex, values, srcindex, n, offset);
1373  }
1374  void setTrivialRange(FromType startindex, ToType startvalue, GA_Size nelements)
1375  {
1376  FromType endindex = startindex + nelements;
1377  if (isTrivial())
1378  {
1379  if (startindex == FromType(0) && nelements >= mySize)
1380  {
1381  myTrivialOffset = startvalue;
1382  mySize = nelements;
1383  return;
1384  }
1385  if (myTrivialOffset+GA_Size(startindex) == GA_Size(startvalue))
1386  {
1387  if (endindex > FromType(mySize))
1388  mySize = endindex;
1389  return;
1390  }
1391  }
1392  else if (startindex == FromType(0) && nelements >= mySize)
1393  {
1394  setTrivial(startvalue, nelements);
1395  return;
1396  }
1397 
1398  exint new_size = SYSmax(exint(endindex), exint(mySize));
1399  harden(new_size);
1400  mySize = new_size;
1402  for (GA_Size i = 0; i < nelements; ++i)
1403  data->set(startindex + i, startvalue + i);
1404  }
1405 
1406  /// Set all entries to a constant value
1407  void constant(ToType value);
1408 
1409  /// Cyclically shift the entire array by howMany
1410  void cycle(GA_Size howMany);
1411 
1412  /// Reverse the entire array
1413  void reverse();
1414 
1415  void harden()
1416  {
1417  if (isTrivial())
1418  {
1421  UT_ASSERT_P((intptr_t(data) & TRIVIAL_MASK) == 0);
1422  INT_TYPE *array = data->getRawData();
1423  for (exint i = 0; i < exint(mySize); i++)
1424  array[i] = ToType(myTrivialOffset+i);
1425 #if GA_OFFSETLIST_VERBOSE_DEBUG
1426  printf("%p taking ownership of new %p in harden()\n", this, data);
1427  fflush(stdout);
1428 #endif
1429  myData = data;
1430  }
1431  else if (myData->isShared())
1432  {
1433  // ensure we have a ListTypeData and that isn't referenced by
1434  // any other GA_ListType
1436 #if GA_OFFSETLIST_VERBOSE_DEBUG
1437  printf("%p removing reference to %p in harden(), and taking ownership of new %p\n", this, myData, data);
1438  fflush(stdout);
1439 #endif
1440  myData->unref();
1441 
1442  // NOTE: DO NOT set myData to NULL, even temporarily, because it
1443  // *must* be threadsafe to call isTrivial() while hardening
1444  // a non-trivial list and get false as a return value.
1445  // GA_IndexMap::compactIndices() may be called at the same
1446  // time as GA_IndexMap::isTrivial(), and isTrivial() *must*
1447  // return false, no matter what the race.
1448  myData = data;
1449  }
1450  UT_ASSERT_P(!isTrivial() && !myData->isShared());
1451  }
1452 
1453  void harden(exint mincapacity)
1454  {
1455  if (isTrivial())
1456  {
1458  ListTypeData *data = ListTypeData::allocate(mincapacity);
1459  UT_ASSERT_P((intptr_t(data) & TRIVIAL_MASK) == 0);
1460  INT_TYPE *array = data->getRawData();
1461  if (mincapacity < mySize)
1462  mySize = mincapacity;
1463  for (exint i = 0; i < exint(mySize); i++)
1464  array[i] = ToType(myTrivialOffset+i);
1465 #if GA_OFFSETLIST_VERBOSE_DEBUG
1466  printf("%p taking ownership of new %p in harden(mincapacity)\n", this, data);
1467  fflush(stdout);
1468 #endif
1469  myData = data;
1470  }
1471  else if (myData->isShared())
1472  {
1473  // ensure we have a ListTypeData and that isn't referenced by
1474  // any other GA_ListType
1475  ListTypeData *data = myData->copy(mySize, mincapacity);
1476 #if GA_OFFSETLIST_VERBOSE_DEBUG
1477  printf("%p removing reference to %p in harden(mincapacity), and taking ownership of new %p\n", this, myData, data);
1478  fflush(stdout);
1479 #endif
1480  myData->unref();
1481 
1482  // NOTE: DO NOT set myData to NULL, even temporarily, because it
1483  // *must* be threadsafe to call isTrivial() while hardening
1484  // a non-trivial list and get false as a return value.
1485  // GA_IndexMap::compactIndices() may be called at the same
1486  // time as GA_IndexMap::isTrivial(), and isTrivial() *must*
1487  // return false, no matter what the race.
1488  myData = data;
1489 
1490  if (mincapacity < mySize)
1491  mySize = mincapacity;
1492  }
1493  else if (mincapacity > myData->capacity())
1494  {
1495 #if GA_OFFSETLIST_VERBOSE_DEBUG
1496  printf("%p bumping capacity of %p, current capacity = %d in harden(mincapacity=%d)\n", this, myData, int(mincapacity), int(myData->capacity()));
1497 #endif
1498  myData = myData->bumpCapacity(mincapacity);
1499 #if GA_OFFSETLIST_VERBOSE_DEBUG
1500  printf(" now %p new capacity = %d\n", myData, int(myData->capacity()));
1501  fflush(stdout);
1502 #endif
1503  }
1504  UT_ASSERT_P(!isTrivial() && !myData->isShared());
1505  }
1506 
1507  /// WARNING: PLEASE DO NOT CALL THIS UNLESS YOU KNOW WHAT YOU'RE DOING!
1508  /// IF YOU'RE UNSURE, YOU DON'T NEED TO CALL THIS!
1509  /// Only call this if it's necessary to copy a GA_ListType and share
1510  /// its ownership in some way that doesn't correctly update the
1511  /// ref count for non-trivial lists.
1512  /// (This was added for GA_PrimitiveList to represent a GA_OffsetList
1513  /// with a UT_FixedVector<int64,2>.)
1514  void incDataRef()
1515  {
1516  if (!isTrivial())
1517  {
1518 #if GA_OFFSETLIST_VERBOSE_DEBUG
1519  printf("%p adding reference to %p in incDataRef()\n", this, myData);
1520  fflush(stdout);
1521 #endif
1522  myData->ref();
1523  }
1524  }
1525 };
1526 
1527 
1528 // A list of offsets. The index type is still specified as a template
1529 // parameter.
1530 template <typename FromType, typename INT_TYPE=exint>
1531 class GA_API GA_OffsetListType : public GA_ListType<FromType, GA_Offset, INT_TYPE>
1532 {
1533 private:
1534  // Shorthand for the base class
1536  using Base::myData;
1537  using Base::myIsFlagSet;
1538  using Base::myIsTrivial;
1539  using Base::myTrivialOffset;
1540  using Base::mySize;
1541 public:
1542  using Base::clear;
1543  using Base::get;
1544  using Base::isTrivial;
1545  using Base::set;
1546  using Base::size;
1547  using typename Base::theIntType;
1548 
1549  // Default c-tor
1550  explicit GA_OffsetListType() : Base() {}
1551  // Copy c-tor
1553  : Base(src) {}
1555  : Base(src) {}
1556  // A GA_OffsetArray is a UT_Array of offsets. The UT_Array doesn't have
1557  // paged storage, nor COW semantics, it's just a flat list of offsets.
1558  // This will construct a GA_OffsetListType by copying a portion of the array.
1559  GA_OffsetListType(const UT_ValArray<GA_Offset> &src, FromType start=FromType(0), FromType end=FromType(-1))
1560  : Base(src, start, end) {}
1561 
1562  /// Copy assignment operator
1564  GA_OffsetListType &operator=(const GA_OffsetListType &src) = default;
1565 
1566  /// Move assignment operator
1568  GA_OffsetListType &operator=(GA_OffsetListType &&src) = default;
1569 
1570  /// Copy assignment operator from GA_ListTypeRef.
1571  /// Although it may seem strange to have this at all, it should be
1572  /// safe, since the destination does take (shared) ownership of any
1573  /// non-trivial data. There should be a GA_OffsetListType somewhere else
1574  /// that already owns this.
1577  {
1578  Base::operator=(src);
1579  return *this;
1580  }
1581 
1582  /// @{
1583  /// Swap offset values for defragmentation process. When defragmenting,
1584  /// offsets will move. This method will update all references to offsets
1585  /// to their new values. This returns the number of values updated.
1586  GA_Size swapOffsetValues(const GA_Defragment &defrag);
1587  /// @}
1588 
1589  /// @section JSON-GA_OffsetList JSON Schema: GA_OffsetList
1590  /// @code
1591  /// {
1592  /// "name" : "GA_OffsetList",
1593  /// "description" : "An array of offsets/indicies",
1594  /// "type" : "array",
1595  /// "items" : "integer",
1596  /// }
1597  /// @endcode
1598  /// @see @ref JSON_FileFormat
1599 
1600  /// Save the offsets by doing the mapping to the points in the save map
1601  bool jsonPointArray(UT_JSONWriter &w, const GA_SaveMap &save) const;
1602  /// Save the offsets by doing the mapping to the vertices in the save map
1603  bool jsonVertexArray(UT_JSONWriter &w, const GA_SaveMap &save) const;
1604  /// Save the offsets by doing the mapping to the primitives in the save map
1605  bool jsonPrimitiveArray(UT_JSONWriter &w, const GA_SaveMap &save) const;
1606 
1607  /// Load a point list from a JSON stream
1608  bool jsonPointArray(UT_JSONParser &p, const GA_LoadMap &load);
1609  /// Load a vertex list from a JSON stream
1610  bool jsonVertexArray(UT_JSONParser &p, const GA_LoadMap &load);
1611  /// Load a primitive list from a JSON stream
1612  bool jsonPrimitiveArray(UT_JSONParser &p, const GA_LoadMap &load);
1613 
1614  /// Generic load given a load offset
1615  bool jsonLoad(UT_JSONParser &p, GA_Offset load_offset);
1616  /// Load, appending to the current offset list without initial clear
1617  bool jsonLoadAppend(UT_JSONParser &p, GA_Offset load_offset);
1618  /// Generic load from a JSON stream saved by index that maps the ordered
1619  /// index to an offset.
1620  bool jsonLoadByIndex(UT_JSONParser &p, const GA_IndexMap &index_map,
1621  GA_Index load_offset);
1622  /// Load from a JSON stream saved by index, mapping the ordered index to
1623  /// an offset and appending to the current offset list without an initial
1624  /// clear.
1625  bool jsonLoadAppendByIndex(UT_JSONParser &p,
1626  const GA_IndexMap &index_map,
1627  GA_Index load_offset);
1628 
1629 private:
1630  bool jsonSaveTranslatedArray(
1631  UT_JSONWriter &w,
1632  const GA_SaveMap &save,
1633  GA_AttributeOwner xlate) const;
1634 };
1635 
1636 /// GA_OffsetList is a map from index to offset
1638 
1639 /// GA_OffsetListRef is like GA_OffsetList, except that it doesn't own
1640 /// its data. It's useful for making a temporary copy of a GA_OffsetList
1641 /// that isn't going to be changing during the lifetime of the copy,
1642 /// to avoid having to ref and unref myData, among a few related speedups.
1644 
1645 #endif
1646 
GLdouble s
Definition: glew.h:1390
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:1447
vbool4 insert(const vbool4 &a, bool val)
Helper: substitute val for a[i].
Definition: simd.h:3340
FromType multipleInsert(FromType i, GA_Size count)
reference operator*() const
void printf(internal::basic_buffer< Char > &buf, basic_string_view< Char > format, basic_format_args< Context > args)
Definition: printf.h:570
UT_ASSERT_COMPILETIME(BRAY_EVENT_MAXFLAGS<=32)
SYS_FORCE_INLINE GA_ListType(const GA_ListType &src)
Copy constructor.
void harden(exint mincapacity)
GLsizeiptr size
Definition: glew.h:1681
GLenum src
Definition: glew.h:2410
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.
GLuint index
Definition: glew.h:1814
GA_OffsetListType< GA_Size > GA_OffsetList
GA_OffsetList is a map from index to offset.
bool GAisValid(GA_Size v)
Definition: GA_Types.h:645
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)
GLint GLsizei const GLuint64 * values
Definition: glew.h:3612
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
Synonym for isClosed()
#define CMP_OP(OP)
void setTrivial(ToType startvalue, GA_Size size)
Makes the list a trivial list with the specified start value and size.
void reverse(I begin, I end)
Definition: pugixml.cpp:7190
FromType findInRangeNotEqual(FromType start, FromType end, ToType search) const
void setTrivialRange(FromType startindex, ToType startvalue, GA_Size nelements)
const GLint * first
Definition: glew.h:1528
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
const GLdouble * v
Definition: glew.h:1391
#define UT_ASSERT_MSG_P(ZZ,...)
Definition: UT_Assert.h:137
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:872
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:231
SYS_FORCE_INLINE GA_ListTypeRef()
Default constructor.
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
#define UT_ASSERT_MSG(ZZ,...)
Definition: UT_Assert.h:138
void set(FromType index, ToType value)
Set the index to the value.
GA_Size GA_Offset
Definition: GA_Types.h:637
GA_OffsetListType(const GA_ListTypeRef< FromType, GA_Offset, INT_TYPE > &src)
SYS_FORCE_INLINE INT_TYPE * getRawData()
long long int64
Definition: SYS_Types.h:111
SYS_FORCE_INLINE bool isTrivial() const
ListTypeData * setCapacity(exint new_capacity)
unsigned long long uint64
Definition: SYS_Types.h:112
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.
std::enable_if< is_contiguous< Container >::value, typename checked< typename Container::value_type >::type >::type reserve(std::back_insert_iterator< Container > &it, std::size_t n)
Definition: format.h:593
base_iterator(const base_iterator< EIT > &src)
int64 exint
Definition: SYS_Types.h:120
GLint GLenum GLsizei GLint GLsizei const void * data
Definition: glew.h:1379
void cycle(GA_Size howMany)
Cyclically shift the entire array by howMany.
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:134
base_iterator & operator++()
iterator end()
FromType findValidInRange(FromType start, FromType end) const
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
GLubyte GLubyte GLubyte GLubyte w
Definition: glew.h:1890
SYS_FORCE_INLINE GA_ListType & operator=(GA_ListType &&src)
Move assignment operator.
void countMemory(UT_MemoryCounter &counter, bool inclusive) const
GLuint GLuint end
Definition: glew.h:1253
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.
SYS_FORCE_INLINE const INT_TYPE & operator()(exint index) const
GLsizei n
Definition: glew.h:4040
const GLfloat * c
Definition: glew.h:16296
friend class GA_ListType
Definition: GA_OffsetList.h:55
void changeSize(FromType new_capacity)
typedef int(WINAPI *PFNWGLRELEASEPBUFFERDCARBPROC)(HPBUFFERARB hPbuffer
Options during loading.
Definition: GA_LoadMap.h:42
Defragmentation of IndexMaps.
Definition: GA_Defragment.h:45
GA_Size removeAll(ToType v, FromType size)
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:631
void unsafeShareData(UT_Array< T > &src)
Definition: UT_Array.h:854
base_iterator(LIST_T *list, FromType c)
void cycle(exint howMany)
Cyclically shifts the entire array by howMany.
Definition: UT_ArrayImpl.h:651
SYS_FORCE_INLINE ToType operator()(FromType i) const
Convenience () operator to access the list entries.
GLuint start
Definition: glew.h:1253
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.
GLfloat GLfloat p
Definition: glew.h:16321
void sortAscending(FromType size)
GA_AttributeOwner
Definition: GA_Types.h:33
SYS_FORCE_INLINE void setClosed(bool v)
Synonym for setExtraFlag(bool)
Allocator::value_type * allocate(Allocator &alloc, std::size_t n)
Definition: format.h:282
SYS_FORCE_INLINE GA_ListType(GA_ListType &&src)
Move constructor.
base_iterator operator+(FromType n) const
GLuint counter
Definition: glew.h:2740
base_iterator operator--(int)
static const intptr_t TRIVIAL_MASK
SYS_FORCE_INLINE void setExtraFlag(bool v)
Synonym for setClosed(bool)
void setTrivial(ToType startvalue, GA_Size size, bool flag)
SYS_FORCE_INLINE void setTrivial(ToType startvalue, GA_Size size, bool flag)
FMT_CONSTEXPR bool find(Ptr first, Ptr last, T value, Ptr &out)
Definition: format.h:2104
GLdouble GLdouble GLdouble r
Definition: glew.h:1406
GLuint GLuint GLsizei count
Definition: glew.h:1253
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
GLenum array
Definition: glew.h:9066
GA_OffsetListType(const UT_ValArray< GA_Offset > &src, FromType start=FromType(0), FromType end=FromType(-1))
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:135
void cycle(GA_Size howMany, FromType size)
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:64
SYS_FORCE_INLINE ~GA_ListType()
Destructor.
FromType removeIndex(FromType i)
Alias for remove to match UT array types.
void constant(ToType value, FromType size)
#define SYSmin(a, b)
Definition: SYS_Math.h:1448
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)
GLsizei const GLfloat * value
Definition: glew.h:1849
void sort(I begin, I end, const Pred &pred)
Definition: pugixml.cpp:7334
SYS_FORCE_INLINE void clear()
clear removes all of the entries
SYS_FORCE_INLINE bool isClosed() const
Synonym for getExtraFlag()
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())
SYS_FORCE_INLINE const INT_TYPE * getArray() const
GLintptr offset
Definition: glew.h:1682
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)