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