diff options
Diffstat (limited to 'LibOVR/Src/Kernel/OVR_Hash.h')
| -rw-r--r-- | LibOVR/Src/Kernel/OVR_Hash.h | 1291 |
1 files changed, 1291 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..6667ac2 --- /dev/null +++ b/LibOVR/Src/Kernel/OVR_Hash.h @@ -0,0 +1,1291 @@ +/************************************************************************************
+
+PublicHeader: None
+Filename : OVR_Hash.h
+Content : Template hash-table/set implementation
+Created : September 19, 2012
+Notes :
+
+Copyright : Copyright 2012 Oculus VR, Inc. All Rights reserved.
+
+Use of this software is subject to the terms of the Oculus license
+agreement provided at the time of installation or download, or which
+otherwise accompanies this software in either electronic or hard copy form.
+
+************************************************************************************/
+
+#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
|