Table of Contents

include/AK/Tools/Common/AkHashList.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 _AKHASHLIST_H
00029 #define _AKHASHLIST_H
00030 
00031 #include <AK/Tools/Common/AkKeyDef.h>// for MapStruct
00032 #include <AK/Tools/Common/AkObject.h>
00033 #include <AK/Tools/Common/AkArray.h>
00034 
00035 // NOTE: when using this template, a hashing function of the following form must be available: 
00036 //
00037 // AkHashType AkHash( T_KEY );
00038 
00039 typedef AkUInt32 AkHashType;
00040 
00041 template < class T_KEY >
00042 AkForceInline AkHashType AkHash(T_KEY in_key) { return (AkHashType)in_key; }
00043 
00044 #define AK_HASH_SIZE_VERY_SMALL 11
00045 static const AkHashType kHashSizes[] = { 29, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741 };
00046 static const size_t kNumHashSizes = sizeof(kHashSizes) / sizeof(kHashSizes[0]);
00047 static const AkReal32 kHashTableGrowthFactor = 0.9f; 
00048 
00049 template < class T_KEY, class T_ITEM, typename T_ALLOC = ArrayPoolDefault >
00050 class AkHashList: public T_ALLOC
00051 {
00052 public:
00053     
00054     struct Item
00055     {
00056         Item * pNextItem;               // our next one
00057         MapStruct<T_KEY, T_ITEM> Assoc; // key-item association
00058     };
00059 
00060     typedef AkArray<Item*, Item*, T_ALLOC, 0 > HashTableArray;
00061 
00062     struct Iterator
00063     {
00064         typename AkHashList<T_KEY,T_ITEM,T_ALLOC>::HashTableArray* pTable;
00065         AkHashType uiTable;
00066         Item* pItem;
00067 
00068         inline Iterator& operator++()
00069         {
00070             AKASSERT( pItem );
00071             pItem = pItem->pNextItem;
00072             
00073             while ( ( pItem == NULL ) && ( ++uiTable < pTable->Length() ) )
00074                 pItem = (*pTable)[ uiTable ];
00075 
00076             return *this;
00077         }
00078 
00079         inline MapStruct<T_KEY, T_ITEM>& operator*()
00080         {
00081             AKASSERT( pItem );
00082             return pItem->Assoc;
00083         }
00084 
00085         bool operator !=( const Iterator& in_rOp ) const
00086         {
00087             return ( pItem != in_rOp.pItem );
00088         }       
00089     };
00090 
00091     // The IteratorEx iterator is intended for usage when a possible erase may occurs
00092     // when simply iterating trough a list, use the simple Iterator, it is faster and lighter.
00093     struct IteratorEx : public Iterator
00094     {
00095         Item* pPrevItem;
00096 
00097         IteratorEx& operator++()
00098         {
00099             AKASSERT( this->pItem );
00100             
00101             pPrevItem = this->pItem;
00102             this->pItem = this->pItem->pNextItem;
00103             
00104             while ((this->pItem == NULL) && (++this->uiTable < this->pTable->Length()))
00105             {
00106                 pPrevItem = NULL;
00107                 this->pItem = (*this->pTable)[ this->uiTable ];
00108             }
00109 
00110             return *this;
00111         }
00112     };
00113 
00114     Iterator Begin()
00115     {
00116         Iterator returnedIt;
00117 
00118         if (HashSize() > 0)
00119         {
00120             returnedIt.pTable = &m_table;
00121             returnedIt.uiTable = 0;
00122             returnedIt.pItem = m_table[0];
00123 
00124             while ((returnedIt.pItem == NULL) && (++returnedIt.uiTable < HashSize()))
00125                 returnedIt.pItem = m_table[returnedIt.uiTable];
00126         }
00127         else
00128         {
00129             returnedIt.pTable = NULL;
00130             returnedIt.uiTable = 0;
00131             returnedIt.pItem = NULL;
00132         }
00133 
00134         return returnedIt;
00135     }
00136 
00137     IteratorEx BeginEx()
00138     {
00139         IteratorEx returnedIt;
00140 
00141         if (HashSize() > 0)
00142         {
00143             returnedIt.pTable = &m_table;
00144             returnedIt.uiTable = 0;
00145             returnedIt.pItem = *(m_table.Begin());
00146             returnedIt.pPrevItem = NULL;
00147 
00148             while ((returnedIt.pItem == NULL) && (++returnedIt.uiTable < HashSize()))
00149                 returnedIt.pItem = m_table[returnedIt.uiTable];
00150         }
00151         else
00152         {
00153             returnedIt.pTable = NULL;
00154             returnedIt.uiTable = 0;
00155             returnedIt.pItem = NULL;
00156         }
00157 
00158         return returnedIt;
00159     }
00160 
00161     inline Iterator End()
00162     {
00163         Iterator returnedIt;
00164         returnedIt.pItem = NULL;
00165         return returnedIt;
00166     }
00167 
00168     IteratorEx FindEx( T_KEY in_Key )
00169     {
00170         IteratorEx returnedIt;
00171 
00172         if (HashSize() > 0)
00173         {
00174             returnedIt.pTable = &m_table;
00175             returnedIt.uiTable = AkHash(in_Key) % HashSize();
00176             returnedIt.pItem = m_table.Length() > 0 ? m_table[returnedIt.uiTable] : NULL;
00177             returnedIt.pPrevItem = NULL;
00178 
00179             while (returnedIt.pItem != NULL)
00180             {
00181                 if (returnedIt.pItem->Assoc.key == in_Key)
00182                     break;
00183 
00184                 returnedIt.pPrevItem = returnedIt.pItem;
00185                 returnedIt.pItem = returnedIt.pItem->pNextItem;
00186             }
00187         }
00188         else
00189         {
00190             returnedIt.pTable = NULL;
00191             returnedIt.uiTable = 0;
00192             returnedIt.pItem = NULL;
00193             returnedIt.pPrevItem = NULL;
00194         }
00195 
00196         return returnedIt;
00197     }
00198 
00199     AkHashList(): m_uiSize( 0 )
00200     {
00201     }
00202 
00203     ~AkHashList()
00204     {
00205         AKASSERT(m_uiSize == 0);
00206         m_table.Term();
00207     }
00208 
00209     void Term()
00210     {
00211         RemoveAll();
00212         m_table.Term();
00213     }
00214 
00215     void RemoveAll()
00216     {
00217         for (AkHashType i = 0; i < HashSize(); ++i)
00218         {
00219             Item * pItem = m_table[ i ];
00220             while ( pItem != NULL )
00221             {
00222                 Item * pNextItem = pItem->pNextItem;
00223                 pItem->Assoc.item.~T_ITEM();
00224                 T_ALLOC::Free( pItem );
00225                 pItem = pNextItem;
00226             }
00227             
00228             m_table[ i ] = NULL;
00229         }
00230 
00231         m_uiSize = 0;
00232     }
00233 
00234     T_ITEM * Exists( T_KEY in_Key )
00235     {
00236         if (HashSize() > 0)
00237         {
00238             AkUIntPtr uiTable = AkHash(in_Key) % HashSize();
00239             return ExistsInList(in_Key, uiTable);
00240         }
00241         return NULL;
00242     }
00243 
00244     // Set using an externally preallocated Item -- Hash list takes ownership of the Item.
00245     T_ITEM * Set( Item * in_pItem )
00246     {
00247         if (CheckSize())
00248         {
00249             AkHashType uiTable = AkHash(in_pItem->Assoc.key) % HashSize();
00250 
00251             AKASSERT(!ExistsInList(in_pItem->Assoc.key, uiTable)); // Item must not exist in list !
00252 
00253             // Add new entry
00254 
00255             in_pItem->pNextItem = m_table[uiTable];
00256             m_table[uiTable] = in_pItem;
00257 
00258             ++m_uiSize;
00259 
00260             return &(in_pItem->Assoc.item);
00261         }
00262 
00263         return NULL;
00264     }
00265 
00266     T_ITEM * Set( T_KEY in_Key )
00267     {
00268         if ( CheckSize() )
00269         {
00270             AkUIntPtr uiTable = AkHash(in_Key) % HashSize();
00271             T_ITEM * pItem = ExistsInList(in_Key, uiTable);
00272             if (pItem)
00273                 return pItem;
00274 
00275             return CreateEntry(in_Key, uiTable);
00276         }
00277 
00278         return NULL;
00279     }
00280 
00281     T_ITEM * Set( T_KEY in_Key, bool& out_bWasAlreadyThere )
00282     {
00283         if (CheckSize())
00284         {
00285             AkHashType uiTable = AkHash(in_Key) % HashSize();
00286             T_ITEM * pItem = ExistsInList(in_Key, uiTable);
00287             if (pItem)
00288             {
00289                 out_bWasAlreadyThere = true;
00290                 return pItem;
00291             }
00292             else
00293             {
00294                 out_bWasAlreadyThere = false;
00295             }
00296 
00297             return CreateEntry(in_Key, uiTable);
00298         }
00299 
00300         return NULL;
00301     }
00302 
00303     void Unset( T_KEY in_Key )
00304     {
00305         if (HashSize() > 0)
00306         {
00307             AkHashType uiTable = AkHash(in_Key) % HashSize();
00308             Item * pItem = m_table[uiTable];
00309             Item * pPrevItem = NULL;
00310             while (pItem != NULL)
00311             {
00312                 if (pItem->Assoc.key == in_Key)
00313                     break;
00314 
00315                 pPrevItem = pItem;
00316                 pItem = pItem->pNextItem;
00317             }
00318 
00319             if (pItem)
00320                 RemoveItem(uiTable, pItem, pPrevItem);
00321         }
00322     }
00323 
00324     IteratorEx Erase( const IteratorEx& in_rIter )
00325     {
00326         IteratorEx returnedIt;
00327         returnedIt.pTable = in_rIter.pTable;
00328         returnedIt.uiTable = in_rIter.uiTable;
00329         returnedIt.pItem = in_rIter.pItem->pNextItem;
00330         returnedIt.pPrevItem = in_rIter.pPrevItem;
00331         
00332         while ( ( returnedIt.pItem == NULL ) && ( ++returnedIt.uiTable < HashSize() ) )
00333         {
00334             returnedIt.pPrevItem = NULL;
00335             returnedIt.pItem = (*returnedIt.pTable)[returnedIt.uiTable];
00336         }
00337         
00338         RemoveItem( in_rIter.uiTable, in_rIter.pItem, in_rIter.pPrevItem );
00339 
00340         return returnedIt;
00341     }
00342 
00343     void RemoveItem( AkHashType in_uiTable, Item* in_pItem, Item* in_pPrevItem )
00344     {
00345         if( in_pPrevItem ) 
00346             in_pPrevItem->pNextItem = in_pItem->pNextItem;
00347         else
00348             m_table[ in_uiTable ] = in_pItem->pNextItem;
00349 
00350         in_pItem->Assoc.item.~T_ITEM();
00351         T_ALLOC::Free(in_pItem);
00352 
00353         --m_uiSize;
00354     }
00355 
00356     AkUInt32 Length() const
00357     {
00358         return m_uiSize;
00359     }
00360 
00361     AKRESULT Reserve(AkUInt32 in_uNumberOfEntires)
00362     {
00363         if ((HashSize() == 0) || (AkReal32)in_uNumberOfEntires / (AkReal32)HashSize() > kHashTableGrowthFactor)
00364             return Resize((AkUInt32)((AkReal32)in_uNumberOfEntires / kHashTableGrowthFactor));
00365 
00366         return AK_Success;
00367     }
00368 
00369     AKRESULT Resize(AkUInt32 in_uExpectedNumberOfEntires)
00370     {
00371         AKRESULT res = AK_Fail;
00372 
00373         AkUInt32 uNewSize = 0;
00374         for (AkUInt32 i = 0; i < kNumHashSizes; ++i)
00375         {
00376             if (kHashSizes[i] > in_uExpectedNumberOfEntires)
00377             {
00378                 uNewSize = kHashSizes[i];
00379                 break;
00380             }
00381         }
00382 
00383         if (uNewSize > 0)
00384         {
00385             HashTableArray oldArray;
00386             oldArray.Transfer(m_table);
00387 
00388             if ( m_table.GrowArray(uNewSize) )
00389             {
00390                 for (AkUInt32 i = 0; i < uNewSize; i++)
00391                     m_table.AddLast(NULL);
00392 
00393                 for (AkUInt32 i = 0; i < oldArray.Length(); i++)
00394                 {
00395                     Item * pItem = oldArray[i];
00396                     while (pItem != NULL)
00397                     {
00398                         Item * pNextItem = pItem->pNextItem;
00399                         {
00400                             AkHashType uiTable = AkHash(pItem->Assoc.key) % HashSize();
00401                             pItem->pNextItem = m_table[uiTable];
00402                             m_table[uiTable] = pItem;
00403                         }
00404                         pItem = pNextItem;
00405                     }
00406                 }
00407 
00408                 oldArray.Term();
00409 
00410                 res = AK_Success;
00411             }
00412             else
00413             {
00414                 //Backpedal..
00415                 m_table.Transfer(oldArray);
00416             }
00417         }
00418 
00419         return res;
00420     }
00421 
00422     inline AkUInt32 HashSize() const
00423     {
00424         return m_table.Length();
00425     }
00426 
00427     inline bool CheckSize() 
00428     {
00429         if ( HashSize() == 0 || (AkReal32)m_uiSize / (AkReal32)HashSize() > kHashTableGrowthFactor )
00430             Resize(HashSize());
00431 
00432         return (HashSize() > 0);
00433     }
00434 
00435 protected:
00436     T_ITEM * ExistsInList( T_KEY in_Key, AkUIntPtr in_uiTable )
00437     {
00438         AKASSERT(HashSize() > 0);
00439         
00440         Item * pItem = m_table[(AkUInt32)in_uiTable];
00441         while (pItem != NULL)
00442         {
00443             if (pItem->Assoc.key == in_Key)
00444                 return &(pItem->Assoc.item); // found
00445 
00446             pItem = pItem->pNextItem;
00447         }
00448 
00449         return NULL; // not found
00450     }
00451 
00452     T_ITEM * CreateEntry( T_KEY in_Key, AkUIntPtr in_uiTable )
00453     {
00454         Item * pNewItem = (Item *)T_ALLOC::Alloc(sizeof(Item));
00455         if ( pNewItem == NULL )
00456             return NULL;
00457 
00458         pNewItem->pNextItem = m_table[ (AkUInt32)in_uiTable ];
00459         pNewItem->Assoc.key = in_Key;
00460 
00461         AkPlacementNew( &(pNewItem->Assoc.item) ) T_ITEM; 
00462 
00463         m_table[(AkUInt32)in_uiTable] = pNewItem;
00464 
00465         ++m_uiSize;
00466 
00467         return &(pNewItem->Assoc.item);
00468     }
00469 
00470     HashTableArray m_table;
00471     AkUInt32 m_uiSize;
00472 };
00473 
00474 // this one lets you define the structure
00475 // only requirement is that T_MAPSTRUCT must have members pNextItem and key.
00476 // client is responsible for allocation/deallocation of T_MAPSTRUCTS.
00477 template <class T_KEY, class T_MAPSTRUCT>
00478 struct AkDefaultHashListBarePolicy
00479 {
00480     static const T_KEY& Key(const T_MAPSTRUCT* in_pItem) {return in_pItem->key;}
00481 };
00482 
00483 template < class T_KEY, class T_MAPSTRUCT, typename T_ALLOC = ArrayPoolDefault, class KEY_POLICY = AkDefaultHashListBarePolicy<T_KEY, T_MAPSTRUCT> > 
00484 class AkHashListBare
00485 {
00486     typedef AkArray<T_MAPSTRUCT*, T_MAPSTRUCT*, T_ALLOC, 0 > HashTableArray;
00487 public:
00488     struct Iterator
00489     {
00490         typename AkHashListBare<T_KEY,T_MAPSTRUCT,T_ALLOC,KEY_POLICY>::HashTableArray* pTable;
00491         AkHashType uiTable;
00492         T_MAPSTRUCT* pItem;
00493 
00494         inline Iterator& operator++()
00495         {
00496             AKASSERT( pItem );
00497             pItem = pItem->pNextItem;
00498             
00499             while ((pItem == NULL) && (++uiTable < pTable->Length()))
00500                 pItem = (*pTable)[ uiTable ];
00501 
00502             return *this;
00503         }
00504 
00505         inline T_MAPSTRUCT * operator*()
00506         {
00507             AKASSERT( pItem );
00508             return pItem;
00509         }
00510 
00511         bool operator !=( const Iterator& in_rOp ) const
00512         {
00513             return ( pItem != in_rOp.pItem );
00514         }       
00515     };
00516 
00517     // The IteratorEx iterator is intended for usage when a possible erase may occurs
00518     // when simply iterating trough a list, use the simple Iterator, it is faster and lighter.
00519     struct IteratorEx : public Iterator
00520     {
00521         T_MAPSTRUCT* pPrevItem;
00522 
00523         IteratorEx& operator++()
00524         {
00525             AKASSERT( this->pItem );
00526             
00527             pPrevItem = this->pItem;
00528             this->pItem = this->pItem->pNextItem;
00529             
00530             while ( ( this->pItem == NULL ) && ( ++this->uiTable < this->pTable->Length() ) )
00531             {
00532                 pPrevItem = NULL;
00533                 this->pItem = (*this->pTable)[ this->uiTable ];
00534             }
00535 
00536             return *this;
00537         }
00538     };
00539 
00540     Iterator Begin()
00541     {
00542         Iterator returnedIt;
00543 
00544         if (HashSize() > 0)
00545         {
00546             returnedIt.pTable = &m_table;
00547             returnedIt.uiTable = 0;
00548             returnedIt.pItem = m_table[0];
00549 
00550             while ((returnedIt.pItem == NULL) && (++returnedIt.uiTable < HashSize()))
00551                 returnedIt.pItem = m_table[returnedIt.uiTable];
00552         }
00553         else
00554         {
00555             returnedIt.pTable = NULL;
00556             returnedIt.uiTable = 0;
00557             returnedIt.pItem = NULL;
00558         }
00559 
00560         return returnedIt;
00561     }
00562 
00563     IteratorEx BeginEx()
00564     {
00565         IteratorEx returnedIt;
00566 
00567         if (HashSize() > 0)
00568         {
00569             returnedIt.pTable = &m_table;
00570             returnedIt.uiTable = 0;
00571             returnedIt.pItem = m_table[0];
00572             returnedIt.pPrevItem = NULL;
00573         
00574             while ( ( returnedIt.pItem == NULL ) && ( ++returnedIt.uiTable < HashSize() ) )
00575                 returnedIt.pItem = m_table[ returnedIt.uiTable ];
00576         }
00577         else
00578         {
00579             returnedIt.pTable = NULL;
00580             returnedIt.uiTable = 0;
00581             returnedIt.pItem = NULL;
00582         }
00583 
00584         return returnedIt;
00585     }
00586 
00587     inline Iterator End()
00588     {
00589         Iterator returnedIt;
00590         returnedIt.pItem = NULL;
00591         return returnedIt;
00592     }
00593 
00594     IteratorEx FindEx( T_KEY in_Key )
00595     {
00596         IteratorEx returnedIt;
00597 
00598         if (HashSize() > 0)
00599         {
00600             returnedIt.pTable = &m_table;
00601             returnedIt.uiTable = AkHash(in_Key) % HashSize();
00602             returnedIt.pItem = m_table[returnedIt.uiTable];
00603             returnedIt.pPrevItem = NULL;
00604 
00605             while (returnedIt.pItem != NULL)
00606             {
00607                 if (KEY_POLICY::Key(returnedIt.pItem) == in_Key)
00608                     break;
00609 
00610                 returnedIt.pPrevItem = returnedIt.pItem;
00611                 returnedIt.pItem = returnedIt.pItem->pNextItem;
00612             }
00613         }
00614         else
00615         {
00616             returnedIt.pTable = NULL;
00617             returnedIt.uiTable = 0;
00618             returnedIt.pItem = NULL;
00619             returnedIt.pPrevItem = NULL;
00620         }
00621 
00622         return returnedIt;
00623     }
00624 
00625     AkHashListBare()
00626         : m_uiSize( 0 )
00627     {
00628     }
00629 
00630     ~AkHashListBare()
00631     {
00632     }
00633 
00634     //If you set 0 as the starting size, you *must* check all returns of Set() calls.
00635     //If you initialize with anything else, you can ignore return codes of Set(), they will always succeed.
00636     bool Init(AkUInt32 in_iStartingSize)
00637     {
00638         m_uiSize = 0;
00639 
00640         if(!m_table.Resize(in_iStartingSize))
00641             return false;
00642 
00643         for ( AkHashType i = 0; i < HashSize(); ++i )
00644             m_table[ i ] = NULL;
00645         
00646         return true;
00647     }
00648 
00649     void Term()
00650     {
00651         AKASSERT( m_uiSize == 0 );
00652         m_table.Term();
00653     }
00654 /*
00655     void RemoveAll()
00656     {
00657         for ( AkHashType i = 0; i < HashSize(); ++i )
00658         {
00659             T_MAPSTRUCT * pItem = m_table[ i ];
00660             while ( pItem != NULL )
00661             {
00662                 T_MAPSTRUCT * pNextItem = pItem->pNextItem;
00663                 pItem->~T_MAPSTRUCT();
00664                 T_ALLOD::Free( pItem );
00665                 pItem = pNextItem;
00666             }
00667             
00668             m_table[ i ] = NULL;
00669         }
00670 
00671         m_uiSize = 0;
00672     }
00673 */
00674     T_MAPSTRUCT * Exists( T_KEY in_Key ) const
00675     {
00676         if (HashSize() > 0)
00677         {
00678             AkHashType uiTable = AkHash(in_Key) % HashSize();
00679             return ExistsInList(in_Key, uiTable);
00680         }
00681         return NULL;
00682     }
00683 
00684     // Set using an externally preallocated T_MAPSTRUCT -- Hash list takes ownership of the T_MAPSTRUCT.
00685     bool Set( T_MAPSTRUCT * in_pItem )
00686     {
00687         if (CheckSize())
00688         {
00689             AkHashType uiTable = AkHash(KEY_POLICY::Key(in_pItem)) % HashSize();
00690             AKASSERT(!ExistsInList(KEY_POLICY::Key(in_pItem), uiTable)); // T_MAPSTRUCT must not exist in list !
00691 
00692             // Add new entry
00693 
00694             in_pItem->pNextItem = m_table[uiTable];
00695             m_table[uiTable] = in_pItem;
00696 
00697             ++m_uiSize;
00698             return true;
00699         }
00700         //This can only happen if the initial size of the map was 0.
00701         return false;
00702     }
00703 
00704     T_MAPSTRUCT * Unset( const T_KEY &in_Key )
00705     {
00706         T_MAPSTRUCT * pItem = NULL;
00707 
00708         if (HashSize() > 0)
00709         {
00710             AkHashType uiTable = AkHash(in_Key) % HashSize();
00711             pItem = m_table[uiTable];
00712             T_MAPSTRUCT * pPrevItem = NULL;
00713             while (pItem != NULL)
00714             {
00715                 if (KEY_POLICY::Key(pItem) == in_Key)
00716                     break;
00717 
00718                 pPrevItem = pItem;
00719                 pItem = pItem->pNextItem;
00720             }
00721 
00722             if (pItem)
00723                 RemoveItem(uiTable, pItem, pPrevItem);
00724         }
00725 
00726         return pItem;
00727     }
00728 
00729     IteratorEx Erase( const IteratorEx& in_rIter )
00730     {
00731         IteratorEx returnedIt;
00732         returnedIt.pTable = in_rIter.pTable;
00733         returnedIt.uiTable = in_rIter.uiTable;
00734         returnedIt.pItem = in_rIter.pItem->pNextItem;
00735         returnedIt.pPrevItem = in_rIter.pPrevItem;
00736         
00737         while ((returnedIt.pItem == NULL) && (++returnedIt.uiTable < returnedIt.pTable->Length()))
00738         {
00739             returnedIt.pPrevItem = NULL;
00740             returnedIt.pItem = (*returnedIt.pTable)[ returnedIt.uiTable ];
00741         }
00742         
00743         RemoveItem( in_rIter.uiTable, in_rIter.pItem, in_rIter.pPrevItem );
00744 
00745         return returnedIt;
00746     }
00747 
00748     AkUInt32 Length() const
00749     {
00750         return m_uiSize;
00751     }
00752 
00753     AKRESULT Reserve(AkUInt32 in_uNumberOfEntires)
00754     {
00755         if ((HashSize() == 0) || (AkReal32)in_uNumberOfEntires / (AkReal32)HashSize() > kHashTableGrowthFactor)
00756             return Resize((AkUInt32)((AkReal32)in_uNumberOfEntires / kHashTableGrowthFactor));
00757 
00758         return AK_Success;
00759     }
00760 
00761     AKRESULT Resize(AkUInt32 in_uExpectedNumberOfEntires)
00762     {
00763         AKRESULT res = AK_Fail;
00764 
00765         AkHashType uNewSize = 0;
00766         for (AkUInt32 i = 0; i < kNumHashSizes; ++i)
00767         {
00768             if (kHashSizes[i] > in_uExpectedNumberOfEntires)
00769             {
00770                 uNewSize = kHashSizes[i];
00771                 break;
00772             }
00773         }
00774 
00775         if (uNewSize > 0)
00776         {
00777             HashTableArray oldArray;
00778             oldArray.Transfer(m_table);
00779 
00780             if (m_table.GrowArray(uNewSize))
00781             {
00782                 for (AkUInt32 i = 0; i < uNewSize; i++)
00783                     m_table.AddLast(NULL);
00784 
00785                 for (AkUInt32 i = 0; i < oldArray.Length(); i++)
00786                 {
00787                     T_MAPSTRUCT* pItem = oldArray[i];
00788                     while (pItem != NULL)
00789                     {
00790                         T_MAPSTRUCT* pNextItem = pItem->pNextItem;
00791                         {
00792                             AkHashType uiTable = AkHash(KEY_POLICY::Key(pItem)) % uNewSize;
00793                             pItem->pNextItem = m_table[uiTable];
00794                             m_table[uiTable] = pItem;
00795                         }
00796                         pItem = pNextItem;
00797                     }
00798                 }
00799 
00800                 oldArray.Term();
00801 
00802                 res = AK_Success;
00803             }
00804             else
00805             {
00806                 //Backpedal..
00807                 m_table.Transfer(oldArray);
00808             }
00809         }
00810 
00811         return res;
00812     }
00813 
00814     inline AkHashType HashSize() const
00815     {
00816         return m_table.Length();
00817     }
00818 
00819 
00820     inline bool CheckSize()
00821     {
00822         if ( (HashSize() == 0) || (AkReal32)m_uiSize / (AkReal32)HashSize() > kHashTableGrowthFactor )
00823             Resize(HashSize());
00824 
00825         return (HashSize() > 0);
00826     }
00827 
00828 protected:
00829     void RemoveItem( AkHashType in_uiTable, T_MAPSTRUCT* in_pItem, T_MAPSTRUCT* in_pPrevItem )
00830     {
00831         if( in_pPrevItem ) 
00832             in_pPrevItem->pNextItem = in_pItem->pNextItem;
00833         else
00834             m_table[ in_uiTable ] = in_pItem->pNextItem;
00835 
00836         --m_uiSize;
00837     }
00838 
00839     T_MAPSTRUCT * ExistsInList( T_KEY in_Key, AkHashType in_uiTable ) const
00840     {
00841         T_MAPSTRUCT * pItem = m_table[in_uiTable];
00842         while (pItem != NULL)
00843         {
00844             if (KEY_POLICY::Key(pItem) == in_Key)
00845                 return pItem; // found
00846             
00847             pItem = pItem->pNextItem;
00848         }
00849 
00850         return NULL; // not found
00851     }
00852 
00853     HashTableArray m_table;
00854 
00855     AkUInt32 m_uiSize;
00856 };
00857 
00858 
00859 #endif // _AKHASHLIST_H