oculus1

annotate libovr/Src/Kernel/OVR_Hash.h @ 3:b069a5c27388

find changesets by author, revision, files, or words in the commit message
added a couple more stuff, fixed all the LibOVR line endings
author John Tsiombikas <nuclear@member.fsf.org>
date Sun, 15 Sep 2013 04:10:05 +0300
parents e2f9e4603129
children
rev   line source
nuclear@3 1 /************************************************************************************
nuclear@3 2
nuclear@3 3 PublicHeader: None
nuclear@3 4 Filename : OVR_Hash.h
nuclear@3 5 Content : Template hash-table/set implementation
nuclear@3 6 Created : September 19, 2012
nuclear@3 7 Notes :
nuclear@3 8
nuclear@3 9 Copyright : Copyright 2012 Oculus VR, Inc. All Rights reserved.
nuclear@3 10
nuclear@3 11 Use of this software is subject to the terms of the Oculus license
nuclear@3 12 agreement provided at the time of installation or download, or which
nuclear@3 13 otherwise accompanies this software in either electronic or hard copy form.
nuclear@3 14
nuclear@3 15 ************************************************************************************/
nuclear@3 16
nuclear@3 17 #ifndef OVR_Hash_h
nuclear@3 18 #define OVR_Hash_h
nuclear@3 19
nuclear@3 20 #include "OVR_ContainerAllocator.h"
nuclear@3 21 #include "OVR_Alg.h"
nuclear@3 22
nuclear@3 23 // 'new' operator is redefined/used in this file.
nuclear@3 24 #undef new
nuclear@3 25
nuclear@3 26 namespace OVR {
nuclear@3 27
nuclear@3 28 //-----------------------------------------------------------------------------------
nuclear@3 29 // ***** Hash Table Implementation
nuclear@3 30
nuclear@3 31 // HastSet and Hash.
nuclear@3 32 //
nuclear@3 33 // Hash table, linear probing, internal chaining. One interesting/nice thing
nuclear@3 34 // about this implementation is that the table itself is a flat chunk of memory
nuclear@3 35 // containing no pointers, only relative indices. If the key and value types
nuclear@3 36 // of the Hash contain no pointers, then the Hash can be serialized using raw IO.
nuclear@3 37 //
nuclear@3 38 // Never shrinks, unless you explicitly Clear() it. Expands on
nuclear@3 39 // demand, though. For best results, if you know roughly how big your
nuclear@3 40 // table will be, default it to that size when you create it.
nuclear@3 41 //
nuclear@3 42 // Key usability feature:
nuclear@3 43 //
nuclear@3 44 // 1. Allows node hash values to either be cached or not.
nuclear@3 45 //
nuclear@3 46 // 2. Allows for alternative keys with methods such as GetAlt(). Handy
nuclear@3 47 // if you need to search nodes by their components; no need to create
nuclear@3 48 // temporary nodes.
nuclear@3 49 //
nuclear@3 50
nuclear@3 51
nuclear@3 52 // *** Hash functors:
nuclear@3 53 //
nuclear@3 54 // IdentityHash - use when the key is already a good hash
nuclear@3 55 // HFixedSizeHash - general hash based on object's in-memory representation.
nuclear@3 56
nuclear@3 57
nuclear@3 58 // Hash is just the input value; can use this for integer-indexed hash tables.
nuclear@3 59 template<class C>
nuclear@3 60 class IdentityHash
nuclear@3 61 {
nuclear@3 62 public:
nuclear@3 63 UPInt operator()(const C& data) const
nuclear@3 64 { return (UPInt) data; }
nuclear@3 65 };
nuclear@3 66
nuclear@3 67 // Computes a hash of an object's representation.
nuclear@3 68 template<class C>
nuclear@3 69 class FixedSizeHash
nuclear@3 70 {
nuclear@3 71 public:
nuclear@3 72 // Alternative: "sdbm" hash function, suggested at same web page
nuclear@3 73 // above, http::/www.cs.yorku.ca/~oz/hash.html
nuclear@3 74 // This is somewhat slower then Bernstein, but it works way better than the above
nuclear@3 75 // hash function for hashing large numbers of 32-bit ints.
nuclear@3 76 static OVR_FORCE_INLINE UPInt SDBM_Hash(const void* data_in, UPInt size, UPInt seed = 5381)
nuclear@3 77 {
nuclear@3 78 const UByte* data = (const UByte*) data_in;
nuclear@3 79 UPInt h = seed;
nuclear@3 80 while (size > 0)
nuclear@3 81 {
nuclear@3 82 size--;
nuclear@3 83 h = (h << 16) + (h << 6) - h + (UPInt)data[size];
nuclear@3 84 }
nuclear@3 85 return h;
nuclear@3 86 }
nuclear@3 87
nuclear@3 88 UPInt operator()(const C& data) const
nuclear@3 89 {
nuclear@3 90 unsigned char* p = (unsigned char*) &data;
nuclear@3 91 int size = sizeof(C);
nuclear@3 92
nuclear@3 93 return SDBM_Hash(p, size);
nuclear@3 94 }
nuclear@3 95 };
nuclear@3 96
nuclear@3 97
nuclear@3 98
nuclear@3 99 // *** HashsetEntry Entry types.
nuclear@3 100
nuclear@3 101 // Compact hash table Entry type that re-computes hash keys during hash traversal.
nuclear@3 102 // Good to use if the hash function is cheap or the hash value is already cached in C.
nuclear@3 103 template<class C, class HashF>
nuclear@3 104 class HashsetEntry
nuclear@3 105 {
nuclear@3 106 public:
nuclear@3 107 // Internal chaining for collisions.
nuclear@3 108 SPInt NextInChain;
nuclear@3 109 C Value;
nuclear@3 110
nuclear@3 111 HashsetEntry()
nuclear@3 112 : NextInChain(-2) { }
nuclear@3 113 HashsetEntry(const HashsetEntry& e)
nuclear@3 114 : NextInChain(e.NextInChain), Value(e.Value) { }
nuclear@3 115 HashsetEntry(const C& key, SPInt next)
nuclear@3 116 : NextInChain(next), Value(key) { }
nuclear@3 117
nuclear@3 118 bool IsEmpty() const { return NextInChain == -2; }
nuclear@3 119 bool IsEndOfChain() const { return NextInChain == -1; }
nuclear@3 120
nuclear@3 121 // Cached hash value access - can be optimized bu storing hash locally.
nuclear@3 122 // Mask value only needs to be used if SetCachedHash is not implemented.
nuclear@3 123 UPInt GetCachedHash(UPInt maskValue) const { return HashF()(Value) & maskValue; }
nuclear@3 124 void SetCachedHash(UPInt) {}
nuclear@3 125
nuclear@3 126 void Clear()
nuclear@3 127 {
nuclear@3 128 Value.~C(); // placement delete
nuclear@3 129 NextInChain = -2;
nuclear@3 130 }
nuclear@3 131 // Free is only used from dtor of hash; Clear is used during regular operations:
nuclear@3 132 // assignment, hash reallocations, value reassignments, so on.
nuclear@3 133 void Free() { Clear(); }
nuclear@3 134 };
nuclear@3 135
nuclear@3 136 // Hash table Entry type that caches the Entry hash value for nodes, so that it
nuclear@3 137 // does not need to be re-computed during access.
nuclear@3 138 template<class C, class HashF>
nuclear@3 139 class HashsetCachedEntry
nuclear@3 140 {
nuclear@3 141 public:
nuclear@3 142 // Internal chaining for collisions.
nuclear@3 143 SPInt NextInChain;
nuclear@3 144 UPInt HashValue;
nuclear@3 145 C Value;
nuclear@3 146
nuclear@3 147 HashsetCachedEntry()
nuclear@3 148 : NextInChain(-2) { }
nuclear@3 149 HashsetCachedEntry(const HashsetCachedEntry& e)
nuclear@3 150 : NextInChain(e.NextInChain), HashValue(e.HashValue), Value(e.Value) { }
nuclear@3 151 HashsetCachedEntry(const C& key, SPInt next)
nuclear@3 152 : NextInChain(next), Value(key) { }
nuclear@3 153
nuclear@3 154 bool IsEmpty() const { return NextInChain == -2; }
nuclear@3 155 bool IsEndOfChain() const { return NextInChain == -1; }
nuclear@3 156
nuclear@3 157 // Cached hash value access - can be optimized bu storing hash locally.
nuclear@3 158 // Mask value only needs to be used if SetCachedHash is not implemented.
nuclear@3 159 UPInt GetCachedHash(UPInt maskValue) const { OVR_UNUSED(maskValue); return HashValue; }
nuclear@3 160 void SetCachedHash(UPInt hashValue) { HashValue = hashValue; }
nuclear@3 161
nuclear@3 162 void Clear()
nuclear@3 163 {
nuclear@3 164 Value.~C();
nuclear@3 165 NextInChain = -2;
nuclear@3 166 }
nuclear@3 167 // Free is only used from dtor of hash; Clear is used during regular operations:
nuclear@3 168 // assignment, hash reallocations, value reassignments, so on.
nuclear@3 169 void Free() { Clear(); }
nuclear@3 170 };
nuclear@3 171
nuclear@3 172
nuclear@3 173 //-----------------------------------------------------------------------------------
nuclear@3 174 // *** HashSet implementation - relies on either cached or regular entries.
nuclear@3 175 //
nuclear@3 176 // Use: Entry = HashsetCachedEntry<C, HashF> if hashes are expensive to
nuclear@3 177 // compute and thus need caching in entries.
nuclear@3 178 // Entry = HashsetEntry<C, HashF> if hashes are already externally cached.
nuclear@3 179 //
nuclear@3 180 template<class C, class HashF = FixedSizeHash<C>,
nuclear@3 181 class AltHashF = HashF,
nuclear@3 182 class Allocator = ContainerAllocator<C>,
nuclear@3 183 class Entry = HashsetCachedEntry<C, HashF> >
nuclear@3 184 class HashSetBase
nuclear@3 185 {
nuclear@3 186 enum { HashMinSize = 8 };
nuclear@3 187
nuclear@3 188 public:
nuclear@3 189 OVR_MEMORY_REDEFINE_NEW(HashSetBase)
nuclear@3 190
nuclear@3 191 typedef HashSetBase<C, HashF, AltHashF, Allocator, Entry> SelfType;
nuclear@3 192
nuclear@3 193 HashSetBase() : pTable(NULL) { }
nuclear@3 194 HashSetBase(int sizeHint) : pTable(NULL) { SetCapacity(this, sizeHint); }
nuclear@3 195 HashSetBase(const SelfType& src) : pTable(NULL) { Assign(this, src); }
nuclear@3 196
nuclear@3 197 ~HashSetBase()
nuclear@3 198 {
nuclear@3 199 if (pTable)
nuclear@3 200 {
nuclear@3 201 // Delete the entries.
nuclear@3 202 for (UPInt i = 0, n = pTable->SizeMask; i <= n; i++)
nuclear@3 203 {
nuclear@3 204 Entry* e = &E(i);
nuclear@3 205 if (!e->IsEmpty())
nuclear@3 206 e->Free();
nuclear@3 207 }
nuclear@3 208
nuclear@3 209 Allocator::Free(pTable);
nuclear@3 210 pTable = NULL;
nuclear@3 211 }
nuclear@3 212 }
nuclear@3 213
nuclear@3 214
nuclear@3 215 void Assign(const SelfType& src)
nuclear@3 216 {
nuclear@3 217 Clear();
nuclear@3 218 if (src.IsEmpty() == false)
nuclear@3 219 {
nuclear@3 220 SetCapacity(src.GetSize());
nuclear@3 221
nuclear@3 222 for (ConstIterator it = src.Begin(); it != src.End(); ++it)
nuclear@3 223 {
nuclear@3 224 Add(*it);
nuclear@3 225 }
nuclear@3 226 }
nuclear@3 227 }
nuclear@3 228
nuclear@3 229
nuclear@3 230 // Remove all entries from the HashSet table.
nuclear@3 231 void Clear()
nuclear@3 232 {
nuclear@3 233 if (pTable)
nuclear@3 234 {
nuclear@3 235 // Delete the entries.
nuclear@3 236 for (UPInt i = 0, n = pTable->SizeMask; i <= n; i++)
nuclear@3 237 {
nuclear@3 238 Entry* e = &E(i);
nuclear@3 239 if (!e->IsEmpty())
nuclear@3 240 e->Clear();
nuclear@3 241 }
nuclear@3 242
nuclear@3 243 Allocator::Free(pTable);
nuclear@3 244 pTable = NULL;
nuclear@3 245 }
nuclear@3 246 }
nuclear@3 247
nuclear@3 248 // Returns true if the HashSet is empty.
nuclear@3 249 bool IsEmpty() const
nuclear@3 250 {
nuclear@3 251 return pTable == NULL || pTable->EntryCount == 0;
nuclear@3 252 }
nuclear@3 253
nuclear@3 254
nuclear@3 255 // Set a new or existing value under the key, to the value.
nuclear@3 256 // Pass a different class of 'key' so that assignment reference object
nuclear@3 257 // can be passed instead of the actual object.
nuclear@3 258 template<class CRef>
nuclear@3 259 void Set(const CRef& key)
nuclear@3 260 {
nuclear@3 261 UPInt hashValue = HashF()(key);
nuclear@3 262 SPInt index = (SPInt)-1;
nuclear@3 263
nuclear@3 264 if (pTable != NULL)
nuclear@3 265 index = findIndexCore(key, hashValue & pTable->SizeMask);
nuclear@3 266
nuclear@3 267 if (index >= 0)
nuclear@3 268 {
nuclear@3 269 E(index).Value = key;
nuclear@3 270 }
nuclear@3 271 else
nuclear@3 272 {
nuclear@3 273 // Entry under key doesn't exist.
nuclear@3 274 add(key, hashValue);
nuclear@3 275 }
nuclear@3 276 }
nuclear@3 277
nuclear@3 278 template<class CRef>
nuclear@3 279 inline void Add(const CRef& key)
nuclear@3 280 {
nuclear@3 281 UPInt hashValue = HashF()(key);
nuclear@3 282 add(key, hashValue);
nuclear@3 283 }
nuclear@3 284
nuclear@3 285 // Remove by alternative key.
nuclear@3 286 template<class K>
nuclear@3 287 void RemoveAlt(const K& key)
nuclear@3 288 {
nuclear@3 289 if (pTable == NULL)
nuclear@3 290 return;
nuclear@3 291
nuclear@3 292 UPInt hashValue = AltHashF()(key);
nuclear@3 293 SPInt index = hashValue & pTable->SizeMask;
nuclear@3 294
nuclear@3 295 Entry* e = &E(index);
nuclear@3 296
nuclear@3 297 // If empty node or occupied by collider, we have nothing to remove.
nuclear@3 298 if (e->IsEmpty() || (e->GetCachedHash(pTable->SizeMask) != (UPInt)index))
nuclear@3 299 return;
nuclear@3 300
nuclear@3 301 // Save index
nuclear@3 302 SPInt naturalIndex = index;
nuclear@3 303 SPInt prevIndex = -1;
nuclear@3 304
nuclear@3 305 while ((e->GetCachedHash(pTable->SizeMask) != (UPInt)naturalIndex) || !(e->Value == key))
nuclear@3 306 {
nuclear@3 307 // Keep looking through the chain.
nuclear@3 308 prevIndex = index;
nuclear@3 309 index = e->NextInChain;
nuclear@3 310 if (index == -1)
nuclear@3 311 return; // End of chain, item not found
nuclear@3 312 e = &E(index);
nuclear@3 313 }
nuclear@3 314
nuclear@3 315 // Found it - our item is at index
nuclear@3 316 if (naturalIndex == index)
nuclear@3 317 {
nuclear@3 318 // If we have a follower, move it to us
nuclear@3 319 if (!e->IsEndOfChain())
nuclear@3 320 {
nuclear@3 321 Entry* enext = &E(e->NextInChain);
nuclear@3 322 e->Clear();
nuclear@3 323 new (e) Entry(*enext);
nuclear@3 324 // Point us to the follower's cell that will be cleared
nuclear@3 325 e = enext;
nuclear@3 326 }
nuclear@3 327 }
nuclear@3 328 else
nuclear@3 329 {
nuclear@3 330 // We are not at natural index, so deal with the prev items next index
nuclear@3 331 E(prevIndex).NextInChain = e->NextInChain;
nuclear@3 332 }
nuclear@3 333
nuclear@3 334 // Clear us, of the follower cell that was moved.
nuclear@3 335 e->Clear();
nuclear@3 336 pTable->EntryCount --;
nuclear@3 337 // Should we check the size to condense hash? ...
nuclear@3 338 }
nuclear@3 339
nuclear@3 340 // Remove by main key.
nuclear@3 341 template<class CRef>
nuclear@3 342 void Remove(const CRef& key)
nuclear@3 343 {
nuclear@3 344 RemoveAlt(key);
nuclear@3 345 }
nuclear@3 346
nuclear@3 347 // Retrieve the pointer to a value under the given key.
nuclear@3 348 // - If there's no value under the key, then return NULL.
nuclear@3 349 // - If there is a value, return the pointer.
nuclear@3 350 template<class K>
nuclear@3 351 C* Get(const K& key)
nuclear@3 352 {
nuclear@3 353 SPInt index = findIndex(key);
nuclear@3 354 if (index >= 0)
nuclear@3 355 return &E(index).Value;
nuclear@3 356 return 0;
nuclear@3 357 }
nuclear@3 358
nuclear@3 359 template<class K>
nuclear@3 360 const C* Get(const K& key) const
nuclear@3 361 {
nuclear@3 362 SPInt index = findIndex(key);
nuclear@3 363 if (index >= 0)
nuclear@3 364 return &E(index).Value;
nuclear@3 365 return 0;
nuclear@3 366 }
nuclear@3 367
nuclear@3 368 // Alternative key versions of Get. Used by Hash.
nuclear@3 369 template<class K>
nuclear@3 370 const C* GetAlt(const K& key) const
nuclear@3 371 {
nuclear@3 372 SPInt index = findIndexAlt(key);
nuclear@3 373 if (index >= 0)
nuclear@3 374 return &E(index).Value;
nuclear@3 375 return 0;
nuclear@3 376 }
nuclear@3 377
nuclear@3 378 template<class K>
nuclear@3 379 C* GetAlt(const K& key)
nuclear@3 380 {
nuclear@3 381 SPInt index = findIndexAlt(key);
nuclear@3 382 if (index >= 0)
nuclear@3 383 return &E(index).Value;
nuclear@3 384 return 0;
nuclear@3 385 }
nuclear@3 386
nuclear@3 387 template<class K>
nuclear@3 388 bool GetAlt(const K& key, C* pval) const
nuclear@3 389 {
nuclear@3 390 SPInt index = findIndexAlt(key);
nuclear@3 391 if (index >= 0)
nuclear@3 392 {
nuclear@3 393 if (pval)
nuclear@3 394 *pval = E(index).Value;
nuclear@3 395 return true;
nuclear@3 396 }
nuclear@3 397 return false;
nuclear@3 398 }
nuclear@3 399
nuclear@3 400
nuclear@3 401 UPInt GetSize() const
nuclear@3 402 {
nuclear@3 403 return pTable == NULL ? 0 : (UPInt)pTable->EntryCount;
nuclear@3 404 }
nuclear@3 405
nuclear@3 406
nuclear@3 407 // Resize the HashSet table to fit one more Entry. Often this
nuclear@3 408 // doesn't involve any action.
nuclear@3 409 void CheckExpand()
nuclear@3 410 {
nuclear@3 411 if (pTable == NULL)
nuclear@3 412 {
nuclear@3 413 // Initial creation of table. Make a minimum-sized table.
nuclear@3 414 setRawCapacity(HashMinSize);
nuclear@3 415 }
nuclear@3 416 else if (pTable->EntryCount * 5 > (pTable->SizeMask + 1) * 4)
nuclear@3 417 {
nuclear@3 418 // pTable is more than 5/4 ths full. Expand.
nuclear@3 419 setRawCapacity((pTable->SizeMask + 1) * 2);
nuclear@3 420 }
nuclear@3 421 }
nuclear@3 422
nuclear@3 423 // Hint the bucket count to >= n.
nuclear@3 424 void Resize(UPInt n)
nuclear@3 425 {
nuclear@3 426 // Not really sure what this means in relation to
nuclear@3 427 // STLport's hash_map... they say they "increase the
nuclear@3 428 // bucket count to at least n" -- but does that mean
nuclear@3 429 // their real capacity after Resize(n) is more like
nuclear@3 430 // n*2 (since they do linked-list chaining within
nuclear@3 431 // buckets?).
nuclear@3 432 SetCapacity(n);
nuclear@3 433 }
nuclear@3 434
nuclear@3 435 // Size the HashSet so that it can comfortably contain the given
nuclear@3 436 // number of elements. If the HashSet already contains more
nuclear@3 437 // elements than newSize, then this may be a no-op.
nuclear@3 438 void SetCapacity(UPInt newSize)
nuclear@3 439 {
nuclear@3 440 UPInt newRawSize = (newSize * 5) / 4;
nuclear@3 441 if (newRawSize <= GetSize())
nuclear@3 442 return;
nuclear@3 443 setRawCapacity(newRawSize);
nuclear@3 444 }
nuclear@3 445
nuclear@3 446 // Disable inappropriate 'operator ->' warning on MSVC6.
nuclear@3 447 #ifdef OVR_CC_MSVC
nuclear@3 448 #if (OVR_CC_MSVC < 1300)
nuclear@3 449 # pragma warning(disable : 4284)
nuclear@3 450 #endif
nuclear@3 451 #endif
nuclear@3 452
nuclear@3 453 // Iterator API, like STL.
nuclear@3 454 struct ConstIterator
nuclear@3 455 {
nuclear@3 456 const C& operator * () const
nuclear@3 457 {
nuclear@3 458 OVR_ASSERT(Index >= 0 && Index <= (SPInt)pHash->pTable->SizeMask);
nuclear@3 459 return pHash->E(Index).Value;
nuclear@3 460 }
nuclear@3 461
nuclear@3 462 const C* operator -> () const
nuclear@3 463 {
nuclear@3 464 OVR_ASSERT(Index >= 0 && Index <= (SPInt)pHash->pTable->SizeMask);
nuclear@3 465 return &pHash->E(Index).Value;
nuclear@3 466 }
nuclear@3 467
nuclear@3 468 void operator ++ ()
nuclear@3 469 {
nuclear@3 470 // Find next non-empty Entry.
nuclear@3 471 if (Index <= (SPInt)pHash->pTable->SizeMask)
nuclear@3 472 {
nuclear@3 473 Index++;
nuclear@3 474 while ((UPInt)Index <= pHash->pTable->SizeMask &&
nuclear@3 475 pHash->E(Index).IsEmpty())
nuclear@3 476 {
nuclear@3 477 Index++;
nuclear@3 478 }
nuclear@3 479 }
nuclear@3 480 }
nuclear@3 481
nuclear@3 482 bool operator == (const ConstIterator& it) const
nuclear@3 483 {
nuclear@3 484 if (IsEnd() && it.IsEnd())
nuclear@3 485 {
nuclear@3 486 return true;
nuclear@3 487 }
nuclear@3 488 else
nuclear@3 489 {
nuclear@3 490 return (pHash == it.pHash) && (Index == it.Index);
nuclear@3 491 }
nuclear@3 492 }
nuclear@3 493
nuclear@3 494 bool operator != (const ConstIterator& it) const
nuclear@3 495 {
nuclear@3 496 return ! (*this == it);
nuclear@3 497 }
nuclear@3 498
nuclear@3 499
nuclear@3 500 bool IsEnd() const
nuclear@3 501 {
nuclear@3 502 return (pHash == NULL) ||
nuclear@3 503 (pHash->pTable == NULL) ||
nuclear@3 504 (Index > (SPInt)pHash->pTable->SizeMask);
nuclear@3 505 }
nuclear@3 506
nuclear@3 507 ConstIterator()
nuclear@3 508 : pHash(NULL), Index(0)
nuclear@3 509 { }
nuclear@3 510
nuclear@3 511 public:
nuclear@3 512 // Constructor was intentionally made public to allow create
nuclear@3 513 // iterator with arbitrary index.
nuclear@3 514 ConstIterator(const SelfType* h, SPInt index)
nuclear@3 515 : pHash(h), Index(index)
nuclear@3 516 { }
nuclear@3 517
nuclear@3 518 const SelfType* GetContainer() const
nuclear@3 519 {
nuclear@3 520 return pHash;
nuclear@3 521 }
nuclear@3 522 SPInt GetIndex() const
nuclear@3 523 {
nuclear@3 524 return Index;
nuclear@3 525 }
nuclear@3 526
nuclear@3 527 protected:
nuclear@3 528 friend class HashSetBase<C, HashF, AltHashF, Allocator, Entry>;
nuclear@3 529
nuclear@3 530 const SelfType* pHash;
nuclear@3 531 SPInt Index;
nuclear@3 532 };
nuclear@3 533
nuclear@3 534 friend struct ConstIterator;
nuclear@3 535
nuclear@3 536
nuclear@3 537 // Non-const Iterator; Get most of it from ConstIterator.
nuclear@3 538 struct Iterator : public ConstIterator
nuclear@3 539 {
nuclear@3 540 // Allow non-const access to entries.
nuclear@3 541 C& operator*() const
nuclear@3 542 {
nuclear@3 543 OVR_ASSERT(ConstIterator::Index >= 0 && ConstIterator::Index <= (SPInt)ConstIterator::pHash->pTable->SizeMask);
nuclear@3 544 return const_cast<SelfType*>(ConstIterator::pHash)->E(ConstIterator::Index).Value;
nuclear@3 545 }
nuclear@3 546
nuclear@3 547 C* operator->() const
nuclear@3 548 {
nuclear@3 549 return &(operator*());
nuclear@3 550 }
nuclear@3 551
nuclear@3 552 Iterator()
nuclear@3 553 : ConstIterator(NULL, 0)
nuclear@3 554 { }
nuclear@3 555
nuclear@3 556 // Removes current element from Hash
nuclear@3 557 void Remove()
nuclear@3 558 {
nuclear@3 559 RemoveAlt(operator*());
nuclear@3 560 }
nuclear@3 561
nuclear@3 562 template <class K>
nuclear@3 563 void RemoveAlt(const K& key)
nuclear@3 564 {
nuclear@3 565 SelfType* phash = const_cast<SelfType*>(ConstIterator::pHash);
nuclear@3 566 //Entry* ee = &phash->E(ConstIterator::Index);
nuclear@3 567 //const C& key = ee->Value;
nuclear@3 568
nuclear@3 569 UPInt hashValue = AltHashF()(key);
nuclear@3 570 SPInt index = hashValue & phash->pTable->SizeMask;
nuclear@3 571
nuclear@3 572 Entry* e = &phash->E(index);
nuclear@3 573
nuclear@3 574 // If empty node or occupied by collider, we have nothing to remove.
nuclear@3 575 if (e->IsEmpty() || (e->GetCachedHash(phash->pTable->SizeMask) != (UPInt)index))
nuclear@3 576 return;
nuclear@3 577
nuclear@3 578 // Save index
nuclear@3 579 SPInt naturalIndex = index;
nuclear@3 580 SPInt prevIndex = -1;
nuclear@3 581
nuclear@3 582 while ((e->GetCachedHash(phash->pTable->SizeMask) != (UPInt)naturalIndex) || !(e->Value == key))
nuclear@3 583 {
nuclear@3 584 // Keep looking through the chain.
nuclear@3 585 prevIndex = index;
nuclear@3 586 index = e->NextInChain;
nuclear@3 587 if (index == -1)
nuclear@3 588 return; // End of chain, item not found
nuclear@3 589 e = &phash->E(index);
nuclear@3 590 }
nuclear@3 591
nuclear@3 592 if (index == (SPInt)ConstIterator::Index)
nuclear@3 593 {
nuclear@3 594 // Found it - our item is at index
nuclear@3 595 if (naturalIndex == index)
nuclear@3 596 {
nuclear@3 597 // If we have a follower, move it to us
nuclear@3 598 if (!e->IsEndOfChain())
nuclear@3 599 {
nuclear@3 600 Entry* enext = &phash->E(e->NextInChain);
nuclear@3 601 e->Clear();
nuclear@3 602 new (e) Entry(*enext);
nuclear@3 603 // Point us to the follower's cell that will be cleared
nuclear@3 604 e = enext;
nuclear@3 605 --ConstIterator::Index;
nuclear@3 606 }
nuclear@3 607 }
nuclear@3 608 else
nuclear@3 609 {
nuclear@3 610 // We are not at natural index, so deal with the prev items next index
nuclear@3 611 phash->E(prevIndex).NextInChain = e->NextInChain;
nuclear@3 612 }
nuclear@3 613
nuclear@3 614 // Clear us, of the follower cell that was moved.
nuclear@3 615 e->Clear();
nuclear@3 616 phash->pTable->EntryCount --;
nuclear@3 617 }
nuclear@3 618 else
nuclear@3 619 OVR_ASSERT(0); //?
nuclear@3 620 }
nuclear@3 621
nuclear@3 622 private:
nuclear@3 623 friend class HashSetBase<C, HashF, AltHashF, Allocator, Entry>;
nuclear@3 624
nuclear@3 625 Iterator(SelfType* h, SPInt i0)
nuclear@3 626 : ConstIterator(h, i0)
nuclear@3 627 { }
nuclear@3 628 };
nuclear@3 629
nuclear@3 630 friend struct Iterator;
nuclear@3 631
nuclear@3 632 Iterator Begin()
nuclear@3 633 {
nuclear@3 634 if (pTable == 0)
nuclear@3 635 return Iterator(NULL, 0);
nuclear@3 636
nuclear@3 637 // Scan till we hit the First valid Entry.
nuclear@3 638 UPInt i0 = 0;
nuclear@3 639 while (i0 <= pTable->SizeMask && E(i0).IsEmpty())
nuclear@3 640 {
nuclear@3 641 i0++;
nuclear@3 642 }
nuclear@3 643 return Iterator(this, i0);
nuclear@3 644 }
nuclear@3 645 Iterator End() { return Iterator(NULL, 0); }
nuclear@3 646
nuclear@3 647 ConstIterator Begin() const { return const_cast<SelfType*>(this)->Begin(); }
nuclear@3 648 ConstIterator End() const { return const_cast<SelfType*>(this)->End(); }
nuclear@3 649
nuclear@3 650 template<class K>
nuclear@3 651 Iterator Find(const K& key)
nuclear@3 652 {
nuclear@3 653 SPInt index = findIndex(key);
nuclear@3 654 if (index >= 0)
nuclear@3 655 return Iterator(this, index);
nuclear@3 656 return Iterator(NULL, 0);
nuclear@3 657 }
nuclear@3 658
nuclear@3 659 template<class K>
nuclear@3 660 Iterator FindAlt(const K& key)
nuclear@3 661 {
nuclear@3 662 SPInt index = findIndexAlt(key);
nuclear@3 663 if (index >= 0)
nuclear@3 664 return Iterator(this, index);
nuclear@3 665 return Iterator(NULL, 0);
nuclear@3 666 }
nuclear@3 667
nuclear@3 668 template<class K>
nuclear@3 669 ConstIterator Find(const K& key) const { return const_cast<SelfType*>(this)->Find(key); }
nuclear@3 670
nuclear@3 671 template<class K>
nuclear@3 672 ConstIterator FindAlt(const K& key) const { return const_cast<SelfType*>(this)->FindAlt(key); }
nuclear@3 673
nuclear@3 674 private:
nuclear@3 675 // Find the index of the matching Entry. If no match, then return -1.
nuclear@3 676 template<class K>
nuclear@3 677 SPInt findIndex(const K& key) const
nuclear@3 678 {
nuclear@3 679 if (pTable == NULL)
nuclear@3 680 return -1;
nuclear@3 681 UPInt hashValue = HashF()(key) & pTable->SizeMask;
nuclear@3 682 return findIndexCore(key, hashValue);
nuclear@3 683 }
nuclear@3 684
nuclear@3 685 template<class K>
nuclear@3 686 SPInt findIndexAlt(const K& key) const
nuclear@3 687 {
nuclear@3 688 if (pTable == NULL)
nuclear@3 689 return -1;
nuclear@3 690 UPInt hashValue = AltHashF()(key) & pTable->SizeMask;
nuclear@3 691 return findIndexCore(key, hashValue);
nuclear@3 692 }
nuclear@3 693
nuclear@3 694 // Find the index of the matching Entry. If no match, then return -1.
nuclear@3 695 template<class K>
nuclear@3 696 SPInt findIndexCore(const K& key, UPInt hashValue) const
nuclear@3 697 {
nuclear@3 698 // Table must exist.
nuclear@3 699 OVR_ASSERT(pTable != 0);
nuclear@3 700 // Hash key must be 'and-ed' by the caller.
nuclear@3 701 OVR_ASSERT((hashValue & ~pTable->SizeMask) == 0);
nuclear@3 702
nuclear@3 703 UPInt index = hashValue;
nuclear@3 704 const Entry* e = &E(index);
nuclear@3 705
nuclear@3 706 // If empty or occupied by a collider, not found.
nuclear@3 707 if (e->IsEmpty() || (e->GetCachedHash(pTable->SizeMask) != index))
nuclear@3 708 return -1;
nuclear@3 709
nuclear@3 710 while(1)
nuclear@3 711 {
nuclear@3 712 OVR_ASSERT(e->GetCachedHash(pTable->SizeMask) == hashValue);
nuclear@3 713
nuclear@3 714 if (e->GetCachedHash(pTable->SizeMask) == hashValue && e->Value == key)
nuclear@3 715 {
nuclear@3 716 // Found it.
nuclear@3 717 return index;
nuclear@3 718 }
nuclear@3 719 // Values can not be equal at this point.
nuclear@3 720 // That would mean that the hash key for the same value differs.
nuclear@3 721 OVR_ASSERT(!(e->Value == key));
nuclear@3 722
nuclear@3 723 // Keep looking through the chain.
nuclear@3 724 index = e->NextInChain;
nuclear@3 725 if (index == (UPInt)-1)
nuclear@3 726 break; // end of chain
nuclear@3 727
nuclear@3 728 e = &E(index);
nuclear@3 729 OVR_ASSERT(!e->IsEmpty());
nuclear@3 730 }
nuclear@3 731 return -1;
nuclear@3 732 }
nuclear@3 733
nuclear@3 734
nuclear@3 735 // Add a new value to the HashSet table, under the specified key.
nuclear@3 736 template<class CRef>
nuclear@3 737 void add(const CRef& key, UPInt hashValue)
nuclear@3 738 {
nuclear@3 739 CheckExpand();
nuclear@3 740 hashValue &= pTable->SizeMask;
nuclear@3 741
nuclear@3 742 pTable->EntryCount++;
nuclear@3 743
nuclear@3 744 SPInt index = hashValue;
nuclear@3 745 Entry* naturalEntry = &(E(index));
nuclear@3 746
nuclear@3 747 if (naturalEntry->IsEmpty())
nuclear@3 748 {
nuclear@3 749 // Put the new Entry in.
nuclear@3 750 new (naturalEntry) Entry(key, -1);
nuclear@3 751 }
nuclear@3 752 else
nuclear@3 753 {
nuclear@3 754 // Find a blank spot.
nuclear@3 755 SPInt blankIndex = index;
nuclear@3 756 do {
nuclear@3 757 blankIndex = (blankIndex + 1) & pTable->SizeMask;
nuclear@3 758 } while(!E(blankIndex).IsEmpty());
nuclear@3 759
nuclear@3 760 Entry* blankEntry = &E(blankIndex);
nuclear@3 761
nuclear@3 762 if (naturalEntry->GetCachedHash(pTable->SizeMask) == (UPInt)index)
nuclear@3 763 {
nuclear@3 764 // Collision. Link into this chain.
nuclear@3 765
nuclear@3 766 // Move existing list head.
nuclear@3 767 new (blankEntry) Entry(*naturalEntry); // placement new, copy ctor
nuclear@3 768
nuclear@3 769 // Put the new info in the natural Entry.
nuclear@3 770 naturalEntry->Value = key;
nuclear@3 771 naturalEntry->NextInChain = blankIndex;
nuclear@3 772 }
nuclear@3 773 else
nuclear@3 774 {
nuclear@3 775 // Existing Entry does not naturally
nuclear@3 776 // belong in this slot. Existing
nuclear@3 777 // Entry must be moved.
nuclear@3 778
nuclear@3 779 // Find natural location of collided element (i.e. root of chain)
nuclear@3 780 SPInt collidedIndex = naturalEntry->GetCachedHash(pTable->SizeMask);
nuclear@3 781 OVR_ASSERT(collidedIndex >= 0 && collidedIndex <= (SPInt)pTable->SizeMask);
nuclear@3 782 for (;;)
nuclear@3 783 {
nuclear@3 784 Entry* e = &E(collidedIndex);
nuclear@3 785 if (e->NextInChain == index)
nuclear@3 786 {
nuclear@3 787 // Here's where we need to splice.
nuclear@3 788 new (blankEntry) Entry(*naturalEntry);
nuclear@3 789 e->NextInChain = blankIndex;
nuclear@3 790 break;
nuclear@3 791 }
nuclear@3 792 collidedIndex = e->NextInChain;
nuclear@3 793 OVR_ASSERT(collidedIndex >= 0 && collidedIndex <= (SPInt)pTable->SizeMask);
nuclear@3 794 }
nuclear@3 795
nuclear@3 796 // Put the new data in the natural Entry.
nuclear@3 797 naturalEntry->Value = key;
nuclear@3 798 naturalEntry->NextInChain = -1;
nuclear@3 799 }
nuclear@3 800 }
nuclear@3 801
nuclear@3 802 // Record hash value: has effect only if cached node is used.
nuclear@3 803 naturalEntry->SetCachedHash(hashValue);
nuclear@3 804 }
nuclear@3 805
nuclear@3 806 // Index access helpers.
nuclear@3 807 Entry& E(UPInt index)
nuclear@3 808 {
nuclear@3 809 // Must have pTable and access needs to be within bounds.
nuclear@3 810 OVR_ASSERT(index <= pTable->SizeMask);
nuclear@3 811 return *(((Entry*) (pTable + 1)) + index);
nuclear@3 812 }
nuclear@3 813 const Entry& E(UPInt index) const
nuclear@3 814 {
nuclear@3 815 OVR_ASSERT(index <= pTable->SizeMask);
nuclear@3 816 return *(((Entry*) (pTable + 1)) + index);
nuclear@3 817 }
nuclear@3 818
nuclear@3 819
nuclear@3 820 // Resize the HashSet table to the given size (Rehash the
nuclear@3 821 // contents of the current table). The arg is the number of
nuclear@3 822 // HashSet table entries, not the number of elements we should
nuclear@3 823 // actually contain (which will be less than this).
nuclear@3 824 void setRawCapacity(UPInt newSize)
nuclear@3 825 {
nuclear@3 826 if (newSize == 0)
nuclear@3 827 {
nuclear@3 828 // Special case.
nuclear@3 829 Clear();
nuclear@3 830 return;
nuclear@3 831 }
nuclear@3 832
nuclear@3 833 // Minimum size; don't incur rehashing cost when expanding
nuclear@3 834 // very small tables. Not that we perform this check before
nuclear@3 835 // 'log2f' call to avoid fp exception with newSize == 1.
nuclear@3 836 if (newSize < HashMinSize)
nuclear@3 837 newSize = HashMinSize;
nuclear@3 838 else
nuclear@3 839 {
nuclear@3 840 // Force newSize to be a power of two.
nuclear@3 841 int bits = Alg::UpperBit(newSize-1) + 1; // Chop( Log2f((float)(newSize-1)) + 1);
nuclear@3 842 OVR_ASSERT((UPInt(1) << bits) >= newSize);
nuclear@3 843 newSize = UPInt(1) << bits;
nuclear@3 844 }
nuclear@3 845
nuclear@3 846 SelfType newHash;
nuclear@3 847 newHash.pTable = (TableType*)
nuclear@3 848 Allocator::Alloc(
nuclear@3 849 sizeof(TableType) + sizeof(Entry) * newSize);
nuclear@3 850 // Need to do something on alloc failure!
nuclear@3 851 OVR_ASSERT(newHash.pTable);
nuclear@3 852
nuclear@3 853 newHash.pTable->EntryCount = 0;
nuclear@3 854 newHash.pTable->SizeMask = newSize - 1;
nuclear@3 855 UPInt i, n;
nuclear@3 856
nuclear@3 857 // Mark all entries as empty.
nuclear@3 858 for (i = 0; i < newSize; i++)
nuclear@3 859 newHash.E(i).NextInChain = -2;
nuclear@3 860
nuclear@3 861 // Copy stuff to newHash
nuclear@3 862 if (pTable)
nuclear@3 863 {
nuclear@3 864 for (i = 0, n = pTable->SizeMask; i <= n; i++)
nuclear@3 865 {
nuclear@3 866 Entry* e = &E(i);
nuclear@3 867 if (e->IsEmpty() == false)
nuclear@3 868 {
nuclear@3 869 // Insert old Entry into new HashSet.
nuclear@3 870 newHash.Add(e->Value);
nuclear@3 871 // placement delete of old element
nuclear@3 872 e->Clear();
nuclear@3 873 }
nuclear@3 874 }
nuclear@3 875
nuclear@3 876 // Delete our old data buffer.
nuclear@3 877 Allocator::Free(pTable);
nuclear@3 878 }
nuclear@3 879
nuclear@3 880 // Steal newHash's data.
nuclear@3 881 pTable = newHash.pTable;
nuclear@3 882 newHash.pTable = NULL;
nuclear@3 883 }
nuclear@3 884
nuclear@3 885 struct TableType
nuclear@3 886 {
nuclear@3 887 UPInt EntryCount;
nuclear@3 888 UPInt SizeMask;
nuclear@3 889 // Entry array follows this structure
nuclear@3 890 // in memory.
nuclear@3 891 };
nuclear@3 892 TableType* pTable;
nuclear@3 893 };
nuclear@3 894
nuclear@3 895
nuclear@3 896
nuclear@3 897 //-----------------------------------------------------------------------------------
nuclear@3 898 template<class C, class HashF = FixedSizeHash<C>,
nuclear@3 899 class AltHashF = HashF,
nuclear@3 900 class Allocator = ContainerAllocator<C>,
nuclear@3 901 class Entry = HashsetCachedEntry<C, HashF> >
nuclear@3 902 class HashSet : public HashSetBase<C, HashF, AltHashF, Allocator, Entry>
nuclear@3 903 {
nuclear@3 904 public:
nuclear@3 905 typedef HashSetBase<C, HashF, AltHashF, Allocator, Entry> BaseType;
nuclear@3 906 typedef HashSet<C, HashF, AltHashF, Allocator, Entry> SelfType;
nuclear@3 907
nuclear@3 908 HashSet() { }
nuclear@3 909 HashSet(int sizeHint) : BaseType(sizeHint) { }
nuclear@3 910 HashSet(const SelfType& src) : BaseType(src) { }
nuclear@3 911 ~HashSet() { }
nuclear@3 912
nuclear@3 913 void operator = (const SelfType& src) { BaseType::Assign(src); }
nuclear@3 914
nuclear@3 915 // Set a new or existing value under the key, to the value.
nuclear@3 916 // Pass a different class of 'key' so that assignment reference object
nuclear@3 917 // can be passed instead of the actual object.
nuclear@3 918 template<class CRef>
nuclear@3 919 void Set(const CRef& key)
nuclear@3 920 {
nuclear@3 921 BaseType::Set(key);
nuclear@3 922 }
nuclear@3 923
nuclear@3 924 template<class CRef>
nuclear@3 925 inline void Add(const CRef& key)
nuclear@3 926 {
nuclear@3 927 BaseType::Add(key);
nuclear@3 928 }
nuclear@3 929
nuclear@3 930 // Hint the bucket count to >= n.
nuclear@3 931 void Resize(UPInt n)
nuclear@3 932 {
nuclear@3 933 BaseType::SetCapacity(n);
nuclear@3 934 }
nuclear@3 935
nuclear@3 936 // Size the HashSet so that it can comfortably contain the given
nuclear@3 937 // number of elements. If the HashSet already contains more
nuclear@3 938 // elements than newSize, then this may be a no-op.
nuclear@3 939 void SetCapacity(UPInt newSize)
nuclear@3 940 {
nuclear@3 941 BaseType::SetCapacity(newSize);
nuclear@3 942 }
nuclear@3 943
nuclear@3 944 };
nuclear@3 945
nuclear@3 946 // HashSet with uncached hash code; declared for convenience.
nuclear@3 947 template<class C, class HashF = FixedSizeHash<C>,
nuclear@3 948 class AltHashF = HashF,
nuclear@3 949 class Allocator = ContainerAllocator<C> >
nuclear@3 950 class HashSetUncached : public HashSet<C, HashF, AltHashF, Allocator, HashsetEntry<C, HashF> >
nuclear@3 951 {
nuclear@3 952 public:
nuclear@3 953
nuclear@3 954 typedef HashSetUncached<C, HashF, AltHashF, Allocator> SelfType;
nuclear@3 955 typedef HashSet<C, HashF, AltHashF, Allocator, HashsetEntry<C, HashF> > BaseType;
nuclear@3 956
nuclear@3 957 // Delegated constructors.
nuclear@3 958 HashSetUncached() { }
nuclear@3 959 HashSetUncached(int sizeHint) : BaseType(sizeHint) { }
nuclear@3 960 HashSetUncached(const SelfType& src) : BaseType(src) { }
nuclear@3 961 ~HashSetUncached() { }
nuclear@3 962
nuclear@3 963 void operator = (const SelfType& src)
nuclear@3 964 {
nuclear@3 965 BaseType::operator = (src);
nuclear@3 966 }
nuclear@3 967 };
nuclear@3 968
nuclear@3 969
nuclear@3 970 //-----------------------------------------------------------------------------------
nuclear@3 971 // ***** Hash hash table implementation
nuclear@3 972
nuclear@3 973 // Node for Hash - necessary so that Hash can delegate its implementation
nuclear@3 974 // to HashSet.
nuclear@3 975 template<class C, class U, class HashF>
nuclear@3 976 struct HashNode
nuclear@3 977 {
nuclear@3 978 typedef HashNode<C, U, HashF> SelfType;
nuclear@3 979 typedef C FirstType;
nuclear@3 980 typedef U SecondType;
nuclear@3 981
nuclear@3 982 C First;
nuclear@3 983 U Second;
nuclear@3 984
nuclear@3 985 // NodeRef is used to allow passing of elements into HashSet
nuclear@3 986 // without using a temporary object.
nuclear@3 987 struct NodeRef
nuclear@3 988 {
nuclear@3 989 const C* pFirst;
nuclear@3 990 const U* pSecond;
nuclear@3 991
nuclear@3 992 NodeRef(const C& f, const U& s) : pFirst(&f), pSecond(&s) { }
nuclear@3 993 NodeRef(const NodeRef& src) : pFirst(src.pFirst), pSecond(src.pSecond) { }
nuclear@3 994
nuclear@3 995 // Enable computation of ghash_node_hashf.
nuclear@3 996 inline UPInt GetHash() const { return HashF()(*pFirst); }
nuclear@3 997 // Necessary conversion to allow HashNode::operator == to work.
nuclear@3 998 operator const C& () const { return *pFirst; }
nuclear@3 999 };
nuclear@3 1000
nuclear@3 1001 // Note: No default constructor is necessary.
nuclear@3 1002 HashNode(const HashNode& src) : First(src.First), Second(src.Second) { }
nuclear@3 1003 HashNode(const NodeRef& src) : First(*src.pFirst), Second(*src.pSecond) { }
nuclear@3 1004 void operator = (const NodeRef& src) { First = *src.pFirst; Second = *src.pSecond; }
nuclear@3 1005
nuclear@3 1006 template<class K>
nuclear@3 1007 bool operator == (const K& src) const { return (First == src); }
nuclear@3 1008
nuclear@3 1009 template<class K>
nuclear@3 1010 static UPInt CalcHash(const K& data) { return HashF()(data); }
nuclear@3 1011 inline UPInt GetHash() const { return HashF()(First); }
nuclear@3 1012
nuclear@3 1013 // Hash functors used with this node. A separate functor is used for alternative
nuclear@3 1014 // key lookup so that it does not need to access the '.First' element.
nuclear@3 1015 struct NodeHashF
nuclear@3 1016 {
nuclear@3 1017 template<class K>
nuclear@3 1018 UPInt operator()(const K& data) const { return data.GetHash(); }
nuclear@3 1019 };
nuclear@3 1020 struct NodeAltHashF
nuclear@3 1021 {
nuclear@3 1022 template<class K>
nuclear@3 1023 UPInt operator()(const K& data) const { return HashNode<C,U,HashF>::CalcHash(data); }
nuclear@3 1024 };
nuclear@3 1025 };
nuclear@3 1026
nuclear@3 1027
nuclear@3 1028
nuclear@3 1029 // **** Extra hashset_entry types to allow NodeRef construction.
nuclear@3 1030
nuclear@3 1031 // The big difference between the below types and the ones used in hash_set is that
nuclear@3 1032 // these allow initializing the node with 'typename C::NodeRef& keyRef', which
nuclear@3 1033 // is critical to avoid temporary node allocation on stack when using placement new.
nuclear@3 1034
nuclear@3 1035 // Compact hash table Entry type that re-computes hash keys during hash traversal.
nuclear@3 1036 // Good to use if the hash function is cheap or the hash value is already cached in C.
nuclear@3 1037 template<class C, class HashF>
nuclear@3 1038 class HashsetNodeEntry
nuclear@3 1039 {
nuclear@3 1040 public:
nuclear@3 1041 // Internal chaining for collisions.
nuclear@3 1042 SPInt NextInChain;
nuclear@3 1043 C Value;
nuclear@3 1044
nuclear@3 1045 HashsetNodeEntry()
nuclear@3 1046 : NextInChain(-2) { }
nuclear@3 1047 HashsetNodeEntry(const HashsetNodeEntry& e)
nuclear@3 1048 : NextInChain(e.NextInChain), Value(e.Value) { }
nuclear@3 1049 HashsetNodeEntry(const C& key, SPInt next)
nuclear@3 1050 : NextInChain(next), Value(key) { }
nuclear@3 1051 HashsetNodeEntry(const typename C::NodeRef& keyRef, SPInt next)
nuclear@3 1052 : NextInChain(next), Value(keyRef) { }
nuclear@3 1053
nuclear@3 1054 bool IsEmpty() const { return NextInChain == -2; }
nuclear@3 1055 bool IsEndOfChain() const { return NextInChain == -1; }
nuclear@3 1056 UPInt GetCachedHash(UPInt maskValue) const { return HashF()(Value) & maskValue; }
nuclear@3 1057 void SetCachedHash(UPInt hashValue) { OVR_UNUSED(hashValue); }
nuclear@3 1058
nuclear@3 1059 void Clear()
nuclear@3 1060 {
nuclear@3 1061 Value.~C(); // placement delete
nuclear@3 1062 NextInChain = -2;
nuclear@3 1063 }
nuclear@3 1064 // Free is only used from dtor of hash; Clear is used during regular operations:
nuclear@3 1065 // assignment, hash reallocations, value reassignments, so on.
nuclear@3 1066 void Free() { Clear(); }
nuclear@3 1067 };
nuclear@3 1068
nuclear@3 1069 // Hash table Entry type that caches the Entry hash value for nodes, so that it
nuclear@3 1070 // does not need to be re-computed during access.
nuclear@3 1071 template<class C, class HashF>
nuclear@3 1072 class HashsetCachedNodeEntry
nuclear@3 1073 {
nuclear@3 1074 public:
nuclear@3 1075 // Internal chaining for collisions.
nuclear@3 1076 SPInt NextInChain;
nuclear@3 1077 UPInt HashValue;
nuclear@3 1078 C Value;
nuclear@3 1079
nuclear@3 1080 HashsetCachedNodeEntry()
nuclear@3 1081 : NextInChain(-2) { }
nuclear@3 1082 HashsetCachedNodeEntry(const HashsetCachedNodeEntry& e)
nuclear@3 1083 : NextInChain(e.NextInChain), HashValue(e.HashValue), Value(e.Value) { }
nuclear@3 1084 HashsetCachedNodeEntry(const C& key, SPInt next)
nuclear@3 1085 : NextInChain(next), Value(key) { }
nuclear@3 1086 HashsetCachedNodeEntry(const typename C::NodeRef& keyRef, SPInt next)
nuclear@3 1087 : NextInChain(next), Value(keyRef) { }
nuclear@3 1088
nuclear@3 1089 bool IsEmpty() const { return NextInChain == -2; }
nuclear@3 1090 bool IsEndOfChain() const { return NextInChain == -1; }
nuclear@3 1091 UPInt GetCachedHash(UPInt maskValue) const { OVR_UNUSED(maskValue); return HashValue; }
nuclear@3 1092 void SetCachedHash(UPInt hashValue) { HashValue = hashValue; }
nuclear@3 1093
nuclear@3 1094 void Clear()
nuclear@3 1095 {
nuclear@3 1096 Value.~C();
nuclear@3 1097 NextInChain = -2;
nuclear@3 1098 }
nuclear@3 1099 // Free is only used from dtor of hash; Clear is used during regular operations:
nuclear@3 1100 // assignment, hash reallocations, value reassignments, so on.
nuclear@3 1101 void Free() { Clear(); }
nuclear@3 1102 };
nuclear@3 1103
nuclear@3 1104
nuclear@3 1105 //-----------------------------------------------------------------------------------
nuclear@3 1106 template<class C, class U,
nuclear@3 1107 class HashF = FixedSizeHash<C>,
nuclear@3 1108 class Allocator = ContainerAllocator<C>,
nuclear@3 1109 class HashNode = OVR::HashNode<C,U,HashF>,
nuclear@3 1110 class Entry = HashsetCachedNodeEntry<HashNode, typename HashNode::NodeHashF>,
nuclear@3 1111 class Container = HashSet<HashNode, typename HashNode::NodeHashF,
nuclear@3 1112 typename HashNode::NodeAltHashF, Allocator,
nuclear@3 1113 Entry> >
nuclear@3 1114 class Hash
nuclear@3 1115 {
nuclear@3 1116 public:
nuclear@3 1117 OVR_MEMORY_REDEFINE_NEW(Hash)
nuclear@3 1118
nuclear@3 1119 // Types used for hash_set.
nuclear@3 1120 typedef U ValueType;
nuclear@3 1121 typedef Hash<C, U, HashF, Allocator, HashNode, Entry, Container> SelfType;
nuclear@3 1122
nuclear@3 1123 // Actual hash table itself, implemented as hash_set.
nuclear@3 1124 Container mHash;
nuclear@3 1125
nuclear@3 1126 public:
nuclear@3 1127 Hash() { }
nuclear@3 1128 Hash(int sizeHint) : mHash(sizeHint) { }
nuclear@3 1129 Hash(const SelfType& src) : mHash(src.mHash) { }
nuclear@3 1130 ~Hash() { }
nuclear@3 1131
nuclear@3 1132 void operator = (const SelfType& src) { mHash = src.mHash; }
nuclear@3 1133
nuclear@3 1134 // Remove all entries from the Hash table.
nuclear@3 1135 inline void Clear() { mHash.Clear(); }
nuclear@3 1136 // Returns true if the Hash is empty.
nuclear@3 1137 inline bool IsEmpty() const { return mHash.IsEmpty(); }
nuclear@3 1138
nuclear@3 1139 // Access (set).
nuclear@3 1140 inline void Set(const C& key, const U& value)
nuclear@3 1141 {
nuclear@3 1142 typename HashNode::NodeRef e(key, value);
nuclear@3 1143 mHash.Set(e);
nuclear@3 1144 }
nuclear@3 1145 inline void Add(const C& key, const U& value)
nuclear@3 1146 {
nuclear@3 1147 typename HashNode::NodeRef e(key, value);
nuclear@3 1148 mHash.Add(e);
nuclear@3 1149 }
nuclear@3 1150
nuclear@3 1151 // Removes an element by clearing its Entry.
nuclear@3 1152 inline void Remove(const C& key)
nuclear@3 1153 {
nuclear@3 1154 mHash.RemoveAlt(key);
nuclear@3 1155 }
nuclear@3 1156 template<class K>
nuclear@3 1157 inline void RemoveAlt(const K& key)
nuclear@3 1158 {
nuclear@3 1159 mHash.RemoveAlt(key);
nuclear@3 1160 }
nuclear@3 1161
nuclear@3 1162 // Retrieve the value under the given key.
nuclear@3 1163 // - If there's no value under the key, then return false and leave *pvalue alone.
nuclear@3 1164 // - If there is a value, return true, and Set *Pvalue to the Entry's value.
nuclear@3 1165 // - If value == NULL, return true or false according to the presence of the key.
nuclear@3 1166 bool Get(const C& key, U* pvalue) const
nuclear@3 1167 {
nuclear@3 1168 const HashNode* p = mHash.GetAlt(key);
nuclear@3 1169 if (p)
nuclear@3 1170 {
nuclear@3 1171 if (pvalue)
nuclear@3 1172 *pvalue = p->Second;
nuclear@3 1173 return true;
nuclear@3 1174 }
nuclear@3 1175 return false;
nuclear@3 1176 }
nuclear@3 1177
nuclear@3 1178 template<class K>
nuclear@3 1179 bool GetAlt(const K& key, U* pvalue) const
nuclear@3 1180 {
nuclear@3 1181 const HashNode* p = mHash.GetAlt(key);
nuclear@3 1182 if (p)
nuclear@3 1183 {
nuclear@3 1184 if (pvalue)
nuclear@3 1185 *pvalue = p->Second;
nuclear@3 1186 return true;
nuclear@3 1187 }
nuclear@3 1188 return false;
nuclear@3 1189 }
nuclear@3 1190
nuclear@3 1191 // Retrieve the pointer to a value under the given key.
nuclear@3 1192 // - If there's no value under the key, then return NULL.
nuclear@3 1193 // - If there is a value, return the pointer.
nuclear@3 1194 inline U* Get(const C& key)
nuclear@3 1195 {
nuclear@3 1196 HashNode* p = mHash.GetAlt(key);
nuclear@3 1197 return p ? &p->Second : 0;
nuclear@3 1198 }
nuclear@3 1199 inline const U* Get(const C& key) const
nuclear@3 1200 {
nuclear@3 1201 const HashNode* p = mHash.GetAlt(key);
nuclear@3 1202 return p ? &p->Second : 0;
nuclear@3 1203 }
nuclear@3 1204
nuclear@3 1205 template<class K>
nuclear@3 1206 inline U* GetAlt(const K& key)
nuclear@3 1207 {
nuclear@3 1208 HashNode* p = mHash.GetAlt(key);
nuclear@3 1209 return p ? &p->Second : 0;
nuclear@3 1210 }
nuclear@3 1211 template<class K>
nuclear@3 1212 inline const U* GetAlt(const K& key) const
nuclear@3 1213 {
nuclear@3 1214 const HashNode* p = mHash.GetAlt(key);
nuclear@3 1215 return p ? &p->Second : 0;
nuclear@3 1216 }
nuclear@3 1217
nuclear@3 1218 // Sizing methods - delegate to Hash.
nuclear@3 1219 inline UPInt GetSize() const { return mHash.GetSize(); }
nuclear@3 1220 inline void Resize(UPInt n) { mHash.Resize(n); }
nuclear@3 1221 inline void SetCapacity(UPInt newSize) { mHash.SetCapacity(newSize); }
nuclear@3 1222
nuclear@3 1223 // Iterator API, like STL.
nuclear@3 1224 typedef typename Container::ConstIterator ConstIterator;
nuclear@3 1225 typedef typename Container::Iterator Iterator;
nuclear@3 1226
nuclear@3 1227 inline Iterator Begin() { return mHash.Begin(); }
nuclear@3 1228 inline Iterator End() { return mHash.End(); }
nuclear@3 1229 inline ConstIterator Begin() const { return mHash.Begin(); }
nuclear@3 1230 inline ConstIterator End() const { return mHash.End(); }
nuclear@3 1231
nuclear@3 1232 Iterator Find(const C& key) { return mHash.FindAlt(key); }
nuclear@3 1233 ConstIterator Find(const C& key) const { return mHash.FindAlt(key); }
nuclear@3 1234
nuclear@3 1235 template<class K>
nuclear@3 1236 Iterator FindAlt(const K& key) { return mHash.FindAlt(key); }
nuclear@3 1237 template<class K>
nuclear@3 1238 ConstIterator FindAlt(const K& key) const { return mHash.FindAlt(key); }
nuclear@3 1239 };
nuclear@3 1240
nuclear@3 1241
nuclear@3 1242
nuclear@3 1243 // Hash with uncached hash code; declared for convenience.
nuclear@3 1244 template<class C, class U, class HashF = FixedSizeHash<C>, class Allocator = ContainerAllocator<C> >
nuclear@3 1245 class HashUncached
nuclear@3 1246 : public Hash<C, U, HashF, Allocator, HashNode<C,U,HashF>,
nuclear@3 1247 HashsetNodeEntry<HashNode<C,U,HashF>, typename HashNode<C,U,HashF>::NodeHashF> >
nuclear@3 1248 {
nuclear@3 1249 public:
nuclear@3 1250 typedef HashUncached<C, U, HashF, Allocator> SelfType;
nuclear@3 1251 typedef Hash<C, U, HashF, Allocator, HashNode<C,U,HashF>,
nuclear@3 1252 HashsetNodeEntry<HashNode<C,U,HashF>,
nuclear@3 1253 typename HashNode<C,U,HashF>::NodeHashF> > BaseType;
nuclear@3 1254
nuclear@3 1255 // Delegated constructors.
nuclear@3 1256 HashUncached() { }
nuclear@3 1257 HashUncached(int sizeHint) : BaseType(sizeHint) { }
nuclear@3 1258 HashUncached(const SelfType& src) : BaseType(src) { }
nuclear@3 1259 ~HashUncached() { }
nuclear@3 1260 void operator = (const SelfType& src) { BaseType::operator = (src); }
nuclear@3 1261 };
nuclear@3 1262
nuclear@3 1263
nuclear@3 1264
nuclear@3 1265 // And identity hash in which keys serve as hash value. Can be uncached,
nuclear@3 1266 // since hash computation is assumed cheap.
nuclear@3 1267 template<class C, class U, class Allocator = ContainerAllocator<C>, class HashF = IdentityHash<C> >
nuclear@3 1268 class HashIdentity
nuclear@3 1269 : public HashUncached<C, U, HashF, Allocator>
nuclear@3 1270 {
nuclear@3 1271 public:
nuclear@3 1272 typedef HashIdentity<C, U, Allocator, HashF> SelfType;
nuclear@3 1273 typedef HashUncached<C, U, HashF, Allocator> BaseType;
nuclear@3 1274
nuclear@3 1275 // Delegated constructors.
nuclear@3 1276 HashIdentity() { }
nuclear@3 1277 HashIdentity(int sizeHint) : BaseType(sizeHint) { }
nuclear@3 1278 HashIdentity(const SelfType& src) : BaseType(src) { }
nuclear@3 1279 ~HashIdentity() { }
nuclear@3 1280 void operator = (const SelfType& src) { BaseType::operator = (src); }
nuclear@3 1281 };
nuclear@3 1282
nuclear@3 1283
nuclear@3 1284 } // OVR
nuclear@3 1285
nuclear@3 1286
nuclear@3 1287 #ifdef OVR_DEFINE_NEW
nuclear@3 1288 #define new OVR_DEFINE_NEW
nuclear@3 1289 #endif
nuclear@3 1290
nuclear@3 1291 #endif