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 how_many, 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.
369  UT_Array<INT_TYPE> array;
370  array.unsafeShareData(getRawData(), size);
371  array.cycle(how_many);
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
501  GA_ListTypeRef(GA_ListTypeRef &&src) noexcept
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
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) noexcept
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  {
827  public:
828  using iterator_category = std::random_access_iterator_tag;
829  using value_type = ToType;
830  using difference_type = FromType;
831  using pointer = ToType*;
832  using reference = ToType;
833 
835  : myList(nullptr)
836  , myCurrent(-1)
837  {
838  }
839 
840  template <typename EIT>
842  : myList(src.myList)
843  , myCurrent(src.myCurrent)
844  {
845  }
847  {
848  return myList->get(myCurrent);
849  }
850  reference item() const
851  {
852  return myList->get(myCurrent);
853  }
854  reference operator[](FromType n) const
855  {
856  return myList->get(myCurrent+n);
857  }
859  {
860  ++myCurrent;
861  return *this;
862  }
864  {
865  base_iterator tmp = *this;
866  ++myCurrent;
867  return tmp;
868  }
870  {
871  --myCurrent;
872  return *this;
873  }
875  {
876  base_iterator tmp = *this;
877  --myCurrent;
878  return tmp;
879  }
881  {
882  myCurrent += n;
883  return *this;
884  }
885  base_iterator operator+(FromType n) const
886  {
887  return base_iterator(myList, myCurrent+n);
888  }
890  { return (*this) += (-n); }
891  base_iterator operator-(FromType n) const
892  { return (*this) + (-n); }
893  template <typename LT>
894  bool operator==(const base_iterator<LT> &r) const
895  { return r.myCurrent == myCurrent; }
896  template <typename LT>
897  bool operator!=(const base_iterator<LT> &r) const
898  { return r.myCurrent != myCurrent; }
899 
900  #define CMP_OP(OP) \
901  template <typename LT> \
902  bool operator OP(const base_iterator<LT> &r) const { \
903  return myCurrent OP r.myCurrent; \
904  }
905  CMP_OP(<)
906  CMP_OP(>)
907  CMP_OP(<=)
908  CMP_OP(>=)
909  #undef CMP_OP
910  template <typename LT>
911  FromType operator-(const base_iterator<LT> &r) const
912  { return (myCurrent - r.myCurrent); }
913  protected:
914  friend class GA_ListTypeRef<FromType, ToType, INT_TYPE>;
915  base_iterator(LIST_T *list, FromType c)
916  : myList(list)
917  , myCurrent(c)
918  {
919  }
920  private:
921  LIST_T *myList;
922  FromType myCurrent;
923  };
924  using iterator = base_iterator<this_type>;
925  using const_iterator = base_iterator<const this_type>;
926 
927  /// @{
928  /// @note It's likely more efficient to use @c forEach() than iterators
929  iterator begin() { return iterator(this, FromType(0)); }
930  iterator end() { return iterator(this, size()); }
931  const_iterator begin() const { return const_iterator(this, FromType(0)); }
932  const_iterator end() const { return const_iterator(this, size()); }
933  /// @}
934 
935  /// Report memory usage (includes all shared memory)
937  int64 getMemoryUsage(bool inclusive) const
938  {
939  return (inclusive ? sizeof(*this) : 0) + (!isTrivial() ? myData->getMemoryUsage(true) : 0);
940  }
941 
943  const INT_TYPE *getArray() const
944  {
945  return !isTrivial() ? myData->getRawData() : nullptr;
946  }
948  INT_TYPE *getArray()
949  {
950  return !isTrivial() ? myData->getRawData() : nullptr;
951  }
952 
953 protected:
954  static const intptr_t POINTER_MASK = ~0x1;
955  static const intptr_t TRIVIAL_MASK = 0x1;
956  static const intptr_t FLAG_MASK = 0x1;
957 #ifndef SESI_LITTLE_ENDIAN
958 #error "Make sure the bitfields in the union work on big endian platforms!"
959 #endif
960  union {
961  ListTypeData *myData;
962  struct {
963  // NOTE: myTrivialOffset must be signed to support
964  // GA_INVALID_OFFSET and GA_INVALID_INDEX, but
965  // mySize can be unsigned.
966  int64 myIsTrivial:1;
967  int64 myTrivialOffset:63;
968  // Make sure that this flag doesn't overlap with the
969  // pointer, so that it doesn't need to be considered
970  // when reading/writing myData. myIsTrivial
971  // can overlap with myData, because it's
972  // mutually exclusive with using myData.
973  uint64 myIsFlagSet:1;
974  uint64 mySize:63;
975  };
976  };
977 };
978 
979 template <typename FromType, typename ToType, typename INT_TYPE=exint>
980 class GA_API GA_ListType : public GA_ListTypeRef<FromType, ToType, INT_TYPE>
981 {
982 private:
983  // These friend declarations are needed for accessing data in related types.
984  template<typename FromType2,typename ToType2,typename INT_TYPE2>
985  friend class GA_ListTypeRef;
986  template<typename FromType2,typename ToType2,typename INT_TYPE2>
987  friend class GA_ListType;
988 
990 protected:
991  using Base::myData;
992  using Base::myIsTrivial;
993  using Base::myTrivialOffset;
994  using Base::myIsFlagSet;
995  using Base::mySize;
996  using Base::POINTER_MASK;
997  using Base::TRIVIAL_MASK;
998  using Base::FLAG_MASK;
999  // I don't know why one build machine running GCC 4.8 needed
1000  // "ListTypeData =" and the other didn't, but I've put it here
1001  // anyway, because it should keep everyone happy.
1002  using ListTypeData = typename Base::ListTypeData;
1003 public:
1004  using Base::get;
1005  using Base::isTrivial;
1006  using Base::size;
1007  using Base::capacity;
1008  using typename Base::theIntType;
1009 public:
1010  /// Default constructor
1012  explicit GA_ListType()
1013  : Base()
1014  {
1015  myIsTrivial = true;
1016  myTrivialOffset = 0;
1017  myIsFlagSet = false;
1018  mySize = 0;
1019  }
1020 
1021  /// Copy constructor
1024  : Base()
1025  {
1026  if (!src.isTrivial())
1027  {
1028 #if GA_OFFSETLIST_VERBOSE_DEBUG
1029  printf("%p adding reference to %p (orig reference by list %p) in copy constructor\n", this, src.myData, &src);
1030  fflush(stdout);
1031 #endif
1032  src.myData->ref();
1033  }
1034  // NOTE: I'm assuming that it's expected that myIsFlagSet will be copied.
1035  Base::operator=(src);
1036  }
1037 
1038  /// Move constructor
1040  GA_ListType(GA_ListType &&src) noexcept
1041  : Base()
1042  {
1043 #if GA_OFFSETLIST_VERBOSE_DEBUG
1044  if (!src.isTrivial())
1045  {
1046  printf("%p stealing reference to %p (orig reference by list %p) in move constructor\n", this, src.myData, &src);
1047  fflush(stdout);
1048  }
1049 #endif
1050  Base::operator=(src);
1051  src.myIsTrivial = true;
1052  }
1053 
1054  /// Copy constructor from GA_ListTypeRef.
1055  /// Although it may seem strange to have this at all, it should be
1056  /// safe, since the destination does take (shared) ownership of any
1057  /// non-trivial data. There should be a GA_ListType somewhere else
1058  /// that already owns this.
1060  explicit GA_ListType(const Base &src)
1061  : Base()
1062  {
1063  if (!src.isTrivial())
1064  {
1065 #if GA_OFFSETLIST_VERBOSE_DEBUG
1066  printf("%p adding reference to %p (orig reference by listref %p) in list(listref) type conversion constructor\n", this, src.myData, &src);
1067  fflush(stdout);
1068 #endif
1069  src.myData->ref();
1070  UT_ASSERT_MSG_P(src.myData->isShared(), "Something should have already owned this data.");
1071  }
1072  // NOTE: I'm assuming that it's expected that myIsFlagSet will be copied.
1073  Base::operator=(src);
1074  }
1075 
1076  /// Trivial list constructor
1078  GA_ListType(ToType startvalue, GA_Size size, bool flag_set=false)
1079  : Base(startvalue, size, flag_set)
1080  {}
1081 
1082  // This will construct a GA_ListType by copying a portion of the array.
1083  GA_ListType(const UT_Array<ToType> &src, FromType start=FromType(0), FromType end=FromType(-1));
1084 
1085  /// Destructor
1088  {
1089  if (!isTrivial())
1090  {
1091 #if GA_OFFSETLIST_VERBOSE_DEBUG
1092  printf("%p removing reference to %p in desctructor\n", this, myData);
1093  fflush(stdout);
1094 #endif
1095  myData->unref();
1096  }
1097  }
1098 
1099  /// Copy assignment operator
1102  {
1103  if (!isTrivial())
1104  {
1105 #if GA_OFFSETLIST_VERBOSE_DEBUG
1106  printf("%p removing reference to %p in copy assignment operator\n", this, myData);
1107  fflush(stdout);
1108 #endif
1109  myData->unref();
1110  }
1111  if (!src.isTrivial())
1112  {
1113 #if GA_OFFSETLIST_VERBOSE_DEBUG
1114  printf("%p adding reference to %p (orig reference by list %p) in copy assignment operator\n", this, src.myData, &src);
1115  fflush(stdout);
1116 #endif
1117  src.myData->ref();
1118  }
1119  // NOTE: I'm assuming that it's expected that myIsFlagSet will be copied.
1120  Base::operator=(src);
1121  return *this;
1122  }
1123 
1124  /// Move assignment operator
1127  {
1128  if (!isTrivial())
1129  {
1130 #if GA_OFFSETLIST_VERBOSE_DEBUG
1131  printf("%p removing reference to %p in move assignment operator\n", this, myData);
1132  fflush(stdout);
1133 #endif
1134  myData->unref();
1135  }
1136 #if GA_OFFSETLIST_VERBOSE_DEBUG
1137  if (!src.isTrivial())
1138  {
1139  printf("%p stealing reference to %p (orig reference by list %p) in move assignment operator\n", this, src.myData, &src);
1140  fflush(stdout);
1141  }
1142 #endif
1143  // NOTE: I'm assuming that it's expected that myIsFlagSet will be copied.
1144  Base::operator=(src);
1145  src.myIsTrivial = true;
1146  return *this;
1147  }
1148 
1149  /// Copy assignment operator from GA_ListTypeRef.
1150  /// Although it may seem strange to have this at all, it should be
1151  /// safe, since the destination does take (shared) ownership of any
1152  /// non-trivial data. There should be a GA_ListType somewhere else
1153  /// that already owns this.
1156  {
1157  if (!isTrivial())
1158  {
1159 #if GA_OFFSETLIST_VERBOSE_DEBUG
1160  printf("%p removing reference to %p in copy-from-listref assignment operator\n", this, myData);
1161  fflush(stdout);
1162 #endif
1163  myData->unref();
1164  }
1165  if (!src.isTrivial())
1166  {
1167 #if GA_OFFSETLIST_VERBOSE_DEBUG
1168  printf("%p adding reference to %p (orig reference by listref %p) in copy-from-listref assignment operator\n", this, src.myData, &src);
1169  fflush(stdout);
1170 #endif
1171  src.myData->ref();
1172  UT_ASSERT_MSG_P(src.myData->isShared(), "Something should have already owned this data.");
1173  }
1174  // NOTE: I'm assuming that it's expected that myIsFlagSet will be copied.
1175  Base::operator=(src);
1176  return *this;
1177  }
1178 
1179  /// Count memory usage using a UT_MemoryCounter in order to count
1180  /// shared memory correctly.
1181  /// If inclusive is true, the size of this object is counted,
1182  /// else only memory owned by this object is counted.
1183  /// If this is pointed to by the calling object, inclusive should be true.
1184  /// If this is contained in the calling object, inclusive should be false.
1185  /// (Its memory was already counted in the size of the calling object.)
1186  void countMemory(UT_MemoryCounter &counter, bool inclusive) const;
1187 
1188  /// clear removes all of the entries
1190  void clear()
1191  {
1192  if (!isTrivial())
1193  {
1194 #if GA_OFFSETLIST_VERBOSE_DEBUG
1195  printf("%p removing reference to %p in clear function\n", this, myData);
1196  fflush(stdout);
1197 #endif
1198  myData->unref();
1199  }
1200  myIsTrivial = true;
1201  // NOTE: DON'T set myIsFlagSet, since it's independent of whether
1202  // this list is clear.
1203  myTrivialOffset = 0;
1204  mySize = 0;
1205  }
1206 
1207  /// Identifies whether the data is a trivial mapping and if so,
1208  /// eliminates storage for the map.
1209  void computeTrivial();
1210 
1211  /// Makes the list a trivial list with the specified start value and size
1212  void setTrivial(ToType startvalue, GA_Size size)
1213  {
1214  UT_ASSERT(size >= 0);
1215  if (!isTrivial())
1216  {
1217 #if GA_OFFSETLIST_VERBOSE_DEBUG
1218  printf("%p removing reference to %p in setTrivial(start,size)\n", this, myData);
1219  fflush(stdout);
1220 #endif
1221  myData->unref();
1222  myIsTrivial = true;
1223  }
1224  myTrivialOffset = startvalue;
1225  mySize = size;
1226  }
1227 
1228  /// Makes the list a trivial list with the specified start value and size,
1229  /// and also sets the extra flag.
1230  void setTrivial(ToType startvalue, GA_Size size, bool flag)
1231  {
1232  UT_ASSERT(size >= 0);
1233  if (!isTrivial())
1234  {
1235 #if GA_OFFSETLIST_VERBOSE_DEBUG
1236  printf("%p removing reference to %p in setTrivial(start,size,flag)\n", this, myData);
1237  fflush(stdout);
1238 #endif
1239  myData->unref();
1240  myIsTrivial = true;
1241  }
1242  myTrivialOffset = startvalue;
1243  mySize = size;
1244  myIsFlagSet = flag;
1245  }
1246 
1247  /// Set the number of entries - if the number is smaller than the current
1248  /// entries, the capacity may be decreased. If doresize is false,
1249  /// only the number of entries is changed, not the size.
1250  void setEntries(FromType sz, bool doresize=true);
1251  /// Reserve capacity for a number of entries (prevents reallocation as
1252  /// elements are appended).
1253  /// This does nothing if the list is currently trivial.
1254  void reserve(FromType mincapacity); // Reserve capacity
1255 
1256  /// If trivial, this sets the size to the minimum of the current size and new_capacity.
1257  /// If not trivial, this sets the capacity to new_capacity, (also correctly decreasing
1258  /// the size if currently greater than new_capacity.)
1259  void changeSize(FromType new_capacity);
1260 
1261  /// Add a single entry (may grow array)
1262  FromType append(ToType value)
1263  {
1264  if (isTrivial())
1265  {
1266  if (!mySize)
1267  {
1269  mySize = 1;
1270  return FromType(0);
1271  }
1272  if (value == ToType(myTrivialOffset) + mySize)
1273  {
1274  ++mySize;
1275  return FromType(mySize-1);
1276  }
1277  }
1278  harden(mySize+1);
1279  myData->set(FromType(mySize), value);
1280  ++mySize;
1281  return FromType(mySize-1);
1282  }
1283 
1284  /// Append all the entries from the source list. The offset will be added
1285  /// to each value in the source list.
1287 
1288  /// Insert a single entry (may grow array)
1289  FromType insert(FromType i, ToType value);
1290 
1291  /// Insert count entries at the given index (may grow array). The new
1292  /// entries will be uninitialized.
1293  FromType multipleInsert(FromType i, GA_Size count);
1294 
1295  /// Remove the entry at the given offset
1296  FromType remove(FromType i);
1297  /// Find an entry and remove it from the list
1298  FromType findAndRemove(ToType i);
1299  /// Alias for remove to match UT array types
1300  FromType removeIndex(FromType i) { return remove(i); }
1301  /// Remove all matching entries from the list
1302  GA_Size removeAll(ToType i);
1303  /// Remove the last entry
1304  void removeLast()
1305  {
1306 #if !(defined(_MSC_VER) && defined(__clang__))
1307  UT_ASSERT_P(mySize > 0);
1308 #endif
1309  --mySize;
1310  }
1311 
1312  /// Sort entries into ascending order
1313  void sortAscending();
1314 
1315  /// Sort entries into ascending order and remove duplicates
1316  void sortAndRemoveDuplicates();
1317 
1318  /// Set the index to the value
1319  void set(FromType index, ToType value)
1320  {
1321 #if !(defined(_MSC_VER) && defined(__clang__))
1322  UT_ASSERT_P(index >= FromType(0) && index < FromType(mySize));
1323 #endif
1324  if (isTrivial())
1325  {
1326  if (myTrivialOffset+GA_Size(index) == GA_Size(value))
1327  return;
1328  if (mySize==1)
1329  {
1330  myTrivialOffset = GA_Size(value);
1331  return;
1332  }
1333  }
1334 
1335  harden();
1336  myData->set(index, value);
1337  }
1338 
1339  template<typename S>
1340  void set(const S *data, exint size, ToType offset)
1341  {
1342  clear();
1343 
1344  if (size == 0)
1345  return;
1346 
1347  // Check for triviality first
1348  ToType first = ToType(data[0]);
1349  bool istrivial = true;
1350  for (int64 i = 1; i < size; ++i)
1351  {
1352  if (ToType(data[i]) != first + ToType(i))
1353  {
1354  istrivial = false;
1355  break;
1356  }
1357  }
1358 
1359  if (istrivial)
1360  setTrivial(first+offset, FromType(size));
1361  else
1362  {
1364  ListTypeData *newdata = ListTypeData::allocate(size);
1365 #if !(defined(_MSC_VER) && defined(__clang__))
1366  UT_ASSERT_P((intptr_t(newdata) & TRIVIAL_MASK) == 0);
1367 #endif
1368  newdata->set(data, size, offset);
1369  mySize = size;
1370  myData = newdata;
1371  }
1372  }
1373 
1374  void copyAdd(FromType destindex, const int *values, GA_Size srcindex, GA_Size n, ToType offset)
1375  {
1376  if (isTrivial())
1377  {
1378  bool ismatch = true;
1379  for (GA_Size i = 0; i < n; ++i)
1380  {
1381  if (myTrivialOffset + GA_Size(destindex) + i != values[srcindex + i] + GA_Size(offset))
1382  {
1383  ismatch = false;
1384  break;
1385  }
1386  }
1387  if (ismatch)
1388  return;
1389  }
1390  harden();
1391  myData->copyAdd(destindex, values, srcindex, n, offset);
1392  }
1393  void copyAdd(FromType destindex, const GA_ListTypeRef<FromType, ToType> &values, FromType srcindex, GA_Size n, ToType offset)
1394  {
1395  if (isTrivial())
1396  {
1397  if (values.isTrivial() && myTrivialOffset + destindex == values.myTrivialOffset + srcindex)
1398  return;
1399 
1400  bool ismatch = true;
1401  for (GA_Size i = 0; i < n; ++i)
1402  {
1403  if (myTrivialOffset + GA_Size(destindex) + i != GA_Size(values(srcindex + i)) + GA_Size(offset))
1404  {
1405  ismatch = false;
1406  break;
1407  }
1408  }
1409  if (ismatch)
1410  return;
1411  }
1412  harden();
1413  myData->copyAdd(destindex, values, srcindex, n, offset);
1414  }
1415  void setTrivialRange(FromType startindex, ToType startvalue, GA_Size nelements)
1416  {
1417  FromType endindex = startindex + nelements;
1418  if (isTrivial())
1419  {
1420  if (startindex == FromType(0) && nelements >= mySize)
1421  {
1422  myTrivialOffset = startvalue;
1423  mySize = nelements;
1424  return;
1425  }
1426  if (myTrivialOffset+GA_Size(startindex) == GA_Size(startvalue))
1427  {
1428  if (endindex > FromType(mySize))
1429  mySize = endindex;
1430  return;
1431  }
1432  }
1433  else if (startindex == FromType(0) && nelements >= mySize)
1434  {
1435  setTrivial(startvalue, nelements);
1436  return;
1437  }
1438 
1439  exint new_size = SYSmax(exint(endindex), exint(mySize));
1440  harden(new_size);
1441  mySize = new_size;
1443  for (GA_Size i = 0; i < nelements; ++i)
1444  data->set(startindex + i, startvalue + i);
1445  }
1446 
1447  /// Set all entries to a constant value
1448  void constant(ToType value);
1449 
1450  /// Cyclically shift the entire array by how_many
1451  void cycle(GA_Size how_many);
1452 
1453  /// Reverse the entire array
1454  void reverse();
1455 
1456  void harden()
1457  {
1458  if (isTrivial())
1459  {
1462 #if !(defined(_MSC_VER) && defined(__clang__))
1463  UT_ASSERT_P((intptr_t(data) & TRIVIAL_MASK) == 0);
1464 #endif
1465  INT_TYPE *array = data->getRawData();
1466  for (exint i = 0; i < exint(mySize); i++)
1467  array[i] = ToType(myTrivialOffset+i);
1468 #if GA_OFFSETLIST_VERBOSE_DEBUG
1469  printf("%p taking ownership of new %p in harden()\n", this, data);
1470  fflush(stdout);
1471 #endif
1472  myData = data;
1473  }
1474  else if (myData->isShared())
1475  {
1476  // ensure we have a ListTypeData and that isn't referenced by
1477  // any other GA_ListType
1479 #if GA_OFFSETLIST_VERBOSE_DEBUG
1480  printf("%p removing reference to %p in harden(), and taking ownership of new %p\n", this, myData, data);
1481  fflush(stdout);
1482 #endif
1483  myData->unref();
1484 
1485  // NOTE: DO NOT set myData to NULL, even temporarily, because it
1486  // *must* be threadsafe to call isTrivial() while hardening
1487  // a non-trivial list and get false as a return value.
1488  // GA_IndexMap::compactIndices() may be called at the same
1489  // time as GA_IndexMap::isTrivial(), and isTrivial() *must*
1490  // return false, no matter what the race.
1491  myData = data;
1492  }
1493 #if !(defined(_MSC_VER) && defined(__clang__))
1494  UT_ASSERT_P(!isTrivial() && !myData->isShared());
1495 #endif
1496  }
1497 
1498  void harden(exint mincapacity)
1499  {
1500  if (isTrivial())
1501  {
1503  ListTypeData *data = ListTypeData::allocate(mincapacity);
1504 #if !(defined(_MSC_VER) && defined(__clang__))
1505  UT_ASSERT_P((intptr_t(data) & TRIVIAL_MASK) == 0);
1506 #endif
1507  INT_TYPE *array = data->getRawData();
1508  if (mincapacity < mySize)
1509  mySize = mincapacity;
1510  for (exint i = 0; i < exint(mySize); i++)
1511  array[i] = ToType(myTrivialOffset+i);
1512 #if GA_OFFSETLIST_VERBOSE_DEBUG
1513  printf("%p taking ownership of new %p in harden(mincapacity)\n", this, data);
1514  fflush(stdout);
1515 #endif
1516  myData = data;
1517  }
1518  else if (myData->isShared())
1519  {
1520  // ensure we have a ListTypeData and that isn't referenced by
1521  // any other GA_ListType
1522  ListTypeData *data = myData->copy(mySize, mincapacity);
1523 #if GA_OFFSETLIST_VERBOSE_DEBUG
1524  printf("%p removing reference to %p in harden(mincapacity), and taking ownership of new %p\n", this, myData, data);
1525  fflush(stdout);
1526 #endif
1527  myData->unref();
1528 
1529  // NOTE: DO NOT set myData to NULL, even temporarily, because it
1530  // *must* be threadsafe to call isTrivial() while hardening
1531  // a non-trivial list and get false as a return value.
1532  // GA_IndexMap::compactIndices() may be called at the same
1533  // time as GA_IndexMap::isTrivial(), and isTrivial() *must*
1534  // return false, no matter what the race.
1535  myData = data;
1536 
1537  if (mincapacity < mySize)
1538  mySize = mincapacity;
1539  }
1540  else if (mincapacity > myData->capacity())
1541  {
1542 #if GA_OFFSETLIST_VERBOSE_DEBUG
1543  printf("%p bumping capacity of %p, current capacity = %d in harden(mincapacity=%d)\n", this, myData, int(mincapacity), int(myData->capacity()));
1544 #endif
1545  myData = myData->bumpCapacity(mincapacity);
1546 #if GA_OFFSETLIST_VERBOSE_DEBUG
1547  printf(" now %p new capacity = %d\n", myData, int(myData->capacity()));
1548  fflush(stdout);
1549 #endif
1550  }
1551 #if !(defined(_MSC_VER) && defined(__clang__))
1552  UT_ASSERT_P(!isTrivial() && !myData->isShared());
1553 #endif
1554  }
1555 
1556  /// WARNING: PLEASE DO NOT CALL THIS UNLESS YOU KNOW WHAT YOU'RE DOING!
1557  /// IF YOU'RE UNSURE, YOU DON'T NEED TO CALL THIS!
1558  /// Only call this if it's necessary to copy a GA_ListType and share
1559  /// its ownership in some way that doesn't correctly update the
1560  /// ref count for non-trivial lists.
1561  /// (This was added for GA_PrimitiveList to represent a GA_OffsetList
1562  /// with a UT_FixedVector<int64,2>.)
1563  void incDataRef()
1564  {
1565  if (!isTrivial())
1566  {
1567 #if GA_OFFSETLIST_VERBOSE_DEBUG
1568  printf("%p adding reference to %p in incDataRef()\n", this, myData);
1569  fflush(stdout);
1570 #endif
1571  myData->ref();
1572  }
1573  }
1574 };
1575 
1576 
1577 // A list of offsets. The index type is still specified as a template
1578 // parameter.
1579 template <typename FromType, typename INT_TYPE=exint>
1580 class GA_API GA_OffsetListType : public GA_ListType<FromType, GA_Offset, INT_TYPE>
1581 {
1582 private:
1583  // Shorthand for the base class
1585  using Base::myData;
1586  using Base::myIsFlagSet;
1587  using Base::myIsTrivial;
1588  using Base::myTrivialOffset;
1589  using Base::mySize;
1590 public:
1591  using Base::clear;
1592  using Base::get;
1593  using Base::isTrivial;
1594  using Base::set;
1595  using Base::size;
1596  using typename Base::theIntType;
1597 
1598  // Default c-tor
1599  explicit GA_OffsetListType() : Base() {}
1600  // Copy c-tor
1602  : Base(src) {}
1604  : Base(src) {}
1605  // A GA_OffsetArray is a UT_Array of offsets. The UT_Array doesn't have
1606  // paged storage, nor COW semantics, it's just a flat list of offsets.
1607  // This will construct a GA_OffsetListType by copying a portion of the array.
1608  GA_OffsetListType(const UT_Array<GA_Offset> &src, FromType start=FromType(0), FromType end=FromType(-1))
1609  : Base(src, start, end) {}
1610 
1611  /// Copy assignment operator
1613  GA_OffsetListType &operator=(const GA_OffsetListType &src) = default;
1614 
1615  /// Move operator
1616  /// @{
1618  GA_OffsetListType(GA_OffsetListType &&src) = default;
1620  GA_OffsetListType &operator=(GA_OffsetListType &&src) = default;
1621  /// @}
1622 
1623  /// Copy assignment operator from GA_ListTypeRef.
1624  /// Although it may seem strange to have this at all, it should be
1625  /// safe, since the destination does take (shared) ownership of any
1626  /// non-trivial data. There should be a GA_OffsetListType somewhere else
1627  /// that already owns this.
1630  {
1631  Base::operator=(src);
1632  return *this;
1633  }
1634 
1635  /// @{
1636  /// Swap offset values for defragmentation process. When defragmenting,
1637  /// offsets will move. This method will update all references to offsets
1638  /// to their new values. This returns the number of values updated.
1639  GA_Size swapOffsetValues(const GA_Defragment &defrag);
1640  /// @}
1641 
1642  /// @section JSON-GA_OffsetList JSON Schema: GA_OffsetList
1643  /// @code
1644  /// {
1645  /// "name" : "GA_OffsetList",
1646  /// "description" : "An array of offsets/indicies",
1647  /// "type" : "array",
1648  /// "items" : "integer",
1649  /// }
1650  /// @endcode
1651  /// @see @ref JSON_FileFormat
1652 
1653  /// Save the offsets by doing the mapping to the points in the save map
1654  bool jsonPointArray(UT_JSONWriter &w, const GA_SaveMap &save) const;
1655  /// Save the offsets by doing the mapping to the vertices in the save map
1656  bool jsonVertexArray(UT_JSONWriter &w, const GA_SaveMap &save) const;
1657  /// Save the offsets by doing the mapping to the primitives in the save map
1658  bool jsonPrimitiveArray(UT_JSONWriter &w, const GA_SaveMap &save) const;
1659 
1660  /// Load a point list from a JSON stream
1661  bool jsonPointArray(UT_JSONParser &p, const GA_LoadMap &load);
1662  /// Load a vertex list from a JSON stream
1663  bool jsonVertexArray(UT_JSONParser &p, const GA_LoadMap &load);
1664  /// Load a primitive list from a JSON stream
1665  bool jsonPrimitiveArray(UT_JSONParser &p, const GA_LoadMap &load);
1666 
1667  /// Generic load given a load offset
1668  bool jsonLoad(UT_JSONParser &p, GA_Offset load_offset);
1669  /// Load, appending to the current offset list without initial clear
1670  bool jsonLoadAppend(UT_JSONParser &p, GA_Offset load_offset);
1671  /// Generic load from a JSON stream saved by index that maps the ordered
1672  /// index to an offset.
1673  bool jsonLoadByIndex(UT_JSONParser &p, const GA_IndexMap &index_map,
1674  GA_Index load_offset);
1675  /// Load from a JSON stream saved by index, mapping the ordered index to
1676  /// an offset and appending to the current offset list without an initial
1677  /// clear.
1678  bool jsonLoadAppendByIndex(UT_JSONParser &p,
1679  const GA_IndexMap &index_map,
1680  GA_Index load_offset);
1681 
1682 private:
1683  bool jsonSaveTranslatedArray(
1684  UT_JSONWriter &w,
1685  const GA_SaveMap &save,
1686  GA_AttributeOwner xlate) const;
1687 };
1688 
1689 /// GA_OffsetList is a map from index to offset
1691 
1692 /// GA_OffsetListRef is like GA_OffsetList, except that it doesn't own
1693 /// its data. It's useful for making a temporary copy of a GA_OffsetList
1694 /// that isn't going to be changing during the lifetime of the copy,
1695 /// to avoid having to ref and unref myData, among a few related speedups.
1697 
1698 #endif
1699 
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:1570
GLint first
Definition: glcorearb.h:405
FromType multipleInsert(FromType i, GA_Size count)
typedef int(APIENTRYP RE_PFNGLXSWAPINTERVALSGIPROC)(int)
reference operator*() const
UT_ASSERT_COMPILETIME(BRAY_EVENT_MAXFLAGS<=32)
SYS_FORCE_INLINE GA_ListType(const GA_ListType &src)
Copy constructor.
void harden(exint mincapacity)
base_iterator operator++(int)
const_iterator end() const
void copyAdd(FromType destindex, const GA_ListTypeRef< FromType, ToType, S > &values, FromType srcindex, GA_Size n, ToType offset)
SYS_FORCE_INLINE GA_ListType(ToType startvalue, GA_Size size, bool flag_set=false)
Trivial list constructor.
FromType append(ToType value)
Add a single entry (may grow array)
Used to pass options and map offset values during saving.
Definition: GA_SaveMap.h:48
void cycle(GA_Size how_many)
Cyclically shift the entire array by how_many.
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)
GLboolean * data
Definition: glcorearb.h:131
void sortAndRemoveDuplicates()
Sort entries into ascending order and remove duplicates.
const GLdouble * v
Definition: glcorearb.h:837
auto printf(const S &fmt, const T &...args) -> int
Definition: printf.h:626
GA_OffsetListType< GA_Size > GA_OffsetList
GA_OffsetList is a map from index to offset.
GLuint start
Definition: glcorearb.h:475
GLsizei const GLfloat * value
Definition: glcorearb.h:824
FromType findInRangeNotEqual(FromType start, FromType end, ToType search) const
SYS_FORCE_INLINE int64 getMemoryUsage(bool inclusive) const
base_iterator & operator--()
void constant(ToType value)
Set all entries to a constant value.
base_iterator & operator+=(FromType n)
ListTypeData * reallocate(exint new_capacity)
Definition: GA_OffsetList.h:86
void copyAdd(FromType destindex, const GA_ListTypeRef< FromType, ToType > &values, FromType srcindex, GA_Size n, ToType offset)
SYS_FORCE_INLINE bool getExtraFlag() const
Synonym for isClosed()
SYS_FORCE_INLINE void relaxedStore(T val)
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.
GLdouble s
Definition: glad.h:3009
FromType findInRangeNotEqual(FromType start, FromType end, ToType search) const
void setTrivialRange(FromType startindex, ToType startvalue, GA_Size nelements)
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:87
base_iterator< const this_type > const_iterator
#define GA_API
Definition: GA_API.h:14
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:37
SYS_FORCE_INLINE GA_ListType(GA_ListType &&src) noexcept
Move constructor.
#define UT_ASSERT_MSG_P(ZZ,...)
Definition: UT_Assert.h:158
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)
OIIO_FORCEINLINE vbool4 insert(const vbool4 &a, bool val)
Helper: substitute val for a[i].
Definition: simd.h:3436
FromType findValidInRange(FromType start, FromType end) const
SYS_FORCE_INLINE bool GAisValid(GA_Size v)
Definition: GA_Types.h:655
void unsafeClearData()
Definition: UT_Array.h:1091
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:236
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:159
void set(FromType index, ToType value)
Set the index to the value.
GA_Size GA_Offset
Definition: GA_Types.h:646
GA_OffsetListType(const GA_ListTypeRef< FromType, GA_Offset, INT_TYPE > &src)
SYS_FORCE_INLINE INT_TYPE * getRawData()
SYS_FORCE_INLINE bool isTrivial() const
GLdouble n
Definition: glcorearb.h:2008
ListTypeData * setCapacity(exint new_capacity)
auto base_iterator(std::back_insert_iterator< Container > &it, checked_ptr< typename Container::value_type >) -> std::back_insert_iterator< Container >
Definition: format.h:394
GLintptr offset
Definition: glcorearb.h:665
void removeLast()
Remove the last entry.
void computeTrivial()
SYS_FORCE_INLINE INT_TYPE & operator()(exint index)
SYS_FORCE_INLINE GA_ListType(const Base &src)
bool isAscending(exint size) const
FromType findAndRemove(ToType i)
Find an entry and remove it from the list.
base_iterator(const base_iterator< EIT > &src)
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:155
base_iterator & operator++()
iterator end()
FromType findValidInRange(FromType start, FromType end) const
GLuint GLuint end
Definition: glcorearb.h:475
static const intptr_t FLAG_MASK
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
void countMemory(UT_MemoryCounter &counter, bool inclusive) const
static const intptr_t POINTER_MASK
ListTypeData * copy(exint size, exint new_capacity) const
SYS_FORCE_INLINE GA_ListTypeRef(ToType startvalue, GA_Size size, bool flag_set=false)
Trivial list constructor.
SYS_FORCE_INLINE const INT_TYPE & operator()(exint index) const
friend class GA_ListType
Definition: GA_OffsetList.h:55
void changeSize(FromType new_capacity)
long long int64
Definition: SYS_Types.h:116
auto get(const UT_ARTIterator< T > &it) -> decltype(it.key())
Definition: UT_ARTMap.h:1073
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:640
void unsafeShareData(UT_Array< T > &src)
Definition: UT_Array.h:1073
base_iterator(LIST_T *list, FromType c)
SYS_FORCE_INLINE ToType operator()(FromType i) const
Convenience () operator to access the list entries.
auto search(const T &set, const V &val) -> std::pair< bool, decltype(std::begin(detail::smart_deref(set)))>
A search function.
Definition: CLI11.h:3170
auto reserve(std::back_insert_iterator< Container > it, size_t n) -> checked_ptr< typename Container::value_type >
Definition: format.h:357
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.
GLint j
Definition: glad.h:2733
SYS_FORCE_INLINE GA_Size capacity() const
Returns the allocated capacity of the list.
GLsizeiptr size
Definition: glcorearb.h:664
void sortAscending(FromType size)
GA_AttributeOwner
Definition: GA_Types.h:35
SYS_FORCE_INLINE void setClosed(bool v)
Synonym for setExtraFlag(bool)
base_iterator operator+(FromType n) const
base_iterator operator--(int)
GLenum GLsizei GLsizei GLint * values
Definition: glcorearb.h:1602
std::random_access_iterator_tag iterator_category
static const intptr_t TRIVIAL_MASK
void cycle(GA_Size how_many, FromType size)
SYS_FORCE_INLINE void setExtraFlag(bool v)
Synonym for setClosed(bool)
LeafData & operator=(const LeafData &)=delete
void setTrivial(ToType startvalue, GA_Size size, bool flag)
SYS_FORCE_INLINE void setTrivial(ToType startvalue, GA_Size size, bool flag)
GLuint index
Definition: glcorearb.h:786
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
SYS_FORCE_INLINE GA_ListType & operator=(GA_ListType &&src) noexcept
Move assignment operator.
GLubyte GLubyte GLubyte GLubyte w
Definition: glcorearb.h:857
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:156
Definition: core.h:1131
GLboolean r
Definition: glcorearb.h:1222
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.
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:1571
void sortAscending()
Sort entries into ascending order.
GA_OffsetListType(const UT_Array< GA_Offset > &src, FromType start=FromType(0), FromType end=FromType(-1))
void copyAdd(FromType destindex, const S *values, GA_Size srcindex, GA_Size n, ToType offset)
void set(const S *data, exint size, ToType offset)
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()
GLint GLsizei count
Definition: glcorearb.h:405
Definition: format.h:895
Definition: format.h:2459
bool isTrivial(exint size) const
SYS_FORCE_INLINE FromType size() const
Returns the number of used elements in the list (always <= capacity())
FMT_CONSTEXPR auto find(Ptr first, Ptr last, T value, Ptr &out) -> bool
Definition: core.h:2089
SYS_FORCE_INLINE const INT_TYPE * getArray() const
GLenum src
Definition: glcorearb.h:1793
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)