1.1 --- a/libovr/Src/Kernel/OVR_Hash.h	Sat Sep 14 17:51:03 2013 +0300
     1.2 +++ b/libovr/Src/Kernel/OVR_Hash.h	Sun Sep 15 04:10:05 2013 +0300
     1.3 @@ -1,1 +1,1291 @@
     1.4 -/************************************************************************************
     1.5 
     1.6 PublicHeader:   None
     1.7 Filename    :   OVR_Hash.h
     1.8 Content     :   Template hash-table/set implementation
     1.9 Created     :   September 19, 2012
    1.10 Notes       : 
    1.11 
    1.12 Copyright   :   Copyright 2012 Oculus VR, Inc. All Rights reserved.
    1.13 
    1.14 Use of this software is subject to the terms of the Oculus license
    1.15 agreement provided at the time of installation or download, or which
    1.16 otherwise accompanies this software in either electronic or hard copy form.
    1.17 
    1.18 ************************************************************************************/
    1.19 
    1.20 #ifndef OVR_Hash_h
    1.21 #define OVR_Hash_h
    1.22 
    1.23 #include "OVR_ContainerAllocator.h"
    1.24 #include "OVR_Alg.h"
    1.25 
    1.26 // 'new' operator is redefined/used in this file.
    1.27 #undef new
    1.28 
    1.29 namespace OVR {
    1.30 
    1.31 //-----------------------------------------------------------------------------------
    1.32 // ***** Hash Table Implementation
    1.33 
    1.34 // HastSet and Hash.
    1.35 //
    1.36 // Hash table, linear probing, internal chaining.  One  interesting/nice thing
    1.37 // about this implementation is that the table itself is a flat chunk of memory
    1.38 // containing no pointers, only relative indices. If the key and value types
    1.39 // of the Hash contain no pointers, then the Hash can be serialized using raw IO.
    1.40 //
    1.41 // Never shrinks, unless you explicitly Clear() it.  Expands on
    1.42 // demand, though.  For best results, if you know roughly how big your
    1.43 // table will be, default it to that size when you create it.
    1.44 //
    1.45 // Key usability feature:
    1.46 //
    1.47 //   1. Allows node hash values to either be cached or not.
    1.48 //
    1.49 //   2. Allows for alternative keys with methods such as GetAlt(). Handy
    1.50 //      if you need to search nodes by their components; no need to create
    1.51 //      temporary nodes.
    1.52 //
    1.53 
    1.54 
    1.55 // *** Hash functors:
    1.56 //
    1.57 //  IdentityHash  - use when the key is already a good hash
    1.58 //  HFixedSizeHash - general hash based on object's in-memory representation.
    1.59 
    1.60 
    1.61 // Hash is just the input value; can use this for integer-indexed hash tables.
    1.62 template<class C>
    1.63 class IdentityHash
    1.64 {
    1.65 public:
    1.66     UPInt operator()(const C& data) const
    1.67     { return (UPInt) data; }
    1.68 };
    1.69 
    1.70 // Computes a hash of an object's representation.
    1.71 template<class C>
    1.72 class FixedSizeHash
    1.73 {
    1.74 public:
    1.75     // Alternative: "sdbm" hash function, suggested at same web page
    1.76     // above, http::/www.cs.yorku.ca/~oz/hash.html
    1.77     // This is somewhat slower then Bernstein, but it works way better than the above
    1.78     // hash function for hashing large numbers of 32-bit ints.
    1.79     static OVR_FORCE_INLINE UPInt SDBM_Hash(const void* data_in, UPInt size, UPInt seed = 5381)     
    1.80     {
    1.81         const UByte* data = (const UByte*) data_in;
    1.82         UPInt        h = seed;
    1.83         while (size > 0)
    1.84         {
    1.85             size--;
    1.86             h = (h << 16) + (h << 6) - h + (UPInt)data[size];
    1.87         }   
    1.88         return h;
    1.89     }
    1.90 
    1.91     UPInt operator()(const C& data) const
    1.92     {
    1.93         unsigned char*  p = (unsigned char*) &data;
    1.94         int size = sizeof(C);
    1.95 
    1.96         return SDBM_Hash(p, size);
    1.97     }
    1.98 };
    1.99 
   1.100 
   1.101 
   1.102 // *** HashsetEntry Entry types. 
   1.103 
   1.104 // Compact hash table Entry type that re-computes hash keys during hash traversal.
   1.105 // Good to use if the hash function is cheap or the hash value is already cached in C.
   1.106 template<class C, class HashF>
   1.107 class HashsetEntry
   1.108 {
   1.109 public:
   1.110     // Internal chaining for collisions.
   1.111     SPInt       NextInChain;
   1.112     C           Value;
   1.113 
   1.114     HashsetEntry()
   1.115         : NextInChain(-2) { }
   1.116     HashsetEntry(const HashsetEntry& e)
   1.117         : NextInChain(e.NextInChain), Value(e.Value) { }
   1.118     HashsetEntry(const C& key, SPInt next)
   1.119         : NextInChain(next), Value(key) { }
   1.120 
   1.121     bool    IsEmpty() const          { return NextInChain == -2;  }
   1.122     bool    IsEndOfChain() const     { return NextInChain == -1;  }
   1.123 
   1.124     // Cached hash value access - can be optimized bu storing hash locally.
   1.125     // Mask value only needs to be used if SetCachedHash is not implemented.
   1.126     UPInt   GetCachedHash(UPInt maskValue) const  { return HashF()(Value) & maskValue; }
   1.127     void    SetCachedHash(UPInt)                  {}
   1.128 
   1.129     void    Clear()
   1.130     {        
   1.131         Value.~C(); // placement delete
   1.132         NextInChain = -2;
   1.133     }
   1.134     // Free is only used from dtor of hash; Clear is used during regular operations:
   1.135     // assignment, hash reallocations, value reassignments, so on.
   1.136     void    Free() { Clear(); }
   1.137 };
   1.138 
   1.139 // Hash table Entry type that caches the Entry hash value for nodes, so that it
   1.140 // does not need to be re-computed during access.
   1.141 template<class C, class HashF>
   1.142 class HashsetCachedEntry
   1.143 {
   1.144 public:
   1.145     // Internal chaining for collisions.
   1.146     SPInt       NextInChain;
   1.147     UPInt       HashValue;
   1.148     C           Value;
   1.149 
   1.150     HashsetCachedEntry()
   1.151         : NextInChain(-2) { }
   1.152     HashsetCachedEntry(const HashsetCachedEntry& e)
   1.153         : NextInChain(e.NextInChain), HashValue(e.HashValue), Value(e.Value) { }
   1.154     HashsetCachedEntry(const C& key, SPInt next)
   1.155         : NextInChain(next), Value(key) { }
   1.156 
   1.157     bool    IsEmpty() const          { return NextInChain == -2;  }
   1.158     bool    IsEndOfChain() const     { return NextInChain == -1;  }
   1.159 
   1.160     // Cached hash value access - can be optimized bu storing hash locally.
   1.161     // Mask value only needs to be used if SetCachedHash is not implemented.
   1.162     UPInt   GetCachedHash(UPInt maskValue) const  { OVR_UNUSED(maskValue); return HashValue; }
   1.163     void    SetCachedHash(UPInt hashValue)        { HashValue = hashValue; }
   1.164 
   1.165     void    Clear()
   1.166     {
   1.167         Value.~C();
   1.168         NextInChain = -2;
   1.169     }
   1.170     // Free is only used from dtor of hash; Clear is used during regular operations:
   1.171     // assignment, hash reallocations, value reassignments, so on.
   1.172     void    Free() { Clear(); }
   1.173 };
   1.174 
   1.175 
   1.176 //-----------------------------------------------------------------------------------
   1.177 // *** HashSet implementation - relies on either cached or regular entries.
   1.178 //
   1.179 // Use: Entry = HashsetCachedEntry<C, HashF> if hashes are expensive to
   1.180 //              compute and thus need caching in entries.
   1.181 //      Entry = HashsetEntry<C, HashF> if hashes are already externally cached.
   1.182 //
   1.183 template<class C, class HashF = FixedSizeHash<C>,
   1.184          class AltHashF = HashF, 
   1.185          class Allocator = ContainerAllocator<C>,
   1.186          class Entry = HashsetCachedEntry<C, HashF> >
   1.187 class HashSetBase
   1.188 {
   1.189     enum { HashMinSize = 8 };
   1.190 
   1.191 public:
   1.192     OVR_MEMORY_REDEFINE_NEW(HashSetBase)
   1.193 
   1.194     typedef HashSetBase<C, HashF, AltHashF, Allocator, Entry>    SelfType;
   1.195 
   1.196     HashSetBase() : pTable(NULL)                       {   }
   1.197     HashSetBase(int sizeHint) : pTable(NULL)           { SetCapacity(this, sizeHint);  }
   1.198     HashSetBase(const SelfType& src) : pTable(NULL)    { Assign(this, src); }
   1.199 
   1.200     ~HashSetBase()                                     
   1.201     { 
   1.202         if (pTable)
   1.203         {
   1.204             // Delete the entries.
   1.205             for (UPInt i = 0, n = pTable->SizeMask; i <= n; i++)
   1.206             {
   1.207                 Entry*  e = &E(i);
   1.208                 if (!e->IsEmpty())             
   1.209                     e->Free();
   1.210             }            
   1.211 
   1.212             Allocator::Free(pTable);
   1.213             pTable = NULL;
   1.214         }
   1.215     }
   1.216 
   1.217 
   1.218     void Assign(const SelfType& src)
   1.219     {
   1.220         Clear();
   1.221         if (src.IsEmpty() == false)
   1.222         {
   1.223             SetCapacity(src.GetSize());
   1.224 
   1.225             for (ConstIterator it = src.Begin(); it != src.End(); ++it)
   1.226             {
   1.227                 Add(*it);
   1.228             }
   1.229         }
   1.230     }
   1.231 
   1.232 
   1.233     // Remove all entries from the HashSet table.
   1.234     void Clear() 
   1.235     {
   1.236         if (pTable)
   1.237         {
   1.238             // Delete the entries.
   1.239             for (UPInt i = 0, n = pTable->SizeMask; i <= n; i++)
   1.240             {
   1.241                 Entry*  e = &E(i);
   1.242                 if (!e->IsEmpty())             
   1.243                     e->Clear();
   1.244             }            
   1.245                 
   1.246             Allocator::Free(pTable);
   1.247             pTable = NULL;
   1.248         }
   1.249     }
   1.250 
   1.251     // Returns true if the HashSet is empty.
   1.252     bool IsEmpty() const
   1.253     {
   1.254         return pTable == NULL || pTable->EntryCount == 0;
   1.255     }
   1.256 
   1.257 
   1.258     // Set a new or existing value under the key, to the value.
   1.259     // Pass a different class of 'key' so that assignment reference object
   1.260     // can be passed instead of the actual object.
   1.261     template<class CRef>
   1.262     void Set(const CRef& key)
   1.263     {
   1.264         UPInt  hashValue = HashF()(key);
   1.265         SPInt  index     = (SPInt)-1;
   1.266 
   1.267         if (pTable != NULL)
   1.268             index = findIndexCore(key, hashValue & pTable->SizeMask);
   1.269 
   1.270         if (index >= 0)
   1.271         {            
   1.272             E(index).Value = key;
   1.273         }
   1.274         else
   1.275         {
   1.276             // Entry under key doesn't exist.
   1.277             add(key, hashValue);
   1.278         }
   1.279     }
   1.280 
   1.281     template<class CRef>
   1.282     inline void Add(const CRef& key)
   1.283     {
   1.284         UPInt hashValue = HashF()(key);
   1.285         add(key, hashValue);
   1.286     }
   1.287 
   1.288     // Remove by alternative key.
   1.289     template<class K>
   1.290     void RemoveAlt(const K& key)
   1.291     {   
   1.292         if (pTable == NULL)
   1.293             return;
   1.294 
   1.295         UPInt   hashValue = AltHashF()(key);
   1.296         SPInt   index     = hashValue & pTable->SizeMask;
   1.297 
   1.298         Entry*  e = &E(index);
   1.299 
   1.300         // If empty node or occupied by collider, we have nothing to remove.
   1.301         if (e->IsEmpty() || (e->GetCachedHash(pTable->SizeMask) != (UPInt)index))
   1.302             return;        
   1.303 
   1.304         // Save index
   1.305         SPInt   naturalIndex = index;
   1.306         SPInt   prevIndex    = -1;
   1.307 
   1.308         while ((e->GetCachedHash(pTable->SizeMask) != (UPInt)naturalIndex) || !(e->Value == key))
   1.309         {
   1.310             // Keep looking through the chain.
   1.311             prevIndex   = index;
   1.312             index       = e->NextInChain;
   1.313             if (index == -1)
   1.314                 return; // End of chain, item not found
   1.315             e = &E(index);
   1.316         }
   1.317 
   1.318         // Found it - our item is at index
   1.319         if (naturalIndex == index)
   1.320         {
   1.321             // If we have a follower, move it to us
   1.322             if (!e->IsEndOfChain())
   1.323             {               
   1.324                 Entry*  enext = &E(e->NextInChain);
   1.325                 e->Clear();
   1.326                 new (e) Entry(*enext);
   1.327                 // Point us to the follower's cell that will be cleared
   1.328                 e = enext;
   1.329             }
   1.330         }
   1.331         else
   1.332         {
   1.333             // We are not at natural index, so deal with the prev items next index
   1.334             E(prevIndex).NextInChain = e->NextInChain;
   1.335         }
   1.336 
   1.337         // Clear us, of the follower cell that was moved.
   1.338         e->Clear();
   1.339         pTable->EntryCount --;
   1.340         // Should we check the size to condense hash? ...
   1.341     }
   1.342 
   1.343     // Remove by main key.
   1.344     template<class CRef>
   1.345     void Remove(const CRef& key)
   1.346     {
   1.347         RemoveAlt(key);
   1.348     }
   1.349 
   1.350     // Retrieve the pointer to a value under the given key.
   1.351     //  - If there's no value under the key, then return NULL.    
   1.352     //  - If there is a value, return the pointer.    
   1.353     template<class K>
   1.354     C* Get(const K& key)
   1.355     {
   1.356         SPInt   index = findIndex(key);
   1.357         if (index >= 0)        
   1.358             return &E(index).Value;        
   1.359         return 0;
   1.360     }   
   1.361 
   1.362     template<class K>
   1.363     const C* Get(const K& key) const
   1.364     {
   1.365         SPInt   index = findIndex(key);
   1.366         if (index >= 0)        
   1.367             return &E(index).Value;        
   1.368         return 0;
   1.369     }
   1.370 
   1.371     // Alternative key versions of Get. Used by Hash.
   1.372     template<class K>
   1.373     const C* GetAlt(const K& key) const
   1.374     {
   1.375         SPInt   index = findIndexAlt(key);
   1.376         if (index >= 0)        
   1.377             return &E(index).Value;
   1.378         return 0;
   1.379     }
   1.380 
   1.381     template<class K>
   1.382     C* GetAlt(const K& key)
   1.383     {
   1.384         SPInt   index = findIndexAlt(key);
   1.385         if (index >= 0)        
   1.386             return &E(index).Value;
   1.387         return 0;
   1.388     }   
   1.389 
   1.390     template<class K>
   1.391     bool GetAlt(const K& key, C* pval) const
   1.392     {
   1.393         SPInt   index = findIndexAlt(key);
   1.394         if (index >= 0)
   1.395         {
   1.396             if (pval)
   1.397                 *pval = E(index).Value;
   1.398             return true;
   1.399         }
   1.400         return false;
   1.401     }
   1.402 
   1.403 
   1.404     UPInt GetSize() const
   1.405     {
   1.406         return pTable == NULL ? 0 : (UPInt)pTable->EntryCount;
   1.407     }
   1.408 
   1.409 
   1.410     // Resize the HashSet table to fit one more Entry.  Often this
   1.411     // doesn't involve any action.
   1.412     void CheckExpand()
   1.413     {
   1.414         if (pTable == NULL)
   1.415         {
   1.416             // Initial creation of table.  Make a minimum-sized table.
   1.417             setRawCapacity(HashMinSize);
   1.418         }
   1.419         else if (pTable->EntryCount * 5 > (pTable->SizeMask + 1) * 4)
   1.420         {
   1.421             // pTable is more than 5/4 ths full.  Expand.
   1.422             setRawCapacity((pTable->SizeMask + 1) * 2);
   1.423         }
   1.424     }
   1.425 
   1.426     // Hint the bucket count to >= n.
   1.427     void Resize(UPInt n)    
   1.428     {
   1.429         // Not really sure what this means in relation to
   1.430         // STLport's hash_map... they say they "increase the
   1.431         // bucket count to at least n" -- but does that mean
   1.432         // their real capacity after Resize(n) is more like
   1.433         // n*2 (since they do linked-list chaining within
   1.434         // buckets?).
   1.435         SetCapacity(n);
   1.436     }
   1.437 
   1.438     // Size the HashSet so that it can comfortably contain the given
   1.439     // number of elements.  If the HashSet already contains more
   1.440     // elements than newSize, then this may be a no-op.
   1.441     void SetCapacity(UPInt newSize)
   1.442     {
   1.443         UPInt newRawSize = (newSize * 5) / 4;
   1.444         if (newRawSize <= GetSize())
   1.445             return;
   1.446         setRawCapacity(newRawSize);
   1.447     }
   1.448 
   1.449     // Disable inappropriate 'operator ->' warning on MSVC6.
   1.450 #ifdef OVR_CC_MSVC
   1.451 #if (OVR_CC_MSVC < 1300)
   1.452 # pragma warning(disable : 4284)
   1.453 #endif
   1.454 #endif
   1.455 
   1.456     // Iterator API, like STL.
   1.457     struct ConstIterator
   1.458     {   
   1.459         const C&    operator * () const
   1.460         {            
   1.461             OVR_ASSERT(Index >= 0 && Index <= (SPInt)pHash->pTable->SizeMask);
   1.462             return pHash->E(Index).Value;
   1.463         }
   1.464 
   1.465         const C*    operator -> () const
   1.466         {
   1.467             OVR_ASSERT(Index >= 0 && Index <= (SPInt)pHash->pTable->SizeMask);
   1.468             return &pHash->E(Index).Value;
   1.469         }
   1.470 
   1.471         void    operator ++ ()
   1.472         {
   1.473             // Find next non-empty Entry.
   1.474             if (Index <= (SPInt)pHash->pTable->SizeMask)
   1.475             {
   1.476                 Index++;
   1.477                 while ((UPInt)Index <= pHash->pTable->SizeMask &&
   1.478                     pHash->E(Index).IsEmpty())
   1.479                 {
   1.480                     Index++;
   1.481                 }
   1.482             }
   1.483         }
   1.484 
   1.485         bool    operator == (const ConstIterator& it) const
   1.486         {
   1.487             if (IsEnd() && it.IsEnd())
   1.488             {
   1.489                 return true;
   1.490             }
   1.491             else
   1.492             {
   1.493                 return (pHash == it.pHash) && (Index == it.Index);
   1.494             }
   1.495         }
   1.496 
   1.497         bool    operator != (const ConstIterator& it) const
   1.498         {
   1.499             return ! (*this == it);
   1.500         }
   1.501 
   1.502 
   1.503         bool    IsEnd() const
   1.504         {
   1.505             return (pHash == NULL) || 
   1.506                 (pHash->pTable == NULL) || 
   1.507                 (Index > (SPInt)pHash->pTable->SizeMask);
   1.508         }
   1.509 
   1.510         ConstIterator()
   1.511             : pHash(NULL), Index(0)
   1.512         { }
   1.513 
   1.514     public:
   1.515         // Constructor was intentionally made public to allow create
   1.516         // iterator with arbitrary index.
   1.517         ConstIterator(const SelfType* h, SPInt index)
   1.518             : pHash(h), Index(index)
   1.519         { }
   1.520 
   1.521         const SelfType* GetContainer() const
   1.522         {
   1.523             return pHash;
   1.524         }
   1.525         SPInt GetIndex() const
   1.526         {
   1.527             return Index;
   1.528         }
   1.529 
   1.530     protected:
   1.531         friend class HashSetBase<C, HashF, AltHashF, Allocator, Entry>;
   1.532 
   1.533         const SelfType* pHash;
   1.534         SPInt           Index;
   1.535     };
   1.536 
   1.537     friend struct ConstIterator;
   1.538 
   1.539 
   1.540     // Non-const Iterator; Get most of it from ConstIterator.
   1.541     struct Iterator : public ConstIterator
   1.542     {      
   1.543         // Allow non-const access to entries.
   1.544         C&  operator*() const
   1.545         {            
   1.546             OVR_ASSERT(ConstIterator::Index >= 0 && ConstIterator::Index <= (SPInt)ConstIterator::pHash->pTable->SizeMask);
   1.547             return const_cast<SelfType*>(ConstIterator::pHash)->E(ConstIterator::Index).Value;
   1.548         }    
   1.549 
   1.550         C*  operator->() const 
   1.551         {
   1.552             return &(operator*());
   1.553         }
   1.554 
   1.555         Iterator()
   1.556             : ConstIterator(NULL, 0)
   1.557         { }
   1.558 
   1.559         // Removes current element from Hash
   1.560         void Remove()
   1.561         {
   1.562             RemoveAlt(operator*());
   1.563         }
   1.564 
   1.565         template <class K>
   1.566         void RemoveAlt(const K& key)
   1.567         {
   1.568             SelfType*   phash = const_cast<SelfType*>(ConstIterator::pHash);
   1.569             //Entry*      ee = &phash->E(ConstIterator::Index);
   1.570             //const C&    key = ee->Value;
   1.571 
   1.572             UPInt       hashValue = AltHashF()(key);
   1.573             SPInt       index     = hashValue & phash->pTable->SizeMask;
   1.574 
   1.575             Entry*      e = &phash->E(index);
   1.576 
   1.577             // If empty node or occupied by collider, we have nothing to remove.
   1.578             if (e->IsEmpty() || (e->GetCachedHash(phash->pTable->SizeMask) != (UPInt)index))
   1.579                 return;        
   1.580 
   1.581             // Save index
   1.582             SPInt   naturalIndex = index;
   1.583             SPInt   prevIndex    = -1;
   1.584 
   1.585             while ((e->GetCachedHash(phash->pTable->SizeMask) != (UPInt)naturalIndex) || !(e->Value == key))
   1.586             {
   1.587                 // Keep looking through the chain.
   1.588                 prevIndex   = index;
   1.589                 index       = e->NextInChain;
   1.590                 if (index == -1)
   1.591                     return; // End of chain, item not found
   1.592                 e = &phash->E(index);
   1.593             }
   1.594 
   1.595             if (index == (SPInt)ConstIterator::Index)
   1.596             {
   1.597                 // Found it - our item is at index
   1.598                 if (naturalIndex == index)
   1.599                 {
   1.600                     // If we have a follower, move it to us
   1.601                     if (!e->IsEndOfChain())
   1.602                     {               
   1.603                         Entry*  enext = &phash->E(e->NextInChain);
   1.604                         e->Clear();
   1.605                         new (e) Entry(*enext);
   1.606                         // Point us to the follower's cell that will be cleared
   1.607                         e = enext;
   1.608                         --ConstIterator::Index;
   1.609                     }
   1.610                 }
   1.611                 else
   1.612                 {
   1.613                     // We are not at natural index, so deal with the prev items next index
   1.614                     phash->E(prevIndex).NextInChain = e->NextInChain;
   1.615                 }
   1.616 
   1.617                 // Clear us, of the follower cell that was moved.
   1.618                 e->Clear();
   1.619                 phash->pTable->EntryCount --;
   1.620             }
   1.621             else 
   1.622                 OVR_ASSERT(0); //?
   1.623         }
   1.624 
   1.625     private:
   1.626         friend class HashSetBase<C, HashF, AltHashF, Allocator, Entry>;
   1.627 
   1.628         Iterator(SelfType* h, SPInt i0)
   1.629             : ConstIterator(h, i0)
   1.630         { }
   1.631     };
   1.632 
   1.633     friend struct Iterator;
   1.634 
   1.635     Iterator    Begin()
   1.636     {
   1.637         if (pTable == 0)
   1.638             return Iterator(NULL, 0);
   1.639 
   1.640         // Scan till we hit the First valid Entry.
   1.641         UPInt  i0 = 0;
   1.642         while (i0 <= pTable->SizeMask && E(i0).IsEmpty())
   1.643         {
   1.644             i0++;
   1.645         }
   1.646         return Iterator(this, i0);
   1.647     }
   1.648     Iterator        End()           { return Iterator(NULL, 0); }
   1.649 
   1.650     ConstIterator   Begin() const   { return const_cast<SelfType*>(this)->Begin();     }
   1.651     ConstIterator   End() const     { return const_cast<SelfType*>(this)->End();   }
   1.652 
   1.653     template<class K>
   1.654     Iterator Find(const K& key)
   1.655     {
   1.656         SPInt index = findIndex(key);
   1.657         if (index >= 0)        
   1.658             return Iterator(this, index);        
   1.659         return Iterator(NULL, 0);
   1.660     }
   1.661 
   1.662     template<class K>
   1.663     Iterator FindAlt(const K& key)
   1.664     {
   1.665         SPInt index = findIndexAlt(key);
   1.666         if (index >= 0)        
   1.667             return Iterator(this, index);        
   1.668         return Iterator(NULL, 0);
   1.669     }
   1.670 
   1.671     template<class K>
   1.672     ConstIterator Find(const K& key) const       { return const_cast<SelfType*>(this)->Find(key); }
   1.673 
   1.674     template<class K>
   1.675     ConstIterator FindAlt(const K& key) const    { return const_cast<SelfType*>(this)->FindAlt(key); }
   1.676 
   1.677 private:
   1.678     // Find the index of the matching Entry.  If no match, then return -1.
   1.679     template<class K>
   1.680     SPInt findIndex(const K& key) const
   1.681     {
   1.682         if (pTable == NULL)
   1.683             return -1;
   1.684         UPInt hashValue = HashF()(key) & pTable->SizeMask;
   1.685         return findIndexCore(key, hashValue);
   1.686     }
   1.687 
   1.688     template<class K>
   1.689     SPInt findIndexAlt(const K& key) const
   1.690     {
   1.691         if (pTable == NULL)
   1.692             return -1;
   1.693         UPInt hashValue = AltHashF()(key) & pTable->SizeMask;
   1.694         return findIndexCore(key, hashValue);
   1.695     }
   1.696 
   1.697     // Find the index of the matching Entry.  If no match, then return -1.
   1.698     template<class K>
   1.699     SPInt findIndexCore(const K& key, UPInt hashValue) const
   1.700     {
   1.701         // Table must exist.
   1.702         OVR_ASSERT(pTable != 0);
   1.703         // Hash key must be 'and-ed' by the caller.
   1.704         OVR_ASSERT((hashValue & ~pTable->SizeMask) == 0);
   1.705 
   1.706         UPInt           index = hashValue;
   1.707         const Entry*    e     = &E(index);
   1.708 
   1.709         // If empty or occupied by a collider, not found.
   1.710         if (e->IsEmpty() || (e->GetCachedHash(pTable->SizeMask) != index))
   1.711             return -1;
   1.712 
   1.713         while(1)
   1.714         {
   1.715             OVR_ASSERT(e->GetCachedHash(pTable->SizeMask) == hashValue);
   1.716 
   1.717             if (e->GetCachedHash(pTable->SizeMask) == hashValue && e->Value == key)
   1.718             {
   1.719                 // Found it.
   1.720                 return index;
   1.721             }
   1.722             // Values can not be equal at this point.
   1.723             // That would mean that the hash key for the same value differs.
   1.724             OVR_ASSERT(!(e->Value == key));
   1.725 
   1.726             // Keep looking through the chain.
   1.727             index = e->NextInChain;
   1.728             if (index == (UPInt)-1)
   1.729                 break; // end of chain
   1.730 
   1.731             e = &E(index);
   1.732             OVR_ASSERT(!e->IsEmpty());
   1.733         }
   1.734         return -1;
   1.735     }
   1.736 
   1.737 
   1.738     // Add a new value to the HashSet table, under the specified key.
   1.739     template<class CRef>
   1.740     void add(const CRef& key, UPInt hashValue)
   1.741     {
   1.742         CheckExpand();
   1.743         hashValue &= pTable->SizeMask;
   1.744 
   1.745         pTable->EntryCount++;
   1.746 
   1.747         SPInt   index        = hashValue;
   1.748         Entry*  naturalEntry = &(E(index));
   1.749 
   1.750         if (naturalEntry->IsEmpty())
   1.751         {
   1.752             // Put the new Entry in.
   1.753             new (naturalEntry) Entry(key, -1);
   1.754         }
   1.755         else
   1.756         {
   1.757             // Find a blank spot.
   1.758             SPInt blankIndex = index;
   1.759             do {
   1.760                 blankIndex = (blankIndex + 1) & pTable->SizeMask;
   1.761             } while(!E(blankIndex).IsEmpty());
   1.762 
   1.763             Entry*  blankEntry = &E(blankIndex);
   1.764 
   1.765             if (naturalEntry->GetCachedHash(pTable->SizeMask) == (UPInt)index)
   1.766             {
   1.767                 // Collision.  Link into this chain.
   1.768 
   1.769                 // Move existing list head.
   1.770                 new (blankEntry) Entry(*naturalEntry);    // placement new, copy ctor
   1.771 
   1.772                 // Put the new info in the natural Entry.
   1.773                 naturalEntry->Value       = key;
   1.774                 naturalEntry->NextInChain = blankIndex;
   1.775             }
   1.776             else
   1.777             {
   1.778                 // Existing Entry does not naturally
   1.779                 // belong in this slot.  Existing
   1.780                 // Entry must be moved.
   1.781 
   1.782                 // Find natural location of collided element (i.e. root of chain)
   1.783                 SPInt collidedIndex = naturalEntry->GetCachedHash(pTable->SizeMask);
   1.784                 OVR_ASSERT(collidedIndex >= 0 && collidedIndex <= (SPInt)pTable->SizeMask);
   1.785                 for (;;)
   1.786                 {
   1.787                     Entry*  e = &E(collidedIndex);
   1.788                     if (e->NextInChain == index)
   1.789                     {
   1.790                         // Here's where we need to splice.
   1.791                         new (blankEntry) Entry(*naturalEntry);
   1.792                         e->NextInChain = blankIndex;
   1.793                         break;
   1.794                     }
   1.795                     collidedIndex = e->NextInChain;
   1.796                     OVR_ASSERT(collidedIndex >= 0 && collidedIndex <= (SPInt)pTable->SizeMask);
   1.797                 }
   1.798 
   1.799                 // Put the new data in the natural Entry.
   1.800                 naturalEntry->Value       = key;
   1.801                 naturalEntry->NextInChain = -1;                
   1.802             }            
   1.803         }
   1.804 
   1.805         // Record hash value: has effect only if cached node is used.
   1.806         naturalEntry->SetCachedHash(hashValue);
   1.807     }
   1.808 
   1.809     // Index access helpers.
   1.810     Entry& E(UPInt index)
   1.811     {
   1.812         // Must have pTable and access needs to be within bounds.
   1.813         OVR_ASSERT(index <= pTable->SizeMask);
   1.814         return *(((Entry*) (pTable + 1)) + index);
   1.815     }
   1.816     const Entry& E(UPInt index) const
   1.817     {        
   1.818         OVR_ASSERT(index <= pTable->SizeMask);
   1.819         return *(((Entry*) (pTable + 1)) + index);
   1.820     }
   1.821 
   1.822 
   1.823     // Resize the HashSet table to the given size (Rehash the
   1.824     // contents of the current table).  The arg is the number of
   1.825     // HashSet table entries, not the number of elements we should
   1.826     // actually contain (which will be less than this).
   1.827     void    setRawCapacity(UPInt newSize)    
   1.828     {
   1.829         if (newSize == 0)
   1.830         {
   1.831             // Special case.
   1.832             Clear();
   1.833             return;
   1.834         }
   1.835 
   1.836         // Minimum size; don't incur rehashing cost when expanding
   1.837         // very small tables. Not that we perform this check before 
   1.838         // 'log2f' call to avoid fp exception with newSize == 1.
   1.839         if (newSize < HashMinSize)        
   1.840             newSize = HashMinSize;       
   1.841         else
   1.842         {
   1.843             // Force newSize to be a power of two.
   1.844             int bits = Alg::UpperBit(newSize-1) + 1; // Chop( Log2f((float)(newSize-1)) + 1);
   1.845             OVR_ASSERT((UPInt(1) << bits) >= newSize);
   1.846             newSize = UPInt(1) << bits;
   1.847         }
   1.848 
   1.849         SelfType  newHash;
   1.850         newHash.pTable = (TableType*)
   1.851             Allocator::Alloc(                
   1.852                 sizeof(TableType) + sizeof(Entry) * newSize);
   1.853         // Need to do something on alloc failure!
   1.854         OVR_ASSERT(newHash.pTable);
   1.855 
   1.856         newHash.pTable->EntryCount = 0;
   1.857         newHash.pTable->SizeMask = newSize - 1;
   1.858         UPInt i, n;
   1.859 
   1.860         // Mark all entries as empty.
   1.861         for (i = 0; i < newSize; i++)
   1.862             newHash.E(i).NextInChain = -2;
   1.863 
   1.864         // Copy stuff to newHash
   1.865         if (pTable)
   1.866         {            
   1.867             for (i = 0, n = pTable->SizeMask; i <= n; i++)
   1.868             {
   1.869                 Entry*  e = &E(i);
   1.870                 if (e->IsEmpty() == false)
   1.871                 {
   1.872                     // Insert old Entry into new HashSet.
   1.873                     newHash.Add(e->Value);
   1.874                     // placement delete of old element
   1.875                     e->Clear();
   1.876                 }
   1.877             }
   1.878 
   1.879             // Delete our old data buffer.
   1.880             Allocator::Free(pTable);
   1.881         }
   1.882 
   1.883         // Steal newHash's data.
   1.884         pTable = newHash.pTable;
   1.885         newHash.pTable = NULL;
   1.886     }
   1.887 
   1.888     struct TableType
   1.889     {
   1.890         UPInt EntryCount;
   1.891         UPInt SizeMask;
   1.892         // Entry array follows this structure
   1.893         // in memory.
   1.894     };
   1.895     TableType*  pTable;
   1.896 };
   1.897 
   1.898 
   1.899 
   1.900 //-----------------------------------------------------------------------------------
   1.901 template<class C, class HashF = FixedSizeHash<C>,
   1.902          class AltHashF = HashF, 
   1.903          class Allocator = ContainerAllocator<C>,
   1.904          class Entry = HashsetCachedEntry<C, HashF> >
   1.905 class HashSet : public HashSetBase<C, HashF, AltHashF, Allocator, Entry>
   1.906 {
   1.907 public:
   1.908     typedef HashSetBase<C, HashF, AltHashF, Allocator, Entry> BaseType;
   1.909     typedef HashSet<C, HashF, AltHashF, Allocator, Entry>     SelfType;
   1.910 
   1.911     HashSet()                                      {   }
   1.912     HashSet(int sizeHint) : BaseType(sizeHint)     {   }
   1.913     HashSet(const SelfType& src) : BaseType(src)   {   }
   1.914     ~HashSet()                                     {   }
   1.915 
   1.916     void operator = (const SelfType& src)   { BaseType::Assign(src); }
   1.917 
   1.918     // Set a new or existing value under the key, to the value.
   1.919     // Pass a different class of 'key' so that assignment reference object
   1.920     // can be passed instead of the actual object.
   1.921     template<class CRef>
   1.922     void Set(const CRef& key)
   1.923     {
   1.924         BaseType::Set(key);
   1.925     }
   1.926 
   1.927     template<class CRef>
   1.928     inline void Add(const CRef& key)
   1.929     {
   1.930         BaseType::Add(key);
   1.931     }
   1.932 
   1.933     // Hint the bucket count to >= n.
   1.934     void Resize(UPInt n)    
   1.935     {
   1.936         BaseType::SetCapacity(n);
   1.937     }
   1.938 
   1.939     // Size the HashSet so that it can comfortably contain the given
   1.940     // number of elements.  If the HashSet already contains more
   1.941     // elements than newSize, then this may be a no-op.
   1.942     void SetCapacity(UPInt newSize)
   1.943     {
   1.944         BaseType::SetCapacity(newSize);
   1.945     }
   1.946 
   1.947 };
   1.948 
   1.949 // HashSet with uncached hash code; declared for convenience.
   1.950 template<class C, class HashF = FixedSizeHash<C>,
   1.951                   class AltHashF = HashF,
   1.952                   class Allocator = ContainerAllocator<C> >
   1.953 class HashSetUncached : public HashSet<C, HashF, AltHashF, Allocator, HashsetEntry<C, HashF> >
   1.954 {
   1.955 public:
   1.956     
   1.957     typedef HashSetUncached<C, HashF, AltHashF, Allocator>                  SelfType;
   1.958     typedef HashSet<C, HashF, AltHashF, Allocator, HashsetEntry<C, HashF> > BaseType;
   1.959 
   1.960     // Delegated constructors.
   1.961     HashSetUncached()                                        { }
   1.962     HashSetUncached(int sizeHint) : BaseType(sizeHint)       { }
   1.963     HashSetUncached(const SelfType& src) : BaseType(src)     { }
   1.964     ~HashSetUncached()                                       { }
   1.965     
   1.966     void    operator = (const SelfType& src)
   1.967     {
   1.968         BaseType::operator = (src);
   1.969     }
   1.970 };
   1.971 
   1.972 
   1.973 //-----------------------------------------------------------------------------------
   1.974 // ***** Hash hash table implementation
   1.975 
   1.976 // Node for Hash - necessary so that Hash can delegate its implementation
   1.977 // to HashSet.
   1.978 template<class C, class U, class HashF>
   1.979 struct HashNode
   1.980 {
   1.981     typedef HashNode<C, U, HashF>   SelfType;
   1.982     typedef C                       FirstType;
   1.983     typedef U                       SecondType;
   1.984 
   1.985     C   First;
   1.986     U   Second;
   1.987 
   1.988     // NodeRef is used to allow passing of elements into HashSet
   1.989     // without using a temporary object.
   1.990     struct NodeRef
   1.991     {
   1.992         const C*   pFirst;
   1.993         const U*   pSecond;
   1.994 
   1.995         NodeRef(const C& f, const U& s) : pFirst(&f), pSecond(&s) { }
   1.996         NodeRef(const NodeRef& src)     : pFirst(src.pFirst), pSecond(src.pSecond) { }
   1.997 
   1.998         // Enable computation of ghash_node_hashf.
   1.999         inline UPInt GetHash() const            { return HashF()(*pFirst); } 
  1.1000         // Necessary conversion to allow HashNode::operator == to work.
  1.1001         operator const C& () const              { return *pFirst; }
  1.1002     };
  1.1003 
  1.1004     // Note: No default constructor is necessary.
  1.1005      HashNode(const HashNode& src) : First(src.First), Second(src.Second)    { }
  1.1006      HashNode(const NodeRef& src) : First(*src.pFirst), Second(*src.pSecond)  { }
  1.1007     void operator = (const NodeRef& src)  { First  = *src.pFirst; Second = *src.pSecond; }
  1.1008 
  1.1009     template<class K>
  1.1010     bool operator == (const K& src) const   { return (First == src); }
  1.1011 
  1.1012     template<class K>
  1.1013     static UPInt CalcHash(const K& data)   { return HashF()(data); }
  1.1014     inline UPInt GetHash() const           { return HashF()(First); }
  1.1015 
  1.1016     // Hash functors used with this node. A separate functor is used for alternative
  1.1017     // key lookup so that it does not need to access the '.First' element.    
  1.1018     struct NodeHashF
  1.1019     {    
  1.1020         template<class K>
  1.1021         UPInt operator()(const K& data) const { return data.GetHash(); } 
  1.1022     };    
  1.1023     struct NodeAltHashF
  1.1024     {
  1.1025         template<class K>
  1.1026         UPInt operator()(const K& data) const { return HashNode<C,U,HashF>::CalcHash(data); }
  1.1027     };
  1.1028 };
  1.1029 
  1.1030 
  1.1031 
  1.1032 // **** Extra hashset_entry types to allow NodeRef construction.
  1.1033 
  1.1034 // The big difference between the below types and the ones used in hash_set is that
  1.1035 // these allow initializing the node with 'typename C::NodeRef& keyRef', which
  1.1036 // is critical to avoid temporary node allocation on stack when using placement new.
  1.1037 
  1.1038 // Compact hash table Entry type that re-computes hash keys during hash traversal.
  1.1039 // Good to use if the hash function is cheap or the hash value is already cached in C.
  1.1040 template<class C, class HashF>
  1.1041 class HashsetNodeEntry
  1.1042 {
  1.1043 public:
  1.1044     // Internal chaining for collisions.
  1.1045     SPInt NextInChain;
  1.1046     C     Value;
  1.1047 
  1.1048     HashsetNodeEntry()
  1.1049         : NextInChain(-2) { }
  1.1050     HashsetNodeEntry(const HashsetNodeEntry& e)
  1.1051         : NextInChain(e.NextInChain), Value(e.Value) { }
  1.1052     HashsetNodeEntry(const C& key, SPInt next)
  1.1053         : NextInChain(next), Value(key) { }    
  1.1054     HashsetNodeEntry(const typename C::NodeRef& keyRef, SPInt next)
  1.1055         : NextInChain(next), Value(keyRef) { }
  1.1056 
  1.1057     bool    IsEmpty() const             { return NextInChain == -2;  }
  1.1058     bool    IsEndOfChain() const        { return NextInChain == -1;  }
  1.1059     UPInt   GetCachedHash(UPInt maskValue) const  { return HashF()(Value) & maskValue; }
  1.1060     void    SetCachedHash(UPInt hashValue)        { OVR_UNUSED(hashValue); }
  1.1061 
  1.1062     void    Clear()
  1.1063     {        
  1.1064         Value.~C(); // placement delete
  1.1065         NextInChain = -2;
  1.1066     }
  1.1067     // Free is only used from dtor of hash; Clear is used during regular operations:
  1.1068     // assignment, hash reallocations, value reassignments, so on.
  1.1069     void    Free() { Clear(); }
  1.1070 };
  1.1071 
  1.1072 // Hash table Entry type that caches the Entry hash value for nodes, so that it
  1.1073 // does not need to be re-computed during access.
  1.1074 template<class C, class HashF>
  1.1075 class HashsetCachedNodeEntry
  1.1076 {
  1.1077 public:
  1.1078     // Internal chaining for collisions.
  1.1079     SPInt NextInChain;
  1.1080     UPInt HashValue;
  1.1081     C     Value;
  1.1082 
  1.1083     HashsetCachedNodeEntry()
  1.1084         : NextInChain(-2) { }
  1.1085     HashsetCachedNodeEntry(const HashsetCachedNodeEntry& e)
  1.1086         : NextInChain(e.NextInChain), HashValue(e.HashValue), Value(e.Value) { }
  1.1087     HashsetCachedNodeEntry(const C& key, SPInt next)
  1.1088         : NextInChain(next), Value(key) { }
  1.1089     HashsetCachedNodeEntry(const typename C::NodeRef& keyRef, SPInt next)
  1.1090         : NextInChain(next), Value(keyRef) { }
  1.1091 
  1.1092     bool    IsEmpty() const            { return NextInChain == -2;  }
  1.1093     bool    IsEndOfChain() const       { return NextInChain == -1;  }
  1.1094     UPInt   GetCachedHash(UPInt maskValue) const  { OVR_UNUSED(maskValue); return HashValue; }
  1.1095     void    SetCachedHash(UPInt hashValue)        { HashValue = hashValue; }
  1.1096 
  1.1097     void    Clear()
  1.1098     {
  1.1099         Value.~C();
  1.1100         NextInChain = -2;
  1.1101     }
  1.1102     // Free is only used from dtor of hash; Clear is used during regular operations:
  1.1103     // assignment, hash reallocations, value reassignments, so on.
  1.1104     void    Free() { Clear(); }
  1.1105 };
  1.1106 
  1.1107 
  1.1108 //-----------------------------------------------------------------------------------
  1.1109 template<class C, class U,
  1.1110          class HashF = FixedSizeHash<C>,
  1.1111          class Allocator = ContainerAllocator<C>,
  1.1112          class HashNode = OVR::HashNode<C,U,HashF>,
  1.1113          class Entry = HashsetCachedNodeEntry<HashNode, typename HashNode::NodeHashF>,
  1.1114          class Container =  HashSet<HashNode, typename HashNode::NodeHashF,
  1.1115              typename HashNode::NodeAltHashF, Allocator,
  1.1116              Entry> >
  1.1117 class Hash
  1.1118 {
  1.1119 public:
  1.1120     OVR_MEMORY_REDEFINE_NEW(Hash)
  1.1121 
  1.1122     // Types used for hash_set.
  1.1123     typedef U                                                           ValueType;
  1.1124     typedef Hash<C, U, HashF, Allocator, HashNode, Entry, Container>    SelfType;
  1.1125 
  1.1126     // Actual hash table itself, implemented as hash_set.
  1.1127     Container   mHash;
  1.1128 
  1.1129 public:
  1.1130     Hash()     {  }
  1.1131     Hash(int sizeHint) : mHash(sizeHint)                        { }
  1.1132     Hash(const SelfType& src) : mHash(src.mHash)                { }
  1.1133     ~Hash()                                                     { }
  1.1134 
  1.1135     void    operator = (const SelfType& src)    { mHash = src.mHash; }
  1.1136 
  1.1137     // Remove all entries from the Hash table.
  1.1138     inline void    Clear() { mHash.Clear(); }
  1.1139     // Returns true if the Hash is empty.
  1.1140     inline bool    IsEmpty() const { return mHash.IsEmpty(); }
  1.1141 
  1.1142     // Access (set).
  1.1143     inline void    Set(const C& key, const U& value)
  1.1144     {
  1.1145         typename HashNode::NodeRef e(key, value);
  1.1146         mHash.Set(e);
  1.1147     }
  1.1148     inline void    Add(const C& key, const U& value)
  1.1149     {
  1.1150         typename HashNode::NodeRef e(key, value);
  1.1151         mHash.Add(e);
  1.1152     }
  1.1153 
  1.1154     // Removes an element by clearing its Entry.
  1.1155     inline void     Remove(const C& key)
  1.1156     {   
  1.1157         mHash.RemoveAlt(key);
  1.1158     }
  1.1159     template<class K>
  1.1160     inline void     RemoveAlt(const K& key)
  1.1161     {   
  1.1162         mHash.RemoveAlt(key);
  1.1163     }
  1.1164 
  1.1165     // Retrieve the value under the given key.    
  1.1166     //  - If there's no value under the key, then return false and leave *pvalue alone.
  1.1167     //  - If there is a value, return true, and Set *Pvalue to the Entry's value.
  1.1168     //  - If value == NULL, return true or false according to the presence of the key.    
  1.1169     bool    Get(const C& key, U* pvalue) const   
  1.1170     {
  1.1171         const HashNode* p = mHash.GetAlt(key);
  1.1172         if (p)
  1.1173         {
  1.1174             if (pvalue)
  1.1175                 *pvalue = p->Second;
  1.1176             return true;
  1.1177         }
  1.1178         return false;
  1.1179     }
  1.1180 
  1.1181     template<class K>
  1.1182     bool    GetAlt(const K& key, U* pvalue) const   
  1.1183     {
  1.1184         const HashNode* p = mHash.GetAlt(key);
  1.1185         if (p)
  1.1186         {
  1.1187             if (pvalue)
  1.1188                 *pvalue = p->Second;
  1.1189             return true;
  1.1190         }
  1.1191         return false;
  1.1192     }
  1.1193 
  1.1194     // Retrieve the pointer to a value under the given key.    
  1.1195     //  - If there's no value under the key, then return NULL.    
  1.1196     //  - If there is a value, return the pointer.    
  1.1197     inline U*  Get(const C& key)
  1.1198     {
  1.1199         HashNode* p = mHash.GetAlt(key);
  1.1200         return p ? &p->Second : 0;
  1.1201     }
  1.1202     inline const U* Get(const C& key) const
  1.1203     {
  1.1204         const HashNode* p = mHash.GetAlt(key);
  1.1205         return p ? &p->Second : 0;
  1.1206     }
  1.1207 
  1.1208     template<class K>
  1.1209     inline U*  GetAlt(const K& key)
  1.1210     {
  1.1211         HashNode* p = mHash.GetAlt(key);
  1.1212         return p ? &p->Second : 0;
  1.1213     }
  1.1214     template<class K>
  1.1215     inline const U* GetAlt(const K& key) const
  1.1216     {
  1.1217         const HashNode* p = mHash.GetAlt(key);
  1.1218         return p ? &p->Second : 0;
  1.1219     }
  1.1220 
  1.1221     // Sizing methods - delegate to Hash.
  1.1222     inline UPInt   GetSize() const              { return mHash.GetSize(); }    
  1.1223     inline void    Resize(UPInt n)              { mHash.Resize(n); }
  1.1224     inline void    SetCapacity(UPInt newSize)   { mHash.SetCapacity(newSize); }
  1.1225 
  1.1226     // Iterator API, like STL.
  1.1227     typedef typename Container::ConstIterator   ConstIterator;
  1.1228     typedef typename Container::Iterator        Iterator;
  1.1229 
  1.1230     inline Iterator        Begin()              { return mHash.Begin(); }
  1.1231     inline Iterator        End()                { return mHash.End(); }
  1.1232     inline ConstIterator   Begin() const        { return mHash.Begin(); }
  1.1233     inline ConstIterator   End() const          { return mHash.End();   }
  1.1234 
  1.1235     Iterator        Find(const C& key)          { return mHash.FindAlt(key);  }
  1.1236     ConstIterator   Find(const C& key) const    { return mHash.FindAlt(key);  }
  1.1237 
  1.1238     template<class K>
  1.1239     Iterator        FindAlt(const K& key)       { return mHash.FindAlt(key);  }
  1.1240     template<class K>
  1.1241     ConstIterator   FindAlt(const K& key) const { return mHash.FindAlt(key);  }
  1.1242 };
  1.1243 
  1.1244 
  1.1245 
  1.1246 // Hash with uncached hash code; declared for convenience.
  1.1247 template<class C, class U, class HashF = FixedSizeHash<C>, class Allocator = ContainerAllocator<C> >
  1.1248 class HashUncached
  1.1249     : public Hash<C, U, HashF, Allocator, HashNode<C,U,HashF>,
  1.1250                    HashsetNodeEntry<HashNode<C,U,HashF>, typename HashNode<C,U,HashF>::NodeHashF> >
  1.1251 {
  1.1252 public:
  1.1253     typedef HashUncached<C, U, HashF, Allocator>                SelfType;
  1.1254     typedef Hash<C, U, HashF, Allocator, HashNode<C,U,HashF>,
  1.1255                  HashsetNodeEntry<HashNode<C,U,HashF>,
  1.1256                  typename HashNode<C,U,HashF>::NodeHashF> >     BaseType;
  1.1257 
  1.1258     // Delegated constructors.
  1.1259     HashUncached()                                        { }
  1.1260     HashUncached(int sizeHint) : BaseType(sizeHint)       { }
  1.1261     HashUncached(const SelfType& src) : BaseType(src)     { }
  1.1262     ~HashUncached()                                       { }
  1.1263     void operator = (const SelfType& src)                 { BaseType::operator = (src); }
  1.1264 };
  1.1265 
  1.1266 
  1.1267 
  1.1268 // And identity hash in which keys serve as hash value. Can be uncached,
  1.1269 // since hash computation is assumed cheap.
  1.1270 template<class C, class U, class Allocator = ContainerAllocator<C>, class HashF = IdentityHash<C> >
  1.1271 class HashIdentity
  1.1272     : public HashUncached<C, U, HashF, Allocator>
  1.1273 {
  1.1274 public:
  1.1275     typedef HashIdentity<C, U, Allocator, HashF> SelfType;
  1.1276     typedef HashUncached<C, U, HashF, Allocator> BaseType;
  1.1277 
  1.1278     // Delegated constructors.
  1.1279     HashIdentity()                                        { }
  1.1280     HashIdentity(int sizeHint) : BaseType(sizeHint)       { }
  1.1281     HashIdentity(const SelfType& src) : BaseType(src)     { }
  1.1282     ~HashIdentity()                                       { }
  1.1283     void operator = (const SelfType& src)                 { BaseType::operator = (src); }
  1.1284 };
  1.1285 
  1.1286 
  1.1287 } // OVR
  1.1288 
  1.1289 
  1.1290 #ifdef OVR_DEFINE_NEW
  1.1291 #define new OVR_DEFINE_NEW
  1.1292 #endif
  1.1293 
  1.1294 #endif
  1.1295 \ No newline at end of file
  1.1296 +/************************************************************************************
  1.1297 +
  1.1298 +PublicHeader:   None
  1.1299 +Filename    :   OVR_Hash.h
  1.1300 +Content     :   Template hash-table/set implementation
  1.1301 +Created     :   September 19, 2012
  1.1302 +Notes       : 
  1.1303 +
  1.1304 +Copyright   :   Copyright 2012 Oculus VR, Inc. All Rights reserved.
  1.1305 +
  1.1306 +Use of this software is subject to the terms of the Oculus license
  1.1307 +agreement provided at the time of installation or download, or which
  1.1308 +otherwise accompanies this software in either electronic or hard copy form.
  1.1309 +
  1.1310 +************************************************************************************/
  1.1311 +
  1.1312 +#ifndef OVR_Hash_h
  1.1313 +#define OVR_Hash_h
  1.1314 +
  1.1315 +#include "OVR_ContainerAllocator.h"
  1.1316 +#include "OVR_Alg.h"
  1.1317 +
  1.1318 +// 'new' operator is redefined/used in this file.
  1.1319 +#undef new
  1.1320 +
  1.1321 +namespace OVR {
  1.1322 +
  1.1323 +//-----------------------------------------------------------------------------------
  1.1324 +// ***** Hash Table Implementation
  1.1325 +
  1.1326 +// HastSet and Hash.
  1.1327 +//
  1.1328 +// Hash table, linear probing, internal chaining.  One  interesting/nice thing
  1.1329 +// about this implementation is that the table itself is a flat chunk of memory
  1.1330 +// containing no pointers, only relative indices. If the key and value types
  1.1331 +// of the Hash contain no pointers, then the Hash can be serialized using raw IO.
  1.1332 +//
  1.1333 +// Never shrinks, unless you explicitly Clear() it.  Expands on
  1.1334 +// demand, though.  For best results, if you know roughly how big your
  1.1335 +// table will be, default it to that size when you create it.
  1.1336 +//
  1.1337 +// Key usability feature:
  1.1338 +//
  1.1339 +//   1. Allows node hash values to either be cached or not.
  1.1340 +//
  1.1341 +//   2. Allows for alternative keys with methods such as GetAlt(). Handy
  1.1342 +//      if you need to search nodes by their components; no need to create
  1.1343 +//      temporary nodes.
  1.1344 +//
  1.1345 +
  1.1346 +
  1.1347 +// *** Hash functors:
  1.1348 +//
  1.1349 +//  IdentityHash  - use when the key is already a good hash
  1.1350 +//  HFixedSizeHash - general hash based on object's in-memory representation.
  1.1351 +
  1.1352 +
  1.1353 +// Hash is just the input value; can use this for integer-indexed hash tables.
  1.1354 +template<class C>
  1.1355 +class IdentityHash
  1.1356 +{
  1.1357 +public:
  1.1358 +    UPInt operator()(const C& data) const
  1.1359 +    { return (UPInt) data; }
  1.1360 +};
  1.1361 +
  1.1362 +// Computes a hash of an object's representation.
  1.1363 +template<class C>
  1.1364 +class FixedSizeHash
  1.1365 +{
  1.1366 +public:
  1.1367 +    // Alternative: "sdbm" hash function, suggested at same web page
  1.1368 +    // above, http::/www.cs.yorku.ca/~oz/hash.html
  1.1369 +    // This is somewhat slower then Bernstein, but it works way better than the above
  1.1370 +    // hash function for hashing large numbers of 32-bit ints.
  1.1371 +    static OVR_FORCE_INLINE UPInt SDBM_Hash(const void* data_in, UPInt size, UPInt seed = 5381)     
  1.1372 +    {
  1.1373 +        const UByte* data = (const UByte*) data_in;
  1.1374 +        UPInt        h = seed;
  1.1375 +        while (size > 0)
  1.1376 +        {
  1.1377 +            size--;
  1.1378 +            h = (h << 16) + (h << 6) - h + (UPInt)data[size];
  1.1379 +        }   
  1.1380 +        return h;
  1.1381 +    }
  1.1382 +
  1.1383 +    UPInt operator()(const C& data) const
  1.1384 +    {
  1.1385 +        unsigned char*  p = (unsigned char*) &data;
  1.1386 +        int size = sizeof(C);
  1.1387 +
  1.1388 +        return SDBM_Hash(p, size);
  1.1389 +    }
  1.1390 +};
  1.1391 +
  1.1392 +
  1.1393 +
  1.1394 +// *** HashsetEntry Entry types. 
  1.1395 +
  1.1396 +// Compact hash table Entry type that re-computes hash keys during hash traversal.
  1.1397 +// Good to use if the hash function is cheap or the hash value is already cached in C.
  1.1398 +template<class C, class HashF>
  1.1399 +class HashsetEntry
  1.1400 +{
  1.1401 +public:
  1.1402 +    // Internal chaining for collisions.
  1.1403 +    SPInt       NextInChain;
  1.1404 +    C           Value;
  1.1405 +
  1.1406 +    HashsetEntry()
  1.1407 +        : NextInChain(-2) { }
  1.1408 +    HashsetEntry(const HashsetEntry& e)
  1.1409 +        : NextInChain(e.NextInChain), Value(e.Value) { }
  1.1410 +    HashsetEntry(const C& key, SPInt next)
  1.1411 +        : NextInChain(next), Value(key) { }
  1.1412 +
  1.1413 +    bool    IsEmpty() const          { return NextInChain == -2;  }
  1.1414 +    bool    IsEndOfChain() const     { return NextInChain == -1;  }
  1.1415 +
  1.1416 +    // Cached hash value access - can be optimized bu storing hash locally.
  1.1417 +    // Mask value only needs to be used if SetCachedHash is not implemented.
  1.1418 +    UPInt   GetCachedHash(UPInt maskValue) const  { return HashF()(Value) & maskValue; }
  1.1419 +    void    SetCachedHash(UPInt)                  {}
  1.1420 +
  1.1421 +    void    Clear()
  1.1422 +    {        
  1.1423 +        Value.~C(); // placement delete
  1.1424 +        NextInChain = -2;
  1.1425 +    }
  1.1426 +    // Free is only used from dtor of hash; Clear is used during regular operations:
  1.1427 +    // assignment, hash reallocations, value reassignments, so on.
  1.1428 +    void    Free() { Clear(); }
  1.1429 +};
  1.1430 +
  1.1431 +// Hash table Entry type that caches the Entry hash value for nodes, so that it
  1.1432 +// does not need to be re-computed during access.
  1.1433 +template<class C, class HashF>
  1.1434 +class HashsetCachedEntry
  1.1435 +{
  1.1436 +public:
  1.1437 +    // Internal chaining for collisions.
  1.1438 +    SPInt       NextInChain;
  1.1439 +    UPInt       HashValue;
  1.1440 +    C           Value;
  1.1441 +
  1.1442 +    HashsetCachedEntry()
  1.1443 +        : NextInChain(-2) { }
  1.1444 +    HashsetCachedEntry(const HashsetCachedEntry& e)
  1.1445 +        : NextInChain(e.NextInChain), HashValue(e.HashValue), Value(e.Value) { }
  1.1446 +    HashsetCachedEntry(const C& key, SPInt next)
  1.1447 +        : NextInChain(next), Value(key) { }
  1.1448 +
  1.1449 +    bool    IsEmpty() const          { return NextInChain == -2;  }
  1.1450 +    bool    IsEndOfChain() const     { return NextInChain == -1;  }
  1.1451 +
  1.1452 +    // Cached hash value access - can be optimized bu storing hash locally.
  1.1453 +    // Mask value only needs to be used if SetCachedHash is not implemented.
  1.1454 +    UPInt   GetCachedHash(UPInt maskValue) const  { OVR_UNUSED(maskValue); return HashValue; }
  1.1455 +    void    SetCachedHash(UPInt hashValue)        { HashValue = hashValue; }
  1.1456 +
  1.1457 +    void    Clear()
  1.1458 +    {
  1.1459 +        Value.~C();
  1.1460 +        NextInChain = -2;
  1.1461 +    }
  1.1462 +    // Free is only used from dtor of hash; Clear is used during regular operations:
  1.1463 +    // assignment, hash reallocations, value reassignments, so on.
  1.1464 +    void    Free() { Clear(); }
  1.1465 +};
  1.1466 +
  1.1467 +
  1.1468 +//-----------------------------------------------------------------------------------
  1.1469 +// *** HashSet implementation - relies on either cached or regular entries.
  1.1470 +//
  1.1471 +// Use: Entry = HashsetCachedEntry<C, HashF> if hashes are expensive to
  1.1472 +//              compute and thus need caching in entries.
  1.1473 +//      Entry = HashsetEntry<C, HashF> if hashes are already externally cached.
  1.1474 +//
  1.1475 +template<class C, class HashF = FixedSizeHash<C>,
  1.1476 +         class AltHashF = HashF, 
  1.1477 +         class Allocator = ContainerAllocator<C>,
  1.1478 +         class Entry = HashsetCachedEntry<C, HashF> >
  1.1479 +class HashSetBase
  1.1480 +{
  1.1481 +    enum { HashMinSize = 8 };
  1.1482 +
  1.1483 +public:
  1.1484 +    OVR_MEMORY_REDEFINE_NEW(HashSetBase)
  1.1485 +
  1.1486 +    typedef HashSetBase<C, HashF, AltHashF, Allocator, Entry>    SelfType;
  1.1487 +
  1.1488 +    HashSetBase() : pTable(NULL)                       {   }
  1.1489 +    HashSetBase(int sizeHint) : pTable(NULL)           { SetCapacity(this, sizeHint);  }
  1.1490 +    HashSetBase(const SelfType& src) : pTable(NULL)    { Assign(this, src); }
  1.1491 +
  1.1492 +    ~HashSetBase()                                     
  1.1493 +    { 
  1.1494 +        if (pTable)
  1.1495 +        {
  1.1496 +            // Delete the entries.
  1.1497 +            for (UPInt i = 0, n = pTable->SizeMask; i <= n; i++)
  1.1498 +            {
  1.1499 +                Entry*  e = &E(i);
  1.1500 +                if (!e->IsEmpty())             
  1.1501 +                    e->Free();
  1.1502 +            }            
  1.1503 +
  1.1504 +            Allocator::Free(pTable);
  1.1505 +            pTable = NULL;
  1.1506 +        }
  1.1507 +    }
  1.1508 +
  1.1509 +
  1.1510 +    void Assign(const SelfType& src)
  1.1511 +    {
  1.1512 +        Clear();
  1.1513 +        if (src.IsEmpty() == false)
  1.1514 +        {
  1.1515 +            SetCapacity(src.GetSize());
  1.1516 +
  1.1517 +            for (ConstIterator it = src.Begin(); it != src.End(); ++it)
  1.1518 +            {
  1.1519 +                Add(*it);
  1.1520 +            }
  1.1521 +        }
  1.1522 +    }
  1.1523 +
  1.1524 +
  1.1525 +    // Remove all entries from the HashSet table.
  1.1526 +    void Clear() 
  1.1527 +    {
  1.1528 +        if (pTable)
  1.1529 +        {
  1.1530 +            // Delete the entries.
  1.1531 +            for (UPInt i = 0, n = pTable->SizeMask; i <= n; i++)
  1.1532 +            {
  1.1533 +                Entry*  e = &E(i);
  1.1534 +                if (!e->IsEmpty())             
  1.1535 +                    e->Clear();
  1.1536 +            }            
  1.1537 +                
  1.1538 +            Allocator::Free(pTable);
  1.1539 +            pTable = NULL;
  1.1540 +        }
  1.1541 +    }
  1.1542 +
  1.1543 +    // Returns true if the HashSet is empty.
  1.1544 +    bool IsEmpty() const
  1.1545 +    {
  1.1546 +        return pTable == NULL || pTable->EntryCount == 0;
  1.1547 +    }
  1.1548 +
  1.1549 +
  1.1550 +    // Set a new or existing value under the key, to the value.
  1.1551 +    // Pass a different class of 'key' so that assignment reference object
  1.1552 +    // can be passed instead of the actual object.
  1.1553 +    template<class CRef>
  1.1554 +    void Set(const CRef& key)
  1.1555 +    {
  1.1556 +        UPInt  hashValue = HashF()(key);
  1.1557 +        SPInt  index     = (SPInt)-1;
  1.1558 +
  1.1559 +        if (pTable != NULL)
  1.1560 +            index = findIndexCore(key, hashValue & pTable->SizeMask);
  1.1561 +
  1.1562 +        if (index >= 0)
  1.1563 +        {            
  1.1564 +            E(index).Value = key;
  1.1565 +        }
  1.1566 +        else
  1.1567 +        {
  1.1568 +            // Entry under key doesn't exist.
  1.1569 +            add(key, hashValue);
  1.1570 +        }
  1.1571 +    }
  1.1572 +
  1.1573 +    template<class CRef>
  1.1574 +    inline void Add(const CRef& key)
  1.1575 +    {
  1.1576 +        UPInt hashValue = HashF()(key);
  1.1577 +        add(key, hashValue);
  1.1578 +    }
  1.1579 +
  1.1580 +    // Remove by alternative key.
  1.1581 +    template<class K>
  1.1582 +    void RemoveAlt(const K& key)
  1.1583 +    {   
  1.1584 +        if (pTable == NULL)
  1.1585 +            return;
  1.1586 +
  1.1587 +        UPInt   hashValue = AltHashF()(key);
  1.1588 +        SPInt   index     = hashValue & pTable->SizeMask;
  1.1589 +
  1.1590 +        Entry*  e = &E(index);
  1.1591 +
  1.1592 +        // If empty node or occupied by collider, we have nothing to remove.
  1.1593 +        if (e->IsEmpty() || (e->GetCachedHash(pTable->SizeMask) != (UPInt)index))
  1.1594 +            return;        
  1.1595 +
  1.1596 +        // Save index
  1.1597 +        SPInt   naturalIndex = index;
  1.1598 +        SPInt   prevIndex    = -1;
  1.1599 +
  1.1600 +        while ((e->GetCachedHash(pTable->SizeMask) != (UPInt)naturalIndex) || !(e->Value == key))
  1.1601 +        {
  1.1602 +            // Keep looking through the chain.
  1.1603 +            prevIndex   = index;
  1.1604 +            index       = e->NextInChain;
  1.1605 +            if (index == -1)
  1.1606 +                return; // End of chain, item not found
  1.1607 +            e = &E(index);
  1.1608 +        }
  1.1609 +
  1.1610 +        // Found it - our item is at index
  1.1611 +        if (naturalIndex == index)
  1.1612 +        {
  1.1613 +            // If we have a follower, move it to us
  1.1614 +            if (!e->IsEndOfChain())
  1.1615 +            {               
  1.1616 +                Entry*  enext = &E(e->NextInChain);
  1.1617 +                e->Clear();
  1.1618 +                new (e) Entry(*enext);
  1.1619 +                // Point us to the follower's cell that will be cleared
  1.1620 +                e = enext;
  1.1621 +            }
  1.1622 +        }
  1.1623 +        else
  1.1624 +        {
  1.1625 +            // We are not at natural index, so deal with the prev items next index
  1.1626 +            E(prevIndex).NextInChain = e->NextInChain;
  1.1627 +        }
  1.1628 +
  1.1629 +        // Clear us, of the follower cell that was moved.
  1.1630 +        e->Clear();
  1.1631 +        pTable->EntryCount --;
  1.1632 +        // Should we check the size to condense hash? ...
  1.1633 +    }
  1.1634 +
  1.1635 +    // Remove by main key.
  1.1636 +    template<class CRef>
  1.1637 +    void Remove(const CRef& key)
  1.1638 +    {
  1.1639 +        RemoveAlt(key);
  1.1640 +    }
  1.1641 +
  1.1642 +    // Retrieve the pointer to a value under the given key.
  1.1643 +    //  - If there's no value under the key, then return NULL.    
  1.1644 +    //  - If there is a value, return the pointer.    
  1.1645 +    template<class K>
  1.1646 +    C* Get(const K& key)
  1.1647 +    {
  1.1648 +        SPInt   index = findIndex(key);
  1.1649 +        if (index >= 0)        
  1.1650 +            return &E(index).Value;        
  1.1651 +        return 0;
  1.1652 +    }   
  1.1653 +
  1.1654 +    template<class K>
  1.1655 +    const C* Get(const K& key) const
  1.1656 +    {
  1.1657 +        SPInt   index = findIndex(key);
  1.1658 +        if (index >= 0)        
  1.1659 +            return &E(index).Value;        
  1.1660 +        return 0;
  1.1661 +    }
  1.1662 +
  1.1663 +    // Alternative key versions of Get. Used by Hash.
  1.1664 +    template<class K>
  1.1665 +    const C* GetAlt(const K& key) const
  1.1666 +    {
  1.1667 +        SPInt   index = findIndexAlt(key);
  1.1668 +        if (index >= 0)        
  1.1669 +            return &E(index).Value;
  1.1670 +        return 0;
  1.1671 +    }
  1.1672 +
  1.1673 +    template<class K>
  1.1674 +    C* GetAlt(const K& key)
  1.1675 +    {
  1.1676 +        SPInt   index = findIndexAlt(key);
  1.1677 +        if (index >= 0)        
  1.1678 +            return &E(index).Value;
  1.1679 +        return 0;
  1.1680 +    }   
  1.1681 +
  1.1682 +    template<class K>
  1.1683 +    bool GetAlt(const K& key, C* pval) const
  1.1684 +    {
  1.1685 +        SPInt   index = findIndexAlt(key);
  1.1686 +        if (index >= 0)
  1.1687 +        {
  1.1688 +            if (pval)
  1.1689 +                *pval = E(index).Value;
  1.1690 +            return true;
  1.1691 +        }
  1.1692 +        return false;
  1.1693 +    }
  1.1694 +
  1.1695 +
  1.1696 +    UPInt GetSize() const
  1.1697 +    {
  1.1698 +        return pTable == NULL ? 0 : (UPInt)pTable->EntryCount;
  1.1699 +    }
  1.1700 +
  1.1701 +
  1.1702 +    // Resize the HashSet table to fit one more Entry.  Often this
  1.1703 +    // doesn't involve any action.
  1.1704 +    void CheckExpand()
  1.1705 +    {
  1.1706 +        if (pTable == NULL)
  1.1707 +        {
  1.1708 +            // Initial creation of table.  Make a minimum-sized table.
  1.1709 +            setRawCapacity(HashMinSize);
  1.1710 +        }
  1.1711 +        else if (pTable->EntryCount * 5 > (pTable->SizeMask + 1) * 4)
  1.1712 +        {
  1.1713 +            // pTable is more than 5/4 ths full.  Expand.
  1.1714 +            setRawCapacity((pTable->SizeMask + 1) * 2);
  1.1715 +        }
  1.1716 +    }
  1.1717 +
  1.1718 +    // Hint the bucket count to >= n.
  1.1719 +    void Resize(UPInt n)    
  1.1720 +    {
  1.1721 +        // Not really sure what this means in relation to
  1.1722 +        // STLport's hash_map... they say they "increase the
  1.1723 +        // bucket count to at least n" -- but does that mean
  1.1724 +        // their real capacity after Resize(n) is more like
  1.1725 +        // n*2 (since they do linked-list chaining within
  1.1726 +        // buckets?).
  1.1727 +        SetCapacity(n);
  1.1728 +    }
  1.1729 +
  1.1730 +    // Size the HashSet so that it can comfortably contain the given
  1.1731 +    // number of elements.  If the HashSet already contains more
  1.1732 +    // elements than newSize, then this may be a no-op.
  1.1733 +    void SetCapacity(UPInt newSize)
  1.1734 +    {
  1.1735 +        UPInt newRawSize = (newSize * 5) / 4;
  1.1736 +        if (newRawSize <= GetSize())
  1.1737 +            return;
  1.1738 +        setRawCapacity(newRawSize);
  1.1739 +    }
  1.1740 +
  1.1741 +    // Disable inappropriate 'operator ->' warning on MSVC6.
  1.1742 +#ifdef OVR_CC_MSVC
  1.1743 +#if (OVR_CC_MSVC < 1300)
  1.1744 +# pragma warning(disable : 4284)
  1.1745 +#endif
  1.1746 +#endif
  1.1747 +
  1.1748 +    // Iterator API, like STL.
  1.1749 +    struct ConstIterator
  1.1750 +    {   
  1.1751 +        const C&    operator * () const
  1.1752 +        {            
  1.1753 +            OVR_ASSERT(Index >= 0 && Index <= (SPInt)pHash->pTable->SizeMask);
  1.1754 +            return pHash->E(Index).Value;
  1.1755 +        }
  1.1756 +
  1.1757 +        const C*    operator -> () const
  1.1758 +        {
  1.1759 +            OVR_ASSERT(Index >= 0 && Index <= (SPInt)pHash->pTable->SizeMask);
  1.1760 +            return &pHash->E(Index).Value;
  1.1761 +        }
  1.1762 +
  1.1763 +        void    operator ++ ()
  1.1764 +        {
  1.1765 +            // Find next non-empty Entry.
  1.1766 +            if (Index <= (SPInt)pHash->pTable->SizeMask)
  1.1767 +            {
  1.1768 +                Index++;
  1.1769 +                while ((UPInt)Index <= pHash->pTable->SizeMask &&
  1.1770 +                    pHash->E(Index).IsEmpty())
  1.1771 +                {
  1.1772 +                    Index++;
  1.1773 +                }
  1.1774 +            }
  1.1775 +        }
  1.1776 +
  1.1777 +        bool    operator == (const ConstIterator& it) const
  1.1778 +        {
  1.1779 +            if (IsEnd() && it.IsEnd())
  1.1780 +            {
  1.1781 +                return true;
  1.1782 +            }
  1.1783 +            else
  1.1784 +            {
  1.1785 +                return (pHash == it.pHash) && (Index == it.Index);
  1.1786 +            }
  1.1787 +        }
  1.1788 +
  1.1789 +        bool    operator != (const ConstIterator& it) const
  1.1790 +        {
  1.1791 +            return ! (*this == it);
  1.1792 +        }
  1.1793 +
  1.1794 +
  1.1795 +        bool    IsEnd() const
  1.1796 +        {
  1.1797 +            return (pHash == NULL) || 
  1.1798 +                (pHash->pTable == NULL) || 
  1.1799 +                (Index > (SPInt)pHash->pTable->SizeMask);
  1.1800 +        }
  1.1801 +
  1.1802 +        ConstIterator()
  1.1803 +            : pHash(NULL), Index(0)
  1.1804 +        { }
  1.1805 +
  1.1806 +    public:
  1.1807 +        // Constructor was intentionally made public to allow create
  1.1808 +        // iterator with arbitrary index.
  1.1809 +        ConstIterator(const SelfType* h, SPInt index)
  1.1810 +            : pHash(h), Index(index)
  1.1811 +        { }
  1.1812 +
  1.1813 +        const SelfType* GetContainer() const
  1.1814 +        {
  1.1815 +            return pHash;
  1.1816 +        }
  1.1817 +        SPInt GetIndex() const
  1.1818 +        {
  1.1819 +            return Index;
  1.1820 +        }
  1.1821 +
  1.1822 +    protected:
  1.1823 +        friend class HashSetBase<C, HashF, AltHashF, Allocator, Entry>;
  1.1824 +
  1.1825 +        const SelfType* pHash;
  1.1826 +        SPInt           Index;
  1.1827 +    };
  1.1828 +
  1.1829 +    friend struct ConstIterator;
  1.1830 +
  1.1831 +
  1.1832 +    // Non-const Iterator; Get most of it from ConstIterator.
  1.1833 +    struct Iterator : public ConstIterator
  1.1834 +    {      
  1.1835 +        // Allow non-const access to entries.
  1.1836 +        C&  operator*() const
  1.1837 +        {            
  1.1838 +            OVR_ASSERT(ConstIterator::Index >= 0 && ConstIterator::Index <= (SPInt)ConstIterator::pHash->pTable->SizeMask);
  1.1839 +            return const_cast<SelfType*>(ConstIterator::pHash)->E(ConstIterator::Index).Value;
  1.1840 +        }    
  1.1841 +
  1.1842 +        C*  operator->() const 
  1.1843 +        {
  1.1844 +            return &(operator*());
  1.1845 +        }
  1.1846 +
  1.1847 +        Iterator()
  1.1848 +            : ConstIterator(NULL, 0)
  1.1849 +        { }
  1.1850 +
  1.1851 +        // Removes current element from Hash
  1.1852 +        void Remove()
  1.1853 +        {
  1.1854 +            RemoveAlt(operator*());
  1.1855 +        }
  1.1856 +
  1.1857 +        template <class K>
  1.1858 +        void RemoveAlt(const K& key)
  1.1859 +        {
  1.1860 +            SelfType*   phash = const_cast<SelfType*>(ConstIterator::pHash);
  1.1861 +            //Entry*      ee = &phash->E(ConstIterator::Index);
  1.1862 +            //const C&    key = ee->Value;
  1.1863 +
  1.1864 +            UPInt       hashValue = AltHashF()(key);
  1.1865 +            SPInt       index     = hashValue & phash->pTable->SizeMask;
  1.1866 +
  1.1867 +            Entry*      e = &phash->E(index);
  1.1868 +
  1.1869 +            // If empty node or occupied by collider, we have nothing to remove.
  1.1870 +            if (e->IsEmpty() || (e->GetCachedHash(phash->pTable->SizeMask) != (UPInt)index))
  1.1871 +                return;        
  1.1872 +
  1.1873 +            // Save index
  1.1874 +            SPInt   naturalIndex = index;
  1.1875 +            SPInt   prevIndex    = -1;
  1.1876 +
  1.1877 +            while ((e->GetCachedHash(phash->pTable->SizeMask) != (UPInt)naturalIndex) || !(e->Value == key))
  1.1878 +            {
  1.1879 +                // Keep looking through the chain.
  1.1880 +                prevIndex   = index;
  1.1881 +                index       = e->NextInChain;
  1.1882 +                if (index == -1)
  1.1883 +                    return; // End of chain, item not found
  1.1884 +                e = &phash->E(index);
  1.1885 +            }
  1.1886 +
  1.1887 +            if (index == (SPInt)ConstIterator::Index)
  1.1888 +            {
  1.1889 +                // Found it - our item is at index
  1.1890 +                if (naturalIndex == index)
  1.1891 +                {
  1.1892 +                    // If we have a follower, move it to us
  1.1893 +                    if (!e->IsEndOfChain())
  1.1894 +                    {               
  1.1895 +                        Entry*  enext = &phash->E(e->NextInChain);
  1.1896 +                        e->Clear();
  1.1897 +                        new (e) Entry(*enext);
  1.1898 +                        // Point us to the follower's cell that will be cleared
  1.1899 +                        e = enext;
  1.1900 +                        --ConstIterator::Index;
  1.1901 +                    }
  1.1902 +                }
  1.1903 +                else
  1.1904 +                {
  1.1905 +                    // We are not at natural index, so deal with the prev items next index
  1.1906 +                    phash->E(prevIndex).NextInChain = e->NextInChain;
  1.1907 +                }
  1.1908 +
  1.1909 +                // Clear us, of the follower cell that was moved.
  1.1910 +                e->Clear();
  1.1911 +                phash->pTable->EntryCount --;
  1.1912 +            }
  1.1913 +            else 
  1.1914 +                OVR_ASSERT(0); //?
  1.1915 +        }
  1.1916 +
  1.1917 +    private:
  1.1918 +        friend class HashSetBase<C, HashF, AltHashF, Allocator, Entry>;
  1.1919 +
  1.1920 +        Iterator(SelfType* h, SPInt i0)
  1.1921 +            : ConstIterator(h, i0)
  1.1922 +        { }
  1.1923 +    };
  1.1924 +
  1.1925 +    friend struct Iterator;
  1.1926 +
  1.1927 +    Iterator    Begin()
  1.1928 +    {
  1.1929 +        if (pTable == 0)
  1.1930 +            return Iterator(NULL, 0);
  1.1931 +
  1.1932 +        // Scan till we hit the First valid Entry.
  1.1933 +        UPInt  i0 = 0;
  1.1934 +        while (i0 <= pTable->SizeMask && E(i0).IsEmpty())
  1.1935 +        {
  1.1936 +            i0++;
  1.1937 +        }
  1.1938 +        return Iterator(this, i0);
  1.1939 +    }
  1.1940 +    Iterator        End()           { return Iterator(NULL, 0); }
  1.1941 +
  1.1942 +    ConstIterator   Begin() const   { return const_cast<SelfType*>(this)->Begin();     }
  1.1943 +    ConstIterator   End() const     { return const_cast<SelfType*>(this)->End();   }
  1.1944 +
  1.1945 +    template<class K>
  1.1946 +    Iterator Find(const K& key)
  1.1947 +    {
  1.1948 +        SPInt index = findIndex(key);
  1.1949 +        if (index >= 0)        
  1.1950 +            return Iterator(this, index);        
  1.1951 +        return Iterator(NULL, 0);
  1.1952 +    }
  1.1953 +
  1.1954 +    template<class K>
  1.1955 +    Iterator FindAlt(const K& key)
  1.1956 +    {
  1.1957 +        SPInt index = findIndexAlt(key);
  1.1958 +        if (index >= 0)        
  1.1959 +            return Iterator(this, index);        
  1.1960 +        return Iterator(NULL, 0);
  1.1961 +    }
  1.1962 +
  1.1963 +    template<class K>
  1.1964 +    ConstIterator Find(const K& key) const       { return const_cast<SelfType*>(this)->Find(key); }
  1.1965 +
  1.1966 +    template<class K>
  1.1967 +    ConstIterator FindAlt(const K& key) const    { return const_cast<SelfType*>(this)->FindAlt(key); }
  1.1968 +
  1.1969 +private:
  1.1970 +    // Find the index of the matching Entry.  If no match, then return -1.
  1.1971 +    template<class K>
  1.1972 +    SPInt findIndex(const K& key) const
  1.1973 +    {
  1.1974 +        if (pTable == NULL)
  1.1975 +            return -1;
  1.1976 +        UPInt hashValue = HashF()(key) & pTable->SizeMask;
  1.1977 +        return findIndexCore(key, hashValue);
  1.1978 +    }
  1.1979 +
  1.1980 +    template<class K>
  1.1981 +    SPInt findIndexAlt(const K& key) const
  1.1982 +    {
  1.1983 +        if (pTable == NULL)
  1.1984 +            return -1;
  1.1985 +        UPInt hashValue = AltHashF()(key) & pTable->SizeMask;
  1.1986 +        return findIndexCore(key, hashValue);
  1.1987 +    }
  1.1988 +
  1.1989 +    // Find the index of the matching Entry.  If no match, then return -1.
  1.1990 +    template<class K>
  1.1991 +    SPInt findIndexCore(const K& key, UPInt hashValue) const
  1.1992 +    {
  1.1993 +        // Table must exist.
  1.1994 +        OVR_ASSERT(pTable != 0);
  1.1995 +        // Hash key must be 'and-ed' by the caller.
  1.1996 +        OVR_ASSERT((hashValue & ~pTable->SizeMask) == 0);
  1.1997 +
  1.1998 +        UPInt           index = hashValue;
  1.1999 +        const Entry*    e     = &E(index);
  1.2000 +
  1.2001 +        // If empty or occupied by a collider, not found.
  1.2002 +        if (e->IsEmpty() || (e->GetCachedHash(pTable->SizeMask) != index))
  1.2003 +            return -1;
  1.2004 +
  1.2005 +        while(1)
  1.2006 +        {
  1.2007 +            OVR_ASSERT(e->GetCachedHash(pTable->SizeMask) == hashValue);
  1.2008 +
  1.2009 +            if (e->GetCachedHash(pTable->SizeMask) == hashValue && e->Value == key)
  1.2010 +            {
  1.2011 +                // Found it.
  1.2012 +                return index;
  1.2013 +            }
  1.2014 +            // Values can not be equal at this point.
  1.2015 +            // That would mean that the hash key for the same value differs.
  1.2016 +            OVR_ASSERT(!(e->Value == key));
  1.2017 +
  1.2018 +            // Keep looking through the chain.
  1.2019 +            index = e->NextInChain;
  1.2020 +            if (index == (UPInt)-1)
  1.2021 +                break; // end of chain
  1.2022 +
  1.2023 +            e = &E(index);
  1.2024 +            OVR_ASSERT(!e->IsEmpty());
  1.2025 +        }
  1.2026 +        return -1;
  1.2027 +    }
  1.2028 +
  1.2029 +
  1.2030 +    // Add a new value to the HashSet table, under the specified key.
  1.2031 +    template<class CRef>
  1.2032 +    void add(const CRef& key, UPInt hashValue)
  1.2033 +    {
  1.2034 +        CheckExpand();
  1.2035 +        hashValue &= pTable->SizeMask;
  1.2036 +
  1.2037 +        pTable->EntryCount++;
  1.2038 +
  1.2039 +        SPInt   index        = hashValue;
  1.2040 +        Entry*  naturalEntry = &(E(index));
  1.2041 +
  1.2042 +        if (naturalEntry->IsEmpty())
  1.2043 +        {
  1.2044 +            // Put the new Entry in.
  1.2045 +            new (naturalEntry) Entry(key, -1);
  1.2046 +        }
  1.2047 +        else
  1.2048 +        {
  1.2049 +            // Find a blank spot.
  1.2050 +            SPInt blankIndex = index;
  1.2051 +            do {
  1.2052 +                blankIndex = (blankIndex + 1) & pTable->SizeMask;
  1.2053 +            } while(!E(blankIndex).IsEmpty());
  1.2054 +
  1.2055 +            Entry*  blankEntry = &E(blankIndex);
  1.2056 +
  1.2057 +            if (naturalEntry->GetCachedHash(pTable->SizeMask) == (UPInt)index)
  1.2058 +            {
  1.2059 +                // Collision.  Link into this chain.
  1.2060 +
  1.2061 +                // Move existing list head.
  1.2062 +                new (blankEntry) Entry(*naturalEntry);    // placement new, copy ctor
  1.2063 +
  1.2064 +                // Put the new info in the natural Entry.
  1.2065 +                naturalEntry->Value       = key;
  1.2066 +                naturalEntry->NextInChain = blankIndex;
  1.2067 +            }
  1.2068 +            else
  1.2069 +            {
  1.2070 +                // Existing Entry does not naturally
  1.2071 +                // belong in this slot.  Existing
  1.2072 +                // Entry must be moved.
  1.2073 +
  1.2074 +                // Find natural location of collided element (i.e. root of chain)
  1.2075 +                SPInt collidedIndex = naturalEntry->GetCachedHash(pTable->SizeMask);
  1.2076 +                OVR_ASSERT(collidedIndex >= 0 && collidedIndex <= (SPInt)pTable->SizeMask);
  1.2077 +                for (;;)
  1.2078 +                {
  1.2079 +                    Entry*  e = &E(collidedIndex);
  1.2080 +                    if (e->NextInChain == index)
  1.2081 +                    {
  1.2082 +                        // Here's where we need to splice.
  1.2083 +                        new (blankEntry) Entry(*naturalEntry);
  1.2084 +                        e->NextInChain = blankIndex;
  1.2085 +                        break;
  1.2086 +                    }
  1.2087 +                    collidedIndex = e->NextInChain;
  1.2088 +                    OVR_ASSERT(collidedIndex >= 0 && collidedIndex <= (SPInt)pTable->SizeMask);
  1.2089 +                }
  1.2090 +
  1.2091 +                // Put the new data in the natural Entry.
  1.2092 +                naturalEntry->Value       = key;
  1.2093 +                naturalEntry->NextInChain = -1;                
  1.2094 +            }            
  1.2095 +        }
  1.2096 +
  1.2097 +        // Record hash value: has effect only if cached node is used.
  1.2098 +        naturalEntry->SetCachedHash(hashValue);
  1.2099 +    }
  1.2100 +
  1.2101 +    // Index access helpers.
  1.2102 +    Entry& E(UPInt index)
  1.2103 +    {
  1.2104 +        // Must have pTable and access needs to be within bounds.
  1.2105 +        OVR_ASSERT(index <= pTable->SizeMask);
  1.2106 +        return *(((Entry*) (pTable + 1)) + index);
  1.2107 +    }
  1.2108 +    const Entry& E(UPInt index) const
  1.2109 +    {        
  1.2110 +        OVR_ASSERT(index <= pTable->SizeMask);
  1.2111 +        return *(((Entry*) (pTable + 1)) + index);
  1.2112 +    }
  1.2113 +
  1.2114 +
  1.2115 +    // Resize the HashSet table to the given size (Rehash the
  1.2116 +    // contents of the current table).  The arg is the number of
  1.2117 +    // HashSet table entries, not the number of elements we should
  1.2118 +    // actually contain (which will be less than this).
  1.2119 +    void    setRawCapacity(UPInt newSize)    
  1.2120 +    {
  1.2121 +        if (newSize == 0)
  1.2122 +        {
  1.2123 +            // Special case.
  1.2124 +            Clear();
  1.2125 +            return;
  1.2126 +        }
  1.2127 +
  1.2128 +        // Minimum size; don't incur rehashing cost when expanding
  1.2129 +        // very small tables. Not that we perform this check before 
  1.2130 +        // 'log2f' call to avoid fp exception with newSize == 1.
  1.2131 +        if (newSize < HashMinSize)        
  1.2132 +            newSize = HashMinSize;       
  1.2133 +        else
  1.2134 +        {
  1.2135 +            // Force newSize to be a power of two.
  1.2136 +            int bits = Alg::UpperBit(newSize-1) + 1; // Chop( Log2f((float)(newSize-1)) + 1);
  1.2137 +            OVR_ASSERT((UPInt(1) << bits) >= newSize);
  1.2138 +            newSize = UPInt(1) << bits;
  1.2139 +        }
  1.2140 +
  1.2141 +        SelfType  newHash;
  1.2142 +        newHash.pTable = (TableType*)
  1.2143 +            Allocator::Alloc(                
  1.2144 +                sizeof(TableType) + sizeof(Entry) * newSize);
  1.2145 +        // Need to do something on alloc failure!
  1.2146 +        OVR_ASSERT(newHash.pTable);
  1.2147 +
  1.2148 +        newHash.pTable->EntryCount = 0;
  1.2149 +        newHash.pTable->SizeMask = newSize - 1;
  1.2150 +        UPInt i, n;
  1.2151 +
  1.2152 +        // Mark all entries as empty.
  1.2153 +        for (i = 0; i < newSize; i++)
  1.2154 +            newHash.E(i).NextInChain = -2;
  1.2155 +
  1.2156 +        // Copy stuff to newHash
  1.2157 +        if (pTable)
  1.2158 +        {            
  1.2159 +            for (i = 0, n = pTable->SizeMask; i <= n; i++)
  1.2160 +            {
  1.2161 +                Entry*  e = &E(i);
  1.2162 +                if (e->IsEmpty() == false)
  1.2163 +                {
  1.2164 +                    // Insert old Entry into new HashSet.
  1.2165 +                    newHash.Add(e->Value);
  1.2166 +                    // placement delete of old element
  1.2167 +                    e->Clear();
  1.2168 +                }
  1.2169 +            }
  1.2170 +
  1.2171 +            // Delete our old data buffer.
  1.2172 +            Allocator::Free(pTable);
  1.2173 +        }
  1.2174 +
  1.2175 +        // Steal newHash's data.
  1.2176 +        pTable = newHash.pTable;
  1.2177 +        newHash.pTable = NULL;
  1.2178 +    }
  1.2179 +
  1.2180 +    struct TableType
  1.2181 +    {
  1.2182 +        UPInt EntryCount;
  1.2183 +        UPInt SizeMask;
  1.2184 +        // Entry array follows this structure
  1.2185 +        // in memory.
  1.2186 +    };
  1.2187 +    TableType*  pTable;
  1.2188 +};
  1.2189 +
  1.2190 +
  1.2191 +
  1.2192 +//-----------------------------------------------------------------------------------
  1.2193 +template<class C, class HashF = FixedSizeHash<C>,
  1.2194 +         class AltHashF = HashF, 
  1.2195 +         class Allocator = ContainerAllocator<C>,
  1.2196 +         class Entry = HashsetCachedEntry<C, HashF> >
  1.2197 +class HashSet : public HashSetBase<C, HashF, AltHashF, Allocator, Entry>
  1.2198 +{
  1.2199 +public:
  1.2200 +    typedef HashSetBase<C, HashF, AltHashF, Allocator, Entry> BaseType;
  1.2201 +    typedef HashSet<C, HashF, AltHashF, Allocator, Entry>     SelfType;
  1.2202 +
  1.2203 +    HashSet()                                      {   }
  1.2204 +    HashSet(int sizeHint) : BaseType(sizeHint)     {   }
  1.2205 +    HashSet(const SelfType& src) : BaseType(src)   {   }
  1.2206 +    ~HashSet()                                     {   }
  1.2207 +
  1.2208 +    void operator = (const SelfType& src)   { BaseType::Assign(src); }
  1.2209 +
  1.2210 +    // Set a new or existing value under the key, to the value.
  1.2211 +    // Pass a different class of 'key' so that assignment reference object
  1.2212 +    // can be passed instead of the actual object.
  1.2213 +    template<class CRef>
  1.2214 +    void Set(const CRef& key)
  1.2215 +    {
  1.2216 +        BaseType::Set(key);
  1.2217 +    }
  1.2218 +
  1.2219 +    template<class CRef>
  1.2220 +    inline void Add(const CRef& key)
  1.2221 +    {
  1.2222 +        BaseType::Add(key);
  1.2223 +    }
  1.2224 +
  1.2225 +    // Hint the bucket count to >= n.
  1.2226 +    void Resize(UPInt n)    
  1.2227 +    {
  1.2228 +        BaseType::SetCapacity(n);
  1.2229 +    }
  1.2230 +
  1.2231 +    // Size the HashSet so that it can comfortably contain the given
  1.2232 +    // number of elements.  If the HashSet already contains more
  1.2233 +    // elements than newSize, then this may be a no-op.
  1.2234 +    void SetCapacity(UPInt newSize)
  1.2235 +    {
  1.2236 +        BaseType::SetCapacity(newSize);
  1.2237 +    }
  1.2238 +
  1.2239 +};
  1.2240 +
  1.2241 +// HashSet with uncached hash code; declared for convenience.
  1.2242 +template<class C, class HashF = FixedSizeHash<C>,
  1.2243 +                  class AltHashF = HashF,
  1.2244 +                  class Allocator = ContainerAllocator<C> >
  1.2245 +class HashSetUncached : public HashSet<C, HashF, AltHashF, Allocator, HashsetEntry<C, HashF> >
  1.2246 +{
  1.2247 +public:
  1.2248 +    
  1.2249 +    typedef HashSetUncached<C, HashF, AltHashF, Allocator>                  SelfType;
  1.2250 +    typedef HashSet<C, HashF, AltHashF, Allocator, HashsetEntry<C, HashF> > BaseType;
  1.2251 +
  1.2252 +    // Delegated constructors.
  1.2253 +    HashSetUncached()                                        { }
  1.2254 +    HashSetUncached(int sizeHint) : BaseType(sizeHint)       { }
  1.2255 +    HashSetUncached(const SelfType& src) : BaseType(src)     { }
  1.2256 +    ~HashSetUncached()                                       { }
  1.2257 +    
  1.2258 +    void    operator = (const SelfType& src)
  1.2259 +    {
  1.2260 +        BaseType::operator = (src);
  1.2261 +    }
  1.2262 +};
  1.2263 +
  1.2264 +
  1.2265 +//-----------------------------------------------------------------------------------
  1.2266 +// ***** Hash hash table implementation
  1.2267 +
  1.2268 +// Node for Hash - necessary so that Hash can delegate its implementation
  1.2269 +// to HashSet.
  1.2270 +template<class C, class U, class HashF>
  1.2271 +struct HashNode
  1.2272 +{
  1.2273 +    typedef HashNode<C, U, HashF>   SelfType;
  1.2274 +    typedef C                       FirstType;
  1.2275 +    typedef U                       SecondType;
  1.2276 +
  1.2277 +    C   First;
  1.2278 +    U   Second;
  1.2279 +
  1.2280 +    // NodeRef is used to allow passing of elements into HashSet
  1.2281 +    // without using a temporary object.
  1.2282 +    struct NodeRef
  1.2283 +    {
  1.2284 +        const C*   pFirst;
  1.2285 +        const U*   pSecond;
  1.2286 +
  1.2287 +        NodeRef(const C& f, const U& s) : pFirst(&f), pSecond(&s) { }
  1.2288 +        NodeRef(const NodeRef& src)     : pFirst(src.pFirst), pSecond(src.pSecond) { }
  1.2289 +
  1.2290 +        // Enable computation of ghash_node_hashf.
  1.2291 +        inline UPInt GetHash() const            { return HashF()(*pFirst); } 
  1.2292 +        // Necessary conversion to allow HashNode::operator == to work.
  1.2293 +        operator const C& () const              { return *pFirst; }
  1.2294 +    };
  1.2295 +
  1.2296 +    // Note: No default constructor is necessary.
  1.2297 +     HashNode(const HashNode& src) : First(src.First), Second(src.Second)    { }
  1.2298 +     HashNode(const NodeRef& src) : First(*src.pFirst), Second(*src.pSecond)  { }
  1.2299 +    void operator = (const NodeRef& src)  { First  = *src.pFirst; Second = *src.pSecond; }
  1.2300 +
  1.2301 +    template<class K>
  1.2302 +    bool operator == (const K& src) const   { return (First == src); }
  1.2303 +
  1.2304 +    template<class K>
  1.2305 +    static UPInt CalcHash(const K& data)   { return HashF()(data); }
  1.2306 +    inline UPInt GetHash() const           { return HashF()(First); }
  1.2307 +
  1.2308 +    // Hash functors used with this node. A separate functor is used for alternative
  1.2309 +    // key lookup so that it does not need to access the '.First' element.    
  1.2310 +    struct NodeHashF
  1.2311 +    {    
  1.2312 +        template<class K>
  1.2313 +        UPInt operator()(const K& data) const { return data.GetHash(); } 
  1.2314 +    };    
  1.2315 +    struct NodeAltHashF
  1.2316 +    {
  1.2317 +        template<class K>
  1.2318 +        UPInt operator()(const K& data) const { return HashNode<C,U,HashF>::CalcHash(data); }
  1.2319 +    };
  1.2320 +};
  1.2321 +
  1.2322 +
  1.2323 +
  1.2324 +// **** Extra hashset_entry types to allow NodeRef construction.
  1.2325 +
  1.2326 +// The big difference between the below types and the ones used in hash_set is that
  1.2327 +// these allow initializing the node with 'typename C::NodeRef& keyRef', which
  1.2328 +// is critical to avoid temporary node allocation on stack when using placement new.
  1.2329 +
  1.2330 +// Compact hash table Entry type that re-computes hash keys during hash traversal.
  1.2331 +// Good to use if the hash function is cheap or the hash value is already cached in C.
  1.2332 +template<class C, class HashF>
  1.2333 +class HashsetNodeEntry
  1.2334 +{
  1.2335 +public:
  1.2336 +    // Internal chaining for collisions.
  1.2337 +    SPInt NextInChain;
  1.2338 +    C     Value;
  1.2339 +
  1.2340 +    HashsetNodeEntry()
  1.2341 +        : NextInChain(-2) { }
  1.2342 +    HashsetNodeEntry(const HashsetNodeEntry& e)
  1.2343 +        : NextInChain(e.NextInChain), Value(e.Value) { }
  1.2344 +    HashsetNodeEntry(const C& key, SPInt next)
  1.2345 +        : NextInChain(next), Value(key) { }    
  1.2346 +    HashsetNodeEntry(const typename C::NodeRef& keyRef, SPInt next)
  1.2347 +        : NextInChain(next), Value(keyRef) { }
  1.2348 +
  1.2349 +    bool    IsEmpty() const             { return NextInChain == -2;  }
  1.2350 +    bool    IsEndOfChain() const        { return NextInChain == -1;  }
  1.2351 +    UPInt   GetCachedHash(UPInt maskValue) const  { return HashF()(Value) & maskValue; }
  1.2352 +    void    SetCachedHash(UPInt hashValue)        { OVR_UNUSED(hashValue); }
  1.2353 +
  1.2354 +    void    Clear()
  1.2355 +    {        
  1.2356 +        Value.~C(); // placement delete
  1.2357 +        NextInChain = -2;
  1.2358 +    }
  1.2359 +    // Free is only used from dtor of hash; Clear is used during regular operations:
  1.2360 +    // assignment, hash reallocations, value reassignments, so on.
  1.2361 +    void    Free() { Clear(); }
  1.2362 +};
  1.2363 +
  1.2364 +// Hash table Entry type that caches the Entry hash value for nodes, so that it
  1.2365 +// does not need to be re-computed during access.
  1.2366 +template<class C, class HashF>
  1.2367 +class HashsetCachedNodeEntry
  1.2368 +{
  1.2369 +public:
  1.2370 +    // Internal chaining for collisions.
  1.2371 +    SPInt NextInChain;
  1.2372 +    UPInt HashValue;
  1.2373 +    C     Value;
  1.2374 +
  1.2375 +    HashsetCachedNodeEntry()
  1.2376 +        : NextInChain(-2) { }
  1.2377 +    HashsetCachedNodeEntry(const HashsetCachedNodeEntry& e)
  1.2378 +        : NextInChain(e.NextInChain), HashValue(e.HashValue), Value(e.Value) { }
  1.2379 +    HashsetCachedNodeEntry(const C& key, SPInt next)
  1.2380 +        : NextInChain(next), Value(key) { }
  1.2381 +    HashsetCachedNodeEntry(const typename C::NodeRef& keyRef, SPInt next)
  1.2382 +        : NextInChain(next), Value(keyRef) { }
  1.2383 +
  1.2384 +    bool    IsEmpty() const            { return NextInChain == -2;  }
  1.2385 +    bool    IsEndOfChain() const       { return NextInChain == -1;  }
  1.2386 +    UPInt   GetCachedHash(UPInt maskValue) const  { OVR_UNUSED(maskValue); return HashValue; }
  1.2387 +    void    SetCachedHash(UPInt hashValue)        { HashValue = hashValue; }
  1.2388 +
  1.2389 +    void    Clear()
  1.2390 +    {
  1.2391 +        Value.~C();
  1.2392 +        NextInChain = -2;
  1.2393 +    }
  1.2394 +    // Free is only used from dtor of hash; Clear is used during regular operations:
  1.2395 +    // assignment, hash reallocations, value reassignments, so on.
  1.2396 +    void    Free() { Clear(); }
  1.2397 +};
  1.2398 +
  1.2399 +
  1.2400 +//-----------------------------------------------------------------------------------
  1.2401 +template<class C, class U,
  1.2402 +         class HashF = FixedSizeHash<C>,
  1.2403 +         class Allocator = ContainerAllocator<C>,
  1.2404 +         class HashNode = OVR::HashNode<C,U,HashF>,
  1.2405 +         class Entry = HashsetCachedNodeEntry<HashNode, typename HashNode::NodeHashF>,
  1.2406 +         class Container =  HashSet<HashNode, typename HashNode::NodeHashF,
  1.2407 +             typename HashNode::NodeAltHashF, Allocator,
  1.2408 +             Entry> >
  1.2409 +class Hash
  1.2410 +{
  1.2411 +public:
  1.2412 +    OVR_MEMORY_REDEFINE_NEW(Hash)
  1.2413 +
  1.2414 +    // Types used for hash_set.
  1.2415 +    typedef U                                                           ValueType;
  1.2416 +    typedef Hash<C, U, HashF, Allocator, HashNode, Entry, Container>    SelfType;
  1.2417 +
  1.2418 +    // Actual hash table itself, implemented as hash_set.
  1.2419 +    Container   mHash;
  1.2420 +
  1.2421 +public:
  1.2422 +    Hash()     {  }
  1.2423 +    Hash(int sizeHint) : mHash(sizeHint)                        { }
  1.2424 +    Hash(const SelfType& src) : mHash(src.mHash)                { }
  1.2425 +    ~Hash()                                                     { }
  1.2426 +
  1.2427 +    void    operator = (const SelfType& src)    { mHash = src.mHash; }
  1.2428 +
  1.2429 +    // Remove all entries from the Hash table.
  1.2430 +    inline void    Clear() { mHash.Clear(); }
  1.2431 +    // Returns true if the Hash is empty.
  1.2432 +    inline bool    IsEmpty() const { return mHash.IsEmpty(); }
  1.2433 +
  1.2434 +    // Access (set).
  1.2435 +    inline void    Set(const C& key, const U& value)
  1.2436 +    {
  1.2437 +        typename HashNode::NodeRef e(key, value);
  1.2438 +        mHash.Set(e);
  1.2439 +    }
  1.2440 +    inline void    Add(const C& key, const U& value)
  1.2441 +    {
  1.2442 +        typename HashNode::NodeRef e(key, value);
  1.2443 +        mHash.Add(e);
  1.2444 +    }
  1.2445 +
  1.2446 +    // Removes an element by clearing its Entry.
  1.2447 +    inline void     Remove(const C& key)
  1.2448 +    {   
  1.2449 +        mHash.RemoveAlt(key);
  1.2450 +    }
  1.2451 +    template<class K>
  1.2452 +    inline void     RemoveAlt(const K& key)
  1.2453 +    {   
  1.2454 +        mHash.RemoveAlt(key);
  1.2455 +    }
  1.2456 +
  1.2457 +    // Retrieve the value under the given key.    
  1.2458 +    //  - If there's no value under the key, then return false and leave *pvalue alone.
  1.2459 +    //  - If there is a value, return true, and Set *Pvalue to the Entry's value.
  1.2460 +    //  - If value == NULL, return true or false according to the presence of the key.    
  1.2461 +    bool    Get(const C& key, U* pvalue) const   
  1.2462 +    {
  1.2463 +        const HashNode* p = mHash.GetAlt(key);
  1.2464 +        if (p)
  1.2465 +        {
  1.2466 +            if (pvalue)
  1.2467 +                *pvalue = p->Second;
  1.2468 +            return true;
  1.2469 +        }
  1.2470 +        return false;
  1.2471 +    }
  1.2472 +
  1.2473 +    template<class K>
  1.2474 +    bool    GetAlt(const K& key, U* pvalue) const   
  1.2475 +    {
  1.2476 +        const HashNode* p = mHash.GetAlt(key);
  1.2477 +        if (p)
  1.2478 +        {
  1.2479 +            if (pvalue)
  1.2480 +                *pvalue = p->Second;
  1.2481 +            return true;
  1.2482 +        }
  1.2483 +        return false;
  1.2484 +    }
  1.2485 +
  1.2486 +    // Retrieve the pointer to a value under the given key.    
  1.2487 +    //  - If there's no value under the key, then return NULL.    
  1.2488 +    //  - If there is a value, return the pointer.    
  1.2489 +    inline U*  Get(const C& key)
  1.2490 +    {
  1.2491 +        HashNode* p = mHash.GetAlt(key);
  1.2492 +        return p ? &p->Second : 0;
  1.2493 +    }
  1.2494 +    inline const U* Get(const C& key) const
  1.2495 +    {
  1.2496 +        const HashNode* p = mHash.GetAlt(key);
  1.2497 +        return p ? &p->Second : 0;
  1.2498 +    }
  1.2499 +
  1.2500 +    template<class K>
  1.2501 +    inline U*  GetAlt(const K& key)
  1.2502 +    {
  1.2503 +        HashNode* p = mHash.GetAlt(key);
  1.2504 +        return p ? &p->Second : 0;
  1.2505 +    }
  1.2506 +    template<class K>
  1.2507 +    inline const U* GetAlt(const K& key) const
  1.2508 +    {
  1.2509 +        const HashNode* p = mHash.GetAlt(key);
  1.2510 +        return p ? &p->Second : 0;
  1.2511 +    }
  1.2512 +
  1.2513 +    // Sizing methods - delegate to Hash.
  1.2514 +    inline UPInt   GetSize() const              { return mHash.GetSize(); }    
  1.2515 +    inline void    Resize(UPInt n)              { mHash.Resize(n); }
  1.2516 +    inline void    SetCapacity(UPInt newSize)   { mHash.SetCapacity(newSize); }
  1.2517 +
  1.2518 +    // Iterator API, like STL.
  1.2519 +    typedef typename Container::ConstIterator   ConstIterator;
  1.2520 +    typedef typename Container::Iterator        Iterator;
  1.2521 +
  1.2522 +    inline Iterator        Begin()              { return mHash.Begin(); }
  1.2523 +    inline Iterator        End()                { return mHash.End(); }
  1.2524 +    inline ConstIterator   Begin() const        { return mHash.Begin(); }
  1.2525 +    inline ConstIterator   End() const          { return mHash.End();   }
  1.2526 +
  1.2527 +    Iterator        Find(const C& key)          { return mHash.FindAlt(key);  }
  1.2528 +    ConstIterator   Find(const C& key) const    { return mHash.FindAlt(key);  }
  1.2529 +
  1.2530 +    template<class K>
  1.2531 +    Iterator        FindAlt(const K& key)       { return mHash.FindAlt(key);  }
  1.2532 +    template<class K>
  1.2533 +    ConstIterator   FindAlt(const K& key) const { return mHash.FindAlt(key);  }
  1.2534 +};
  1.2535 +
  1.2536 +
  1.2537 +
  1.2538 +// Hash with uncached hash code; declared for convenience.
  1.2539 +template<class C, class U, class HashF = FixedSizeHash<C>, class Allocator = ContainerAllocator<C> >
  1.2540 +class HashUncached
  1.2541 +    : public Hash<C, U, HashF, Allocator, HashNode<C,U,HashF>,
  1.2542 +                   HashsetNodeEntry<HashNode<C,U,HashF>, typename HashNode<C,U,HashF>::NodeHashF> >
  1.2543 +{
  1.2544 +public:
  1.2545 +    typedef HashUncached<C, U, HashF, Allocator>                SelfType;
  1.2546 +    typedef Hash<C, U, HashF, Allocator, HashNode<C,U,HashF>,
  1.2547 +                 HashsetNodeEntry<HashNode<C,U,HashF>,
  1.2548 +                 typename HashNode<C,U,HashF>::NodeHashF> >     BaseType;
  1.2549 +
  1.2550 +    // Delegated constructors.
  1.2551 +    HashUncached()                                        { }
  1.2552 +    HashUncached(int sizeHint) : BaseType(sizeHint)       { }
  1.2553 +    HashUncached(const SelfType& src) : BaseType(src)     { }
  1.2554 +    ~HashUncached()                                       { }
  1.2555 +    void operator = (const SelfType& src)                 { BaseType::operator = (src); }
  1.2556 +};
  1.2557 +
  1.2558 +
  1.2559 +
  1.2560 +// And identity hash in which keys serve as hash value. Can be uncached,
  1.2561 +// since hash computation is assumed cheap.
  1.2562 +template<class C, class U, class Allocator = ContainerAllocator<C>, class HashF = IdentityHash<C> >
  1.2563 +class HashIdentity
  1.2564 +    : public HashUncached<C, U, HashF, Allocator>
  1.2565 +{
  1.2566 +public:
  1.2567 +    typedef HashIdentity<C, U, Allocator, HashF> SelfType;
  1.2568 +    typedef HashUncached<C, U, HashF, Allocator> BaseType;
  1.2569 +
  1.2570 +    // Delegated constructors.
  1.2571 +    HashIdentity()                                        { }
  1.2572 +    HashIdentity(int sizeHint) : BaseType(sizeHint)       { }
  1.2573 +    HashIdentity(const SelfType& src) : BaseType(src)     { }
  1.2574 +    ~HashIdentity()                                       { }
  1.2575 +    void operator = (const SelfType& src)                 { BaseType::operator = (src); }
  1.2576 +};
  1.2577 +
  1.2578 +
  1.2579 +} // OVR
  1.2580 +
  1.2581 +
  1.2582 +#ifdef OVR_DEFINE_NEW
  1.2583 +#define new OVR_DEFINE_NEW
  1.2584 +#endif
  1.2585 +
  1.2586 +#endif