00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef OVR_Hash_h
00018 #define OVR_Hash_h
00019
00020 #include "OVR_ContainerAllocator.h"
00021 #include "OVR_Alg.h"
00022
00023
00024 #undef new
00025
00026 namespace OVR {
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059 template<class C>
00060 class IdentityHash
00061 {
00062 public:
00063 UPInt operator()(const C& data) const
00064 { return (UPInt) data; }
00065 };
00066
00067
00068 template<class C>
00069 class FixedSizeHash
00070 {
00071 public:
00072
00073
00074
00075
00076 static OVR_FORCE_INLINE UPInt SDBM_Hash(const void* data_in, UPInt size, UPInt seed = 5381)
00077 {
00078 const UByte* data = (const UByte*) data_in;
00079 UPInt h = seed;
00080 while (size > 0)
00081 {
00082 size--;
00083 h = (h << 16) + (h << 6) - h + (UPInt)data[size];
00084 }
00085 return h;
00086 }
00087
00088 UPInt operator()(const C& data) const
00089 {
00090 unsigned char* p = (unsigned char*) &data;
00091 int size = sizeof(C);
00092
00093 return SDBM_Hash(p, size);
00094 }
00095 };
00096
00097
00098
00099
00100
00101
00102
00103 template<class C, class HashF>
00104 class HashsetEntry
00105 {
00106 public:
00107
00108 SPInt NextInChain;
00109 C Value;
00110
00111 HashsetEntry()
00112 : NextInChain(-2) { }
00113 HashsetEntry(const HashsetEntry& e)
00114 : NextInChain(e.NextInChain), Value(e.Value) { }
00115 HashsetEntry(const C& key, SPInt next)
00116 : NextInChain(next), Value(key) { }
00117
00118 bool IsEmpty() const { return NextInChain == -2; }
00119 bool IsEndOfChain() const { return NextInChain == -1; }
00120
00121
00122
00123 UPInt GetCachedHash(UPInt maskValue) const { return HashF()(Value) & maskValue; }
00124 void SetCachedHash(UPInt) {}
00125
00126 void Clear()
00127 {
00128 Value.~C();
00129 NextInChain = -2;
00130 }
00131
00132
00133 void Free() { Clear(); }
00134 };
00135
00136
00137
00138 template<class C, class HashF>
00139 class HashsetCachedEntry
00140 {
00141 public:
00142
00143 SPInt NextInChain;
00144 UPInt HashValue;
00145 C Value;
00146
00147 HashsetCachedEntry()
00148 : NextInChain(-2) { }
00149 HashsetCachedEntry(const HashsetCachedEntry& e)
00150 : NextInChain(e.NextInChain), HashValue(e.HashValue), Value(e.Value) { }
00151 HashsetCachedEntry(const C& key, SPInt next)
00152 : NextInChain(next), Value(key) { }
00153
00154 bool IsEmpty() const { return NextInChain == -2; }
00155 bool IsEndOfChain() const { return NextInChain == -1; }
00156
00157
00158
00159 UPInt GetCachedHash(UPInt maskValue) const { OVR_UNUSED(maskValue); return HashValue; }
00160 void SetCachedHash(UPInt hashValue) { HashValue = hashValue; }
00161
00162 void Clear()
00163 {
00164 Value.~C();
00165 NextInChain = -2;
00166 }
00167
00168
00169 void Free() { Clear(); }
00170 };
00171
00172
00173
00174
00175
00176
00177
00178
00179
00180 template<class C, class HashF = FixedSizeHash<C>,
00181 class AltHashF = HashF,
00182 class Allocator = ContainerAllocator<C>,
00183 class Entry = HashsetCachedEntry<C, HashF> >
00184 class HashSetBase
00185 {
00186 enum { HashMinSize = 8 };
00187
00188 public:
00189 OVR_MEMORY_REDEFINE_NEW(HashSetBase)
00190
00191 typedef HashSetBase<C, HashF, AltHashF, Allocator, Entry> SelfType;
00192
00193 HashSetBase() : pTable(NULL) { }
00194 HashSetBase(int sizeHint) : pTable(NULL) { SetCapacity(this, sizeHint); }
00195 HashSetBase(const SelfType& src) : pTable(NULL) { Assign(this, src); }
00196
00197 ~HashSetBase()
00198 {
00199 if (pTable)
00200 {
00201
00202 for (UPInt i = 0, n = pTable->SizeMask; i <= n; i++)
00203 {
00204 Entry* e = &E(i);
00205 if (!e->IsEmpty())
00206 e->Free();
00207 }
00208
00209 Allocator::Free(pTable);
00210 pTable = NULL;
00211 }
00212 }
00213
00214
00215 void Assign(const SelfType& src)
00216 {
00217 Clear();
00218 if (src.IsEmpty() == false)
00219 {
00220 SetCapacity(src.GetSize());
00221
00222 for (ConstIterator it = src.Begin(); it != src.End(); ++it)
00223 {
00224 Add(*it);
00225 }
00226 }
00227 }
00228
00229
00230
00231 void Clear()
00232 {
00233 if (pTable)
00234 {
00235
00236 for (UPInt i = 0, n = pTable->SizeMask; i <= n; i++)
00237 {
00238 Entry* e = &E(i);
00239 if (!e->IsEmpty())
00240 e->Clear();
00241 }
00242
00243 Allocator::Free(pTable);
00244 pTable = NULL;
00245 }
00246 }
00247
00248
00249 bool IsEmpty() const
00250 {
00251 return pTable == NULL || pTable->EntryCount == 0;
00252 }
00253
00254
00255
00256
00257
00258 template<class CRef>
00259 void Set(const CRef& key)
00260 {
00261 UPInt hashValue = HashF()(key);
00262 SPInt index = (SPInt)-1;
00263
00264 if (pTable != NULL)
00265 index = findIndexCore(key, hashValue & pTable->SizeMask);
00266
00267 if (index >= 0)
00268 {
00269 E(index).Value = key;
00270 }
00271 else
00272 {
00273
00274 add(key, hashValue);
00275 }
00276 }
00277
00278 template<class CRef>
00279 inline void Add(const CRef& key)
00280 {
00281 UPInt hashValue = HashF()(key);
00282 add(key, hashValue);
00283 }
00284
00285
00286 template<class K>
00287 void RemoveAlt(const K& key)
00288 {
00289 if (pTable == NULL)
00290 return;
00291
00292 UPInt hashValue = AltHashF()(key);
00293 SPInt index = hashValue & pTable->SizeMask;
00294
00295 Entry* e = &E(index);
00296
00297
00298 if (e->IsEmpty() || (e->GetCachedHash(pTable->SizeMask) != (UPInt)index))
00299 return;
00300
00301
00302 SPInt naturalIndex = index;
00303 SPInt prevIndex = -1;
00304
00305 while ((e->GetCachedHash(pTable->SizeMask) != (UPInt)naturalIndex) || !(e->Value == key))
00306 {
00307
00308 prevIndex = index;
00309 index = e->NextInChain;
00310 if (index == -1)
00311 return;
00312 e = &E(index);
00313 }
00314
00315
00316 if (naturalIndex == index)
00317 {
00318
00319 if (!e->IsEndOfChain())
00320 {
00321 Entry* enext = &E(e->NextInChain);
00322 e->Clear();
00323 new (e) Entry(*enext);
00324
00325 e = enext;
00326 }
00327 }
00328 else
00329 {
00330
00331 E(prevIndex).NextInChain = e->NextInChain;
00332 }
00333
00334
00335 e->Clear();
00336 pTable->EntryCount --;
00337
00338 }
00339
00340
00341 template<class CRef>
00342 void Remove(const CRef& key)
00343 {
00344 RemoveAlt(key);
00345 }
00346
00347
00348
00349
00350 template<class K>
00351 C* Get(const K& key)
00352 {
00353 SPInt index = findIndex(key);
00354 if (index >= 0)
00355 return &E(index).Value;
00356 return 0;
00357 }
00358
00359 template<class K>
00360 const C* Get(const K& key) const
00361 {
00362 SPInt index = findIndex(key);
00363 if (index >= 0)
00364 return &E(index).Value;
00365 return 0;
00366 }
00367
00368
00369 template<class K>
00370 const C* GetAlt(const K& key) const
00371 {
00372 SPInt index = findIndexAlt(key);
00373 if (index >= 0)
00374 return &E(index).Value;
00375 return 0;
00376 }
00377
00378 template<class K>
00379 C* GetAlt(const K& key)
00380 {
00381 SPInt index = findIndexAlt(key);
00382 if (index >= 0)
00383 return &E(index).Value;
00384 return 0;
00385 }
00386
00387 template<class K>
00388 bool GetAlt(const K& key, C* pval) const
00389 {
00390 SPInt index = findIndexAlt(key);
00391 if (index >= 0)
00392 {
00393 if (pval)
00394 *pval = E(index).Value;
00395 return true;
00396 }
00397 return false;
00398 }
00399
00400
00401 UPInt GetSize() const
00402 {
00403 return pTable == NULL ? 0 : (UPInt)pTable->EntryCount;
00404 }
00405
00406
00407
00408
00409 void CheckExpand()
00410 {
00411 if (pTable == NULL)
00412 {
00413
00414 setRawCapacity(HashMinSize);
00415 }
00416 else if (pTable->EntryCount * 5 > (pTable->SizeMask + 1) * 4)
00417 {
00418
00419 setRawCapacity((pTable->SizeMask + 1) * 2);
00420 }
00421 }
00422
00423
00424 void Resize(UPInt n)
00425 {
00426
00427
00428
00429
00430
00431
00432 SetCapacity(n);
00433 }
00434
00435
00436
00437
00438 void SetCapacity(UPInt newSize)
00439 {
00440 UPInt newRawSize = (newSize * 5) / 4;
00441 if (newRawSize <= GetSize())
00442 return;
00443 setRawCapacity(newRawSize);
00444 }
00445
00446
00447 #ifdef OVR_CC_MSVC
00448 #if (OVR_CC_MSVC < 1300)
00449 # pragma warning(disable : 4284)
00450 #endif
00451 #endif
00452
00453
00454 struct ConstIterator
00455 {
00456 const C& operator * () const
00457 {
00458 OVR_ASSERT(Index >= 0 && Index <= (SPInt)pHash->pTable->SizeMask);
00459 return pHash->E(Index).Value;
00460 }
00461
00462 const C* operator -> () const
00463 {
00464 OVR_ASSERT(Index >= 0 && Index <= (SPInt)pHash->pTable->SizeMask);
00465 return &pHash->E(Index).Value;
00466 }
00467
00468 void operator ++ ()
00469 {
00470
00471 if (Index <= (SPInt)pHash->pTable->SizeMask)
00472 {
00473 Index++;
00474 while ((UPInt)Index <= pHash->pTable->SizeMask &&
00475 pHash->E(Index).IsEmpty())
00476 {
00477 Index++;
00478 }
00479 }
00480 }
00481
00482 bool operator == (const ConstIterator& it) const
00483 {
00484 if (IsEnd() && it.IsEnd())
00485 {
00486 return true;
00487 }
00488 else
00489 {
00490 return (pHash == it.pHash) && (Index == it.Index);
00491 }
00492 }
00493
00494 bool operator != (const ConstIterator& it) const
00495 {
00496 return ! (*this == it);
00497 }
00498
00499
00500 bool IsEnd() const
00501 {
00502 return (pHash == NULL) ||
00503 (pHash->pTable == NULL) ||
00504 (Index > (SPInt)pHash->pTable->SizeMask);
00505 }
00506
00507 ConstIterator()
00508 : pHash(NULL), Index(0)
00509 { }
00510
00511 public:
00512
00513
00514 ConstIterator(const SelfType* h, SPInt index)
00515 : pHash(h), Index(index)
00516 { }
00517
00518 const SelfType* GetContainer() const
00519 {
00520 return pHash;
00521 }
00522 SPInt GetIndex() const
00523 {
00524 return Index;
00525 }
00526
00527 protected:
00528 friend class HashSetBase<C, HashF, AltHashF, Allocator, Entry>;
00529
00530 const SelfType* pHash;
00531 SPInt Index;
00532 };
00533
00534 friend struct ConstIterator;
00535
00536
00537
00538 struct Iterator : public ConstIterator
00539 {
00540
00541 C& operator*() const
00542 {
00543 OVR_ASSERT(ConstIterator::Index >= 0 && ConstIterator::Index <= (SPInt)ConstIterator::pHash->pTable->SizeMask);
00544 return const_cast<SelfType*>(ConstIterator::pHash)->E(ConstIterator::Index).Value;
00545 }
00546
00547 C* operator->() const
00548 {
00549 return &(operator*());
00550 }
00551
00552 Iterator()
00553 : ConstIterator(NULL, 0)
00554 { }
00555
00556
00557 void Remove()
00558 {
00559 RemoveAlt(operator*());
00560 }
00561
00562 template <class K>
00563 void RemoveAlt(const K& key)
00564 {
00565 SelfType* phash = const_cast<SelfType*>(ConstIterator::pHash);
00566
00567
00568
00569 UPInt hashValue = AltHashF()(key);
00570 SPInt index = hashValue & phash->pTable->SizeMask;
00571
00572 Entry* e = &phash->E(index);
00573
00574
00575 if (e->IsEmpty() || (e->GetCachedHash(phash->pTable->SizeMask) != (UPInt)index))
00576 return;
00577
00578
00579 SPInt naturalIndex = index;
00580 SPInt prevIndex = -1;
00581
00582 while ((e->GetCachedHash(phash->pTable->SizeMask) != (UPInt)naturalIndex) || !(e->Value == key))
00583 {
00584
00585 prevIndex = index;
00586 index = e->NextInChain;
00587 if (index == -1)
00588 return;
00589 e = &phash->E(index);
00590 }
00591
00592 if (index == (SPInt)ConstIterator::Index)
00593 {
00594
00595 if (naturalIndex == index)
00596 {
00597
00598 if (!e->IsEndOfChain())
00599 {
00600 Entry* enext = &phash->E(e->NextInChain);
00601 e->Clear();
00602 new (e) Entry(*enext);
00603
00604 e = enext;
00605 --ConstIterator::Index;
00606 }
00607 }
00608 else
00609 {
00610
00611 phash->E(prevIndex).NextInChain = e->NextInChain;
00612 }
00613
00614
00615 e->Clear();
00616 phash->pTable->EntryCount --;
00617 }
00618 else
00619 OVR_ASSERT(0);
00620 }
00621
00622 private:
00623 friend class HashSetBase<C, HashF, AltHashF, Allocator, Entry>;
00624
00625 Iterator(SelfType* h, SPInt i0)
00626 : ConstIterator(h, i0)
00627 { }
00628 };
00629
00630 friend struct Iterator;
00631
00632 Iterator Begin()
00633 {
00634 if (pTable == 0)
00635 return Iterator(NULL, 0);
00636
00637
00638 UPInt i0 = 0;
00639 while (i0 <= pTable->SizeMask && E(i0).IsEmpty())
00640 {
00641 i0++;
00642 }
00643 return Iterator(this, i0);
00644 }
00645 Iterator End() { return Iterator(NULL, 0); }
00646
00647 ConstIterator Begin() const { return const_cast<SelfType*>(this)->Begin(); }
00648 ConstIterator End() const { return const_cast<SelfType*>(this)->End(); }
00649
00650 template<class K>
00651 Iterator Find(const K& key)
00652 {
00653 SPInt index = findIndex(key);
00654 if (index >= 0)
00655 return Iterator(this, index);
00656 return Iterator(NULL, 0);
00657 }
00658
00659 template<class K>
00660 Iterator FindAlt(const K& key)
00661 {
00662 SPInt index = findIndexAlt(key);
00663 if (index >= 0)
00664 return Iterator(this, index);
00665 return Iterator(NULL, 0);
00666 }
00667
00668 template<class K>
00669 ConstIterator Find(const K& key) const { return const_cast<SelfType*>(this)->Find(key); }
00670
00671 template<class K>
00672 ConstIterator FindAlt(const K& key) const { return const_cast<SelfType*>(this)->FindAlt(key); }
00673
00674 private:
00675
00676 template<class K>
00677 SPInt findIndex(const K& key) const
00678 {
00679 if (pTable == NULL)
00680 return -1;
00681 UPInt hashValue = HashF()(key) & pTable->SizeMask;
00682 return findIndexCore(key, hashValue);
00683 }
00684
00685 template<class K>
00686 SPInt findIndexAlt(const K& key) const
00687 {
00688 if (pTable == NULL)
00689 return -1;
00690 UPInt hashValue = AltHashF()(key) & pTable->SizeMask;
00691 return findIndexCore(key, hashValue);
00692 }
00693
00694
00695 template<class K>
00696 SPInt findIndexCore(const K& key, UPInt hashValue) const
00697 {
00698
00699 OVR_ASSERT(pTable != 0);
00700
00701 OVR_ASSERT((hashValue & ~pTable->SizeMask) == 0);
00702
00703 UPInt index = hashValue;
00704 const Entry* e = &E(index);
00705
00706
00707 if (e->IsEmpty() || (e->GetCachedHash(pTable->SizeMask) != index))
00708 return -1;
00709
00710 while(1)
00711 {
00712 OVR_ASSERT(e->GetCachedHash(pTable->SizeMask) == hashValue);
00713
00714 if (e->GetCachedHash(pTable->SizeMask) == hashValue && e->Value == key)
00715 {
00716
00717 return index;
00718 }
00719
00720
00721 OVR_ASSERT(!(e->Value == key));
00722
00723
00724 index = e->NextInChain;
00725 if (index == (UPInt)-1)
00726 break;
00727
00728 e = &E(index);
00729 OVR_ASSERT(!e->IsEmpty());
00730 }
00731 return -1;
00732 }
00733
00734
00735
00736 template<class CRef>
00737 void add(const CRef& key, UPInt hashValue)
00738 {
00739 CheckExpand();
00740 hashValue &= pTable->SizeMask;
00741
00742 pTable->EntryCount++;
00743
00744 SPInt index = hashValue;
00745 Entry* naturalEntry = &(E(index));
00746
00747 if (naturalEntry->IsEmpty())
00748 {
00749
00750 new (naturalEntry) Entry(key, -1);
00751 }
00752 else
00753 {
00754
00755 SPInt blankIndex = index;
00756 do {
00757 blankIndex = (blankIndex + 1) & pTable->SizeMask;
00758 } while(!E(blankIndex).IsEmpty());
00759
00760 Entry* blankEntry = &E(blankIndex);
00761
00762 if (naturalEntry->GetCachedHash(pTable->SizeMask) == (UPInt)index)
00763 {
00764
00765
00766
00767 new (blankEntry) Entry(*naturalEntry);
00768
00769
00770 naturalEntry->Value = key;
00771 naturalEntry->NextInChain = blankIndex;
00772 }
00773 else
00774 {
00775
00776
00777
00778
00779
00780 SPInt collidedIndex = naturalEntry->GetCachedHash(pTable->SizeMask);
00781 OVR_ASSERT(collidedIndex >= 0 && collidedIndex <= (SPInt)pTable->SizeMask);
00782 for (;;)
00783 {
00784 Entry* e = &E(collidedIndex);
00785 if (e->NextInChain == index)
00786 {
00787
00788 new (blankEntry) Entry(*naturalEntry);
00789 e->NextInChain = blankIndex;
00790 break;
00791 }
00792 collidedIndex = e->NextInChain;
00793 OVR_ASSERT(collidedIndex >= 0 && collidedIndex <= (SPInt)pTable->SizeMask);
00794 }
00795
00796
00797 naturalEntry->Value = key;
00798 naturalEntry->NextInChain = -1;
00799 }
00800 }
00801
00802
00803 naturalEntry->SetCachedHash(hashValue);
00804 }
00805
00806
00807 Entry& E(UPInt index)
00808 {
00809
00810 OVR_ASSERT(index <= pTable->SizeMask);
00811 return *(((Entry*) (pTable + 1)) + index);
00812 }
00813 const Entry& E(UPInt index) const
00814 {
00815 OVR_ASSERT(index <= pTable->SizeMask);
00816 return *(((Entry*) (pTable + 1)) + index);
00817 }
00818
00819
00820
00821
00822
00823
00824 void setRawCapacity(UPInt newSize)
00825 {
00826 if (newSize == 0)
00827 {
00828
00829 Clear();
00830 return;
00831 }
00832
00833
00834
00835
00836 if (newSize < HashMinSize)
00837 newSize = HashMinSize;
00838 else
00839 {
00840
00841 int bits = Alg::UpperBit(newSize-1) + 1;
00842 OVR_ASSERT((UPInt(1) << bits) >= newSize);
00843 newSize = UPInt(1) << bits;
00844 }
00845
00846 SelfType newHash;
00847 newHash.pTable = (TableType*)
00848 Allocator::Alloc(
00849 sizeof(TableType) + sizeof(Entry) * newSize);
00850
00851 OVR_ASSERT(newHash.pTable);
00852
00853 newHash.pTable->EntryCount = 0;
00854 newHash.pTable->SizeMask = newSize - 1;
00855 UPInt i, n;
00856
00857
00858 for (i = 0; i < newSize; i++)
00859 newHash.E(i).NextInChain = -2;
00860
00861
00862 if (pTable)
00863 {
00864 for (i = 0, n = pTable->SizeMask; i <= n; i++)
00865 {
00866 Entry* e = &E(i);
00867 if (e->IsEmpty() == false)
00868 {
00869
00870 newHash.Add(e->Value);
00871
00872 e->Clear();
00873 }
00874 }
00875
00876
00877 Allocator::Free(pTable);
00878 }
00879
00880
00881 pTable = newHash.pTable;
00882 newHash.pTable = NULL;
00883 }
00884
00885 struct TableType
00886 {
00887 UPInt EntryCount;
00888 UPInt SizeMask;
00889
00890
00891 };
00892 TableType* pTable;
00893 };
00894
00895
00896
00897
00898 template<class C, class HashF = FixedSizeHash<C>,
00899 class AltHashF = HashF,
00900 class Allocator = ContainerAllocator<C>,
00901 class Entry = HashsetCachedEntry<C, HashF> >
00902 class HashSet : public HashSetBase<C, HashF, AltHashF, Allocator, Entry>
00903 {
00904 public:
00905 typedef HashSetBase<C, HashF, AltHashF, Allocator, Entry> BaseType;
00906 typedef HashSet<C, HashF, AltHashF, Allocator, Entry> SelfType;
00907
00908 HashSet() { }
00909 HashSet(int sizeHint) : BaseType(sizeHint) { }
00910 HashSet(const SelfType& src) : BaseType(src) { }
00911 ~HashSet() { }
00912
00913 void operator = (const SelfType& src) { BaseType::Assign(src); }
00914
00915
00916
00917
00918 template<class CRef>
00919 void Set(const CRef& key)
00920 {
00921 BaseType::Set(key);
00922 }
00923
00924 template<class CRef>
00925 inline void Add(const CRef& key)
00926 {
00927 BaseType::Add(key);
00928 }
00929
00930
00931 void Resize(UPInt n)
00932 {
00933 BaseType::SetCapacity(n);
00934 }
00935
00936
00937
00938
00939 void SetCapacity(UPInt newSize)
00940 {
00941 BaseType::SetCapacity(newSize);
00942 }
00943
00944 };
00945
00946
00947 template<class C, class HashF = FixedSizeHash<C>,
00948 class AltHashF = HashF,
00949 class Allocator = ContainerAllocator<C> >
00950 class HashSetUncached : public HashSet<C, HashF, AltHashF, Allocator, HashsetEntry<C, HashF> >
00951 {
00952 public:
00953
00954 typedef HashSetUncached<C, HashF, AltHashF, Allocator> SelfType;
00955 typedef HashSet<C, HashF, AltHashF, Allocator, HashsetEntry<C, HashF> > BaseType;
00956
00957
00958 HashSetUncached() { }
00959 HashSetUncached(int sizeHint) : BaseType(sizeHint) { }
00960 HashSetUncached(const SelfType& src) : BaseType(src) { }
00961 ~HashSetUncached() { }
00962
00963 void operator = (const SelfType& src)
00964 {
00965 BaseType::operator = (src);
00966 }
00967 };
00968
00969
00970
00971
00972
00973
00974
00975 template<class C, class U, class HashF>
00976 struct HashNode
00977 {
00978 typedef HashNode<C, U, HashF> SelfType;
00979 typedef C FirstType;
00980 typedef U SecondType;
00981
00982 C First;
00983 U Second;
00984
00985
00986
00987 struct NodeRef
00988 {
00989 const C* pFirst;
00990 const U* pSecond;
00991
00992 NodeRef(const C& f, const U& s) : pFirst(&f), pSecond(&s) { }
00993 NodeRef(const NodeRef& src) : pFirst(src.pFirst), pSecond(src.pSecond) { }
00994
00995
00996 inline UPInt GetHash() const { return HashF()(*pFirst); }
00997
00998 operator const C& () const { return *pFirst; }
00999 };
01000
01001
01002 HashNode(const HashNode& src) : First(src.First), Second(src.Second) { }
01003 HashNode(const NodeRef& src) : First(*src.pFirst), Second(*src.pSecond) { }
01004 void operator = (const NodeRef& src) { First = *src.pFirst; Second = *src.pSecond; }
01005
01006 template<class K>
01007 bool operator == (const K& src) const { return (First == src); }
01008
01009 template<class K>
01010 static UPInt CalcHash(const K& data) { return HashF()(data); }
01011 inline UPInt GetHash() const { return HashF()(First); }
01012
01013
01014
01015 struct NodeHashF
01016 {
01017 template<class K>
01018 UPInt operator()(const K& data) const { return data.GetHash(); }
01019 };
01020 struct NodeAltHashF
01021 {
01022 template<class K>
01023 UPInt operator()(const K& data) const { return HashNode<C,U,HashF>::CalcHash(data); }
01024 };
01025 };
01026
01027
01028
01029
01030
01031
01032
01033
01034
01035
01036
01037 template<class C, class HashF>
01038 class HashsetNodeEntry
01039 {
01040 public:
01041
01042 SPInt NextInChain;
01043 C Value;
01044
01045 HashsetNodeEntry()
01046 : NextInChain(-2) { }
01047 HashsetNodeEntry(const HashsetNodeEntry& e)
01048 : NextInChain(e.NextInChain), Value(e.Value) { }
01049 HashsetNodeEntry(const C& key, SPInt next)
01050 : NextInChain(next), Value(key) { }
01051 HashsetNodeEntry(const typename C::NodeRef& keyRef, SPInt next)
01052 : NextInChain(next), Value(keyRef) { }
01053
01054 bool IsEmpty() const { return NextInChain == -2; }
01055 bool IsEndOfChain() const { return NextInChain == -1; }
01056 UPInt GetCachedHash(UPInt maskValue) const { return HashF()(Value) & maskValue; }
01057 void SetCachedHash(UPInt hashValue) { OVR_UNUSED(hashValue); }
01058
01059 void Clear()
01060 {
01061 Value.~C();
01062 NextInChain = -2;
01063 }
01064
01065
01066 void Free() { Clear(); }
01067 };
01068
01069
01070
01071 template<class C, class HashF>
01072 class HashsetCachedNodeEntry
01073 {
01074 public:
01075
01076 SPInt NextInChain;
01077 UPInt HashValue;
01078 C Value;
01079
01080 HashsetCachedNodeEntry()
01081 : NextInChain(-2) { }
01082 HashsetCachedNodeEntry(const HashsetCachedNodeEntry& e)
01083 : NextInChain(e.NextInChain), HashValue(e.HashValue), Value(e.Value) { }
01084 HashsetCachedNodeEntry(const C& key, SPInt next)
01085 : NextInChain(next), Value(key) { }
01086 HashsetCachedNodeEntry(const typename C::NodeRef& keyRef, SPInt next)
01087 : NextInChain(next), Value(keyRef) { }
01088
01089 bool IsEmpty() const { return NextInChain == -2; }
01090 bool IsEndOfChain() const { return NextInChain == -1; }
01091 UPInt GetCachedHash(UPInt maskValue) const { OVR_UNUSED(maskValue); return HashValue; }
01092 void SetCachedHash(UPInt hashValue) { HashValue = hashValue; }
01093
01094 void Clear()
01095 {
01096 Value.~C();
01097 NextInChain = -2;
01098 }
01099
01100
01101 void Free() { Clear(); }
01102 };
01103
01104
01105
01106 template<class C, class U,
01107 class HashF = FixedSizeHash<C>,
01108 class Allocator = ContainerAllocator<C>,
01109 class HashNode = OVR::HashNode<C,U,HashF>,
01110 class Entry = HashsetCachedNodeEntry<HashNode, typename HashNode::NodeHashF>,
01111 class Container = HashSet<HashNode, typename HashNode::NodeHashF,
01112 typename HashNode::NodeAltHashF, Allocator,
01113 Entry> >
01114 class Hash
01115 {
01116 public:
01117 OVR_MEMORY_REDEFINE_NEW(Hash)
01118
01119
01120 typedef U ValueType;
01121 typedef Hash<C, U, HashF, Allocator, HashNode, Entry, Container> SelfType;
01122
01123
01124 Container mHash;
01125
01126 public:
01127 Hash() { }
01128 Hash(int sizeHint) : mHash(sizeHint) { }
01129 Hash(const SelfType& src) : mHash(src.mHash) { }
01130 ~Hash() { }
01131
01132 void operator = (const SelfType& src) { mHash = src.mHash; }
01133
01134
01135 inline void Clear() { mHash.Clear(); }
01136
01137 inline bool IsEmpty() const { return mHash.IsEmpty(); }
01138
01139
01140 inline void Set(const C& key, const U& value)
01141 {
01142 typename HashNode::NodeRef e(key, value);
01143 mHash.Set(e);
01144 }
01145 inline void Add(const C& key, const U& value)
01146 {
01147 typename HashNode::NodeRef e(key, value);
01148 mHash.Add(e);
01149 }
01150
01151
01152 inline void Remove(const C& key)
01153 {
01154 mHash.RemoveAlt(key);
01155 }
01156 template<class K>
01157 inline void RemoveAlt(const K& key)
01158 {
01159 mHash.RemoveAlt(key);
01160 }
01161
01162
01163
01164
01165
01166 bool Get(const C& key, U* pvalue) const
01167 {
01168 const HashNode* p = mHash.GetAlt(key);
01169 if (p)
01170 {
01171 if (pvalue)
01172 *pvalue = p->Second;
01173 return true;
01174 }
01175 return false;
01176 }
01177
01178 template<class K>
01179 bool GetAlt(const K& key, U* pvalue) const
01180 {
01181 const HashNode* p = mHash.GetAlt(key);
01182 if (p)
01183 {
01184 if (pvalue)
01185 *pvalue = p->Second;
01186 return true;
01187 }
01188 return false;
01189 }
01190
01191
01192
01193
01194 inline U* Get(const C& key)
01195 {
01196 HashNode* p = mHash.GetAlt(key);
01197 return p ? &p->Second : 0;
01198 }
01199 inline const U* Get(const C& key) const
01200 {
01201 const HashNode* p = mHash.GetAlt(key);
01202 return p ? &p->Second : 0;
01203 }
01204
01205 template<class K>
01206 inline U* GetAlt(const K& key)
01207 {
01208 HashNode* p = mHash.GetAlt(key);
01209 return p ? &p->Second : 0;
01210 }
01211 template<class K>
01212 inline const U* GetAlt(const K& key) const
01213 {
01214 const HashNode* p = mHash.GetAlt(key);
01215 return p ? &p->Second : 0;
01216 }
01217
01218
01219 inline UPInt GetSize() const { return mHash.GetSize(); }
01220 inline void Resize(UPInt n) { mHash.Resize(n); }
01221 inline void SetCapacity(UPInt newSize) { mHash.SetCapacity(newSize); }
01222
01223
01224 typedef typename Container::ConstIterator ConstIterator;
01225 typedef typename Container::Iterator Iterator;
01226
01227 inline Iterator Begin() { return mHash.Begin(); }
01228 inline Iterator End() { return mHash.End(); }
01229 inline ConstIterator Begin() const { return mHash.Begin(); }
01230 inline ConstIterator End() const { return mHash.End(); }
01231
01232 Iterator Find(const C& key) { return mHash.FindAlt(key); }
01233 ConstIterator Find(const C& key) const { return mHash.FindAlt(key); }
01234
01235 template<class K>
01236 Iterator FindAlt(const K& key) { return mHash.FindAlt(key); }
01237 template<class K>
01238 ConstIterator FindAlt(const K& key) const { return mHash.FindAlt(key); }
01239 };
01240
01241
01242
01243
01244 template<class C, class U, class HashF = FixedSizeHash<C>, class Allocator = ContainerAllocator<C> >
01245 class HashUncached
01246 : public Hash<C, U, HashF, Allocator, HashNode<C,U,HashF>,
01247 HashsetNodeEntry<HashNode<C,U,HashF>, typename HashNode<C,U,HashF>::NodeHashF> >
01248 {
01249 public:
01250 typedef HashUncached<C, U, HashF, Allocator> SelfType;
01251 typedef Hash<C, U, HashF, Allocator, HashNode<C,U,HashF>,
01252 HashsetNodeEntry<HashNode<C,U,HashF>,
01253 typename HashNode<C,U,HashF>::NodeHashF> > BaseType;
01254
01255
01256 HashUncached() { }
01257 HashUncached(int sizeHint) : BaseType(sizeHint) { }
01258 HashUncached(const SelfType& src) : BaseType(src) { }
01259 ~HashUncached() { }
01260 void operator = (const SelfType& src) { BaseType::operator = (src); }
01261 };
01262
01263
01264
01265
01266
01267 template<class C, class U, class Allocator = ContainerAllocator<C>, class HashF = IdentityHash<C> >
01268 class HashIdentity
01269 : public HashUncached<C, U, HashF, Allocator>
01270 {
01271 public:
01272 typedef HashIdentity<C, U, Allocator, HashF> SelfType;
01273 typedef HashUncached<C, U, HashF, Allocator> BaseType;
01274
01275
01276 HashIdentity() { }
01277 HashIdentity(int sizeHint) : BaseType(sizeHint) { }
01278 HashIdentity(const SelfType& src) : BaseType(src) { }
01279 ~HashIdentity() { }
01280 void operator = (const SelfType& src) { BaseType::operator = (src); }
01281 };
01282
01283
01284 }
01285
01286
01287 #ifdef OVR_DEFINE_NEW
01288 #define new OVR_DEFINE_NEW
01289 #endif
01290
01291 #endif