40 template <
class T_KEY >
43 #define AK_HASH_SIZE_VERY_SMALL 11
44 extern const AK_SELECTANY 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 };
48 template <
class T_KEY,
class T_ITEM,
typename T_ALLOC = ArrayPoolDefault >
151 pPrevItem = this->
pItem;
172 pPrevItem = this->
pItem;
192 returnedIt.uiTable = 0;
195 while ((returnedIt.pItem ==
NULL) && (++returnedIt.uiTable <
HashSize()))
196 returnedIt.pItem =
m_table[returnedIt.uiTable];
200 returnedIt.pTable =
NULL;
201 returnedIt.uiTable = 0;
202 returnedIt.pItem =
NULL;
210 ConstIterator returnedIt;
215 returnedIt.uiTable = 0;
218 while ((returnedIt.pItem ==
NULL) && (++returnedIt.uiTable <
HashSize()))
219 returnedIt.pItem =
m_table[returnedIt.uiTable];
223 returnedIt.pTable =
NULL;
224 returnedIt.uiTable = 0;
225 returnedIt.pItem =
NULL;
233 IteratorEx returnedIt;
238 returnedIt.uiTable = 0;
240 returnedIt.pPrevItem =
NULL;
242 while ((returnedIt.pItem ==
NULL) && (++returnedIt.uiTable <
HashSize()))
243 returnedIt.pItem =
m_table[returnedIt.uiTable];
247 returnedIt.pTable =
NULL;
248 returnedIt.uiTable = 0;
249 returnedIt.pItem =
NULL;
257 ConstIteratorEx returnedIt;
262 returnedIt.uiTable = 0;
264 returnedIt.pPrevItem =
NULL;
266 while ((returnedIt.pItem ==
NULL) && (++returnedIt.uiTable <
HashSize()))
267 returnedIt.pItem =
m_table[returnedIt.uiTable];
271 returnedIt.pTable =
NULL;
272 returnedIt.uiTable = 0;
273 returnedIt.pItem =
NULL;
286 inline ConstIterator
End()
const
288 ConstIterator returnedIt;
295 IteratorEx returnedIt;
302 ConstIteratorEx returnedIt;
309 IteratorEx returnedIt;
316 returnedIt.pPrevItem =
NULL;
318 while (returnedIt.pItem !=
NULL)
320 if (returnedIt.pItem->Assoc.key == in_Key)
323 returnedIt.pPrevItem = returnedIt.pItem;
324 returnedIt.pItem = returnedIt.pItem->pNextItem;
329 returnedIt.pTable =
NULL;
330 returnedIt.uiTable = 0;
331 returnedIt.pItem =
NULL;
332 returnedIt.pPrevItem =
NULL;
338 ConstIteratorEx
FindEx(T_KEY in_Key)
const
340 ConstIteratorEx returnedIt;
347 returnedIt.pPrevItem =
NULL;
349 while (returnedIt.pItem !=
NULL)
351 if (returnedIt.pItem->Assoc.key == in_Key)
354 returnedIt.pPrevItem = returnedIt.pItem;
355 returnedIt.pItem = returnedIt.pItem->pNextItem;
360 returnedIt.pTable =
NULL;
361 returnedIt.uiTable = 0;
362 returnedIt.pItem =
NULL;
363 returnedIt.pPrevItem =
NULL;
390 while ( pItem !=
NULL )
392 Item * pNextItem = pItem->pNextItem;
393 pItem->Assoc.item.~T_ITEM();
415 T_ITEM *
Set( Item * in_pItem )
425 in_pItem->pNextItem =
m_table[uiTable];
430 return &(in_pItem->Assoc.item);
436 T_ITEM *
Set( T_KEY in_Key )
451 T_ITEM *
Set( T_KEY in_Key,
bool& out_bWasAlreadyThere )
459 out_bWasAlreadyThere =
true;
464 out_bWasAlreadyThere =
false;
478 Item * pItem =
m_table[uiTable];
479 Item * pPrevItem =
NULL;
480 while (pItem !=
NULL)
482 if (pItem->Assoc.key == in_Key)
486 pItem = pItem->pNextItem;
494 IteratorEx
Erase(
const IteratorEx& in_rIter )
496 IteratorEx returnedIt;
497 returnedIt.
pTable = in_rIter.pTable;
498 returnedIt.uiTable = in_rIter.uiTable;
499 returnedIt.pItem = in_rIter.pItem->pNextItem;
500 returnedIt.pPrevItem = in_rIter.pPrevItem;
502 while ( ( returnedIt.pItem ==
NULL ) && ( ++returnedIt.uiTable <
HashSize() ) )
504 returnedIt.pPrevItem =
NULL;
505 returnedIt.pItem = (*returnedIt.pTable)[returnedIt.uiTable];
508 RemoveItem( in_rIter.uiTable, in_rIter.pItem, in_rIter.pPrevItem );
516 in_pPrevItem->pNextItem = in_pItem->pNextItem;
518 m_table[ in_uiTable ] = in_pItem->pNextItem;
520 in_pItem->Assoc.item.~T_ITEM();
546 if (
kHashSizes[i] > in_uExpectedNumberOfEntires)
560 for (
AkUInt32 i = 0; i < uNewSize; i++)
565 Item * pItem = oldArray[i];
566 while (pItem !=
NULL)
568 Item * pNextItem = pItem->pNextItem;
571 pItem->pNextItem =
m_table[uiTable];
621 while (pItem !=
NULL)
623 if (pItem->Assoc.key == in_Key)
624 return &(pItem->Assoc.item);
626 pItem = pItem->pNextItem;
634 Item * pNewItem = (Item *)T_ALLOC::Alloc(
sizeof(Item));
635 if ( pNewItem ==
NULL )
639 pNewItem->Assoc.key = in_Key;
647 return &(pNewItem->Assoc.item);
657 template <
class T_KEY,
class T_MAPSTRUCT>
660 static const T_KEY&
Key(
const T_MAPSTRUCT* in_pItem) {
return in_pItem->key;}
661 static T_MAPSTRUCT*&
Next(T_MAPSTRUCT* in_pItem) {
return (*in_pItem).pNextItem; }
664 template <
class T_KEY,
class T_MAPSTRUCT>
667 static const T_KEY&
Key(
const T_MAPSTRUCT* in_pItem) {
return in_pItem->Key(); }
668 static T_MAPSTRUCT*&
Next(T_MAPSTRUCT* in_pItem) {
return (*in_pItem).pNextItem; }
671 template <
class T_KEY,
class T_MAPSTRUCT>
674 template <
class T_KEY,
class T_MAPSTRUCT,
typename T_ALLOC = ArrayPoolDefault,
class KEY_POLICY = AkDefaultHashListBarePolicy<T_KEY, T_MAPSTRUCT>,
class LIST_POLICY = AkDefaultHashListBarePolicy<T_KEY, T_MAPSTRUCT>>
769 pPrevItem = this->
pItem;
790 pPrevItem = this->
pItem;
810 returnedIt.uiTable = 0;
813 while ((returnedIt.pItem ==
NULL) && (++returnedIt.uiTable <
HashSize()))
814 returnedIt.pItem =
m_table[returnedIt.uiTable];
818 returnedIt.pTable =
NULL;
819 returnedIt.uiTable = 0;
820 returnedIt.pItem =
NULL;
828 ConstIterator returnedIt;
833 returnedIt.uiTable = 0;
836 while ((returnedIt.pItem ==
NULL) && (++returnedIt.uiTable <
HashSize()))
837 returnedIt.pItem =
m_table[returnedIt.uiTable];
841 returnedIt.pTable =
NULL;
842 returnedIt.uiTable = 0;
843 returnedIt.pItem =
NULL;
851 IteratorEx returnedIt;
856 returnedIt.uiTable = 0;
858 returnedIt.pPrevItem =
NULL;
860 while ( ( returnedIt.pItem ==
NULL ) && ( ++returnedIt.uiTable <
HashSize() ) )
861 returnedIt.pItem =
m_table[ returnedIt.uiTable ];
865 returnedIt.pTable =
NULL;
866 returnedIt.uiTable = 0;
867 returnedIt.pItem =
NULL;
868 returnedIt.pPrevItem =
NULL;
876 ConstIteratorEx returnedIt;
881 returnedIt.uiTable = 0;
883 returnedIt.pPrevItem =
NULL;
885 while ((returnedIt.pItem ==
NULL) && (++returnedIt.uiTable <
HashSize()))
886 returnedIt.pItem =
m_table[returnedIt.uiTable];
890 returnedIt.pTable =
NULL;
891 returnedIt.uiTable = 0;
892 returnedIt.pItem =
NULL;
893 returnedIt.pPrevItem =
NULL;
906 inline ConstIterator
End()
const
908 ConstIterator returnedIt;
915 IteratorEx returnedIt;
921 returnedIt.pItem =
m_table[returnedIt.uiTable];
922 returnedIt.pPrevItem =
NULL;
924 while (returnedIt.pItem !=
NULL)
926 if (KEY_POLICY::Key(returnedIt.pItem) == in_Key)
929 returnedIt.pPrevItem = returnedIt.pItem;
930 returnedIt.pItem = LIST_POLICY::Next(returnedIt.pItem);
935 returnedIt.pTable =
NULL;
936 returnedIt.uiTable = 0;
937 returnedIt.pItem =
NULL;
938 returnedIt.pPrevItem =
NULL;
944 ConstIteratorEx
FindEx(T_KEY in_Key)
const
946 ConstIteratorEx returnedIt;
952 returnedIt.pItem =
m_table[returnedIt.uiTable];
953 returnedIt.pPrevItem =
NULL;
955 while (returnedIt.pItem !=
NULL)
957 if (KEY_POLICY::Key(returnedIt.pItem) == in_Key)
960 returnedIt.pPrevItem = returnedIt.pItem;
961 returnedIt.pItem = returnedIt.pItem->pNextItem;
966 returnedIt.pTable =
NULL;
967 returnedIt.uiTable = 0;
968 returnedIt.pItem =
NULL;
969 returnedIt.pPrevItem =
NULL;
1035 bool Set( T_MAPSTRUCT * in_pItem,
bool& out_exists )
1047 _Set(in_pItem, uiTable);
1054 bool Set( T_MAPSTRUCT * in_pItem )
1060 _Set(in_pItem, uiTable);
1068 void _Set( T_MAPSTRUCT * in_pItem,
AkHashType in_uiTable )
1070 LIST_POLICY::Next(in_pItem) =
m_table[in_uiTable];
1071 m_table[in_uiTable] = in_pItem;
1076 T_MAPSTRUCT *
Unset(
const T_KEY &in_Key )
1078 T_MAPSTRUCT * pItem =
NULL;
1084 T_MAPSTRUCT * pPrevItem =
NULL;
1085 while (pItem !=
NULL)
1087 if (KEY_POLICY::Key(pItem) == in_Key)
1091 pItem = LIST_POLICY::Next(pItem);
1101 IteratorEx
Erase(
const IteratorEx& in_rIter )
1103 IteratorEx returnedIt;
1104 returnedIt.
pTable = in_rIter.pTable;
1105 returnedIt.uiTable = in_rIter.uiTable;
1106 returnedIt.pItem = LIST_POLICY::Next(in_rIter.pItem);
1107 returnedIt.pPrevItem = in_rIter.pPrevItem;
1109 while ((returnedIt.pItem ==
NULL) && (++returnedIt.uiTable < returnedIt.pTable->Length()))
1111 returnedIt.pPrevItem =
NULL;
1112 returnedIt.pItem = (*returnedIt.pTable)[ returnedIt.uiTable ];
1115 RemoveItem( in_rIter.uiTable, in_rIter.pItem, in_rIter.pPrevItem );
1140 if (
kHashSizes[i] > in_uExpectedNumberOfEntires)
1154 for (
AkUInt32 i = 0; i < uNewSize; i++)
1159 T_MAPSTRUCT* pItem = oldArray[i];
1160 while (pItem !=
NULL)
1162 T_MAPSTRUCT* pNextItem = LIST_POLICY::Next(pItem);
1165 LIST_POLICY::Next(pItem) =
m_table[uiTable];
1204 LIST_POLICY::Next(in_pPrevItem) = LIST_POLICY::Next(in_pItem);
1206 m_table[ in_uiTable ] = LIST_POLICY::Next(in_pItem);
1213 T_MAPSTRUCT * pItem =
m_table[in_uiTable];
1214 while (pItem !=
NULL)
1216 if (KEY_POLICY::Key(pItem) == in_Key)
1219 pItem = LIST_POLICY::Next(pItem);
1231 #endif // _AKHASHLIST_H