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