17 #ifndef INC_KY_Kernel_Hash_H
18 #define INC_KY_Kernel_Hash_H
61 UPInt operator()(
const C& data)
const
62 {
return (UPInt) data; }
74 static KY_INLINE UPInt SDBM_Hash(
const void* data_in, UPInt size, UPInt seed = 5381)
76 const UByte* data = (
const UByte*) data_in;
81 h = (h << 16) + (h << 6) - h + (UPInt)data[size];
86 UPInt operator()(
const C& data)
const
88 unsigned char* p = (
unsigned char*) &data;
91 return SDBM_Hash(p, size);
101 template<
class C,
class HashF>
110 : NextInChain(-2) { }
111 HashsetEntry(
const HashsetEntry& e)
112 : NextInChain(e.NextInChain), Value(e.Value) { }
113 HashsetEntry(
const C& key, SPInt next)
114 : NextInChain(next), Value(key) { }
116 bool IsEmpty()
const {
return NextInChain == -2; }
117 bool IsEndOfChain()
const {
return NextInChain == -1; }
121 UPInt GetCachedHash(UPInt maskValue)
const {
return HashF()(Value) & maskValue; }
122 void SetCachedHash(UPInt) {}
131 void Free() { Clear(); }
136 template<
class C,
class HashF>
137 class HashsetCachedEntry
146 : NextInChain(-2) { }
147 HashsetCachedEntry(
const HashsetCachedEntry& e)
148 : NextInChain(e.NextInChain), HashValue(e.HashValue), Value(e.Value) { }
149 HashsetCachedEntry(
const C& key, SPInt next)
150 : NextInChain(next), Value(key) { }
152 bool IsEmpty()
const {
return NextInChain == -2; }
153 bool IsEndOfChain()
const {
return NextInChain == -1; }
157 UPInt GetCachedHash(UPInt maskValue)
const { KY_UNUSED(maskValue);
return HashValue; }
158 void SetCachedHash(UPInt hashValue) { HashValue = hashValue; }
167 void Free() { Clear(); }
178 template<
class C,
class HashF = FixedSizeHash<C>,
179 class AltHashF = HashF,
180 class Allocator = AllocatorGH<C>,
181 class Entry = HashsetCachedEntry<C, HashF> >
184 enum { HashMinSize = 8 };
187 KY_MEMORY_REDEFINE_NEW(HashSetBase, Allocator::StatId)
189 typedef HashSetBase<C, HashF, AltHashF, Allocator, Entry> SelfType;
191 HashSetBase() : pTable(NULL) { }
192 HashSetBase(
int sizeHint) : pTable(NULL) { SetCapacity(
this, sizeHint); }
193 explicit HashSetBase(
void* pmemAddr) : pTable(NULL){ KY_UNUSED(pmemAddr); }
194 HashSetBase(
void* pmemAddr,
int sizeHint) : pTable(NULL) { SetCapacity(pmemAddr, sizeHint); }
195 HashSetBase(
const SelfType& src) : pTable(NULL) { Assign(
this, src); }
201 for (UPInt i = 0, n = pTable->SizeMask; i <= n; i++)
208 Allocator::Free(pTable);
214 void Assign(
void* pmemAddr,
const SelfType& src)
217 if (src.IsEmpty() ==
false)
219 SetCapacity(pmemAddr, src.GetSize());
221 for (ConstIterator it = src.Begin(); it != src.End(); ++it)
235 for (UPInt i = 0, n = pTable->SizeMask; i <= n; i++)
242 Allocator::Free(pTable);
250 return pTable == NULL || pTable->EntryCount == 0;
258 void Set(
void* pmemAddr,
const CRef& key)
260 UPInt hashValue = HashF()(key);
261 SPInt index = (SPInt)-1;
264 index = findIndexCore(key, hashValue & pTable->SizeMask);
268 E(index).Value = key;
273 add(pmemAddr, key, hashValue);
278 inline void Add(
void* pmemAddr,
const CRef& key)
280 UPInt hashValue = HashF()(key);
281 add(pmemAddr, key, hashValue);
286 void RemoveAlt(
const K& key)
291 UPInt hashValue = AltHashF()(key);
292 SPInt index = hashValue & pTable->SizeMask;
294 Entry* e = &E(index);
297 if (e->IsEmpty() || (e->GetCachedHash(pTable->SizeMask) != (UPInt)index))
301 SPInt naturalIndex = index;
302 SPInt prevIndex = -1;
304 while ((e->GetCachedHash(pTable->SizeMask) != (UPInt)naturalIndex) || !(e->Value == key))
308 index = e->NextInChain;
315 if (naturalIndex == index)
318 if (!e->IsEndOfChain())
320 Entry* enext = &E(e->NextInChain);
322 new (e) Entry(*enext);
330 E(prevIndex).NextInChain = e->NextInChain;
335 pTable->EntryCount --;
341 void Remove(
const CRef& key)
352 SPInt index = findIndex(key);
354 return &E(index).Value;
359 const C* Get(
const K& key)
const
361 SPInt index = findIndex(key);
363 return &E(index).Value;
369 const C* GetAlt(
const K& key)
const
371 SPInt index = findIndexAlt(key);
373 return &E(index).Value;
378 C* GetAlt(
const K& key)
380 SPInt index = findIndexAlt(key);
382 return &E(index).Value;
387 bool GetAlt(
const K& key, C* pval)
const
389 SPInt index = findIndexAlt(key);
393 *pval = E(index).Value;
400 UPInt GetSize()
const
402 return pTable == NULL ? 0 : (UPInt)pTable->EntryCount;
408 void CheckExpand(
void* pmemAddr)
413 setRawCapacity(pmemAddr, HashMinSize);
415 else if (pTable->EntryCount * 5 > (pTable->SizeMask + 1) * 4)
418 setRawCapacity(pmemAddr, (pTable->SizeMask + 1) * 2);
423 void Resize(
void* pmemAddr, UPInt n)
431 SetCapacity(pmemAddr, n);
437 void SetCapacity(
void* pmemAddr, UPInt newSize)
439 UPInt newRawSize = (newSize * 5) / 4;
440 if (newRawSize <= GetSize())
442 setRawCapacity(pmemAddr, newRawSize);
447 #if (KY_CC_MSVC < 1300)
448 # pragma warning(disable : 4284)
457 KY_ASSERT(Index >= 0 && Index <= (SPInt)pHash->pTable->SizeMask);
458 return pHash->E(Index).Value;
461 const C* operator -> ()
const
463 KY_ASSERT(Index >= 0 && Index <= (SPInt)pHash->pTable->SizeMask);
464 return &pHash->E(Index).Value;
470 if (Index <= (SPInt)pHash->pTable->SizeMask)
473 while ((UPInt)Index <= pHash->pTable->SizeMask &&
474 pHash->E(Index).IsEmpty())
481 bool operator == (
const ConstIterator& it)
const
483 if (IsEnd() && it.IsEnd())
489 return (pHash == it.pHash) && (Index == it.Index);
493 bool operator != (
const ConstIterator& it)
const
495 return ! (*
this == it);
501 return (pHash == NULL) ||
502 (pHash->pTable == NULL) ||
503 (Index > (SPInt)pHash->pTable->SizeMask);
507 : pHash(NULL), Index(0)
513 ConstIterator(
const SelfType* h, SPInt index)
514 : pHash(h), Index(index)
517 const SelfType* GetContainer()
const
521 SPInt GetIndex()
const
527 friend class HashSetBase<C, HashF, AltHashF, Allocator, Entry>;
529 const SelfType* pHash;
533 friend struct ConstIterator;
537 struct Iterator :
public ConstIterator
542 KY_ASSERT(ConstIterator::Index >= 0 && ConstIterator::Index <= (SPInt)ConstIterator::pHash->pTable->SizeMask);
543 return const_cast<SelfType*
>(ConstIterator::pHash)->E(ConstIterator::Index).Value;
546 C* operator->()
const
552 : ConstIterator(NULL, 0)
558 RemoveAlt(
operator*());
562 void RemoveAlt(
const K& key)
564 SelfType* phash =
const_cast<SelfType*
>(ConstIterator::pHash);
568 UPInt hashValue = AltHashF()(key);
569 SPInt index = hashValue & phash->pTable->SizeMask;
571 Entry* e = &phash->E(index);
574 if (e->IsEmpty() || (e->GetCachedHash(phash->pTable->SizeMask) != (UPInt)index))
578 SPInt naturalIndex = index;
579 SPInt prevIndex = -1;
581 while ((e->GetCachedHash(phash->pTable->SizeMask) != (UPInt)naturalIndex) || !(e->Value == key))
585 index = e->NextInChain;
588 e = &phash->E(index);
591 if (index == (SPInt)ConstIterator::Index)
594 if (naturalIndex == index)
597 if (!e->IsEndOfChain())
599 Entry* enext = &phash->E(e->NextInChain);
601 new (e) Entry(*enext);
604 --ConstIterator::Index;
610 phash->E(prevIndex).NextInChain = e->NextInChain;
615 phash->pTable->EntryCount --;
622 friend class HashSetBase<C, HashF, AltHashF, Allocator, Entry>;
624 Iterator(SelfType* h, SPInt i0)
625 : ConstIterator(h, i0)
629 friend struct Iterator;
634 return Iterator(NULL, 0);
638 while (i0 <= pTable->SizeMask && E(i0).IsEmpty())
642 return Iterator(
this, i0);
644 Iterator End() {
return Iterator(NULL, 0); }
646 ConstIterator Begin()
const {
return const_cast<SelfType*
>(
this)->Begin(); }
647 ConstIterator End()
const {
return const_cast<SelfType*
>(
this)->End(); }
650 Iterator Find(
const K& key)
652 SPInt index = findIndex(key);
654 return Iterator(
this, index);
655 return Iterator(NULL, 0);
659 Iterator FindAlt(
const K& key)
661 SPInt index = findIndexAlt(key);
663 return Iterator(
this, index);
664 return Iterator(NULL, 0);
668 ConstIterator Find(
const K& key)
const {
return const_cast<SelfType*
>(
this)->Find(key); }
671 ConstIterator FindAlt(
const K& key)
const {
return const_cast<SelfType*
>(
this)->FindAlt(key); }
676 SPInt findIndex(
const K& key)
const
680 UPInt hashValue = HashF()(key) & pTable->SizeMask;
681 return findIndexCore(key, hashValue);
685 SPInt findIndexAlt(
const K& key)
const
689 UPInt hashValue = AltHashF()(key) & pTable->SizeMask;
690 return findIndexCore(key, hashValue);
695 SPInt findIndexCore(
const K& key, UPInt hashValue)
const
698 KY_ASSERT(pTable != 0);
700 KY_ASSERT((hashValue & ~pTable->SizeMask) == 0);
702 UPInt index = hashValue;
703 const Entry* e = &E(index);
706 if (e->IsEmpty() || (e->GetCachedHash(pTable->SizeMask) != index))
711 KY_ASSERT(e->GetCachedHash(pTable->SizeMask) == hashValue);
713 if (e->GetCachedHash(pTable->SizeMask) == hashValue && e->Value == key)
720 KY_ASSERT(!(e->Value == key));
723 index = e->NextInChain;
724 if (index == (UPInt)-1)
728 KY_ASSERT(!e->IsEmpty());
736 void add(
void* pmemAddr,
const CRef& key, UPInt hashValue)
738 CheckExpand(pmemAddr);
739 hashValue &= pTable->SizeMask;
741 pTable->EntryCount++;
743 SPInt index = hashValue;
744 Entry* naturalEntry = &(E(index));
746 if (naturalEntry->IsEmpty())
749 new (naturalEntry) Entry(key, -1);
754 SPInt blankIndex = index;
756 blankIndex = (blankIndex + 1) & pTable->SizeMask;
757 }
while(!E(blankIndex).IsEmpty());
759 Entry* blankEntry = &E(blankIndex);
761 if (naturalEntry->GetCachedHash(pTable->SizeMask) == (UPInt)index)
766 new (blankEntry) Entry(*naturalEntry);
769 naturalEntry->Value = key;
770 naturalEntry->NextInChain = blankIndex;
779 SPInt collidedIndex = naturalEntry->GetCachedHash(pTable->SizeMask);
780 KY_ASSERT(collidedIndex >= 0 && collidedIndex <= (SPInt)pTable->SizeMask);
783 Entry* e = &E(collidedIndex);
784 if (e->NextInChain == index)
787 new (blankEntry) Entry(*naturalEntry);
788 e->NextInChain = blankIndex;
791 collidedIndex = e->NextInChain;
792 KY_ASSERT(collidedIndex >= 0 && collidedIndex <= (SPInt)pTable->SizeMask);
796 naturalEntry->Value = key;
797 naturalEntry->NextInChain = -1;
802 naturalEntry->SetCachedHash(hashValue);
806 Entry& E(UPInt index)
809 KY_ASSERT(index <= pTable->SizeMask);
810 return *(((Entry*) (pTable + 1)) + index);
812 const Entry& E(UPInt index)
const
814 KY_ASSERT(index <= pTable->SizeMask);
815 return *(((Entry*) (pTable + 1)) + index);
823 void setRawCapacity(
void* pheapAddr, UPInt newSize)
835 if (newSize < HashMinSize)
836 newSize = HashMinSize;
840 int bits = Alg::UpperBit(newSize-1) + 1;
841 KY_ASSERT((UPInt(1) << bits) >= newSize);
842 newSize = UPInt(1) << bits;
846 newHash.pTable = (TableType*)
849 sizeof(TableType) +
sizeof(Entry) * newSize,
852 KY_ASSERT(newHash.pTable);
854 newHash.pTable->EntryCount = 0;
855 newHash.pTable->SizeMask = newSize - 1;
859 for (i = 0; i < newSize; i++)
860 newHash.E(i).NextInChain = -2;
865 for (i = 0, n = pTable->SizeMask; i <= n; i++)
868 if (e->IsEmpty() ==
false)
871 newHash.Add(pheapAddr, e->Value);
878 Allocator::Free(pTable);
882 pTable = newHash.pTable;
883 newHash.pTable = NULL;
899 template<
class C,
class HashF = FixedSizeHash<C>,
900 class AltHashF = HashF,
901 class Allocator = AllocatorGH<C>,
902 class Entry = HashsetCachedEntry<C, HashF> >
903 class HashSet :
public HashSetBase<C, HashF, AltHashF, Allocator, Entry>
906 typedef HashSetBase<C, HashF, AltHashF, Allocator, Entry> BaseType;
907 typedef HashSet<C, HashF, AltHashF, Allocator, Entry> SelfType;
910 HashSet(
int sizeHint) : BaseType(sizeHint) { }
911 explicit HashSet(
void* pheap) : BaseType(pheap) { }
912 HashSet(
void* pheap,
int sizeHint) : BaseType(pheap, sizeHint) { }
913 HashSet(
const SelfType& src) : BaseType(src) { }
916 void operator = (
const SelfType& src) { BaseType::Assign(
this, src); }
922 void Set(
const CRef& key)
924 BaseType::Set(
this, key);
928 inline void Add(
const CRef& key)
930 BaseType::Add(
this, key);
937 BaseType::CheckExpand(
this);
943 BaseType::SetCapacity(
this, n);
949 void SetCapacity(UPInt newSize)
951 BaseType::SetCapacity(
this, newSize);
957 template<
class C,
class HashF = FixedSizeHash<C>,
958 class AltHashF = HashF,
959 int SID = Stat_Default_Mem,
960 class Entry = HashsetCachedEntry<C, HashF> >
961 class HashSetLH :
public HashSet<C, HashF, AltHashF, AllocatorLH<C, SID>, Entry>
964 typedef HashSetLH<C, HashF, AltHashF, SID, Entry> SelfType;
965 typedef HashSet<C, HashF, AltHashF, AllocatorLH<C, SID>, Entry > BaseType;
969 HashSetLH(
int sizeHint) : BaseType(sizeHint) { }
970 HashSetLH(
const SelfType& src) : BaseType(src) { }
973 void operator = (
const SelfType& src)
975 BaseType::operator = (src);
979 template<
class C,
class HashF = FixedSizeHash<C>,
980 class AltHashF = HashF,
981 int SID = Stat_Default_Mem,
982 class Entry = HashsetCachedEntry<C, HashF> >
983 class HashSetDH :
public HashSetBase<C, HashF, AltHashF, AllocatorDH<C, SID>, Entry>
987 typedef HashSetDH<C, HashF, AltHashF, SID, Entry> SelfType;
988 typedef HashSetBase<C, HashF, AltHashF, AllocatorDH<C, SID>, Entry> BaseType;
990 explicit HashSetDH(
void* pheap) : pHeap(pheap) { }
991 HashSetDH(
void* pheap,
int sizeHint) : BaseType(pheap, sizeHint), pHeap(pheap) { }
992 HashSetDH(
const SelfType& src) : BaseType(src), pHeap(src.pHeap) { }
995 void operator = (
const SelfType& src)
997 BaseType::Assign(src.pHeap, src);
1004 template<
class CRef>
1005 void Set(
const CRef& key)
1007 BaseType::Set(pHeap, key);
1010 template<
class CRef>
1011 inline void Add(
const CRef& key)
1013 BaseType::Add(pHeap, key);
1020 BaseType::CheckExpand(
this);
1024 void Resize(UPInt n)
1026 BaseType::SetCapacity(pHeap, n);
1032 void SetCapacity(UPInt newSize)
1034 BaseType::SetCapacity(pHeap, newSize);
1040 template<
class C,
class HashF = FixedSizeHash<C>,
1041 class AltHashF = HashF,
1042 class Allocator = AllocatorGH<C> >
1043 class HashSetUncached :
public HashSet<C, HashF, AltHashF, Allocator, HashsetEntry<C, HashF> >
1047 typedef HashSetUncached<C, HashF, AltHashF, Allocator> SelfType;
1048 typedef HashSet<C, HashF, AltHashF, Allocator, HashsetEntry<C, HashF> > BaseType;
1051 HashSetUncached() { }
1052 HashSetUncached(
int sizeHint) : BaseType(sizeHint) { }
1053 HashSetUncached(
const SelfType& src) : BaseType(src) { }
1054 ~HashSetUncached() { }
1056 void operator = (
const SelfType& src)
1058 BaseType::operator = (src);
1063 template<
class C,
class HashF = FixedSizeHash<C>,
1064 class AltHashF = HashF,
1065 int SID = Stat_Default_Mem >
1066 class HashSetUncachedLH :
public HashSet<C, HashF, AltHashF, AllocatorLH<C, SID>, HashsetEntry<C, HashF> >
1070 typedef HashSetUncachedLH<C, HashF, AltHashF, SID> SelfType;
1071 typedef HashSet<C, HashF, AltHashF, AllocatorLH<C, SID>, HashsetEntry<C, HashF> > BaseType;
1074 HashSetUncachedLH() { }
1075 HashSetUncachedLH(
int sizeHint) : BaseType(sizeHint) { }
1076 HashSetUncachedLH(
const SelfType& src) : BaseType(src) { }
1077 ~HashSetUncachedLH() { }
1079 void operator = (
const SelfType& src)
1081 BaseType::operator = (src);
1087 class HashF = FixedSizeHash<C>,
1088 class AltHashF = HashF,
1089 int SID = Stat_Default_Mem >
1090 class HashSetUncachedDH :
public HashSetDH<C, HashF, AltHashF, SID, HashsetEntry<C, HashF> >
1094 typedef HashSetUncachedDH<C, HashF, AltHashF, SID> SelfType;
1095 typedef HashSetDH<C, HashF, AltHashF, SID, HashsetEntry<C, HashF> > BaseType;
1098 explicit HashSetUncachedDH(
void* pheap) : BaseType(pheap) { }
1099 HashSetUncachedDH(
void* pheap,
int sizeHint) : BaseType(pheap, sizeHint) { }
1100 HashSetUncachedDH(
const SelfType& src) : BaseType(src) { }
1101 ~HashSetUncachedDH() { }
1103 void operator = (
const SelfType& src)
1105 BaseType::operator = (src);
1115 template<
class C,
class U,
class HashF>
1118 typedef HashNode<C, U, HashF> SelfType;
1119 typedef C FirstType;
1120 typedef U SecondType;
1132 NodeRef(
const C& f,
const U& s) : pFirst(&f), pSecond(&s) { }
1133 NodeRef(
const NodeRef& src) : pFirst(src.pFirst), pSecond(src.pSecond) { }
1136 inline UPInt GetHash()
const {
return HashF()(*pFirst); }
1138 operator const C& ()
const {
return *pFirst; }
1142 HashNode(
const HashNode& src) : First(src.First), Second(src.Second) { }
1143 HashNode(
const NodeRef& src) : First(*src.pFirst), Second(*src.pSecond) { }
1144 void operator = (
const NodeRef& src) { First = *src.pFirst; Second = *src.pSecond; }
1146 #ifdef KY_CC_RENESAS
1147 bool operator == (
const NodeRef& src)
const {
return (First == *src.pFirst); }
1151 bool operator == (
const K& src)
const {
return (First == src); }
1154 static UPInt CalcHash(
const K& data) {
return HashF()(data); }
1155 inline UPInt GetHash()
const {
return HashF()(First); }
1162 UPInt operator()(
const K& data)
const {
return data.GetHash(); }
1167 UPInt operator()(
const K& data)
const {
return HashNode<C,U,HashF>::CalcHash(data); }
1181 template<
class C,
class HashF>
1182 class HashsetNodeEntry
1190 : NextInChain(-2) { }
1191 HashsetNodeEntry(
const HashsetNodeEntry& e)
1192 : NextInChain(e.NextInChain), Value(e.Value) { }
1193 HashsetNodeEntry(
const C& key, SPInt next)
1194 : NextInChain(next), Value(key) { }
1195 HashsetNodeEntry(
const typename C::NodeRef& keyRef, SPInt next)
1196 : NextInChain(next), Value(keyRef) { }
1198 bool IsEmpty()
const {
return NextInChain == -2; }
1199 bool IsEndOfChain()
const {
return NextInChain == -1; }
1200 UPInt GetCachedHash(UPInt maskValue)
const {
return HashF()(Value) & maskValue; }
1201 void SetCachedHash(UPInt hashValue) { KY_UNUSED(hashValue); }
1210 void Free() { Clear(); }
1215 template<
class C,
class HashF>
1216 class HashsetCachedNodeEntry
1224 HashsetCachedNodeEntry()
1225 : NextInChain(-2) { }
1226 HashsetCachedNodeEntry(
const HashsetCachedNodeEntry& e)
1227 : NextInChain(e.NextInChain), HashValue(e.HashValue), Value(e.Value) { }
1228 HashsetCachedNodeEntry(
const C& key, SPInt next)
1229 : NextInChain(next), Value(key) { }
1230 HashsetCachedNodeEntry(
const typename C::NodeRef& keyRef, SPInt next)
1231 : NextInChain(next), Value(keyRef) { }
1233 bool IsEmpty()
const {
return NextInChain == -2; }
1234 bool IsEndOfChain()
const {
return NextInChain == -1; }
1235 UPInt GetCachedHash(UPInt maskValue)
const { KY_UNUSED(maskValue);
return HashValue; }
1236 void SetCachedHash(UPInt hashValue) { HashValue = hashValue; }
1245 void Free() { Clear(); }
1249 template<
class C,
class U,
1250 class HashF = FixedSizeHash<C>,
1251 class Allocator = AllocatorGH<C>,
1252 class HashNode = Kaim::HashNode<C,U,HashF>,
1253 class Entry = HashsetCachedNodeEntry<HashNode, typename HashNode::NodeHashF>,
1254 class Container = HashSet<HashNode,
typename HashNode::NodeHashF,
1255 typename HashNode::NodeAltHashF, Allocator,
1260 KY_MEMORY_REDEFINE_NEW(Hash, Allocator::StatId)
1263 typedef U ValueType;
1264 typedef Hash<C, U, HashF, Allocator, HashNode, Entry, Container> SelfType;
1271 Hash(
int sizeHint) : mHash(sizeHint) { }
1272 explicit Hash(
void* pheap) : mHash(pheap) { }
1273 Hash(
void* pheap,
int sizeHint) : mHash(pheap, sizeHint) { }
1274 Hash(
const SelfType& src) : mHash(src.mHash) { }
1277 void operator = (
const SelfType& src) { mHash = src.mHash; }
1280 inline void Clear() { mHash.Clear(); }
1282 inline bool IsEmpty()
const {
return mHash.IsEmpty(); }
1285 inline void Set(
const C& key,
const U& value)
1287 typename HashNode::NodeRef e(key, value);
1290 inline void Add(
const C& key,
const U& value)
1292 typename HashNode::NodeRef e(key, value);
1297 inline void Remove(
const C& key)
1299 mHash.RemoveAlt(key);
1302 inline void RemoveAlt(
const K& key)
1304 mHash.RemoveAlt(key);
1311 bool Get(
const C& key, U* pvalue)
const
1313 const HashNode* p = mHash.GetAlt(key);
1317 *pvalue = p->Second;
1324 bool GetAlt(
const K& key, U* pvalue)
const
1326 const HashNode* p = mHash.GetAlt(key);
1330 *pvalue = p->Second;
1339 inline U* Get(
const C& key)
1341 HashNode* p = mHash.GetAlt(key);
1342 return p ? &p->Second : 0;
1344 inline const U* Get(
const C& key)
const
1346 const HashNode* p = mHash.GetAlt(key);
1347 return p ? &p->Second : 0;
1351 inline U* GetAlt(
const K& key)
1353 HashNode* p = mHash.GetAlt(key);
1354 return p ? &p->Second : 0;
1357 inline const U* GetAlt(
const K& key)
const
1359 const HashNode* p = mHash.GetAlt(key);
1360 return p ? &p->Second : 0;
1364 inline UPInt GetSize()
const {
return mHash.GetSize(); }
1365 inline void Resize(UPInt n) { mHash.Resize(n); }
1366 inline void SetCapacity(UPInt newSize) { mHash.SetCapacity(newSize); }
1369 typedef typename Container::ConstIterator ConstIterator;
1370 typedef typename Container::Iterator Iterator;
1372 inline Iterator Begin() {
return mHash.Begin(); }
1373 inline Iterator End() {
return mHash.End(); }
1374 inline ConstIterator Begin()
const {
return mHash.Begin(); }
1375 inline ConstIterator End()
const {
return mHash.End(); }
1377 Iterator Find(
const C& key) {
return mHash.FindAlt(key); }
1378 ConstIterator Find(
const C& key)
const {
return mHash.FindAlt(key); }
1381 Iterator FindAlt(
const K& key) {
return mHash.FindAlt(key); }
1383 ConstIterator FindAlt(
const K& key)
const {
return mHash.FindAlt(key); }
1389 template<
class C,
class U,
1390 class HashF = FixedSizeHash<C>,
1391 int SID = Stat_Default_Mem,
1392 class HashNode = Kaim::HashNode<C,U,HashF>,
1393 class Entry = HashsetCachedNodeEntry<HashNode, typename HashNode::NodeHashF> >
1395 :
public Hash<C, U, HashF, AllocatorLH<C, SID>, HashNode, Entry>
1398 typedef HashLH<C, U, HashF, SID, HashNode, Entry> SelfType;
1399 typedef Hash<C, U, HashF, AllocatorLH<C, SID>, HashNode, Entry> BaseType;
1403 HashLH(
int sizeHint) : BaseType(sizeHint) { }
1404 HashLH(
const SelfType& src) : BaseType(src) { }
1406 void operator = (
const SelfType& src) { BaseType::operator = (src); }
1411 template<
class C,
class U,
1412 class HashF = FixedSizeHash<C>,
1413 int SID = Stat_Default_Mem,
1414 class HashNode = Kaim::HashNode<C,U,HashF>,
1415 class Entry = HashsetCachedNodeEntry<HashNode, typename HashNode::NodeHashF> >
1417 :
public Hash<C, U, HashF, AllocatorDH<C, SID>, HashNode, Entry,
1418 HashSetDH<HashNode, typename HashNode::NodeHashF,
1419 typename HashNode::NodeAltHashF, SID, Entry> >
1422 typedef HashDH<C, U, HashF, SID, HashNode, Entry> SelfType;
1423 typedef Hash<C, U, HashF, AllocatorDH<C, SID>, HashNode, Entry,
1424 HashSetDH<HashNode,
typename HashNode::NodeHashF,
1425 typename HashNode::NodeAltHashF, SID, Entry> > BaseType;
1428 explicit HashDH(
void* pheap) : BaseType(pheap) { }
1429 HashDH(
void* pheap,
int sizeHint) : BaseType(pheap, sizeHint) { }
1430 HashDH(
const SelfType& src) : BaseType(src) { }
1432 void operator = (
const SelfType& src) { BaseType::operator = (src); }
1437 template<
class C,
class U,
class HashF = FixedSizeHash<C>,
class Allocator = AllocatorGH<C> >
1439 :
public Hash<C, U, HashF, Allocator, HashNode<C,U,HashF>,
1440 HashsetNodeEntry<HashNode<C,U,HashF>, typename HashNode<C,U,HashF>::NodeHashF> >
1443 typedef HashUncached<C, U, HashF, Allocator> SelfType;
1444 typedef Hash<C, U, HashF, Allocator, HashNode<C,U,HashF>,
1445 HashsetNodeEntry<HashNode<C,U,HashF>,
typename HashNode<C,U,HashF>::NodeHashF> > BaseType;
1449 HashUncached(
int sizeHint) : BaseType(sizeHint) { }
1450 HashUncached(
const SelfType& src) : BaseType(src) { }
1452 void operator = (
const SelfType& src) { BaseType::operator = (src); }
1457 template<
class C,
class U,
class HashF = FixedSizeHash<C>,
int StatId = Stat_Default_Mem>
1458 class HashUncachedLH
1459 :
public HashLH<C, U, HashF, StatId, HashNode<C,U,HashF>,
1460 HashsetNodeEntry<HashNode<C,U,HashF>, typename HashNode<C,U,HashF>::NodeHashF> >
1463 typedef HashUncachedLH<C, U, HashF, StatId> SelfType;
1464 typedef HashLH<C, U, HashF, StatId, HashNode<C,U,HashF>,
1465 HashsetNodeEntry<HashNode<C,U,HashF>,
typename HashNode<C,U,HashF>::NodeHashF> > BaseType;
1468 HashUncachedLH() { }
1469 HashUncachedLH(
int sizeHint) : BaseType(sizeHint) { }
1470 HashUncachedLH(
const SelfType& src) : BaseType(src) { }
1471 ~HashUncachedLH() { }
1472 void operator = (
const SelfType& src) { BaseType::operator = (src); }
1476 template<
class C,
class U,
class HashF = FixedSizeHash<C>,
int StatId = Stat_Default_Mem>
1477 class HashUncachedDH
1478 :
public HashDH<C, U, HashF, StatId, HashNode<C,U,HashF>,
1479 HashsetNodeEntry<HashNode<C,U,HashF>, typename HashNode<C,U,HashF>::NodeHashF> >
1482 typedef HashUncachedDH<C, U, HashF, StatId> SelfType;
1483 typedef HashDH<C, U, HashF, StatId, HashNode<C,U,HashF>,
1484 HashsetNodeEntry<HashNode<C,U,HashF>,
typename HashNode<C,U,HashF>::NodeHashF> > BaseType;
1487 explicit HashUncachedDH(
void* pheap) : BaseType(pheap) { }
1488 HashUncachedDH(
void* pheap,
int sizeHint) : BaseType(pheap, sizeHint) { }
1489 HashUncachedDH(
const SelfType& src) : BaseType(src) { }
1490 ~HashUncachedDH() { }
1491 void operator = (
const SelfType& src) { BaseType::operator = (src); }
1496 template<
class C,
class U,
class Allocator = AllocatorGH<C>,
class HashF = IdentityHash<C> >
1498 :
public HashUncached<C, U, HashF, Allocator>
1501 typedef HashIdentity<C, U, Allocator, HashF> SelfType;
1502 typedef HashUncached<C, U, HashF, Allocator> BaseType;
1506 HashIdentity(
int sizeHint) : BaseType(sizeHint) { }
1507 HashIdentity(
const SelfType& src) : BaseType(src) { }
1509 void operator = (
const SelfType& src) { BaseType::operator = (src); }
1515 template<
class C,
class U,
int SID = Stat_Default_Mem,
class HashF = IdentityHash<C> >
1516 class HashIdentityLH
1517 :
public HashUncachedLH<C, U, HashF, SID>
1520 typedef HashIdentityLH<C, U, SID, HashF> SelfType;
1521 typedef HashUncachedLH<C, U, HashF, SID> BaseType;
1524 HashIdentityLH() { }
1525 HashIdentityLH(
int sizeHint) : BaseType(sizeHint) { }
1526 HashIdentityLH(
const SelfType& src) : BaseType(src) { }
1527 ~HashIdentityLH() { }
1528 void operator = (
const SelfType& src) { BaseType::operator = (src); }
1532 template<
class C,
class U,
int SID = Stat_Default_Mem,
class HashF = IdentityHash<C> >
1533 class HashIdentityDH
1534 :
public HashUncachedDH<C, U, HashF, SID>
1537 typedef HashIdentityDH<C, U, SID, HashF> SelfType;
1538 typedef HashUncachedDH<C, U, HashF, SID> BaseType;
1541 explicit HashIdentityDH(
void* pheap) : BaseType(pheap) { }
1542 HashIdentityDH(
void* pheap,
int sizeHint) : BaseType(pheap, sizeHint) { }
1543 HashIdentityDH(
const SelfType& src) : BaseType(src) { }
1544 ~HashIdentityDH() { }
1545 void operator = (
const SelfType& src) { BaseType::operator = (src); }
1551 #if defined(KY_DEFINE_NEW)
1552 #define new KY_DEFINE_NEW
Definition: gamekitcrowddispersion.h:20
Vec2f operator*(KyFloat32 s, const Vec2f &v)
Multiplies the X and Y coordinates of v by s.
Definition: vec2f.h:184