nuclear@0: /************************************************************************************
nuclear@0: 
nuclear@0: PublicHeader:   None
nuclear@0: Filename    :   OVR_Hash.h
nuclear@0: Content     :   Template hash-table/set implementation
nuclear@0: Created     :   September 19, 2012
nuclear@0: Notes       : 
nuclear@0: 
nuclear@0: Copyright   :   Copyright 2014 Oculus VR, LLC All Rights reserved.
nuclear@0: 
nuclear@0: Licensed under the Oculus VR Rift SDK License Version 3.2 (the "License"); 
nuclear@0: you may not use the Oculus VR Rift SDK except in compliance with the License, 
nuclear@0: which is provided at the time of installation or download, or which 
nuclear@0: otherwise accompanies this software in either electronic or hard copy form.
nuclear@0: 
nuclear@0: You may obtain a copy of the License at
nuclear@0: 
nuclear@0: http://www.oculusvr.com/licenses/LICENSE-3.2 
nuclear@0: 
nuclear@0: Unless required by applicable law or agreed to in writing, the Oculus VR SDK 
nuclear@0: distributed under the License is distributed on an "AS IS" BASIS,
nuclear@0: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
nuclear@0: See the License for the specific language governing permissions and
nuclear@0: limitations under the License.
nuclear@0: 
nuclear@0: ************************************************************************************/
nuclear@0: 
nuclear@0: #ifndef OVR_Hash_h
nuclear@0: #define OVR_Hash_h
nuclear@0: 
nuclear@0: #include "OVR_ContainerAllocator.h"
nuclear@0: #include "OVR_Alg.h"
nuclear@0: 
nuclear@0: // 'new' operator is redefined/used in this file.
nuclear@0: #undef new
nuclear@0: 
nuclear@0: namespace OVR {
nuclear@0: 
nuclear@0: //-----------------------------------------------------------------------------------
nuclear@0: // ***** Hash Table Implementation
nuclear@0: 
nuclear@0: // HastSet and Hash.
nuclear@0: //
nuclear@0: // Hash table, linear probing, internal chaining.  One  interesting/nice thing
nuclear@0: // about this implementation is that the table itself is a flat chunk of memory
nuclear@0: // containing no pointers, only relative indices. If the key and value types
nuclear@0: // of the Hash contain no pointers, then the Hash can be serialized using raw IO.
nuclear@0: //
nuclear@0: // Never shrinks, unless you explicitly Clear() it.  Expands on
nuclear@0: // demand, though.  For best results, if you know roughly how big your
nuclear@0: // table will be, default it to that size when you create it.
nuclear@0: //
nuclear@0: // Key usability feature:
nuclear@0: //
nuclear@0: //   1. Allows node hash values to either be cached or not.
nuclear@0: //
nuclear@0: //   2. Allows for alternative keys with methods such as GetAlt(). Handy
nuclear@0: //      if you need to search nodes by their components; no need to create
nuclear@0: //      temporary nodes.
nuclear@0: //
nuclear@0: 
nuclear@0: 
nuclear@0: // *** Hash functors:
nuclear@0: //
nuclear@0: //  IdentityHash  - use when the key is already a good hash
nuclear@0: //  HFixedSizeHash - general hash based on object's in-memory representation.
nuclear@0: 
nuclear@0: 
nuclear@0: // Hash is just the input value; can use this for integer-indexed hash tables.
nuclear@0: template<class C>
nuclear@0: class IdentityHash
nuclear@0: {
nuclear@0: public:
nuclear@0:     size_t operator()(const C& data) const
nuclear@0:     { return (size_t) data; }
nuclear@0: };
nuclear@0: 
nuclear@0: // Computes a hash of an object's representation.
nuclear@0: template<class C>
nuclear@0: class FixedSizeHash
nuclear@0: {
nuclear@0: public:
nuclear@0:     // Alternative: "sdbm" hash function, suggested at same web page
nuclear@0:     // above, http::/www.cs.yorku.ca/~oz/hash.html
nuclear@0:     // This is somewhat slower then Bernstein, but it works way better than the above
nuclear@0:     // hash function for hashing large numbers of 32-bit ints.
nuclear@0:     static OVR_FORCE_INLINE size_t SDBM_Hash(const void* data_in, size_t size, size_t seed = 5381)     
nuclear@0:     {
nuclear@0:         const uint8_t* data = (const uint8_t*) data_in;
nuclear@0:         size_t       h = seed;
nuclear@0:         while (size-- > 0)
nuclear@0:         {
nuclear@0:             #ifndef __clang_analyzer__ // It mistakenly thinks data is garbage.
nuclear@0:             h = (h << 16) + (h << 6) - h + (size_t)data[size];
nuclear@0:             #endif
nuclear@0:         }   
nuclear@0:         return h;
nuclear@0:     }
nuclear@0: 
nuclear@0:     size_t operator()(const C& data) const
nuclear@0:     {
nuclear@0:         const unsigned char*  p = (const unsigned char*) &data;
nuclear@0:         const size_t size = sizeof(C);
nuclear@0: 
nuclear@0:         return SDBM_Hash(p, size);
nuclear@0:     }
nuclear@0: };
nuclear@0: 
nuclear@0: 
nuclear@0: 
nuclear@0: // *** HashsetEntry Entry types. 
nuclear@0: 
nuclear@0: // Compact hash table Entry type that re-computes hash keys during hash traversal.
nuclear@0: // Good to use if the hash function is cheap or the hash value is already cached in C.
nuclear@0: template<class C, class HashF>
nuclear@0: class HashsetEntry
nuclear@0: {
nuclear@0: public:
nuclear@0:     // Internal chaining for collisions.
nuclear@0:     intptr_t    NextInChain;
nuclear@0:     C           Value;
nuclear@0: 
nuclear@0:     HashsetEntry()
nuclear@0:         : NextInChain(-2) { }
nuclear@0:     HashsetEntry(const HashsetEntry& e)
nuclear@0:         : NextInChain(e.NextInChain), Value(e.Value) { }
nuclear@0:     HashsetEntry(const C& key, intptr_t next)
nuclear@0:         : NextInChain(next), Value(key) { }
nuclear@0: 
nuclear@0:     bool    IsEmpty() const          { return NextInChain == -2;  }
nuclear@0:     bool    IsEndOfChain() const     { return NextInChain == -1;  }
nuclear@0: 
nuclear@0:     // Cached hash value access - can be optimized bu storing hash locally.
nuclear@0:     // Mask value only needs to be used if SetCachedHash is not implemented.
nuclear@0:     size_t  GetCachedHash(size_t maskValue) const  { return HashF()(Value) & maskValue; }
nuclear@0:     void    SetCachedHash(size_t)                  {}
nuclear@0: 
nuclear@0:     void    Clear()
nuclear@0:     {        
nuclear@0:         Value.~C(); // placement delete
nuclear@0:         NextInChain = -2;
nuclear@0:     }
nuclear@0:     // Free is only used from dtor of hash; Clear is used during regular operations:
nuclear@0:     // assignment, hash reallocations, value reassignments, so on.
nuclear@0:     void    Free() { Clear(); }
nuclear@0: };
nuclear@0: 
nuclear@0: // Hash table Entry type that caches the Entry hash value for nodes, so that it
nuclear@0: // does not need to be re-computed during access.
nuclear@0: template<class C, class HashF>
nuclear@0: class HashsetCachedEntry
nuclear@0: {
nuclear@0: public:
nuclear@0:     // Internal chaining for collisions.
nuclear@0:     intptr_t    NextInChain;
nuclear@0:     size_t      HashValue;
nuclear@0:     C           Value;
nuclear@0: 
nuclear@0:     HashsetCachedEntry()
nuclear@0:         : NextInChain(-2) { }
nuclear@0:     HashsetCachedEntry(const HashsetCachedEntry& e)
nuclear@0:         : NextInChain(e.NextInChain), HashValue(e.HashValue), Value(e.Value) { }
nuclear@0:     HashsetCachedEntry(const C& key, intptr_t next)
nuclear@0:         : NextInChain(next), Value(key) { }
nuclear@0: 
nuclear@0:     bool    IsEmpty() const          { return NextInChain == -2;  }
nuclear@0:     bool    IsEndOfChain() const     { return NextInChain == -1;  }
nuclear@0: 
nuclear@0:     // Cached hash value access - can be optimized bu storing hash locally.
nuclear@0:     // Mask value only needs to be used if SetCachedHash is not implemented.
nuclear@0:     size_t  GetCachedHash(size_t maskValue) const  { OVR_UNUSED(maskValue); return HashValue; }
nuclear@0:     void    SetCachedHash(size_t hashValue)        { HashValue = hashValue; }
nuclear@0: 
nuclear@0:     void    Clear()
nuclear@0:     {
nuclear@0:         Value.~C();
nuclear@0:         NextInChain = -2;
nuclear@0:     }
nuclear@0:     // Free is only used from dtor of hash; Clear is used during regular operations:
nuclear@0:     // assignment, hash reallocations, value reassignments, so on.
nuclear@0:     void    Free() { Clear(); }
nuclear@0: };
nuclear@0: 
nuclear@0: 
nuclear@0: //-----------------------------------------------------------------------------------
nuclear@0: // *** HashSet implementation - relies on either cached or regular entries.
nuclear@0: //
nuclear@0: // Use: Entry = HashsetCachedEntry<C, HashF> if hashes are expensive to
nuclear@0: //              compute and thus need caching in entries.
nuclear@0: //      Entry = HashsetEntry<C, HashF> if hashes are already externally cached.
nuclear@0: //
nuclear@0: template<class C, class HashF = FixedSizeHash<C>,
nuclear@0:          class AltHashF = HashF, 
nuclear@0:          class Allocator = ContainerAllocator<C>,
nuclear@0:          class Entry = HashsetCachedEntry<C, HashF> >
nuclear@0: class HashSetBase
nuclear@0: {
nuclear@0:     enum { HashMinSize = 8 };
nuclear@0: 
nuclear@0: public:
nuclear@0:     OVR_MEMORY_REDEFINE_NEW(HashSetBase)
nuclear@0: 
nuclear@0:     typedef HashSetBase<C, HashF, AltHashF, Allocator, Entry>    SelfType;
nuclear@0: 
nuclear@0:     HashSetBase() : pTable(NULL)                       {   }
nuclear@0:     HashSetBase(int sizeHint) : pTable(NULL)           { SetCapacity(this, sizeHint);  }
nuclear@0:     HashSetBase(const SelfType& src) : pTable(NULL)    { Assign(this, src); }
nuclear@0: 
nuclear@0:     ~HashSetBase()                                     
nuclear@0:     { 
nuclear@0:         if (pTable)
nuclear@0:         {
nuclear@0:             // Delete the entries.
nuclear@0:             for (size_t i = 0, n = pTable->SizeMask; i <= n; i++)
nuclear@0:             {
nuclear@0:                 Entry*  e = &E(i);
nuclear@0:                 if (!e->IsEmpty())             
nuclear@0:                     e->Free();
nuclear@0:             }            
nuclear@0: 
nuclear@0:             Allocator::Free(pTable);
nuclear@0:             pTable = NULL;
nuclear@0:         }
nuclear@0:     }
nuclear@0: 
nuclear@0: 
nuclear@0:     void Assign(const SelfType& src)
nuclear@0:     {
nuclear@0:         Clear();
nuclear@0:         if (src.IsEmpty() == false)
nuclear@0:         {
nuclear@0:             SetCapacity(src.GetSize());
nuclear@0: 
nuclear@0:             for (ConstIterator it = src.Begin(); it != src.End(); ++it)
nuclear@0:             {
nuclear@0:                 Add(*it);
nuclear@0:             }
nuclear@0:         }
nuclear@0:     }
nuclear@0: 
nuclear@0: 
nuclear@0:     // Remove all entries from the HashSet table.
nuclear@0:     void Clear() 
nuclear@0:     {
nuclear@0:         if (pTable)
nuclear@0:         {
nuclear@0:             // Delete the entries.
nuclear@0:             for (size_t i = 0, n = pTable->SizeMask; i <= n; i++)
nuclear@0:             {
nuclear@0:                 Entry*  e = &E(i);
nuclear@0:                 if (!e->IsEmpty())             
nuclear@0:                     e->Clear();
nuclear@0:             }            
nuclear@0:                 
nuclear@0:             Allocator::Free(pTable);
nuclear@0:             pTable = NULL;
nuclear@0:         }
nuclear@0:     }
nuclear@0: 
nuclear@0:     // Returns true if the HashSet is empty.
nuclear@0:     bool IsEmpty() const
nuclear@0:     {
nuclear@0:         return pTable == NULL || pTable->EntryCount == 0;
nuclear@0:     }
nuclear@0: 
nuclear@0: 
nuclear@0:     // Set a new or existing value under the key, to the value.
nuclear@0:     // Pass a different class of 'key' so that assignment reference object
nuclear@0:     // can be passed instead of the actual object.
nuclear@0:     template<class CRef>
nuclear@0:     void Set(const CRef& key)
nuclear@0:     {
nuclear@0:         size_t hashValue = HashF()(key);
nuclear@0:         intptr_t  index     = (intptr_t)-1;
nuclear@0: 
nuclear@0:         if (pTable != NULL)
nuclear@0:             index = findIndexCore(key, hashValue & pTable->SizeMask);
nuclear@0: 
nuclear@0:         if (index >= 0)
nuclear@0:         {            
nuclear@0:             E(index).Value = key;
nuclear@0:         }
nuclear@0:         else
nuclear@0:         {
nuclear@0:             // Entry under key doesn't exist.
nuclear@0:             add(key, hashValue);
nuclear@0:         }
nuclear@0:     }
nuclear@0: 
nuclear@0:     template<class CRef>
nuclear@0:     inline void Add(const CRef& key)
nuclear@0:     {
nuclear@0:         size_t hashValue = HashF()(key);
nuclear@0:         add(key, hashValue);
nuclear@0:     }
nuclear@0: 
nuclear@0:     // Remove by alternative key.
nuclear@0:     template<class K>
nuclear@0:     void RemoveAlt(const K& key)
nuclear@0:     {   
nuclear@0:         if (pTable == NULL)
nuclear@0:             return;
nuclear@0: 
nuclear@0:         size_t   hashValue = AltHashF()(key);
nuclear@0:         intptr_t index     = hashValue & pTable->SizeMask;
nuclear@0: 
nuclear@0:         Entry*  e = &E(index);
nuclear@0: 
nuclear@0:         // If empty node or occupied by collider, we have nothing to remove.
nuclear@0:         if (e->IsEmpty() || (e->GetCachedHash(pTable->SizeMask) != (size_t)index))
nuclear@0:             return;        
nuclear@0: 
nuclear@0:         // Save index
nuclear@0:         intptr_t naturalIndex = index;
nuclear@0:         intptr_t prevIndex    = -1;
nuclear@0: 
nuclear@0:         while ((e->GetCachedHash(pTable->SizeMask) != (size_t)naturalIndex) || !(e->Value == key))
nuclear@0:         {
nuclear@0:             // Keep looking through the chain.
nuclear@0:             prevIndex   = index;
nuclear@0:             index       = e->NextInChain;
nuclear@0:             if (index == -1)
nuclear@0:                 return; // End of chain, item not found
nuclear@0:             e = &E(index);
nuclear@0:         }
nuclear@0: 
nuclear@0:         // Found it - our item is at index
nuclear@0:         if (naturalIndex == index)
nuclear@0:         {
nuclear@0:             // If we have a follower, move it to us
nuclear@0:             if (!e->IsEndOfChain())
nuclear@0:             {               
nuclear@0:                 Entry*  enext = &E(e->NextInChain);
nuclear@0:                 e->Clear();
nuclear@0:                 new (e) Entry(*enext);
nuclear@0:                 // Point us to the follower's cell that will be cleared
nuclear@0:                 e = enext;
nuclear@0:             }
nuclear@0:         }
nuclear@0:         else
nuclear@0:         {
nuclear@0:             // We are not at natural index, so deal with the prev items next index
nuclear@0:             E(prevIndex).NextInChain = e->NextInChain;
nuclear@0:         }
nuclear@0: 
nuclear@0:         // Clear us, of the follower cell that was moved.
nuclear@0:         e->Clear();
nuclear@0:         pTable->EntryCount --;
nuclear@0:         // Should we check the size to condense hash? ...
nuclear@0:     }
nuclear@0: 
nuclear@0:     // Remove by main key.
nuclear@0:     template<class CRef>
nuclear@0:     void Remove(const CRef& key)
nuclear@0:     {
nuclear@0:         RemoveAlt(key);
nuclear@0:     }
nuclear@0: 
nuclear@0:     // Retrieve the pointer to a value under the given key.
nuclear@0:     //  - If there's no value under the key, then return NULL.    
nuclear@0:     //  - If there is a value, return the pointer.    
nuclear@0:     template<class K>
nuclear@0:     C* Get(const K& key)
nuclear@0:     {
nuclear@0:         intptr_t index = findIndex(key);
nuclear@0:         if (index >= 0)        
nuclear@0:             return &E(index).Value;        
nuclear@0:         return 0;
nuclear@0:     }   
nuclear@0: 
nuclear@0:     template<class K>
nuclear@0:     const C* Get(const K& key) const
nuclear@0:     {
nuclear@0:         intptr_t index = findIndex(key);
nuclear@0:         if (index >= 0)        
nuclear@0:             return &E(index).Value;        
nuclear@0:         return 0;
nuclear@0:     }
nuclear@0: 
nuclear@0:     // Alternative key versions of Get. Used by Hash.
nuclear@0:     template<class K>
nuclear@0:     const C* GetAlt(const K& key) const
nuclear@0:     {
nuclear@0:         intptr_t index = findIndexAlt(key);
nuclear@0:         if (index >= 0)        
nuclear@0:             return &E(index).Value;
nuclear@0:         return 0;
nuclear@0:     }
nuclear@0: 
nuclear@0:     template<class K>
nuclear@0:     C* GetAlt(const K& key)
nuclear@0:     {
nuclear@0:         intptr_t index = findIndexAlt(key);
nuclear@0:         if (index >= 0)        
nuclear@0:             return &E(index).Value;
nuclear@0:         return 0;
nuclear@0:     }   
nuclear@0: 
nuclear@0:     template<class K>
nuclear@0:     bool GetAlt(const K& key, C* pval) const
nuclear@0:     {
nuclear@0:         intptr_t index = findIndexAlt(key);
nuclear@0:         if (index >= 0)
nuclear@0:         {
nuclear@0:             if (pval)
nuclear@0:                 *pval = E(index).Value;
nuclear@0:             return true;
nuclear@0:         }
nuclear@0:         return false;
nuclear@0:     }
nuclear@0: 
nuclear@0: 
nuclear@0:     size_t GetSize() const
nuclear@0:     {
nuclear@0:         return pTable == NULL ? 0 : (size_t)pTable->EntryCount;
nuclear@0:     }
nuclear@0: 	int GetSizeI() const { return (int)GetSize(); }
nuclear@0: 
nuclear@0: 
nuclear@0:     // Resize the HashSet table to fit one more Entry.  Often this
nuclear@0:     // doesn't involve any action.
nuclear@0:     void CheckExpand()
nuclear@0:     {
nuclear@0:         if (pTable == NULL)
nuclear@0:         {
nuclear@0:             // Initial creation of table.  Make a minimum-sized table.
nuclear@0:             setRawCapacity(HashMinSize);
nuclear@0:         }
nuclear@0:         else if (pTable->EntryCount * 5 > (pTable->SizeMask + 1) * 4)
nuclear@0:         {
nuclear@0:             // pTable is more than 5/4 ths full.  Expand.
nuclear@0:             setRawCapacity((pTable->SizeMask + 1) * 2);
nuclear@0:         }
nuclear@0:     }
nuclear@0: 
nuclear@0:     // Hint the bucket count to >= n.
nuclear@0:     void Resize(size_t n)    
nuclear@0:     {
nuclear@0:         // Not really sure what this means in relation to
nuclear@0:         // STLport's hash_map... they say they "increase the
nuclear@0:         // bucket count to at least n" -- but does that mean
nuclear@0:         // their real capacity after Resize(n) is more like
nuclear@0:         // n*2 (since they do linked-list chaining within
nuclear@0:         // buckets?).
nuclear@0:         SetCapacity(n);
nuclear@0:     }
nuclear@0: 
nuclear@0:     // Size the HashSet so that it can comfortably contain the given
nuclear@0:     // number of elements.  If the HashSet already contains more
nuclear@0:     // elements than newSize, then this may be a no-op.
nuclear@0:     void SetCapacity(size_t newSize)
nuclear@0:     {
nuclear@0:         size_t newRawSize = (newSize * 5) / 4;
nuclear@0:         if (newRawSize <= GetSize())
nuclear@0:             return;
nuclear@0:         setRawCapacity(newRawSize);
nuclear@0:     }
nuclear@0: 
nuclear@0:     // Disable inappropriate 'operator ->' warning on MSVC6.
nuclear@0: #ifdef OVR_CC_MSVC
nuclear@0: #if (OVR_CC_MSVC < 1300)
nuclear@0: # pragma warning(disable : 4284)
nuclear@0: #endif
nuclear@0: #endif
nuclear@0: 
nuclear@0:     // Iterator API, like STL.
nuclear@0:     struct ConstIterator
nuclear@0:     {   
nuclear@0:         const C&    operator * () const
nuclear@0:         {            
nuclear@0:             OVR_ASSERT(Index >= 0 && Index <= (intptr_t)pHash->pTable->SizeMask);
nuclear@0:             return pHash->E(Index).Value;
nuclear@0:         }
nuclear@0: 
nuclear@0:         const C*    operator -> () const
nuclear@0:         {
nuclear@0:             OVR_ASSERT(Index >= 0 && Index <= (intptr_t)pHash->pTable->SizeMask);
nuclear@0:             return &pHash->E(Index).Value;
nuclear@0:         }
nuclear@0: 
nuclear@0:         void    operator ++ ()
nuclear@0:         {
nuclear@0:             // Find next non-empty Entry.
nuclear@0:             if (Index <= (intptr_t)pHash->pTable->SizeMask)
nuclear@0:             {
nuclear@0:                 Index++;
nuclear@0:                 while ((size_t)Index <= pHash->pTable->SizeMask &&
nuclear@0:                     pHash->E(Index).IsEmpty())
nuclear@0:                 {
nuclear@0:                     Index++;
nuclear@0:                 }
nuclear@0:             }
nuclear@0:         }
nuclear@0: 
nuclear@0:         bool    operator == (const ConstIterator& it) const
nuclear@0:         {
nuclear@0:             if (IsEnd() && it.IsEnd())
nuclear@0:             {
nuclear@0:                 return true;
nuclear@0:             }
nuclear@0:             else
nuclear@0:             {
nuclear@0:                 return (pHash == it.pHash) && (Index == it.Index);
nuclear@0:             }
nuclear@0:         }
nuclear@0: 
nuclear@0:         bool    operator != (const ConstIterator& it) const
nuclear@0:         {
nuclear@0:             return ! (*this == it);
nuclear@0:         }
nuclear@0: 
nuclear@0: 
nuclear@0:         bool    IsEnd() const
nuclear@0:         {
nuclear@0:             return (pHash == NULL) || 
nuclear@0:                 (pHash->pTable == NULL) || 
nuclear@0:                 (Index > (intptr_t)pHash->pTable->SizeMask);
nuclear@0:         }
nuclear@0: 
nuclear@0:         ConstIterator()
nuclear@0:             : pHash(NULL), Index(0)
nuclear@0:         { }
nuclear@0: 
nuclear@0:     public:
nuclear@0:         // Constructor was intentionally made public to allow create
nuclear@0:         // iterator with arbitrary index.
nuclear@0:         ConstIterator(const SelfType* h, intptr_t index)
nuclear@0:             : pHash(h), Index(index)
nuclear@0:         { }
nuclear@0: 
nuclear@0:         const SelfType* GetContainer() const
nuclear@0:         {
nuclear@0:             return pHash;
nuclear@0:         }
nuclear@0:         intptr_t GetIndex() const
nuclear@0:         {
nuclear@0:             return Index;
nuclear@0:         }
nuclear@0: 
nuclear@0:     protected:
nuclear@0:         friend class HashSetBase<C, HashF, AltHashF, Allocator, Entry>;
nuclear@0: 
nuclear@0:         const SelfType* pHash;
nuclear@0:         intptr_t        Index;
nuclear@0:     };
nuclear@0: 
nuclear@0:     friend struct ConstIterator;
nuclear@0: 
nuclear@0: 
nuclear@0:     // Non-const Iterator; Get most of it from ConstIterator.
nuclear@0:     struct Iterator : public ConstIterator
nuclear@0:     {      
nuclear@0:         // Allow non-const access to entries.
nuclear@0:         C&  operator*() const
nuclear@0:         {            
nuclear@0:             OVR_ASSERT((ConstIterator::pHash) && ConstIterator::pHash->pTable && (ConstIterator::Index >= 0) && (ConstIterator::Index <= (intptr_t)ConstIterator::pHash->pTable->SizeMask));
nuclear@0:             return const_cast<SelfType*>(ConstIterator::pHash)->E(ConstIterator::Index).Value;
nuclear@0:         }    
nuclear@0: 
nuclear@0:         C*  operator->() const 
nuclear@0:         {
nuclear@0:             return &(operator*());
nuclear@0:         }
nuclear@0: 
nuclear@0:         Iterator()
nuclear@0:             : ConstIterator(NULL, 0)
nuclear@0:         { }
nuclear@0: 
nuclear@0:         // Removes current element from Hash
nuclear@0:         void Remove()
nuclear@0:         {
nuclear@0:             RemoveAlt(operator*());
nuclear@0:         }
nuclear@0: 
nuclear@0:         template <class K>
nuclear@0:         void RemoveAlt(const K& key)
nuclear@0:         {
nuclear@0:             SelfType*   phash = const_cast<SelfType*>(ConstIterator::pHash);
nuclear@0:             //Entry*      ee = &phash->E(ConstIterator::Index);
nuclear@0:             //const C&    key = ee->Value;
nuclear@0: 
nuclear@0:             size_t      hashValue = AltHashF()(key);
nuclear@0:             intptr_t    index     = hashValue & phash->pTable->SizeMask;
nuclear@0: 
nuclear@0:             Entry*      e = &phash->E(index);
nuclear@0: 
nuclear@0:             // If empty node or occupied by collider, we have nothing to remove.
nuclear@0:             if (e->IsEmpty() || (e->GetCachedHash(phash->pTable->SizeMask) != (size_t)index))
nuclear@0:                 return;        
nuclear@0: 
nuclear@0:             // Save index
nuclear@0:             intptr_t   naturalIndex = index;
nuclear@0:             intptr_t   prevIndex    = -1;
nuclear@0: 
nuclear@0:             while ((e->GetCachedHash(phash->pTable->SizeMask) != (size_t)naturalIndex) || !(e->Value == key))
nuclear@0:             {
nuclear@0:                 // Keep looking through the chain.
nuclear@0:                 prevIndex   = index;
nuclear@0:                 index       = e->NextInChain;
nuclear@0:                 if (index == -1)
nuclear@0:                     return; // End of chain, item not found
nuclear@0:                 e = &phash->E(index);
nuclear@0:             }
nuclear@0: 
nuclear@0:             if (index == (intptr_t)ConstIterator::Index)
nuclear@0:             {
nuclear@0:                 // Found it - our item is at index
nuclear@0:                 if (naturalIndex == index)
nuclear@0:                 {
nuclear@0:                     // If we have a follower, move it to us
nuclear@0:                     if (!e->IsEndOfChain())
nuclear@0:                     {               
nuclear@0:                         Entry*  enext = &phash->E(e->NextInChain);
nuclear@0:                         e->Clear();
nuclear@0:                         new (e) Entry(*enext);
nuclear@0:                         // Point us to the follower's cell that will be cleared
nuclear@0:                         e = enext;
nuclear@0:                         --ConstIterator::Index;
nuclear@0:                     }
nuclear@0:                 }
nuclear@0:                 else
nuclear@0:                 {
nuclear@0:                     // We are not at natural index, so deal with the prev items next index
nuclear@0:                     phash->E(prevIndex).NextInChain = e->NextInChain;
nuclear@0:                 }
nuclear@0: 
nuclear@0:                 // Clear us, of the follower cell that was moved.
nuclear@0:                 e->Clear();
nuclear@0:                 phash->pTable->EntryCount --;
nuclear@0:             }
nuclear@0:             else 
nuclear@0:                 OVR_ASSERT(0); //?
nuclear@0:         }
nuclear@0: 
nuclear@0:     private:
nuclear@0:         friend class HashSetBase<C, HashF, AltHashF, Allocator, Entry>;
nuclear@0: 
nuclear@0:         Iterator(SelfType* h, intptr_t i0)
nuclear@0:             : ConstIterator(h, i0)
nuclear@0:         { }
nuclear@0:     };
nuclear@0: 
nuclear@0:     friend struct Iterator;
nuclear@0: 
nuclear@0:     Iterator    Begin()
nuclear@0:     {
nuclear@0:         if (pTable == 0)
nuclear@0:             return Iterator(NULL, 0);
nuclear@0: 
nuclear@0:         // Scan till we hit the First valid Entry.
nuclear@0:         size_t i0 = 0;
nuclear@0:         while (i0 <= pTable->SizeMask && E(i0).IsEmpty())
nuclear@0:         {
nuclear@0:             i0++;
nuclear@0:         }
nuclear@0:         return Iterator(this, i0);
nuclear@0:     }
nuclear@0:     Iterator        End()           { return Iterator(NULL, 0); }
nuclear@0: 
nuclear@0:     ConstIterator   Begin() const   { return const_cast<SelfType*>(this)->Begin();     }
nuclear@0:     ConstIterator   End() const     { return const_cast<SelfType*>(this)->End();   }
nuclear@0: 
nuclear@0:     template<class K>
nuclear@0:     Iterator Find(const K& key)
nuclear@0:     {
nuclear@0:         intptr_t index = findIndex(key);
nuclear@0:         if (index >= 0)        
nuclear@0:             return Iterator(this, index);        
nuclear@0:         return Iterator(NULL, 0);
nuclear@0:     }
nuclear@0: 
nuclear@0:     template<class K>
nuclear@0:     Iterator FindAlt(const K& key)
nuclear@0:     {
nuclear@0:         intptr_t index = findIndexAlt(key);
nuclear@0:         if (index >= 0)        
nuclear@0:             return Iterator(this, index);        
nuclear@0:         return Iterator(NULL, 0);
nuclear@0:     }
nuclear@0: 
nuclear@0:     template<class K>
nuclear@0:     ConstIterator Find(const K& key) const       { return const_cast<SelfType*>(this)->Find(key); }
nuclear@0: 
nuclear@0:     template<class K>
nuclear@0:     ConstIterator FindAlt(const K& key) const    { return const_cast<SelfType*>(this)->FindAlt(key); }
nuclear@0: 
nuclear@0: private:
nuclear@0:     // Find the index of the matching Entry.  If no match, then return -1.
nuclear@0:     template<class K>
nuclear@0:     intptr_t findIndex(const K& key) const
nuclear@0:     {
nuclear@0:         if (pTable == NULL)
nuclear@0:             return -1;
nuclear@0:         size_t hashValue = HashF()(key) & pTable->SizeMask;
nuclear@0:         return findIndexCore(key, hashValue);
nuclear@0:     }
nuclear@0: 
nuclear@0:     template<class K>
nuclear@0:     intptr_t findIndexAlt(const K& key) const
nuclear@0:     {
nuclear@0:         if (pTable == NULL)
nuclear@0:             return -1;
nuclear@0:         size_t hashValue = AltHashF()(key) & pTable->SizeMask;
nuclear@0:         return findIndexCore(key, hashValue);
nuclear@0:     }
nuclear@0: 
nuclear@0:     // Find the index of the matching Entry.  If no match, then return -1.
nuclear@0:     template<class K>
nuclear@0:     intptr_t findIndexCore(const K& key, size_t hashValue) const
nuclear@0:     {
nuclear@0:         // Table must exist.
nuclear@0:         OVR_ASSERT(pTable != 0);
nuclear@0:         // Hash key must be 'and-ed' by the caller.
nuclear@0:         OVR_ASSERT((hashValue & ~pTable->SizeMask) == 0);
nuclear@0: 
nuclear@0:         size_t          index = hashValue;
nuclear@0:         const Entry*    e     = &E(index);
nuclear@0: 
nuclear@0:         // If empty or occupied by a collider, not found.
nuclear@0:         if (e->IsEmpty() || (e->GetCachedHash(pTable->SizeMask) != index))
nuclear@0:             return -1;
nuclear@0: 
nuclear@0:         while(1)
nuclear@0:         {
nuclear@0:             OVR_ASSERT(e->GetCachedHash(pTable->SizeMask) == hashValue);
nuclear@0: 
nuclear@0:             if (e->GetCachedHash(pTable->SizeMask) == hashValue && e->Value == key)
nuclear@0:             {
nuclear@0:                 // Found it.
nuclear@0:                 return index;
nuclear@0:             }
nuclear@0:             // Values can not be equal at this point.
nuclear@0:             // That would mean that the hash key for the same value differs.
nuclear@0:             OVR_ASSERT(!(e->Value == key));
nuclear@0: 
nuclear@0:             // Keep looking through the chain.
nuclear@0:             index = e->NextInChain;
nuclear@0:             if (index == (size_t)-1)
nuclear@0:                 break; // end of chain
nuclear@0: 
nuclear@0:             e = &E(index);
nuclear@0:             OVR_ASSERT(!e->IsEmpty());
nuclear@0:         }
nuclear@0:         return -1;
nuclear@0:     }
nuclear@0: 
nuclear@0: 
nuclear@0:     // Add a new value to the HashSet table, under the specified key.
nuclear@0:     template<class CRef>
nuclear@0:     void add(const CRef& key, size_t hashValue)
nuclear@0:     {
nuclear@0:         CheckExpand();
nuclear@0:         hashValue &= pTable->SizeMask;
nuclear@0: 
nuclear@0:         pTable->EntryCount++;
nuclear@0: 
nuclear@0:         intptr_t   index        = hashValue;
nuclear@0:         Entry*  naturalEntry = &(E(index));
nuclear@0: 
nuclear@0:         if (naturalEntry->IsEmpty())
nuclear@0:         {
nuclear@0:             // Put the new Entry in.
nuclear@0:             new (naturalEntry) Entry(key, -1);
nuclear@0:         }
nuclear@0:         else
nuclear@0:         {
nuclear@0:             // Find a blank spot.
nuclear@0:             intptr_t blankIndex = index;
nuclear@0:             do {
nuclear@0:                 blankIndex = (blankIndex + 1) & pTable->SizeMask;
nuclear@0:             } while(!E(blankIndex).IsEmpty());
nuclear@0: 
nuclear@0:             Entry*  blankEntry = &E(blankIndex);
nuclear@0: 
nuclear@0:             if (naturalEntry->GetCachedHash(pTable->SizeMask) == (size_t)index)
nuclear@0:             {
nuclear@0:                 // Collision.  Link into this chain.
nuclear@0: 
nuclear@0:                 // Move existing list head.
nuclear@0:                 new (blankEntry) Entry(*naturalEntry);    // placement new, copy ctor
nuclear@0: 
nuclear@0:                 // Put the new info in the natural Entry.
nuclear@0:                 naturalEntry->Value       = key;
nuclear@0:                 naturalEntry->NextInChain = blankIndex;
nuclear@0:             }
nuclear@0:             else
nuclear@0:             {
nuclear@0:                 // Existing Entry does not naturally
nuclear@0:                 // belong in this slot.  Existing
nuclear@0:                 // Entry must be moved.
nuclear@0: 
nuclear@0:                 // Find natural location of collided element (i.e. root of chain)
nuclear@0:                 intptr_t collidedIndex = naturalEntry->GetCachedHash(pTable->SizeMask);
nuclear@0:                 OVR_ASSERT(collidedIndex >= 0 && collidedIndex <= (intptr_t)pTable->SizeMask);
nuclear@0:                 for (;;)
nuclear@0:                 {
nuclear@0:                     Entry*  e = &E(collidedIndex);
nuclear@0:                     if (e->NextInChain == index)
nuclear@0:                     {
nuclear@0:                         // Here's where we need to splice.
nuclear@0:                         new (blankEntry) Entry(*naturalEntry);
nuclear@0:                         e->NextInChain = blankIndex;
nuclear@0:                         break;
nuclear@0:                     }
nuclear@0:                     collidedIndex = e->NextInChain;
nuclear@0:                     OVR_ASSERT(collidedIndex >= 0 && collidedIndex <= (intptr_t)pTable->SizeMask);
nuclear@0:                 }
nuclear@0: 
nuclear@0:                 // Put the new data in the natural Entry.
nuclear@0:                 naturalEntry->Value       = key;
nuclear@0:                 naturalEntry->NextInChain = -1;                
nuclear@0:             }            
nuclear@0:         }
nuclear@0: 
nuclear@0:         // Record hash value: has effect only if cached node is used.
nuclear@0:         naturalEntry->SetCachedHash(hashValue);
nuclear@0:     }
nuclear@0: 
nuclear@0:     // Index access helpers.
nuclear@0:     Entry& E(size_t index)
nuclear@0:     {
nuclear@0:         // Must have pTable and access needs to be within bounds.
nuclear@0:         OVR_ASSERT(index <= pTable->SizeMask);
nuclear@0:         return *(((Entry*) (pTable + 1)) + index);
nuclear@0:     }
nuclear@0:     const Entry& E(size_t index) const
nuclear@0:     {        
nuclear@0:         OVR_ASSERT(index <= pTable->SizeMask);
nuclear@0:         return *(((Entry*) (pTable + 1)) + index);
nuclear@0:     }
nuclear@0: 
nuclear@0: 
nuclear@0:     // Resize the HashSet table to the given size (Rehash the
nuclear@0:     // contents of the current table).  The arg is the number of
nuclear@0:     // HashSet table entries, not the number of elements we should
nuclear@0:     // actually contain (which will be less than this).
nuclear@0:     void    setRawCapacity(size_t newSize)    
nuclear@0:     {
nuclear@0:         if (newSize == 0)
nuclear@0:         {
nuclear@0:             // Special case.
nuclear@0:             Clear();
nuclear@0:             return;
nuclear@0:         }
nuclear@0: 
nuclear@0:         // Minimum size; don't incur rehashing cost when expanding
nuclear@0:         // very small tables. Not that we perform this check before 
nuclear@0:         // 'log2f' call to avoid fp exception with newSize == 1.
nuclear@0:         if (newSize < HashMinSize)        
nuclear@0:             newSize = HashMinSize;       
nuclear@0:         else
nuclear@0:         {
nuclear@0:             // Force newSize to be a power of two.
nuclear@0:             int bits = Alg::UpperBit(newSize-1) + 1; // Chop( Log2f((float)(newSize-1)) + 1);
nuclear@0:             OVR_ASSERT((size_t(1) << bits) >= newSize);
nuclear@0:             newSize = size_t(1) << bits;
nuclear@0:         }
nuclear@0: 
nuclear@0:         SelfType  newHash;
nuclear@0:         newHash.pTable = (TableType*)
nuclear@0:             Allocator::Alloc(                
nuclear@0:                 sizeof(TableType) + sizeof(Entry) * newSize);
nuclear@0:         // Need to do something on alloc failure!
nuclear@0:         OVR_ASSERT(newHash.pTable);
nuclear@0: 
nuclear@0:         newHash.pTable->EntryCount = 0;
nuclear@0:         newHash.pTable->SizeMask = newSize - 1;
nuclear@0:         size_t i, n;
nuclear@0: 
nuclear@0:         // Mark all entries as empty.
nuclear@0:         for (i = 0; i < newSize; i++)
nuclear@0:             newHash.E(i).NextInChain = -2;
nuclear@0: 
nuclear@0:         // Copy stuff to newHash
nuclear@0:         if (pTable)
nuclear@0:         {            
nuclear@0:             for (i = 0, n = pTable->SizeMask; i <= n; i++)
nuclear@0:             {
nuclear@0:                 Entry*  e = &E(i);
nuclear@0:                 if (e->IsEmpty() == false)
nuclear@0:                 {
nuclear@0:                     // Insert old Entry into new HashSet.
nuclear@0:                     newHash.Add(e->Value);
nuclear@0:                     // placement delete of old element
nuclear@0:                     e->Clear();
nuclear@0:                 }
nuclear@0:             }
nuclear@0: 
nuclear@0:             // Delete our old data buffer.
nuclear@0:             Allocator::Free(pTable);
nuclear@0:         }
nuclear@0: 
nuclear@0:         // Steal newHash's data.
nuclear@0:         pTable = newHash.pTable;
nuclear@0:         newHash.pTable = NULL;
nuclear@0:     }
nuclear@0: 
nuclear@0:     struct TableType
nuclear@0:     {
nuclear@0:         size_t EntryCount;
nuclear@0:         size_t SizeMask;
nuclear@0:         // Entry array follows this structure
nuclear@0:         // in memory.
nuclear@0:     };
nuclear@0:     TableType*  pTable;
nuclear@0: };
nuclear@0: 
nuclear@0: 
nuclear@0: 
nuclear@0: //-----------------------------------------------------------------------------------
nuclear@0: template<class C, class HashF = FixedSizeHash<C>,
nuclear@0:          class AltHashF = HashF, 
nuclear@0:          class Allocator = ContainerAllocator<C>,
nuclear@0:          class Entry = HashsetCachedEntry<C, HashF> >
nuclear@0: class HashSet : public HashSetBase<C, HashF, AltHashF, Allocator, Entry>
nuclear@0: {
nuclear@0: public:
nuclear@0:     typedef HashSetBase<C, HashF, AltHashF, Allocator, Entry> BaseType;
nuclear@0:     typedef HashSet<C, HashF, AltHashF, Allocator, Entry>     SelfType;
nuclear@0: 
nuclear@0:     HashSet()                                      {   }
nuclear@0:     HashSet(int sizeHint) : BaseType(sizeHint)     {   }
nuclear@0:     HashSet(const SelfType& src) : BaseType(src)   {   }
nuclear@0:     ~HashSet()                                     {   }
nuclear@0: 
nuclear@0:     void operator = (const SelfType& src)   { BaseType::Assign(src); }
nuclear@0: 
nuclear@0:     // Set a new or existing value under the key, to the value.
nuclear@0:     // Pass a different class of 'key' so that assignment reference object
nuclear@0:     // can be passed instead of the actual object.
nuclear@0:     template<class CRef>
nuclear@0:     void Set(const CRef& key)
nuclear@0:     {
nuclear@0:         BaseType::Set(key);
nuclear@0:     }
nuclear@0: 
nuclear@0:     template<class CRef>
nuclear@0:     inline void Add(const CRef& key)
nuclear@0:     {
nuclear@0:         BaseType::Add(key);
nuclear@0:     }
nuclear@0: 
nuclear@0:     // Hint the bucket count to >= n.
nuclear@0:     void Resize(size_t n)    
nuclear@0:     {
nuclear@0:         BaseType::SetCapacity(n);
nuclear@0:     }
nuclear@0: 
nuclear@0:     // Size the HashSet so that it can comfortably contain the given
nuclear@0:     // number of elements.  If the HashSet already contains more
nuclear@0:     // elements than newSize, then this may be a no-op.
nuclear@0:     void SetCapacity(size_t newSize)
nuclear@0:     {
nuclear@0:         BaseType::SetCapacity(newSize);
nuclear@0:     }
nuclear@0: 
nuclear@0: };
nuclear@0: 
nuclear@0: // HashSet with uncached hash code; declared for convenience.
nuclear@0: template<class C, class HashF = FixedSizeHash<C>,
nuclear@0:                   class AltHashF = HashF,
nuclear@0:                   class Allocator = ContainerAllocator<C> >
nuclear@0: class HashSetUncached : public HashSet<C, HashF, AltHashF, Allocator, HashsetEntry<C, HashF> >
nuclear@0: {
nuclear@0: public:
nuclear@0:     
nuclear@0:     typedef HashSetUncached<C, HashF, AltHashF, Allocator>                  SelfType;
nuclear@0:     typedef HashSet<C, HashF, AltHashF, Allocator, HashsetEntry<C, HashF> > BaseType;
nuclear@0: 
nuclear@0:     // Delegated constructors.
nuclear@0:     HashSetUncached()                                        { }
nuclear@0:     HashSetUncached(int sizeHint) : BaseType(sizeHint)       { }
nuclear@0:     HashSetUncached(const SelfType& src) : BaseType(src)     { }
nuclear@0:     ~HashSetUncached()                                       { }
nuclear@0:     
nuclear@0:     void    operator = (const SelfType& src)
nuclear@0:     {
nuclear@0:         BaseType::operator = (src);
nuclear@0:     }
nuclear@0: };
nuclear@0: 
nuclear@0: 
nuclear@0: //-----------------------------------------------------------------------------------
nuclear@0: // ***** Hash hash table implementation
nuclear@0: 
nuclear@0: // Node for Hash - necessary so that Hash can delegate its implementation
nuclear@0: // to HashSet.
nuclear@0: template<class C, class U, class HashF>
nuclear@0: struct HashNode
nuclear@0: {
nuclear@0:     typedef HashNode<C, U, HashF>   SelfType;
nuclear@0:     typedef C                       FirstType;
nuclear@0:     typedef U                       SecondType;
nuclear@0: 
nuclear@0:     C   First;
nuclear@0:     U   Second;
nuclear@0: 
nuclear@0:     // NodeRef is used to allow passing of elements into HashSet
nuclear@0:     // without using a temporary object.
nuclear@0:     struct NodeRef
nuclear@0:     {
nuclear@0:         const C*   pFirst;
nuclear@0:         const U*   pSecond;
nuclear@0: 
nuclear@0:         NodeRef(const C& f, const U& s) : pFirst(&f), pSecond(&s) { }
nuclear@0:         NodeRef(const NodeRef& src)     : pFirst(src.pFirst), pSecond(src.pSecond) { }
nuclear@0: 
nuclear@0:         // Enable computation of ghash_node_hashf.
nuclear@0:         inline size_t GetHash() const            { return HashF()(*pFirst); } 
nuclear@0:         // Necessary conversion to allow HashNode::operator == to work.
nuclear@0:         operator const C& () const              { return *pFirst; }
nuclear@0:     };
nuclear@0: 
nuclear@0:     // Note: No default constructor is necessary.
nuclear@0:      HashNode(const HashNode& src) : First(src.First), Second(src.Second)    { }
nuclear@0:      HashNode(const NodeRef& src) : First(*src.pFirst), Second(*src.pSecond)  { }
nuclear@0:     void operator = (const NodeRef& src)  { First  = *src.pFirst; Second = *src.pSecond; }
nuclear@0: 
nuclear@0:     template<class K>
nuclear@0:     bool operator == (const K& src) const   { return (First == src); }
nuclear@0: 
nuclear@0:     template<class K>
nuclear@0:     static size_t CalcHash(const K& data)   { return HashF()(data); }
nuclear@0:     inline size_t GetHash() const           { return HashF()(First); }
nuclear@0: 
nuclear@0:     // Hash functors used with this node. A separate functor is used for alternative
nuclear@0:     // key lookup so that it does not need to access the '.First' element.    
nuclear@0:     struct NodeHashF
nuclear@0:     {    
nuclear@0:         template<class K>
nuclear@0:         size_t operator()(const K& data) const { return data.GetHash(); } 
nuclear@0:     };    
nuclear@0:     struct NodeAltHashF
nuclear@0:     {
nuclear@0:         template<class K>
nuclear@0:         size_t operator()(const K& data) const { return HashNode<C,U,HashF>::CalcHash(data); }
nuclear@0:     };
nuclear@0: };
nuclear@0: 
nuclear@0: 
nuclear@0: 
nuclear@0: // **** Extra hashset_entry types to allow NodeRef construction.
nuclear@0: 
nuclear@0: // The big difference between the below types and the ones used in hash_set is that
nuclear@0: // these allow initializing the node with 'typename C::NodeRef& keyRef', which
nuclear@0: // is critical to avoid temporary node allocation on stack when using placement new.
nuclear@0: 
nuclear@0: // Compact hash table Entry type that re-computes hash keys during hash traversal.
nuclear@0: // Good to use if the hash function is cheap or the hash value is already cached in C.
nuclear@0: template<class C, class HashF>
nuclear@0: class HashsetNodeEntry
nuclear@0: {
nuclear@0: public:
nuclear@0:     // Internal chaining for collisions.
nuclear@0:     intptr_t NextInChain;
nuclear@0:     C     Value;
nuclear@0: 
nuclear@0:     HashsetNodeEntry()
nuclear@0:         : NextInChain(-2) { }
nuclear@0:     HashsetNodeEntry(const HashsetNodeEntry& e)
nuclear@0:         : NextInChain(e.NextInChain), Value(e.Value) { }
nuclear@0:     HashsetNodeEntry(const C& key, intptr_t next)
nuclear@0:         : NextInChain(next), Value(key) { }    
nuclear@0:     HashsetNodeEntry(const typename C::NodeRef& keyRef, intptr_t next)
nuclear@0:         : NextInChain(next), Value(keyRef) { }
nuclear@0: 
nuclear@0:     bool    IsEmpty() const             { return NextInChain == -2;  }
nuclear@0:     bool    IsEndOfChain() const        { return NextInChain == -1;  }
nuclear@0:     size_t  GetCachedHash(size_t maskValue) const  { return HashF()(Value) & maskValue; }
nuclear@0:     void    SetCachedHash(size_t hashValue)        { OVR_UNUSED(hashValue); }
nuclear@0: 
nuclear@0:     void    Clear()
nuclear@0:     {        
nuclear@0:         Value.~C(); // placement delete
nuclear@0:         NextInChain = -2;
nuclear@0:     }
nuclear@0:     // Free is only used from dtor of hash; Clear is used during regular operations:
nuclear@0:     // assignment, hash reallocations, value reassignments, so on.
nuclear@0:     void    Free() { Clear(); }
nuclear@0: };
nuclear@0: 
nuclear@0: // Hash table Entry type that caches the Entry hash value for nodes, so that it
nuclear@0: // does not need to be re-computed during access.
nuclear@0: template<class C, class HashF>
nuclear@0: class HashsetCachedNodeEntry
nuclear@0: {
nuclear@0: public:
nuclear@0:     // Internal chaining for collisions.
nuclear@0:     intptr_t NextInChain;
nuclear@0:     size_t HashValue;
nuclear@0:     C     Value;
nuclear@0: 
nuclear@0:     HashsetCachedNodeEntry()
nuclear@0:         : NextInChain(-2) { }
nuclear@0:     HashsetCachedNodeEntry(const HashsetCachedNodeEntry& e)
nuclear@0:         : NextInChain(e.NextInChain), HashValue(e.HashValue), Value(e.Value) { }
nuclear@0:     HashsetCachedNodeEntry(const C& key, intptr_t next)
nuclear@0:         : NextInChain(next), Value(key) { }
nuclear@0:     HashsetCachedNodeEntry(const typename C::NodeRef& keyRef, intptr_t next)
nuclear@0:         : NextInChain(next), Value(keyRef) { }
nuclear@0: 
nuclear@0:     bool    IsEmpty() const            { return NextInChain == -2;  }
nuclear@0:     bool    IsEndOfChain() const       { return NextInChain == -1;  }
nuclear@0:     size_t  GetCachedHash(size_t maskValue) const  { OVR_UNUSED(maskValue); return HashValue; }
nuclear@0:     void    SetCachedHash(size_t hashValue)        { HashValue = hashValue; }
nuclear@0: 
nuclear@0:     void    Clear()
nuclear@0:     {
nuclear@0:         Value.~C();
nuclear@0:         NextInChain = -2;
nuclear@0:     }
nuclear@0:     // Free is only used from dtor of hash; Clear is used during regular operations:
nuclear@0:     // assignment, hash reallocations, value reassignments, so on.
nuclear@0:     void    Free() { Clear(); }
nuclear@0: };
nuclear@0: 
nuclear@0: 
nuclear@0: //-----------------------------------------------------------------------------------
nuclear@0: template<class C, class U,
nuclear@0:          class HashF = FixedSizeHash<C>,
nuclear@0:          class Allocator = ContainerAllocator<C>,
nuclear@0:          class HashNode = OVR::HashNode<C,U,HashF>,
nuclear@0:          class Entry = HashsetCachedNodeEntry<HashNode, typename HashNode::NodeHashF>,
nuclear@0:          class Container =  HashSet<HashNode, typename HashNode::NodeHashF,
nuclear@0:              typename HashNode::NodeAltHashF, Allocator,
nuclear@0:              Entry> >
nuclear@0: class Hash
nuclear@0: {
nuclear@0: public:
nuclear@0:     OVR_MEMORY_REDEFINE_NEW(Hash)
nuclear@0: 
nuclear@0:     // Types used for hash_set.
nuclear@0:     typedef U                                                           ValueType;
nuclear@0:     typedef Hash<C, U, HashF, Allocator, HashNode, Entry, Container>    SelfType;
nuclear@0: 
nuclear@0:     // Actual hash table itself, implemented as hash_set.
nuclear@0:     Container   mHash;
nuclear@0: 
nuclear@0: public:
nuclear@0:     Hash()     {  }
nuclear@0:     Hash(int sizeHint) : mHash(sizeHint)                        { }
nuclear@0:     Hash(const SelfType& src) : mHash(src.mHash)                { }
nuclear@0:     ~Hash()                                                     { }
nuclear@0: 
nuclear@0:     void    operator = (const SelfType& src)    { mHash = src.mHash; }
nuclear@0: 
nuclear@0:     // Remove all entries from the Hash table.
nuclear@0:     inline void    Clear() { mHash.Clear(); }
nuclear@0:     // Returns true if the Hash is empty.
nuclear@0:     inline bool    IsEmpty() const { return mHash.IsEmpty(); }
nuclear@0: 
nuclear@0:     // Access (set).
nuclear@0:     inline void    Set(const C& key, const U& value)
nuclear@0:     {
nuclear@0:         typename HashNode::NodeRef e(key, value);
nuclear@0:         mHash.Set(e);
nuclear@0:     }
nuclear@0:     inline void    Add(const C& key, const U& value)
nuclear@0:     {
nuclear@0:         typename HashNode::NodeRef e(key, value);
nuclear@0:         mHash.Add(e);
nuclear@0:     }
nuclear@0: 
nuclear@0:     // Removes an element by clearing its Entry.
nuclear@0:     inline void     Remove(const C& key)
nuclear@0:     {   
nuclear@0:         mHash.RemoveAlt(key);
nuclear@0:     }
nuclear@0:     template<class K>
nuclear@0:     inline void     RemoveAlt(const K& key)
nuclear@0:     {   
nuclear@0:         mHash.RemoveAlt(key);
nuclear@0:     }
nuclear@0: 
nuclear@0:     // Retrieve the value under the given key.    
nuclear@0:     //  - If there's no value under the key, then return false and leave *pvalue alone.
nuclear@0:     //  - If there is a value, return true, and Set *Pvalue to the Entry's value.
nuclear@0:     //  - If value == NULL, return true or false according to the presence of the key.    
nuclear@0:     bool    Get(const C& key, U* pvalue) const   
nuclear@0:     {
nuclear@0:         const HashNode* p = mHash.GetAlt(key);
nuclear@0:         if (p)
nuclear@0:         {
nuclear@0:             if (pvalue)
nuclear@0:                 *pvalue = p->Second;
nuclear@0:             return true;
nuclear@0:         }
nuclear@0:         return false;
nuclear@0:     }
nuclear@0: 
nuclear@0:     template<class K>
nuclear@0:     bool    GetAlt(const K& key, U* pvalue) const   
nuclear@0:     {
nuclear@0:         const HashNode* p = mHash.GetAlt(key);
nuclear@0:         if (p)
nuclear@0:         {
nuclear@0:             if (pvalue)
nuclear@0:                 *pvalue = p->Second;
nuclear@0:             return true;
nuclear@0:         }
nuclear@0:         return false;
nuclear@0:     }
nuclear@0: 
nuclear@0:     // Retrieve the pointer to a value under the given key.    
nuclear@0:     //  - If there's no value under the key, then return NULL.    
nuclear@0:     //  - If there is a value, return the pointer.    
nuclear@0:     inline U*  Get(const C& key)
nuclear@0:     {
nuclear@0:         HashNode* p = mHash.GetAlt(key);
nuclear@0:         return p ? &p->Second : 0;
nuclear@0:     }
nuclear@0:     inline const U* Get(const C& key) const
nuclear@0:     {
nuclear@0:         const HashNode* p = mHash.GetAlt(key);
nuclear@0:         return p ? &p->Second : 0;
nuclear@0:     }
nuclear@0: 
nuclear@0:     template<class K>
nuclear@0:     inline U*  GetAlt(const K& key)
nuclear@0:     {
nuclear@0:         HashNode* p = mHash.GetAlt(key);
nuclear@0:         return p ? &p->Second : 0;
nuclear@0:     }
nuclear@0:     template<class K>
nuclear@0:     inline const U* GetAlt(const K& key) const
nuclear@0:     {
nuclear@0:         const HashNode* p = mHash.GetAlt(key);
nuclear@0:         return p ? &p->Second : 0;
nuclear@0:     }
nuclear@0: 
nuclear@0:     // Sizing methods - delegate to Hash.
nuclear@0:     inline size_t  GetSize() const              { return mHash.GetSize(); }    
nuclear@0: 	inline int     GetSizeI() const             { return (int)GetSize(); }
nuclear@0: 	inline void    Resize(size_t n)              { mHash.Resize(n); }
nuclear@0:     inline void    SetCapacity(size_t newSize)   { mHash.SetCapacity(newSize); }
nuclear@0: 
nuclear@0:     // Iterator API, like STL.
nuclear@0:     typedef typename Container::ConstIterator   ConstIterator;
nuclear@0:     typedef typename Container::Iterator        Iterator;
nuclear@0: 
nuclear@0:     inline Iterator        Begin()              { return mHash.Begin(); }
nuclear@0:     inline Iterator        End()                { return mHash.End(); }
nuclear@0:     inline ConstIterator   Begin() const        { return mHash.Begin(); }
nuclear@0:     inline ConstIterator   End() const          { return mHash.End();   }
nuclear@0: 
nuclear@0:     Iterator        Find(const C& key)          { return mHash.FindAlt(key);  }
nuclear@0:     ConstIterator   Find(const C& key) const    { return mHash.FindAlt(key);  }
nuclear@0: 
nuclear@0:     template<class K>
nuclear@0:     Iterator        FindAlt(const K& key)       { return mHash.FindAlt(key);  }
nuclear@0:     template<class K>
nuclear@0:     ConstIterator   FindAlt(const K& key) const { return mHash.FindAlt(key);  }
nuclear@0: };
nuclear@0: 
nuclear@0: 
nuclear@0: 
nuclear@0: // Hash with uncached hash code; declared for convenience.
nuclear@0: template<class C, class U, class HashF = FixedSizeHash<C>, class Allocator = ContainerAllocator<C> >
nuclear@0: class HashUncached
nuclear@0:     : public Hash<C, U, HashF, Allocator, HashNode<C,U,HashF>,
nuclear@0:                    HashsetNodeEntry<HashNode<C,U,HashF>, typename HashNode<C,U,HashF>::NodeHashF> >
nuclear@0: {
nuclear@0: public:
nuclear@0:     typedef HashUncached<C, U, HashF, Allocator>                SelfType;
nuclear@0:     typedef Hash<C, U, HashF, Allocator, HashNode<C,U,HashF>,
nuclear@0:                  HashsetNodeEntry<HashNode<C,U,HashF>,
nuclear@0:                  typename HashNode<C,U,HashF>::NodeHashF> >     BaseType;
nuclear@0: 
nuclear@0:     // Delegated constructors.
nuclear@0:     HashUncached()                                        { }
nuclear@0:     HashUncached(int sizeHint) : BaseType(sizeHint)       { }
nuclear@0:     HashUncached(const SelfType& src) : BaseType(src)     { }
nuclear@0:     ~HashUncached()                                       { }
nuclear@0:     void operator = (const SelfType& src)                 { BaseType::operator = (src); }
nuclear@0: };
nuclear@0: 
nuclear@0: 
nuclear@0: 
nuclear@0: // And identity hash in which keys serve as hash value. Can be uncached,
nuclear@0: // since hash computation is assumed cheap.
nuclear@0: template<class C, class U, class Allocator = ContainerAllocator<C>, class HashF = IdentityHash<C> >
nuclear@0: class HashIdentity
nuclear@0:     : public HashUncached<C, U, HashF, Allocator>
nuclear@0: {
nuclear@0: public:
nuclear@0:     typedef HashIdentity<C, U, Allocator, HashF> SelfType;
nuclear@0:     typedef HashUncached<C, U, HashF, Allocator> BaseType;
nuclear@0: 
nuclear@0:     // Delegated constructors.
nuclear@0:     HashIdentity()                                        { }
nuclear@0:     HashIdentity(int sizeHint) : BaseType(sizeHint)       { }
nuclear@0:     HashIdentity(const SelfType& src) : BaseType(src)     { }
nuclear@0:     ~HashIdentity()                                       { }
nuclear@0:     void operator = (const SelfType& src)                 { BaseType::operator = (src); }
nuclear@0: };
nuclear@0: 
nuclear@0: 
nuclear@0: } // OVR
nuclear@0: 
nuclear@0: 
nuclear@0: #ifdef OVR_DEFINE_NEW
nuclear@0: #define new OVR_DEFINE_NEW
nuclear@0: #endif
nuclear@0: 
nuclear@0: #endif