Table of Contents

include/AK/Tools/Common/AkListBare.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 // AkListBare.h
00029 
00030 #ifndef _AKLISTBARE_H
00031 #define _AKLISTBARE_H
00032 
00033 // this one lets you define the structure
00034 // only requirement is that T must have member pNextItem (if using the default AkListBareNextItem policy struct).
00035 // client is responsible for allocation/deallocation of T.
00036 
00037 // WATCH OUT !
00038 // - remember that removeall/term can't delete the elements for you.
00039 // - be sure to destroy elements AFTER removing them from the list, as remove will
00040 // access members of the element.
00041 
00042 /* Usage: List of AkMyType.
00043 
00044 - With default AkMyType::pNextItem, no count (Length() is not available):
00045 typedef AkListBare<AkMyType> AkMyList1;
00046 
00047 - With custom AkMyType::pNextItemCustom, no count:
00048 struct AkListBareNextItemCustom
00049 {
00050     static AkForceInline AkMyType *& Get( AkMyType * in_pItem ) 
00051     {
00052         return in_pItem->pNextItemCustom;
00053     }
00054 };
00055 typedef AkListBare<AkMyType,AkListBareNextItemCustom> AkMyList2;
00056 
00057 - With default AkMyType::pNextItem, WITH count (Length() is available):
00058 typedef AkListBare<AkMyType,AkListBareNextItem,AkCountPolicyWithCount> AkMyList3;
00059 
00060 */
00061 
00062 //
00063 // List bare policy classes.
00064 //
00065 
00066 /// Next item name policy.
00067 template <class T> struct AkListBareNextItem
00068 {
00069     /// Default policy.
00070     static AkForceInline T *& Get( T * in_pItem ) 
00071     {
00072         return in_pItem->pNextItem;
00073     }
00074 };
00075 
00076 /// Item count policy. These policy classes must define protected methods 
00077 /// ResetCount(), IncrementCount(), DecrementCount() and optionally, public unsigned int Length() const.
00078 template <class T> 
00079 class AkCountPolicyNoCount
00080 {
00081 protected:
00082     AkForceInline void ResetCount( T* ) {}
00083     AkForceInline void IncrementCount( T* ) {}
00084     AkForceInline void DecrementCount( T* ) {}
00085 };
00086 
00087 template <class T> 
00088 class AkCountPolicyWithCount
00089 {
00090 public:
00091     /// Get list length.
00092     AkForceInline unsigned int Length() const
00093     {
00094         return m_ulNumListItems;
00095     }
00096 
00097 protected:
00098     AkCountPolicyWithCount() :m_ulNumListItems( 0 ) {}
00099 
00100     AkForceInline void ResetCount( T* ) { m_ulNumListItems = 0; }
00101     AkForceInline void IncrementCount( T* ) { ++m_ulNumListItems; }
00102     AkForceInline void DecrementCount( T* ) { --m_ulNumListItems; }
00103 
00104 private:
00105     unsigned int    m_ulNumListItems;           ///< how many we have
00106 };
00107 
00108 /// Last item policy. These policy classes must define protected methods 
00109 /// UpdateLast(), SetLast(), RemoveItem() and AddItem().
00110 template <class T> 
00111 class AkLastPolicyWithLast
00112 {
00113 public:
00114     /// Get last element.
00115     AkForceInline T * Last() { return m_pLast; }
00116     AkForceInline const T * Last() const { return m_pLast; }
00117 
00118 protected:
00119     AkForceInline AkLastPolicyWithLast() : m_pLast( NULL ) {}
00120 
00121     // Policy interface:
00122     // UpdateLast() is called by host to inform the policy that it should set the last item to a new value.
00123     // The policy is thus free to do what it wants. On the other hand, SetLast() must make sense for the user of the list,
00124     // otherwise it must not be implemented.
00125     AkForceInline void UpdateLast( T * in_pLast ) { m_pLast = in_pLast; }
00126     AkForceInline void SetLast( T * in_pLast ) { m_pLast = in_pLast; }
00127     AkForceInline void RemoveItem( T * in_pItem, T * in_pPrevItem )
00128     {
00129         // Is it the last one ?
00130         if( in_pItem == m_pLast )
00131         {
00132             // new last one is the previous one
00133             m_pLast = in_pPrevItem;
00134         }
00135     }
00136     AkForceInline void AddItem( T * in_pItem, T * in_pNextItem )
00137     {
00138         // Update tail.
00139         // Note: will never occur since it is used with iteratorEx (have EndEx?).
00140         if ( in_pNextItem == NULL )   
00141             m_pLast = in_pItem;
00142     }
00143 
00144 protected:
00145     T *             m_pLast;                    ///< bottom of list
00146 };
00147 
00148 template <class T> 
00149 class AkLastPolicyNoLast
00150 {
00151 protected:
00152     // Policy interface:
00153     // UpdateLast() is called by host to inform the policy that it should set the last item to a new value.
00154     // The policy is thus free to do what it wants. On the other hand, SetLast() must make sense for the user of the list,
00155     // otherwise it must not be implemented.
00156     AkForceInline void UpdateLast( T * ) {}
00157     // SetLast is voluntarily left undefined so that calling AkListBare::AddLast() with this policy results in a compile-time error.
00158     //AkForceInline void SetLast( T * in_pLast );
00159     AkForceInline void RemoveItem( T *, T * ) {}
00160     AkForceInline void AddItem( T *, T * ) {}
00161 };
00162 
00163 
00164 /// Implementation of List Bare.
00165 template <class T, template <class> class U_NEXTITEM = AkListBareNextItem, template <class> class COUNT_POLICY = AkCountPolicyNoCount, template <class> class LAST_POLICY = AkLastPolicyWithLast > class AkListBare : public COUNT_POLICY< T >, public LAST_POLICY< T >
00166 {
00167 public:
00168     /// Iterator.
00169     struct Iterator
00170     {
00171         T* pItem;   ///< Next item.
00172 
00173         /// Operator ++.
00174         inline Iterator& operator++()
00175         {
00176             AKASSERT( pItem );
00177             pItem = U_NEXTITEM<T>::Get( pItem );
00178             return *this;
00179         }
00180 
00181         /// Operator *.
00182         inline T * operator*() const
00183         {
00184             AKASSERT( pItem );
00185             return pItem;
00186         }
00187 
00188         /// Operator !=.
00189         bool operator !=( const Iterator& in_rOp ) const
00190         {
00191             return ( pItem != in_rOp.pItem );
00192         }
00193         
00194         /// Operator ==.
00195         bool operator ==( const Iterator& in_rOp ) const
00196         {
00197             return ( pItem == in_rOp.pItem );
00198         }
00199     };
00200 
00201     /// The IteratorEx iterator is intended for usage when a possible erase may occurs
00202     /// when simply iterating trough a list, use the simple Iterator, it is faster and lighter.
00203     struct IteratorEx : public Iterator
00204     {
00205         T* pPrevItem;   ///< Previous item.
00206 
00207         /// Operator ++.
00208         IteratorEx& operator++()
00209         {
00210             AKASSERT( this->pItem );
00211             
00212             pPrevItem = this->pItem;
00213             this->pItem = U_NEXTITEM<T>::Get( this->pItem );
00214             
00215             return *this;
00216         }
00217     };
00218 
00219     /// Erase item.
00220     IteratorEx Erase( const IteratorEx& in_rIter )
00221     {
00222         IteratorEx returnedIt;
00223         returnedIt.pItem = U_NEXTITEM<T>::Get( in_rIter.pItem );
00224         returnedIt.pPrevItem = in_rIter.pPrevItem;
00225 
00226         RemoveItem( in_rIter.pItem, in_rIter.pPrevItem );
00227 
00228         return returnedIt;
00229     }
00230 
00231     /// Insert item.
00232     IteratorEx Insert( const IteratorEx& in_rIter,
00233                        T * in_pItem )
00234     {
00235         IteratorEx returnedIt;
00236         AddItem( in_pItem, in_rIter.pItem, in_rIter.pPrevItem );
00237         returnedIt = in_rIter;
00238         returnedIt.pPrevItem = in_pItem;
00239         return returnedIt;
00240     }
00241 
00242     /// End condition.
00243     inline Iterator End() const
00244     {
00245         Iterator returnedIt;
00246         returnedIt.pItem = NULL;
00247         return returnedIt;
00248     }
00249 
00250     /// Get IteratorEx at beginning.
00251     inline IteratorEx BeginEx()
00252     {
00253         IteratorEx returnedIt;
00254         
00255         returnedIt.pItem = m_pFirst;
00256         returnedIt.pPrevItem = NULL;
00257         
00258         return returnedIt;
00259     }
00260 
00261     /// Get Iterator at beginning.
00262     inline Iterator Begin() const
00263     {
00264         Iterator returnedIt;
00265         
00266         returnedIt.pItem = m_pFirst;
00267         
00268         return returnedIt;
00269     }
00270 
00271     /// Get Iterator from item.
00272     inline IteratorEx FindEx( T *  in_pItem )
00273     {
00274         IteratorEx it = BeginEx();
00275         for ( ; it != End(); ++it )
00276         {
00277             if ( it.pItem == in_pItem )
00278                 break;
00279         }
00280 
00281         return it;
00282     }
00283 
00284     /// Constructor.
00285     AkListBare()
00286     : m_pFirst( NULL )
00287     {
00288     }
00289     
00290     /// Destructor.
00291     ~AkListBare()
00292     {
00293     }
00294 
00295     /// Terminate.
00296     void Term()
00297     {
00298         RemoveAll();
00299     }
00300 
00301     /// Add element at the beginning of list.
00302     void AddFirst( T * in_pItem )
00303     {
00304         if ( m_pFirst == NULL )
00305         {
00306             m_pFirst = in_pItem;
00307             LAST_POLICY<T>::UpdateLast( in_pItem );
00308             U_NEXTITEM<T>::Get( in_pItem ) = NULL;
00309         }
00310         else
00311         {
00312             U_NEXTITEM<T>::Get( in_pItem ) = m_pFirst;
00313             m_pFirst = in_pItem;
00314         }
00315 
00316         COUNT_POLICY<T>::IncrementCount( in_pItem );
00317     }
00318 
00319     /// Add element at the end of list.
00320     void AddLast( T * in_pItem )
00321     {
00322         U_NEXTITEM<T>::Get( in_pItem ) = NULL;
00323 
00324         if ( m_pFirst == NULL )
00325         {
00326             m_pFirst = in_pItem;
00327         }
00328         else
00329         {
00330             U_NEXTITEM<T>::Get( LAST_POLICY<T>::Last() ) = in_pItem;
00331         }
00332 
00333         LAST_POLICY<T>::SetLast( in_pItem );
00334 
00335         COUNT_POLICY<T>::IncrementCount( in_pItem );
00336     }
00337 
00338     /// Remove an element.
00339     AKRESULT Remove( T * in_pItem )
00340     {
00341         IteratorEx it = FindEx( in_pItem );
00342         if ( it != End() )
00343         {
00344             Erase( it );
00345             return AK_Success;
00346         }
00347 
00348         return AK_Fail;
00349     }
00350 
00351     /// Remove the first element.
00352     AKRESULT RemoveFirst()
00353     {
00354         if( m_pFirst == NULL )
00355             return AK_Fail;
00356 
00357         if ( U_NEXTITEM<T>::Get( m_pFirst ) == NULL )
00358         {
00359             m_pFirst = NULL;
00360             LAST_POLICY<T>::UpdateLast( NULL );
00361         }
00362         else
00363         {
00364             m_pFirst = U_NEXTITEM<T>::Get( m_pFirst );
00365         }
00366 
00367         COUNT_POLICY<T>::DecrementCount( m_pFirst );
00368 
00369         return AK_Success;
00370     }
00371 
00372     /// Remove all elements.
00373     AkForceInline void RemoveAll()
00374     {
00375         // Items being externally managed, all we need to do here is clear our members.
00376         m_pFirst = NULL;
00377         LAST_POLICY<T>::UpdateLast( NULL );
00378         COUNT_POLICY<T>::ResetCount( m_pFirst );
00379     }
00380 
00381     /// Get first element.
00382     AkForceInline T * First()
00383     {
00384         return m_pFirst;
00385     }
00386 
00387     /// Empty condition.
00388     AkForceInline bool IsEmpty() const
00389     {
00390         return m_pFirst == NULL;
00391     }
00392 
00393     /// Remove an element.
00394     void RemoveItem( T * in_pItem, T * in_pPrevItem )
00395     {
00396         // Is it the first one ?
00397 
00398         if( in_pItem == m_pFirst )
00399         {
00400             // new first one is the next one
00401             m_pFirst = U_NEXTITEM<T>::Get( in_pItem );
00402         }
00403         else
00404         {
00405             // take it out of the used space
00406             U_NEXTITEM<T>::Get( in_pPrevItem ) = U_NEXTITEM<T>::Get( in_pItem );
00407         }
00408 
00409         LAST_POLICY<T>::RemoveItem( in_pItem, in_pPrevItem );
00410 
00411         COUNT_POLICY<T>::DecrementCount( m_pFirst );
00412     }
00413 
00414     /// Add an element.
00415     void AddItem( T * in_pItem, T * in_pNextItem, T * in_pPrevItem )
00416     {
00417         U_NEXTITEM<T>::Get( in_pItem ) = in_pNextItem;
00418 
00419         if ( in_pPrevItem == NULL )
00420             m_pFirst = in_pItem;
00421         else
00422             U_NEXTITEM<T>::Get( in_pPrevItem ) = in_pItem;
00423 
00424         LAST_POLICY<T>::AddItem( in_pItem, in_pNextItem );
00425         
00426         COUNT_POLICY<T>::IncrementCount( in_pItem );
00427     }
00428 
00429 protected:
00430     T *             m_pFirst;                   ///< top of list
00431 };
00432 
00433 #endif // _AKLISTBARE_H