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