gwnavruntime/kernel/SF_Hash.h Source File

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