E:/p4/sw/physx/PxShared/1.0/trunk/src/foundation/include/PsHashInternals.h
Go to the documentation of this file.00001 // This code contains NVIDIA Confidential Information and is disclosed to you 00002 // under a form of NVIDIA software license agreement provided separately to you. 00003 // 00004 // Notice 00005 // NVIDIA Corporation and its licensors retain all intellectual property and 00006 // proprietary rights in and to this software and related documentation and 00007 // any modifications thereto. Any use, reproduction, disclosure, or 00008 // distribution of this software and related documentation without an express 00009 // license agreement from NVIDIA Corporation is strictly prohibited. 00010 // 00011 // ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES 00012 // NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO 00013 // THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT, 00014 // MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE. 00015 // 00016 // Information and code furnished is believed to be accurate and reliable. 00017 // However, NVIDIA Corporation assumes no responsibility for the consequences of use of such 00018 // information or for any infringement of patents or other rights of third parties that may 00019 // result from its use. No license is granted by implication or otherwise under any patent 00020 // or patent rights of NVIDIA Corporation. Details are subject to change without notice. 00021 // This code supersedes and replaces all information previously supplied. 00022 // NVIDIA Corporation products are not authorized for use as critical 00023 // components in life support devices or systems without express written approval of 00024 // NVIDIA Corporation. 00025 // 00026 // Copyright (c) 2008-2014 NVIDIA Corporation. All rights reserved. 00027 // Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved. 00028 // Copyright (c) 2001-2004 NovodeX AG. All rights reserved. 00029 00030 #ifndef PSFOUNDATION_PSHASHINTERNALS_H 00031 #define PSFOUNDATION_PSHASHINTERNALS_H 00032 00033 #include "PsBasicTemplates.h" 00034 #include "PsArray.h" 00035 #include "PsBitUtils.h" 00036 #include "PsHash.h" 00037 #include "foundation/PxIntrinsics.h" 00038 00039 #if PX_VC 00040 #pragma warning(push) 00041 #pragma warning(disable : 4127) // conditional expression is constant 00042 #endif 00043 namespace physx 00044 { 00045 namespace shdfnd 00046 { 00047 namespace internal 00048 { 00049 template <class Entry, class Key, class HashFn, class GetKey, class Allocator, bool compacting> 00050 class HashBase : private Allocator 00051 { 00052 void init(uint32_t initialTableSize, float loadFactor) 00053 { 00054 mBuffer = NULL; 00055 mEntries = NULL; 00056 mEntriesNext = NULL; 00057 mHash = NULL; 00058 mEntriesCapacity = 0; 00059 mHashSize = 0; 00060 mLoadFactor = loadFactor; 00061 mFreeList = uint32_t(EOL); 00062 mTimestamp = 0; 00063 mEntriesCount = 0; 00064 00065 if(initialTableSize) 00066 reserveInternal(initialTableSize); 00067 } 00068 00069 public: 00070 typedef Entry EntryType; 00071 00072 HashBase(uint32_t initialTableSize = 64, float loadFactor = 0.75f) : Allocator(PX_DEBUG_EXP("hashBase")) 00073 { 00074 init(initialTableSize, loadFactor); 00075 } 00076 00077 HashBase(uint32_t initialTableSize, float loadFactor, const Allocator& alloc) : Allocator(alloc) 00078 { 00079 init(initialTableSize, loadFactor); 00080 } 00081 00082 HashBase(const Allocator& alloc) : Allocator(alloc) 00083 { 00084 init(64, 0.75f); 00085 } 00086 00087 ~HashBase() 00088 { 00089 destroy(); // No need to clear() 00090 00091 if(mBuffer) 00092 Allocator::deallocate(mBuffer); 00093 } 00094 00095 static const uint32_t EOL = 0xffffffff; 00096 00097 PX_INLINE Entry* create(const Key& k, bool& exists) 00098 { 00099 uint32_t h = 0; 00100 if(mHashSize) 00101 { 00102 h = hash(k); 00103 uint32_t index = mHash[h]; 00104 while(index != EOL && !HashFn().equal(GetKey()(mEntries[index]), k)) 00105 index = mEntriesNext[index]; 00106 exists = index != EOL; 00107 if(exists) 00108 return mEntries + index; 00109 } 00110 else 00111 exists = false; 00112 00113 if(freeListEmpty()) 00114 { 00115 grow(); 00116 h = hash(k); 00117 } 00118 00119 uint32_t entryIndex = freeListGetNext(); 00120 00121 mEntriesNext[entryIndex] = mHash[h]; 00122 mHash[h] = entryIndex; 00123 00124 mEntriesCount++; 00125 mTimestamp++; 00126 00127 return mEntries + entryIndex; 00128 } 00129 00130 PX_INLINE const Entry* find(const Key& k) const 00131 { 00132 if(!mHashSize) 00133 return NULL; 00134 00135 const uint32_t h = hash(k); 00136 uint32_t index = mHash[h]; 00137 while(index != EOL && !HashFn().equal(GetKey()(mEntries[index]), k)) 00138 index = mEntriesNext[index]; 00139 return index != EOL ? mEntries + index : NULL; 00140 } 00141 00142 PX_INLINE bool erase(const Key& k) 00143 { 00144 if(!mHashSize) 00145 return false; 00146 00147 const uint32_t h = hash(k); 00148 uint32_t* ptr = mHash + h; 00149 while(*ptr != EOL && !HashFn().equal(GetKey()(mEntries[*ptr]), k)) 00150 ptr = mEntriesNext + *ptr; 00151 00152 if(*ptr == EOL) 00153 return false; 00154 00155 const uint32_t index = *ptr; 00156 *ptr = mEntriesNext[index]; 00157 00158 mEntries[index].~Entry(); 00159 00160 mEntriesCount--; 00161 mTimestamp++; 00162 00163 if(compacting && index != mEntriesCount) 00164 replaceWithLast(index); 00165 00166 freeListAdd(index); 00167 00168 return true; 00169 } 00170 00171 PX_INLINE uint32_t size() const 00172 { 00173 return mEntriesCount; 00174 } 00175 00176 PX_INLINE uint32_t capacity() const 00177 { 00178 return mHashSize; 00179 } 00180 00181 void clear() 00182 { 00183 if(!mHashSize || mEntriesCount == 0) 00184 return; 00185 00186 destroy(); 00187 00188 intrinsics::memSet(mHash, EOL, mHashSize * sizeof(uint32_t)); 00189 00190 const uint32_t sizeMinus1 = mEntriesCapacity - 1; 00191 for(uint32_t i = 0; i < sizeMinus1; i++) 00192 { 00193 prefetchLine(mEntriesNext + i, 128); 00194 mEntriesNext[i] = i + 1; 00195 } 00196 mEntriesNext[mEntriesCapacity - 1] = uint32_t(EOL); 00197 mFreeList = 0; 00198 mEntriesCount = 0; 00199 } 00200 00201 void reserve(uint32_t size) 00202 { 00203 if(size > mHashSize) 00204 reserveInternal(size); 00205 } 00206 00207 PX_INLINE const Entry* getEntries() const 00208 { 00209 return mEntries; 00210 } 00211 00212 PX_INLINE Entry* insertUnique(const Key& k) 00213 { 00214 PX_ASSERT(find(k) == NULL); 00215 uint32_t h = hash(k); 00216 00217 uint32_t entryIndex = freeListGetNext(); 00218 00219 mEntriesNext[entryIndex] = mHash[h]; 00220 mHash[h] = entryIndex; 00221 00222 mEntriesCount++; 00223 mTimestamp++; 00224 00225 return mEntries + entryIndex; 00226 } 00227 00228 private: 00229 void destroy() 00230 { 00231 for(uint32_t i = 0; i < mHashSize; i++) 00232 { 00233 for(uint32_t j = mHash[i]; j != EOL; j = mEntriesNext[j]) 00234 mEntries[j].~Entry(); 00235 } 00236 } 00237 00238 template <typename HK, typename GK, class A, bool comp> 00239 PX_NOINLINE void copy(const HashBase<Entry, Key, HK, GK, A, comp>& other); 00240 00241 // free list management - if we're coalescing, then we use mFreeList to hold 00242 // the top of the free list and it should always be equal to size(). Otherwise, 00243 // we build a free list in the next() pointers. 00244 00245 PX_INLINE void freeListAdd(uint32_t index) 00246 { 00247 if(compacting) 00248 { 00249 mFreeList--; 00250 PX_ASSERT(mFreeList == mEntriesCount); 00251 } 00252 else 00253 { 00254 mEntriesNext[index] = mFreeList; 00255 mFreeList = index; 00256 } 00257 } 00258 00259 PX_INLINE void freeListAdd(uint32_t start, uint32_t end) 00260 { 00261 if(!compacting) 00262 { 00263 for(uint32_t i = start; i < end - 1; i++) // add the new entries to the free list 00264 mEntriesNext[i] = i + 1; 00265 00266 // link in old free list 00267 mEntriesNext[end - 1] = mFreeList; 00268 PX_ASSERT(mFreeList != end - 1); 00269 mFreeList = start; 00270 } 00271 else if(mFreeList == EOL) // don't reset the free ptr for the compacting hash unless it's empty 00272 mFreeList = start; 00273 } 00274 00275 PX_INLINE uint32_t freeListGetNext() 00276 { 00277 PX_ASSERT(!freeListEmpty()); 00278 if(compacting) 00279 { 00280 PX_ASSERT(mFreeList == mEntriesCount); 00281 return mFreeList++; 00282 } 00283 else 00284 { 00285 uint32_t entryIndex = mFreeList; 00286 mFreeList = mEntriesNext[mFreeList]; 00287 return entryIndex; 00288 } 00289 } 00290 00291 PX_INLINE bool freeListEmpty() const 00292 { 00293 if(compacting) 00294 return mEntriesCount == mEntriesCapacity; 00295 else 00296 return mFreeList == EOL; 00297 } 00298 00299 PX_INLINE void replaceWithLast(uint32_t index) 00300 { 00301 PX_PLACEMENT_NEW(mEntries + index, Entry)(mEntries[mEntriesCount]); 00302 mEntries[mEntriesCount].~Entry(); 00303 mEntriesNext[index] = mEntriesNext[mEntriesCount]; 00304 00305 uint32_t h = hash(GetKey()(mEntries[index])); 00306 uint32_t* ptr; 00307 for(ptr = mHash + h; *ptr != mEntriesCount; ptr = mEntriesNext + *ptr) 00308 PX_ASSERT(*ptr != EOL); 00309 *ptr = index; 00310 } 00311 00312 PX_INLINE uint32_t hash(const Key& k, uint32_t hashSize) const 00313 { 00314 return HashFn()(k) & (hashSize - 1); 00315 } 00316 00317 PX_INLINE uint32_t hash(const Key& k) const 00318 { 00319 return hash(k, mHashSize); 00320 } 00321 00322 void reserveInternal(uint32_t size) 00323 { 00324 if(!isPowerOfTwo(size)) 00325 size = nextPowerOfTwo(size); 00326 00327 PX_ASSERT(!(size & (size - 1))); 00328 00329 // decide whether iteration can be done on the entries directly 00330 bool resizeCompact = compacting || freeListEmpty(); 00331 00332 // define new table sizes 00333 uint32_t oldEntriesCapacity = mEntriesCapacity; 00334 uint32_t newEntriesCapacity = uint32_t(float(size) * mLoadFactor); 00335 uint32_t newHashSize = size; 00336 00337 // allocate new common buffer and setup pointers to new tables 00338 uint8_t* newBuffer; 00339 uint32_t* newHash; 00340 uint32_t* newEntriesNext; 00341 Entry* newEntries; 00342 { 00343 uint32_t newHashByteOffset = 0; 00344 uint32_t newEntriesNextBytesOffset = newHashByteOffset + newHashSize * sizeof(uint32_t); 00345 uint32_t newEntriesByteOffset = newEntriesNextBytesOffset + newEntriesCapacity * sizeof(uint32_t); 00346 newEntriesByteOffset += (16 - (newEntriesByteOffset & 15)) & 15; 00347 uint32_t newBufferByteSize = newEntriesByteOffset + newEntriesCapacity * sizeof(Entry); 00348 00349 newBuffer = reinterpret_cast<uint8_t*>(Allocator::allocate(newBufferByteSize, __FILE__, __LINE__)); 00350 PX_ASSERT(newBuffer); 00351 00352 newHash = reinterpret_cast<uint32_t*>(newBuffer + newHashByteOffset); 00353 newEntriesNext = reinterpret_cast<uint32_t*>(newBuffer + newEntriesNextBytesOffset); 00354 newEntries = reinterpret_cast<Entry*>(newBuffer + newEntriesByteOffset); 00355 } 00356 00357 // initialize new hash table 00358 intrinsics::memSet(newHash, uint32_t(EOL), newHashSize * sizeof(uint32_t)); 00359 00360 // iterate over old entries, re-hash and create new entries 00361 if(resizeCompact) 00362 { 00363 // check that old free list is empty - we don't need to copy the next entries 00364 PX_ASSERT(compacting || mFreeList == EOL); 00365 00366 for(uint32_t index = 0; index < mEntriesCount; ++index) 00367 { 00368 uint32_t h = hash(GetKey()(mEntries[index]), newHashSize); 00369 newEntriesNext[index] = newHash[h]; 00370 newHash[h] = index; 00371 00372 PX_PLACEMENT_NEW(newEntries + index, Entry)(mEntries[index]); 00373 mEntries[index].~Entry(); 00374 } 00375 } 00376 else 00377 { 00378 // copy old free list, only required for non compact resizing 00379 intrinsics::memCopy(newEntriesNext, mEntriesNext, mEntriesCapacity * sizeof(uint32_t)); 00380 00381 for(uint32_t bucket = 0; bucket < mHashSize; bucket++) 00382 { 00383 uint32_t index = mHash[bucket]; 00384 while(index != EOL) 00385 { 00386 uint32_t h = hash(GetKey()(mEntries[index]), newHashSize); 00387 newEntriesNext[index] = newHash[h]; 00388 PX_ASSERT(index != newHash[h]); 00389 00390 newHash[h] = index; 00391 00392 PX_PLACEMENT_NEW(newEntries + index, Entry)(mEntries[index]); 00393 mEntries[index].~Entry(); 00394 00395 index = mEntriesNext[index]; 00396 } 00397 } 00398 } 00399 00400 // swap buffer and pointers 00401 Allocator::deallocate(mBuffer); 00402 mBuffer = newBuffer; 00403 mHash = newHash; 00404 mHashSize = newHashSize; 00405 mEntriesNext = newEntriesNext; 00406 mEntries = newEntries; 00407 mEntriesCapacity = newEntriesCapacity; 00408 00409 freeListAdd(oldEntriesCapacity, newEntriesCapacity); 00410 } 00411 00412 void grow() 00413 { 00414 PX_ASSERT((mFreeList == EOL) || (compacting && (mEntriesCount == mEntriesCapacity))); 00415 00416 uint32_t size = mHashSize == 0 ? 16 : mHashSize * 2; 00417 reserve(size); 00418 } 00419 00420 uint8_t* mBuffer; 00421 Entry* mEntries; 00422 uint32_t* mEntriesNext; // same size as mEntries 00423 uint32_t* mHash; 00424 uint32_t mEntriesCapacity; 00425 uint32_t mHashSize; 00426 float mLoadFactor; 00427 uint32_t mFreeList; 00428 uint32_t mTimestamp; 00429 uint32_t mEntriesCount; // number of entries 00430 00431 public: 00432 class Iter 00433 { 00434 public: 00435 PX_INLINE Iter(HashBase& b) : mBucket(0), mEntry(uint32_t(b.EOL)), mTimestamp(b.mTimestamp), mBase(b) 00436 { 00437 if(mBase.mEntriesCapacity > 0) 00438 { 00439 mEntry = mBase.mHash[0]; 00440 skip(); 00441 } 00442 } 00443 00444 PX_INLINE void check() const 00445 { 00446 PX_ASSERT(mTimestamp == mBase.mTimestamp); 00447 } 00448 PX_INLINE Entry operator*() const 00449 { 00450 check(); 00451 return mBase.mEntries[mEntry]; 00452 } 00453 PX_INLINE Entry* operator->() const 00454 { 00455 check(); 00456 return mBase.mEntries + mEntry; 00457 } 00458 PX_INLINE Iter operator++() 00459 { 00460 check(); 00461 advance(); 00462 return *this; 00463 } 00464 PX_INLINE Iter operator++(int) 00465 { 00466 check(); 00467 Iter i = *this; 00468 advance(); 00469 return i; 00470 } 00471 PX_INLINE bool done() const 00472 { 00473 check(); 00474 return mEntry == mBase.EOL; 00475 } 00476 00477 private: 00478 PX_INLINE void advance() 00479 { 00480 mEntry = mBase.mEntriesNext[mEntry]; 00481 skip(); 00482 } 00483 PX_INLINE void skip() 00484 { 00485 while(mEntry == mBase.EOL) 00486 { 00487 if(++mBucket == mBase.mHashSize) 00488 break; 00489 mEntry = mBase.mHash[mBucket]; 00490 } 00491 } 00492 00493 Iter& operator=(const Iter&); 00494 00495 uint32_t mBucket; 00496 uint32_t mEntry; 00497 uint32_t mTimestamp; 00498 HashBase& mBase; 00499 }; 00500 }; 00501 00502 template <class Entry, class Key, class HashFn, class GetKey, class Allocator, bool compacting> 00503 template <typename HK, typename GK, class A, bool comp> 00504 PX_NOINLINE void 00505 HashBase<Entry, Key, HashFn, GetKey, Allocator, compacting>::copy(const HashBase<Entry, Key, HK, GK, A, comp>& other) 00506 { 00507 reserve(other.mEntriesCount); 00508 00509 for(uint32_t i = 0; i < other.mEntriesCount; i++) 00510 { 00511 for(uint32_t j = other.mHash[i]; j != EOL; j = other.mEntriesNext[j]) 00512 { 00513 const Entry& otherEntry = other.mEntries[j]; 00514 00515 bool exists; 00516 Entry* newEntry = create(GK()(otherEntry), exists); 00517 PX_ASSERT(!exists); 00518 00519 PX_PLACEMENT_NEW(newEntry, Entry)(otherEntry); 00520 } 00521 } 00522 } 00523 00524 template <class Key, class HashFn, class Allocator = typename AllocatorTraits<Key>::Type, bool Coalesced = false> 00525 class HashSetBase 00526 { 00527 PX_NOCOPY(HashSetBase) 00528 public: 00529 struct GetKey 00530 { 00531 PX_INLINE const Key& operator()(const Key& e) 00532 { 00533 return e; 00534 } 00535 }; 00536 00537 typedef HashBase<Key, Key, HashFn, GetKey, Allocator, Coalesced> BaseMap; 00538 typedef typename BaseMap::Iter Iterator; 00539 00540 HashSetBase(uint32_t initialTableSize, float loadFactor, const Allocator& alloc) 00541 : mBase(initialTableSize, loadFactor, alloc) 00542 { 00543 } 00544 00545 HashSetBase(const Allocator& alloc) : mBase(64, 0.75f, alloc) 00546 { 00547 } 00548 00549 HashSetBase(uint32_t initialTableSize = 64, float loadFactor = 0.75f) : mBase(initialTableSize, loadFactor) 00550 { 00551 } 00552 00553 bool insert(const Key& k) 00554 { 00555 bool exists; 00556 Key* e = mBase.create(k, exists); 00557 if(!exists) 00558 PX_PLACEMENT_NEW(e, Key)(k); 00559 return !exists; 00560 } 00561 00562 PX_INLINE bool contains(const Key& k) const 00563 { 00564 return mBase.find(k) != 0; 00565 } 00566 PX_INLINE bool erase(const Key& k) 00567 { 00568 return mBase.erase(k); 00569 } 00570 PX_INLINE uint32_t size() const 00571 { 00572 return mBase.size(); 00573 } 00574 PX_INLINE uint32_t capacity() const 00575 { 00576 return mBase.capacity(); 00577 } 00578 PX_INLINE void reserve(uint32_t size) 00579 { 00580 mBase.reserve(size); 00581 } 00582 PX_INLINE void clear() 00583 { 00584 mBase.clear(); 00585 } 00586 00587 protected: 00588 BaseMap mBase; 00589 }; 00590 00591 template <class Key, class Value, class HashFn, class Allocator = typename AllocatorTraits<Pair<const Key, Value> >::Type> 00592 class HashMapBase 00593 { 00594 PX_NOCOPY(HashMapBase) 00595 public: 00596 typedef Pair<const Key, Value> Entry; 00597 00598 struct GetKey 00599 { 00600 PX_INLINE const Key& operator()(const Entry& e) 00601 { 00602 return e.first; 00603 } 00604 }; 00605 00606 typedef HashBase<Entry, Key, HashFn, GetKey, Allocator, true> BaseMap; 00607 typedef typename BaseMap::Iter Iterator; 00608 00609 HashMapBase(uint32_t initialTableSize, float loadFactor, const Allocator& alloc) 00610 : mBase(initialTableSize, loadFactor, alloc) 00611 { 00612 } 00613 00614 HashMapBase(const Allocator& alloc) : mBase(64, 0.75f, alloc) 00615 { 00616 } 00617 00618 HashMapBase(uint32_t initialTableSize = 64, float loadFactor = 0.75f) : mBase(initialTableSize, loadFactor) 00619 { 00620 } 00621 00622 bool insert(const Key /*&*/ k, const Value /*&*/ v) 00623 { 00624 bool exists; 00625 Entry* e = mBase.create(k, exists); 00626 if(!exists) 00627 PX_PLACEMENT_NEW(e, Entry)(k, v); 00628 return !exists; 00629 } 00630 00631 Value& operator[](const Key& k) 00632 { 00633 bool exists; 00634 Entry* e = mBase.create(k, exists); 00635 if(!exists) 00636 PX_PLACEMENT_NEW(e, Entry)(k, Value()); 00637 00638 return e->second; 00639 } 00640 00641 PX_INLINE const Entry* find(const Key& k) const 00642 { 00643 return mBase.find(k); 00644 } 00645 PX_INLINE bool erase(const Key& k) 00646 { 00647 return mBase.erase(k); 00648 } 00649 PX_INLINE uint32_t size() const 00650 { 00651 return mBase.size(); 00652 } 00653 PX_INLINE uint32_t capacity() const 00654 { 00655 return mBase.capacity(); 00656 } 00657 PX_INLINE Iterator getIterator() 00658 { 00659 return Iterator(mBase); 00660 } 00661 PX_INLINE void reserve(uint32_t size) 00662 { 00663 mBase.reserve(size); 00664 } 00665 PX_INLINE void clear() 00666 { 00667 mBase.clear(); 00668 } 00669 00670 protected: 00671 BaseMap mBase; 00672 }; 00673 } 00674 00675 } // namespace shdfnd 00676 } // namespace physx 00677 00678 #if PX_VC 00679 #pragma warning(pop) 00680 #endif 00681 #endif // #ifndef PSFOUNDATION_PSHASHINTERNALS_H
Generated on Tue Jul 28 14:21:55 2015 for NVIDIA(R) PsFoundation Reference by
![doxygen](doxygen.png)