oculus1

annotate libovr/Src/Kernel/OVR_Hash.h @ 1:e2f9e4603129

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