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
Questions? Problems? Need more info? Contact us, and we can help!
Visit our Support pageRegister your project and we'll help you get started with no strings attached!
Get started with Wwise