smallVector.h

Go to the documentation of this file.

//
// Copyright 2019 Pixar
//
// Licensed under the terms set forth in the LICENSE.txt file available at
// https://openusd.org/license.
//
#ifndef PXR_BASE_TF_SMALL_VECTOR_H
#define PXR_BASE_TF_SMALL_VECTOR_H
 
 
#include "pxr/pxr.h"
 
#include "pxr/base/arch/defines.h"
 
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <initializer_list>
#include <iterator>
#include <limits>
#include <memory>
#include <new>
#include <type_traits>
 
PXR_NAMESPACE_OPEN_SCOPE
 
// Contains parts of the small vector implementation that do not depend on
// *all* of TfSmallVector's template parameters.
class TfSmallVectorBase
{
protected:
    // We present the public size_type and difference_type as std::size_t and
    // std::ptrdiff_t to match std::vector, but internally we store size &
    // capacity as uint32_t.
    using _SizeMemberType = std::uint32_t;
 
    // Union type containing local storage or a pointer to heap storage.
    template <size_t Size, size_t Align, size_t NumLocal>
    union _DataUnion;
 
    // Helper alias to produce the right _DataUnion instantiation for a given
    // ValueType and NumLocal elements.
    template <class ValueType, size_t NumLocal>
    using _Data = _DataUnion<sizeof(ValueType), alignof(ValueType), NumLocal>;
 
public:
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
 
    // Returns the local capacity that may be used without increasing the size
    // of the TfSmallVector.  TfSmallVector<T, N> will never use more local
    // capacity than is specified by N but clients that wish to maximize local
    // occupancy in a generic way can compute N using this function.
    template <typename U>
    static constexpr size_type ComputeSerendipitousLocalCapacity() {
        return (alignof(U) <= alignof(_Data<U, 0>))
            ? sizeof(_Data<U, 0>) / sizeof(U)
            : 0;
    }
 
protected:
 
    // Enabler used to disambiguate the range-based constructor (begin, end)
    // from the n-copies constructor (size_t n, value_type const &value)
    // when the value_type is integral.
    template<typename _ForwardIterator>
    using _EnableIfForwardIterator =
        std::enable_if_t<
            std::is_convertible_v<
                typename std::iterator_traits<
                    _ForwardIterator>::iterator_category,
                std::forward_iterator_tag
                >
        >;
    
    // Invoke std::uninitialized_copy that either moves or copies entries,
    // depending on whether the type is move constructible or not.
    template <typename Iterator>
    static Iterator _UninitializedMove(
        Iterator first, Iterator last, Iterator dest) {
        return std::uninitialized_copy(
            std::make_move_iterator(first),
            std::make_move_iterator(last),
            dest);
    }
 
    // Invokes either the move or copy constructor (via placement new),
    // depending on whether U is move constructible or not.
    template <typename U>
    static void _MoveConstruct(U *p, U *src) {
        new (p) U(std::move(*src));
    }
 
    // The data storage, which is a union of both the local storage, as well
    // as a pointer, holding the address to the remote storage on the heap, if
    // used.
    template <size_t Size, size_t Align, size_t NumLocal>
    union _DataUnion {
    public:
        // XXX: Could in principle assert in calls to GetLocalStorage() when
        // HasLocal is false. Add dependency on tf/diagnostic.h?
        static constexpr bool HasLocal = NumLocal != 0;
 
        void *GetLocalStorage() {
            return HasLocal ? _local : nullptr;
        }
        const void *GetLocalStorage() const {
            return HasLocal ? _local : nullptr;
        }
 
        void *GetRemoteStorage() {
            return _remote;
        }
        const void *GetRemoteStorage() const {
            return _remote;
        }
 
        void SetRemoteStorage(void *p) {
            _remote = p;
        }
    private:
        // Pointer to heap storage.
        void *_remote;
        // Local storage -- min size is sizeof(_remote).
        alignas(NumLocal == 0 ? std::alignment_of_v<void *> : Align)
        char _local[std::max<size_t>(Size * NumLocal, sizeof(_remote))];
    };
};
 
template <typename T, uint32_t N>
class TfSmallVector : public TfSmallVectorBase
{
public:
 
 
    typedef T value_type;
    typedef T& reference;
    typedef const T& const_reference;
 
 
 
    using iterator = T*;
    using const_iterator = const T*;
    typedef std::reverse_iterator<iterator> reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 
 
    TfSmallVector() : _size(0), _capacity(N) {}
 
    explicit TfSmallVector(size_type n) :
        _capacity(N) {
        _InitStorage(n);
        value_type *d = data();
        for (size_type i = 0; i < n; ++i) {
            new (d + i) value_type();
        }
    }
 
    TfSmallVector(size_type n, const value_type &v) :
        _capacity(N) {
        _InitStorage(n);
        std::uninitialized_fill_n(data(), n, v);
    }
 
    enum DefaultInitTag { DefaultInit };
    TfSmallVector(size_type n, DefaultInitTag) :
        _capacity(N) {
        _InitStorage(n);
        value_type *d = data();
        for (size_type i = 0; i < n; ++i) {
            new (d + i) value_type;
        }
    }
 
    TfSmallVector(const TfSmallVector &rhs) : _capacity(N) {
        _InitStorage(rhs.size());
        std::uninitialized_copy(rhs.begin(), rhs.end(), begin());
    }
 
    TfSmallVector(TfSmallVector &&rhs) : _size(0), _capacity(N) {
        // If rhs can not be stored locally, take rhs's remote storage and
        // reset rhs to empty.
        if (rhs.size() > N) {
            _SetRemoteStorage(rhs._GetRemoteStorage());
            std::swap(_capacity, rhs._capacity);
        }
 
        // If rhs is stored locally, it's faster to simply move the entries
        // into this vector's storage, destruct the entries at rhs, and swap
        // sizes. Note that capacities will be the same in this case, so no
        // need to swap those.
        else {
            // If N is 0, this means that rhs is empty and there are no
            // elements that need moving or destroying.
            // This avoids warnings in GCC.
            if constexpr (N > 0) {
                _UninitializedMove(rhs.begin(), rhs.end(), begin());
                rhs._Destruct();
            }
        }
        std::swap(_size, rhs._size);
    }
 
    TfSmallVector(std::initializer_list<T> values)
        : TfSmallVector(values.begin(), values.end()) {
    }
 
    template<typename ForwardIterator,
         typename = _EnableIfForwardIterator<ForwardIterator>>
    TfSmallVector(ForwardIterator first, ForwardIterator last) : _capacity(N)
    {
        _InitStorage(std::distance(first, last));
        std::uninitialized_copy(first, last, begin());
    }
 
    ~TfSmallVector() {
        _Destruct();
        _FreeStorage();
    }
 
    TfSmallVector &operator=(const TfSmallVector &rhs) {
        if (this != &rhs) {
            assign(rhs.begin(), rhs.end());
        }
        return *this;
    }
 
    TfSmallVector &operator=(TfSmallVector &&rhs) {
        if (this != &rhs) {
            swap(rhs);
        }
        return *this;
    }
 
    TfSmallVector &operator=(std::initializer_list<T> ilist) {
        assign(ilist.begin(), ilist.end());
        return *this;
    }
 
    void swap(TfSmallVector &rhs) {
        // Both this vector and rhs are stored locally.
        if (_IsLocal() && rhs._IsLocal()) {
            TfSmallVector *smaller = size() < rhs.size() ? this : &rhs;
            TfSmallVector *larger = size() < rhs.size() ? &rhs : this;
 
            // Swap all the entries up to the size of the smaller vector.
            std::swap_ranges(smaller->begin(), smaller->end(), larger->begin());
 
            // Move the tail end of the entries, and destruct them at the
            // source vector.
            for (size_type i = smaller->size(); i < larger->size(); ++i) {
                _MoveConstruct(smaller->data() + i, &(*larger)[i]);
                (*larger)[i].~value_type();
            }
 
            // Swap sizes. Capacities are already equal in this case.
            std::swap(smaller->_size, larger->_size);
        }
 
        // Both this vector and rhs are stored remotely. Simply swap the
        // pointers, as well as size and capacity.
        else if (!_IsLocal() && !rhs._IsLocal()) {
            value_type *tmp = _GetRemoteStorage();
            _SetRemoteStorage(rhs._GetRemoteStorage());
            rhs._SetRemoteStorage(tmp);
 
            std::swap(_size, rhs._size);
            std::swap(_capacity, rhs._capacity);
        }
 
        // Either this vector or rhs is stored remotely, whereas the other
        // one is stored locally.
        else {
            TfSmallVector *remote = _IsLocal() ? &rhs : this;
            TfSmallVector *local =  _IsLocal() ? this : &rhs;
 
            // Get a pointer to the remote storage. We'll be overwriting the
            // pointer value below, so gotta retain it first.
            value_type *remoteStorage = remote->_GetStorage();
 
            // Move all the entries from the vector with the local storage, to
            // the other vector's local storage. This will overwrite the pointer
            // to the other vectors remote storage. Note that we will have to
            // also destruct the elements at the source's local storage. The
            // source will become the one with the remote storage, so those
            // entries will be essentially freed.
            for (size_type i = 0; i < local->size(); ++i) {
                _MoveConstruct(remote->_GetLocalStorage() + i, &(*local)[i]);
                (*local)[i].~value_type();
            }
 
            // Swap the remote storage into the vector which previously had the
            // local storage. It's been properly cleaned up now.
            local->_SetRemoteStorage(remoteStorage);
 
            // Swap sizes and capacities. Easy peasy. 
            std::swap(remote->_size, local->_size);
            std::swap(remote->_capacity, local->_capacity);
        }
 
    }
 
    iterator insert(const_iterator it, value_type &&v) {
        return _Insert(it, std::move(v));
    }
 
    iterator insert(const_iterator it, const value_type &v) {
        return _Insert(it, v);
    }
 
    iterator erase(const_iterator it) {
        return erase(it, it + 1);
    }
 
    iterator erase(const_iterator it, const_iterator last) {
        value_type *p = const_cast<value_type *>(&*it);
        value_type *q = const_cast<value_type *>(&*last);
 
         // If we're not removing anything, bail out.
        if (p == q) {
            return iterator(p);
        }
   
        const size_type num = std::distance(p, q);
       
        // Move entries starting at last, down a few slots to starting a it.
        value_type *e = data() + size();
        std::move(q, e, p);
 
        // Destruct all the freed up slots at the end of the vector.
        for (value_type *i = (e - num); i != e; ++i) {
            i->~value_type();
        }
 
        // Bump down the size.
        _size -= num;
 
        // Return an iterator to the next entry.
        return iterator(p);
    }
 
    void reserve(size_type newCapacity) {
        // Only reserve storage if the new capacity would grow past the local
        // storage, or the currently allocated storage. We'll grow to
        // accommodate exactly newCapacity entries.
        if (newCapacity > capacity()) {
            _GrowStorage(newCapacity);
        }
    } 
 
    void resize(size_type newSize, const value_type &v = value_type()) {
        // If the new size is smaller than the current size, let go of some
        // entries at the tail.
        if (newSize < size()) {
            erase(const_iterator(data() + newSize), 
                  const_iterator(data() + size())); 
        }
 
        // Otherwise, lets grow and fill: Reserve some storage, fill the tail
        // end with copies of v, and update the new size.
        else if (newSize > size()) {
            reserve(newSize);
            std::uninitialized_fill(data() + size(), data() + newSize, v);
            _size = newSize;
        }
    }
 
    void clear() {
        _Destruct();
        _size = 0;
    }
 
    template<typename ForwardIterator,
         typename = _EnableIfForwardIterator<ForwardIterator>>
    void assign(ForwardIterator first, ForwardIterator last) {
        clear();
        const size_type newSize = std::distance(first, last);
        reserve(newSize);
        std::uninitialized_copy(first, last, begin());
        _size = newSize;
    }
 
    void assign(std::initializer_list<T> ilist) {
        assign(ilist.begin(), ilist.end());
    }
 
    template < typename... Args >
    void emplace_back(Args&&... args) {
        if (size() == capacity()) {
            _GrowStorage(_NextCapacity());
        }
        new (data() + size()) value_type(std::forward<Args>(args)...);
        _size += 1;
    }
 
    void push_back(const value_type &v) {
        emplace_back(v);
    }
 
    void push_back(value_type &&v) {
        emplace_back(std::move(v));
    }
 
    template <typename ForwardIterator>
    void insert(iterator pos, ForwardIterator first, ForwardIterator last)
    {
        static_assert(
            std::is_convertible<
            typename std::iterator_traits<ForwardIterator>::iterator_category,
            std::forward_iterator_tag>::value,
            "Input Iterators not supported.");
 
        // Check for the insert-at-end special case as the very first thing so
        // that we give the compiler the best possible opportunity to
        // eliminate the general case code.
        const bool insertAtEnd = pos == end();
 
        const long numNewElems = std::distance(first, last);
        const size_type neededCapacity = size() + numNewElems;
        const size_type nextCapacity =
            std::max(_NextCapacity(), neededCapacity);
 
        // Insertions at the end would be handled correctly by the code below
        // without this special case.  However, insert(end(), f, l) is an
        // extremely common operation so we provide this fast path both to
        // avoid unneeded work and to make it easier for the compiler to
        // eliminate dead code when pos == end().
        if (insertAtEnd) {
            // The reallocation here is not a simple reserve.  We want to grow
            // the storage only when there are too many new elements but the
            // desired size is based on the growth factor.
            if (neededCapacity > capacity()) {
                _GrowStorage(nextCapacity);
            }
            std::uninitialized_copy(first, last, end());
            _size += numNewElems;
            return;
        }
 
        if (neededCapacity > capacity()) {
            // Because we need to realloc, we can do the insertion by copying
            // each range, [begin(), pos), [first, last), [pos, end()), into
            // the new storage.
 
            const size_type posI = std::distance(begin(), pos);
            value_type *newStorage = _Allocate(nextCapacity);
 
            iterator newPrefixBegin = iterator(newStorage);
            iterator newPos = newPrefixBegin + posI;
            iterator newSuffixBegin = newPos + numNewElems;
            _UninitializedMove(begin(), pos, newPrefixBegin);
            std::uninitialized_copy(first, last, newPos);
            _UninitializedMove(pos, end(), newSuffixBegin);
 
            // Destroy old data and set up this new buffer.
            _Destruct();
            _FreeStorage();
            _SetRemoteStorage(newStorage);
            _capacity = nextCapacity;
        }
        else {
            // Insert in-place requires handling four ranges.
            //
            // For both the range-to-move [pos, end()) and the range-to-insert
            // [first, last), there are two subranges: the subrange to copy
            // and the subrange to uinitialized_copy.  Note that only three of
            // these ranges may be non-empty: either there is a non-empty
            // prefix of [pos, end()) that needs to be copied over existing
            // elements or there is a non-empty suffix of [first, last) that
            // needs to be placed in uninitialized storage.
 
            const long numMoveElems = std::distance(pos, end());
            const long numUninitMoves = std::min(numNewElems, numMoveElems);
            const long numInitMoves = numMoveElems - numUninitMoves;
            const long numUninitNews = numNewElems - numUninitMoves;
            const long numInitNews = numNewElems - numUninitNews;
 
            // Move our existing elements out of the way of new elements.
            iterator umSrc = pos + numInitMoves;
            iterator umDst = end() + numUninitNews;
            _UninitializedMove(umSrc, end(), umDst);
            std::copy_backward(pos, umSrc, umDst);
 
            // Copy new elements into place.
            for (long i=0; i<numInitNews; ++i, ++first, ++pos) {
                *pos = *first;
            }
            std::uninitialized_copy(first, last, end());
        }
 
        _size += numNewElems;
    }
 
    void insert(iterator pos, std::initializer_list<T> ilist) {
        insert(pos, ilist.begin(), ilist.end());
    }
 
    void pop_back() {
        back().~value_type();
        _size -= 1;
    }
 
    size_type size() const {
        return _size;
    }
 
    static constexpr size_type max_size() {
        return std::numeric_limits<_SizeMemberType>::max();
    }
 
    bool empty() const {
        return size() == 0;
    }
 
    size_type capacity() const {
        return _capacity;
    }
 
    static constexpr size_type internal_capacity() {
        return N;
    }
 
 
    iterator begin() {
        return iterator(_GetStorage());
    }
 
    const_iterator begin() const {
        return const_iterator(_GetStorage());
    }
 
    const_iterator cbegin() const {
        return begin();
    }
 
 
 
    iterator end() {
        return iterator(_GetStorage() + size());
    }
 
    const_iterator end() const {
        return const_iterator(_GetStorage() + size());
    }
 
    const_iterator cend() const {
        return end();
    }
 
 
 
    reverse_iterator rbegin() {
        return reverse_iterator(end());
    }
 
    const_reverse_iterator rbegin() const {
        return const_reverse_iterator(end());
    }
 
    const_reverse_iterator crbegin() const {
        return rbegin();
    }
 
 
 
    reverse_iterator rend() {
        return reverse_iterator(begin());
    }
 
    const_reverse_iterator rend() const {
        return const_reverse_iterator(begin());
    }
 
    const_reverse_iterator crend() const {
        return rend();
    }
 
 
    reference front() {
        return *begin();
    }
 
    const_reference front() const {
        return *begin();
    }
 
    reference back() {
        return data()[size() - 1];
    }
 
    const_reference back() const {
        return data()[size() - 1];
    }
 
    reference operator[](size_type i) {
        return data()[i];
    }
 
    const_reference operator[](size_type i) const {
        return data()[i];
    }
 
    value_type *data() {
        return _GetStorage();
    }
 
    const value_type *data() const {
        return _GetStorage();
    }
 
    bool operator==(const TfSmallVector &rhs) const {
        return size() == rhs.size() && std::equal(begin(), end(), rhs.begin());
    }
 
    bool operator!=(const TfSmallVector &rhs) const {
        return !operator==(rhs);
    }
    
private:
 
    // Raw data access.
    value_type *_GetLocalStorage() {
        return static_cast<value_type *>(_data.GetLocalStorage());
    }
    const value_type *_GetLocalStorage() const {
        return static_cast<const value_type *>(_data.GetLocalStorage());
    }
 
    value_type *_GetRemoteStorage() {
        return static_cast<value_type *>(_data.GetRemoteStorage());
    }
    const value_type *_GetRemoteStorage() const {
        return static_cast<const value_type *>(_data.GetRemoteStorage());
    }
 
    void _SetRemoteStorage(value_type *p) {
        _data.SetRemoteStorage(static_cast<void *>(p));
    }
    
    // Returns true if the local storage is used.
    bool _IsLocal() const {
        return _capacity <= N;
    }
 
    // Return a pointer to the storage, which is either local or remote
    // depending on the current capacity.
    value_type *_GetStorage() {
        return _IsLocal() ? _GetLocalStorage() : _GetRemoteStorage();
    }
 
    // Return a const pointer to the storage, which is either local or remote
    // depending on the current capacity.
    const value_type *_GetStorage() const {
        return _IsLocal() ? _GetLocalStorage() : _GetRemoteStorage();
    }
 
    // Free the remotely allocated storage.
    void _FreeStorage() {
        if (!_IsLocal()) {
            ::operator delete(_data.GetRemoteStorage(), std::nothrow);
        }
    }
 
    // Destructs all the elements stored in this vector.
    void _Destruct() {
        value_type *b = data();
        value_type *e = b + size();
        for (value_type *p = b; p != e; ++p) {
            p->~value_type();
        }
    }
 
    // Allocate a buffer on the heap.
    static value_type *_Allocate(size_type size) {
        return static_cast<value_type *>(
            ::operator new(sizeof(value_type) * size, std::nothrow));
    }
 
    // Initialize the vector with new storage, updating the capacity and size.
    void _InitStorage(size_type size) {
        if (size > capacity()) {
            _SetRemoteStorage(_Allocate(size));
            _capacity = size;
        }
#if defined(ARCH_COMPILER_GCC) && ARCH_COMPILER_GCC_MAJOR < 11
        else if constexpr (!_data.HasLocal) {
            // When there's no local storage and we're not allocating remote
            // storage, initialize the remote storage pointer to avoid 
            // spurious compiler warnings about maybe-uninitialized values
            // being used. 
 
            // This clause can be removed upon upgrade to gcc 11 as 
            // the new compiler no longer generates this warning in this case.
            _data.SetRemoteStorage(nullptr);
        }
#endif
        _size = size;
    }
 
    // Grow the storage to be able to accommodate newCapacity entries. This
    // always allocates remote storage.
    void _GrowStorage(const size_type newCapacity) {
        value_type *newStorage = _Allocate(newCapacity);
        _UninitializedMove(begin(), end(), iterator(newStorage));
        _Destruct();
        _FreeStorage();
        _SetRemoteStorage(newStorage);
        _capacity = newCapacity;
    }
 
    // Returns the next capacity to use for vector growth. The growth factor
    // here is 1.5. A constant 1 is added so that we do not have to special
    // case initial capacities of 0 and 1.
    size_type _NextCapacity() const {
        const size_type cap = capacity();
        return cap + (cap / 2) + 1;
    }
 
    // Insert the value v at iterator it. We use this method that takes a 
    // universal reference to de-duplicate the logic required for the insert
    // overloads, one taking an rvalue reference, and the other one taking a
    // const reference. This way, we can take the most optimal code path (
    // move, or copy without making redundant copies) based on whether v is
    // a rvalue reference or const reference.
    template < typename U >
    iterator _Insert(const_iterator it, U &&v) {
        value_type *newEntry;
 
        // If the iterator points to the end, simply push back.
        if (it == end()) {
            push_back(std::forward<U>(v));
            return end() - 1;
        }
 
        // Grow the remote storage, if we need to. This invalidates iterators,
        // so special care must be taken in order to return a new, valid
        // iterator.
        else if (size() == capacity()) {
            const size_type newCapacity = _NextCapacity();
            value_type *newStorage = _Allocate(newCapacity);
            
            value_type *i = const_cast<value_type *>(&*it);
            value_type *curData = data();
            newEntry = _UninitializedMove(curData, i, newStorage);
 
            new (newEntry) value_type(std::forward<U>(v));
 
            _UninitializedMove(i, curData + size(), newEntry + 1);
 
            _Destruct();
            _FreeStorage();
 
            _SetRemoteStorage(newStorage);
            _capacity = newCapacity;
        }
 
        // Our current capacity is big enough to allow us to simply shift
        // elements up one slot and insert v at it.
        else {
            // Move all the elements after it up by one slot.
            newEntry = const_cast<value_type *>(&*it);
            value_type *last = const_cast<value_type *>(&back());
            new (data() + size()) value_type(std::move(*last));
            std::move_backward(newEntry, last, last + 1);
 
            // Move v into the slot at the supplied iterator position.
            newEntry->~value_type();
            new (newEntry) value_type(std::forward<U>(v));
        }
 
        // Bump size and return an iterator to the newly inserted entry.
        ++_size;
        return iterator(newEntry);
    }
 
    // The vector storage, which is a union of the local storage and a pointer
    // to the heap memory, if allocated.
    _Data<value_type, N> _data;
 
    // The current size of the vector, i.e. how many entries it contains.
    _SizeMemberType _size;
 
    // The current capacity of the vector, i.e. how big the currently allocated
    // storage space is.
    _SizeMemberType _capacity;
};
 
 
template < typename T, uint32_t N >
void swap(TfSmallVector<T, N> &a, TfSmallVector<T, N> &b)
{
    a.swap(b);
}
 
 
// Return the largest local capacity N so that sizeof(TfSmallVector<T, N>) <=
// SizeOf.
template <class T, size_t SizeOf>
constexpr uint32_t
TfComputeSmallVectorLocalCapacityForTotalSize()
{
    // If T is over-aligned, sizeof(TfSmallVector<T, 1>) can be greater than
    // sizeof(TfSmallVector<T, 0>) + sizeof(T).  If sizeof(TfSmallVector<T, 1>)
    // is not already too large, we take the total desired size minus
    // sizeof(TfSmallVector<T, 1>), divide the difference by sizeof(T) and add
    // one.
    constexpr size_t SizeOfOne = sizeof(TfSmallVector<T, 1>);
    constexpr size_t LocalCap = SizeOfOne > SizeOf ? 0
        : ((SizeOf - SizeOfOne) / sizeof(T)) + 1;
    constexpr size_t LocalCapMax = std::numeric_limits<uint32_t>::max();
    constexpr uint32_t LocalCap32 = static_cast<uint32_t>(
        LocalCap > LocalCapMax ? LocalCapMax : LocalCap);
    static_assert(sizeof(TfSmallVector<T, LocalCap32>) <= SizeOf);
    return LocalCap32;
}
 
PXR_NAMESPACE_CLOSE_SCOPE
 
#endif