fbxarray.h

Go to the documentation of this file.

/****************************************************************************************
 
   Copyright (C) 2017 Autodesk, Inc.
   All rights reserved.
 
   Use of this software is subject to the terms of the Autodesk license agreement
   provided at the time of installation or download, or which otherwise accompanies
   this software in either electronic or hard copy form.
 
****************************************************************************************/

#ifndef _FBXSDK_CORE_BASE_ARRAY_H_
#define _FBXSDK_CORE_BASE_ARRAY_H_

#include <fbxsdk/fbxsdk_def.h>

#include <fbxsdk/fbxsdk_nsbegin.h>

#if defined(FBXSDK_COMPILER_MSC)
    #pragma warning( push )
    #pragma warning( disable : 4201 ) // nonstandard extension used: nameless struct/union
#endif

#ifdef THROW_EXCEPTIONS
    #define FBX_THROW(x) throw std::runtime_error(x)
    #define FBX_ARRAY_INLINE __forceinline
#else
    #define FBX_THROW(x) FBX_ASSERT_NOW(x)
    #define FBX_ARRAY_INLINE inline
#endif


template <class T, const int Alignment = 16> class FbxArray
{
protected:
    struct tData {
        union {
            struct {
                int    mSize;
                int    mCapacity;
            };
            char Padding[Alignment];
        };
        T    mArray[15];        
    } *mData;
public:
    typedef int (*CompareFunc)(const void*, const void*);

    FbxArray() : mData(NULL){}

    FbxArray(const int pCapacity) : mData(NULL){ if( pCapacity > 0 ) Reserve(pCapacity); }

    FbxArray(const FbxArray& pArray) : mData(NULL){ *this = pArray; }

    ~FbxArray(){ Clear(); }

    inline int InsertAt(const int pIndex, const T& pElement, bool pCompact=false)
    {
        FBX_ASSERT_RETURN_VALUE(pIndex >= 0, -1);
        int lIndex = FbxMin(pIndex, GetSize());
        if( GetSize() >= GetCapacity() )
        {
            T lElement = pElement;    //Copy element because we might move memory
            int lNewCapacity = FbxMax(pCompact ? GetCapacity() + 1 : GetCapacity() * 2, 1);    //We always double capacity when not compacting
            Allocate(lNewCapacity);
            FBX_ASSERT_RETURN_VALUE(mData, -1);
            mData->mCapacity = lNewCapacity;
            return InsertAt(pIndex, lElement);    //Insert copied element because reference might be moved
        }

        if( lIndex < GetSize() )    //Move elements to leave a space open to insert the new element
        {
            //If pElement is inside memmove range, copy element and insert copy instead
            if( (&pElement >= &GetArray()[lIndex]) && (&pElement < &GetArray()[GetSize()]) )
            {
                T lElement = pElement;
                return InsertAt(pIndex, lElement);
            }
            memmove(&GetArray()[lIndex + 1], &GetArray()[lIndex], (GetSize() - lIndex) * sizeof(T));
        }

        memcpy(&GetArray()[lIndex], &pElement, sizeof(T));
        mData->mSize++;

        return lIndex;
    }

    inline int Add(const T& pElement)
    {
        int lIndex = GetSize();

        if (lIndex >= GetCapacity())
        {
            T lElement = pElement;    //Copy element because we might move memory
            int lNewCapacity = FbxMax(GetCapacity() * 2, 1);    //We always double capacity
            Allocate(lNewCapacity);
            FBX_ASSERT_RETURN_VALUE(mData, -1);
            mData->mCapacity = lNewCapacity;
            return Add(lElement);    //Insert copied element because reference might be moved
        }

        memcpy(&GetArray()[lIndex], &pElement, sizeof(T));
        mData->mSize++;

        return lIndex;
    }

    inline int AddUnique(const T& pElement)
    {
        int lIndex = Find(pElement);
        return ( lIndex == -1 ) ? Add(pElement) : lIndex;
    }

    inline int AddCompact(const T& pElement)
    {
        return InsertAt(GetSize(), pElement, true);
    }

    inline int Size() const { return GetSize(); }

    inline int Capacity() const { return GetCapacity(); }

    FBX_ARRAY_INLINE T& operator[](const int pIndex) const
    {
        if (pIndex < 0)
        {
            FBX_THROW("Index is out of range!");
        }

        if (pIndex >= GetSize())
        {
            if (pIndex < GetCapacity())
            {
                FBX_THROW("Index is out of range, but not outside of capacity! Call SetAt() to use reserved memory.");
            }

            FBX_THROW("Index is out of range!");
        }

        return GetArray()[pIndex];
    }

    inline T GetAt(const int pIndex) const
    {
        return operator[](pIndex);
    }

    inline T GetFirst() const
    {
        return GetAt(0);
    }

    inline T GetLast() const
    {
        return GetAt(GetSize() - 1);
    }

    inline int Find(const T& pElement, const int pStartIndex = 0) const
    {
        const int size = GetSize();

        FBX_ASSERT_RETURN_VALUE(pStartIndex >= 0, -1);
        FBX_ASSERT_RETURN_VALUE(size >= 0, -1);

        for (int i = pStartIndex; i < size; ++i)
        {
            if (GetArray()[i] == pElement) return i;
        }
        return -1;
    }

    inline int FindReverse(const T& pElement, const int pStartIndex = FBXSDK_INT_MAX) const
    {
        const int size = GetSize();

        FBX_ASSERT_RETURN_VALUE(size > 0, -1);

        for (int i = FbxMin(pStartIndex, size - 1); i >= 0; --i)
        {
            if (GetArray()[i] == pElement) return i;
        }
        return -1;
    }

    inline bool Reserve(const int pCapacity)
    {
        FBX_ASSERT_RETURN_VALUE(pCapacity >= 0, false);
        if( pCapacity > GetCapacity() )
        {
            Allocate(pCapacity);
            FBX_ASSERT_RETURN_VALUE(mData, false);
            mData->mCapacity = pCapacity;

            //Initialize new memory to zero
            memset(&GetArray()[GetSize()], 0, (GetCapacity() - GetSize()) * sizeof(T));
        }
        return true;
    }

    inline void SetAt(const int pIndex, const T& pElement)
    {
        FBX_ASSERT_RETURN(pIndex >= 0 && pIndex < GetCapacity());
        if( pIndex >= GetSize() ) mData->mSize = pIndex + 1;

        T* const array = GetArray();
        if (array) memcpy(&array[pIndex], &pElement, sizeof(T));
    }

    inline void SetFirst(const T& pElement)
    {
        SetAt(0, pElement);
    }

    inline void SetLast(const T& pElement)
    {
        SetAt(GetSize() - 1, pElement);
    }

    FBX_ARRAY_INLINE T RemoveAt(const int pIndex)
    {
        const int size = GetSize();
        const int index = pIndex + 1;
        if (index < 0 || index > size)
        {
            FBX_THROW("Index is out of range!");
        }

        T lElement = GetAt(pIndex);
        if (index < size)
        {
            memmove(&GetArray()[pIndex], &GetArray()[index], (size - pIndex - 1) * sizeof(T));
        }
        mData->mSize--;
        return lElement;
    }

    inline T RemoveFirst()
    {
        return RemoveAt(0);
    }

    inline T RemoveLast()
    {
        return RemoveAt(GetSize() - 1);
    }

    inline bool RemoveIt(const T& pElement)
    {
        int Index = Find(pElement);
        if( Index >= 0 )
        {
            RemoveAt(Index);
            return true;
        }
        return false;
    }

    inline void RemoveRange(const int pIndex, const int pCount)
    {
        const int size = GetSize();
        if (size == 0)
            // the array is already empty (or not allocated yet)
            // no point in continuing
            return;

        FBX_ASSERT(GetArray() != NULL);
        FBX_ASSERT_RETURN(pCount >  0);
        FBX_ASSERT_RETURN(pIndex >= 0);

        size_t lastItem = pIndex + pCount;
        FBX_ASSERT_RETURN(lastItem >= 0);
        FBX_ASSERT_RETURN(lastItem <= (size_t)size);
        FBX_ASSERT_RETURN(lastItem < FBXSDK_INT_MAX);

        if (lastItem < (size_t)size)
        {
            memmove(&GetArray()[pIndex], &GetArray()[pIndex + pCount], (size - pIndex - pCount) * (unsigned)sizeof(T));
        }

        if (mData)
        {
            mData->mSize -= pCount;
        }
    }

    inline bool ResizeUninitialized(const int pSize, bool pPreserveCapacityIfPossible = false)
    {
        if( pSize == GetSize() && GetSize() == GetCapacity() ) return true;

        if( pSize == 0 )
        {
            Clear();
            return true;
        }

        FBX_ASSERT_RETURN_VALUE(pSize > 0, false);

        bool lReallocate;
        if (pPreserveCapacityIfPossible)
            lReallocate = pSize > GetCapacity();
        else
            lReallocate = pSize != GetCapacity();
        
        if (lReallocate)
        {
            Allocate(pSize);
            FBX_ASSERT_RETURN_VALUE(mData, false);
            mData->mCapacity = pSize;
        }

        mData->mSize = pSize;
        return true;
    }

    inline bool Resize(const int pSize, bool pPreserveCapacityIfPossible = false)
    {
        if (pSize == GetSize() && GetSize() == GetCapacity()) return true;

        if (pSize == 0)
        {
            Clear();
            return true;
        }

        FBX_ASSERT_RETURN_VALUE(pSize > 0, false);

        bool lReallocate;
        if (pPreserveCapacityIfPossible)
            lReallocate = pSize > GetCapacity();
        else
            lReallocate = pSize != GetCapacity();

        if (lReallocate)
        {
            Allocate(pSize);
            FBX_ASSERT_RETURN_VALUE(mData, false);

            if (pSize > GetCapacity())    //Initialize new memory to zero
            {
                memset(&GetArray()[GetSize()], 0, (pSize - GetSize()) * sizeof(T));
            }
        
            mData->mCapacity = pSize;
        }

        mData->mSize = pSize;
        return true;
    }

    inline bool Grow(const int pSize)
    {
        const int size = GetSize();

        // Check int32 paramater does not overflow
        FbxLongLong newSize = static_cast<FbxLongLong>(size) + static_cast<FbxLongLong>(pSize);
        if (newSize > INT_MAX)
        {
            return false;
        }

        return Resize(size + pSize);
    }

    inline bool Shrink(const int pSize)
    {
        const int size = GetSize();

        // Check int32 paramater does not overflow
        FbxLongLong newSize = static_cast<FbxLongLong>(size) - static_cast<FbxLongLong>(pSize);
        if (pSize < 0 || newSize < 0 || newSize > size)
        {
            return false;
        }

        return Resize(size - pSize);
    }

    inline bool Compact()
    {
        return Resize(GetSize());
    }

    inline void Clear()
    {
        if( mData != NULL )
        {
            FbxFree(mData);
            mData = NULL;
        }
    }

    inline void Sort(CompareFunc pCompareFunc)
    {
        qsort(GetArray(), GetSize(), sizeof(T), pCompareFunc);
    }

    inline T* GetArray() const { return mData ? &mData->mArray[0] : NULL; }

    inline operator T* () const { return GetArray(); }

    inline void AddArray(const FbxArray<T>& pOther)
    {
        if( Grow(pOther.GetSize()) )
        {
            memcpy(&GetArray()[GetSize() - pOther.GetSize()], pOther.GetArray(), pOther.GetSize() * sizeof(T));
        }
    }

    inline void AddArrayNoDuplicate(const FbxArray<T>& pOther)
    {
        for( int i = 0, c = pOther.GetSize(); i < c; ++i )
        {
            AddUnique(pOther[i]);
        }
    }

    inline void RemoveArray(const FbxArray<T>& pOther)
    {
        for( int i = 0, c = pOther.GetSize(); i < c; ++i )
        {
            RemoveIt(pOther[i]);
        }
    }

    inline FbxArray<T>& operator=(const FbxArray<T>& pOther)
    {
        if( this != &pOther )
        {
            if( Resize(pOther.GetSize()) )
            {
                memcpy(GetArray(), pOther.GetArray(), pOther.GetSize() * sizeof(T));
            }
        }
        return *this;
    }

    inline bool operator==(const FbxArray<T>& pOther) const
    {
        if( this == &pOther ) return true;
        if( GetSize() != pOther.GetSize() ) return false;
        return memcmp(GetArray(), pOther.GetArray(), sizeof(T) * GetSize()) == 0;
    }

/*****************************************************************************************************************************
** WARNING! Anything beyond these lines is for internal use, may not be documented and is subject to change without notice! **
*****************************************************************************************************************************/
#ifndef DOXYGEN_SHOULD_SKIP_THIS
    inline int GetCount() const { return mData ? mData->mSize : 0; }

private:
    inline void Allocate(const int pCapacity)
    {
        tData* lOldData = mData;
        tData* lData = (tData*)FbxRealloc(mData, (size_t)Alignment + FbxAllocSize(pCapacity, sizeof(T)));
        if (lData)
        {
            mData = lData;
            if (!lOldData)
            {
                mData->mSize = 0;
                mData->mCapacity = 0;
            }
        }
        else
        {
            mData = NULL;
        }
    }

    inline int GetSize() const { return mData ? mData->mSize : 0; }
    inline int GetCapacity() const { return mData ? mData->mCapacity : 0; }

#if defined(FBXSDK_COMPILER_MSC)
    //Previously class FbxArray is for pointers. Somehow, it's used to store other types. Here's a compile-time checking for known incompatible classes.
    //If it happens you find new incompatible ones, declare them with macro FBXSDK_INCOMPATIBLE_WITH_ARRAY. Also see file fbxstring.h.
    FBX_ASSERT_STATIC(FBXSDK_IS_SIMPLE_TYPE(T) || __is_enum(T) || (__has_trivial_constructor(T)&&__has_trivial_destructor(T)) || !FBXSDK_IS_INCOMPATIBLE_WITH_ARRAY(T));
#endif

#endif /* !DOXYGEN_SHOULD_SKIP_THIS *****************************************************************************************/
};

#if defined(FBXSDK_COMPILER_MSC)
    #pragma warning( pop )
#endif

template <class T> inline void FbxArrayFree(FbxArray<T>& pArray)
{
    for( int i = 0, c = pArray.Size(); i < c; ++i )
    {
        FbxFree(pArray[i]);
    }
    pArray.Clear();
}

template <class T> inline void FbxArrayDelete(FbxArray<T>& pArray)
{
    for( int i = 0, c = pArray.Size(); i < c; ++i )
    {
        FbxDelete(pArray[i]);
    }
    pArray.Clear();
}

template <class T> inline void FbxArrayDestroy(FbxArray<T>& pArray)
{
    for( int i = 0, c = pArray.Size(); i < c; ++i )
    {
        (pArray[i])->Destroy();
    }
    pArray.Clear();
}

template <class T> FBXSDK_INCOMPATIBLE_WITH_ARRAY_TEMPLATE(FbxArray<T>);

#include <fbxsdk/fbxsdk_nsend.h>

#undef FBX_ARRAY_INLINE
#undef FBX_THROW

#endif /* _FBXSDK_CORE_BASE_ARRAY_H_ */