oculus1
diff libovr/Src/Kernel/OVR_Hash.h @ 1:e2f9e4603129
added LibOVR and started a simple vr wrapper.
author | John Tsiombikas <nuclear@member.fsf.org> |
---|---|
date | Sat, 14 Sep 2013 16:14:59 +0300 |
parents | |
children | b069a5c27388 |
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/libovr/Src/Kernel/OVR_Hash.h Sat Sep 14 16:14:59 2013 +0300 1.3 @@ -0,0 +1,1 @@ 1.4 +/************************************************************************************ 1.5 1.6 PublicHeader: None 1.7 Filename : OVR_Hash.h 1.8 Content : Template hash-table/set implementation 1.9 Created : September 19, 2012 1.10 Notes : 1.11 1.12 Copyright : Copyright 2012 Oculus VR, Inc. All Rights reserved. 1.13 1.14 Use of this software is subject to the terms of the Oculus license 1.15 agreement provided at the time of installation or download, or which 1.16 otherwise accompanies this software in either electronic or hard copy form. 1.17 1.18 ************************************************************************************/ 1.19 1.20 #ifndef OVR_Hash_h 1.21 #define OVR_Hash_h 1.22 1.23 #include "OVR_ContainerAllocator.h" 1.24 #include "OVR_Alg.h" 1.25 1.26 // 'new' operator is redefined/used in this file. 1.27 #undef new 1.28 1.29 namespace OVR { 1.30 1.31 //----------------------------------------------------------------------------------- 1.32 // ***** Hash Table Implementation 1.33 1.34 // HastSet and Hash. 1.35 // 1.36 // Hash table, linear probing, internal chaining. One interesting/nice thing 1.37 // about this implementation is that the table itself is a flat chunk of memory 1.38 // containing no pointers, only relative indices. If the key and value types 1.39 // of the Hash contain no pointers, then the Hash can be serialized using raw IO. 1.40 // 1.41 // Never shrinks, unless you explicitly Clear() it. Expands on 1.42 // demand, though. For best results, if you know roughly how big your 1.43 // table will be, default it to that size when you create it. 1.44 // 1.45 // Key usability feature: 1.46 // 1.47 // 1. Allows node hash values to either be cached or not. 1.48 // 1.49 // 2. Allows for alternative keys with methods such as GetAlt(). Handy 1.50 // if you need to search nodes by their components; no need to create 1.51 // temporary nodes. 1.52 // 1.53 1.54 1.55 // *** Hash functors: 1.56 // 1.57 // IdentityHash - use when the key is already a good hash 1.58 // HFixedSizeHash - general hash based on object's in-memory representation. 1.59 1.60 1.61 // Hash is just the input value; can use this for integer-indexed hash tables. 1.62 template<class C> 1.63 class IdentityHash 1.64 { 1.65 public: 1.66 UPInt operator()(const C& data) const 1.67 { return (UPInt) data; } 1.68 }; 1.69 1.70 // Computes a hash of an object's representation. 1.71 template<class C> 1.72 class FixedSizeHash 1.73 { 1.74 public: 1.75 // Alternative: "sdbm" hash function, suggested at same web page 1.76 // above, http::/www.cs.yorku.ca/~oz/hash.html 1.77 // This is somewhat slower then Bernstein, but it works way better than the above 1.78 // hash function for hashing large numbers of 32-bit ints. 1.79 static OVR_FORCE_INLINE UPInt SDBM_Hash(const void* data_in, UPInt size, UPInt seed = 5381) 1.80 { 1.81 const UByte* data = (const UByte*) data_in; 1.82 UPInt h = seed; 1.83 while (size > 0) 1.84 { 1.85 size--; 1.86 h = (h << 16) + (h << 6) - h + (UPInt)data[size]; 1.87 } 1.88 return h; 1.89 } 1.90 1.91 UPInt operator()(const C& data) const 1.92 { 1.93 unsigned char* p = (unsigned char*) &data; 1.94 int size = sizeof(C); 1.95 1.96 return SDBM_Hash(p, size); 1.97 } 1.98 }; 1.99 1.100 1.101 1.102 // *** HashsetEntry Entry types. 1.103 1.104 // Compact hash table Entry type that re-computes hash keys during hash traversal. 1.105 // Good to use if the hash function is cheap or the hash value is already cached in C. 1.106 template<class C, class HashF> 1.107 class HashsetEntry 1.108 { 1.109 public: 1.110 // Internal chaining for collisions. 1.111 SPInt NextInChain; 1.112 C Value; 1.113 1.114 HashsetEntry() 1.115 : NextInChain(-2) { } 1.116 HashsetEntry(const HashsetEntry& e) 1.117 : NextInChain(e.NextInChain), Value(e.Value) { } 1.118 HashsetEntry(const C& key, SPInt next) 1.119 : NextInChain(next), Value(key) { } 1.120 1.121 bool IsEmpty() const { return NextInChain == -2; } 1.122 bool IsEndOfChain() const { return NextInChain == -1; } 1.123 1.124 // Cached hash value access - can be optimized bu storing hash locally. 1.125 // Mask value only needs to be used if SetCachedHash is not implemented. 1.126 UPInt GetCachedHash(UPInt maskValue) const { return HashF()(Value) & maskValue; } 1.127 void SetCachedHash(UPInt) {} 1.128 1.129 void Clear() 1.130 { 1.131 Value.~C(); // placement delete 1.132 NextInChain = -2; 1.133 } 1.134 // Free is only used from dtor of hash; Clear is used during regular operations: 1.135 // assignment, hash reallocations, value reassignments, so on. 1.136 void Free() { Clear(); } 1.137 }; 1.138 1.139 // Hash table Entry type that caches the Entry hash value for nodes, so that it 1.140 // does not need to be re-computed during access. 1.141 template<class C, class HashF> 1.142 class HashsetCachedEntry 1.143 { 1.144 public: 1.145 // Internal chaining for collisions. 1.146 SPInt NextInChain; 1.147 UPInt HashValue; 1.148 C Value; 1.149 1.150 HashsetCachedEntry() 1.151 : NextInChain(-2) { } 1.152 HashsetCachedEntry(const HashsetCachedEntry& e) 1.153 : NextInChain(e.NextInChain), HashValue(e.HashValue), Value(e.Value) { } 1.154 HashsetCachedEntry(const C& key, SPInt next) 1.155 : NextInChain(next), Value(key) { } 1.156 1.157 bool IsEmpty() const { return NextInChain == -2; } 1.158 bool IsEndOfChain() const { return NextInChain == -1; } 1.159 1.160 // Cached hash value access - can be optimized bu storing hash locally. 1.161 // Mask value only needs to be used if SetCachedHash is not implemented. 1.162 UPInt GetCachedHash(UPInt maskValue) const { OVR_UNUSED(maskValue); return HashValue; } 1.163 void SetCachedHash(UPInt hashValue) { HashValue = hashValue; } 1.164 1.165 void Clear() 1.166 { 1.167 Value.~C(); 1.168 NextInChain = -2; 1.169 } 1.170 // Free is only used from dtor of hash; Clear is used during regular operations: 1.171 // assignment, hash reallocations, value reassignments, so on. 1.172 void Free() { Clear(); } 1.173 }; 1.174 1.175 1.176 //----------------------------------------------------------------------------------- 1.177 // *** HashSet implementation - relies on either cached or regular entries. 1.178 // 1.179 // Use: Entry = HashsetCachedEntry<C, HashF> if hashes are expensive to 1.180 // compute and thus need caching in entries. 1.181 // Entry = HashsetEntry<C, HashF> if hashes are already externally cached. 1.182 // 1.183 template<class C, class HashF = FixedSizeHash<C>, 1.184 class AltHashF = HashF, 1.185 class Allocator = ContainerAllocator<C>, 1.186 class Entry = HashsetCachedEntry<C, HashF> > 1.187 class HashSetBase 1.188 { 1.189 enum { HashMinSize = 8 }; 1.190 1.191 public: 1.192 OVR_MEMORY_REDEFINE_NEW(HashSetBase) 1.193 1.194 typedef HashSetBase<C, HashF, AltHashF, Allocator, Entry> SelfType; 1.195 1.196 HashSetBase() : pTable(NULL) { } 1.197 HashSetBase(int sizeHint) : pTable(NULL) { SetCapacity(this, sizeHint); } 1.198 HashSetBase(const SelfType& src) : pTable(NULL) { Assign(this, src); } 1.199 1.200 ~HashSetBase() 1.201 { 1.202 if (pTable) 1.203 { 1.204 // Delete the entries. 1.205 for (UPInt i = 0, n = pTable->SizeMask; i <= n; i++) 1.206 { 1.207 Entry* e = &E(i); 1.208 if (!e->IsEmpty()) 1.209 e->Free(); 1.210 } 1.211 1.212 Allocator::Free(pTable); 1.213 pTable = NULL; 1.214 } 1.215 } 1.216 1.217 1.218 void Assign(const SelfType& src) 1.219 { 1.220 Clear(); 1.221 if (src.IsEmpty() == false) 1.222 { 1.223 SetCapacity(src.GetSize()); 1.224 1.225 for (ConstIterator it = src.Begin(); it != src.End(); ++it) 1.226 { 1.227 Add(*it); 1.228 } 1.229 } 1.230 } 1.231 1.232 1.233 // Remove all entries from the HashSet table. 1.234 void Clear() 1.235 { 1.236 if (pTable) 1.237 { 1.238 // Delete the entries. 1.239 for (UPInt i = 0, n = pTable->SizeMask; i <= n; i++) 1.240 { 1.241 Entry* e = &E(i); 1.242 if (!e->IsEmpty()) 1.243 e->Clear(); 1.244 } 1.245 1.246 Allocator::Free(pTable); 1.247 pTable = NULL; 1.248 } 1.249 } 1.250 1.251 // Returns true if the HashSet is empty. 1.252 bool IsEmpty() const 1.253 { 1.254 return pTable == NULL || pTable->EntryCount == 0; 1.255 } 1.256 1.257 1.258 // Set a new or existing value under the key, to the value. 1.259 // Pass a different class of 'key' so that assignment reference object 1.260 // can be passed instead of the actual object. 1.261 template<class CRef> 1.262 void Set(const CRef& key) 1.263 { 1.264 UPInt hashValue = HashF()(key); 1.265 SPInt index = (SPInt)-1; 1.266 1.267 if (pTable != NULL) 1.268 index = findIndexCore(key, hashValue & pTable->SizeMask); 1.269 1.270 if (index >= 0) 1.271 { 1.272 E(index).Value = key; 1.273 } 1.274 else 1.275 { 1.276 // Entry under key doesn't exist. 1.277 add(key, hashValue); 1.278 } 1.279 } 1.280 1.281 template<class CRef> 1.282 inline void Add(const CRef& key) 1.283 { 1.284 UPInt hashValue = HashF()(key); 1.285 add(key, hashValue); 1.286 } 1.287 1.288 // Remove by alternative key. 1.289 template<class K> 1.290 void RemoveAlt(const K& key) 1.291 { 1.292 if (pTable == NULL) 1.293 return; 1.294 1.295 UPInt hashValue = AltHashF()(key); 1.296 SPInt index = hashValue & pTable->SizeMask; 1.297 1.298 Entry* e = &E(index); 1.299 1.300 // If empty node or occupied by collider, we have nothing to remove. 1.301 if (e->IsEmpty() || (e->GetCachedHash(pTable->SizeMask) != (UPInt)index)) 1.302 return; 1.303 1.304 // Save index 1.305 SPInt naturalIndex = index; 1.306 SPInt prevIndex = -1; 1.307 1.308 while ((e->GetCachedHash(pTable->SizeMask) != (UPInt)naturalIndex) || !(e->Value == key)) 1.309 { 1.310 // Keep looking through the chain. 1.311 prevIndex = index; 1.312 index = e->NextInChain; 1.313 if (index == -1) 1.314 return; // End of chain, item not found 1.315 e = &E(index); 1.316 } 1.317 1.318 // Found it - our item is at index 1.319 if (naturalIndex == index) 1.320 { 1.321 // If we have a follower, move it to us 1.322 if (!e->IsEndOfChain()) 1.323 { 1.324 Entry* enext = &E(e->NextInChain); 1.325 e->Clear(); 1.326 new (e) Entry(*enext); 1.327 // Point us to the follower's cell that will be cleared 1.328 e = enext; 1.329 } 1.330 } 1.331 else 1.332 { 1.333 // We are not at natural index, so deal with the prev items next index 1.334 E(prevIndex).NextInChain = e->NextInChain; 1.335 } 1.336 1.337 // Clear us, of the follower cell that was moved. 1.338 e->Clear(); 1.339 pTable->EntryCount --; 1.340 // Should we check the size to condense hash? ... 1.341 } 1.342 1.343 // Remove by main key. 1.344 template<class CRef> 1.345 void Remove(const CRef& key) 1.346 { 1.347 RemoveAlt(key); 1.348 } 1.349 1.350 // Retrieve the pointer to a value under the given key. 1.351 // - If there's no value under the key, then return NULL. 1.352 // - If there is a value, return the pointer. 1.353 template<class K> 1.354 C* Get(const K& key) 1.355 { 1.356 SPInt index = findIndex(key); 1.357 if (index >= 0) 1.358 return &E(index).Value; 1.359 return 0; 1.360 } 1.361 1.362 template<class K> 1.363 const C* Get(const K& key) const 1.364 { 1.365 SPInt index = findIndex(key); 1.366 if (index >= 0) 1.367 return &E(index).Value; 1.368 return 0; 1.369 } 1.370 1.371 // Alternative key versions of Get. Used by Hash. 1.372 template<class K> 1.373 const C* GetAlt(const K& key) const 1.374 { 1.375 SPInt index = findIndexAlt(key); 1.376 if (index >= 0) 1.377 return &E(index).Value; 1.378 return 0; 1.379 } 1.380 1.381 template<class K> 1.382 C* GetAlt(const K& key) 1.383 { 1.384 SPInt index = findIndexAlt(key); 1.385 if (index >= 0) 1.386 return &E(index).Value; 1.387 return 0; 1.388 } 1.389 1.390 template<class K> 1.391 bool GetAlt(const K& key, C* pval) const 1.392 { 1.393 SPInt index = findIndexAlt(key); 1.394 if (index >= 0) 1.395 { 1.396 if (pval) 1.397 *pval = E(index).Value; 1.398 return true; 1.399 } 1.400 return false; 1.401 } 1.402 1.403 1.404 UPInt GetSize() const 1.405 { 1.406 return pTable == NULL ? 0 : (UPInt)pTable->EntryCount; 1.407 } 1.408 1.409 1.410 // Resize the HashSet table to fit one more Entry. Often this 1.411 // doesn't involve any action. 1.412 void CheckExpand() 1.413 { 1.414 if (pTable == NULL) 1.415 { 1.416 // Initial creation of table. Make a minimum-sized table. 1.417 setRawCapacity(HashMinSize); 1.418 } 1.419 else if (pTable->EntryCount * 5 > (pTable->SizeMask + 1) * 4) 1.420 { 1.421 // pTable is more than 5/4 ths full. Expand. 1.422 setRawCapacity((pTable->SizeMask + 1) * 2); 1.423 } 1.424 } 1.425 1.426 // Hint the bucket count to >= n. 1.427 void Resize(UPInt n) 1.428 { 1.429 // Not really sure what this means in relation to 1.430 // STLport's hash_map... they say they "increase the 1.431 // bucket count to at least n" -- but does that mean 1.432 // their real capacity after Resize(n) is more like 1.433 // n*2 (since they do linked-list chaining within 1.434 // buckets?). 1.435 SetCapacity(n); 1.436 } 1.437 1.438 // Size the HashSet so that it can comfortably contain the given 1.439 // number of elements. If the HashSet already contains more 1.440 // elements than newSize, then this may be a no-op. 1.441 void SetCapacity(UPInt newSize) 1.442 { 1.443 UPInt newRawSize = (newSize * 5) / 4; 1.444 if (newRawSize <= GetSize()) 1.445 return; 1.446 setRawCapacity(newRawSize); 1.447 } 1.448 1.449 // Disable inappropriate 'operator ->' warning on MSVC6. 1.450 #ifdef OVR_CC_MSVC 1.451 #if (OVR_CC_MSVC < 1300) 1.452 # pragma warning(disable : 4284) 1.453 #endif 1.454 #endif 1.455 1.456 // Iterator API, like STL. 1.457 struct ConstIterator 1.458 { 1.459 const C& operator * () const 1.460 { 1.461 OVR_ASSERT(Index >= 0 && Index <= (SPInt)pHash->pTable->SizeMask); 1.462 return pHash->E(Index).Value; 1.463 } 1.464 1.465 const C* operator -> () const 1.466 { 1.467 OVR_ASSERT(Index >= 0 && Index <= (SPInt)pHash->pTable->SizeMask); 1.468 return &pHash->E(Index).Value; 1.469 } 1.470 1.471 void operator ++ () 1.472 { 1.473 // Find next non-empty Entry. 1.474 if (Index <= (SPInt)pHash->pTable->SizeMask) 1.475 { 1.476 Index++; 1.477 while ((UPInt)Index <= pHash->pTable->SizeMask && 1.478 pHash->E(Index).IsEmpty()) 1.479 { 1.480 Index++; 1.481 } 1.482 } 1.483 } 1.484 1.485 bool operator == (const ConstIterator& it) const 1.486 { 1.487 if (IsEnd() && it.IsEnd()) 1.488 { 1.489 return true; 1.490 } 1.491 else 1.492 { 1.493 return (pHash == it.pHash) && (Index == it.Index); 1.494 } 1.495 } 1.496 1.497 bool operator != (const ConstIterator& it) const 1.498 { 1.499 return ! (*this == it); 1.500 } 1.501 1.502 1.503 bool IsEnd() const 1.504 { 1.505 return (pHash == NULL) || 1.506 (pHash->pTable == NULL) || 1.507 (Index > (SPInt)pHash->pTable->SizeMask); 1.508 } 1.509 1.510 ConstIterator() 1.511 : pHash(NULL), Index(0) 1.512 { } 1.513 1.514 public: 1.515 // Constructor was intentionally made public to allow create 1.516 // iterator with arbitrary index. 1.517 ConstIterator(const SelfType* h, SPInt index) 1.518 : pHash(h), Index(index) 1.519 { } 1.520 1.521 const SelfType* GetContainer() const 1.522 { 1.523 return pHash; 1.524 } 1.525 SPInt GetIndex() const 1.526 { 1.527 return Index; 1.528 } 1.529 1.530 protected: 1.531 friend class HashSetBase<C, HashF, AltHashF, Allocator, Entry>; 1.532 1.533 const SelfType* pHash; 1.534 SPInt Index; 1.535 }; 1.536 1.537 friend struct ConstIterator; 1.538 1.539 1.540 // Non-const Iterator; Get most of it from ConstIterator. 1.541 struct Iterator : public ConstIterator 1.542 { 1.543 // Allow non-const access to entries. 1.544 C& operator*() const 1.545 { 1.546 OVR_ASSERT(ConstIterator::Index >= 0 && ConstIterator::Index <= (SPInt)ConstIterator::pHash->pTable->SizeMask); 1.547 return const_cast<SelfType*>(ConstIterator::pHash)->E(ConstIterator::Index).Value; 1.548 } 1.549 1.550 C* operator->() const 1.551 { 1.552 return &(operator*()); 1.553 } 1.554 1.555 Iterator() 1.556 : ConstIterator(NULL, 0) 1.557 { } 1.558 1.559 // Removes current element from Hash 1.560 void Remove() 1.561 { 1.562 RemoveAlt(operator*()); 1.563 } 1.564 1.565 template <class K> 1.566 void RemoveAlt(const K& key) 1.567 { 1.568 SelfType* phash = const_cast<SelfType*>(ConstIterator::pHash); 1.569 //Entry* ee = &phash->E(ConstIterator::Index); 1.570 //const C& key = ee->Value; 1.571 1.572 UPInt hashValue = AltHashF()(key); 1.573 SPInt index = hashValue & phash->pTable->SizeMask; 1.574 1.575 Entry* e = &phash->E(index); 1.576 1.577 // If empty node or occupied by collider, we have nothing to remove. 1.578 if (e->IsEmpty() || (e->GetCachedHash(phash->pTable->SizeMask) != (UPInt)index)) 1.579 return; 1.580 1.581 // Save index 1.582 SPInt naturalIndex = index; 1.583 SPInt prevIndex = -1; 1.584 1.585 while ((e->GetCachedHash(phash->pTable->SizeMask) != (UPInt)naturalIndex) || !(e->Value == key)) 1.586 { 1.587 // Keep looking through the chain. 1.588 prevIndex = index; 1.589 index = e->NextInChain; 1.590 if (index == -1) 1.591 return; // End of chain, item not found 1.592 e = &phash->E(index); 1.593 } 1.594 1.595 if (index == (SPInt)ConstIterator::Index) 1.596 { 1.597 // Found it - our item is at index 1.598 if (naturalIndex == index) 1.599 { 1.600 // If we have a follower, move it to us 1.601 if (!e->IsEndOfChain()) 1.602 { 1.603 Entry* enext = &phash->E(e->NextInChain); 1.604 e->Clear(); 1.605 new (e) Entry(*enext); 1.606 // Point us to the follower's cell that will be cleared 1.607 e = enext; 1.608 --ConstIterator::Index; 1.609 } 1.610 } 1.611 else 1.612 { 1.613 // We are not at natural index, so deal with the prev items next index 1.614 phash->E(prevIndex).NextInChain = e->NextInChain; 1.615 } 1.616 1.617 // Clear us, of the follower cell that was moved. 1.618 e->Clear(); 1.619 phash->pTable->EntryCount --; 1.620 } 1.621 else 1.622 OVR_ASSERT(0); //? 1.623 } 1.624 1.625 private: 1.626 friend class HashSetBase<C, HashF, AltHashF, Allocator, Entry>; 1.627 1.628 Iterator(SelfType* h, SPInt i0) 1.629 : ConstIterator(h, i0) 1.630 { } 1.631 }; 1.632 1.633 friend struct Iterator; 1.634 1.635 Iterator Begin() 1.636 { 1.637 if (pTable == 0) 1.638 return Iterator(NULL, 0); 1.639 1.640 // Scan till we hit the First valid Entry. 1.641 UPInt i0 = 0; 1.642 while (i0 <= pTable->SizeMask && E(i0).IsEmpty()) 1.643 { 1.644 i0++; 1.645 } 1.646 return Iterator(this, i0); 1.647 } 1.648 Iterator End() { return Iterator(NULL, 0); } 1.649 1.650 ConstIterator Begin() const { return const_cast<SelfType*>(this)->Begin(); } 1.651 ConstIterator End() const { return const_cast<SelfType*>(this)->End(); } 1.652 1.653 template<class K> 1.654 Iterator Find(const K& key) 1.655 { 1.656 SPInt index = findIndex(key); 1.657 if (index >= 0) 1.658 return Iterator(this, index); 1.659 return Iterator(NULL, 0); 1.660 } 1.661 1.662 template<class K> 1.663 Iterator FindAlt(const K& key) 1.664 { 1.665 SPInt index = findIndexAlt(key); 1.666 if (index >= 0) 1.667 return Iterator(this, index); 1.668 return Iterator(NULL, 0); 1.669 } 1.670 1.671 template<class K> 1.672 ConstIterator Find(const K& key) const { return const_cast<SelfType*>(this)->Find(key); } 1.673 1.674 template<class K> 1.675 ConstIterator FindAlt(const K& key) const { return const_cast<SelfType*>(this)->FindAlt(key); } 1.676 1.677 private: 1.678 // Find the index of the matching Entry. If no match, then return -1. 1.679 template<class K> 1.680 SPInt findIndex(const K& key) const 1.681 { 1.682 if (pTable == NULL) 1.683 return -1; 1.684 UPInt hashValue = HashF()(key) & pTable->SizeMask; 1.685 return findIndexCore(key, hashValue); 1.686 } 1.687 1.688 template<class K> 1.689 SPInt findIndexAlt(const K& key) const 1.690 { 1.691 if (pTable == NULL) 1.692 return -1; 1.693 UPInt hashValue = AltHashF()(key) & pTable->SizeMask; 1.694 return findIndexCore(key, hashValue); 1.695 } 1.696 1.697 // Find the index of the matching Entry. If no match, then return -1. 1.698 template<class K> 1.699 SPInt findIndexCore(const K& key, UPInt hashValue) const 1.700 { 1.701 // Table must exist. 1.702 OVR_ASSERT(pTable != 0); 1.703 // Hash key must be 'and-ed' by the caller. 1.704 OVR_ASSERT((hashValue & ~pTable->SizeMask) == 0); 1.705 1.706 UPInt index = hashValue; 1.707 const Entry* e = &E(index); 1.708 1.709 // If empty or occupied by a collider, not found. 1.710 if (e->IsEmpty() || (e->GetCachedHash(pTable->SizeMask) != index)) 1.711 return -1; 1.712 1.713 while(1) 1.714 { 1.715 OVR_ASSERT(e->GetCachedHash(pTable->SizeMask) == hashValue); 1.716 1.717 if (e->GetCachedHash(pTable->SizeMask) == hashValue && e->Value == key) 1.718 { 1.719 // Found it. 1.720 return index; 1.721 } 1.722 // Values can not be equal at this point. 1.723 // That would mean that the hash key for the same value differs. 1.724 OVR_ASSERT(!(e->Value == key)); 1.725 1.726 // Keep looking through the chain. 1.727 index = e->NextInChain; 1.728 if (index == (UPInt)-1) 1.729 break; // end of chain 1.730 1.731 e = &E(index); 1.732 OVR_ASSERT(!e->IsEmpty()); 1.733 } 1.734 return -1; 1.735 } 1.736 1.737 1.738 // Add a new value to the HashSet table, under the specified key. 1.739 template<class CRef> 1.740 void add(const CRef& key, UPInt hashValue) 1.741 { 1.742 CheckExpand(); 1.743 hashValue &= pTable->SizeMask; 1.744 1.745 pTable->EntryCount++; 1.746 1.747 SPInt index = hashValue; 1.748 Entry* naturalEntry = &(E(index)); 1.749 1.750 if (naturalEntry->IsEmpty()) 1.751 { 1.752 // Put the new Entry in. 1.753 new (naturalEntry) Entry(key, -1); 1.754 } 1.755 else 1.756 { 1.757 // Find a blank spot. 1.758 SPInt blankIndex = index; 1.759 do { 1.760 blankIndex = (blankIndex + 1) & pTable->SizeMask; 1.761 } while(!E(blankIndex).IsEmpty()); 1.762 1.763 Entry* blankEntry = &E(blankIndex); 1.764 1.765 if (naturalEntry->GetCachedHash(pTable->SizeMask) == (UPInt)index) 1.766 { 1.767 // Collision. Link into this chain. 1.768 1.769 // Move existing list head. 1.770 new (blankEntry) Entry(*naturalEntry); // placement new, copy ctor 1.771 1.772 // Put the new info in the natural Entry. 1.773 naturalEntry->Value = key; 1.774 naturalEntry->NextInChain = blankIndex; 1.775 } 1.776 else 1.777 { 1.778 // Existing Entry does not naturally 1.779 // belong in this slot. Existing 1.780 // Entry must be moved. 1.781 1.782 // Find natural location of collided element (i.e. root of chain) 1.783 SPInt collidedIndex = naturalEntry->GetCachedHash(pTable->SizeMask); 1.784 OVR_ASSERT(collidedIndex >= 0 && collidedIndex <= (SPInt)pTable->SizeMask); 1.785 for (;;) 1.786 { 1.787 Entry* e = &E(collidedIndex); 1.788 if (e->NextInChain == index) 1.789 { 1.790 // Here's where we need to splice. 1.791 new (blankEntry) Entry(*naturalEntry); 1.792 e->NextInChain = blankIndex; 1.793 break; 1.794 } 1.795 collidedIndex = e->NextInChain; 1.796 OVR_ASSERT(collidedIndex >= 0 && collidedIndex <= (SPInt)pTable->SizeMask); 1.797 } 1.798 1.799 // Put the new data in the natural Entry. 1.800 naturalEntry->Value = key; 1.801 naturalEntry->NextInChain = -1; 1.802 } 1.803 } 1.804 1.805 // Record hash value: has effect only if cached node is used. 1.806 naturalEntry->SetCachedHash(hashValue); 1.807 } 1.808 1.809 // Index access helpers. 1.810 Entry& E(UPInt index) 1.811 { 1.812 // Must have pTable and access needs to be within bounds. 1.813 OVR_ASSERT(index <= pTable->SizeMask); 1.814 return *(((Entry*) (pTable + 1)) + index); 1.815 } 1.816 const Entry& E(UPInt index) const 1.817 { 1.818 OVR_ASSERT(index <= pTable->SizeMask); 1.819 return *(((Entry*) (pTable + 1)) + index); 1.820 } 1.821 1.822 1.823 // Resize the HashSet table to the given size (Rehash the 1.824 // contents of the current table). The arg is the number of 1.825 // HashSet table entries, not the number of elements we should 1.826 // actually contain (which will be less than this). 1.827 void setRawCapacity(UPInt newSize) 1.828 { 1.829 if (newSize == 0) 1.830 { 1.831 // Special case. 1.832 Clear(); 1.833 return; 1.834 } 1.835 1.836 // Minimum size; don't incur rehashing cost when expanding 1.837 // very small tables. Not that we perform this check before 1.838 // 'log2f' call to avoid fp exception with newSize == 1. 1.839 if (newSize < HashMinSize) 1.840 newSize = HashMinSize; 1.841 else 1.842 { 1.843 // Force newSize to be a power of two. 1.844 int bits = Alg::UpperBit(newSize-1) + 1; // Chop( Log2f((float)(newSize-1)) + 1); 1.845 OVR_ASSERT((UPInt(1) << bits) >= newSize); 1.846 newSize = UPInt(1) << bits; 1.847 } 1.848 1.849 SelfType newHash; 1.850 newHash.pTable = (TableType*) 1.851 Allocator::Alloc( 1.852 sizeof(TableType) + sizeof(Entry) * newSize); 1.853 // Need to do something on alloc failure! 1.854 OVR_ASSERT(newHash.pTable); 1.855 1.856 newHash.pTable->EntryCount = 0; 1.857 newHash.pTable->SizeMask = newSize - 1; 1.858 UPInt i, n; 1.859 1.860 // Mark all entries as empty. 1.861 for (i = 0; i < newSize; i++) 1.862 newHash.E(i).NextInChain = -2; 1.863 1.864 // Copy stuff to newHash 1.865 if (pTable) 1.866 { 1.867 for (i = 0, n = pTable->SizeMask; i <= n; i++) 1.868 { 1.869 Entry* e = &E(i); 1.870 if (e->IsEmpty() == false) 1.871 { 1.872 // Insert old Entry into new HashSet. 1.873 newHash.Add(e->Value); 1.874 // placement delete of old element 1.875 e->Clear(); 1.876 } 1.877 } 1.878 1.879 // Delete our old data buffer. 1.880 Allocator::Free(pTable); 1.881 } 1.882 1.883 // Steal newHash's data. 1.884 pTable = newHash.pTable; 1.885 newHash.pTable = NULL; 1.886 } 1.887 1.888 struct TableType 1.889 { 1.890 UPInt EntryCount; 1.891 UPInt SizeMask; 1.892 // Entry array follows this structure 1.893 // in memory. 1.894 }; 1.895 TableType* pTable; 1.896 }; 1.897 1.898 1.899 1.900 //----------------------------------------------------------------------------------- 1.901 template<class C, class HashF = FixedSizeHash<C>, 1.902 class AltHashF = HashF, 1.903 class Allocator = ContainerAllocator<C>, 1.904 class Entry = HashsetCachedEntry<C, HashF> > 1.905 class HashSet : public HashSetBase<C, HashF, AltHashF, Allocator, Entry> 1.906 { 1.907 public: 1.908 typedef HashSetBase<C, HashF, AltHashF, Allocator, Entry> BaseType; 1.909 typedef HashSet<C, HashF, AltHashF, Allocator, Entry> SelfType; 1.910 1.911 HashSet() { } 1.912 HashSet(int sizeHint) : BaseType(sizeHint) { } 1.913 HashSet(const SelfType& src) : BaseType(src) { } 1.914 ~HashSet() { } 1.915 1.916 void operator = (const SelfType& src) { BaseType::Assign(src); } 1.917 1.918 // Set a new or existing value under the key, to the value. 1.919 // Pass a different class of 'key' so that assignment reference object 1.920 // can be passed instead of the actual object. 1.921 template<class CRef> 1.922 void Set(const CRef& key) 1.923 { 1.924 BaseType::Set(key); 1.925 } 1.926 1.927 template<class CRef> 1.928 inline void Add(const CRef& key) 1.929 { 1.930 BaseType::Add(key); 1.931 } 1.932 1.933 // Hint the bucket count to >= n. 1.934 void Resize(UPInt n) 1.935 { 1.936 BaseType::SetCapacity(n); 1.937 } 1.938 1.939 // Size the HashSet so that it can comfortably contain the given 1.940 // number of elements. If the HashSet already contains more 1.941 // elements than newSize, then this may be a no-op. 1.942 void SetCapacity(UPInt newSize) 1.943 { 1.944 BaseType::SetCapacity(newSize); 1.945 } 1.946 1.947 }; 1.948 1.949 // HashSet with uncached hash code; declared for convenience. 1.950 template<class C, class HashF = FixedSizeHash<C>, 1.951 class AltHashF = HashF, 1.952 class Allocator = ContainerAllocator<C> > 1.953 class HashSetUncached : public HashSet<C, HashF, AltHashF, Allocator, HashsetEntry<C, HashF> > 1.954 { 1.955 public: 1.956 1.957 typedef HashSetUncached<C, HashF, AltHashF, Allocator> SelfType; 1.958 typedef HashSet<C, HashF, AltHashF, Allocator, HashsetEntry<C, HashF> > BaseType; 1.959 1.960 // Delegated constructors. 1.961 HashSetUncached() { } 1.962 HashSetUncached(int sizeHint) : BaseType(sizeHint) { } 1.963 HashSetUncached(const SelfType& src) : BaseType(src) { } 1.964 ~HashSetUncached() { } 1.965 1.966 void operator = (const SelfType& src) 1.967 { 1.968 BaseType::operator = (src); 1.969 } 1.970 }; 1.971 1.972 1.973 //----------------------------------------------------------------------------------- 1.974 // ***** Hash hash table implementation 1.975 1.976 // Node for Hash - necessary so that Hash can delegate its implementation 1.977 // to HashSet. 1.978 template<class C, class U, class HashF> 1.979 struct HashNode 1.980 { 1.981 typedef HashNode<C, U, HashF> SelfType; 1.982 typedef C FirstType; 1.983 typedef U SecondType; 1.984 1.985 C First; 1.986 U Second; 1.987 1.988 // NodeRef is used to allow passing of elements into HashSet 1.989 // without using a temporary object. 1.990 struct NodeRef 1.991 { 1.992 const C* pFirst; 1.993 const U* pSecond; 1.994 1.995 NodeRef(const C& f, const U& s) : pFirst(&f), pSecond(&s) { } 1.996 NodeRef(const NodeRef& src) : pFirst(src.pFirst), pSecond(src.pSecond) { } 1.997 1.998 // Enable computation of ghash_node_hashf. 1.999 inline UPInt GetHash() const { return HashF()(*pFirst); } 1.1000 // Necessary conversion to allow HashNode::operator == to work. 1.1001 operator const C& () const { return *pFirst; } 1.1002 }; 1.1003 1.1004 // Note: No default constructor is necessary. 1.1005 HashNode(const HashNode& src) : First(src.First), Second(src.Second) { } 1.1006 HashNode(const NodeRef& src) : First(*src.pFirst), Second(*src.pSecond) { } 1.1007 void operator = (const NodeRef& src) { First = *src.pFirst; Second = *src.pSecond; } 1.1008 1.1009 template<class K> 1.1010 bool operator == (const K& src) const { return (First == src); } 1.1011 1.1012 template<class K> 1.1013 static UPInt CalcHash(const K& data) { return HashF()(data); } 1.1014 inline UPInt GetHash() const { return HashF()(First); } 1.1015 1.1016 // Hash functors used with this node. A separate functor is used for alternative 1.1017 // key lookup so that it does not need to access the '.First' element. 1.1018 struct NodeHashF 1.1019 { 1.1020 template<class K> 1.1021 UPInt operator()(const K& data) const { return data.GetHash(); } 1.1022 }; 1.1023 struct NodeAltHashF 1.1024 { 1.1025 template<class K> 1.1026 UPInt operator()(const K& data) const { return HashNode<C,U,HashF>::CalcHash(data); } 1.1027 }; 1.1028 }; 1.1029 1.1030 1.1031 1.1032 // **** Extra hashset_entry types to allow NodeRef construction. 1.1033 1.1034 // The big difference between the below types and the ones used in hash_set is that 1.1035 // these allow initializing the node with 'typename C::NodeRef& keyRef', which 1.1036 // is critical to avoid temporary node allocation on stack when using placement new. 1.1037 1.1038 // Compact hash table Entry type that re-computes hash keys during hash traversal. 1.1039 // Good to use if the hash function is cheap or the hash value is already cached in C. 1.1040 template<class C, class HashF> 1.1041 class HashsetNodeEntry 1.1042 { 1.1043 public: 1.1044 // Internal chaining for collisions. 1.1045 SPInt NextInChain; 1.1046 C Value; 1.1047 1.1048 HashsetNodeEntry() 1.1049 : NextInChain(-2) { } 1.1050 HashsetNodeEntry(const HashsetNodeEntry& e) 1.1051 : NextInChain(e.NextInChain), Value(e.Value) { } 1.1052 HashsetNodeEntry(const C& key, SPInt next) 1.1053 : NextInChain(next), Value(key) { } 1.1054 HashsetNodeEntry(const typename C::NodeRef& keyRef, SPInt next) 1.1055 : NextInChain(next), Value(keyRef) { } 1.1056 1.1057 bool IsEmpty() const { return NextInChain == -2; } 1.1058 bool IsEndOfChain() const { return NextInChain == -1; } 1.1059 UPInt GetCachedHash(UPInt maskValue) const { return HashF()(Value) & maskValue; } 1.1060 void SetCachedHash(UPInt hashValue) { OVR_UNUSED(hashValue); } 1.1061 1.1062 void Clear() 1.1063 { 1.1064 Value.~C(); // placement delete 1.1065 NextInChain = -2; 1.1066 } 1.1067 // Free is only used from dtor of hash; Clear is used during regular operations: 1.1068 // assignment, hash reallocations, value reassignments, so on. 1.1069 void Free() { Clear(); } 1.1070 }; 1.1071 1.1072 // Hash table Entry type that caches the Entry hash value for nodes, so that it 1.1073 // does not need to be re-computed during access. 1.1074 template<class C, class HashF> 1.1075 class HashsetCachedNodeEntry 1.1076 { 1.1077 public: 1.1078 // Internal chaining for collisions. 1.1079 SPInt NextInChain; 1.1080 UPInt HashValue; 1.1081 C Value; 1.1082 1.1083 HashsetCachedNodeEntry() 1.1084 : NextInChain(-2) { } 1.1085 HashsetCachedNodeEntry(const HashsetCachedNodeEntry& e) 1.1086 : NextInChain(e.NextInChain), HashValue(e.HashValue), Value(e.Value) { } 1.1087 HashsetCachedNodeEntry(const C& key, SPInt next) 1.1088 : NextInChain(next), Value(key) { } 1.1089 HashsetCachedNodeEntry(const typename C::NodeRef& keyRef, SPInt next) 1.1090 : NextInChain(next), Value(keyRef) { } 1.1091 1.1092 bool IsEmpty() const { return NextInChain == -2; } 1.1093 bool IsEndOfChain() const { return NextInChain == -1; } 1.1094 UPInt GetCachedHash(UPInt maskValue) const { OVR_UNUSED(maskValue); return HashValue; } 1.1095 void SetCachedHash(UPInt hashValue) { HashValue = hashValue; } 1.1096 1.1097 void Clear() 1.1098 { 1.1099 Value.~C(); 1.1100 NextInChain = -2; 1.1101 } 1.1102 // Free is only used from dtor of hash; Clear is used during regular operations: 1.1103 // assignment, hash reallocations, value reassignments, so on. 1.1104 void Free() { Clear(); } 1.1105 }; 1.1106 1.1107 1.1108 //----------------------------------------------------------------------------------- 1.1109 template<class C, class U, 1.1110 class HashF = FixedSizeHash<C>, 1.1111 class Allocator = ContainerAllocator<C>, 1.1112 class HashNode = OVR::HashNode<C,U,HashF>, 1.1113 class Entry = HashsetCachedNodeEntry<HashNode, typename HashNode::NodeHashF>, 1.1114 class Container = HashSet<HashNode, typename HashNode::NodeHashF, 1.1115 typename HashNode::NodeAltHashF, Allocator, 1.1116 Entry> > 1.1117 class Hash 1.1118 { 1.1119 public: 1.1120 OVR_MEMORY_REDEFINE_NEW(Hash) 1.1121 1.1122 // Types used for hash_set. 1.1123 typedef U ValueType; 1.1124 typedef Hash<C, U, HashF, Allocator, HashNode, Entry, Container> SelfType; 1.1125 1.1126 // Actual hash table itself, implemented as hash_set. 1.1127 Container mHash; 1.1128 1.1129 public: 1.1130 Hash() { } 1.1131 Hash(int sizeHint) : mHash(sizeHint) { } 1.1132 Hash(const SelfType& src) : mHash(src.mHash) { } 1.1133 ~Hash() { } 1.1134 1.1135 void operator = (const SelfType& src) { mHash = src.mHash; } 1.1136 1.1137 // Remove all entries from the Hash table. 1.1138 inline void Clear() { mHash.Clear(); } 1.1139 // Returns true if the Hash is empty. 1.1140 inline bool IsEmpty() const { return mHash.IsEmpty(); } 1.1141 1.1142 // Access (set). 1.1143 inline void Set(const C& key, const U& value) 1.1144 { 1.1145 typename HashNode::NodeRef e(key, value); 1.1146 mHash.Set(e); 1.1147 } 1.1148 inline void Add(const C& key, const U& value) 1.1149 { 1.1150 typename HashNode::NodeRef e(key, value); 1.1151 mHash.Add(e); 1.1152 } 1.1153 1.1154 // Removes an element by clearing its Entry. 1.1155 inline void Remove(const C& key) 1.1156 { 1.1157 mHash.RemoveAlt(key); 1.1158 } 1.1159 template<class K> 1.1160 inline void RemoveAlt(const K& key) 1.1161 { 1.1162 mHash.RemoveAlt(key); 1.1163 } 1.1164 1.1165 // Retrieve the value under the given key. 1.1166 // - If there's no value under the key, then return false and leave *pvalue alone. 1.1167 // - If there is a value, return true, and Set *Pvalue to the Entry's value. 1.1168 // - If value == NULL, return true or false according to the presence of the key. 1.1169 bool Get(const C& key, U* pvalue) const 1.1170 { 1.1171 const HashNode* p = mHash.GetAlt(key); 1.1172 if (p) 1.1173 { 1.1174 if (pvalue) 1.1175 *pvalue = p->Second; 1.1176 return true; 1.1177 } 1.1178 return false; 1.1179 } 1.1180 1.1181 template<class K> 1.1182 bool GetAlt(const K& key, U* pvalue) const 1.1183 { 1.1184 const HashNode* p = mHash.GetAlt(key); 1.1185 if (p) 1.1186 { 1.1187 if (pvalue) 1.1188 *pvalue = p->Second; 1.1189 return true; 1.1190 } 1.1191 return false; 1.1192 } 1.1193 1.1194 // Retrieve the pointer to a value under the given key. 1.1195 // - If there's no value under the key, then return NULL. 1.1196 // - If there is a value, return the pointer. 1.1197 inline U* Get(const C& key) 1.1198 { 1.1199 HashNode* p = mHash.GetAlt(key); 1.1200 return p ? &p->Second : 0; 1.1201 } 1.1202 inline const U* Get(const C& key) const 1.1203 { 1.1204 const HashNode* p = mHash.GetAlt(key); 1.1205 return p ? &p->Second : 0; 1.1206 } 1.1207 1.1208 template<class K> 1.1209 inline U* GetAlt(const K& key) 1.1210 { 1.1211 HashNode* p = mHash.GetAlt(key); 1.1212 return p ? &p->Second : 0; 1.1213 } 1.1214 template<class K> 1.1215 inline const U* GetAlt(const K& key) const 1.1216 { 1.1217 const HashNode* p = mHash.GetAlt(key); 1.1218 return p ? &p->Second : 0; 1.1219 } 1.1220 1.1221 // Sizing methods - delegate to Hash. 1.1222 inline UPInt GetSize() const { return mHash.GetSize(); } 1.1223 inline void Resize(UPInt n) { mHash.Resize(n); } 1.1224 inline void SetCapacity(UPInt newSize) { mHash.SetCapacity(newSize); } 1.1225 1.1226 // Iterator API, like STL. 1.1227 typedef typename Container::ConstIterator ConstIterator; 1.1228 typedef typename Container::Iterator Iterator; 1.1229 1.1230 inline Iterator Begin() { return mHash.Begin(); } 1.1231 inline Iterator End() { return mHash.End(); } 1.1232 inline ConstIterator Begin() const { return mHash.Begin(); } 1.1233 inline ConstIterator End() const { return mHash.End(); } 1.1234 1.1235 Iterator Find(const C& key) { return mHash.FindAlt(key); } 1.1236 ConstIterator Find(const C& key) const { return mHash.FindAlt(key); } 1.1237 1.1238 template<class K> 1.1239 Iterator FindAlt(const K& key) { return mHash.FindAlt(key); } 1.1240 template<class K> 1.1241 ConstIterator FindAlt(const K& key) const { return mHash.FindAlt(key); } 1.1242 }; 1.1243 1.1244 1.1245 1.1246 // Hash with uncached hash code; declared for convenience. 1.1247 template<class C, class U, class HashF = FixedSizeHash<C>, class Allocator = ContainerAllocator<C> > 1.1248 class HashUncached 1.1249 : public Hash<C, U, HashF, Allocator, HashNode<C,U,HashF>, 1.1250 HashsetNodeEntry<HashNode<C,U,HashF>, typename HashNode<C,U,HashF>::NodeHashF> > 1.1251 { 1.1252 public: 1.1253 typedef HashUncached<C, U, HashF, Allocator> SelfType; 1.1254 typedef Hash<C, U, HashF, Allocator, HashNode<C,U,HashF>, 1.1255 HashsetNodeEntry<HashNode<C,U,HashF>, 1.1256 typename HashNode<C,U,HashF>::NodeHashF> > BaseType; 1.1257 1.1258 // Delegated constructors. 1.1259 HashUncached() { } 1.1260 HashUncached(int sizeHint) : BaseType(sizeHint) { } 1.1261 HashUncached(const SelfType& src) : BaseType(src) { } 1.1262 ~HashUncached() { } 1.1263 void operator = (const SelfType& src) { BaseType::operator = (src); } 1.1264 }; 1.1265 1.1266 1.1267 1.1268 // And identity hash in which keys serve as hash value. Can be uncached, 1.1269 // since hash computation is assumed cheap. 1.1270 template<class C, class U, class Allocator = ContainerAllocator<C>, class HashF = IdentityHash<C> > 1.1271 class HashIdentity 1.1272 : public HashUncached<C, U, HashF, Allocator> 1.1273 { 1.1274 public: 1.1275 typedef HashIdentity<C, U, Allocator, HashF> SelfType; 1.1276 typedef HashUncached<C, U, HashF, Allocator> BaseType; 1.1277 1.1278 // Delegated constructors. 1.1279 HashIdentity() { } 1.1280 HashIdentity(int sizeHint) : BaseType(sizeHint) { } 1.1281 HashIdentity(const SelfType& src) : BaseType(src) { } 1.1282 ~HashIdentity() { } 1.1283 void operator = (const SelfType& src) { BaseType::operator = (src); } 1.1284 }; 1.1285 1.1286 1.1287 } // OVR 1.1288 1.1289 1.1290 #ifdef OVR_DEFINE_NEW 1.1291 #define new OVR_DEFINE_NEW 1.1292 #endif 1.1293 1.1294 #endif 1.1295 \ No newline at end of file