array.h

Go to the documentation of this file.

//
// Copyright 2016 Pixar
//
// Licensed under the Apache License, Version 2.0 (the "Apache License")
// with the following modification; you may not use this file except in
// compliance with the Apache License and the following modification to it:
// Section 6. Trademarks. is deleted and replaced with:
//
// 6. Trademarks. This License does not grant permission to use the trade
//    names, trademarks, service marks, or product names of the Licensor
//    and its affiliates, except as required to comply with Section 4(c) of
//    the License and to reproduce the content of the NOTICE file.
//
// You may obtain a copy of the Apache License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the Apache License with the above modification is
// distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, either express or implied. See the Apache License for the specific
// language governing permissions and limitations under the Apache 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/operators.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 <boost/functional/hash.hpp>
#include <boost/iterator_adaptors.hpp>
#include <boost/iterator/reverse_iterator.hpp>

#include <algorithm>
#include <atomic>
#include <cstddef>
#include <cstdlib>
#include <memory>
#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;
};

template<typename ELEM>
class VtArray : public Vt_ArrayBase {
  public:

    typedef ELEM ElementType;
    typedef ELEM value_type;

    template <typename Value>
    class PointerIterator
        : public boost::iterator_adaptor<PointerIterator<Value>, Value *> {
    public:
        PointerIterator() :
            PointerIterator::iterator_adaptor_(0) {}
        explicit PointerIterator(Value *p) :
            PointerIterator::iterator_adaptor_(p) {}
        template <typename OtherValue>
        PointerIterator(PointerIterator<OtherValue> const &other,
                        typename boost::enable_if_convertible
                        <OtherValue*, Value*>::type* = 0) :
            PointerIterator::iterator_adaptor_(other.base()) {}
      private:
        friend class boost::iterator_core_access;
    };


    typedef PointerIterator<ElementType> iterator;
    typedef PointerIterator<const ElementType> const_iterator;
    typedef boost::reverse_iterator<iterator> reverse_iterator;
    typedef boost::reverse_iterator<const_iterator> const_reverse_iterator;

    typedef typename PointerIterator<ElementType>::reference
        reference;
    typedef typename PointerIterator<const ElementType>::reference
        const_reference;
    typedef typename PointerIterator<ElementType>::pointer pointer;
    typedef typename PointerIterator<const ElementType>::pointer const_pointer;


    VtArray() : _data(nullptr) {}

    template <typename LegacyInputIterator>
    VtArray(LegacyInputIterator first, LegacyInputIterator last,
            typename std::enable_if<
                !std::is_integral<LegacyInputIterator>::value, 
                void>::type* = 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);
            _DecRef();
            _data = newData;
        }
        // Copy the value.
        ::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);
    }

    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) {
        struct _Filler {
            inline void operator()(pointer b, pointer e) const {
                std::uninitialized_fill(b, e, value_type());
            }
        };
        return resize(newSize, _Filler());
    }

    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.totalSize = 0;
    }

    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);
    }

ARCH_PRAGMA_PUSH
ARCH_PRAGMA_FORCING_TO_BOOL
ARCH_PRAGMA_UNSAFE_USE_OF_BOOL
ARCH_PRAGMA_UNARY_MINUS_ON_UNSIGNED
    VTOPERATOR_CPPARRAY(+)
    VTOPERATOR_CPPARRAY(-)
    VTOPERATOR_CPPARRAY(*)
    VTOPERATOR_CPPARRAY(/)
    VTOPERATOR_CPPARRAY(%)
    VTOPERATOR_CPPARRAY_UNARY(-)
ARCH_PRAGMA_POP

  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 VtStreamOutIterator {
    public:
        _Streamer(const_pointer data) : _p(data) { }
        virtual ~_Streamer() { }
        virtual void Next(std::ostream &out)
        {
            VtStreamOut(*_p++, out);
        }

    private:
        const_pointer _p;
    };

    friend std::ostream &operator <<(std::ostream &out, const VtArray &self) {
        VtArray::_Streamer streamer(self.cdata());
        VtStreamOutArray(&streamer, self.size(), self._GetShapeData(), out);
        return out;
    }

    friend void swap(VtArray &lhs, VtArray &rhs) {
        lhs.swap(rhs);
    }

    void _DetachIfNotUnique() {
        if (_IsUnique())
            return;
        // Copy to local.
        _DetachCopyHook(__ARCH_PRETTY_FUNCTION__);
        auto *newData = _AllocateCopy(_data, size(), size());
        _DecRef();
        _data = newData;
    }

    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.
        void *data = malloc(
            sizeof(_ControlBlock) + capacity * sizeof(value_type));
        // 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();
                }
                free(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;
};

template <class ELEM>
typename std::enable_if<VtIsHashable<ELEM>(), size_t>::type
hash_value(VtArray<ELEM> const &array) {
    size_t h = array.size();
    for (auto const &x: array) {
        boost::hash_combine(h, x);
    }
    return h;
}

// Specialize traits so others can figure out that VtArray is an array.
template <typename T>
struct VtIsArray< VtArray <T> > : public std::true_type {};

// 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(+)
VTOPERATOR_CPPSCALAR(-)
VTOPERATOR_CPPSCALAR(*)
VTOPERATOR_CPPSCALAR_DOUBLE(*)
VTOPERATOR_CPPSCALAR(/)
VTOPERATOR_CPPSCALAR_DOUBLE(/)
VTOPERATOR_CPPSCALAR(%)
ARCH_PRAGMA_POP

PXR_NAMESPACE_CLOSE_SCOPE

#endif // PXR_BASE_VT_ARRAY_H