array.h

Go to the documentation of this file.

//**************************************************************************/
// Copyright (c) 2008 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.
//
//**************************************************************************/
// DESCRIPTION:
// CREATED: October 2008
//**************************************************************************/

namespace mudbox {

void MBDLL_DECL QuickSort( void *pBase, unsigned int  iNum, unsigned int  iSize, int ( * fComparator ) ( const void *, const void * ) );

class MBDLL_DECL Block
{
protected:
    Block( const char *sName, unsigned int iItemSize )
    {                                                                     
        m_sName = sName;
        m_pNext = s_pHead;
        m_pPrev = 0;
        if ( m_pNext ) m_pNext->m_pPrev = this;
        s_pHead = this;
        m_iItemSize = iItemSize;
    };

    ~Block( void );
    Block *m_pNext, *m_pPrev;
    unsigned int m_iItemSize;
    static Block *s_pHead;

public:
    inline static const Block *Head( void ) { return s_pHead; };
    inline const Block *Next( void ) const { return m_pNext; };
    inline unsigned int ItemSize( void ) const { return m_iItemSize; };

    const char *Name( void ) const;
    long long Size( void ) const;
    long long Address( void ) const;
    static void LogAll( float fSizeFilter = 0.01f, bool bSortByAddress = false );
    void Check( void ) const;
    static void CheckAll( void );
    static bool RegisterMemoryBlock( long long iSize );
    static bool UnregisterMemoryBlock( long long iSize );
    static void SetAllocatorID( const char *pAllocatorID );
    static void CopyMemoryBlock( void *pDestination, const void *pSource, long long iSize );

    // Allocates iBytes aligned to iAlignment boundaries. iAlignment must be a positive power of two.
    static void* AlignedAlloc( size_t iBytes, unsigned int iAlignment );
    
    // Frees memory allocated with AlignedAlloc
    static void AlignedFree( void* pData );
    
    const char *m_sName;
};

template < typename type >
class MBDLL_TEMPLATE_DECL Array : public Block
{
    friend class Block;
public:
    Array( const char *sName ) : Block( sName, sizeof(type) )
    { 
        m_bData  = true; 
        m_iSize  = 0; 
        m_pArray = 0; 
        m_pThis  = this;
    };
    Array( const char *sName, unsigned int iSize ) : Block( sName, sizeof(type) ) 
    { 
        m_bData  = true; 
        m_iSize  = iSize;
        m_pArray = 0;
        try
        {
            if ( RegisterMemoryBlock( sizeof(type)*iSize ) )
            {
                SetAllocatorID( sName );
                m_pArray = new type[iSize];
                SetAllocatorID( 0 );
            }
            else
                throw &Error::s_cBadAlloc;
        }
        catch ( ... )
        {
            LogAll();
            throw &Error::s_cBadAlloc;
        };
        m_pThis = this;
    };
    Array( const char *sName, const type *pArray, int iSize ) : Block( sName, sizeof(type) )
    { 
        m_bData  = true; 
        m_pArray = 0;
        try
        {
            if ( RegisterMemoryBlock( sizeof(type)*iSize ) )
            {
                SetAllocatorID( sName );
                m_pArray = new type[iSize];
                SetAllocatorID( 0 );
            }
            else
                Error::ThrowBadAlloc();
        }
        catch ( ... )
        {
            // probably std::bad_alloc
            LogAll();
            throw &Error::s_cBadAlloc;
        };
        if ( !m_pArray )
            return;

        memcpy( m_pArray, pArray, sizeof(type)*iSize ); 
        m_iSize = iSize; 
        m_pThis = this;
    };

    Array( const char *sName, bool bNoObjects ) : Block( sName, sizeof(type) )
    { 
        m_bData  = bNoObjects; 
        m_iSize  = 0; 
        m_pArray = 0; 
        m_pThis  = this;
    };

    Array( const char *sName, const Array<type> &a ) : Block( sName, sizeof(type) )
    { 
        m_bData    = true; 
        m_pArray   = a.m_pArray; 
        m_iSize    = a.m_iSize; 
        a.m_iSize  = 0; 
        a.m_pArray = 0; 
        m_pThis    = this;
    };

    void Clear( bool bDestruct = false ) 
    { 
        bDestruct = bDestruct;

        if ( m_pArray ) 
        {   
            UnregisterMemoryBlock( (long long)(sizeof(type)*m_iSize) );
//          if ( bDestruct )
                delete [] m_pArray; 
//          else
//              delete m_pArray;
            m_pArray = 0; 
        }; 
        m_iSize = 0; 
    };

    inline Array<type> Clone( void ) const { Array<type> a; Copy( a ); return a; };

    inline bool Copy( Array<type> &a ) const 
    { 
        if ( !a.Alloc( m_iSize ) )
            return false; 
        memcpy( a.m_pArray, m_pArray, sizeof(type)*a.m_iSize ); 
        return true;
    };

    inline void Set( unsigned int iStart, unsigned int iSize, unsigned char cPattern ) 
    { MB_ASSERT( m_pThis == this ); MB_ASSERT( iStart+iSize <= m_iSize ); memset( m_pArray+iStart, int(cPattern), sizeof(type)*iSize ); };

    inline bool Extend( unsigned int iElementIndex )
    {
        if ( iElementIndex == 0xffffffff )
            return true;
        unsigned int iNewSize = m_iSize;
        while ( iElementIndex >= iNewSize )
            iNewSize = iNewSize*2+1;
        if( iNewSize > m_iSize )
            return Alloc( iNewSize );
        return true;
    };

    bool Alloc( unsigned int iNewSize )
    {
        if ( iNewSize == m_iSize )
            return true;
        MB_ASSERT( m_pThis == this ); 
        type *pNew = 0;
        try
        {
            if ( RegisterMemoryBlock( sizeof(type)*iNewSize ) )
            {
                SetAllocatorID( m_sName );
                pNew = new type[iNewSize];
                SetAllocatorID( 0 );
            }
            else
                throw &Error::s_cBadAlloc;      
        }
        catch ( Error * )
        {
            LogAll();
            return false;
        }
        catch ( ... )
        {
            // probably std::bad_alloc
            // not a good idea to call LogAll here, since that function also uses memory, and might fail. In that case stack overflow might happen.
            //LogAll();
            throw &Error::s_cBadAlloc;
        };
        if ( pNew == 0 )
            return false;
        if ( m_iSize )
        {
            UnregisterMemoryBlock( sizeof(type)*m_iSize );
            if ( m_bData )          
                CopyMemoryBlock( pNew, m_pArray, Min( iNewSize, m_iSize )*sizeof(type) );
            else
                for ( unsigned int i = 0; i < Min( iNewSize, m_iSize ); i++ )
                    pNew[i] = m_pArray[i];
            delete [] m_pArray;
        };
        m_pArray = pNew;
        m_iSize  = iNewSize;
        return true;
    };

    inline type &operator []( int iIndex )
    { 
        MB_ASSERT( m_pThis == this ); 
        MB_ONBUG( (unsigned int)(iIndex) >= m_iSize )
            return m_pArray[0];
        return m_pArray[iIndex]; 
    };

    inline type &operator []( unsigned int iIndex ) 
    { 
        MB_ASSERT( m_pThis == this ); 
        MB_ONBUG( iIndex >= m_iSize ) 
            return m_pArray[0];
        return m_pArray[iIndex];
    };

    inline const type &operator []( unsigned int iIndex )  const
    { 
        MB_ASSERT( m_pThis == this ); 
        MB_ONBUG( iIndex >= m_iSize )
            return m_pArray[0];
        return m_pArray[iIndex]; 
    };


    // these are unsafe......
    inline type *indexedAddr(unsigned int i)             { return &operator[]( i ); };
    inline const type *indexedAddr(unsigned int i) const { return &operator[]( i ); };

    inline type *baseAddr()             { return &operator[]( 0 ); };
    inline const type *baseAddr() const { return &operator[]( 0 ); };

    inline void operator =( const Array<type> &a ) 
    { MB_ASSERT( m_pThis == this && a.m_pThis == &a ); Clear(); m_iSize = a.m_iSize; m_pArray = a.m_pArray; a.m_iSize = 0; a.m_pArray = 0; };

protected:
    mutable type              *m_pArray;
    mutable unsigned int       m_iSize;
    mutable bool               m_bData;
    mutable const Array<type> *m_pThis;

private:
    // removing these and replacing them with baseAddr/indexedAddr will make it far easier to see or grep
    // where we are leaking addresses of elements. DEPRECATED. DO NOT USE. IT ALWAYS RETURNs 0
    // 
    inline type *operator +( unsigned int iIndex ) { MB_ASSERT( 0 /*m_pThis == this*/ ); return 0; /*&operator[]( iIndex );*/ };
    inline type *operator +( int iIndex ) { MB_ASSERT( 0 /*m_pThis == this*/ ); return 0; /*&operator[]( iIndex );*/ };

public:
    ~Array( void ) { MB_ASSERT( m_pThis == this ); Clear(); };
};


template < typename type >
class MBDLL_TEMPLATE_DECL Store : public Array<type>
{
public:
    Store(
        const char *sName = "unknown"       
        ) : Array<type>( sName ) { m_iSize = 0; };
        
    Store(
        unsigned int iSize,     
        const char *sName       
        ) : Array<type>( sName, iSize ) { m_iSize = iSize; };
        
    Store(
        const type *pArray,             
        int iSize,                      
        const char *sName = "unknown"   
        ) : Array<type>( sName, pArray, iSize ) { m_iSize = iSize; };
        
    Store(
        bool bNoObjects,    
        const char *sName   
        ) : Array<type>( sName, bNoObjects ) { m_iSize = 0; };
        
    Store(
        const Store &s  
        ) : Array<type>( s.m_sName, s ) { m_iSize = s.m_iSize; s.m_iSize = 0; };
        
    ~Store( void ) { Clear( !Array<type>::m_bData ); };

    bool Copy(
        Store &s    
        ) const { s.m_iSize = m_iSize; return Array<type>::Copy( s ); };
    
    Store Clone( void ) const { Store s; s.SetItemCount( m_iSize ); Copy( s ); return s; };
    
    void Clone(
        Store &s    
        ) const { s.SetItemCount( m_iSize ); Copy( s ); };

    inline void Clear(
        bool bDestruct = false  
        ) { Array<type>::Clear( bDestruct ); m_iSize = 0; };
        
    inline bool SetItemCount(
        unsigned int iSize,         
        bool bKeepContent = false   
        ) 
    { 
        if ( iSize <= m_iSize )
        {
            m_iSize = iSize;
            return true;
        };
        if ( !bKeepContent ) 
            Clear(); 
        if ( Array<type>::Alloc( iSize ) ) 
        { 
            m_iSize = iSize; 
            return true; 
        };
        return false;
    };
    
    inline bool Allocate(
        unsigned int iSize,         
        bool bKeepContent = false   
        ) { if ( !bKeepContent ) Clear(); return Array<type>::Alloc( iSize ); };
        
    inline bool Extend(
        unsigned int iIndex     
        )
    { 
        if ( Array<type>::Extend( iIndex ) )
        {
            m_iSize = Max( m_iSize, iIndex+1 );
            return true;
        };
        return false;
    };
    
    inline bool Extend(
        int iIndex  
        ) { return Extend( (unsigned int)iIndex ); };
        
    inline void RemoveTail(
        int iItemCount = 1      
        ) { SetItemCount( ItemCount()-iItemCount ); };
        
    inline void Fill(
        type cPattern       
        ) { for ( unsigned int i = 0; i < m_iSize; i++ ) operator[](i) = cPattern; };

    inline void ByteFill(
        unsigned char cPattern  
        ) { memset( Array<type>::m_pArray, (unsigned int)cPattern, sizeof(type) * m_iSize ); }

    inline unsigned int Add(
        const type &e   
        ) { if( Array<type>::Extend( m_iSize ) ) { Array<type>::operator[]( m_iSize ) = e; return m_iSize++; } else return 0xffffffff; };
    
    inline unsigned int Add(
        type &e 
        ) { if( Array<type>::Extend( m_iSize ) ) { Array<type>::operator[]( m_iSize ) = e; return m_iSize++; } else return 0xffffffff; };

    inline Store &operator =( const Store &s ) { m_iSize = s.m_iSize; s.m_iSize = 0; Array<type>::operator =( s ); return *this; };
    
    void GetFrom(
        Store &s    
        ) { m_iSize = s.m_iSize; Array<type>::operator =( s ); };
    
    const type &operator []( unsigned int iIndex ) const { return Array<type>::m_pArray[iIndex]; };
    
    type &operator []( unsigned int iIndex ) { MB_ASSERT( iIndex < m_iSize ); return Array<type>::m_pArray[iIndex]; };
    
    const type &operator []( int iIndex ) const { return operator[]( (unsigned int)iIndex ); };
    
    type &operator []( int iIndex ) { return operator[]( (unsigned int)iIndex ); };
    
    
    inline bool IsEmpty( void ) const { return ItemCount() == 0; };
    
    inline operator bool( void ) const { return !IsEmpty(); };
    
    inline bool operator !( void ) const { return IsEmpty(); };

    void SetBuffer( type *pData, unsigned int iSize = 0 ) { m_iSize = Array<type>::m_iSize = iSize; Array<type>::m_pArray = pData; };

    void Serialize(         // currently implemented in stream.h
        class Stream &s     
                   );

    inline void Sort( void ) { QuickSort( Array<type>::m_pArray, m_iSize, sizeof(type), Compare ); };
    
    inline type *Find(
        type a      
        ) { return (type *) bsearch( &a, Array<type>::m_pArray, m_iSize, sizeof(type), Compare ); };
    
    inline type *Find( type *a ) { return (type *) bsearch( a, Array<type>::m_pArray, m_iSize, sizeof(type), Compare ); };
    
    inline unsigned int IndexOf( type pValue )
    {
        for(unsigned int i = 0; i < ItemCount(); ++i )
            if( (*this)[i] == pValue )
                return i;
        return 0xffffffff;
    };

    unsigned int Remove(
        const type &e   
        )
    {
        unsigned int j = 0, i = 0;
        while ( i < ItemCount() )
        {
            if ( operator[]( i ) != e )
                operator[]( j++ ) = operator[]( i );
            i++;
        };
        SetItemCount( j );
        return i-j;
    };

    void RemoveAt(
        unsigned int iIndex     
        )
    {
        while ( iIndex+1 < ItemCount( ) )
        {
            operator[]( iIndex ) = operator[]( iIndex+1 );
            iIndex++;
        };
        SetItemCount( Min(iIndex,ItemCount()-1) );
    };
    
    unsigned int RemoveDuplicates( void )
    {
        if ( ItemCount() == 0 )
            return 0;
        Sort();
        unsigned int j = 0;
        for ( unsigned int i = 0; i < ItemCount()-1; i++ )
        {
            if ( operator[]( i ) != operator[]( i+1 ) )
                operator[]( j++ ) = operator[]( i );
        };
        operator[]( j++ ) = operator[]( ItemCount()-1 );
        unsigned iRemoved = ItemCount()-j;
        m_iSize = j;
        return iRemoved;
    };

    inline unsigned int ItemCount( void ) const { return m_iSize; };
    
    inline type &Last( void ) { if ( ItemCount() ) return operator []( ItemCount()-1 ); else throw new Error( "Store::LastItem called for an empty store" ); };

    inline void Optimize( void ) { Array<type>::Alloc( m_iSize ); };

protected:
    static int Compare( const void *a, const void *b ) { return (int)(*((type *)a)-*((type *)b)); };

private:
    inline type *operator +( unsigned int iIndex ) { return 0; /* &operator[]( iIndex ); */ };
    
    inline type *operator +( int iIndex ) { return 0; /* &operator[]( iIndex ); */ };

public:
    mutable unsigned int m_iSize;
};

template<typename T>
class ExtendableStore
{
    unsigned int m_iLogicalItemCount;
    
    const unsigned int m_iBlockItemCount;
    const unsigned int m_iBlockPow;
    const unsigned int m_iBlockMask;
    
    const unsigned int m_iAlignment;

    Store< T* > m_aBlocks;

public:
    
    ExtendableStore() :
        m_iBlockItemCount(16384),
        m_iBlockPow(14),
        m_iBlockMask(0x3FFF),
        m_iLogicalItemCount(0),
        m_iAlignment(16)
    {
        
    };
    
    ~ExtendableStore() 
    {
        Clear();
    };

    inline unsigned int ItemCount() const { return m_iLogicalItemCount; }
    
    inline void SetItemCount(
        unsigned int iCount     
        ) { if( iCount == 0 ) Clear(); else Extend( iCount-1 ); m_iLogicalItemCount = iCount; }

    inline void Clear()
    {
        m_iLogicalItemCount = 0;
        for( unsigned int i = 0; i < m_aBlocks.ItemCount(); ++i )
        {
            Block::AlignedFree( (void*)m_aBlocks[i] );
        }
        m_aBlocks.Clear();
    }

    inline void Add( 
        const T& t  
        )
    {
        const unsigned int c = ItemCount();
        Extend(c);
        operator[](c) = t;
    }

    inline void Extend( 
        unsigned int iIndex 
        )
    {
        const unsigned int iBlock = iIndex >> m_iBlockPow;

        // extend the logical item count to include iIndex
        m_iLogicalItemCount = Max( iIndex + 1, m_iLogicalItemCount );

        // if this block has already be allocated we are done.
        if( iBlock < m_aBlocks.ItemCount() )
            return;

        // allocate enough blocks to include iIndex
        const unsigned int ic = m_aBlocks.ItemCount();
        m_aBlocks.Extend( iBlock );
        for( unsigned int i = ic; i < m_aBlocks.ItemCount(); ++i )
        {
            T* pNewBlock = (T*)Block::AlignedAlloc( sizeof(T) * m_iBlockItemCount, m_iAlignment );
            MB_ASSERT( ((size_t) pNewBlock) % m_iAlignment == 0 );
            m_aBlocks[i] = pNewBlock;
        }
    }

    inline void Fill( 
        T cPattern 
        )
    { 
        for ( unsigned int i = 0; i < m_aBlocks.ItemCount(); i++ )
            for( unsigned int j = 0; j < m_iBlockItemCount; ++j )
                m_aBlocks[i][j] = cPattern;
    }

    inline unsigned int IndexOf( const T& pValue ) const
    {
        for(unsigned int i = 0; i < ItemCount(); ++i )
            if( (*this)[i] == pValue )
                return i;
        return 0xffffffff;
    };

    inline T &Last( void ) { if ( ItemCount() ) return operator []( ItemCount()-1 ); else throw new Error( "ExtenableStore::LastItem called for an empty store" ); };

    inline T &operator []( unsigned int iIndex )
    { 
        const unsigned int iBlock = iIndex >> m_iBlockPow;
        const unsigned int iBlockItem = iIndex & m_iBlockMask;
        return m_aBlocks[ iBlock ][iBlockItem];
    }

    inline const T &operator []( unsigned int iIndex ) const
    { 
        const unsigned int iBlock = iIndex >> m_iBlockPow;
        const unsigned int iBlockItem = iIndex & m_iBlockMask;
        return m_aBlocks[ iBlock ][iBlockItem];
    }

    void Serialize( Stream& s ); // This is defined in Stream.h
};





}; // end of namespace mudbox