array.h

Go to the documentation of this file.

//
// Copyright 2016 Pixar
//
// Licensed under the terms set forth in the LICENSE.txt file available at
// https://openusd.org/license.
//
#ifndef PXR_BASE_VT_ARRAY_H
#define PXR_BASE_VT_ARRAY_H
 
 
#include "pxr/pxr.h"
#include "pxr/base/vt/api.h"
#include "pxr/base/vt/hash.h"
#include "pxr/base/vt/streamOut.h"
#include "pxr/base/vt/traits.h"
#include "pxr/base/vt/types.h"
 
#include "pxr/base/arch/functionLite.h"
#include "pxr/base/arch/pragmas.h"
#include "pxr/base/tf/diagnostic.h"
#include "pxr/base/tf/mallocTag.h"
#include "pxr/base/tf/preprocessorUtilsLite.h"
 
#include <algorithm>
#include <atomic>
#include <cstddef>
#include <cstdlib>
#include <iterator>
#include <limits>
#include <memory>
#include <new>
#include <type_traits>
 
PXR_NAMESPACE_OPEN_SCOPE
 
// Helper class for clients that create VtArrays referring to foreign-owned
// data.
class Vt_ArrayForeignDataSource
{
public:
    explicit Vt_ArrayForeignDataSource(
        void (*detachedFn)(Vt_ArrayForeignDataSource *self) = nullptr,
        size_t initRefCount = 0)
        : _refCount(initRefCount)
        , _detachedFn(detachedFn) {}
    
private:
    template <class T> friend class VtArray;
    // Invoked when no more arrays share this data source.
    void _ArraysDetached() { if (_detachedFn) { _detachedFn(this); } }
protected:
    std::atomic<size_t> _refCount;
    void (*_detachedFn)(Vt_ArrayForeignDataSource *self);
};
 
// Private base class helper for VtArray implementation.
class Vt_ArrayBase
{
public:
    Vt_ArrayBase() : _shapeData { 0 }, _foreignSource(nullptr) {}
 
    Vt_ArrayBase(Vt_ArrayForeignDataSource *foreignSrc)
        : _shapeData { 0 }, _foreignSource(foreignSrc) {}
 
    Vt_ArrayBase(Vt_ArrayBase const &other) = default;
    Vt_ArrayBase(Vt_ArrayBase &&other) : Vt_ArrayBase(other) {
        other._shapeData.clear();
        other._foreignSource = nullptr;
    }
 
    Vt_ArrayBase &operator=(Vt_ArrayBase const &other) = default;
    Vt_ArrayBase &operator=(Vt_ArrayBase &&other) {
        if (this == &other)
            return *this;
        *this = other;
        other._shapeData.clear();
        other._foreignSource = nullptr;
        return *this;
    }
    
protected:
    // Control block header for native data representation.  Houses refcount and
    // capacity.  For arrays with native data, this structure always lives
    // immediately preceding the start of the array's _data in memory.  See
    // _GetControlBlock() for details.
    struct _ControlBlock {
        _ControlBlock() : nativeRefCount(0), capacity(0) {}
        _ControlBlock(size_t initCount, size_t initCap)
            : nativeRefCount(initCount), capacity(initCap) {}
        mutable std::atomic<size_t> nativeRefCount;
        size_t capacity;
    };
    
    _ControlBlock &_GetControlBlock(void *nativeData) {
        TF_DEV_AXIOM(!_foreignSource);
        return *(reinterpret_cast<_ControlBlock *>(nativeData) - 1);
    }
    
    _ControlBlock const &_GetControlBlock(void *nativeData) const {
        TF_DEV_AXIOM(!_foreignSource);
        return *(reinterpret_cast<_ControlBlock *>(nativeData) - 1);
    }
 
    // Mutable ref count, as is standard.
    std::atomic<size_t> &_GetNativeRefCount(void *nativeData) const {
        return _GetControlBlock(nativeData).nativeRefCount;
    }
 
    size_t &_GetCapacity(void *nativeData) {
        return _GetControlBlock(nativeData).capacity;
    }
    size_t const &_GetCapacity(void *nativeData) const {
        return _GetControlBlock(nativeData).capacity;
    }
 
    VT_API void _DetachCopyHook(char const *funcName) const;
 
    Vt_ShapeData _shapeData;
    Vt_ArrayForeignDataSource *_foreignSource;
};
 
ARCH_PRAGMA_PUSH
ARCH_PRAGMA_NON_EXPORTED_BASE_CLASS
template<typename ELEM>
class VtArray : public Vt_ArrayBase {
ARCH_PRAGMA_POP
  public:
 
    typedef ELEM ElementType;
    typedef ELEM value_type;
 
 
    using iterator = ElementType *;
    using const_iterator = ElementType const *;
    
    typedef std::reverse_iterator<iterator> reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 
    typedef ElementType &reference;
    typedef ElementType const &const_reference;
    typedef ElementType *pointer;
    typedef ElementType const *const_pointer;
 
 
    VtArray() : _data(nullptr) {}
 
    template <typename LegacyInputIterator>
    VtArray(LegacyInputIterator first, LegacyInputIterator last,
            std::enable_if_t<
                !std::is_integral_v<LegacyInputIterator>> * = nullptr)
        : VtArray() {
        assign(first, last); 
    }
 
    VtArray(Vt_ArrayForeignDataSource *foreignSrc,
            ElementType *data, size_t size, bool addRef = true)
        : Vt_ArrayBase(foreignSrc)
        , _data(data) {
        if (addRef) {
            foreignSrc->_refCount.fetch_add(1, std::memory_order_relaxed);
        }
        _shapeData.totalSize = size;
    }
    
    VtArray(VtArray const &other) : Vt_ArrayBase(other)
                                  , _data(other._data) {
        if (!_data)
            return;
 
        if (ARCH_LIKELY(!_foreignSource)) {
            _GetNativeRefCount(_data).fetch_add(1, std::memory_order_relaxed);
        }
        else {
            _foreignSource->_refCount.fetch_add(1, std::memory_order_relaxed);
        }
    }
    
    VtArray(VtArray &&other) : Vt_ArrayBase(std::move(other))
                             , _data(other._data) {
        other._data = nullptr;
    }
 
    VtArray(std::initializer_list<ELEM> initializerList)
        : VtArray() {
        assign(initializerList);
    }
 
    explicit VtArray(size_t n)
        : VtArray() {
        assign(n, value_type());
    }
 
    explicit VtArray(size_t n, value_type const &value)
        : VtArray() {
        assign(n, value);
    }
 
    VtArray &operator=(VtArray const &other) {
        // This might look recursive but it's really invoking move-assign, since
        // we create a temporary copy (an rvalue).
        if (this != &other)
            *this = VtArray(other);
        return *this;
    }
 
    VtArray &operator=(VtArray &&other) {
        if (this == &other)
            return *this;
        _DecRef();
        static_cast<Vt_ArrayBase &>(*this) = std::move(other);
        _data = other._data;
        other._data = nullptr;
        return *this;
    }
 
    VtArray &operator=(std::initializer_list<ELEM> initializerList) {
        this->assign(initializerList.begin(), initializerList.end());
        return *this;
    }
 
    ~VtArray() { _DecRef(); }
    
    VtArray const &AsConst() const noexcept {
        return *this;
    }
 
    
    iterator begin() { return iterator(data()); }
    iterator end() { return iterator(data() + size()); }
 
    const_iterator begin() const { return const_iterator(data()); }
    const_iterator end() const { return const_iterator(data() + size()); }
 
    const_iterator cbegin() const { return begin(); }
    const_iterator cend() const { return end(); }
 
    reverse_iterator rbegin() { return reverse_iterator(end()); }
    reverse_iterator rend() { return reverse_iterator(begin()); }
 
    const_reverse_iterator rbegin() const {
        return const_reverse_iterator(end());
    }
    const_reverse_iterator rend() const {
        return const_reverse_iterator(begin());
    }
 
    const_reverse_iterator crbegin() const { return rbegin(); }
    const_reverse_iterator crend() const { return rend(); }
 
    pointer data() { _DetachIfNotUnique(); return _data; }
    const_pointer data() const { return _data; }
    const_pointer cdata() const { return _data; }
 
    template <typename... Args>
    void emplace_back(Args&&... args) {
        // If this is a non-pxr array with rank > 1, disallow push_back.
        if (ARCH_UNLIKELY(_shapeData.otherDims[0])) {
            TF_CODING_ERROR("Array rank %u != 1", _shapeData.GetRank());
            return;
        }
        // If we don't own the data, or if we need more space, realloc.
        size_t curSize = size();
        if (ARCH_UNLIKELY(
                _foreignSource || !_IsUnique() || curSize == capacity())) {
            value_type *newData = _AllocateCopy(
                _data, _CapacityForSize(curSize + 1), curSize);
            ::new (static_cast<void*>(newData + curSize)) value_type(
                std::forward<Args>(args)...);
            _DecRef();
            _data = newData;
        }
        else {
            ::new (static_cast<void*>(_data + curSize)) value_type(
                std::forward<Args>(args)...);
        }
        // Adjust size.
        ++_shapeData.totalSize;
    }
 
    void push_back(ElementType const& element) {
        emplace_back(element);
    }
 
    void push_back(ElementType&& element) {
        emplace_back(std::move(element));
    }
 
    void pop_back() {
        // If this is a presto array with rank > 1, disallow push_back.
        if (ARCH_UNLIKELY(_shapeData.otherDims[0])) {
            TF_CODING_ERROR("Array rank %u != 1", _shapeData.GetRank());
            return;
        }
        _DetachIfNotUnique();
        // Invoke the destructor.
        (_data + size() - 1)->~value_type();
        // Adjust size.
        --_shapeData.totalSize;
    }
 
    size_t size() const { return _shapeData.totalSize; }
 
    size_t capacity() const {
        if (!_data) {
            return 0;
        }
        // We do not allow mutation to foreign source data, so always report
        // foreign sourced arrays as at capacity.
        return ARCH_UNLIKELY(_foreignSource) ? size() : _GetCapacity(_data);
    }
 
    constexpr size_t max_size() const {
        // Popular compilers limit object sizes to half the address space, so we
        // follow suit, taking max bytes as one less than the maximum value of a
        // difference between pointers.  This is unobtainable in practice: on a
        // 64-bit machine this is more than 8 million terabytes.
        return (std::numeric_limits<ptrdiff_t>::max() - 1 -
                sizeof(_ControlBlock)) / sizeof(value_type);
    }
 
    bool empty() const { return size() == 0; }
    
    void reserve(size_t num) {
        if (num <= capacity())
            return;
        
        value_type *newData =
            _data ? _AllocateCopy(_data, num, size()) : _AllocateNew(num);
 
        _DecRef();
        _data = newData;
    }
 
    reference front() { return *begin(); }
    const_reference front() const { return *begin(); }
    const_reference cfront() const { return *begin(); }
 
    reference back() { return *rbegin(); }
    const_reference back() const { return *rbegin(); }
    const_reference cback() const { return *rbegin(); }
 
    void resize(size_t newSize) {
        return resize(newSize, value_type());
    }
 
    void resize(size_t newSize, value_type const &value) {
        return resize(newSize,
                      [&value](pointer b, pointer e) {
                          std::uninitialized_fill(b, e, value);
                      });
    }
 
    void resize(size_t newSize, value_type &value) {
        return resize(newSize, const_cast<value_type const &>(value));
    }
 
    void resize(size_t newSize, value_type &&value) {
        return resize(newSize, const_cast<value_type const &>(value));
    }
 
    template <class FillElemsFn>
    void resize(size_t newSize, FillElemsFn &&fillElems) {
        const size_t oldSize = size();
        if (oldSize == newSize) {
            return;
        }
        if (newSize == 0) {
            clear();
            return;
        }
 
        const bool growing = newSize > oldSize;
        value_type *newData = _data;
 
        if (!_data) {
            // Allocate newSize elements and initialize.
            newData = _AllocateNew(newSize);
            std::forward<FillElemsFn>(fillElems)(newData, newData + newSize);
        }
        else if (_IsUnique()) {
            if (growing) {
                if (newSize > _GetCapacity(_data)) {
                    newData = _AllocateCopy(_data, newSize, oldSize);
                }
                // fill with newly added elements from oldSize to newSize.
                std::forward<FillElemsFn>(fillElems)(newData + oldSize,
                                                     newData + newSize);
            }
            else {
                // destroy removed elements
                for (auto *cur = newData + newSize,
                         *end = newData + oldSize; cur != end; ++cur) {
                    cur->~value_type();
                }
            }
        }
        else {
            newData =
                _AllocateCopy(_data, newSize, growing ? oldSize : newSize);
            if (growing) {
                // fill with newly added elements from oldSize to newSize.
                std::forward<FillElemsFn>(fillElems)(newData + oldSize,
                                                     newData + newSize);
            }
        }
 
        // If we created new data, clean up the old and move over to the new.
        if (newData != _data) {
            _DecRef();
            _data = newData;
        }
        // Adjust size.
        _shapeData.totalSize = newSize;
    }
 
    void clear() {
        if (!_data)
            return;
        if (_IsUnique()) {
            // Clear out elements, run dtors, keep capacity.
            for (value_type *p = _data, *e = _data + size(); p != e; ++p) {
                p->~value_type();
            }
        }
        else {
            // Detach to empty.
            _DecRef();
        }
        _shapeData.clear();
    }
 
    iterator insert(const_iterator pos, value_type const &value) {
        // If value is an element of the array, we make a copy and move-insert
        // it.  std::less (and friends) and the standard's guarantee of a strict
        // pointer total order ensures this works.
        const const_pointer valuePtr = std::addressof(value);
        if (std::less_equal<const_pointer>{}(cdata(), valuePtr) &&
            std::less<const_pointer>{}(valuePtr, cdata() + size())) {
            value_type tmp { value };
            return insert(pos,
                          std::make_move_iterator(std::addressof(tmp)),
                          std::make_move_iterator(std::addressof(tmp) + 1));
        }
        return insert(pos, valuePtr, valuePtr + 1);
    }
 
    iterator insert(const_iterator pos, value_type &&value) {
        // If value is an element of the array, we move it to a temp spot and
        // move-insert that.  std::less (and friends) and the standard's
        // guarantee of a strict pointer total order ensures this works.
        const const_pointer valuePtr = std::addressof(value);
        if (std::less_equal<const_pointer>{}(cdata(), valuePtr) &&
            std::less<const_pointer>{}(valuePtr, cdata() + size())) {
            value_type tmp { std::move(value) };
            return insert(pos,
                          std::make_move_iterator(std::addressof(tmp)),
                          std::make_move_iterator(std::addressof(tmp) + 1));
        }
        return insert(pos,
                      std::make_move_iterator(valuePtr),
                      std::make_move_iterator(valuePtr + 1));
    }
 
    iterator insert(const_iterator pos, size_t count, value_type const &fill) {
        // If fill is an element of the array, we copy it to a temporary and
        // insert that.  std::less (and friends) and the standard's guarantee of
        // a strict pointer total order ensures this works.
        const const_pointer fillPtr = std::addressof(fill);
        if (std::less_equal<const_pointer>{}(cdata(), fillPtr) &&
            std::less<const_pointer>{}(fillPtr, cdata() + size())) {
            value_type tmp { fill };
            return insert(pos, count, [&tmp](pointer b, pointer e) {
                std::uninitialized_fill(b, e, tmp);
            });
        }
        return insert(pos, count, [&fill](pointer b, pointer e) {
            std::uninitialized_fill(b, e, fill);
        });
    }
 
    iterator insert(const_iterator pos, std::initializer_list<ELEM> ilist) {
        return insert(pos, ilist.begin(), ilist.end());
    }
 
    template <class LegacyInputIterator>
    std::enable_if_t<
        !std::is_integral_v<LegacyInputIterator>, iterator>
    insert(
        const_iterator pos,
        LegacyInputIterator first, LegacyInputIterator last) {
        return insert(pos, std::distance(first, last),
                      [&first, &last](pointer b, pointer e) {
                          std::uninitialized_copy(first, last, b);
                      });
    }
 
    template <class FillElemsFn>
    std::enable_if_t<
        !std::is_integral_v<std::decay_t<FillElemsFn>>,
        iterator>
    insert(const_iterator pos, size_t count, FillElemsFn &&fillElems) {
        if (count == 0) {
            return begin() + std::distance(cbegin(), pos);
        }
        if (empty()) {
            resize(count, std::forward<FillElemsFn>(fillElems));
            return begin();
        }
        // This array is not empty, and we will insert at least one element.
        const size_t newSize = size() + count;
        if (_IsUnique()) {
            if (newSize <= capacity()) {
                // We can avoid reallocation.
                iterator ncpos = begin() + std::distance(cbegin(), pos);
                iterator iend = end();
                if (pos != cend()) {
                    // The 'count' tail elements must be uninitialized_move'd
                    // over.  The remainder must be move_backward'd.
                    std::uninitialized_copy(
                        std::make_move_iterator(iend-count),
                        std::make_move_iterator(iend), iend);
                    std::move_backward(ncpos, iend-count, iend);
                }
                // Fill new elements.
                value_type *p = std::addressof(*ncpos);
                std::forward<FillElemsFn>(fillElems)(p, p + count);
                // Set new size.
                _shapeData.totalSize = newSize;
                return ncpos;
            }
            else {
                // We need to allocate, but can move items.
                value_type* newData = _AllocateNew(newSize);
                size_t posOffset = std::distance(cbegin(), pos);
                std::uninitialized_copy(
                    std::make_move_iterator(begin()),
                    std::make_move_iterator(begin() + posOffset), newData);
                std::uninitialized_copy(
                    std::make_move_iterator(begin() + posOffset),
                    std::make_move_iterator(end()),
                    newData + posOffset + count);
                // Drop the old data and fill the new elements.
                _DecRef();
                _data = newData;
                _shapeData.totalSize = newSize;
                std::forward<FillElemsFn>(fillElems)(
                    newData + posOffset, newData + posOffset + count);
                return begin() + posOffset;
            }
        }
        else {
            // Allocate new space and copy.
            value_type* newData = _AllocateNew(newSize);
            size_t posOffset = std::distance(cbegin(), pos);
            std::uninitialized_copy(cbegin(), pos, newData);
            std::uninitialized_copy(pos, cend(), newData + posOffset + count);
            // Drop the old data and fill the new elements.
            _DecRef();
            _data = newData;
            _shapeData.totalSize = newSize;
            std::forward<FillElemsFn>(fillElems)(
                newData + posOffset, newData + posOffset + count);
            return begin() + posOffset;
        }
        // unreachable.
    }
    
    iterator erase(const_iterator pos) {
        TF_DEV_AXIOM(pos != cend());
        return erase(pos, pos+1);
    }
 
    iterator erase(const_iterator first, const_iterator last) {
        if (first == last) {
            return std::next(begin(), std::distance(cbegin(), last));
        }
        if ((first == cbegin()) && (last == cend())) {
            clear();
            return end();
        }
        // Given the previous two conditions, we know that we are removing
        // at least one element and the result array will contain at least one
        // element.
        value_type* removeStart =
            std::next(_data, std::distance(cbegin(), first));
        value_type* removeEnd = std::next(_data, std::distance(cbegin(), last));
        value_type* endIt = std::next(_data, size());
        size_t newSize = size() - std::distance(first, last);
        if (_IsUnique()) {
            // If the array is unique, we can simply move the tail elements
            // and free to the end of the array.
            value_type* deleteIt = std::move(removeEnd, endIt, removeStart);
            for (; deleteIt != endIt; ++deleteIt) {
                deleteIt->~value_type();
            }
            _shapeData.totalSize = newSize;
            return iterator(removeStart);
        } else {
            // If the array is not unique, we want to avoid copying the
            // elements in the range we are erasing. We allocate a
            // new buffer and copy the head and tail ranges, omitting
            // [first, last)
            value_type* newData = _AllocateNew(newSize);
            value_type* newMiddle = std::uninitialized_copy(
                _data, removeStart, newData);
            value_type* newEnd = std::uninitialized_copy(
                removeEnd, endIt, newMiddle);
            TF_DEV_AXIOM(newEnd == std::next(newData, newSize));
            TF_DEV_AXIOM(std::distance(newData, newMiddle) == 
                         std::distance(_data, removeStart));
            _DecRef();
            _data = newData;
            _shapeData.totalSize = newSize;
            return iterator(newMiddle);
        }
    }
 
    template <class ForwardIter>
    typename std::enable_if<!std::is_integral<ForwardIter>::value>::type
    assign(ForwardIter first, ForwardIter last) {
        struct _Copier {
            void operator()(pointer b, pointer e) const {
                std::uninitialized_copy(first, last, b);
            }
            ForwardIter const &first, &last;
        };
        clear();
        resize(std::distance(first, last), _Copier { first, last });
    }
 
    void assign(size_t n, const value_type &fill) {
        struct _Filler {
            void operator()(pointer b, pointer e) const {
                std::uninitialized_fill(b, e, fill);
            }
            const value_type &fill;
        };
        clear();
        resize(n, _Filler { fill });
    }
 
    void assign(std::initializer_list<ELEM> initializerList) {
        assign(initializerList.begin(), initializerList.end());
    }
 
    void swap(VtArray &other) { 
        std::swap(_data, other._data);
        std::swap(_shapeData, other._shapeData);
        std::swap(_foreignSource, other._foreignSource);
    }
 
 
    ElementType &operator[](size_t index) {
        return data()[index];
    }
 
    ElementType const &operator[](size_t index) const {
        return data()[index];
    }
 
    bool IsIdentical(VtArray const & other) const {
        return
            _data == other._data &&
            _shapeData == other._shapeData &&
            _foreignSource == other._foreignSource;
    }
 
    bool operator == (VtArray const & other) const {
        return IsIdentical(other) ||
            (*_GetShapeData() == *other._GetShapeData() &&
             std::equal(cbegin(), cend(), other.cbegin()));
    }
 
    bool operator != (VtArray const &other) const {
        return !(*this == other);
    }
 
    bool MakeUnique() {
        return _DetachIfNotUnique(/*invokeHook=*/false);
    }
 
  public:
    // XXX -- Public so VtValue::_ArrayHelper<T,U>::GetShapeData() has access.
    Vt_ShapeData const *_GetShapeData() const {
        return &_shapeData;
    }
    Vt_ShapeData *_GetShapeData() {
        return &_shapeData;
    }
 
  private:
    class _Streamer {
    public:
        explicit _Streamer(const_pointer data) : _p(data) { }
        void operator()(std::ostream &out) const {
            VtStreamOut(*_p++, out);
        }
 
    private:
        mutable const_pointer _p;
    };
 
    friend std::ostream &operator <<(std::ostream &out, const VtArray &self) {
        VtArray::_Streamer streamer(self.cdata());
        VtStreamOutArray(out, self._GetShapeData(), streamer);
        return out;
    }
 
    friend void swap(VtArray &lhs, VtArray &rhs) {
        lhs.swap(rhs);
    }
 
    bool _DetachIfNotUnique(bool invokeHook=true) {
        if (_IsUnique()) {
            return false;
        }
        // Copy to local.
        if (invokeHook) {
            _DetachCopyHook(__ARCH_PRETTY_FUNCTION__);
        }
        auto *newData = _AllocateCopy(_data, size(), size());
        _DecRef();
        _data = newData;
        return true;
    }
 
    inline bool _IsUnique() const {
        return !_data ||
            (ARCH_LIKELY(!_foreignSource) && _GetNativeRefCount(_data) == 1);
    }
 
    inline size_t _CapacityForSize(size_t sz) const {
        // Currently just successive powers of two.
        size_t cap = 1;
        while (cap < sz) {
            cap += cap;
        }
        return cap;
    }
 
    value_type *_AllocateNew(size_t capacity) {
        TfAutoMallocTag2 tag("VtArray::_AllocateNew", __ARCH_PRETTY_FUNCTION__);
        // Need space for the control block and capacity elements.
        // Exceptionally large capacity requests can overflow the arithmetic
        // here.  If that happens we'll just attempt to allocate the max size_t
        // value and let new() throw.
        size_t numBytes = (capacity <= max_size())
            ? sizeof(_ControlBlock) + capacity * sizeof(value_type)
            : std::numeric_limits<size_t>::max();
        void *data = ::operator new(numBytes);
        // Placement-new a control block.
        ::new (data) _ControlBlock(/*count=*/1, capacity);
        // Data starts after the block.
        return reinterpret_cast<value_type *>(
            static_cast<_ControlBlock *>(data) + 1);
    }
 
    value_type *_AllocateCopy(value_type *src, size_t newCapacity,
                              size_t numToCopy) {
        // Allocate and copy elements.
        value_type *newData = _AllocateNew(newCapacity);
        std::uninitialized_copy(src, src + numToCopy, newData);
        return newData;
    }
 
    void _DecRef() {
        if (!_data)
            return;
        if (ARCH_LIKELY(!_foreignSource)) {
            // Drop the refcount.  If we take it to zero, destroy the data.
            if (_GetNativeRefCount(_data).fetch_sub(
                    1, std::memory_order_release) == 1) {
                std::atomic_thread_fence(std::memory_order_acquire);
                for (value_type *p = _data, *e = _data + _shapeData.totalSize;
                     p != e; ++p) {
                    p->~value_type();
                }
                ::operator delete(static_cast<void *>(
                                      std::addressof(_GetControlBlock(_data))));
            }
        }
        else {
            // Drop the refcount in the foreign source.  If we take it to zero,
            // invoke the function pointer to alert the foreign source.
            if (_foreignSource->_refCount.fetch_sub(
                    1, std::memory_order_release) == 1) {
                std::atomic_thread_fence(std::memory_order_acquire);
                _foreignSource->_ArraysDetached();
            }
        }
        _foreignSource = nullptr;
        _data = nullptr;
    }
    
    value_type *_data;
};
 
// VtArray can transform if the underlying element type can.
template <class ELEM>
struct VtValueTypeCanTransform<VtArray<ELEM>> :
    VtValueTypeCanTransform<ELEM> {};
 
// Declare basic array instantiations as extern templates.  They are explicitly
// instantiated in array.cpp.
#define VT_ARRAY_EXTERN_TMPL(unused, elem) \
    VT_API_TEMPLATE_CLASS(VtArray< VT_TYPE(elem) >);
TF_PP_SEQ_FOR_EACH(VT_ARRAY_EXTERN_TMPL, ~, VT_SCALAR_VALUE_TYPES)
 
template <class HashState, class ELEM>
inline std::enable_if_t<VtIsHashable<ELEM>()>
TfHashAppend(HashState &h, VtArray<ELEM> const &array)
{
    h.Append(array.size());
    h.AppendContiguous(array.cdata(), array.size());
}
 
template <class ELEM>
typename std::enable_if<VtIsHashable<ELEM>(), size_t>::type
hash_value(VtArray<ELEM> const &array) {
    return TfHash()(array);
}
 
// Specialize traits so others can figure out that VtArray is an array.
template <typename T>
struct VtIsArray< VtArray <T> > : public std::true_type {};
 
template <class T>
struct Vt_ArrayOpHelp {
    static T Add(T l, T r) { return l + r; }
    static T Sub(T l, T r) { return l - r; }
    static T Mul(T l, T r) { return l * r; }
    static T Div(T l, T r) { return l / r; }
    static T Mod(T l, T r) { return l % r; }
};
 
template <class T>
struct Vt_ArrayOpHelpScalar {
    static T Mul(T l, double r) { return l * r; }
    static T Mul(double l, T r) { return l * r; }
    static T Div(T l, double r) { return l / r; }
    static T Div(double l, T r) { return l / r; }
};
 
// These operations on bool-arrays are highly questionable, but this preserves
// existing behavior in the name of Hyrum's Law.
template <>
struct Vt_ArrayOpHelp<bool> {
    static bool Add(bool l, bool r) { return l | r; }
    static bool Sub(bool l, bool r) { return l ^ r; }
    static bool Mul(bool l, bool r) { return l & r; }
    static bool Div(bool l, bool r) { return l; }
    static bool Mod(bool l, bool r) { return false; }
};
 
template <>
struct Vt_ArrayOpHelpScalar<bool> {
    static bool Mul(bool l, double r) { return l && (r != 0.0); }
    static bool Mul(double l, bool r) { return (l != 0.0) && r; }
    static bool Div(bool l, double r) { return (r == 0.0) || l; }
    static bool Div(double l, bool r) { return !r || (l != 0.0); }
};
 
#define VTOPERATOR_CPPARRAY(op, opName)                                        \
    template <class T>                                                         \
    VtArray<T>                                                                 \
    operator op (VtArray<T> const &lhs, VtArray<T> const &rhs)                 \
    {                                                                          \
        using Op = Vt_ArrayOpHelp<T>;                                          \
        /* accept empty vecs */                                                \
        if (!lhs.empty() && !rhs.empty() && lhs.size() != rhs.size()) {        \
            TF_CODING_ERROR("Non-conforming inputs for operator %s", #op);     \
            return VtArray<T>();                                               \
        }                                                                      \
        /* promote empty vecs to vecs of zeros */                              \
        const bool leftEmpty = lhs.size() == 0, rightEmpty = rhs.size() == 0;  \
        VtArray<T> ret(leftEmpty ? rhs.size() : lhs.size());                   \
        T zero = VtZero<T>();                                                  \
        if (leftEmpty) {                                                       \
            std::transform(                                                    \
                rhs.begin(), rhs.end(), ret.begin(),                           \
                [zero](T const &r) { return Op:: opName (zero, r); });         \
        }                                                                      \
        else if (rightEmpty) {                                                 \
            std::transform(                                                    \
                lhs.begin(), lhs.end(), ret.begin(),                           \
                [zero](T const &l) { return Op:: opName (l, zero); });         \
        }                                                                      \
        else {                                                                 \
            std::transform(                                                    \
                lhs.begin(), lhs.end(), rhs.begin(), ret.begin(),              \
                [](T const &l, T const &r) { return Op:: opName (l, r); });    \
        }                                                                      \
        return ret;                                                            \
    }
 
ARCH_PRAGMA_PUSH
ARCH_PRAGMA_FORCING_TO_BOOL
ARCH_PRAGMA_UNSAFE_USE_OF_BOOL
ARCH_PRAGMA_UNARY_MINUS_ON_UNSIGNED
 
VTOPERATOR_CPPARRAY(+, Add);
VTOPERATOR_CPPARRAY(-, Sub);
VTOPERATOR_CPPARRAY(*, Mul);
VTOPERATOR_CPPARRAY(/, Div);
VTOPERATOR_CPPARRAY(%, Mod);
    
template <class T>
VtArray<T>
operator-(VtArray<T> const &a) {
    VtArray<T> ret(a.size());
    std::transform(a.begin(), a.end(), ret.begin(),
                   [](T const &x) { return -x; });
    return ret;
}
 
ARCH_PRAGMA_POP
 
// Operations on scalars and arrays
// These are free functions defined in Array.h
#define VTOPERATOR_CPPSCALAR(op,opName)                                 \
    template<typename T>                                                \
    VtArray<T> operator op (T const &scalar, VtArray<T> const &arr) {   \
        using Op = Vt_ArrayOpHelp<T>;                                   \
        VtArray<T> ret(arr.size());                                     \
        std::transform(arr.begin(), arr.end(), ret.begin(),             \
                       [&scalar](T const &aObj) {                       \
                           return Op:: opName (scalar, aObj);           \
                       });                                              \
        return ret;                                                     \
    }                                                                   \
    template<typename T>                                                \
    VtArray<T> operator op (VtArray<T> const &arr, T const &scalar) {   \
        using Op = Vt_ArrayOpHelp<T>;                                   \
        VtArray<T> ret(arr.size());                                     \
        std::transform(arr.begin(), arr.end(), ret.begin(),             \
                       [&scalar](T const &aObj) {                       \
                           return Op:: opName (aObj, scalar);           \
                       });                                              \
        return ret;                                                     \
    } 
 
// define special-case operators on arrays and doubles - except if the array
// holds doubles, in which case we already defined the operator (with
// VTOPERATOR_CPPSCALAR above) so we can't do it again!
#define VTOPERATOR_CPPSCALAR_DOUBLE(op,opName)                          \
    template<typename T>                                                \
    std::enable_if_t<!std::is_same<T, double>::value, VtArray<T>>       \
    operator op (double const &scalar, VtArray<T> const &arr) {         \
        using Op = Vt_ArrayOpHelpScalar<T>;                             \
        VtArray<T> ret(arr.size());                                     \
        std::transform(arr.begin(), arr.end(), ret.begin(),             \
                       [&scalar](T const &aObj) {                       \
                           return Op:: opName (scalar, aObj);           \
                       });                                              \
        return ret;                                                     \
    }                                                                   \
    template<typename T>                                                \
    std::enable_if_t<!std::is_same<T, double>::value, VtArray<T>>       \
    operator op (VtArray<T> const &arr, double const &scalar) {         \
        using Op = Vt_ArrayOpHelpScalar<T>;                             \
        VtArray<T> ret(arr.size());                                     \
        std::transform(arr.begin(), arr.end(), ret.begin(),             \
                       [&scalar](T const &aObj) {                       \
                           return Op:: opName (aObj, scalar);           \
                       });                                              \
        return ret;                                                     \
    } 
 
// free functions for operators combining scalar and array types
ARCH_PRAGMA_PUSH
ARCH_PRAGMA_FORCING_TO_BOOL
ARCH_PRAGMA_UNSAFE_USE_OF_BOOL
ARCH_PRAGMA_UNARY_MINUS_ON_UNSIGNED
VTOPERATOR_CPPSCALAR(+, Add)
VTOPERATOR_CPPSCALAR(-, Sub)
VTOPERATOR_CPPSCALAR(*, Mul)
VTOPERATOR_CPPSCALAR_DOUBLE(*, Mul)
VTOPERATOR_CPPSCALAR(/, Div)
VTOPERATOR_CPPSCALAR_DOUBLE(/, Div)
VTOPERATOR_CPPSCALAR(%, Mod)
ARCH_PRAGMA_POP
 
PXR_NAMESPACE_CLOSE_SCOPE
 
#endif // PXR_BASE_VT_ARRAY_H