7#ifndef PXR_BASE_TF_SMALL_VECTOR_H
8#define PXR_BASE_TF_SMALL_VECTOR_H
15#include "pxr/base/arch/defines.h"
21#include <initializer_list>
28PXR_NAMESPACE_OPEN_SCOPE
32class TfSmallVectorBase
38 using _SizeMemberType = std::uint32_t;
41 template <
size_t Size,
size_t Align,
size_t NumLocal>
46 template <
class ValueType,
size_t NumLocal>
47 using _Data = _DataUnion<
sizeof(ValueType),
alignof(ValueType), NumLocal>;
50 using size_type = std::size_t;
51 using difference_type = std::ptrdiff_t;
58 static constexpr size_type ComputeSerendipitousLocalCapacity() {
59 return (
alignof(U) <=
alignof(_Data<U, 0>))
60 ?
sizeof(_Data<U, 0>) /
sizeof(U)
69 template<
typename _ForwardIterator>
70 using _EnableIfForwardIterator =
72 std::is_convertible_v<
73 typename std::iterator_traits<
74 _ForwardIterator>::iterator_category,
75 std::forward_iterator_tag
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),
93 static void _MoveConstruct(U *p, U *src) {
94 new (p) U(std::move(*src));
100 template <
size_t Size,
size_t Align,
size_t NumLocal>
105 static constexpr bool HasLocal = NumLocal != 0;
107 void *GetLocalStorage() {
108 return HasLocal ? _local :
nullptr;
110 const void *GetLocalStorage()
const {
111 return HasLocal ? _local :
nullptr;
114 void *GetRemoteStorage() {
117 const void *GetRemoteStorage()
const {
121 void SetRemoteStorage(
void *p) {
128 alignas(NumLocal == 0 ? std::alignment_of_v<void *> : Align)
129 char _local[std::max<size_t>(Size * NumLocal,
sizeof(_remote))];
155template <
typename T, u
int32_t N>
170 typedef T value_type;
171 typedef T& reference;
172 typedef const T& const_reference;
180 using const_iterator =
const T*;
181 typedef std::reverse_iterator<iterator> reverse_iterator;
182 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
195 value_type *d =
data();
196 for (size_type i = 0; i < n; ++i) {
197 new (d + i) value_type();
206 std::uninitialized_fill_n(
data(), n, v);
215 value_type *d =
data();
216 for (size_type i = 0; i < n; ++i) {
217 new (d + i) value_type;
224 _InitStorage(rhs.
size());
225 std::uninitialized_copy(rhs.begin(), rhs.end(), begin());
233 if (rhs.size() > N) {
234 _SetRemoteStorage(rhs._GetRemoteStorage());
235 std::swap(_capacity, rhs._capacity);
243 _UninitializedMove(rhs.begin(), rhs.end(), begin());
246 std::swap(_size, rhs._size);
256 template<
typename ForwardIterator,
257 typename = _EnableIfForwardIterator<ForwardIterator>>
260 _InitStorage(std::distance(first, last));
261 std::uninitialized_copy(first, last, begin());
275 assign(rhs.begin(), rhs.end());
292 assign(ilist.begin(), ilist.end());
300 if (_IsLocal() && rhs._IsLocal()) {
305 std::swap_ranges(smaller->begin(), smaller->end(), larger->begin());
309 for (size_type i = smaller->
size(); i < larger->
size(); ++i) {
310 _MoveConstruct(smaller->
data() + i, &(*larger)[i]);
311 (*larger)[i].~value_type();
315 std::swap(smaller->_size, larger->_size);
320 else if (!_IsLocal() && !rhs._IsLocal()) {
321 value_type *tmp = _GetRemoteStorage();
322 _SetRemoteStorage(rhs._GetRemoteStorage());
323 rhs._SetRemoteStorage(tmp);
325 std::swap(_size, rhs._size);
326 std::swap(_capacity, rhs._capacity);
337 value_type *remoteStorage = remote->_GetStorage();
345 for (size_type i = 0; i < local->
size(); ++i) {
346 _MoveConstruct(remote->_GetLocalStorage() + i, &(*local)[i]);
347 (*local)[i].~value_type();
352 local->_SetRemoteStorage(remoteStorage);
355 std::swap(remote->_size, local->_size);
356 std::swap(remote->_capacity, local->_capacity);
363 iterator
insert(const_iterator it, value_type &&v) {
364 return _Insert(it, std::move(v));
369 iterator
insert(const_iterator it,
const value_type &v) {
370 return _Insert(it, v);
376 return erase(it, it + 1);
381 iterator
erase(const_iterator it, const_iterator last) {
382 value_type *p =
const_cast<value_type *
>(&*it);
383 value_type *q =
const_cast<value_type *
>(&*last);
390 const size_type num = std::distance(p, q);
397 for (value_type *i = (e - num); i != e; ++i) {
415 _GrowStorage(newCapacity);
421 void resize(size_type newSize,
const value_type &v = value_type()) {
424 if (newSize <
size()) {
431 else if (newSize >
size()) {
433 std::uninitialized_fill(
data() +
size(),
data() + newSize, v);
449 template<
typename ForwardIterator,
450 typename = _EnableIfForwardIterator<ForwardIterator>>
451 void assign(ForwardIterator first, ForwardIterator last) {
453 const size_type newSize = std::distance(first, last);
455 std::uninitialized_copy(first, last, begin());
461 void assign(std::initializer_list<T> ilist) {
462 assign(ilist.begin(), ilist.end());
467 template <
typename... Args >
470 _GrowStorage(_NextCapacity());
472 new (
data() +
size()) value_type(std::forward<Args>(args)...);
491 template <
typename ForwardIterator>
492 void insert(iterator pos, ForwardIterator first, ForwardIterator last)
496 typename std::iterator_traits<ForwardIterator>::iterator_category,
497 std::forward_iterator_tag>::value,
498 "Input Iterators not supported.");
503 const bool insertAtEnd = pos == end();
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);
520 _GrowStorage(nextCapacity);
522 std::uninitialized_copy(first, last, end());
523 _size += numNewElems;
532 const size_type posI = std::distance(begin(), pos);
533 value_type *newStorage = _Allocate(nextCapacity);
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);
545 _SetRemoteStorage(newStorage);
546 _capacity = nextCapacity;
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;
566 iterator umSrc = pos + numInitMoves;
567 iterator umDst = end() + numUninitNews;
568 _UninitializedMove(umSrc, end(), umDst);
569 std::copy_backward(pos, umSrc, umDst);
572 for (
long i=0; i<numInitNews; ++i, ++first, ++pos) {
575 std::uninitialized_copy(first, last, end());
578 _size += numNewElems;
583 void insert(iterator pos, std::initializer_list<T> ilist) {
584 insert(pos, ilist.begin(), ilist.end());
590 back().~value_type();
603 return std::numeric_limits<_SizeMemberType>::max();
633 return iterator(_GetStorage());
636 const_iterator begin()
const {
637 return const_iterator(_GetStorage());
640 const_iterator cbegin()
const {
650 return iterator(_GetStorage() +
size());
653 const_iterator end()
const {
654 return const_iterator(_GetStorage() +
size());
657 const_iterator cend()
const {
666 reverse_iterator rbegin() {
667 return reverse_iterator(end());
670 const_reverse_iterator rbegin()
const {
671 return const_reverse_iterator(end());
674 const_reverse_iterator crbegin()
const {
683 reverse_iterator rend() {
684 return reverse_iterator(begin());
687 const_reverse_iterator rend()
const {
688 return const_reverse_iterator(begin());
691 const_reverse_iterator crend()
const {
736 return _GetStorage();
741 const value_type *
data()
const {
742 return _GetStorage();
748 return size() == rhs.
size() && std::equal(begin(), end(), rhs.begin());
760 value_type *_GetLocalStorage() {
761 return static_cast<value_type *
>(_data.GetLocalStorage());
763 const value_type *_GetLocalStorage()
const {
764 return static_cast<const value_type *
>(_data.GetLocalStorage());
767 value_type *_GetRemoteStorage() {
768 return static_cast<value_type *
>(_data.GetRemoteStorage());
770 const value_type *_GetRemoteStorage()
const {
771 return static_cast<const value_type *
>(_data.GetRemoteStorage());
774 void _SetRemoteStorage(value_type *p) {
775 _data.SetRemoteStorage(
static_cast<void *
>(p));
779 bool _IsLocal()
const {
780 return _capacity <= N;
785 value_type *_GetStorage() {
786 return _IsLocal() ? _GetLocalStorage() : _GetRemoteStorage();
791 const value_type *_GetStorage()
const {
792 return _IsLocal() ? _GetLocalStorage() : _GetRemoteStorage();
796 void _FreeStorage() {
798 free(_GetRemoteStorage());
804 value_type *b =
data();
805 value_type *e = b +
size();
806 for (value_type *p = b; p != e; ++p) {
812 static value_type *_Allocate(size_type
size) {
813 return static_cast<value_type *
>(malloc(
sizeof(value_type) *
size));
817 void _InitStorage(size_type
size) {
819 _SetRemoteStorage(_Allocate(
size));
822#if defined(ARCH_COMPILER_GCC) && ARCH_COMPILER_GCC_MAJOR < 11
823 else if constexpr (!_data.HasLocal) {
831 _data.SetRemoteStorage(
nullptr);
839 void _GrowStorage(
const size_type newCapacity) {
840 value_type *newStorage = _Allocate(newCapacity);
841 _UninitializedMove(begin(), end(), iterator(newStorage));
844 _SetRemoteStorage(newStorage);
845 _capacity = newCapacity;
851 size_type _NextCapacity()
const {
853 return cap + (cap / 2) + 1;
862 template <
typename U >
863 iterator _Insert(const_iterator it, U &&v) {
864 value_type *newEntry;
876 const size_type newCapacity = _NextCapacity();
877 value_type *newStorage = _Allocate(newCapacity);
879 value_type *i =
const_cast<value_type *
>(&*it);
880 value_type *curData =
data();
881 newEntry = _UninitializedMove(curData, i, newStorage);
883 new (newEntry) value_type(std::forward<U>(v));
885 _UninitializedMove(i, curData +
size(), newEntry + 1);
890 _SetRemoteStorage(newStorage);
891 _capacity = newCapacity;
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);
904 newEntry->~value_type();
905 new (newEntry) value_type(std::forward<U>(v));
910 return iterator(newEntry);
915 _Data<value_type, N> _data;
918 _SizeMemberType _size;
922 _SizeMemberType _capacity;
927template <
typename T, u
int32_t N >
935PXR_NAMESPACE_CLOSE_SCOPE
This is a small-vector class with local storage optimization, the local storage can be specified via ...
void push_back(const value_type &v)
Copy an entry to the back of the vector,.
void pop_back()
Remove the entry at the back of the vector.
const_reference front() const
Returns the first element in the vector.
reference operator[](size_type i)
Access the specified element.
void assign(ForwardIterator first, ForwardIterator last)
Clears any previously held entries, and copies entries between [ first, last ) to this vector.
void reserve(size_type newCapacity)
Reserve storage for newCapacity entries.
iterator erase(const_iterator it)
Erase an entry at the given iterator.
TfSmallVector(ForwardIterator first, ForwardIterator last)
Creates a new vector containing copies of the data between first and last.
void assign(std::initializer_list< T > ilist)
Replace existing contents with the contents of ilist.
TfSmallVector(std::initializer_list< T > values)
Construct a new vector from initializer list.
~TfSmallVector()
Destructor.
bool operator!=(const TfSmallVector &rhs) const
Lexicographically compares the elements in the vectors for inequality.
size_type size() const
Returns the current size of the vector.
const_reference back() const
Returns the last elements in the vector.
iterator erase(const_iterator it, const_iterator last)
Erase entries between [ first, last ) from the vector.
TfSmallVector & operator=(std::initializer_list< T > ilist)
Replace existing contents with the contents of ilist.
TfSmallVector(size_type n)
Construct a vector holding n value-initialized elements.
bool empty() const
Returns true if this vector is empty.
reference front()
Returns the first element in the vector.
static constexpr size_type max_size()
Returns the maximum size of this vector.
TfSmallVector(size_type n, const value_type &v)
Construct a vector holding n copies of v.
bool operator==(const TfSmallVector &rhs) const
Lexicographically compares the elements in the vectors for equality.
void swap(TfSmallVector &rhs)
Swap two vector instances.
void resize(size_type newSize, const value_type &v=value_type())
Resize the vector to newSize and insert copies of \v.
const value_type * data() const
Direct access to the underlying array.
DefaultInitTag
Construct a vector holding n default-initialized elements.
TfSmallVector(const TfSmallVector &rhs)
Copy constructor.
const_reference operator[](size_type i) const
Access the specified element.
TfSmallVector & operator=(const TfSmallVector &rhs)
Assignment operator.
static constexpr size_type internal_capacity()
Returns the local storage capacity.
void insert(iterator pos, ForwardIterator first, ForwardIterator last)
Copy the range denoted by [first, last) into this vector before pos.
void emplace_back(Args &&... args)
Emplace an entry at the back of the vector.
void clear()
Clear the entries in the vector.
iterator insert(const_iterator it, value_type &&v)
Insert an rvalue-reference entry at the given iterator position.
TfSmallVector & operator=(TfSmallVector &&rhs)
Move assignment operator.
size_type capacity() const
Returns the current capacity of this vector.
TfSmallVector(TfSmallVector &&rhs)
Move constructor.
void insert(iterator pos, std::initializer_list< T > ilist)
Insert elements from ilist starting at position pos.
value_type * data()
Direct access to the underlying array.
iterator insert(const_iterator it, const value_type &v)
Insert an entry at the given iterator.
reference back()
Returns the last element in the vector.
void push_back(value_type &&v)
Move an entry to the back of the vector.