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 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</span>
00180         Iterator operator+(AkUInt32 inc) const
00181         {
00182             AKASSERT( pItem );
00183             Iterator returnedIt;
00184             returnedIt.pItem = pItem + inc;
00185             return returnedIt;
00186         }
00187 
00188         /// - operator</span>
00189         AkUInt32 operator-(Iterator const& rhs) const
00190         {
00191             AKASSERT((pItem && rhs.pItem)||(!pItem && !rhs.pItem));
00192             return (AkUInt32)(pItem - rhs.pItem);
00193         }
00194 
00195         /// ++ operator</span>
00196         Iterator& operator++()
00197         {
00198             AKASSERT( pItem );
00199             ++pItem;
00200             return *this;
00201         }
00202 
00203         /// -- operator</span>
00204         Iterator& operator--()
00205         {
00206             AKASSERT( pItem );
00207             --pItem;
00208             return *this;
00209         }
00210 
00211         /// * operator</span>
00212         T& operator*()
00213         {
00214             AKASSERT( pItem );
00215             return *pItem;
00216         }
00217 
00218         /// == operator</span>
00219         bool operator ==( const Iterator& in_rOp ) const
00220         {
00221             return ( pItem == in_rOp.pItem );
00222         }
00223 
00224         /// != operator</span>
00225         bool operator !=( const Iterator& in_rOp ) const
00226         {
00227             return ( pItem != in_rOp.pItem );
00228         }
00229     };
00230 #endif // #ifndef SWIG
00231 
00232     /// Returns the iterator to the first item of the array, will be End() if the array is empty.
00233     Iterator Begin() const
00234     {
00235         Iterator returnedIt;
00236         returnedIt.pItem = m_pItems;
00237         return returnedIt;
00238     }
00239 
00240     /// Returns the iterator to the end of the array
00241     Iterator End() const
00242     {
00243         Iterator returnedIt;
00244         returnedIt.pItem = m_pItems + m_uLength;
00245         return returnedIt;
00246     }
00247 
00248     /// Returns the iterator th the specified item, will be End() if the item is not found
00249     Iterator FindEx( ARG_T in_Item ) const
00250     {
00251         Iterator it = Begin();
00252 
00253         for ( Iterator itEnd = End(); it != itEnd; ++it )
00254         {
00255             if ( *it == in_Item )
00256                 break;
00257         }
00258 
00259         return it;
00260     }
00261 
00262     /// Returns the iterator th the specified item, will be End() if the item is not found
00263     /// The array must be in ascending sorted order.
00264     Iterator BinarySearch( ARG_T in_Item ) const
00265     {
00266         Iterator itResult = End();
00267         if (m_pItems)
00268         {
00269             T * pTop = m_pItems, * pBottom = m_pItems + m_uLength;
00270 
00271             while ( pTop <= pBottom )
00272             {
00273                 T* pThis = ( pBottom - pTop ) / 2 + pTop; 
00274                 if( in_Item < *pThis )
00275                     pBottom = pThis - 1;
00276                 else if ( in_Item > *pThis ) 
00277                     pTop = pThis + 1;
00278                 else
00279                 {
00280                     itResult.pItem = pThis;
00281                     break;
00282                 }
00283             }
00284         }
00285 
00286         return itResult;
00287     }
00288 
00289     /// Erase the specified iterator from the array
00290     Iterator Erase( Iterator& in_rIter )
00291     {
00292         AKASSERT( m_pItems != 0 );
00293 
00294         // Move items by 1
00295 
00296         T * pItemLast = m_pItems + m_uLength - 1;
00297 
00298         for ( T * pItem = in_rIter.pItem; pItem < pItemLast; pItem++ )
00299             TMovePolicy::Move( pItem[ 0 ], pItem[ 1 ] );
00300 
00301         // Destroy the last item
00302 
00303         pItemLast->~T();
00304 
00305         m_uLength--;
00306 
00307         return in_rIter;
00308     }
00309 
00310     /// Erase the item at the specified index
00311     void Erase( unsigned int in_uIndex )
00312     {
00313         AKASSERT( m_pItems != 0 );
00314 
00315         // Move items by 1
00316 
00317         T * pItemLast = m_pItems + m_uLength - 1;
00318 
00319         for ( T * pItem = m_pItems+in_uIndex; pItem < pItemLast; pItem++ )
00320             TMovePolicy::Move( pItem[ 0 ], pItem[ 1 ] );
00321 
00322         // Destroy the last item
00323 
00324         pItemLast->~T();
00325 
00326         m_uLength--;
00327     }
00328 
00329     /// Erase the specified iterator in the array. but it dos not guarantee the ordering in the array.
00330     /// This version should be used only when the order in the array is not an issue.
00331     Iterator EraseSwap( Iterator& in_rIter )
00332     {
00333         AKASSERT( m_pItems != 0 );
00334 
00335         if ( Length( ) > 1 )
00336         {
00337             // Swap last item with this one.
00338             TMovePolicy::Move( *in_rIter.pItem, Last( ) );
00339         }
00340 
00341         // Destroy.
00342         AKASSERT( Length( ) > 0 );
00343         Last( ).~T();
00344 
00345         m_uLength--;
00346 
00347         return in_rIter;
00348     }
00349 
00350     /// Pre-Allocate a number of spaces in the array
00351     AKRESULT Reserve( AkUInt32 in_ulReserve )
00352     {
00353         AKASSERT( m_pItems == 0 && m_uLength == 0 );
00354         AKASSERT( in_ulReserve || TGrowBy );
00355 
00356         if ( in_ulReserve )
00357         {
00358             m_pItems = (T *) TAlloc::Alloc( sizeof( T ) * in_ulReserve );
00359             if ( m_pItems == 0 )
00360                 return AK_InsufficientMemory;
00361 
00362             m_ulReserved = in_ulReserve;
00363         }
00364 
00365         return AK_Success;
00366     }
00367 
00368     AkUInt32 Reserved() const { return m_ulReserved; }
00369 
00370     /// Term the array. Must be called before destroying the object.
00371     void Term()
00372     {
00373         if ( m_pItems )
00374         {
00375             RemoveAll();
00376             TAlloc::Free( m_pItems );
00377             m_pItems = 0;
00378             m_ulReserved = 0;
00379         }
00380     }
00381 
00382     /// Returns the numbers of items in the array.
00383     AkForceInline AkUInt32 Length() const
00384     {
00385         return m_uLength;
00386     }
00387 
00388     /// Returns a pointer to the first item in the array.
00389     AkForceInline T * Data() const
00390     {
00391         return m_pItems;
00392     }
00393 
00394     /// Returns true if the number items in the array is 0, false otherwise.
00395     AkForceInline bool IsEmpty() const
00396     {
00397         return m_uLength == 0;
00398     }
00399     
00400     /// Returns a pointer to the specified item in the list if it exists, 0 if not found.
00401     T* Exists(ARG_T in_Item) const
00402     {
00403         Iterator it = FindEx( in_Item );
00404         return ( it != End() ) ? it.pItem : 0;
00405     }
00406 
00407     /// Add an item in the array, without filling it.
00408     /// Returns a pointer to the location to be filled.
00409     T * AddLast()
00410     {
00411         size_t cItems = Length();
00412 
00413 #if defined(_MSC_VER)
00414 #pragma warning( push )
00415 #pragma warning( disable : 4127 )
00416 #endif
00417         if ( ( cItems >= m_ulReserved ) && TGrowBy > 0 )
00418         {
00419             if ( !GrowArray() ) 
00420                 return 0;
00421         }
00422 #if defined(_MSC_VER)
00423 #pragma warning( pop )
00424 #endif
00425 
00426         // have we got space for a new one ?
00427         if(  cItems < m_ulReserved )
00428         {
00429             T * pEnd = m_pItems + m_uLength++;
00430             AkPlacementNew( pEnd ) T; 
00431             return pEnd;
00432         }
00433 
00434         return 0;
00435     }
00436 
00437     /// Add an item in the array, and fills it with the provided item.
00438     T * AddLast(ARG_T in_rItem)
00439     {
00440         T * pItem = AddLast();
00441         if ( pItem )
00442             *pItem = in_rItem;
00443         return pItem;
00444     }
00445 
00446     /// Returns a reference to the last item in the array.
00447     T& Last()
00448     {
00449         AKASSERT( m_uLength );
00450 
00451         return *( m_pItems + m_uLength - 1 );
00452     }
00453 
00454     /// Removes the last item from the array.
00455     void RemoveLast()
00456     {
00457         AKASSERT( m_uLength );
00458         ( m_pItems + m_uLength - 1 )->~T();
00459         m_uLength--;
00460     }
00461 
00462     /// Removes the specified item if found in the array.
00463     AKRESULT Remove(ARG_T in_rItem)
00464     {
00465         Iterator it = FindEx( in_rItem );
00466         if ( it != End() )
00467         {
00468             Erase( it );
00469             return AK_Success;
00470         }
00471 
00472         return AK_Fail;
00473     }
00474 
00475     /// Fast remove of the specified item in the array.
00476     /// This method do not guarantee keeping ordering of the array.
00477     AKRESULT RemoveSwap(ARG_T in_rItem)
00478     {
00479         Iterator it = FindEx( in_rItem );
00480         if ( it != End() )
00481         {
00482             EraseSwap( it );
00483             return AK_Success;
00484         }
00485 
00486         return AK_Fail;
00487     }
00488 
00489     /// Removes all items in the array
00490     void RemoveAll()
00491     {
00492         for ( Iterator it = Begin(), itEnd = End(); it != itEnd; ++it )
00493             (*it).~T();
00494         m_uLength = 0;
00495     }
00496 
00497     /// Operator [], return a reference to the specified index.
00498     AkForceInline T& operator[](unsigned int uiIndex) const
00499     {
00500         AKASSERT( m_pItems );
00501         AKASSERT( uiIndex < Length() );
00502         return m_pItems[uiIndex];
00503     }
00504 
00505     /// Insert an item at the specified position without filling it.
00506     /// Returns the pointer to the item to be filled.
00507     T * Insert(unsigned int in_uIndex)
00508     {
00509         AKASSERT( in_uIndex <= Length() );
00510 
00511         size_t cItems = Length();
00512 
00513 #if defined(_MSC_VER)
00514 #pragma warning( push )
00515 #pragma warning( disable : 4127 )
00516 #endif
00517         if ( ( cItems >= m_ulReserved ) && TGrowBy > 0 )
00518         {
00519             if ( !GrowArray() ) 
00520                 return 0;
00521         }
00522 #if defined(_MSC_VER)
00523 #pragma warning( pop )
00524 #endif
00525 
00526         // have we got space for a new one ?
00527         if(  cItems < m_ulReserved )
00528         {
00529             T * pItemLast = m_pItems + m_uLength++;
00530             AkPlacementNew( pItemLast ) T; 
00531 
00532             // Move items by 1
00533 
00534             for ( T * pItem = pItemLast; pItem > ( m_pItems + in_uIndex ); --pItem )
00535                 TMovePolicy::Move( pItem[ 0 ], pItem[ -1 ] );
00536 
00537             // Reinitialize item at index
00538 
00539             ( m_pItems + in_uIndex )->~T();
00540             AkPlacementNew( m_pItems + in_uIndex ) T; 
00541 
00542             return m_pItems + in_uIndex;
00543         }
00544 
00545         return 0;
00546     }
00547 
00548     /// Resize the array.
00549     bool GrowArray( AkUInt32 in_uGrowBy = TGrowBy )
00550     {
00551         AKASSERT( in_uGrowBy );
00552         
00553         AkUInt32 ulNewReserve = m_ulReserved + in_uGrowBy;
00554         T * pNewItems = (T *) TAlloc::Alloc( sizeof( T ) * ulNewReserve );
00555         if ( !pNewItems ) 
00556             return false;
00557 
00558         // Copy all elements in new array, destroy old ones
00559 
00560         size_t cItems = Length();
00561 
00562         if ( m_pItems && m_pItems != pNewItems /*AkHybridAllocator may serve up same memory*/ ) 
00563         {
00564             for ( size_t i = 0; i < cItems; ++i )
00565             {
00566                 AkPlacementNew( pNewItems + i ) T; 
00567 
00568                 TMovePolicy::Move( pNewItems[ i ], m_pItems[ i ] );
00569                 
00570                 m_pItems[ i ].~T();
00571             }
00572 
00573             TAlloc::Free( m_pItems );
00574         }
00575 
00576         m_pItems = pNewItems;
00577         m_ulReserved = ulNewReserve;
00578 
00579         return true;
00580     }
00581 
00582     /// Resize the array to the specified size.
00583     bool Resize(AkUInt32 in_uiSize)
00584     {
00585         AkUInt32 cItems = Length();
00586         if (in_uiSize < cItems)
00587         {
00588             //Destroy superfluous elements
00589             for(AkUInt32 i = in_uiSize - 1 ; i < cItems; i++)
00590             {
00591                 m_pItems[ i ].~T();
00592             }
00593             m_uLength = in_uiSize;
00594             return true;
00595         }
00596 
00597         if ( in_uiSize > m_ulReserved )
00598         {
00599             if ( !GrowArray(in_uiSize - cItems) ) 
00600                 return false;
00601         }
00602 
00603         //Create the missing items.
00604         for(size_t i = cItems; i < in_uiSize; i++)
00605         {
00606             AkPlacementNew( m_pItems + i ) T; 
00607         }
00608 
00609         m_uLength = in_uiSize;
00610         return true;
00611     }
00612 
00613     void Transfer(AkArray<T,ARG_T,TAlloc,TGrowBy,TMovePolicy>& in_rSource)
00614     {
00615         Term();
00616 
00617         TAlloc::TransferMem( (void **)&m_pItems, in_rSource, (void*)in_rSource.m_pItems );
00618         m_uLength = in_rSource.m_uLength;
00619         m_ulReserved = in_rSource.m_ulReserved;
00620 
00621         in_rSource.m_pItems = NULL;
00622         in_rSource.m_uLength = 0;
00623         in_rSource.m_ulReserved = 0;
00624     }
00625 
00626     AKRESULT Copy(const AkArray<T, ARG_T, TAlloc, TGrowBy, TMovePolicy>& in_rSource)
00627     {
00628         Term();
00629 
00630         if (Resize(in_rSource.Length()))
00631         {
00632             for (AkUInt32 i = 0; i < in_rSource.Length(); ++i)
00633                 m_pItems[i] = in_rSource.m_pItems[i];
00634             return AK_Success;
00635         }
00636         return AK_Fail;
00637     }
00638 
00639 protected:
00640 
00641     T *         m_pItems;       ///< pointer to the beginning of the array.
00642     AkUInt32    m_uLength;      ///< number of items in the array.
00643     AkUInt32    m_ulReserved;   ///< how many we can have at most (currently allocated).
00644 };
00645 
00646 
00647 #endif