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()
00116     {
00117         return m_pLast;
00118     }
00119 
00120 protected:
00121     AkForceInline AkLastPolicyWithLast() : m_pLast( NULL ) {}
00122 
00123     // Policy interface:
00124     // UpdateLast() is called by host to inform the policy that it should set the last item to a new value.
00125     // The policy is thus free to do what it wants. On the other hand, SetLast() must make sense for the user of the list,
00126     // otherwise it must not be implemented.
00127     AkForceInline void UpdateLast( T * in_pLast ) { m_pLast = in_pLast; }
00128     AkForceInline void SetLast( T * in_pLast ) { m_pLast = in_pLast; }
00129     AkForceInline void RemoveItem( T * in_pItem, T * in_pPrevItem )
00130     {
00131         // Is it the last one ?
00132         if( in_pItem == m_pLast )
00133         {
00134             // new last one is the previous one
00135             m_pLast = in_pPrevItem;
00136         }
00137     }
00138     AkForceInline void AddItem( T * in_pItem, T * in_pNextItem )
00139     {
00140         // Update tail.
00141         // Note: will never occur since it is used with iteratorEx (have EndEx?).
00142         if ( in_pNextItem == NULL )   
00143             m_pLast = in_pItem;
00144     }
00145 
00146 protected:
00147     T *             m_pLast;                    ///< bottom of list
00148 };
00149 
00150 template <class T> 
00151 class AkLastPolicyNoLast
00152 {
00153 protected:
00154     // Policy interface:
00155     // UpdateLast() is called by host to inform the policy that it should set the last item to a new value.
00156     // The policy is thus free to do what it wants. On the other hand, SetLast() must make sense for the user of the list,
00157     // otherwise it must not be implemented.
00158     AkForceInline void UpdateLast( T * ) {}
00159     // SetLast is voluntarily left undefined so that calling AkListBare::AddLast() with this policy results in a compile-time error.
00160     //AkForceInline void SetLast( T * in_pLast );
00161     AkForceInline void RemoveItem( T *, T * ) {}
00162     AkForceInline void AddItem( T *, T * ) {}
00163 };
00164 
00165 
00166 /// Implementation of List Bare.
00167 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 >
00168 {
00169 public:
00170     /// Iterator.
00171     struct Iterator
00172     {
00173         T* pItem;   ///< Next item.
00174 
00175         /// Operator ++.
00176         inline Iterator& operator++()
00177         {
00178             AKASSERT( pItem );
00179             pItem = U_NEXTITEM<T>::Get( pItem );
00180             return *this;
00181         }
00182 
00183         /// Operator *.
00184         inline T * operator*() const
00185         {
00186             AKASSERT( pItem );
00187             return pItem;
00188         }
00189 
00190         /// Operator !=.
00191         bool operator !=( const Iterator& in_rOp ) const
00192         {
00193             return ( pItem != in_rOp.pItem );
00194         }
00195         
00196         /// Operator ==.
00197         bool operator ==( const Iterator& in_rOp ) const
00198         {
00199             return ( pItem == in_rOp.pItem );
00200         }
00201     };
00202 
00203     /// The IteratorEx iterator is intended for usage when a possible erase may occurs
00204     /// when simply iterating trough a list, use the simple Iterator, it is faster and lighter.
00205     struct IteratorEx : public Iterator
00206     {
00207         T* pPrevItem;   ///< Previous item.
00208 
00209         /// Operator ++.
00210         IteratorEx& operator++()
00211         {
00212             AKASSERT( this->pItem );
00213             
00214             pPrevItem = this->pItem;
00215             this->pItem = U_NEXTITEM<T>::Get( this->pItem );
00216             
00217             return *this;
00218         }
00219     };
00220 
00221     /// Erase item.
00222     IteratorEx Erase( const IteratorEx& in_rIter )
00223     {
00224         IteratorEx returnedIt;
00225         returnedIt.pItem = U_NEXTITEM<T>::Get( in_rIter.pItem );
00226         returnedIt.pPrevItem = in_rIter.pPrevItem;
00227 
00228         RemoveItem( in_rIter.pItem, in_rIter.pPrevItem );
00229 
00230         return returnedIt;
00231     }
00232 
00233     /// Insert item.
00234     IteratorEx Insert( const IteratorEx& in_rIter,
00235                        T * in_pItem )
00236     {
00237         IteratorEx returnedIt;
00238         AddItem( in_pItem, in_rIter.pItem, in_rIter.pPrevItem );
00239         returnedIt = in_rIter;
00240         returnedIt.pPrevItem = in_pItem;
00241         return returnedIt;
00242     }
00243 
00244     /// End condition.
00245     inline Iterator End() const
00246     {
00247         Iterator returnedIt;
00248         returnedIt.pItem = NULL;
00249         return returnedIt;
00250     }
00251 
00252     /// Get IteratorEx at beginning.
00253     inline IteratorEx BeginEx()
00254     {
00255         IteratorEx returnedIt;
00256         
00257         returnedIt.pItem = m_pFirst;
00258         returnedIt.pPrevItem = NULL;
00259         
00260         return returnedIt;
00261     }
00262 
00263     /// Get Iterator at beginning.
00264     inline Iterator Begin() const
00265     {
00266         Iterator returnedIt;
00267         
00268         returnedIt.pItem = m_pFirst;
00269         
00270         return returnedIt;
00271     }
00272 
00273     /// Get Iterator from item.
00274     inline IteratorEx FindEx( T *  in_pItem )
00275     {
00276         IteratorEx it = BeginEx();
00277         for ( ; it != End(); ++it )
00278         {
00279             if ( it.pItem == in_pItem )
00280                 break;
00281         }
00282 
00283         return it;
00284     }
00285 
00286     /// Constructor.
00287     AkListBare()
00288     : m_pFirst( NULL )
00289     {
00290     }
00291     
00292     /// Destructor.
00293     ~AkListBare()
00294     {
00295     }
00296 
00297     /// Terminate.
00298     void Term()
00299     {
00300         RemoveAll();
00301     }
00302 
00303     /// Add element at the beginning of list.
00304     void AddFirst( T * in_pItem )
00305     {
00306         if ( m_pFirst == NULL )
00307         {
00308             m_pFirst = in_pItem;
00309             LAST_POLICY<T>::UpdateLast( in_pItem );
00310             U_NEXTITEM<T>::Get( in_pItem ) = NULL;
00311         }
00312         else
00313         {
00314             U_NEXTITEM<T>::Get( in_pItem ) = m_pFirst;
00315             m_pFirst = in_pItem;
00316         }
00317 
00318         COUNT_POLICY<T>::IncrementCount( in_pItem );
00319     }
00320 
00321     /// Add element at the end of list.
00322     void AddLast( T * in_pItem )
00323     {
00324         U_NEXTITEM<T>::Get( in_pItem ) = NULL;
00325 
00326         if ( m_pFirst == NULL )
00327         {
00328             m_pFirst = in_pItem;
00329         }
00330         else
00331         {
00332             U_NEXTITEM<T>::Get( LAST_POLICY<T>::Last() ) = in_pItem;
00333         }
00334 
00335         LAST_POLICY<T>::SetLast( in_pItem );
00336 
00337         COUNT_POLICY<T>::IncrementCount( in_pItem );
00338     }
00339 
00340     /// Remove an element.
00341     AKRESULT Remove( T * in_pItem )
00342     {
00343         IteratorEx it = FindEx( in_pItem );
00344         if ( it != End() )
00345         {
00346             Erase( it );
00347             return AK_Success;
00348         }
00349 
00350         return AK_Fail;
00351     }
00352 
00353     /// Remove the first element.
00354     AKRESULT RemoveFirst()
00355     {
00356         if( m_pFirst == NULL )
00357             return AK_Fail;
00358 
00359         if ( U_NEXTITEM<T>::Get( m_pFirst ) == NULL )
00360         {
00361             m_pFirst = NULL;
00362             LAST_POLICY<T>::UpdateLast( NULL );
00363         }
00364         else
00365         {
00366             m_pFirst = U_NEXTITEM<T>::Get( m_pFirst );
00367         }
00368 
00369         COUNT_POLICY<T>::DecrementCount( m_pFirst );
00370 
00371         return AK_Success;
00372     }
00373 
00374     /// Remove all elements.
00375     AkForceInline void RemoveAll()
00376     {
00377         // Items being externally managed, all we need to do here is clear our members.
00378         m_pFirst = NULL;
00379         LAST_POLICY<T>::UpdateLast( NULL );
00380         COUNT_POLICY<T>::ResetCount( m_pFirst );
00381     }
00382 
00383     /// Get first element.
00384     AkForceInline T * First()
00385     {
00386         return m_pFirst;
00387     }
00388 
00389     /// Empty condition.
00390     AkForceInline bool IsEmpty() const
00391     {
00392         return m_pFirst == NULL;
00393     }
00394 
00395     /// Remove an element.
00396     void RemoveItem( T * in_pItem, T * in_pPrevItem )
00397     {
00398         // Is it the first one ?
00399 
00400         if( in_pItem == m_pFirst )
00401         {
00402             // new first one is the next one
00403             m_pFirst = U_NEXTITEM<T>::Get( in_pItem );
00404         }
00405         else
00406         {
00407             // take it out of the used space
00408             U_NEXTITEM<T>::Get( in_pPrevItem ) = U_NEXTITEM<T>::Get( in_pItem );
00409         }
00410 
00411         LAST_POLICY<T>::RemoveItem( in_pItem, in_pPrevItem );
00412 
00413         COUNT_POLICY<T>::DecrementCount( m_pFirst );
00414     }
00415 
00416     /// Add an element.
00417     void AddItem( T * in_pItem, T * in_pNextItem, T * in_pPrevItem )
00418     {
00419         U_NEXTITEM<T>::Get( in_pItem ) = in_pNextItem;
00420 
00421         if ( in_pPrevItem == NULL )
00422             m_pFirst = in_pItem;
00423         else
00424             U_NEXTITEM<T>::Get( in_pPrevItem ) = in_pItem;
00425 
00426         LAST_POLICY<T>::AddItem( in_pItem, in_pNextItem );
00427         
00428         COUNT_POLICY<T>::IncrementCount( in_pItem );
00429     }
00430 
00431 protected:
00432     T *             m_pFirst;                   ///< top of list
00433 };
00434 
00435 #endif // _AKLISTBARE_H