From e490c3c7f7bb5461cfa78a214827aa534fb43a3e Mon Sep 17 00:00:00 2001 From: Sven Gothel Date: Sat, 21 Mar 2015 21:19:34 +0100 Subject: Bump OculusVR RIFT SDK to 0.4.4 --- LibOVR/Src/Kernel/OVR_Hash.h | 217 ++++++++++++++++++++++--------------------- 1 file changed, 110 insertions(+), 107 deletions(-) (limited to 'LibOVR/Src/Kernel/OVR_Hash.h') diff --git a/LibOVR/Src/Kernel/OVR_Hash.h b/LibOVR/Src/Kernel/OVR_Hash.h index 04c4db8..3316d1e 100644 --- a/LibOVR/Src/Kernel/OVR_Hash.h +++ b/LibOVR/Src/Kernel/OVR_Hash.h @@ -6,16 +6,16 @@ Content : Template hash-table/set implementation Created : September 19, 2012 Notes : -Copyright : Copyright 2014 Oculus VR, Inc. All Rights reserved. +Copyright : Copyright 2014 Oculus VR, LLC All Rights reserved. -Licensed under the Oculus VR Rift SDK License Version 3.1 (the "License"); +Licensed under the Oculus VR Rift SDK License Version 3.2 (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 +http://www.oculusvr.com/licenses/LICENSE-3.2 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, @@ -71,8 +71,8 @@ template class IdentityHash { public: - UPInt operator()(const C& data) const - { return (UPInt) data; } + size_t operator()(const C& data) const + { return (size_t) data; } }; // Computes a hash of an object's representation. @@ -84,22 +84,23 @@ public: // 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) + static OVR_FORCE_INLINE size_t SDBM_Hash(const void* data_in, size_t size, size_t seed = 5381) { - const UByte* data = (const UByte*) data_in; - UPInt h = seed; - while (size > 0) + const uint8_t* data = (const uint8_t*) data_in; + size_t h = seed; + while (size-- > 0) { - size--; - h = (h << 16) + (h << 6) - h + (UPInt)data[size]; + #ifndef __clang_analyzer__ // It mistakenly thinks data is garbage. + h = (h << 16) + (h << 6) - h + (size_t)data[size]; + #endif } return h; } - UPInt operator()(const C& data) const + size_t operator()(const C& data) const { - unsigned char* p = (unsigned char*) &data; - int size = sizeof(C); + const unsigned char* p = (const unsigned char*) &data; + const size_t size = sizeof(C); return SDBM_Hash(p, size); } @@ -116,14 +117,14 @@ class HashsetEntry { public: // Internal chaining for collisions. - SPInt NextInChain; + intptr_t NextInChain; C Value; HashsetEntry() : NextInChain(-2) { } HashsetEntry(const HashsetEntry& e) : NextInChain(e.NextInChain), Value(e.Value) { } - HashsetEntry(const C& key, SPInt next) + HashsetEntry(const C& key, intptr_t next) : NextInChain(next), Value(key) { } bool IsEmpty() const { return NextInChain == -2; } @@ -131,8 +132,8 @@ public: // 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) {} + size_t GetCachedHash(size_t maskValue) const { return HashF()(Value) & maskValue; } + void SetCachedHash(size_t) {} void Clear() { @@ -151,15 +152,15 @@ class HashsetCachedEntry { public: // Internal chaining for collisions. - SPInt NextInChain; - UPInt HashValue; + 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, SPInt next) + HashsetCachedEntry(const C& key, intptr_t next) : NextInChain(next), Value(key) { } bool IsEmpty() const { return NextInChain == -2; } @@ -167,8 +168,8 @@ public: // 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; } + size_t GetCachedHash(size_t maskValue) const { OVR_UNUSED(maskValue); return HashValue; } + void SetCachedHash(size_t hashValue) { HashValue = hashValue; } void Clear() { @@ -210,7 +211,7 @@ public: if (pTable) { // Delete the entries. - for (UPInt i = 0, n = pTable->SizeMask; i <= n; i++) + for (size_t i = 0, n = pTable->SizeMask; i <= n; i++) { Entry* e = &E(i); if (!e->IsEmpty()) @@ -244,7 +245,7 @@ public: if (pTable) { // Delete the entries. - for (UPInt i = 0, n = pTable->SizeMask; i <= n; i++) + for (size_t i = 0, n = pTable->SizeMask; i <= n; i++) { Entry* e = &E(i); if (!e->IsEmpty()) @@ -269,8 +270,8 @@ public: template void Set(const CRef& key) { - UPInt hashValue = HashF()(key); - SPInt index = (SPInt)-1; + size_t hashValue = HashF()(key); + intptr_t index = (intptr_t)-1; if (pTable != NULL) index = findIndexCore(key, hashValue & pTable->SizeMask); @@ -289,7 +290,7 @@ public: template inline void Add(const CRef& key) { - UPInt hashValue = HashF()(key); + size_t hashValue = HashF()(key); add(key, hashValue); } @@ -300,20 +301,20 @@ public: if (pTable == NULL) return; - UPInt hashValue = AltHashF()(key); - SPInt index = hashValue & pTable->SizeMask; + 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) != (UPInt)index)) + if (e->IsEmpty() || (e->GetCachedHash(pTable->SizeMask) != (size_t)index)) return; // Save index - SPInt naturalIndex = index; - SPInt prevIndex = -1; + intptr_t naturalIndex = index; + intptr_t prevIndex = -1; - while ((e->GetCachedHash(pTable->SizeMask) != (UPInt)naturalIndex) || !(e->Value == key)) + while ((e->GetCachedHash(pTable->SizeMask) != (size_t)naturalIndex) || !(e->Value == key)) { // Keep looking through the chain. prevIndex = index; @@ -361,7 +362,7 @@ public: template C* Get(const K& key) { - SPInt index = findIndex(key); + intptr_t index = findIndex(key); if (index >= 0) return &E(index).Value; return 0; @@ -370,7 +371,7 @@ public: template const C* Get(const K& key) const { - SPInt index = findIndex(key); + intptr_t index = findIndex(key); if (index >= 0) return &E(index).Value; return 0; @@ -380,7 +381,7 @@ public: template const C* GetAlt(const K& key) const { - SPInt index = findIndexAlt(key); + intptr_t index = findIndexAlt(key); if (index >= 0) return &E(index).Value; return 0; @@ -389,7 +390,7 @@ public: template C* GetAlt(const K& key) { - SPInt index = findIndexAlt(key); + intptr_t index = findIndexAlt(key); if (index >= 0) return &E(index).Value; return 0; @@ -398,7 +399,7 @@ public: template bool GetAlt(const K& key, C* pval) const { - SPInt index = findIndexAlt(key); + intptr_t index = findIndexAlt(key); if (index >= 0) { if (pval) @@ -409,10 +410,11 @@ public: } - UPInt GetSize() const + size_t GetSize() const { - return pTable == NULL ? 0 : (UPInt)pTable->EntryCount; + 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 @@ -432,7 +434,7 @@ public: } // Hint the bucket count to >= n. - void Resize(UPInt n) + void Resize(size_t n) { // Not really sure what this means in relation to // STLport's hash_map... they say they "increase the @@ -446,9 +448,9 @@ public: // 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) + void SetCapacity(size_t newSize) { - UPInt newRawSize = (newSize * 5) / 4; + size_t newRawSize = (newSize * 5) / 4; if (newRawSize <= GetSize()) return; setRawCapacity(newRawSize); @@ -466,23 +468,23 @@ public: { const C& operator * () const { - OVR_ASSERT(Index >= 0 && Index <= (SPInt)pHash->pTable->SizeMask); + OVR_ASSERT(Index >= 0 && Index <= (intptr_t)pHash->pTable->SizeMask); return pHash->E(Index).Value; } const C* operator -> () const { - OVR_ASSERT(Index >= 0 && Index <= (SPInt)pHash->pTable->SizeMask); + OVR_ASSERT(Index >= 0 && Index <= (intptr_t)pHash->pTable->SizeMask); return &pHash->E(Index).Value; } void operator ++ () { // Find next non-empty Entry. - if (Index <= (SPInt)pHash->pTable->SizeMask) + if (Index <= (intptr_t)pHash->pTable->SizeMask) { Index++; - while ((UPInt)Index <= pHash->pTable->SizeMask && + while ((size_t)Index <= pHash->pTable->SizeMask && pHash->E(Index).IsEmpty()) { Index++; @@ -512,7 +514,7 @@ public: { return (pHash == NULL) || (pHash->pTable == NULL) || - (Index > (SPInt)pHash->pTable->SizeMask); + (Index > (intptr_t)pHash->pTable->SizeMask); } ConstIterator() @@ -522,7 +524,7 @@ public: public: // Constructor was intentionally made public to allow create // iterator with arbitrary index. - ConstIterator(const SelfType* h, SPInt index) + ConstIterator(const SelfType* h, intptr_t index) : pHash(h), Index(index) { } @@ -530,7 +532,7 @@ public: { return pHash; } - SPInt GetIndex() const + intptr_t GetIndex() const { return Index; } @@ -539,7 +541,7 @@ public: friend class HashSetBase; const SelfType* pHash; - SPInt Index; + intptr_t Index; }; friend struct ConstIterator; @@ -551,7 +553,7 @@ public: // Allow non-const access to entries. C& operator*() const { - OVR_ASSERT(ConstIterator::Index >= 0 && ConstIterator::Index <= (SPInt)ConstIterator::pHash->pTable->SizeMask); + OVR_ASSERT((ConstIterator::pHash) && ConstIterator::pHash->pTable && (ConstIterator::Index >= 0) && (ConstIterator::Index <= (intptr_t)ConstIterator::pHash->pTable->SizeMask)); return const_cast(ConstIterator::pHash)->E(ConstIterator::Index).Value; } @@ -577,20 +579,20 @@ public: //Entry* ee = &phash->E(ConstIterator::Index); //const C& key = ee->Value; - UPInt hashValue = AltHashF()(key); - SPInt index = hashValue & phash->pTable->SizeMask; + 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) != (UPInt)index)) + if (e->IsEmpty() || (e->GetCachedHash(phash->pTable->SizeMask) != (size_t)index)) return; // Save index - SPInt naturalIndex = index; - SPInt prevIndex = -1; + intptr_t naturalIndex = index; + intptr_t prevIndex = -1; - while ((e->GetCachedHash(phash->pTable->SizeMask) != (UPInt)naturalIndex) || !(e->Value == key)) + while ((e->GetCachedHash(phash->pTable->SizeMask) != (size_t)naturalIndex) || !(e->Value == key)) { // Keep looking through the chain. prevIndex = index; @@ -600,7 +602,7 @@ public: e = &phash->E(index); } - if (index == (SPInt)ConstIterator::Index) + if (index == (intptr_t)ConstIterator::Index) { // Found it - our item is at index if (naturalIndex == index) @@ -633,7 +635,7 @@ public: private: friend class HashSetBase; - Iterator(SelfType* h, SPInt i0) + Iterator(SelfType* h, intptr_t i0) : ConstIterator(h, i0) { } }; @@ -646,7 +648,7 @@ public: return Iterator(NULL, 0); // Scan till we hit the First valid Entry. - UPInt i0 = 0; + size_t i0 = 0; while (i0 <= pTable->SizeMask && E(i0).IsEmpty()) { i0++; @@ -661,7 +663,7 @@ public: template Iterator Find(const K& key) { - SPInt index = findIndex(key); + intptr_t index = findIndex(key); if (index >= 0) return Iterator(this, index); return Iterator(NULL, 0); @@ -670,7 +672,7 @@ public: template Iterator FindAlt(const K& key) { - SPInt index = findIndexAlt(key); + intptr_t index = findIndexAlt(key); if (index >= 0) return Iterator(this, index); return Iterator(NULL, 0); @@ -685,33 +687,33 @@ public: private: // Find the index of the matching Entry. If no match, then return -1. template - SPInt findIndex(const K& key) const + intptr_t findIndex(const K& key) const { if (pTable == NULL) return -1; - UPInt hashValue = HashF()(key) & pTable->SizeMask; + size_t hashValue = HashF()(key) & pTable->SizeMask; return findIndexCore(key, hashValue); } template - SPInt findIndexAlt(const K& key) const + intptr_t findIndexAlt(const K& key) const { if (pTable == NULL) return -1; - UPInt hashValue = AltHashF()(key) & pTable->SizeMask; + 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 - SPInt findIndexCore(const K& key, UPInt hashValue) const + 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); - UPInt index = hashValue; + size_t index = hashValue; const Entry* e = &E(index); // If empty or occupied by a collider, not found. @@ -733,7 +735,7 @@ private: // Keep looking through the chain. index = e->NextInChain; - if (index == (UPInt)-1) + if (index == (size_t)-1) break; // end of chain e = &E(index); @@ -745,14 +747,14 @@ private: // Add a new value to the HashSet table, under the specified key. template - void add(const CRef& key, UPInt hashValue) + void add(const CRef& key, size_t hashValue) { CheckExpand(); hashValue &= pTable->SizeMask; pTable->EntryCount++; - SPInt index = hashValue; + intptr_t index = hashValue; Entry* naturalEntry = &(E(index)); if (naturalEntry->IsEmpty()) @@ -763,14 +765,14 @@ private: else { // Find a blank spot. - SPInt blankIndex = index; + intptr_t blankIndex = index; do { blankIndex = (blankIndex + 1) & pTable->SizeMask; } while(!E(blankIndex).IsEmpty()); Entry* blankEntry = &E(blankIndex); - if (naturalEntry->GetCachedHash(pTable->SizeMask) == (UPInt)index) + if (naturalEntry->GetCachedHash(pTable->SizeMask) == (size_t)index) { // Collision. Link into this chain. @@ -788,8 +790,8 @@ private: // 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); + intptr_t collidedIndex = naturalEntry->GetCachedHash(pTable->SizeMask); + OVR_ASSERT(collidedIndex >= 0 && collidedIndex <= (intptr_t)pTable->SizeMask); for (;;) { Entry* e = &E(collidedIndex); @@ -801,7 +803,7 @@ private: break; } collidedIndex = e->NextInChain; - OVR_ASSERT(collidedIndex >= 0 && collidedIndex <= (SPInt)pTable->SizeMask); + OVR_ASSERT(collidedIndex >= 0 && collidedIndex <= (intptr_t)pTable->SizeMask); } // Put the new data in the natural Entry. @@ -815,13 +817,13 @@ private: } // Index access helpers. - Entry& E(UPInt index) + 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(UPInt index) const + const Entry& E(size_t index) const { OVR_ASSERT(index <= pTable->SizeMask); return *(((Entry*) (pTable + 1)) + index); @@ -832,7 +834,7 @@ private: // 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) + void setRawCapacity(size_t newSize) { if (newSize == 0) { @@ -850,8 +852,8 @@ private: { // 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; + OVR_ASSERT((size_t(1) << bits) >= newSize); + newSize = size_t(1) << bits; } SelfType newHash; @@ -863,7 +865,7 @@ private: newHash.pTable->EntryCount = 0; newHash.pTable->SizeMask = newSize - 1; - UPInt i, n; + size_t i, n; // Mark all entries as empty. for (i = 0; i < newSize; i++) @@ -895,8 +897,8 @@ private: struct TableType { - UPInt EntryCount; - UPInt SizeMask; + size_t EntryCount; + size_t SizeMask; // Entry array follows this structure // in memory. }; @@ -939,7 +941,7 @@ public: } // Hint the bucket count to >= n. - void Resize(UPInt n) + void Resize(size_t n) { BaseType::SetCapacity(n); } @@ -947,7 +949,7 @@ public: // 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) + void SetCapacity(size_t newSize) { BaseType::SetCapacity(newSize); } @@ -1004,7 +1006,7 @@ struct HashNode NodeRef(const NodeRef& src) : pFirst(src.pFirst), pSecond(src.pSecond) { } // Enable computation of ghash_node_hashf. - inline UPInt GetHash() const { return HashF()(*pFirst); } + inline size_t GetHash() const { return HashF()(*pFirst); } // Necessary conversion to allow HashNode::operator == to work. operator const C& () const { return *pFirst; } }; @@ -1018,20 +1020,20 @@ struct HashNode bool operator == (const K& src) const { return (First == src); } template - static UPInt CalcHash(const K& data) { return HashF()(data); } - inline UPInt GetHash() const { return HashF()(First); } + 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 - UPInt operator()(const K& data) const { return data.GetHash(); } + size_t operator()(const K& data) const { return data.GetHash(); } }; struct NodeAltHashF { template - UPInt operator()(const K& data) const { return HashNode::CalcHash(data); } + size_t operator()(const K& data) const { return HashNode::CalcHash(data); } }; }; @@ -1050,22 +1052,22 @@ class HashsetNodeEntry { public: // Internal chaining for collisions. - SPInt NextInChain; + intptr_t NextInChain; C Value; HashsetNodeEntry() : NextInChain(-2) { } HashsetNodeEntry(const HashsetNodeEntry& e) : NextInChain(e.NextInChain), Value(e.Value) { } - HashsetNodeEntry(const C& key, SPInt next) + HashsetNodeEntry(const C& key, intptr_t next) : NextInChain(next), Value(key) { } - HashsetNodeEntry(const typename C::NodeRef& keyRef, SPInt next) + 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; } - UPInt GetCachedHash(UPInt maskValue) const { return HashF()(Value) & maskValue; } - void SetCachedHash(UPInt hashValue) { OVR_UNUSED(hashValue); } + size_t GetCachedHash(size_t maskValue) const { return HashF()(Value) & maskValue; } + void SetCachedHash(size_t hashValue) { OVR_UNUSED(hashValue); } void Clear() { @@ -1084,23 +1086,23 @@ class HashsetCachedNodeEntry { public: // Internal chaining for collisions. - SPInt NextInChain; - UPInt HashValue; + 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, SPInt next) + HashsetCachedNodeEntry(const C& key, intptr_t next) : NextInChain(next), Value(key) { } - HashsetCachedNodeEntry(const typename C::NodeRef& keyRef, SPInt next) + 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; } - UPInt GetCachedHash(UPInt maskValue) const { OVR_UNUSED(maskValue); return HashValue; } - void SetCachedHash(UPInt hashValue) { HashValue = hashValue; } + size_t GetCachedHash(size_t maskValue) const { OVR_UNUSED(maskValue); return HashValue; } + void SetCachedHash(size_t hashValue) { HashValue = hashValue; } void Clear() { @@ -1227,9 +1229,10 @@ public: } // 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); } + 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; -- cgit v1.2.3