- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files
- Directories
- Examples

- File List
- File Members

# array.h

Go to the documentation of this file.

    00001
    00002 //**************************************************************************/
    00003 // Copyright (c) 2008 Autodesk, Inc.
    00004 // All rights reserved.
    00005 //
    00006 // Use of this software is subject to the terms of the Autodesk license
    00007 // agreement provided at the time of installation or download, or which
    00008 // otherwise accompanies this software in either electronic or hard copy form.
    00009 //
    00010 //**************************************************************************/
    00011 // DESCRIPTION:
    00012 // CREATED: October 2008
    00013 //**************************************************************************/
    00014
    00015 namespace mudbox {
    00016
    00017 void MBDLL_DECL QuickSort( void *pBase, unsigned int  iNum, unsigned int  iSize, int ( * fComparator ) ( const void *, const void * ) );
    00018
    00020 class MBDLL_DECL Block
    00021 {
    00022 protected:
    00023     Block( const char *sName, unsigned int iItemSize )
    00024     {
    00025         m_sName = sName;
    00026         m_pNext = s_pHead;
    00027         m_pPrev = 0;
    00028         if ( m_pNext ) m_pNext->m_pPrev = this;
    00029         s_pHead = this;
    00030         m_iItemSize = iItemSize;
    00031     };
    00032
    00033     ~Block( void );
    00034     Block *m_pNext, *m_pPrev;
    00035     unsigned int m_iItemSize;
    00036     static Block *s_pHead;
    00037
    00038 public:
    00039     inline static const Block *Head( void ) { return s_pHead; };
    00040     inline const Block *Next( void ) const { return m_pNext; };
    00041     inline unsigned int ItemSize( void ) const { return m_iItemSize; };
    00042
    00043     const char *Name( void ) const;
    00044     long long Size( void ) const;
    00045     long long Address( void ) const;
    00046     static void LogAll( float fSizeFilter = 0.01f, bool bSortByAddress = false );
    00047     void Check( void ) const;
    00048     static void CheckAll( void );
    00049     static bool RegisterMemoryBlock( long long iSize );
    00050     static bool UnregisterMemoryBlock( long long iSize );
    00051     static void SetAllocatorID( const char *pAllocatorID );
    00052     static void CopyMemoryBlock( void *pDestination, const void *pSource, long long iSize );
    00053
    00054     const char *m_sName;
    00055 };
    00056
    00058 template < typename type >
    00059 class MBDLL_TEMPLATE_DECL Array : public Block
    00060 {
    00061     friend class Block;
    00062 public:
    00063     Array( const char *sName ) : Block( sName, sizeof(type) )
    00064     {
    00065         m_bData = true;
    00066         m_iSize = 0;
    00067         m_pArray = 0;
    00068         m_pThis = this;
    00069     };
    00070     Array( const char *sName, unsigned int iSize ) : Block( sName, sizeof(type) )
    00071     {
    00072         m_bData = true;
    00073         m_iSize = iSize;
    00074         m_pArray = 0;
    00075         try
    00076         {
    00077             if ( RegisterMemoryBlock( sizeof(type)*iSize ) )
    00078             {
    00079                 SetAllocatorID( sName );
    00080                 m_pArray = new type[iSize];
    00081                 SetAllocatorID( 0 );
    00082             }
    00083             else
    00084                 throw &Error::s_cBadAlloc;
    00085         }
    00086         catch ( ... )
    00087         {
    00088             LogAll();
    00089             throw &Error::s_cBadAlloc;
    00090         };
    00091         m_pThis = this;
    00092     };
    00093     Array( const char *sName, const type *pArray, int iSize ) : Block( sName, sizeof(type) )
    00094     {
    00095         m_bData = true;
    00096         m_pArray = 0;
    00097         try
    00098         {
    00099             if ( RegisterMemoryBlock( sizeof(type)*iSize ) )
    00100             {
    00101                 SetAllocatorID( sName );
    00102                 m_pArray = new type[iSize];
    00103                 SetAllocatorID( 0 );
    00104             }
    00105             else
    00106                 Error::ThrowBadAlloc();
    00107         }
    00108         catch ( ... )
    00109         {
    00110             // probably std::bad_alloc
    00111             LogAll();
    00112             throw &Error::s_cBadAlloc;
    00113         };
    00114         if( !m_pArray )
    00115             return;
    00116
    00117         memcpy( m_pArray, pArray, sizeof(type)*iSize );
    00118         m_iSize = iSize;
    00119         m_pThis = this;
    00120     };
    00121     Array( const char *sName, bool bNoObjects ) : Block( sName, sizeof(type) )
    00122     {
    00123         m_bData = bNoObjects;
    00124         m_iSize = 0;
    00125         m_pArray = 0;
    00126         m_pThis = this;
    00127     };
    00128     Array( const char *sName, const Array<type> &a ) : Block( sName, sizeof(type) )
    00129     {
    00130         m_bData = true;
    00131         m_pArray = a.m_pArray;
    00132         m_iSize = a.m_iSize;
    00133         a.m_iSize = 0;
    00134         a.m_pArray = 0;
    00135         m_pThis = this;
    00136     };
    00137     void Clear( bool bDestruct = false )
    00138     {
    00139         bDestruct = bDestruct;
    00140
    00141         if ( m_pArray )
    00142         {
    00143             UnregisterMemoryBlock( (long long)(sizeof(type)*m_iSize) );
    00144 //          if ( bDestruct )
    00145                 delete [] m_pArray;
    00146 //          else
    00147 //              delete m_pArray;
    00148             m_pArray = 0;
    00149         };
    00150         m_iSize = 0;
    00151     };
    00152     inline Array<type> Clone( void ) const { Array<type> a; Copy( a ); return a; };
    00153     inline bool Copy( Array<type> &a ) const
    00154     {
    00155         if ( !a.Alloc( m_iSize ) )
    00156             return false;
    00157         memcpy( a.m_pArray, m_pArray, sizeof(type)*a.m_iSize );
    00158         return true;
    00159     };
    00160     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 ); };
    00161     inline bool Extend( unsigned int iElementIndex )
    00162     {
    00163         if ( iElementIndex == 0xffffffff )
    00164             return true;
    00165         unsigned int iNewSize = m_iSize;
    00166         while ( iElementIndex >= iNewSize )
    00167             iNewSize = iNewSize*2+1;
    00168         if( iNewSize > m_iSize )
    00169             return Alloc( iNewSize );
    00170         return true;
    00171     };
    00172     bool Alloc( unsigned int iNewSize )
    00173     {
    00174         if ( iNewSize == m_iSize )
    00175             return true;
    00176         MB_ASSERT( m_pThis == this );
    00177         type *pNew = 0;
    00178         try
    00179         {
    00180             if ( RegisterMemoryBlock( sizeof(type)*iNewSize ) )
    00181             {
    00182                 SetAllocatorID( m_sName );
    00183                 pNew = new type[iNewSize];
    00184                 SetAllocatorID( 0 );
    00185             }
    00186             else
    00187                 throw &Error::s_cBadAlloc;
    00188         }
    00189         catch ( Error * )
    00190         {
    00191             LogAll();
    00192             return false;
    00193         }
    00194         catch ( ... )
    00195         {
    00196             // probably std::bad_alloc
    00197             // not a good idea to call LogAll here, since that function also uses memory, and might fail. In that case stack overflow might happen.
    00198             //LogAll();
    00199             throw &Error::s_cBadAlloc;
    00200         };
    00201         if( pNew == 0 )
    00202             return false;
    00203         if( m_iSize )
    00204         {
    00205             UnregisterMemoryBlock( sizeof(type)*m_iSize );
    00206             if ( m_bData )
    00207                 CopyMemoryBlock( pNew, m_pArray, Min( iNewSize, m_iSize )*sizeof(type) );
    00208             else
    00209                 for ( unsigned int i = 0; i < Min( iNewSize, m_iSize ); i++ )
    00210                     pNew[i] = m_pArray[i];
    00211             delete [] m_pArray;
    00212         };
    00213         m_pArray = pNew;
    00214         m_iSize = iNewSize;
    00215         return true;
    00216     };
    00217
    00218     inline type &operator []( int iIndex )
    00219     {
    00220         MB_ASSERT( m_pThis == this );
    00221         MB_ONBUG( (unsigned int)(iIndex) >= m_iSize )
    00222             return m_pArray[0];
    00223         return m_pArray[iIndex];
    00224     };
    00225     inline type &operator []( unsigned int iIndex )
    00226     {
    00227         MB_ASSERT( m_pThis == this );
    00228         MB_ONBUG( iIndex >= m_iSize )
    00229             return m_pArray[0];
    00230         return m_pArray[iIndex];
    00231     };
    00232     inline const type &operator []( unsigned int iIndex )  const
    00233     {
    00234         MB_ASSERT( m_pThis == this );
    00235         MB_ONBUG( iIndex >= m_iSize )
    00236             return m_pArray[0];
    00237         return m_pArray[iIndex];
    00238     };
    00239     inline type *operator +( unsigned int iIndex ) { MB_ASSERT( m_pThis == this ); return &operator[]( iIndex ); };
    00240     inline type *operator +( int iIndex ) { MB_ASSERT( m_pThis == this ); return &operator[]( iIndex ); };
    00241     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; };
    00242
    00243 protected:
    00244
    00245     mutable type *m_pArray;
    00246     mutable unsigned int m_iSize;
    00247     mutable bool m_bData;
    00248     mutable const Array<type> *m_pThis;
    00249
    00250 public:
    00251     ~Array( void ) { MB_ASSERT( m_pThis == this ); Clear(); };
    00252     virtual long long MemoryUsage( void ) const { return m_iSize*sizeof(type); };
    00253 };
    00254
    00297
    00298 template < typename type >
    00299 class MBDLL_TEMPLATE_DECL Store : public Array<type>
    00300 {
    00301 public:
    00303     Store(
    00304         const char *sName = "unknown"
    00305         ) : Array<type>( sName ) { m_iSize = 0; };
    00306
    00315     Store(
    00316         unsigned int iSize,
    00317         const char *sName
    00318         ) : Array<type>( sName, iSize ) { m_iSize = iSize; };
    00319
    00325     Store(
    00326         const type *pArray,
    00327         int iSize,
    00328         const char *sName = "unknown"
    00329         ) : Array<type>( sName, pArray, iSize ) { m_iSize = iSize; };
    00330
    00332     Store(
    00333         bool bNoObjects,
    00334         const char *sName
    00335         ) : Array<type>( sName, bNoObjects ) { m_iSize = 0; };
    00336
    00338     Store(
    00339         const Store &s
    00340         ) : Array<type>( s.m_sName, s ) { m_iSize = s.m_iSize; s.m_iSize = 0; };
    00341
    00343     ~Store( void ) { Clear( !Array<type>::m_bData ); };
    00344
    00346     bool Copy(
    00347         Store &s
    00348         ) const { s.m_iSize = m_iSize; return Array<type>::Copy( s ); };
    00349
    00351     Store Clone( void ) const { Store s; s.SetItemCount( m_iSize ); Copy( s ); return s; };
    00352
    00354     void Clone(
    00355         Store &s
    00356         ) const { s.SetItemCount( m_iSize ); Copy( s ); };
    00357
    00359     inline void Clear(
    00360         bool bDestruct = false
    00361         ) { Array<type>::Clear( bDestruct ); m_iSize = 0; };
    00362
    00368     inline bool SetItemCount(
    00369         unsigned int iSize,
    00370         bool bKeepContent = false
    00371         )
    00372     {
    00373         if ( iSize <= m_iSize )
    00374         {
    00375             m_iSize = iSize;
    00376             return true;
    00377         };
    00378         if ( !bKeepContent )
    00379             Clear();
    00380         if ( Array<type>::Alloc( iSize ) )
    00381         {
    00382             m_iSize = iSize;
    00383             return true;
    00384         };
    00385         return false;
    00386     };
    00387
    00393     inline bool Allocate(
    00394         unsigned int iSize,
    00395         bool bKeepContent = false
    00396         ) { if ( !bKeepContent ) Clear(); return Array<type>::Alloc( iSize ); };
    00397
    00403     inline bool Extend(
    00404         unsigned int iIndex
    00405         )
    00406     {
    00407         if ( Array<type>::Extend( iIndex ) )
    00408         {
    00409             m_iSize = Max( m_iSize, iIndex+1 );
    00410             return true;
    00411         };
    00412         return false;
    00413     };
    00414
    00420     inline bool Extend(
    00421         int iIndex
    00422         ) { return Extend( (unsigned int)iIndex ); };
    00423
    00425     inline void RemoveTail(
    00426         int iItemCount = 1
    00427         ) { SetItemCount( ItemCount()-iItemCount ); };
    00428
    00430     inline void Fill(
    00431         type cPattern
    00432         ) { for ( unsigned int i = 0; i < m_iSize; i++ ) operator[](i) = cPattern; };
    00433
    00438     inline unsigned int Add(
    00439         const type &e
    00440         ) { if( Array<type>::Extend( m_iSize ) ) { Array<type>::operator[]( m_iSize ) = e; return m_iSize++; } else return 0xffffffff; };
    00441
    00446     inline unsigned int Add(
    00447         type &e
    00448         ) { if( Array<type>::Extend( m_iSize ) ) { Array<type>::operator[]( m_iSize ) = e; return m_iSize++; } else return 0xffffffff; };
    00449
    00453     inline Store &operator =( const Store &s ) { m_iSize = s.m_iSize; s.m_iSize = 0; Array<type>::operator =( s ); return *this; };
    00454
    00458     void GetFrom(
    00459         Store &s
    00460         ) { m_iSize = s.m_iSize; Array<type>::operator =( s ); };
    00461
    00463     const type &operator []( unsigned int iIndex ) const { return Array<type>::m_pArray[iIndex]; };
    00464
    00466     type &operator []( unsigned int iIndex ) { MB_ASSERT( iIndex < m_iSize ); return Array<type>::m_pArray[iIndex]; };
    00467
    00469     const type &operator []( int iIndex ) const { return operator[]( (unsigned int)iIndex ); };
    00470
    00472     type &operator []( int iIndex ) { return operator[]( (unsigned int)iIndex ); };
    00473
    00479     inline type *operator +( unsigned int iIndex ) { return &operator[]( iIndex ); };
    00480
    00486     inline type *operator +( int iIndex ) { return &operator[]( iIndex ); };
    00487
    00489     inline bool IsEmpty( void ) const { return ItemCount() == 0; };
    00490
    00492     inline operator bool( void ) const { return !IsEmpty(); };
    00493
    00495     inline bool operator !( void ) const { return IsEmpty(); };
    00496
    00506     void SetBuffer( type *pData, unsigned int iSize = 0 ) { m_iSize = Array<type>::m_iSize = iSize; Array<type>::m_pArray = pData; };
    00507
    00509     void Serialize(
    00510         class Stream &s
    00511                    );
    00512
    00525     inline void Sort( void ) { QuickSort( Array<type>::m_pArray, m_iSize, sizeof(type), Compare ); };
    00526
    00535     inline type *Find(
    00536         type a
    00537         ) { return (type *) bsearch( &a, Array<type>::m_pArray, m_iSize, sizeof(type), Compare ); };
    00538
    00547     inline type *Find( type *a ) { return (type *) bsearch( a, Array<type>::m_pArray, m_iSize, sizeof(type), Compare ); };
    00548
    00553     inline unsigned int IndexOf( type pValue )
    00554     {
    00555         for(unsigned int i = 0; i < ItemCount(); ++i )
    00556             if( (*this)[i] == pValue )
    00557                 return i;
    00558         return 0xffffffff;
    00559     };
    00560
    00562     unsigned int Remove(
    00563         const type &e
    00564         )
    00565     {
    00566         unsigned int j = 0, i = 0;
    00567         while ( i < ItemCount() )
    00568         {
    00569             if ( operator[]( i ) != e )
    00570                 operator[]( j++ ) = operator[]( i );
    00571             i++;
    00572         };
    00573         SetItemCount( j );
    00574         return i-j;
    00575     };
    00576
    00578     void RemoveAt(
    00579         unsigned int iIndex
    00580         )
    00581     {
    00582         while ( iIndex+1 < ItemCount( ) )
    00583         {
    00584             operator[]( iIndex ) = operator[]( iIndex+1 );
    00585             iIndex++;
    00586         };
    00587         SetItemCount( Min(iIndex,ItemCount()-1) );
    00588     };
    00589
    00596     unsigned int RemoveDuplicates( void )
    00597     {
    00598         if ( ItemCount() == 0 )
    00599             return 0;
    00600         Sort();
    00601         unsigned int j = 0;
    00602         for ( unsigned int i = 0; i < ItemCount()-1; i++ )
    00603         {
    00604             if ( operator[]( i ) != operator[]( i+1 ) )
    00605                 operator[]( j++ ) = operator[]( i );
    00606         };
    00607         operator[]( j++ ) = operator[]( ItemCount()-1 );
    00608         unsigned iRemoved = ItemCount()-j;
    00609         m_iSize = j;
    00610         return iRemoved;
    00611     };
    00612
    00614     inline unsigned int ItemCount( void ) const { return m_iSize; };
    00615
    00617     inline type &Last( void ) { if ( ItemCount() ) return operator []( ItemCount()-1 ); else throw new Error( "Store::LastItem called for an empty store" ); };
    00618
    00628     inline void Optimize( void ) { Array<type>::Alloc( m_iSize ); };
    00629
    00630 protected:
    00631     static int Compare( const void *a, const void *b ) { return (int)(*((type *)a)-*((type *)b)); };
    00632
    00633 public:
    00634     mutable unsigned int m_iSize;
    00635 };
    00636
    00637 }; // end of namespace mudbox
    00638