Table of Contents

include/AK/Tools/Common/AkArray.h

Go to the documentation of this file.
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 * ReAlloc( void * in_pCurrent, size_t in_uOldSize, size_t in_uNewSize )
00056     {
00057         return AK::MemoryMgr::Realloc(U_POOL::Get(), in_pCurrent, in_uNewSize);
00058     }
00059 
00060     AkForceInline void Free( void * in_pAddress )
00061     {
00062         AK::MemoryMgr::Free( U_POOL::Get(), in_pAddress );
00063     }
00064 
00065     AkForceInline void TransferMem(void *& io_pDest, AkArrayAllocatorNoAlign<U_POOL> in_srcAlloc, void * in_pSrc ) 
00066     {
00067         io_pDest = in_pSrc;
00068     }
00069 };
00070 
00071 template <class U_POOL>
00072 struct AkArrayAllocatorAlignedSimd
00073 {
00074     AkForceInline void * Alloc( size_t in_uSize )
00075     {
00076         return AK::MemoryMgr::Malign( U_POOL::Get(), in_uSize, AK_SIMD_ALIGNMENT );
00077     }
00078 
00079     AkForceInline void * ReAlloc(void * in_pCurrent, size_t in_uOldSize, size_t in_uNewSize)
00080     {
00081         void* pNew = Alloc(in_uNewSize);
00082         if (pNew && in_pCurrent)
00083         {
00084             AKPLATFORM::AkMemCpy(pNew, in_pCurrent, (AkUInt32)in_uOldSize);
00085             Free(in_pCurrent);
00086         }
00087         return pNew;
00088     }
00089 
00090     AkForceInline void Free( void * in_pAddress )
00091     {
00092         AK::MemoryMgr::Falign( U_POOL::Get(), in_pAddress );
00093     }
00094 
00095     AkForceInline void TransferMem(void *& io_pDest, AkArrayAllocatorAlignedSimd<U_POOL> in_srcAlloc, void * in_pSrc ) 
00096     {
00097         io_pDest = in_pSrc;
00098     }
00099 
00100 };
00101 
00102 // AkHybridAllocator
00103 //  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.
00104 //  If the array grows to a larger size than uBufferSizeBytes, the the memory is allocated from the default memory pool.
00105 //  NOTE: only use with types that are trivially copyable.
00106 template< AkUInt32 uBufferSizeBytes, AkUInt8 uAlignmentSize = AK_OS_STRUCT_ALIGN>
00107 struct AkHybridAllocator
00108 {
00109     static const AkUInt32 _uBufferSizeBytes = uBufferSizeBytes;
00110 
00111     AkForceInline void * Alloc(size_t in_uSize)
00112     {
00113         if (in_uSize <= uBufferSizeBytes)
00114             return (void *)&m_buffer;
00115         else
00116             return AK::MemoryMgr::Malign(g_DefaultPoolId, in_uSize, uAlignmentSize);
00117     }
00118 
00119     AkForceInline void * ReAlloc( void * in_pCurrent, size_t in_uOldSize, size_t in_uNewSize )
00120     {
00121         void* pNew = Alloc(in_uNewSize);
00122         if (pNew != in_pCurrent && pNew && in_pCurrent)
00123         {
00124             AKPLATFORM::AkMemCpy(pNew, in_pCurrent, (AkUInt32)in_uOldSize);
00125             Free(in_pCurrent);
00126         }
00127         return pNew;
00128     }
00129 
00130     AkForceInline void Free(void * in_pAddress)
00131     {
00132         if (&m_buffer != in_pAddress)
00133             AK::MemoryMgr::Falign(g_DefaultPoolId, in_pAddress);
00134     }
00135 
00136     AkForceInline void TransferMem(void *& io_pDest, AkHybridAllocator<uBufferSizeBytes, uAlignmentSize>& in_srcAlloc, void * in_pSrc)
00137     {
00138         if (&in_srcAlloc.m_buffer == in_pSrc)
00139         {
00140             AKPLATFORM::AkMemCpy(m_buffer, in_srcAlloc.m_buffer, uBufferSizeBytes);
00141             io_pDest = m_buffer;
00142         }
00143         else
00144         {
00145             io_pDest = in_pSrc;
00146         }
00147     }
00148     
00149     AK_ALIGN(char m_buffer[uBufferSizeBytes], uAlignmentSize);
00150 };
00151 
00152 template <class T>
00153 struct AkAssignmentMovePolicy
00154 {
00155     // By default the assignment operator is invoked to move elements of an array from slot to slot.  If desired,
00156     //  a custom 'Move' operation can be passed into TMovePolicy to transfer ownership of resources from in_Src to in_Dest.
00157     static AkForceInline void Move( T& in_Dest, T& in_Src )
00158     {
00159         in_Dest = in_Src;
00160     }
00161 
00162     static AkForceInline bool IsTrivial()
00163     {
00164         return true;
00165     }
00166 };
00167 
00168 // Can be used as TMovePolicy to create arrays of arrays.
00169 template <class T>
00170 struct AkTransferMovePolicy
00171 {
00172     static AkForceInline void Move( T& in_Dest, T& in_Src )
00173     {
00174         in_Dest.Transfer(in_Src); //transfer ownership of resources.
00175     }
00176 
00177     static AkForceInline bool IsTrivial()
00178     {
00179         return false;
00180     }
00181 };
00182 
00183 // Common allocators:
00184 typedef AkArrayAllocatorNoAlign<_ArrayPoolDefault> ArrayPoolDefault;
00185 typedef AkArrayAllocatorNoAlign<_ArrayPoolLEngineDefault> ArrayPoolLEngineDefault;
00186 typedef AkArrayAllocatorAlignedSimd<_ArrayPoolLEngineDefault> ArrayPoolLEngineDefaultAlignedSimd;
00187 
00188 /// Specific implementation of array
00189 template <class T, class ARG_T, class TAlloc = ArrayPoolDefault, unsigned long TGrowBy = 1, class TMovePolicy = AkAssignmentMovePolicy<T> > class AkArray : public TAlloc
00190 {
00191 public:
00192     /// Constructor
00193     AkArray()
00194         : m_pItems( 0 )
00195         , m_uLength( 0 )
00196         , m_ulReserved( 0 )
00197     {
00198     }
00199 
00200     /// Destructor
00201     ~AkArray()
00202     {
00203         AKASSERT( m_pItems == 0 );
00204         AKASSERT( m_uLength == 0 );
00205         AKASSERT( m_ulReserved == 0 );
00206     }
00207 
00208 // Workaround for SWIG to parse nested structure: 
00209 // Bypass this inner struct and use a proxy in a separate header.
00210 #ifndef SWIG
00211     /// Iterator
00212     struct Iterator
00213     {
00214         T* pItem;   ///< Pointer to the item in the array.
00215 
00216         /// + operator</span>
00217         Iterator operator+(AkUInt32 inc) const
00218         {
00219             AKASSERT( pItem );
00220             Iterator returnedIt;
00221             returnedIt.pItem = pItem + inc;
00222             return returnedIt;
00223         }
00224 
00225         /// - operator</span>
00226         AkUInt32 operator-(Iterator const& rhs) const
00227         {
00228             AKASSERT((pItem && rhs.pItem)||(!pItem && !rhs.pItem));
00229             return (AkUInt32)(pItem - rhs.pItem);
00230         }
00231 
00232         /// ++ operator</span>
00233         Iterator& operator++()
00234         {
00235             AKASSERT( pItem );
00236             ++pItem;
00237             return *this;
00238         }
00239 
00240         /// -- operator</span>
00241         Iterator& operator--()
00242         {
00243             AKASSERT( pItem );
00244             --pItem;
00245             return *this;
00246         }
00247 
00248         /// * operator</span>
00249         T& operator*()
00250         {
00251             AKASSERT( pItem );
00252             return *pItem;
00253         }
00254 
00255         /// == operator</span>
00256         bool operator ==( const Iterator& in_rOp ) const
00257         {
00258             return ( pItem == in_rOp.pItem );
00259         }
00260 
00261         /// != operator</span>
00262         bool operator !=( const Iterator& in_rOp ) const
00263         {
00264             return ( pItem != in_rOp.pItem );
00265         }
00266     };
00267 #endif // #ifndef SWIG
00268 
00269     /// Returns the iterator to the first item of the array, will be End() if the array is empty.
00270     Iterator Begin() const
00271     {
00272         Iterator returnedIt;
00273         returnedIt.pItem = m_pItems;
00274         return returnedIt;
00275     }
00276 
00277     /// Returns the iterator to the end of the array
00278     Iterator End() const
00279     {
00280         Iterator returnedIt;
00281         returnedIt.pItem = m_pItems + m_uLength;
00282         return returnedIt;
00283     }
00284 
00285     /// Returns the iterator th the specified item, will be End() if the item is not found
00286     Iterator FindEx( ARG_T in_Item ) const
00287     {
00288         Iterator it = Begin();
00289 
00290         for ( Iterator itEnd = End(); it != itEnd; ++it )
00291         {
00292             if ( *it == in_Item )
00293                 break;
00294         }
00295 
00296         return it;
00297     }
00298 
00299     /// Returns the iterator th the specified item, will be End() if the item is not found
00300     /// The array must be in ascending sorted order.
00301     Iterator BinarySearch( ARG_T in_Item ) const
00302     {
00303         Iterator itResult = End();
00304         if (m_pItems)
00305         {
00306             T * pTop = m_pItems, * pBottom = m_pItems + m_uLength;
00307 
00308             while ( pTop <= pBottom )
00309             {
00310                 T* pThis = ( pBottom - pTop ) / 2 + pTop; 
00311                 if( in_Item < *pThis )
00312                     pBottom = pThis - 1;
00313                 else if ( in_Item > *pThis ) 
00314                     pTop = pThis + 1;
00315                 else
00316                 {
00317                     itResult.pItem = pThis;
00318                     break;
00319                 }
00320             }
00321         }
00322 
00323         return itResult;
00324     }
00325 
00326     /// Erase the specified iterator from the array
00327     Iterator Erase( Iterator& in_rIter )
00328     {
00329         AKASSERT( m_pItems != 0 );
00330 
00331         // Move items by 1
00332 
00333         T * pItemLast = m_pItems + m_uLength - 1;
00334 
00335         for ( T * pItem = in_rIter.pItem; pItem < pItemLast; pItem++ )
00336             TMovePolicy::Move( pItem[ 0 ], pItem[ 1 ] );
00337 
00338         // Destroy the last item
00339 
00340         pItemLast->~T();
00341 
00342         m_uLength--;
00343 
00344         return in_rIter;
00345     }
00346 
00347     /// Erase the item at the specified index
00348     void Erase( unsigned int in_uIndex )
00349     {
00350         AKASSERT( m_pItems != 0 );
00351 
00352         // Move items by 1
00353 
00354         T * pItemLast = m_pItems + m_uLength - 1;
00355 
00356         for ( T * pItem = m_pItems+in_uIndex; pItem < pItemLast; pItem++ )
00357             TMovePolicy::Move( pItem[ 0 ], pItem[ 1 ] );
00358 
00359         // Destroy the last item
00360 
00361         pItemLast->~T();
00362 
00363         m_uLength--;
00364     }
00365 
00366     /// Erase the specified iterator in the array. but it dos not guarantee the ordering in the array.
00367     /// This version should be used only when the order in the array is not an issue.
00368     Iterator EraseSwap( Iterator& in_rIter )
00369     {
00370         AKASSERT( m_pItems != 0 );
00371 
00372         if ( Length( ) > 1 )
00373         {
00374             // Swap last item with this one.
00375             TMovePolicy::Move( *in_rIter.pItem, Last( ) );
00376         }
00377 
00378         // Destroy.
00379         AKASSERT( Length( ) > 0 );
00380         Last( ).~T();
00381 
00382         m_uLength--;
00383 
00384         return in_rIter;
00385     }
00386 
00387     /// Pre-Allocate a number of spaces in the array
00388     AKRESULT Reserve( AkUInt32 in_ulReserve )
00389     {
00390         AKASSERT( m_pItems == 0 && m_uLength == 0 );
00391         AKASSERT( in_ulReserve || TGrowBy );
00392 
00393         if ( in_ulReserve )
00394         {
00395             m_pItems = (T *) TAlloc::Alloc( sizeof( T ) * in_ulReserve );
00396             if ( m_pItems == 0 )
00397                 return AK_InsufficientMemory;
00398 
00399             m_ulReserved = in_ulReserve;
00400         }
00401 
00402         return AK_Success;
00403     }
00404 
00405     AkUInt32 Reserved() const { return m_ulReserved; }
00406 
00407     /// Term the array. Must be called before destroying the object.
00408     void Term()
00409     {
00410         if ( m_pItems )
00411         {
00412             RemoveAll();
00413             TAlloc::Free( m_pItems );
00414             m_pItems = 0;
00415             m_ulReserved = 0;
00416         }
00417     }
00418 
00419     /// Returns the numbers of items in the array.
00420     AkForceInline AkUInt32 Length() const
00421     {
00422         return m_uLength;
00423     }
00424 
00425     /// Returns a pointer to the first item in the array.
00426     AkForceInline T * Data() const
00427     {
00428         return m_pItems;
00429     }
00430 
00431     /// Returns true if the number items in the array is 0, false otherwise.
00432     AkForceInline bool IsEmpty() const
00433     {
00434         return m_uLength == 0;
00435     }
00436     
00437     /// Returns a pointer to the specified item in the list if it exists, 0 if not found.
00438     AkForceInline T* Exists(ARG_T in_Item) const
00439     {
00440         Iterator it = FindEx( in_Item );
00441         return ( it != End() ) ? it.pItem : 0;
00442     }
00443 
00444     /// Add an item in the array, without filling it.
00445     /// Returns a pointer to the location to be filled.
00446     AkForceInline T * AddLast()
00447     {
00448         size_t cItems = Length();
00449 
00450 #if defined(_MSC_VER)
00451 #pragma warning( push )
00452 #pragma warning( disable : 4127 )
00453 #endif
00454         if ( ( cItems >= m_ulReserved ) && TGrowBy > 0 )
00455         {
00456             if ( !GrowArray() ) 
00457                 return 0;
00458         }
00459 #if defined(_MSC_VER)
00460 #pragma warning( pop )
00461 #endif
00462 
00463         // have we got space for a new one ?
00464         if(  cItems < m_ulReserved )
00465         {
00466             T * pEnd = m_pItems + m_uLength++;
00467             AkPlacementNew( pEnd ) T; 
00468             return pEnd;
00469         }
00470 
00471         return 0;
00472     }
00473 
00474     /// Add an item in the array, and fills it with the provided item.
00475     AkForceInline T * AddLast(ARG_T in_rItem)
00476     {
00477         T * pItem = AddLast();
00478         if ( pItem )
00479             *pItem = in_rItem;
00480         return pItem;
00481     }
00482 
00483     /// Returns a reference to the last item in the array.
00484     T& Last()
00485     {
00486         AKASSERT( m_uLength );
00487 
00488         return *( m_pItems + m_uLength - 1 );
00489     }
00490 
00491     /// Removes the last item from the array.
00492     void RemoveLast()
00493     {
00494         AKASSERT( m_uLength );
00495         ( m_pItems + m_uLength - 1 )->~T();
00496         m_uLength--;
00497     }
00498 
00499     /// Removes the specified item if found in the array.
00500     AKRESULT Remove(ARG_T in_rItem)
00501     {
00502         Iterator it = FindEx( in_rItem );
00503         if ( it != End() )
00504         {
00505             Erase( it );
00506             return AK_Success;
00507         }
00508 
00509         return AK_Fail;
00510     }
00511 
00512     /// Fast remove of the specified item in the array.
00513     /// This method do not guarantee keeping ordering of the array.
00514     AKRESULT RemoveSwap(ARG_T in_rItem)
00515     {
00516         Iterator it = FindEx( in_rItem );
00517         if ( it != End() )
00518         {
00519             EraseSwap( it );
00520             return AK_Success;
00521         }
00522 
00523         return AK_Fail;
00524     }
00525 
00526     /// Removes all items in the array
00527     void RemoveAll()
00528     {
00529         for ( Iterator it = Begin(), itEnd = End(); it != itEnd; ++it )
00530             (*it).~T();
00531         m_uLength = 0;
00532     }
00533 
00534     /// Operator [], return a reference to the specified index.
00535     AkForceInline T& operator[](unsigned int uiIndex) const
00536     {
00537         AKASSERT( m_pItems );
00538         AKASSERT( uiIndex < Length() );
00539         return m_pItems[uiIndex];
00540     }
00541 
00542     /// Insert an item at the specified position without filling it.
00543     /// Returns the pointer to the item to be filled.
00544     T * Insert(unsigned int in_uIndex)
00545     {
00546         AKASSERT( in_uIndex <= Length() );
00547 
00548         size_t cItems = Length();
00549 
00550 #if defined(_MSC_VER)
00551 #pragma warning( push )
00552 #pragma warning( disable : 4127 )
00553 #endif
00554         if ( ( cItems >= m_ulReserved ) && TGrowBy > 0 )
00555         {
00556             if ( !GrowArray() ) 
00557                 return 0;
00558         }
00559 #if defined(_MSC_VER)
00560 #pragma warning( pop )
00561 #endif
00562 
00563         // have we got space for a new one ?
00564         if(  cItems < m_ulReserved )
00565         {
00566             T * pItemLast = m_pItems + m_uLength++;
00567             AkPlacementNew( pItemLast ) T; 
00568 
00569             // Move items by 1
00570 
00571             for ( T * pItem = pItemLast; pItem > ( m_pItems + in_uIndex ); --pItem )
00572                 TMovePolicy::Move( pItem[ 0 ], pItem[ -1 ] );
00573 
00574             // Reinitialize item at index
00575 
00576             ( m_pItems + in_uIndex )->~T();
00577             AkPlacementNew( m_pItems + in_uIndex ) T; 
00578 
00579             return m_pItems + in_uIndex;
00580         }
00581 
00582         return 0;
00583     }
00584 
00585     /// Resize the array.
00586     bool GrowArray( AkUInt32 in_uGrowBy = TGrowBy )
00587     {
00588         AKASSERT( in_uGrowBy );
00589         
00590         AkUInt32 ulNewReserve = m_ulReserved + in_uGrowBy;
00591         T * pNewItems = NULL;
00592         size_t cItems = Length();
00593         if (TMovePolicy::IsTrivial())
00594         {
00595             pNewItems = (T *)TAlloc::ReAlloc(m_pItems, sizeof(T) * cItems, sizeof(T) * ulNewReserve);
00596             if (!pNewItems)
00597                 return false;           
00598         }
00599         else
00600         {
00601             pNewItems = (T *)TAlloc::Alloc(sizeof(T) * ulNewReserve);
00602             if (!pNewItems)
00603                 return false;
00604 
00605             // Copy all elements in new array, destroy old ones         
00606             if (m_pItems && m_pItems != pNewItems /*AkHybridAllocator may serve up same memory*/)
00607             {
00608                 for (size_t i = 0; i < cItems; ++i)
00609                 {
00610                     AkPlacementNew(pNewItems + i) T;
00611 
00612                     TMovePolicy::Move(pNewItems[i], m_pItems[i]);
00613 
00614                     m_pItems[i].~T();
00615                 }
00616 
00617                 TAlloc::Free(m_pItems);
00618             }
00619         }
00620     
00621         m_pItems = pNewItems;       
00622         m_ulReserved = ulNewReserve;
00623         return true;
00624     }
00625 
00626     /// Resize the array to the specified size.
00627     bool Resize(AkUInt32 in_uiSize)
00628     {
00629         AkUInt32 cItems = Length();
00630         if (in_uiSize < cItems)
00631         {
00632             //Destroy superfluous elements
00633             for(AkUInt32 i = in_uiSize - 1 ; i < cItems; i++)
00634             {
00635                 m_pItems[ i ].~T();
00636             }
00637             m_uLength = in_uiSize;
00638             return true;
00639         }
00640 
00641         if ( in_uiSize > m_ulReserved )
00642         {
00643             if ( !GrowArray(in_uiSize - cItems) ) 
00644                 return false;
00645         }
00646 
00647         //Create the missing items.
00648         for(size_t i = cItems; i < in_uiSize; i++)
00649         {
00650             AkPlacementNew( m_pItems + i ) T; 
00651         }
00652 
00653         m_uLength = in_uiSize;
00654         return true;
00655     }
00656 
00657     void Transfer(AkArray<T,ARG_T,TAlloc,TGrowBy,TMovePolicy>& in_rSource)
00658     {
00659         Term();
00660 
00661         TAlloc::TransferMem( (void*&)m_pItems, in_rSource, (void*)in_rSource.m_pItems );
00662         m_uLength = in_rSource.m_uLength;
00663         m_ulReserved = in_rSource.m_ulReserved;
00664 
00665         in_rSource.m_pItems = NULL;
00666         in_rSource.m_uLength = 0;
00667         in_rSource.m_ulReserved = 0;
00668     }
00669 
00670     AKRESULT Copy(const AkArray<T, ARG_T, TAlloc, TGrowBy, TMovePolicy>& in_rSource)
00671     {
00672         Term();
00673 
00674         if (Resize(in_rSource.Length()))
00675         {
00676             for (AkUInt32 i = 0; i < in_rSource.Length(); ++i)
00677                 m_pItems[i] = in_rSource.m_pItems[i];
00678             return AK_Success;
00679         }
00680         return AK_Fail;
00681     }
00682 
00683 protected:
00684 
00685     T *         m_pItems;       ///< pointer to the beginning of the array.
00686     AkUInt32    m_uLength;      ///< number of items in the array.
00687     AkUInt32    m_ulReserved;   ///< how many we can have at most (currently allocated).
00688 };
00689 
00690 
00691 #endif