00001 /*******************************************************************************
00002 The content of this file includes portions of the AUDIOKINETIC Wwise Technology
00003 released in source code form as part of the SDK installer package.
00004 
00005 Commercial License Usage
00006 
00007 Licensees holding valid commercial licenses to the AUDIOKINETIC Wwise Technology
00008 may use this file in accordance with the end user license agreement provided 
00009 with the software or, alternatively, in accordance with the terms contained in a
00010 written agreement between you and Audiokinetic Inc.
00011 
00012 Apache License Usage
00013 
00014 Alternatively, this file may be used under the Apache License, Version 2.0 (the 
00015 "Apache License"); you may not use this file except in compliance with the 
00016 Apache License. You may obtain a copy of the Apache License at 
00017 http://www.apache.org/licenses/LICENSE-2.0.
00018 
00019 Unless required by applicable law or agreed to in writing, software distributed
00020 under the Apache License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES
00021 OR CONDITIONS OF ANY KIND, either express or implied. See the Apache License for
00022 the specific language governing permissions and limitations under the License.
00023 
00024   Version: <VERSION>  Build: <BUILDNUMBER>
00025   Copyright (c) <COPYRIGHTYEAR> Audiokinetic Inc.
00026 *******************************************************************************/
00027 
00028 #ifndef _AKARRAY_H
00029 #define _AKARRAY_H
00030 
00031 #include <AK/Tools/Common/AkObject.h>
00032 #include <AK/Tools/Common/AkAssert.h>
00033 #include <AK/Tools/Common/AkPlatformFuncs.h>
00034 
00035 #define AK_DEFINE_ARRAY_POOL( _name_, _poolID_ )    \
00036 struct _name_                                       \
00037 {                                                   \
00038     static AkMemPoolId Get()                        \
00039     {                                               \
00040         return _poolID_;                            \
00041     }                                               \
00042 };
00043 
00044 AK_DEFINE_ARRAY_POOL( _ArrayPoolDefault, g_DefaultPoolId )
00045 AK_DEFINE_ARRAY_POOL( _ArrayPoolLEngineDefault, g_LEngineDefaultPoolId )
00046 
00047 template <class U_POOL>
00048 struct AkArrayAllocatorNoAlign
00049 {
00050     AkForceInline void * Alloc( size_t in_uSize )
00051     {
00052         return AK::MemoryMgr::Malloc( U_POOL::Get(), in_uSize );
00053     }
00054 
00055     AkForceInline void Free( void * in_pAddress )
00056     {
00057         AK::MemoryMgr::Free( U_POOL::Get(), in_pAddress );
00058     }
00059 
00060     AkForceInline void TransferMem(void *& io_pDest, AkArrayAllocatorNoAlign<U_POOL> in_srcAlloc, void * in_pSrc ) 
00061     {
00062         io_pDest = in_pSrc;
00063     }
00064 };
00065 
00066 template <class U_POOL>
00067 struct AkArrayAllocatorAlignedSimd
00068 {
00069     AkForceInline void * Alloc( size_t in_uSize )
00070     {
00071         return AK::MemoryMgr::Malign( U_POOL::Get(), in_uSize, AK_SIMD_ALIGNMENT );
00072     }
00073 
00074     AkForceInline void Free( void * in_pAddress )
00075     {
00076         AK::MemoryMgr::Falign( U_POOL::Get(), in_pAddress );
00077     }
00078 
00079     AkForceInline void TransferMem(void *& io_pDest, AkArrayAllocatorAlignedSimd<U_POOL> in_srcAlloc, void * in_pSrc ) 
00080     {
00081         io_pDest = in_pSrc;
00082     }
00083 
00084 };
00085 
00086 // AkHybridAllocator
00087 //  Attempts to allocate from a small buffer of size uBufferSizeBytes, which is contained within the array type.  Useful if the array is expected to contain a small number of elements.
00088 //  If the array grows to a larger size than uBufferSizeBytes, the the memory is allocated from the default memory pool.
00089 //  NOTE: only use with types that are trivially copyable.
00090 template< AkUInt32 uBufferSizeBytes, AkUInt8 uAlignmentSize = AK_OS_STRUCT_ALIGN>
00091 struct AkHybridAllocator
00092 {
00093     static const AkUInt32 _uBufferSizeBytes = uBufferSizeBytes;
00094 
00095     AkForceInline void * Alloc(size_t in_uSize)
00096     {
00097         if (in_uSize <= uBufferSizeBytes)
00098             return (void *)&m_buffer;
00099         else
00100             return AK::MemoryMgr::Malign(g_DefaultPoolId, in_uSize, uAlignmentSize);
00101     }
00102 
00103     AkForceInline void Free(void * in_pAddress)
00104     {
00105         if (&m_buffer != in_pAddress)
00106             AK::MemoryMgr::Falign(g_DefaultPoolId, in_pAddress);
00107     }
00108 
00109     AkForceInline void TransferMem(void *& io_pDest, AkHybridAllocator<uBufferSizeBytes, uAlignmentSize>& in_srcAlloc, void * in_pSrc)
00110     {
00111         if (&in_srcAlloc.m_buffer == in_pSrc)
00112         {
00113             AKPLATFORM::AkMemCpy(m_buffer, in_srcAlloc.m_buffer, uBufferSizeBytes);
00114             io_pDest = m_buffer;
00115         }
00116         else
00117         {
00118             io_pDest = in_pSrc;
00119         }
00120     }
00121     
00122     AK_ALIGN(char m_buffer[uBufferSizeBytes], uAlignmentSize);
00123 };
00124 
00125 template <class T>
00126 struct AkAssignmentMovePolicy
00127 {
00128     // By default the assignment operator is invoked to move elements of an array from slot to slot.  If desired,
00129     //  a custom 'Move' operation can be passed into TMovePolicy to transfer ownership of resources from in_Src to in_Dest.
00130     static AkForceInline void Move( T& in_Dest, T& in_Src )
00131     {
00132         in_Dest = in_Src;
00133     }
00134 };
00135 
00136 // Can be used as TMovePolicy to create arrays of arrays.
00137 template <class T>
00138 struct AkTransferMovePolicy
00139 {
00140     static AkForceInline void Move( T& in_Dest, T& in_Src )
00141     {
00142         in_Dest.Transfer(in_Src); //transfer ownership of resources.
00143     }
00144 };
00145 
00146 // Common allocators:
00147 typedef AkArrayAllocatorNoAlign<_ArrayPoolDefault> ArrayPoolDefault;
00148 typedef AkArrayAllocatorNoAlign<_ArrayPoolLEngineDefault> ArrayPoolLEngineDefault;
00149 typedef AkArrayAllocatorAlignedSimd<_ArrayPoolLEngineDefault> ArrayPoolLEngineDefaultAlignedSimd;
00150 
00151 /// Specific implementation of array
00152 template <class T, class ARG_T, class TAlloc = ArrayPoolDefault, unsigned long TGrowBy = 1, class TMovePolicy = AkAssignmentMovePolicy<T> > class AkArray : public TAlloc
00153 {
00154 public:
00155     /// Constructor
00156     AkArray()
00157         : m_pItems( 0 )
00158         , m_uLength( 0 )
00159         , m_ulReserved( 0 )
00160     {
00161     }
00162 
00163     /// Destructor
00164     ~AkArray()
00165     {
00166         AKASSERT( m_pItems == 0 );
00167         AKASSERT( m_uLength == 0 );
00168         AKASSERT( m_ulReserved == 0 );
00169     }
00170 
00171 // Workaround for SWIG to parse nested structure: 
00172 // Bypass this inner struct and use a proxy in a separate header.
00173 #ifndef SWIG
00174     /// Iterator
00175     struct Iterator
00176     {
00177         T* pItem;   ///< Pointer to the item in the array.
00178 
00179         /// ++ operator
00180         Iterator& operator++()
00181         {
00182             AKASSERT( pItem );
00183             ++pItem;
00184             return *this;
00185         }
00186 
00187         /// -- operator
00188         Iterator& operator--()
00189         {
00190             AKASSERT( pItem );
00191             --pItem;
00192             return *this;
00193         }
00194 
00195         /// * operator
00196         T& operator*()
00197         {
00198             AKASSERT( pItem );
00199             return *pItem;
00200         }
00201 
00202         /// == operator
00203         bool operator ==( const Iterator& in_rOp ) const
00204         {
00205             return ( pItem == in_rOp.pItem );
00206         }
00207 
00208         /// != operator
00209         bool operator !=( const Iterator& in_rOp ) const
00210         {
00211             return ( pItem != in_rOp.pItem );
00212         }
00213     };
00214 #endif // #ifndef SWIG
00215 
00216     /// Returns the iterator to the first item of the array, will be End() if the array is empty.
00217     Iterator Begin() const
00218     {
00219         Iterator returnedIt;
00220         returnedIt.pItem = m_pItems;
00221         return returnedIt;
00222     }
00223 
00224     /// Returns the iterator to the end of the array
00225     Iterator End() const
00226     {
00227         Iterator returnedIt;
00228         returnedIt.pItem = m_pItems + m_uLength;
00229         return returnedIt;
00230     }
00231 
00232     /// Returns the iterator th the specified item, will be End() if the item is not found
00233     Iterator FindEx( ARG_T in_Item ) const
00234     {
00235         Iterator it = Begin();
00236 
00237         for ( Iterator itEnd = End(); it != itEnd; ++it )
00238         {
00239             if ( *it == in_Item )
00240                 break;
00241         }
00242 
00243         return it;
00244     }
00245 
00246     /// Returns the iterator th the specified item, will be End() if the item is not found
00247     /// The array must be in ascending sorted order.
00248     Iterator BinarySearch( ARG_T in_Item ) const
00249     {
00250         Iterator itResult = End();
00251         if (m_pItems)
00252         {
00253             T * pTop = m_pItems, * pBottom = m_pItems + m_uLength;
00254 
00255             while ( pTop <= pBottom )
00256             {
00257                 T* pThis = ( pBottom - pTop ) / 2 + pTop; 
00258                 if( in_Item < *pThis )
00259                     pBottom = pThis - 1;
00260                 else if ( in_Item > *pThis ) 
00261                     pTop = pThis + 1;
00262                 else
00263                 {
00264                     itResult.pItem = pThis;
00265                     break;
00266                 }
00267             }
00268         }
00269 
00270         return itResult;
00271     }
00272 
00273     /// Erase the specified iterator from the array
00274     Iterator Erase( Iterator& in_rIter )
00275     {
00276         AKASSERT( m_pItems != 0 );
00277 
00278         // Move items by 1
00279 
00280         T * pItemLast = m_pItems + m_uLength - 1;
00281 
00282         for ( T * pItem = in_rIter.pItem; pItem < pItemLast; pItem++ )
00283             TMovePolicy::Move( pItem[ 0 ], pItem[ 1 ] );
00284 
00285         // Destroy the last item
00286 
00287         pItemLast->~T();
00288 
00289         m_uLength--;
00290 
00291         return in_rIter;
00292     }
00293 
00294     /// Erase the item at the specified index
00295     void Erase( unsigned int in_uIndex )
00296     {
00297         AKASSERT( m_pItems != 0 );
00298 
00299         // Move items by 1
00300 
00301         T * pItemLast = m_pItems + m_uLength - 1;
00302 
00303         for ( T * pItem = m_pItems+in_uIndex; pItem < pItemLast; pItem++ )
00304             TMovePolicy::Move( pItem[ 0 ], pItem[ 1 ] );
00305 
00306         // Destroy the last item
00307 
00308         pItemLast->~T();
00309 
00310         m_uLength--;
00311     }
00312 
00313     /// Erase the specified iterator in the array. but it dos not guarantee the ordering in the array.
00314     /// This version should be used only when the order in the array is not an issue.
00315     Iterator EraseSwap( Iterator& in_rIter )
00316     {
00317         AKASSERT( m_pItems != 0 );
00318 
00319         if ( Length( ) > 1 )
00320         {
00321             // Swap last item with this one.
00322             TMovePolicy::Move( *in_rIter.pItem, Last( ) );
00323         }
00324 
00325         // Destroy.
00326         AKASSERT( Length( ) > 0 );
00327         Last( ).~T();
00328 
00329         m_uLength--;
00330 
00331         return in_rIter;
00332     }
00333 
00334     /// Pre-Allocate a number of spaces in the array
00335     AKRESULT Reserve( AkUInt32 in_ulReserve )
00336     {
00337         AKASSERT( m_pItems == 0 && m_uLength == 0 );
00338         AKASSERT( in_ulReserve || TGrowBy );
00339 
00340         if ( in_ulReserve )
00341         {
00342             m_pItems = (T *) TAlloc::Alloc( sizeof( T ) * in_ulReserve );
00343             if ( m_pItems == 0 )
00344                 return AK_InsufficientMemory;
00345 
00346             m_ulReserved = in_ulReserve;
00347         }
00348 
00349         return AK_Success;
00350     }
00351 
00352     AkUInt32 Reserved() const { return m_ulReserved; }
00353 
00354     /// Term the array. Must be called before destroying the object.
00355     void Term()
00356     {
00357         if ( m_pItems )
00358         {
00359             RemoveAll();
00360             TAlloc::Free( m_pItems );
00361             m_pItems = 0;
00362             m_ulReserved = 0;
00363         }
00364     }
00365 
00366     /// Returns the numbers of items in the array.
00367     AkForceInline AkUInt32 Length() const
00368     {
00369         return m_uLength;
00370     }
00371 
00372     /// Returns true if the number items in the array is 0, false otherwise.
00373     AkForceInline bool IsEmpty() const
00374     {
00375         return m_uLength == 0;
00376     }
00377     
00378     /// Returns a pointer to the specified item in the list if it exists, 0 if not found.
00379     T* Exists(ARG_T in_Item) const
00380     {
00381         Iterator it = FindEx( in_Item );
00382         return ( it != End() ) ? it.pItem : 0;
00383     }
00384 
00385     /// Add an item in the array, without filling it.
00386     /// Returns a pointer to the location to be filled.
00387     T * AddLast()
00388     {
00389         size_t cItems = Length();
00390 
00391 #if defined(_MSC_VER)
00392 #pragma warning( push )
00393 #pragma warning( disable : 4127 )
00394 #endif
00395         if ( ( cItems >= m_ulReserved ) && TGrowBy > 0 )
00396         {
00397             if ( !GrowArray() ) 
00398                 return 0;
00399         }
00400 #if defined(_MSC_VER)
00401 #pragma warning( pop )
00402 #endif
00403 
00404         // have we got space for a new one ?
00405         if(  cItems < m_ulReserved )
00406         {
00407             T * pEnd = m_pItems + m_uLength++;
00408             AkPlacementNew( pEnd ) T; 
00409             return pEnd;
00410         }
00411 
00412         return 0;
00413     }
00414 
00415     /// Add an item in the array, and fills it with the provided item.
00416     T * AddLast(ARG_T in_rItem)
00417     {
00418         T * pItem = AddLast();
00419         if ( pItem )
00420             *pItem = in_rItem;
00421         return pItem;
00422     }
00423 
00424     /// Returns a reference to the last item in the array.
00425     T& Last()
00426     {
00427         AKASSERT( m_uLength );
00428 
00429         return *( m_pItems + m_uLength - 1 );
00430     }
00431 
00432     /// Removes the last item from the array.
00433     void RemoveLast()
00434     {
00435         AKASSERT( m_uLength );
00436         ( m_pItems + m_uLength - 1 )->~T();
00437         m_uLength--;
00438     }
00439 
00440     /// Removes the specified item if found in the array.
00441     AKRESULT Remove(ARG_T in_rItem)
00442     {
00443         Iterator it = FindEx( in_rItem );
00444         if ( it != End() )
00445         {
00446             Erase( it );
00447             return AK_Success;
00448         }
00449 
00450         return AK_Fail;
00451     }
00452 
00453     /// Fast remove of the specified item in the array.
00454     /// This method do not guarantee keeping ordering of the array.
00455     AKRESULT RemoveSwap(ARG_T in_rItem)
00456     {
00457         Iterator it = FindEx( in_rItem );
00458         if ( it != End() )
00459         {
00460             EraseSwap( it );
00461             return AK_Success;
00462         }
00463 
00464         return AK_Fail;
00465     }
00466 
00467     /// Removes all items in the array
00468     void RemoveAll()
00469     {
00470         for ( Iterator it = Begin(), itEnd = End(); it != itEnd; ++it )
00471             (*it).~T();
00472         m_uLength = 0;
00473     }
00474 
00475     /// Operator [], return a reference to the specified index.
00476     AkForceInline T& operator[](unsigned int uiIndex) const
00477     {
00478         AKASSERT( m_pItems );
00479         AKASSERT( uiIndex < Length() );
00480         return m_pItems[uiIndex];
00481     }
00482 
00483     /// Insert an item at the specified position without filling it.
00484     /// Returns the pointer to the item to be filled.
00485     T * Insert(unsigned int in_uIndex)
00486     {
00487         AKASSERT( in_uIndex <= Length() );
00488 
00489         size_t cItems = Length();
00490 
00491 #if defined(_MSC_VER)
00492 #pragma warning( push )
00493 #pragma warning( disable : 4127 )
00494 #endif
00495         if ( ( cItems >= m_ulReserved ) && TGrowBy > 0 )
00496         {
00497             if ( !GrowArray() ) 
00498                 return 0;
00499         }
00500 #if defined(_MSC_VER)
00501 #pragma warning( pop )
00502 #endif
00503 
00504         // have we got space for a new one ?
00505         if(  cItems < m_ulReserved )
00506         {
00507             T * pItemLast = m_pItems + m_uLength++;
00508             AkPlacementNew( pItemLast ) T; 
00509 
00510             // Move items by 1
00511 
00512             for ( T * pItem = pItemLast; pItem > ( m_pItems + in_uIndex ); --pItem )
00513                 TMovePolicy::Move( pItem[ 0 ], pItem[ -1 ] );
00514 
00515             // Reinitialize item at index
00516 
00517             ( m_pItems + in_uIndex )->~T();
00518             AkPlacementNew( m_pItems + in_uIndex ) T; 
00519 
00520             return m_pItems + in_uIndex;
00521         }
00522 
00523         return 0;
00524     }
00525 
00526     /// Resize the array.
00527     bool GrowArray( AkUInt32 in_uGrowBy = TGrowBy )
00528     {
00529         AKASSERT( in_uGrowBy );
00530         
00531         AkUInt32 ulNewReserve = m_ulReserved + in_uGrowBy;
00532         T * pNewItems = (T *) TAlloc::Alloc( sizeof( T ) * ulNewReserve );
00533         if ( !pNewItems ) 
00534             return false;
00535 
00536         // Copy all elements in new array, destroy old ones
00537 
00538         size_t cItems = Length();
00539 
00540         if ( m_pItems && m_pItems != pNewItems /*AkHybridAllocator may serve up same memory*/ ) 
00541         {
00542             for ( size_t i = 0; i < cItems; ++i )
00543             {
00544                 AkPlacementNew( pNewItems + i ) T; 
00545 
00546                 TMovePolicy::Move( pNewItems[ i ], m_pItems[ i ] );
00547                 
00548                 m_pItems[ i ].~T();
00549             }
00550 
00551             TAlloc::Free( m_pItems );
00552         }
00553 
00554         m_pItems = pNewItems;
00555         m_ulReserved = ulNewReserve;
00556 
00557         return true;
00558     }
00559 
00560     /// Resize the array to the specified size.
00561     bool Resize(AkUInt32 in_uiSize)
00562     {
00563         AkUInt32 cItems = Length();
00564         if (in_uiSize < cItems)
00565         {
00566             //Destroy superfluous elements
00567             for(AkUInt32 i = in_uiSize - 1 ; i < cItems; i++)
00568             {
00569                 m_pItems[ i ].~T();
00570             }
00571             m_uLength = in_uiSize;
00572             return true;
00573         }
00574 
00575         if ( in_uiSize > m_ulReserved )
00576         {
00577             if ( !GrowArray(in_uiSize - cItems) ) 
00578                 return false;
00579         }
00580 
00581         //Create the missing items.
00582         for(size_t i = cItems; i < in_uiSize; i++)
00583         {
00584             AkPlacementNew( m_pItems + i ) T; 
00585         }
00586 
00587         m_uLength = in_uiSize;
00588         return true;
00589     }
00590 
00591     void Transfer(AkArray<T,ARG_T,TAlloc,TGrowBy,TMovePolicy>& in_rSource)
00592     {
00593         Term();
00594 
00595         TAlloc::TransferMem( (void*&)m_pItems, in_rSource, (void*)in_rSource.m_pItems );
00596         m_uLength = in_rSource.m_uLength;
00597         m_ulReserved = in_rSource.m_ulReserved;
00598 
00599         in_rSource.m_pItems = NULL;
00600         in_rSource.m_uLength = 0;
00601         in_rSource.m_ulReserved = 0;
00602     }
00603 
00604     AKRESULT Copy(const AkArray<T, ARG_T, TAlloc, TGrowBy, TMovePolicy>& in_rSource)
00605     {
00606         Term();
00607 
00608         if (Resize(in_rSource.Length()))
00609         {
00610             for (AkUInt32 i = 0; i < in_rSource.Length(); ++i)
00611                 m_pItems[i] = in_rSource.m_pItems[i];
00612             return AK_Success;
00613         }
00614         return AK_Fail;
00615     }
00616 
00617 protected:
00618 
00619     T *         m_pItems;       ///< pointer to the beginning of the array.
00620     AkUInt32    m_uLength;      ///< number of items in the array.
00621     AkUInt32    m_ulReserved;   ///< how many we can have at most (currently allocated).
00622 };
00623 
00624 
00625 #endif