Version
menu_open

include/AK/Tools/Common/AkArray.h

Go to the documentation of this file.
00001 
00002 //
00003 // Copyright (c) 2006 Audiokinetic Inc. / All Rights Reserved
00004 //
00006 
00007 #ifndef _AKARRAY_H
00008 #define _AKARRAY_H
00009 
00010 #include <AK/Tools/Common/AkObject.h>
00011 #include <AK/Tools/Common/AkAssert.h>
00012 
00013 #define AK_DEFINE_ARRAY_POOL( _name_, _poolID_ )    \
00014 struct _name_                                       \
00015 {                                                   \
00016     static AkMemPoolId Get()                        \
00017     {                                               \
00018         return _poolID_;                            \
00019     }                                               \
00020 };
00021 
00022 AK_DEFINE_ARRAY_POOL( _ArrayPoolDefault, g_DefaultPoolId )
00023 AK_DEFINE_ARRAY_POOL( _ArrayPoolLEngineDefault, g_LEngineDefaultPoolId )
00024 
00025 template <class U_POOL>
00026 struct AkArrayAllocatorNoAlign
00027 {
00028     static AkForceInline void * Alloc( size_t in_uSize )
00029     {
00030         return AK::MemoryMgr::Malloc( U_POOL::Get(), in_uSize );
00031     }
00032 
00033     static AkForceInline void Free( void * in_pAddress )
00034     {
00035         AK::MemoryMgr::Free( U_POOL::Get(), in_pAddress );
00036     }
00037 };
00038 
00039 template <class U_POOL>
00040 struct AkArrayAllocatorAlignedSimd
00041 {
00042     static AkForceInline void * Alloc( size_t in_uSize )
00043     {
00044         return AK::MemoryMgr::Malign( U_POOL::Get(), in_uSize, AK_SIMD_ALIGNMENT );
00045     }
00046 
00047     static AkForceInline void Free( void * in_pAddress )
00048     {
00049         AK::MemoryMgr::Falign( U_POOL::Get(), in_pAddress );
00050     }
00051 };
00052 
00053 
00054 template <class T>
00055 struct AkAssignmentMovePolicy
00056 {
00057     // By default the assignment operator is invoked to move elements of an array from slot to slot.  If desired,
00058     //  a custom 'Move' operation can be passed into TMovePolicy to transfer ownership of resources from in_Src to in_Dest.
00059     static AkForceInline void Move( T& in_Dest, T& in_Src )
00060     {
00061         in_Dest = in_Src;
00062     }
00063 };
00064 
00065 // Can be used as TMovePolicy to create arrays of arrays.
00066 template <class T>
00067 struct AkTransferMovePolicy
00068 {
00069     static AkForceInline void Move( T& in_Dest, T& in_Src )
00070     {
00071         in_Dest.Transfer(in_Src); //transfer ownership of resources.
00072     }
00073 };
00074 
00075 // Common allocators:
00076 typedef AkArrayAllocatorNoAlign<_ArrayPoolDefault> ArrayPoolDefault;
00077 typedef AkArrayAllocatorNoAlign<_ArrayPoolLEngineDefault> ArrayPoolLEngineDefault;
00078 typedef AkArrayAllocatorAlignedSimd<_ArrayPoolLEngineDefault> ArrayPoolLEngineDefaultAlignedSimd;
00079 
00081 template <class T, class ARG_T, class TAlloc = ArrayPoolDefault, unsigned long TGrowBy = 1, class TMovePolicy = AkAssignmentMovePolicy<T> > class AkArray : public TAlloc
00082 {
00083 public:
00085     AkArray()
00086         : m_pItems( 0 )
00087         , m_uLength( 0 )
00088         , m_ulReserved( 0 )
00089     {
00090     }
00091 
00093     ~AkArray()
00094     {
00095         AKASSERT( m_pItems == 0 );
00096         AKASSERT( m_uLength == 0 );
00097         AKASSERT( m_ulReserved == 0 );
00098     }
00099 
00100 // Workaround for SWIG to parse nested structure: 
00101 // Bypass this inner struct and use a proxy in a separate header.
00102 #ifndef SWIG
00103 
00104     struct Iterator
00105     {
00106         T* pItem;   
00107 
00109         Iterator& operator++()
00110         {
00111             AKASSERT( pItem );
00112             ++pItem;
00113             return *this;
00114         }
00115 
00117         Iterator& operator--()
00118         {
00119             AKASSERT( pItem );
00120             --pItem;
00121             return *this;
00122         }
00123 
00125         T& operator*()
00126         {
00127             AKASSERT( pItem );
00128             return *pItem;
00129         }
00130 
00132         bool operator ==( const Iterator& in_rOp ) const
00133         {
00134             return ( pItem == in_rOp.pItem );
00135         }
00136 
00138         bool operator !=( const Iterator& in_rOp ) const
00139         {
00140             return ( pItem != in_rOp.pItem );
00141         }
00142     };
00143 #endif // #ifndef SWIG
00144 
00146     Iterator Begin() const
00147     {
00148         Iterator returnedIt;
00149         returnedIt.pItem = m_pItems;
00150         return returnedIt;
00151     }
00152 
00154     Iterator End() const
00155     {
00156         Iterator returnedIt;
00157         returnedIt.pItem = m_pItems + m_uLength;
00158         return returnedIt;
00159     }
00160 
00162     Iterator FindEx( ARG_T in_Item ) const
00163     {
00164         Iterator it = Begin();
00165 
00166         for ( Iterator itEnd = End(); it != itEnd; ++it )
00167         {
00168             if ( *it == in_Item )
00169                 break;
00170         }
00171 
00172         return it;
00173     }
00174 
00177     Iterator BinarySearch( ARG_T in_Item ) const
00178     {
00179         Iterator itResult = End();
00180         if (m_pItems)
00181         {
00182             T * pTop = m_pItems, * pBottom = m_pItems + m_uLength;
00183 
00184             while ( pTop <= pBottom )
00185             {
00186                 T* pThis = ( pBottom - pTop ) / 2 + pTop; 
00187                 if( in_Item < *pThis )
00188                     pBottom = pThis - 1;
00189                 else if ( in_Item > *pThis ) 
00190                     pTop = pThis + 1;
00191                 else
00192                 {
00193                     itResult.pItem = pThis;
00194                     break;
00195                 }
00196             }
00197         }
00198 
00199         return itResult;
00200     }
00201 
00203     Iterator Erase( Iterator& in_rIter )
00204     {
00205         AKASSERT( m_pItems != 0 );
00206 
00207         // Move items by 1
00208 
00209         T * pItemLast = m_pItems + m_uLength - 1;
00210 
00211         for ( T * pItem = in_rIter.pItem; pItem < pItemLast; pItem++ )
00212             TMovePolicy::Move( pItem[ 0 ], pItem[ 1 ] );
00213 
00214         // Destroy the last item
00215 
00216         pItemLast->~T();
00217 
00218         m_uLength--;
00219 
00220         return in_rIter;
00221     }
00222 
00224     void Erase( unsigned int in_uIndex )
00225     {
00226         AKASSERT( m_pItems != 0 );
00227 
00228         // Move items by 1
00229 
00230         T * pItemLast = m_pItems + m_uLength - 1;
00231 
00232         for ( T * pItem = m_pItems+in_uIndex; pItem < pItemLast; pItem++ )
00233             TMovePolicy::Move( pItem[ 0 ], pItem[ 1 ] );
00234 
00235         // Destroy the last item
00236 
00237         pItemLast->~T();
00238 
00239         m_uLength--;
00240     }
00241 
00244     Iterator EraseSwap( Iterator& in_rIter )
00245     {
00246         AKASSERT( m_pItems != 0 );
00247 
00248         if ( Length( ) > 1 )
00249         {
00250             // Swap last item with this one.
00251             TMovePolicy::Move( *in_rIter.pItem, Last( ) );
00252         }
00253 
00254         // Destroy.
00255         AKASSERT( Length( ) > 0 );
00256         Last( ).~T();
00257 
00258         m_uLength--;
00259 
00260         return in_rIter;
00261     }
00262 
00264     AKRESULT Reserve( AkUInt32 in_ulReserve )
00265     {
00266         AKASSERT( m_pItems == 0 && m_uLength == 0 );
00267         AKASSERT( in_ulReserve || TGrowBy );
00268 
00269         if ( in_ulReserve )
00270         {
00271             m_pItems = (T *) TAlloc::Alloc( sizeof( T ) * in_ulReserve );
00272             if ( m_pItems == 0 )
00273                 return AK_InsufficientMemory;
00274 
00275             m_ulReserved = in_ulReserve;
00276         }
00277 
00278         return AK_Success;
00279     }
00280 
00281     AkUInt32 Reserved() const { return m_ulReserved; }
00282 
00284     void Term()
00285     {
00286         if ( m_pItems )
00287         {
00288             RemoveAll();
00289             TAlloc::Free( m_pItems );
00290             m_pItems = 0;
00291             m_ulReserved = 0;
00292         }
00293     }
00294 
00296     AkForceInline AkUInt32 Length() const
00297     {
00298         return m_uLength;
00299     }
00300 
00302     AkForceInline bool IsEmpty() const
00303     {
00304         return m_uLength == 0;
00305     }
00306     
00308     T* Exists(ARG_T in_Item) const
00309     {
00310         Iterator it = FindEx( in_Item );
00311         return ( it != End() ) ? it.pItem : 0;
00312     }
00313 
00316     T * AddLast()
00317     {
00318         size_t cItems = Length();
00319 
00320 #if defined(_MSC_VER)
00321 #pragma warning( push )
00322 #pragma warning( disable : 4127 )
00323 #endif
00324         if ( ( cItems >= m_ulReserved ) && TGrowBy > 0 )
00325         {
00326             if ( !GrowArray() ) 
00327                 return 0;
00328         }
00329 #if defined(_MSC_VER)
00330 #pragma warning( pop )
00331 #endif
00332 
00333         // have we got space for a new one ?
00334         if(  cItems < m_ulReserved )
00335         {
00336             T * pEnd = m_pItems + m_uLength++;
00337             AkPlacementNew( pEnd ) T; 
00338             return pEnd;
00339         }
00340 
00341         return 0;
00342     }
00343 
00345     T * AddLast(ARG_T in_rItem)
00346     {
00347         T * pItem = AddLast();
00348         if ( pItem )
00349             *pItem = in_rItem;
00350         return pItem;
00351     }
00352 
00354     T& Last()
00355     {
00356         AKASSERT( m_uLength );
00357 
00358         return *( m_pItems + m_uLength - 1 );
00359     }
00360 
00362     void RemoveLast()
00363     {
00364         AKASSERT( m_uLength );
00365         ( m_pItems + m_uLength - 1 )->~T();
00366         m_uLength--;
00367     }
00368 
00370     AKRESULT Remove(ARG_T in_rItem)
00371     {
00372         Iterator it = FindEx( in_rItem );
00373         if ( it != End() )
00374         {
00375             Erase( it );
00376             return AK_Success;
00377         }
00378 
00379         return AK_Fail;
00380     }
00381 
00384     AKRESULT RemoveSwap(ARG_T in_rItem)
00385     {
00386         Iterator it = FindEx( in_rItem );
00387         if ( it != End() )
00388         {
00389             EraseSwap( it );
00390             return AK_Success;
00391         }
00392 
00393         return AK_Fail;
00394     }
00395 
00397     void RemoveAll()
00398     {
00399         for ( Iterator it = Begin(), itEnd = End(); it != itEnd; ++it )
00400             (*it).~T();
00401         m_uLength = 0;
00402     }
00403 
00405     T& operator[](unsigned int uiIndex) const
00406     {
00407         AKASSERT( m_pItems );
00408         AKASSERT( uiIndex < Length() );
00409         return m_pItems[uiIndex];
00410     }
00411 
00414     T * Insert(unsigned int in_uIndex)
00415     {
00416         AKASSERT( in_uIndex <= Length() );
00417 
00418         size_t cItems = Length();
00419 
00420 #if defined(_MSC_VER)
00421 #pragma warning( push )
00422 #pragma warning( disable : 4127 )
00423 #endif
00424         if ( ( cItems >= m_ulReserved ) && TGrowBy > 0 )
00425         {
00426             if ( !GrowArray() ) 
00427                 return 0;
00428         }
00429 #if defined(_MSC_VER)
00430 #pragma warning( pop )
00431 #endif
00432 
00433         // have we got space for a new one ?
00434         if(  cItems < m_ulReserved )
00435         {
00436             T * pItemLast = m_pItems + m_uLength++;
00437             AkPlacementNew( pItemLast ) T; 
00438 
00439             // Move items by 1
00440 
00441             for ( T * pItem = pItemLast; pItem > ( m_pItems + in_uIndex ); --pItem )
00442                 TMovePolicy::Move( pItem[ 0 ], pItem[ -1 ] );
00443 
00444             // Reinitialize item at index
00445 
00446             ( m_pItems + in_uIndex )->~T();
00447             AkPlacementNew( m_pItems + in_uIndex ) T; 
00448 
00449             return m_pItems + in_uIndex;
00450         }
00451 
00452         return 0;
00453     }
00454 
00456     bool GrowArray( AkUInt32 in_uGrowBy = TGrowBy )
00457     {
00458         AKASSERT( in_uGrowBy );
00459         
00460         AkUInt32 ulNewReserve = m_ulReserved + in_uGrowBy;
00461         T * pNewItems = (T *) TAlloc::Alloc( sizeof( T ) * ulNewReserve );
00462         if ( !pNewItems ) 
00463             return false;
00464 
00465         // Copy all elements in new array, destroy old ones
00466 
00467         size_t cItems = Length();
00468 
00469         if ( m_pItems ) 
00470         {
00471             for ( size_t i = 0; i < cItems; ++i )
00472             {
00473                 AkPlacementNew( pNewItems + i ) T; 
00474 
00475                 TMovePolicy::Move( pNewItems[ i ], m_pItems[ i ] );
00476                 
00477                 m_pItems[ i ].~T();
00478             }
00479 
00480             TAlloc::Free( m_pItems );
00481         }
00482 
00483         m_pItems = pNewItems;
00484         m_ulReserved = ulNewReserve;
00485 
00486         return true;
00487     }
00488 
00490     bool Resize(AkUInt32 in_uiSize)
00491     {
00492         AkUInt32 cItems = Length();
00493         if (in_uiSize < cItems)
00494         {
00495             //Destroy superfluous elements
00496             for(AkUInt32 i = in_uiSize - 1 ; i < cItems; i++)
00497             {
00498                 m_pItems[ i ].~T();
00499             }
00500             m_uLength = in_uiSize;
00501             return true;
00502         }
00503 
00504         if ( in_uiSize > m_ulReserved )
00505         {
00506             if ( !GrowArray(in_uiSize - cItems) ) 
00507                 return false;
00508         }
00509 
00510         //Create the missing items.
00511         for(size_t i = cItems; i < in_uiSize; i++)
00512         {
00513             AkPlacementNew( m_pItems + i ) T; 
00514         }
00515 
00516         m_uLength = in_uiSize;
00517         return true;
00518     }
00519 
00520     void Transfer(AkArray<T,ARG_T,TAlloc,TGrowBy,TMovePolicy>& in_rSource)
00521     {
00522         if (m_pItems)
00523             Term();
00524 
00525         m_pItems = in_rSource.m_pItems;
00526         m_uLength = in_rSource.m_uLength;
00527         m_ulReserved = in_rSource.m_ulReserved;
00528 
00529         in_rSource.m_pItems = NULL;
00530         in_rSource.m_uLength = 0;
00531         in_rSource.m_ulReserved = 0;
00532     }
00533 
00534 protected:
00535 
00536     T *         m_pItems;       
00537     AkUInt32    m_uLength;      
00538     AkUInt32    m_ulReserved;   
00539 };
00540 
00541 #endif

Cette page a-t-elle été utile ?

Besoin d'aide ?

Des questions ? Des problèmes ? Besoin de plus d'informations ? Contactez-nous, nous pouvons vous aider !

Visitez notre page d'Aide

Décrivez-nous de votre projet. Nous sommes là pour vous aider.

Enregistrez votre projet et nous vous aiderons à démarrer sans aucune obligation !

Partir du bon pied avec Wwise