OVR_Hash.h
Go to the documentation of this file.
00001 /************************************************************************************
00002 
00003 PublicHeader:   None
00004 Filename    :   OVR_Hash.h
00005 Content     :   Template hash-table/set implementation
00006 Created     :   September 19, 2012
00007 Notes       : 
00008 
00009 Copyright   :   Copyright 2012 Oculus VR, Inc. All Rights reserved.
00010 
00011 Use of this software is subject to the terms of the Oculus license
00012 agreement provided at the time of installation or download, or which
00013 otherwise accompanies this software in either electronic or hard copy form.
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 // 'new' operator is redefined/used in this file.
00024 #undef new
00025 
00026 namespace OVR {
00027 
00028 //-----------------------------------------------------------------------------------
00029 // ***** Hash Table Implementation
00030 
00031 // HastSet and Hash.
00032 //
00033 // Hash table, linear probing, internal chaining.  One  interesting/nice thing
00034 // about this implementation is that the table itself is a flat chunk of memory
00035 // containing no pointers, only relative indices. If the key and value types
00036 // of the Hash contain no pointers, then the Hash can be serialized using raw IO.
00037 //
00038 // Never shrinks, unless you explicitly Clear() it.  Expands on
00039 // demand, though.  For best results, if you know roughly how big your
00040 // table will be, default it to that size when you create it.
00041 //
00042 // Key usability feature:
00043 //
00044 //   1. Allows node hash values to either be cached or not.
00045 //
00046 //   2. Allows for alternative keys with methods such as GetAlt(). Handy
00047 //      if you need to search nodes by their components; no need to create
00048 //      temporary nodes.
00049 //
00050 
00051 
00052 // *** Hash functors:
00053 //
00054 //  IdentityHash  - use when the key is already a good hash
00055 //  HFixedSizeHash - general hash based on object's in-memory representation.
00056 
00057 
00058 // Hash is just the input value; can use this for integer-indexed hash tables.
00059 template<class C>
00060 class IdentityHash
00061 {
00062 public:
00063     UPInt operator()(const C& data) const
00064     { return (UPInt) data; }
00065 };
00066 
00067 // Computes a hash of an object's representation.
00068 template<class C>
00069 class FixedSizeHash
00070 {
00071 public:
00072     // Alternative: "sdbm" hash function, suggested at same web page
00073     // above, http::/www.cs.yorku.ca/~oz/hash.html
00074     // This is somewhat slower then Bernstein, but it works way better than the above
00075     // hash function for hashing large numbers of 32-bit ints.
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 // *** HashsetEntry Entry types. 
00100 
00101 // Compact hash table Entry type that re-computes hash keys during hash traversal.
00102 // Good to use if the hash function is cheap or the hash value is already cached in C.
00103 template<class C, class HashF>
00104 class HashsetEntry
00105 {
00106 public:
00107     // Internal chaining for collisions.
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     // Cached hash value access - can be optimized bu storing hash locally.
00122     // Mask value only needs to be used if SetCachedHash is not implemented.
00123     UPInt   GetCachedHash(UPInt maskValue) const  { return HashF()(Value) & maskValue; }
00124     void    SetCachedHash(UPInt)                  {}
00125 
00126     void    Clear()
00127     {        
00128         Value.~C(); // placement delete
00129         NextInChain = -2;
00130     }
00131     // Free is only used from dtor of hash; Clear is used during regular operations:
00132     // assignment, hash reallocations, value reassignments, so on.
00133     void    Free() { Clear(); }
00134 };
00135 
00136 // Hash table Entry type that caches the Entry hash value for nodes, so that it
00137 // does not need to be re-computed during access.
00138 template<class C, class HashF>
00139 class HashsetCachedEntry
00140 {
00141 public:
00142     // Internal chaining for collisions.
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     // Cached hash value access - can be optimized bu storing hash locally.
00158     // Mask value only needs to be used if SetCachedHash is not implemented.
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     // Free is only used from dtor of hash; Clear is used during regular operations:
00168     // assignment, hash reallocations, value reassignments, so on.
00169     void    Free() { Clear(); }
00170 };
00171 
00172 
00173 //-----------------------------------------------------------------------------------
00174 // *** HashSet implementation - relies on either cached or regular entries.
00175 //
00176 // Use: Entry = HashsetCachedEntry<C, HashF> if hashes are expensive to
00177 //              compute and thus need caching in entries.
00178 //      Entry = HashsetEntry<C, HashF> if hashes are already externally cached.
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             // Delete the entries.
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     // Remove all entries from the HashSet table.
00231     void Clear() 
00232     {
00233         if (pTable)
00234         {
00235             // Delete the entries.
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     // Returns true if the HashSet is empty.
00249     bool IsEmpty() const
00250     {
00251         return pTable == NULL || pTable->EntryCount == 0;
00252     }
00253 
00254 
00255     // Set a new or existing value under the key, to the value.
00256     // Pass a different class of 'key' so that assignment reference object
00257     // can be passed instead of the actual object.
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             // Entry under key doesn't exist.
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     // Remove by alternative key.
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         // If empty node or occupied by collider, we have nothing to remove.
00298         if (e->IsEmpty() || (e->GetCachedHash(pTable->SizeMask) != (UPInt)index))
00299             return;        
00300 
00301         // Save index
00302         SPInt   naturalIndex = index;
00303         SPInt   prevIndex    = -1;
00304 
00305         while ((e->GetCachedHash(pTable->SizeMask) != (UPInt)naturalIndex) || !(e->Value == key))
00306         {
00307             // Keep looking through the chain.
00308             prevIndex   = index;
00309             index       = e->NextInChain;
00310             if (index == -1)
00311                 return; // End of chain, item not found
00312             e = &E(index);
00313         }
00314 
00315         // Found it - our item is at index
00316         if (naturalIndex == index)
00317         {
00318             // If we have a follower, move it to us
00319             if (!e->IsEndOfChain())
00320             {               
00321                 Entry*  enext = &E(e->NextInChain);
00322                 e->Clear();
00323                 new (e) Entry(*enext);
00324                 // Point us to the follower's cell that will be cleared
00325                 e = enext;
00326             }
00327         }
00328         else
00329         {
00330             // We are not at natural index, so deal with the prev items next index
00331             E(prevIndex).NextInChain = e->NextInChain;
00332         }
00333 
00334         // Clear us, of the follower cell that was moved.
00335         e->Clear();
00336         pTable->EntryCount --;
00337         // Should we check the size to condense hash? ...
00338     }
00339 
00340     // Remove by main key.
00341     template<class CRef>
00342     void Remove(const CRef& key)
00343     {
00344         RemoveAlt(key);
00345     }
00346 
00347     // Retrieve the pointer to a value under the given key.
00348     //  - If there's no value under the key, then return NULL.    
00349     //  - If there is a value, return the pointer.    
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     // Alternative key versions of Get. Used by Hash.
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     // Resize the HashSet table to fit one more Entry.  Often this
00408     // doesn't involve any action.
00409     void CheckExpand()
00410     {
00411         if (pTable == NULL)
00412         {
00413             // Initial creation of table.  Make a minimum-sized table.
00414             setRawCapacity(HashMinSize);
00415         }
00416         else if (pTable->EntryCount * 5 > (pTable->SizeMask + 1) * 4)
00417         {
00418             // pTable is more than 5/4 ths full.  Expand.
00419             setRawCapacity((pTable->SizeMask + 1) * 2);
00420         }
00421     }
00422 
00423     // Hint the bucket count to >= n.
00424     void Resize(UPInt n)    
00425     {
00426         // Not really sure what this means in relation to
00427         // STLport's hash_map... they say they "increase the
00428         // bucket count to at least n" -- but does that mean
00429         // their real capacity after Resize(n) is more like
00430         // n*2 (since they do linked-list chaining within
00431         // buckets?).
00432         SetCapacity(n);
00433     }
00434 
00435     // Size the HashSet so that it can comfortably contain the given
00436     // number of elements.  If the HashSet already contains more
00437     // elements than newSize, then this may be a no-op.
00438     void SetCapacity(UPInt newSize)
00439     {
00440         UPInt newRawSize = (newSize * 5) / 4;
00441         if (newRawSize <= GetSize())
00442             return;
00443         setRawCapacity(newRawSize);
00444     }
00445 
00446     // Disable inappropriate 'operator ->' warning on MSVC6.
00447 #ifdef OVR_CC_MSVC
00448 #if (OVR_CC_MSVC < 1300)
00449 # pragma warning(disable : 4284)
00450 #endif
00451 #endif
00452 
00453     // Iterator API, like STL.
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             // Find next non-empty Entry.
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         // Constructor was intentionally made public to allow create
00513         // iterator with arbitrary index.
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     // Non-const Iterator; Get most of it from ConstIterator.
00538     struct Iterator : public ConstIterator
00539     {      
00540         // Allow non-const access to entries.
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         // Removes current element from Hash
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             //Entry*      ee = &phash->E(ConstIterator::Index);
00567             //const C&    key = ee->Value;
00568 
00569             UPInt       hashValue = AltHashF()(key);
00570             SPInt       index     = hashValue & phash->pTable->SizeMask;
00571 
00572             Entry*      e = &phash->E(index);
00573 
00574             // If empty node or occupied by collider, we have nothing to remove.
00575             if (e->IsEmpty() || (e->GetCachedHash(phash->pTable->SizeMask) != (UPInt)index))
00576                 return;        
00577 
00578             // Save index
00579             SPInt   naturalIndex = index;
00580             SPInt   prevIndex    = -1;
00581 
00582             while ((e->GetCachedHash(phash->pTable->SizeMask) != (UPInt)naturalIndex) || !(e->Value == key))
00583             {
00584                 // Keep looking through the chain.
00585                 prevIndex   = index;
00586                 index       = e->NextInChain;
00587                 if (index == -1)
00588                     return; // End of chain, item not found
00589                 e = &phash->E(index);
00590             }
00591 
00592             if (index == (SPInt)ConstIterator::Index)
00593             {
00594                 // Found it - our item is at index
00595                 if (naturalIndex == index)
00596                 {
00597                     // If we have a follower, move it to us
00598                     if (!e->IsEndOfChain())
00599                     {               
00600                         Entry*  enext = &phash->E(e->NextInChain);
00601                         e->Clear();
00602                         new (e) Entry(*enext);
00603                         // Point us to the follower's cell that will be cleared
00604                         e = enext;
00605                         --ConstIterator::Index;
00606                     }
00607                 }
00608                 else
00609                 {
00610                     // We are not at natural index, so deal with the prev items next index
00611                     phash->E(prevIndex).NextInChain = e->NextInChain;
00612                 }
00613 
00614                 // Clear us, of the follower cell that was moved.
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         // Scan till we hit the First valid Entry.
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     // Find the index of the matching Entry.  If no match, then return -1.
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     // Find the index of the matching Entry.  If no match, then return -1.
00695     template<class K>
00696     SPInt findIndexCore(const K& key, UPInt hashValue) const
00697     {
00698         // Table must exist.
00699         OVR_ASSERT(pTable != 0);
00700         // Hash key must be 'and-ed' by the caller.
00701         OVR_ASSERT((hashValue & ~pTable->SizeMask) == 0);
00702 
00703         UPInt           index = hashValue;
00704         const Entry*    e     = &E(index);
00705 
00706         // If empty or occupied by a collider, not found.
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                 // Found it.
00717                 return index;
00718             }
00719             // Values can not be equal at this point.
00720             // That would mean that the hash key for the same value differs.
00721             OVR_ASSERT(!(e->Value == key));
00722 
00723             // Keep looking through the chain.
00724             index = e->NextInChain;
00725             if (index == (UPInt)-1)
00726                 break; // end of chain
00727 
00728             e = &E(index);
00729             OVR_ASSERT(!e->IsEmpty());
00730         }
00731         return -1;
00732     }
00733 
00734 
00735     // Add a new value to the HashSet table, under the specified key.
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             // Put the new Entry in.
00750             new (naturalEntry) Entry(key, -1);
00751         }
00752         else
00753         {
00754             // Find a blank spot.
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                 // Collision.  Link into this chain.
00765 
00766                 // Move existing list head.
00767                 new (blankEntry) Entry(*naturalEntry);    // placement new, copy ctor
00768 
00769                 // Put the new info in the natural Entry.
00770                 naturalEntry->Value       = key;
00771                 naturalEntry->NextInChain = blankIndex;
00772             }
00773             else
00774             {
00775                 // Existing Entry does not naturally
00776                 // belong in this slot.  Existing
00777                 // Entry must be moved.
00778 
00779                 // Find natural location of collided element (i.e. root of chain)
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                         // Here's where we need to splice.
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                 // Put the new data in the natural Entry.
00797                 naturalEntry->Value       = key;
00798                 naturalEntry->NextInChain = -1;                
00799             }            
00800         }
00801 
00802         // Record hash value: has effect only if cached node is used.
00803         naturalEntry->SetCachedHash(hashValue);
00804     }
00805 
00806     // Index access helpers.
00807     Entry& E(UPInt index)
00808     {
00809         // Must have pTable and access needs to be within bounds.
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     // Resize the HashSet table to the given size (Rehash the
00821     // contents of the current table).  The arg is the number of
00822     // HashSet table entries, not the number of elements we should
00823     // actually contain (which will be less than this).
00824     void    setRawCapacity(UPInt newSize)    
00825     {
00826         if (newSize == 0)
00827         {
00828             // Special case.
00829             Clear();
00830             return;
00831         }
00832 
00833         // Minimum size; don't incur rehashing cost when expanding
00834         // very small tables. Not that we perform this check before 
00835         // 'log2f' call to avoid fp exception with newSize == 1.
00836         if (newSize < HashMinSize)        
00837             newSize = HashMinSize;       
00838         else
00839         {
00840             // Force newSize to be a power of two.
00841             int bits = Alg::UpperBit(newSize-1) + 1; // Chop( Log2f((float)(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         // Need to do something on alloc failure!
00851         OVR_ASSERT(newHash.pTable);
00852 
00853         newHash.pTable->EntryCount = 0;
00854         newHash.pTable->SizeMask = newSize - 1;
00855         UPInt i, n;
00856 
00857         // Mark all entries as empty.
00858         for (i = 0; i < newSize; i++)
00859             newHash.E(i).NextInChain = -2;
00860 
00861         // Copy stuff to newHash
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                     // Insert old Entry into new HashSet.
00870                     newHash.Add(e->Value);
00871                     // placement delete of old element
00872                     e->Clear();
00873                 }
00874             }
00875 
00876             // Delete our old data buffer.
00877             Allocator::Free(pTable);
00878         }
00879 
00880         // Steal newHash's data.
00881         pTable = newHash.pTable;
00882         newHash.pTable = NULL;
00883     }
00884 
00885     struct TableType
00886     {
00887         UPInt EntryCount;
00888         UPInt SizeMask;
00889         // Entry array follows this structure
00890         // in memory.
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     // Set a new or existing value under the key, to the value.
00916     // Pass a different class of 'key' so that assignment reference object
00917     // can be passed instead of the actual object.
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     // Hint the bucket count to >= n.
00931     void Resize(UPInt n)    
00932     {
00933         BaseType::SetCapacity(n);
00934     }
00935 
00936     // Size the HashSet so that it can comfortably contain the given
00937     // number of elements.  If the HashSet already contains more
00938     // elements than newSize, then this may be a no-op.
00939     void SetCapacity(UPInt newSize)
00940     {
00941         BaseType::SetCapacity(newSize);
00942     }
00943 
00944 };
00945 
00946 // HashSet with uncached hash code; declared for convenience.
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     // Delegated constructors.
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 // ***** Hash hash table implementation
00972 
00973 // Node for Hash - necessary so that Hash can delegate its implementation
00974 // to HashSet.
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     // NodeRef is used to allow passing of elements into HashSet
00986     // without using a temporary object.
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         // Enable computation of ghash_node_hashf.
00996         inline UPInt GetHash() const            { return HashF()(*pFirst); } 
00997         // Necessary conversion to allow HashNode::operator == to work.
00998         operator const C& () const              { return *pFirst; }
00999     };
01000 
01001     // Note: No default constructor is necessary.
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     // Hash functors used with this node. A separate functor is used for alternative
01014     // key lookup so that it does not need to access the '.First' element.    
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 // **** Extra hashset_entry types to allow NodeRef construction.
01030 
01031 // The big difference between the below types and the ones used in hash_set is that
01032 // these allow initializing the node with 'typename C::NodeRef& keyRef', which
01033 // is critical to avoid temporary node allocation on stack when using placement new.
01034 
01035 // Compact hash table Entry type that re-computes hash keys during hash traversal.
01036 // Good to use if the hash function is cheap or the hash value is already cached in C.
01037 template<class C, class HashF>
01038 class HashsetNodeEntry
01039 {
01040 public:
01041     // Internal chaining for collisions.
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(); // placement delete
01062         NextInChain = -2;
01063     }
01064     // Free is only used from dtor of hash; Clear is used during regular operations:
01065     // assignment, hash reallocations, value reassignments, so on.
01066     void    Free() { Clear(); }
01067 };
01068 
01069 // Hash table Entry type that caches the Entry hash value for nodes, so that it
01070 // does not need to be re-computed during access.
01071 template<class C, class HashF>
01072 class HashsetCachedNodeEntry
01073 {
01074 public:
01075     // Internal chaining for collisions.
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     // Free is only used from dtor of hash; Clear is used during regular operations:
01100     // assignment, hash reallocations, value reassignments, so on.
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     // Types used for hash_set.
01120     typedef U                                                           ValueType;
01121     typedef Hash<C, U, HashF, Allocator, HashNode, Entry, Container>    SelfType;
01122 
01123     // Actual hash table itself, implemented as hash_set.
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     // Remove all entries from the Hash table.
01135     inline void    Clear() { mHash.Clear(); }
01136     // Returns true if the Hash is empty.
01137     inline bool    IsEmpty() const { return mHash.IsEmpty(); }
01138 
01139     // Access (set).
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     // Removes an element by clearing its Entry.
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     // Retrieve the value under the given key.    
01163     //  - If there's no value under the key, then return false and leave *pvalue alone.
01164     //  - If there is a value, return true, and Set *Pvalue to the Entry's value.
01165     //  - If value == NULL, return true or false according to the presence of the key.    
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     // Retrieve the pointer to a value under the given key.    
01192     //  - If there's no value under the key, then return NULL.    
01193     //  - If there is a value, return the pointer.    
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     // Sizing methods - delegate to Hash.
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     // Iterator API, like STL.
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 // Hash with uncached hash code; declared for convenience.
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     // Delegated constructors.
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 // And identity hash in which keys serve as hash value. Can be uncached,
01266 // since hash computation is assumed cheap.
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     // Delegated constructors.
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 } // OVR
01285 
01286 
01287 #ifdef OVR_DEFINE_NEW
01288 #define new OVR_DEFINE_NEW
01289 #endif
01290 
01291 #endif


oculus_sdk
Author(s): Tully Foote
autogenerated on Thu Jun 6 2019 20:13:48