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