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