summaryrefslogtreecommitdiffhomepage
path: root/ovr_sdk_win_23.0.0/LibOVRKernel/Src/Kernel/OVR_Hash.h
diff options
context:
space:
mode:
Diffstat (limited to 'ovr_sdk_win_23.0.0/LibOVRKernel/Src/Kernel/OVR_Hash.h')
-rw-r--r--ovr_sdk_win_23.0.0/LibOVRKernel/Src/Kernel/OVR_Hash.h1261
1 files changed, 1261 insertions, 0 deletions
diff --git a/ovr_sdk_win_23.0.0/LibOVRKernel/Src/Kernel/OVR_Hash.h b/ovr_sdk_win_23.0.0/LibOVRKernel/Src/Kernel/OVR_Hash.h
new file mode 100644
index 0000000..7f0f38d
--- /dev/null
+++ b/ovr_sdk_win_23.0.0/LibOVRKernel/Src/Kernel/OVR_Hash.h
@@ -0,0 +1,1261 @@
+/************************************************************************************
+
+PublicHeader: None
+Filename : OVR_Hash.h
+Content : Template hash-table/set implementation
+Created : September 19, 2012
+Notes :
+
+Copyright : Copyright (c) Facebook Technologies, LLC and its affiliates. All rights reserved.
+
+Licensed under the Oculus Master SDK License Version 1.0 (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
+
+https://developer.oculus.com/licenses/oculusmastersdk-1.0
+
+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_Alg.h"
+#include "OVR_ContainerAllocator.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:
+ size_t operator()(const C& data) const {
+ return (size_t)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 size_t SDBM_Hash(const void* data_in, size_t size, size_t seed = 5381) {
+ const uint8_t* data = (const uint8_t*)data_in;
+ size_t h = seed;
+ while (size > 0) {
+ --size;
+#ifndef __clang_analyzer__ // It mistakenly thinks data is garbage.
+ h = (h << 16) + (h << 6) - h + (size_t)data[size];
+#endif
+ }
+ return h;
+ }
+
+ size_t operator()(const C& data) const {
+ const unsigned char* p = (const unsigned char*)&data;
+ const size_t 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.
+ intptr_t NextInChain;
+ C Value;
+
+ HashsetEntry() : NextInChain(-2) {}
+ HashsetEntry(const HashsetEntry& e) : NextInChain(e.NextInChain), Value(e.Value) {}
+ HashsetEntry(const C& key, intptr_t 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.
+ size_t GetCachedHash(size_t maskValue) const {
+ return HashF()(Value) & maskValue;
+ }
+ void SetCachedHash(size_t) {}
+
+ 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.
+ intptr_t NextInChain;
+ size_t HashValue;
+ C Value;
+
+ HashsetCachedEntry() : NextInChain(-2) {}
+ HashsetCachedEntry(const HashsetCachedEntry& e)
+ : NextInChain(e.NextInChain), HashValue(e.HashValue), Value(e.Value) {}
+ HashsetCachedEntry(const C& key, intptr_t 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.
+ size_t GetCachedHash(size_t maskValue) const {
+ OVR_UNUSED(maskValue);
+ return HashValue;
+ }
+ void SetCachedHash(size_t 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(sizeHint);
+ }
+ HashSetBase(const SelfType& src) : pTable(NULL) {
+ Assign(src);
+ }
+
+ ~HashSetBase() {
+ if (pTable) {
+ // Delete the entries.
+ for (size_t 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 (size_t 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) {
+ size_t hashValue = HashF()(key);
+ intptr_t index = (intptr_t)-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) {
+ size_t hashValue = HashF()(key);
+ add(key, hashValue);
+ }
+
+ // Remove by alternative key.
+ template <class K>
+ void RemoveAlt(const K& key) {
+ if (pTable == NULL)
+ return;
+
+ size_t hashValue = AltHashF()(key);
+ intptr_t 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) != (size_t)index))
+ return;
+
+ // Save index
+ intptr_t naturalIndex = index;
+ intptr_t prevIndex = -1;
+
+ while ((e->GetCachedHash(pTable->SizeMask) != (size_t)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) {
+ intptr_t index = findIndex(key);
+ if (index >= 0)
+ return &E(index).Value;
+ return 0;
+ }
+
+ template <class K>
+ const C* Get(const K& key) const {
+ intptr_t 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 {
+ intptr_t index = findIndexAlt(key);
+ if (index >= 0)
+ return &E(index).Value;
+ return 0;
+ }
+
+ template <class K>
+ C* GetAlt(const K& key) {
+ intptr_t index = findIndexAlt(key);
+ if (index >= 0)
+ return &E(index).Value;
+ return 0;
+ }
+
+ template <class K>
+ bool GetAlt(const K& key, C* pval) const {
+ intptr_t index = findIndexAlt(key);
+ if (index >= 0) {
+ if (pval)
+ *pval = E(index).Value;
+ return true;
+ }
+ return false;
+ }
+
+ size_t GetSize() const {
+ return pTable == NULL ? 0 : (size_t)pTable->EntryCount;
+ }
+ int GetSizeI() const {
+ return (int)GetSize();
+ }
+
+ // 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(size_t 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(size_t newSize) {
+ size_t 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 <= (intptr_t)pHash->pTable->SizeMask);
+ return pHash->E(Index).Value;
+ }
+
+ const C* operator->() const {
+ OVR_ASSERT(Index >= 0 && Index <= (intptr_t)pHash->pTable->SizeMask);
+ return &pHash->E(Index).Value;
+ }
+
+ void operator++() {
+ // Find next non-empty Entry.
+ if (Index <= (intptr_t)pHash->pTable->SizeMask) {
+ Index++;
+ while ((size_t)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 > (intptr_t)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, intptr_t index) : pHash(h), Index(index) {}
+
+ const SelfType* GetContainer() const {
+ return pHash;
+ }
+ intptr_t GetIndex() const {
+ return Index;
+ }
+
+ protected:
+ friend class HashSetBase<C, HashF, AltHashF, Allocator, Entry>;
+
+ const SelfType* pHash;
+ intptr_t 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::pHash) && ConstIterator::pHash->pTable && (ConstIterator::Index >= 0) &&
+ (ConstIterator::Index <= (intptr_t)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;
+
+ size_t hashValue = AltHashF()(key);
+ intptr_t 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) != (size_t)index))
+ return;
+
+ // Save index
+ intptr_t naturalIndex = index;
+ intptr_t prevIndex = -1;
+
+ while ((e->GetCachedHash(phash->pTable->SizeMask) != (size_t)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 == (intptr_t)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, intptr_t i0) : ConstIterator(h, i0) {}
+ };
+
+ friend struct Iterator;
+
+ Iterator Begin() {
+ if (pTable == 0)
+ return Iterator(NULL, 0);
+
+ // Scan till we hit the First valid Entry.
+ size_t 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) {
+ intptr_t index = findIndex(key);
+ if (index >= 0)
+ return Iterator(this, index);
+ return Iterator(NULL, 0);
+ }
+
+ template <class K>
+ Iterator FindAlt(const K& key) {
+ intptr_t 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>
+ intptr_t findIndex(const K& key) const {
+ if (pTable == NULL)
+ return -1;
+ size_t hashValue = HashF()(key) & pTable->SizeMask;
+ return findIndexCore(key, hashValue);
+ }
+
+ template <class K>
+ intptr_t findIndexAlt(const K& key) const {
+ if (pTable == NULL)
+ return -1;
+ size_t 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>
+ intptr_t findIndexCore(const K& key, size_t hashValue) const {
+ // Table must exist.
+ OVR_ASSERT(pTable != 0);
+ // Hash key must be 'and-ed' by the caller.
+ OVR_ASSERT((hashValue & ~pTable->SizeMask) == 0);
+
+ size_t 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 == (size_t)-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, size_t hashValue) {
+ CheckExpand();
+ hashValue &= pTable->SizeMask;
+
+ pTable->EntryCount++;
+
+ intptr_t index = hashValue;
+ Entry* naturalEntry = &(E(index));
+
+ if (naturalEntry->IsEmpty()) {
+ // Put the new Entry in.
+ new (naturalEntry) Entry(key, -1);
+ } else {
+ // Find a blank spot.
+ intptr_t blankIndex = index;
+ do {
+ blankIndex = (blankIndex + 1) & pTable->SizeMask;
+ } while (!E(blankIndex).IsEmpty());
+
+ Entry* blankEntry = &E(blankIndex);
+
+ if (naturalEntry->GetCachedHash(pTable->SizeMask) == (size_t)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)
+ intptr_t collidedIndex = naturalEntry->GetCachedHash(pTable->SizeMask);
+ OVR_ASSERT(collidedIndex >= 0 && collidedIndex <= (intptr_t)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 <= (intptr_t)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(size_t index) {
+ // Must have pTable and access needs to be within bounds.
+ OVR_ASSERT(index <= pTable->SizeMask);
+ return *(((Entry*)(pTable + 1)) + index);
+ }
+ const Entry& E(size_t 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(size_t 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((size_t(1) << bits) >= newSize);
+ newSize = size_t(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;
+ size_t 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 {
+ size_t EntryCount;
+ size_t 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(size_t 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(size_t 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 size_t 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 size_t CalcHash(const K& data) {
+ return HashF()(data);
+ }
+ inline size_t 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>
+ size_t operator()(const K& data) const {
+ return data.GetHash();
+ }
+ };
+ struct NodeAltHashF {
+ template <class K>
+ size_t 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.
+ intptr_t NextInChain;
+ C Value;
+
+ HashsetNodeEntry() : NextInChain(-2) {}
+ HashsetNodeEntry(const HashsetNodeEntry& e) : NextInChain(e.NextInChain), Value(e.Value) {}
+ HashsetNodeEntry(const C& key, intptr_t next) : NextInChain(next), Value(key) {}
+ HashsetNodeEntry(const typename C::NodeRef& keyRef, intptr_t next)
+ : NextInChain(next), Value(keyRef) {}
+
+ bool IsEmpty() const {
+ return NextInChain == -2;
+ }
+ bool IsEndOfChain() const {
+ return NextInChain == -1;
+ }
+ size_t GetCachedHash(size_t maskValue) const {
+ return HashF()(Value) & maskValue;
+ }
+ void SetCachedHash(size_t 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.
+ intptr_t NextInChain;
+ size_t HashValue;
+ C Value;
+
+ HashsetCachedNodeEntry() : NextInChain(-2) {}
+ HashsetCachedNodeEntry(const HashsetCachedNodeEntry& e)
+ : NextInChain(e.NextInChain), HashValue(e.HashValue), Value(e.Value) {}
+ HashsetCachedNodeEntry(const C& key, intptr_t next) : NextInChain(next), Value(key) {}
+ HashsetCachedNodeEntry(const typename C::NodeRef& keyRef, intptr_t next)
+ : NextInChain(next), Value(keyRef) {}
+
+ bool IsEmpty() const {
+ return NextInChain == -2;
+ }
+ bool IsEndOfChain() const {
+ return NextInChain == -1;
+ }
+ size_t GetCachedHash(size_t maskValue) const {
+ OVR_UNUSED(maskValue);
+ return HashValue;
+ }
+ void SetCachedHash(size_t 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 size_t GetSize() const {
+ return mHash.GetSize();
+ }
+ inline int GetSizeI() const {
+ return (int)GetSize();
+ }
+ inline void Resize(size_t n) {
+ mHash.Resize(n);
+ }
+ inline void SetCapacity(size_t 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);
+ }
+};
+
+} // namespace OVR
+
+#ifdef OVR_DEFINE_NEW
+#define new OVR_DEFINE_NEW
+#endif
+
+#endif
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-20 01:26:23 +0000