HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
smallVector.h
Go to the documentation of this file.
1 //
2 // Copyright 2019 Pixar
3 //
4 // Licensed under the terms set forth in the LICENSE.txt file available at
5 // https://openusd.org/license.
6 //
7 #ifndef PXR_BASE_TF_SMALL_VECTOR_H
8 #define PXR_BASE_TF_SMALL_VECTOR_H
9 
10 ///
11 /// \file
12 
13 #include "pxr/pxr.h"
14 
15 #include "pxr/base/arch/defines.h"
16 
17 #include <algorithm>
18 #include <cstddef>
19 #include <cstdint>
20 #include <cstdlib>
21 #include <initializer_list>
22 #include <iterator>
23 #include <limits>
24 #include <memory>
25 #include <new>
26 #include <type_traits>
27 
29 
30 // Contains parts of the small vector implementation that do not depend on
31 // *all* of TfSmallVector's template parameters.
33 {
34 protected:
35  // We present the public size_type and difference_type as std::size_t and
36  // std::ptrdiff_t to match std::vector, but internally we store size &
37  // capacity as uint32_t.
38  using _SizeMemberType = std::uint32_t;
39 
40  // Union type containing local storage or a pointer to heap storage.
41  template <size_t Size, size_t Align, size_t NumLocal>
42  union _DataUnion;
43 
44  // Helper alias to produce the right _DataUnion instantiation for a given
45  // ValueType and NumLocal elements.
46  template <class ValueType, size_t NumLocal>
48 
49 public:
50  using size_type = std::size_t;
51  using difference_type = std::ptrdiff_t;
52 
53  // Returns the local capacity that may be used without increasing the size
54  // of the TfSmallVector. TfSmallVector<T, N> will never use more local
55  // capacity than is specified by N but clients that wish to maximize local
56  // occupancy in a generic way can compute N using this function.
57  template <typename U>
59  return (alignof(U) <= alignof(_Data<U, 0>))
60  ? sizeof(_Data<U, 0>) / sizeof(U)
61  : 0;
62  }
63 
64 protected:
65 
66  // Enabler used to disambiguate the range-based constructor (begin, end)
67  // from the n-copies constructor (size_t n, value_type const &value)
68  // when the value_type is integral.
69  template<typename _ForwardIterator>
72  std::is_convertible_v<
73  typename std::iterator_traits<
74  _ForwardIterator>::iterator_category,
75  std::forward_iterator_tag
76  >
77  >;
78 
79  // Invoke std::uninitialized_copy that either moves or copies entries,
80  // depending on whether the type is move constructible or not.
81  template <typename Iterator>
82  static Iterator _UninitializedMove(
83  Iterator first, Iterator last, Iterator dest) {
84  return std::uninitialized_copy(
85  std::make_move_iterator(first),
86  std::make_move_iterator(last),
87  dest);
88  }
89 
90  // Invokes either the move or copy constructor (via placement new),
91  // depending on whether U is move constructible or not.
92  template <typename U>
93  static void _MoveConstruct(U *p, U *src) {
94  new (p) U(std::move(*src));
95  }
96 
97  // The data storage, which is a union of both the local storage, as well
98  // as a pointer, holding the address to the remote storage on the heap, if
99  // used.
100  template <size_t Size, size_t Align, size_t NumLocal>
101  union _DataUnion {
102  public:
103  // XXX: Could in principle assert in calls to GetLocalStorage() when
104  // HasLocal is false. Add dependency on tf/diagnostic.h?
105  static constexpr bool HasLocal = NumLocal != 0;
106 
107  void *GetLocalStorage() {
108  return HasLocal ? _local : nullptr;
109  }
110  const void *GetLocalStorage() const {
111  return HasLocal ? _local : nullptr;
112  }
113 
115  return _remote;
116  }
117  const void *GetRemoteStorage() const {
118  return _remote;
119  }
120 
121  void SetRemoteStorage(void *p) {
122  _remote = p;
123  }
124  private:
125  // Pointer to heap storage.
126  void *_remote;
127  // Local storage -- min size is sizeof(_remote).
128  alignas(NumLocal == 0 ? std::alignment_of_v<void *> : Align)
129  char _local[std::max<size_t>(Size * NumLocal, sizeof(_remote))];
130  };
131 };
132 
133 ////////////////////////////////////////////////////////////////////////////////
134 ///
135 /// \class TfSmallVector
136 ///
137 /// This is a small-vector class with local storage optimization, the local
138 /// storage can be specified via a template parameter, and expresses the
139 /// number of entries the container can store locally.
140 ///
141 /// In addition to the local storage optimization, this vector is also
142 /// optimized for storing a smaller number of entries on the heap: It features
143 /// a reduced memory footprint (minimum 16 bytes) by limiting max_size() to
144 /// 2^32, which should still be more than enough for most use cases where a
145 /// small-vector is advantageous.
146 ///
147 /// TfSmallVector mimics the std::vector API, and can thus be easily used as a
148 /// drop-in replacement where appropriate. Note, however, that not all the
149 /// methods on std::vector are implemented here, and that TfSmallVector may
150 /// have methods in addition to those that you would find on std::vector.
151 ///
152 /// Note that a TfSmallVector that has grown beyond its local storage, will
153 /// NOT move its entries back into the local storage once it shrinks back to N.
154 ///
155 template <typename T, uint32_t N>
157 {
158 public:
159 
160  /// XXX: Functionality currently missing, and which we would like to add as
161  /// needed:
162  /// - emplace
163  /// - shrink_to_fit
164  /// - shrink_to_local / shrink_to_internal (or similar, free standing
165  /// function)
166 
167  /// \name Relevant Typedefs.
168  /// @{
169 
170  typedef T value_type;
171  typedef T& reference;
172  typedef const T& const_reference;
173 
174  /// }@
175 
176  /// \name Iterator Support.
177  /// @{
178 
179  using iterator = T*;
180  using const_iterator = const T*;
181  typedef std::reverse_iterator<iterator> reverse_iterator;
182  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
183 
184  /// }@
185 
186  /// Default constructor.
187  ///
188  TfSmallVector() : _size(0), _capacity(N) {}
189 
190  /// Construct a vector holding \p n value-initialized elements.
191  ///
193  _capacity(N) {
194  _InitStorage(n);
195  value_type *d = data();
196  for (size_type i = 0; i < n; ++i) {
197  new (d + i) value_type();
198  }
199  }
200 
201  /// Construct a vector holding \p n copies of \p v.
202  ///
204  _capacity(N) {
205  _InitStorage(n);
206  std::uninitialized_fill_n(data(), n, v);
207  }
208 
209  /// Construct a vector holding \p n default-initialized elements.
210  ///
213  _capacity(N) {
214  _InitStorage(n);
215  value_type *d = data();
216  for (size_type i = 0; i < n; ++i) {
217  new (d + i) value_type;
218  }
219  }
220 
221  /// Copy constructor.
222  ///
223  TfSmallVector(const TfSmallVector &rhs) : _capacity(N) {
224  _InitStorage(rhs.size());
225  std::uninitialized_copy(rhs.begin(), rhs.end(), begin());
226  }
227 
228  /// Move constructor.
229  ///
230  TfSmallVector(TfSmallVector &&rhs) : _size(0), _capacity(N) {
231  // If rhs can not be stored locally, take rhs's remote storage and
232  // reset rhs to empty.
233  if (rhs.size() > N) {
234  _SetRemoteStorage(rhs._GetRemoteStorage());
235  std::swap(_capacity, rhs._capacity);
236  }
237 
238  // If rhs is stored locally, it's faster to simply move the entries
239  // into this vector's storage, destruct the entries at rhs, and swap
240  // sizes. Note that capacities will be the same in this case, so no
241  // need to swap those.
242  else {
243  _UninitializedMove(rhs.begin(), rhs.end(), begin());
244  rhs._Destruct();
245  }
246  std::swap(_size, rhs._size);
247  }
248 
249  /// Construct a new vector from initializer list
250  TfSmallVector(std::initializer_list<T> values)
251  : TfSmallVector(values.begin(), values.end()) {
252  }
253 
254  /// Creates a new vector containing copies of the data between
255  /// \p first and \p last.
256  template<typename ForwardIterator,
257  typename = _EnableIfForwardIterator<ForwardIterator>>
258  TfSmallVector(ForwardIterator first, ForwardIterator last) : _capacity(N)
259  {
260  _InitStorage(std::distance(first, last));
261  std::uninitialized_copy(first, last, begin());
262  }
263 
264  /// Destructor.
265  ///
267  _Destruct();
268  _FreeStorage();
269  }
270 
271  /// Assignment operator.
272  ///
274  if (this != &rhs) {
275  assign(rhs.begin(), rhs.end());
276  }
277  return *this;
278  }
279 
280  /// Move assignment operator.
281  ///
283  if (this != &rhs) {
284  swap(rhs);
285  }
286  return *this;
287  }
288 
289  /// Replace existing contents with the contents of \p ilist.
290  ///
291  TfSmallVector &operator=(std::initializer_list<T> ilist) {
292  assign(ilist.begin(), ilist.end());
293  return *this;
294  }
295 
296  /// Swap two vector instances.
297  ///
298  void swap(TfSmallVector &rhs) {
299  // Both this vector and rhs are stored locally.
300  if (_IsLocal() && rhs._IsLocal()) {
301  TfSmallVector *smaller = size() < rhs.size() ? this : &rhs;
302  TfSmallVector *larger = size() < rhs.size() ? &rhs : this;
303 
304  // Swap all the entries up to the size of the smaller vector.
305  std::swap_ranges(smaller->begin(), smaller->end(), larger->begin());
306 
307  // Move the tail end of the entries, and destruct them at the
308  // source vector.
309  for (size_type i = smaller->size(); i < larger->size(); ++i) {
310  _MoveConstruct(smaller->data() + i, &(*larger)[i]);
311  (*larger)[i].~value_type();
312  }
313 
314  // Swap sizes. Capacities are already equal in this case.
315  std::swap(smaller->_size, larger->_size);
316  }
317 
318  // Both this vector and rhs are stored remotely. Simply swap the
319  // pointers, as well as size and capacity.
320  else if (!_IsLocal() && !rhs._IsLocal()) {
321  value_type *tmp = _GetRemoteStorage();
322  _SetRemoteStorage(rhs._GetRemoteStorage());
323  rhs._SetRemoteStorage(tmp);
324 
325  std::swap(_size, rhs._size);
326  std::swap(_capacity, rhs._capacity);
327  }
328 
329  // Either this vector or rhs is stored remotely, whereas the other
330  // one is stored locally.
331  else {
332  TfSmallVector *remote = _IsLocal() ? &rhs : this;
333  TfSmallVector *local = _IsLocal() ? this : &rhs;
334 
335  // Get a pointer to the remote storage. We'll be overwriting the
336  // pointer value below, so gotta retain it first.
337  value_type *remoteStorage = remote->_GetStorage();
338 
339  // Move all the entries from the vector with the local storage, to
340  // the other vector's local storage. This will overwrite the pointer
341  // to the other vectors remote storage. Note that we will have to
342  // also destruct the elements at the source's local storage. The
343  // source will become the one with the remote storage, so those
344  // entries will be essentially freed.
345  for (size_type i = 0; i < local->size(); ++i) {
346  _MoveConstruct(remote->_GetLocalStorage() + i, &(*local)[i]);
347  (*local)[i].~value_type();
348  }
349 
350  // Swap the remote storage into the vector which previously had the
351  // local storage. It's been properly cleaned up now.
352  local->_SetRemoteStorage(remoteStorage);
353 
354  // Swap sizes and capacities. Easy peasy.
355  std::swap(remote->_size, local->_size);
356  std::swap(remote->_capacity, local->_capacity);
357  }
358 
359  }
360 
361  /// Insert an rvalue-reference entry at the given iterator position.
362  ///
364  return _Insert(it, std::move(v));
365  }
366 
367  /// Insert an entry at the given iterator.
368  ///
370  return _Insert(it, v);
371  }
372 
373  /// Erase an entry at the given iterator.
374  ///
376  return erase(it, it + 1);
377  }
378 
379  /// Erase entries between [ \p first, \p last ) from the vector.
380  ///
382  value_type *p = const_cast<value_type *>(&*it);
383  value_type *q = const_cast<value_type *>(&*last);
384 
385  // If we're not removing anything, bail out.
386  if (p == q) {
387  return iterator(p);
388  }
389 
390  const size_type num = std::distance(p, q);
391 
392  // Move entries starting at last, down a few slots to starting a it.
393  value_type *e = data() + size();
394  std::move(q, e, p);
395 
396  // Destruct all the freed up slots at the end of the vector.
397  for (value_type *i = (e - num); i != e; ++i) {
398  i->~value_type();
399  }
400 
401  // Bump down the size.
402  _size -= num;
403 
404  // Return an iterator to the next entry.
405  return iterator(p);
406  }
407 
408  /// Reserve storage for \p newCapacity entries.
409  ///
410  void reserve(size_type newCapacity) {
411  // Only reserve storage if the new capacity would grow past the local
412  // storage, or the currently allocated storage. We'll grow to
413  // accommodate exactly newCapacity entries.
414  if (newCapacity > capacity()) {
415  _GrowStorage(newCapacity);
416  }
417  }
418 
419  /// Resize the vector to \p newSize and insert copies of \v.
420  ///
421  void resize(size_type newSize, const value_type &v = value_type()) {
422  // If the new size is smaller than the current size, let go of some
423  // entries at the tail.
424  if (newSize < size()) {
425  erase(const_iterator(data() + newSize),
426  const_iterator(data() + size()));
427  }
428 
429  // Otherwise, lets grow and fill: Reserve some storage, fill the tail
430  // end with copies of v, and update the new size.
431  else if (newSize > size()) {
432  reserve(newSize);
433  std::uninitialized_fill(data() + size(), data() + newSize, v);
434  _size = newSize;
435  }
436  }
437 
438  /// Clear the entries in the vector. Does not let go of the underpinning
439  /// storage.
440  ///
441  void clear() {
442  _Destruct();
443  _size = 0;
444  }
445 
446  /// Clears any previously held entries, and copies entries between
447  /// [ \p first, \p last ) to this vector.
448  ///
449  template<typename ForwardIterator,
450  typename = _EnableIfForwardIterator<ForwardIterator>>
451  void assign(ForwardIterator first, ForwardIterator last) {
452  clear();
453  const size_type newSize = std::distance(first, last);
454  reserve(newSize);
455  std::uninitialized_copy(first, last, begin());
456  _size = newSize;
457  }
458 
459  /// Replace existing contents with the contents of \p ilist.
460  ///
461  void assign(std::initializer_list<T> ilist) {
462  assign(ilist.begin(), ilist.end());
463  }
464 
465  /// Emplace an entry at the back of the vector.
466  ///
467  template < typename... Args >
468  void emplace_back(Args&&... args) {
469  if (size() == capacity()) {
470  _GrowStorage(_NextCapacity());
471  }
472  new (data() + size()) value_type(std::forward<Args>(args)...);
473  _size += 1;
474  }
475 
476  /// Copy an entry to the back of the vector,
477  ///
478  void push_back(const value_type &v) {
479  emplace_back(v);
480  }
481 
482  /// Move an entry to the back of the vector.
483  ///
485  emplace_back(std::move(v));
486  }
487 
488  /// Copy the range denoted by [\p first, \p last) into this vector
489  /// before \p pos.
490  ///
491  template <typename ForwardIterator>
492  void insert(iterator pos, ForwardIterator first, ForwardIterator last)
493  {
494  static_assert(
495  std::is_convertible<
496  typename std::iterator_traits<ForwardIterator>::iterator_category,
497  std::forward_iterator_tag>::value,
498  "Input Iterators not supported.");
499 
500  // Check for the insert-at-end special case as the very first thing so
501  // that we give the compiler the best possible opportunity to
502  // eliminate the general case code.
503  const bool insertAtEnd = pos == end();
504 
505  const long numNewElems = std::distance(first, last);
506  const size_type neededCapacity = size() + numNewElems;
507  const size_type nextCapacity =
508  std::max(_NextCapacity(), neededCapacity);
509 
510  // Insertions at the end would be handled correctly by the code below
511  // without this special case. However, insert(end(), f, l) is an
512  // extremely common operation so we provide this fast path both to
513  // avoid unneeded work and to make it easier for the compiler to
514  // eliminate dead code when pos == end().
515  if (insertAtEnd) {
516  // The reallocation here is not a simple reserve. We want to grow
517  // the storage only when there are too many new elements but the
518  // desired size is based on the growth factor.
519  if (neededCapacity > capacity()) {
520  _GrowStorage(nextCapacity);
521  }
522  std::uninitialized_copy(first, last, end());
523  _size += numNewElems;
524  return;
525  }
526 
527  if (neededCapacity > capacity()) {
528  // Because we need to realloc, we can do the insertion by copying
529  // each range, [begin(), pos), [first, last), [pos, end()), into
530  // the new storage.
531 
532  const size_type posI = std::distance(begin(), pos);
533  value_type *newStorage = _Allocate(nextCapacity);
534 
535  iterator newPrefixBegin = iterator(newStorage);
536  iterator newPos = newPrefixBegin + posI;
537  iterator newSuffixBegin = newPos + numNewElems;
538  _UninitializedMove(begin(), pos, newPrefixBegin);
539  std::uninitialized_copy(first, last, newPos);
540  _UninitializedMove(pos, end(), newSuffixBegin);
541 
542  // Destroy old data and set up this new buffer.
543  _Destruct();
544  _FreeStorage();
545  _SetRemoteStorage(newStorage);
546  _capacity = nextCapacity;
547  }
548  else {
549  // Insert in-place requires handling four ranges.
550  //
551  // For both the range-to-move [pos, end()) and the range-to-insert
552  // [first, last), there are two subranges: the subrange to copy
553  // and the subrange to uinitialized_copy. Note that only three of
554  // these ranges may be non-empty: either there is a non-empty
555  // prefix of [pos, end()) that needs to be copied over existing
556  // elements or there is a non-empty suffix of [first, last) that
557  // needs to be placed in uninitialized storage.
558 
559  const long numMoveElems = std::distance(pos, end());
560  const long numUninitMoves = std::min(numNewElems, numMoveElems);
561  const long numInitMoves = numMoveElems - numUninitMoves;
562  const long numUninitNews = numNewElems - numUninitMoves;
563  const long numInitNews = numNewElems - numUninitNews;
564 
565  // Move our existing elements out of the way of new elements.
566  iterator umSrc = pos + numInitMoves;
567  iterator umDst = end() + numUninitNews;
568  _UninitializedMove(umSrc, end(), umDst);
569  std::copy_backward(pos, umSrc, umDst);
570 
571  // Copy new elements into place.
572  for (long i=0; i<numInitNews; ++i, ++first, ++pos) {
573  *pos = *first;
574  }
575  std::uninitialized_copy(first, last, end());
576  }
577 
578  _size += numNewElems;
579  }
580 
581  /// Insert elements from \p ilist starting at position \p pos.
582  ///
583  void insert(iterator pos, std::initializer_list<T> ilist) {
584  insert(pos, ilist.begin(), ilist.end());
585  }
586 
587  /// Remove the entry at the back of the vector.
588  ///
589  void pop_back() {
590  back().~value_type();
591  _size -= 1;
592  }
593 
594  /// Returns the current size of the vector.
595  ///
596  size_type size() const {
597  return _size;
598  }
599 
600  /// Returns the maximum size of this vector.
601  ///
602  static constexpr size_type max_size() {
604  }
605 
606  /// Returns \c true if this vector is empty.
607  ///
608  bool empty() const {
609  return size() == 0;
610  }
611 
612  /// Returns the current capacity of this vector. Note that if the returned
613  /// value is <= N, it does NOT mean the storage is local. A vector that has
614  /// previously grown beyond its local storage, will not move entries back to
615  /// the local storage once it shrinks to N.
616  ///
617  size_type capacity() const {
618  return _capacity;
619  }
620 
621  /// Returns the local storage capacity. The vector uses its local storage
622  /// if capacity() <= internal_capacity().
623  /// This method mimics the boost::container::small_vector interface.
624  ///
625  static constexpr size_type internal_capacity() {
626  return N;
627  }
628 
629  /// \name Returns an iterator to the beginning of the vector.
630  /// @{
631 
633  return iterator(_GetStorage());
634  }
635 
637  return const_iterator(_GetStorage());
638  }
639 
641  return begin();
642  }
643 
644  /// @}
645 
646  /// \name Returns an iterator to the end of the vector.
647  /// @{
648 
650  return iterator(_GetStorage() + size());
651  }
652 
653  const_iterator end() const {
654  return const_iterator(_GetStorage() + size());
655  }
656 
658  return end();
659  }
660 
661  /// @}
662 
663  /// \name Returns a reverse iterator to the beginning of the vector.
664  /// @{
665 
667  return reverse_iterator(end());
668  }
669 
671  return const_reverse_iterator(end());
672  }
673 
675  return rbegin();
676  }
677 
678  /// @}
679 
680  /// \name Returns a reverse iterator to the end of the vector.
681  /// @{
682 
684  return reverse_iterator(begin());
685  }
686 
688  return const_reverse_iterator(begin());
689  }
690 
692  return rend();
693  }
694 
695  /// @}
696 
697  /// Returns the first element in the vector.
698  ///
700  return *begin();
701  }
702 
703  /// Returns the first element in the vector.
704  ///
706  return *begin();
707  }
708 
709  /// Returns the last element in the vector.
710  ///
712  return data()[size() - 1];
713  }
714 
715  /// Returns the last elements in the vector.
716  ///
718  return data()[size() - 1];
719  }
720 
721  /// Access the specified element.
722  ///
724  return data()[i];
725  }
726 
727  /// Access the specified element.
728  ///
730  return data()[i];
731  }
732 
733  /// Direct access to the underlying array.
734  ///
736  return _GetStorage();
737  }
738 
739  /// Direct access to the underlying array.
740  ///
741  const value_type *data() const {
742  return _GetStorage();
743  }
744 
745  /// Lexicographically compares the elements in the vectors for equality.
746  ///
747  bool operator==(const TfSmallVector &rhs) const {
748  return size() == rhs.size() && std::equal(begin(), end(), rhs.begin());
749  }
750 
751  /// Lexicographically compares the elements in the vectors for inequality.
752  ///
753  bool operator!=(const TfSmallVector &rhs) const {
754  return !operator==(rhs);
755  }
756 
757 private:
758 
759  // Raw data access.
760  value_type *_GetLocalStorage() {
761  return static_cast<value_type *>(_data.GetLocalStorage());
762  }
763  const value_type *_GetLocalStorage() const {
764  return static_cast<const value_type *>(_data.GetLocalStorage());
765  }
766 
767  value_type *_GetRemoteStorage() {
768  return static_cast<value_type *>(_data.GetRemoteStorage());
769  }
770  const value_type *_GetRemoteStorage() const {
771  return static_cast<const value_type *>(_data.GetRemoteStorage());
772  }
773 
774  void _SetRemoteStorage(value_type *p) {
775  _data.SetRemoteStorage(static_cast<void *>(p));
776  }
777 
778  // Returns true if the local storage is used.
779  bool _IsLocal() const {
780  return _capacity <= N;
781  }
782 
783  // Return a pointer to the storage, which is either local or remote
784  // depending on the current capacity.
785  value_type *_GetStorage() {
786  return _IsLocal() ? _GetLocalStorage() : _GetRemoteStorage();
787  }
788 
789  // Return a const pointer to the storage, which is either local or remote
790  // depending on the current capacity.
791  const value_type *_GetStorage() const {
792  return _IsLocal() ? _GetLocalStorage() : _GetRemoteStorage();
793  }
794 
795  // Free the remotely allocated storage.
796  void _FreeStorage() {
797  if (!_IsLocal()) {
798  free(_GetRemoteStorage());
799  }
800  }
801 
802  // Destructs all the elements stored in this vector.
803  void _Destruct() {
804  value_type *b = data();
805  value_type *e = b + size();
806  for (value_type *p = b; p != e; ++p) {
807  p->~value_type();
808  }
809  }
810 
811  // Allocate a buffer on the heap.
812  static value_type *_Allocate(size_type size) {
813  return static_cast<value_type *>(malloc(sizeof(value_type) * size));
814  }
815 
816  // Initialize the vector with new storage, updating the capacity and size.
817  void _InitStorage(size_type size) {
818  if (size > capacity()) {
819  _SetRemoteStorage(_Allocate(size));
820  _capacity = size;
821  }
822 #if defined(ARCH_COMPILER_GCC) && ARCH_COMPILER_GCC_MAJOR < 11
823  else if constexpr (!_data.HasLocal) {
824  // When there's no local storage and we're not allocating remote
825  // storage, initialize the remote storage pointer to avoid
826  // spurious compiler warnings about maybe-uninitialized values
827  // being used.
828 
829  // This clause can be removed upon upgrade to gcc 11 as
830  // the new compiler no longer generates this warning in this case.
831  _data.SetRemoteStorage(nullptr);
832  }
833 #endif
834  _size = size;
835  }
836 
837  // Grow the storage to be able to accommodate newCapacity entries. This
838  // always allocates remote storage.
839  void _GrowStorage(const size_type newCapacity) {
840  value_type *newStorage = _Allocate(newCapacity);
841  _UninitializedMove(begin(), end(), iterator(newStorage));
842  _Destruct();
843  _FreeStorage();
844  _SetRemoteStorage(newStorage);
845  _capacity = newCapacity;
846  }
847 
848  // Returns the next capacity to use for vector growth. The growth factor
849  // here is 1.5. A constant 1 is added so that we do not have to special
850  // case initial capacities of 0 and 1.
851  size_type _NextCapacity() const {
852  const size_type cap = capacity();
853  return cap + (cap / 2) + 1;
854  }
855 
856  // Insert the value v at iterator it. We use this method that takes a
857  // universal reference to de-duplicate the logic required for the insert
858  // overloads, one taking an rvalue reference, and the other one taking a
859  // const reference. This way, we can take the most optimal code path (
860  // move, or copy without making redundant copies) based on whether v is
861  // a rvalue reference or const reference.
862  template < typename U >
863  iterator _Insert(const_iterator it, U &&v) {
864  value_type *newEntry;
865 
866  // If the iterator points to the end, simply push back.
867  if (it == end()) {
868  push_back(std::forward<U>(v));
869  return end() - 1;
870  }
871 
872  // Grow the remote storage, if we need to. This invalidates iterators,
873  // so special care must be taken in order to return a new, valid
874  // iterator.
875  else if (size() == capacity()) {
876  const size_type newCapacity = _NextCapacity();
877  value_type *newStorage = _Allocate(newCapacity);
878 
879  value_type *i = const_cast<value_type *>(&*it);
880  value_type *curData = data();
881  newEntry = _UninitializedMove(curData, i, newStorage);
882 
883  new (newEntry) value_type(std::forward<U>(v));
884 
885  _UninitializedMove(i, curData + size(), newEntry + 1);
886 
887  _Destruct();
888  _FreeStorage();
889 
890  _SetRemoteStorage(newStorage);
891  _capacity = newCapacity;
892  }
893 
894  // Our current capacity is big enough to allow us to simply shift
895  // elements up one slot and insert v at it.
896  else {
897  // Move all the elements after it up by one slot.
898  newEntry = const_cast<value_type *>(&*it);
899  value_type *last = const_cast<value_type *>(&back());
900  new (data() + size()) value_type(std::move(*last));
901  std::move_backward(newEntry, last, last + 1);
902 
903  // Move v into the slot at the supplied iterator position.
904  newEntry->~value_type();
905  new (newEntry) value_type(std::forward<U>(v));
906  }
907 
908  // Bump size and return an iterator to the newly inserted entry.
909  ++_size;
910  return iterator(newEntry);
911  }
912 
913  // The vector storage, which is a union of the local storage and a pointer
914  // to the heap memory, if allocated.
915  _Data<value_type, N> _data;
916 
917  // The current size of the vector, i.e. how many entries it contains.
918  _SizeMemberType _size;
919 
920  // The current capacity of the vector, i.e. how big the currently allocated
921  // storage space is.
922  _SizeMemberType _capacity;
923 };
924 
925 ////////////////////////////////////////////////////////////////////////////////
926 
927 template < typename T, uint32_t N >
929 {
930  a.swap(b);
931 }
932 
933 ////////////////////////////////////////////////////////////////////////////////
934 
936 
937 #endif
void swap(ArAssetInfo &lhs, ArAssetInfo &rhs)
Definition: assetInfo.h:57
const_reference operator[](size_type i) const
Definition: smallVector.h:729
size_type capacity() const
Definition: smallVector.h:617
GLint first
Definition: glcorearb.h:405
const_reverse_iterator rend() const
Definition: smallVector.h:687
typename std::enable_if< B, T >::type enable_if_t
Define Imath::enable_if_t to be std for C++14, equivalent for C++11.
const void * GetRemoteStorage() const
Definition: smallVector.h:117
void push_back(const value_type &v)
Definition: smallVector.h:478
void insert(iterator pos, std::initializer_list< T > ilist)
Definition: smallVector.h:583
void resize(size_type newSize, const value_type &v=value_type())
Definition: smallVector.h:421
TfSmallVector()
}@
Definition: smallVector.h:188
reverse_iterator rend()
Definition: smallVector.h:683
reverse_iterator rbegin()
Definition: smallVector.h:666
bool operator==(const TfSmallVector &rhs) const
Definition: smallVector.h:747
reference back()
Definition: smallVector.h:711
iterator end()
Definition: smallVector.h:649
const_iterator cbegin() const
Definition: smallVector.h:640
void swap(UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > &a, UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > &b)
Definition: UT_ArraySet.h:1699
const GLdouble * v
Definition: glcorearb.h:837
void reserve(size_type newCapacity)
Definition: smallVector.h:410
static Iterator _UninitializedMove(Iterator first, Iterator last, Iterator dest)
Definition: smallVector.h:82
GLsizei const GLfloat * value
Definition: glcorearb.h:824
std::ptrdiff_t difference_type
Definition: smallVector.h:51
static void _MoveConstruct(U *p, U *src)
Definition: smallVector.h:93
std::uint32_t _SizeMemberType
Definition: smallVector.h:38
TfSmallVector(std::initializer_list< T > values)
Construct a new vector from initializer list.
Definition: smallVector.h:250
static constexpr size_type max_size()
Definition: smallVector.h:602
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1222
TfSmallVector(size_type n, const value_type &v)
Definition: smallVector.h:203
size_type size() const
Definition: smallVector.h:596
reference front()
Definition: smallVector.h:699
bool empty() const
Definition: smallVector.h:608
IMATH_HOSTDEVICE constexpr bool equal(T1 a, T2 b, T3 t) IMATH_NOEXCEPT
Definition: ImathFun.h:105
ImageBuf OIIO_API min(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
GLdouble GLdouble GLdouble q
Definition: glad.h:2445
iterator erase(const_iterator it, const_iterator last)
Definition: smallVector.h:381
const_reverse_iterator crbegin() const
Definition: smallVector.h:674
static constexpr size_type internal_capacity()
Definition: smallVector.h:625
const_iterator begin() const
Definition: smallVector.h:636
bool operator!=(const TfSmallVector &rhs) const
Definition: smallVector.h:753
GLdouble n
Definition: glcorearb.h:2008
iterator insert(const_iterator it, const value_type &v)
Definition: smallVector.h:369
TfSmallVector & operator=(std::initializer_list< T > ilist)
Definition: smallVector.h:291
iterator begin()
Definition: smallVector.h:632
GLuint GLuint end
Definition: glcorearb.h:475
TfSmallVector & operator=(const TfSmallVector &rhs)
Definition: smallVector.h:273
void emplace_back(Args &&...args)
Definition: smallVector.h:468
TfSmallVector & operator=(TfSmallVector &&rhs)
Definition: smallVector.h:282
TfSmallVector(size_type n)
Definition: smallVector.h:192
const_iterator end() const
Definition: smallVector.h:653
TfSmallVector(size_type n, DefaultInitTag)
Definition: smallVector.h:212
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1222
std::enable_if_t< std::is_convertible_v< typename std::iterator_traits< _ForwardIterator >::iterator_category, std::forward_iterator_tag > > _EnableIfForwardIterator
Definition: smallVector.h:77
void push_back(value_type &&v)
Definition: smallVector.h:484
__hostdev__ uint64_t last(uint32_t i) const
Definition: NanoVDB.h:5976
GLsizeiptr size
Definition: glcorearb.h:664
iterator erase(const_iterator it)
Definition: smallVector.h:375
PXR_NAMESPACE_CLOSE_SCOPE PXR_NAMESPACE_OPEN_SCOPE
Definition: path.h:1425
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: smallVector.h:182
GLenum GLsizei GLsizei GLint * values
Definition: glcorearb.h:1602
void insert(iterator pos, ForwardIterator first, ForwardIterator last)
Definition: smallVector.h:492
const_reverse_iterator crend() const
Definition: smallVector.h:691
iterator insert(const_iterator it, value_type &&v)
Definition: smallVector.h:363
ImageBuf OIIO_API max(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
void assign(std::initializer_list< T > ilist)
Definition: smallVector.h:461
#define PXR_NAMESPACE_CLOSE_SCOPE
Definition: pxr.h:74
GA_API const UT_StringHolder N
**If you just want to fire and args
Definition: thread.h:618
TfSmallVector(ForwardIterator first, ForwardIterator last)
Definition: smallVector.h:258
const_reference front() const
Definition: smallVector.h:705
TfSmallVector(const TfSmallVector &rhs)
Definition: smallVector.h:223
const_iterator cend() const
Definition: smallVector.h:657
TfSmallVector(TfSmallVector &&rhs)
Definition: smallVector.h:230
const void * GetLocalStorage() const
Definition: smallVector.h:110
void assign(ForwardIterator first, ForwardIterator last)
Definition: smallVector.h:451
const_reference back() const
Definition: smallVector.h:717
std::size_t size_type
Definition: smallVector.h:50
void pop_back()
Definition: smallVector.h:589
SIM_API const UT_StringHolder distance
const_reverse_iterator rbegin() const
Definition: smallVector.h:670
const T & const_reference
Definition: smallVector.h:172
reference operator[](size_type i)
Definition: smallVector.h:723
static constexpr bool HasLocal
Definition: smallVector.h:105
void swap(TfSmallVector &rhs)
Definition: smallVector.h:298
std::reverse_iterator< iterator > reverse_iterator
Definition: smallVector.h:181
const value_type * data() const
Definition: smallVector.h:741
GLenum src
Definition: glcorearb.h:1793
static constexpr size_type ComputeSerendipitousLocalCapacity()
Definition: smallVector.h:58
value_type * data()
Definition: smallVector.h:735