ovr_sdk

annotate LibOVR/Src/Kernel/OVR_Hash.h @ 0:1b39a1b46319

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