summaryrefslogtreecommitdiff
path: root/src/inc/shash.h
blob: 7da434947c776279f9a1572f6c49e07a56aa8ebe (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
//
// Copyright (c) Microsoft. All rights reserved.
// Licensed under the MIT license. See LICENSE file in the project root for full license information.
//


#ifndef _SHASH_H_
#define _SHASH_H_

#include "utilcode.h" // for string hash functions
#include "clrtypes.h"
#include "check.h"
#include "iterator.h"

// SHash is a templated closed chaining hash table of pointers.  It provides
// for multiple entries under the same key, and also for deleting elements.

// Synchronization:
// Synchronization requirements depend on use.  There are several properties to take into account:
//
// - Lookups may be asynchronous with each other
// - Lookups must be exclusive with Add operations 
//    (@todo: this can be remedied by delaying destruction of old tables during reallocation, e.g. during GC)
// - Remove operations may be asynchronous with Lookup/Add, unless elements are also deallocated. (In which 
//    case full synchronization is required)

// Common "gotchas":
// - The Add method never replaces an element. The new element will be added even if an element with the same
//   key is already present. If you don't want this, use AddOrReplace.
// - You need special sentinel values for the element to represent Null and Deleted. 0 and -1 are the default
//   choices but you will need something else if elements can legally have any of these two values.
// - Deriving directly from the general purpose classes (such as SHash itself) requires implementing a
//   TRAITS class which can be daunting. Consider using one of the specialized classes (e.g. WStringSHash) first.

// A SHash is templated by a class of TRAITS.  These traits define the various specifics of the
// particular hash table.
// The required traits are:
//
// element_t                                    Type of elements in the hash table.  These elements are stored
//                                              by value in the hash table. Elements must look more or less 
//                                              like primitives - they must support assignment relatively 
//                                              efficiently.  There are 2 required sentinel values: 
//                                              Null and Deleted (described below).  (Note that element_t is 
//                                              very commonly a pointer type.)  
//
//                                              The key must be derivable from the element; if your
//                                              table's keys are independent of the stored values, element_t
//                                              should be a key/value pair.
//                                              
// key_t                                        Type of the lookup key.  The key is used for identity 
//                                              comparison between elements, and also as a key for lookup. 
//                                              This is also used by value and should support 
//                                              efficient assignment.
//
// count_t                                      integral type for counts.  Typically inherited by default 
//                                              Traits (COUNT_T).
//
// static key_t GetKey(const element_t &e)      Get key from element.  Should be stable for a given e.
// static BOOL Equals(key_t k1, key_t k2)       Compare 2 keys for equality.  Again, should be stable.
// static count_t Hash(key_t k)                 Compute hash from a key.  For efficient operation, the hashes
//                                              for a set of elements should have random uniform distribution.
//
// static const bool s_NoThrow                  TRUE if GetKey, Equals, and hash are NOTHROW functions.  
//                                              Affects the THROWS clauses of several SHash functions.
//                                              (Note that the Null- and Deleted-related functions below 
//                                              are not affected by this and must always be NOTHROW.)
//
// static element_t Null()                      Return the Null sentinal value.  May be inherited from 
//                                              default traits if it can be assigned from 0.
// static element_t Deleted()                   Return the Deleted sentinal value.  May be inherited from the
//                                              default traits if it can be assigned from -1.
// static const bool IsNull(const ELEMENT &e)   Compare element with Null sentinal value. May be inherited from
//                                              default traits if it can be assigned from 0.
// static const bool IsDeleted(const ELEMENT &e) Compare element with Deleted sentinal value. May be inherited from the
//                                              default traits if it can be assigned from -1.
//
// static void OnDestructPerEntryCleanupAction(ELEMENT& e) Called on every element when in hashtable destructor.
//                                              s_DestructPerEntryCleanupAction must be set to true if implemented.
//
// s_growth_factor_numerator
// s_growth_factor_denominator                  Factor to grow allocation (numerator/denominator).  
//                                              Typically inherited from default traits (3/2)
//
// s_density_factor_numerator                   
// s_density_factor_denominator                 Maxium occupied density of table before growth 
//                                              occurs (num/denom).  Typically inherited (3/4).
//
// s_minimum_allocation                         Minimum table allocation count (size on first growth.)  It is 
//                                              probably preferable to call Reallocate on initialization rather
//                                              than override his from the default traits. (7)
//
// s_supports_remove                            Set to false for a slightly faster implementation that does not 
//                                              support deletes. There is a downside to the s_supports_remove flag, 
//                                              in that there may be more copies of the template instantiated through 
//                                              the system as different variants are used.
//
// s_DestructPerEntryCleanupAction              Set to true if OnDestructPerEntryCleanupAction has non-empty implementation.
//
// DefaultHashTraits provides defaults for seldomly customized values in traits classes. 

template < typename ELEMENT > 
class DefaultSHashTraits
{
  public:
    typedef COUNT_T count_t;
    typedef ELEMENT element_t;
    typedef DPTR(element_t) PTR_element_t;   // by default SHash is DAC-aware. For RS
                                             // only SHash use NonDacAwareSHashTraits
                                             // (which typedefs element_t* PTR_element_t)

    static const COUNT_T s_growth_factor_numerator = 3;
    static const COUNT_T s_growth_factor_denominator = 2;

    static const COUNT_T s_density_factor_numerator = 3;
    static const COUNT_T s_density_factor_denominator = 4;

    static const COUNT_T s_minimum_allocation = 7;

    static const bool s_supports_remove = true;

    static const ELEMENT Null() { return (const ELEMENT) 0; }
    static const ELEMENT Deleted() { return (const ELEMENT) -1; }
    static bool IsNull(const ELEMENT &e) { return e == (const ELEMENT) 0; }
    static bool IsDeleted(const ELEMENT &e) { return e == (const ELEMENT) -1; }

    static inline void OnDestructPerEntryCleanupAction(const ELEMENT& e) { /* Do nothing */ }
    static const bool s_DestructPerEntryCleanupAction = false;

    static const bool s_NoThrow = true;

    // No defaults - must specify:
    // 
    // typedef key_t;
    // static key_t GetKey(const element_t &i);
    // static BOOL Equals(key_t k1, key_t k2);
    // static count_t Hash(key_t k);
};

// Hash table class definition

template <typename TRAITS>
class SHash : public TRAITS
            , private noncopyable
{
    friend class VerifyLayoutsMD;  // verifies class layout doesn't accidentally change

  public:
    // explicitly declare local typedefs for these traits types, otherwise 
    // the compiler may get confused
    typedef typename TRAITS::element_t element_t;
    typedef typename TRAITS::PTR_element_t PTR_element_t;
    typedef typename TRAITS::key_t key_t;
    typedef typename TRAITS::count_t count_t;

    class Index;
    friend class Index;
    class Iterator;

    class KeyIndex;
    friend class KeyIndex;
    class KeyIterator;

    // Constructor/destructor.  SHash tables always start out empty, with no
    // allocation overhead.  Call Reallocate to prime with an initial size if
    // desired.

    SHash();

    ~SHash();

    // Lookup an element in the table by key.  Returns NULL if no element in the table
    // has the given key.  Note that multiple entries for the same key may be stored - 
    // this will return the first element added.  Use KeyIterator to find all elements
    // with a given key.

    element_t Lookup(key_t key) const;

    // Pointer-based flavor of Lookup (allows efficient access to tables of structures)

    const element_t* LookupPtr(key_t key) const;

    // Add an element to the hash table.  This will never replace an element; multiple
    // elements may be stored with the same key.

    void Add(const element_t &element);

    // Add a new element to the hash table, if no element with the same key is already 
    // there. Otherwise, it will replace the existing element. This has the effect of
    // updating an element rather than adding a duplicate. 
    void AddOrReplace(const element_t & element);

    // Remove the first element matching the key from the hash table.  

    void Remove(key_t key);

    // Remove the specific element.

    void Remove(Iterator& i);
    void Remove(KeyIterator& i);

    // Pointer-based flavor of Remove (allows efficient access to tables of structures)

    void RemovePtr(element_t * element);

    // Remove all elements in the hashtable

    void RemoveAll();

    // Begin and End pointers for iteration over entire table. 

    Iterator Begin() const;
    Iterator End() const;

    // Begin and End pointers for iteration over all elements with a given key.

    KeyIterator Begin(key_t key) const;
    KeyIterator End(key_t key) const;

    // Return the number of elements currently stored in the table

    count_t GetCount() const; 

    // Resizes a hash table for growth.  The new size is computed based
    // on the current population, growth factor, and maximum density factor.

    void Grow();

    // Reallocates a hash table to a specific size.  The size must be big enough
    // to hold all elements in the table appropriately.  
    //
    // Note that the actual table size must always be a prime number; the number
    // passed in will be upward adjusted if necessary.

    void Reallocate(count_t newTableSize);

    // Makes a call on the Functor for each element in the hash table, passing
    // the element as an argument. Functor is expected to look like this:
    //
    // class Functor
    // {
    //     public:
    //     void operator() (element_t &element) { ... }
    // }

    template<typename Functor> void ForEach(Functor &functor);

  private:

    // See if it is OK to grow the hash table by one element.  If not, reallocate
    // the hash table.
    BOOL CheckGrowth();
    
    // See if it is OK to grow the hash table by one element. If not, allocate new 
    // hash table and return it together with its size *pcNewSize (used by code:AddPhases).
    // Returns NULL if there already is space for one element.
    element_t * CheckGrowth_OnlyAllocateNewTable(count_t * pcNewSize);
    
    // Allocates new resized hash table for growth. Does not update the hash table on the object.
    // The new size is computed based on the current population, growth factor, and maximum density factor.
    element_t * Grow_OnlyAllocateNewTable(count_t * pcNewSize);
    
    // Utility function to allocate new table (does not copy the values into it yet). Returns the size of new table in 
    // *pcNewTableSize (finds next prime).
    // Phase 1 of code:Reallocate - it is split to support code:AddPhases.
    element_t * AllocateNewTable(count_t requestedSize, count_t * pcNewTableSize);
    
    // Utility function to replace old table with newly allocated table (as allocated by 
    // code:AllocateNewTable). Copies all 'old' values into the new table first.
    // Returns the old table. Caller is expected to delete it (via code:DeleteOldTable).
    // Phase 2 of code:Reallocate - it is split to support code:AddPhases.
    element_t * ReplaceTable(element_t * newTable, count_t newTableSize);
    
    // Utility function to delete old table (as returned by code:ReplaceTable).
    // Phase 3 of code:Reallocate - it is split to support code:AddPhases.
    void DeleteOldTable(element_t * oldTable);
    
    // Utility function that does not call code:CheckGrowth.
    // Add an element to the hash table.  This will never replace an element; multiple 
    // elements may be stored with the same key.
    void Add_GrowthChecked(const element_t & element);
    
    // Utility function to add a new element to the hash table.  Note that
    // it is perfectly fine for the element to be a duplicate - if so it
    // is added an additional time. Returns TRUE if a new empty spot was used;
    // FALSE if an existing deleted slot.
    static BOOL Add(element_t *table, count_t tableSize, const element_t &element);

    // Utility function to add a new element to the hash table, if no element with the same key
    // is already there. Otherwise, it will replace the existing element. This has the effect of
    // updating an element rather than adding a duplicate. 
    void AddOrReplace(element_t *table, count_t tableSize, const element_t &element);
 
    // Utility function to find the first element with the given key in 
    // the hash table.

    static const element_t* Lookup(PTR_element_t table, count_t tableSize, key_t key);

    // Utility function to remove the first element with the given key
    // in the hash table.

    void Remove(element_t *table, count_t tableSize, key_t key);

    // Utility function to remove the specific element.

    void RemoveElement(element_t *table, count_t tableSize, element_t *element);

    // Index for whole table iterator.  This is also the base for the keyed iterator.

  public:

    class Index
#ifdef _DEBUG
        // CheckedIteratorBase is a no-op in RET builds. having it as an empty base-class
        // causes differences in the sizeof(SHash::Iterator) in DAC vs. non-DAC builds.
        // avoid the issue by not specifying it as a base class in RET builds
        : public CheckedIteratorBase< SHash<TRAITS> >
#endif
    {
        friend class SHash;
        friend class Iterator;
        friend class Enumerator<const element_t, Iterator>;

        // The methods implementation has to be here for portability
        // Some compilers won't compile the separate implementation in shash.inl
      protected:

        PTR_element_t m_table;
        count_t m_tableSize;
        count_t m_index;

        Index(const SHash *hash, BOOL begin)
        : m_table(hash->m_table),
            m_tableSize(hash->m_tableSize),
            m_index(begin ? 0 : m_tableSize)
        {
            LIMITED_METHOD_CONTRACT;
        }

        const element_t &Get() const
        {
            LIMITED_METHOD_CONTRACT;

            return m_table[m_index];
        }

        void First()
        {
            LIMITED_METHOD_CONTRACT;

            if (m_index < m_tableSize)
                if (TRAITS::IsNull(m_table[m_index]) || TRAITS::IsDeleted(m_table[m_index]))
                    Next();
        }

        void Next()
        {
            LIMITED_METHOD_CONTRACT;

            if (m_index >= m_tableSize)
                return;
            
            for (;;)
            {
                m_index++;
                if (m_index >= m_tableSize)
                    break;
                if (!TRAITS::IsNull(m_table[m_index]) && !TRAITS::IsDeleted(m_table[m_index]))
                    break;
            }
        }

        bool Equal(const Index &i) const
        { 
            LIMITED_METHOD_CONTRACT;

            return i.m_index == m_index; 
        }

        CHECK DoCheck() const
        {
            CHECK_OK;
        }
    };

    class Iterator : public Index, public Enumerator<const element_t, Iterator>
    {
        friend class SHash;

      public:
        Iterator(const SHash *hash, BOOL begin)
          : Index(hash, begin)
        {
        }
    };

    // Index for iterating elements with a given key.  
    //
    // Note that the m_index field
    // is artificially bumped to m_tableSize when the end of iteration is reached.
    // This allows a canonical End iterator to be used.

    class KeyIndex : public Index
    {
        friend class SHash;
        friend class KeyIterator;
        friend class Enumerator<const element_t, KeyIterator>;

        // The methods implementation has to be here for portability
        // Some compilers won't compile the separate implementation in shash.inl
      protected:
        key_t       m_key;
        count_t     m_increment;

        KeyIndex(const SHash *hash, BOOL begin)
        : Index(hash, begin),
            m_increment(0)
        {
            LIMITED_METHOD_CONTRACT;
        }

        void SetKey(key_t key)
        {
            LIMITED_METHOD_CONTRACT;

            if (Index::m_tableSize > 0)
            {
                m_key = key;
                count_t hash = TRAITS::Hash(key);

                this->m_index = hash % this->m_tableSize;
                m_increment = (hash % (this->m_tableSize-1)) + 1;

                // Find first valid element
                if (TRAITS::IsNull(this->m_table[this->m_index]))
                    this->m_index = this->m_tableSize;
                else if (TRAITS::IsDeleted(this->m_table[this->m_index])
                        || !TRAITS::Equals(m_key, TRAITS::GetKey(this->m_table[this->m_index])))
                    Next();
            }
        }

        void Next()
        {
            LIMITED_METHOD_CONTRACT;

            while (TRUE)
            {
                this->m_index += m_increment;
                if (this->m_index >= this->m_tableSize)
                    this->m_index -= this->m_tableSize;

                if (TRAITS::IsNull(this->m_table[this->m_index]))
                {
                    this->m_index = this->m_tableSize;
                    break;
                }

                if (!TRAITS::IsDeleted(this->m_table[this->m_index])
                        && TRAITS::Equals(m_key, TRAITS::GetKey(this->m_table[this->m_index])))
                {
                    break;
                }
            }
        }
    };

    class KeyIterator : public KeyIndex, public Enumerator<const element_t, KeyIterator>
    {
        friend class SHash;

      public:

        operator Iterator &()
        {
            return *(Iterator*)this;
        }

        operator const Iterator &()
        {
            return *(const Iterator*)this;
        }

        KeyIterator(const SHash *hash, BOOL begin)
          : KeyIndex(hash, begin)
        {
        }
    };

    // Wrapper and holder for adding an element to the hash table. Useful for Add operations that have to happen 
    // under a rare lock that does not allow call out into host.
    // There are 3 phases:
    //    1. code:PreallocateForAdd ... Can allocate memory (calls into host).
    //    2. code:Add ... Adds one element (does NOT call into host).
    //       or code:AddNothing_PublishPreallocatedTable ... Publishes the pre-allocated memory from step #1 (if any).
    //    3. code:DeleteOldTable (or destructor) ... Can delete the old memory (calls into host).
    // Example:
    //      CrstHolder lockAdd(&crstLockForAdd); // Serialize all Add operations.
    //      HostAssemblyMap::AddPhases addCall;
    //      addCall.PreallocateForAdd(&shash); // 1. Allocates memory for one Add call (if needed). addCall serves as holder for the allocated memory.
    //      {
    //          // We cannot call out into host from ForbidSuspend region (i.e. no allocations/deallocations).
    //          ForbidSuspendThreadHolder suspend; // Required by the 'special' read-lock
    //          {
    //              CrstHolder lock(&crstLock);
    //              if (some_condition)
    //              {   // 2a. Add item. This may replace SHash inner table with the one pre-allocated in step 1.
    //                  addCall.Add(shashItem);
    //              }
    //              else
    //              {   // 2b. Skip adding item. This may replace SHash inner table with the one pre-allocated in step 1.
    //                  addCall.AddNothing_PublishPreallocatedTable();
    //              }
    //          }
    //      }
    //      addCall.DeleteOldTable(); // 3. Cleanup old table memory from shash (if it was replaced by pre-allocated table in step 2).
    //                                // Note: addCall destructor would take care of deleting the memory as well.
    class AddPhases
    {
    public:
        AddPhases();
        ~AddPhases();
        
        // Prepares object for one call to code:Add. Pre-allocates new table memory if needed, does not publish 
        // the table yet (it is kept ready only in this holder for call to code:Add).
        // Calls out into host.
        void PreallocateForAdd(SHash * pHash);
        
        // Add an element to the hash table. This will never replace an element; multiple elements may be stored 
        // with the same key.
        // Will use/publish pre-allocated memory from code:PreallocateForAdd.
        // Does not call out into host.
        // Only one Add* method can be called once per object! (Create a new object for each call)
        void Add(const element_t & element);
        
        // Element will not be added to the hash table.
        // Will use/publish pre-allocated memory from code:PreallocateForAdd.
        // Does not call out into host.
        // Only one Add* method can be called once per object! (Create a new object for each call)
        void AddNothing_PublishPreallocatedTable();
        
        // Deletes old table if it was replaced by call to code:Add or code:AddNothing_PublishPreallocatedTable.
        // Calls out into host.
        void DeleteOldTable();
        
    private:
        SHash *     m_pHash;
        element_t * m_newTable;
        count_t     m_newTableSize;
        element_t * m_oldTable;
        
    #ifdef _DEBUG
        PTR_element_t dbg_m_table;
        count_t       dbg_m_tableSize;
        count_t       dbg_m_tableCount;
        count_t       dbg_m_tableOccupied;
        count_t       dbg_m_tableMax;
        BOOL          dbg_m_fAddCalled;
    #endif //_DEBUG
    };  // class SHash::AddPhases

    // Adds an entry to the hash table according to the guidelines above for
    // avoiding a callout to the host while the read lock is held.
    // Returns true if elem was added to the map, otherwise false.
    // When elem was not added (false is returned), and if ppStoredElem is non-null,
    // then it is set to point to the value in the map.
    template <typename LockHolderT,
              typename AddLockHolderT,
              typename LockT,
              typename AddLockT>
    bool CheckAddInPhases(
        element_t const & elem,
        LockT & lock,
        AddLockT & addLock,
        IUnknown * addRefObject = nullptr);
        
  private:
    
    // Test for prime number.
    static BOOL IsPrime(COUNT_T number);

    // Find the next prime number >= the given value.  

    static COUNT_T NextPrime(COUNT_T number);

    // Instance members

    PTR_element_t m_table;                // pointer to table
    count_t       m_tableSize;            // allocated size of table
    count_t       m_tableCount;           // number of elements in table
    count_t       m_tableOccupied;        // number, includes deleted slots
    count_t       m_tableMax;             // maximum occupied count before reallocating
};  // class SHash

// disables support for DAC marshaling. Useful for defining right-side only SHashes
template <typename PARENT>
class NonDacAwareSHashTraits : public PARENT
{
public:
    typedef typename PARENT::element_t element_t;
    typedef element_t * PTR_element_t;
};

// disables support for removing elements - produces slightly faster implementation

template <typename PARENT>
class NoRemoveSHashTraits : public PARENT
{
public:
    // explicitly declare local typedefs for these traits types, otherwise 
    // the compiler may get confused
    typedef typename PARENT::element_t element_t;
    typedef typename PARENT::count_t count_t;

    static const bool s_supports_remove = false;
    static const element_t Deleted() { UNREACHABLE(); }
    static bool IsDeleted(const element_t &e) { LIMITED_METHOD_DAC_CONTRACT; return false; }
};

// PtrHashTraits is a template to provides useful defaults for pointer hash tables
// It relies on methods GetKey and Hash defined on ELEMENT

template <typename ELEMENT, typename KEY> 
class PtrSHashTraits : public DefaultSHashTraits<ELEMENT *>
{
  public:

    // explicitly declare local typedefs for these traits types, otherwise 
    // the compiler may get confused
    typedef DefaultSHashTraits<ELEMENT *> PARENT;
    typedef typename PARENT::element_t element_t;
    typedef typename PARENT::count_t count_t;

    typedef KEY key_t;

    static key_t GetKey(const element_t &e) 
    { 
        WRAPPER_NO_CONTRACT;
        return e->GetKey(); 
    }
    static BOOL Equals(key_t k1, key_t k2) 
    { 
        LIMITED_METHOD_CONTRACT;
        return k1 == k2; 
    }
    static count_t Hash(key_t k)
    { 
        WRAPPER_NO_CONTRACT;
        return ELEMENT::Hash(k);
    }
};

template <typename ELEMENT, typename KEY>
class PtrSHash : public SHash< PtrSHashTraits<ELEMENT, KEY> >
{
};

template <typename ELEMENT, typename KEY> 
class PtrSHashWithCleanupTraits
    : public PtrSHashTraits<ELEMENT, KEY>
{
public:
    void OnDestructPerEntryCleanupAction(ELEMENT * elem)
    {
        delete elem;
    }
    static const bool s_DestructPerEntryCleanupAction = true;
};

// a class that automatically deletes data referenced by the pointers (so effectively it takes ownership of the data)
// since I was too lazy to implement Remove() APIs properly, removing entries is disallowed
template <typename ELEMENT, typename KEY>
class PtrSHashWithCleanup : public SHash< NoRemoveSHashTraits< PtrSHashWithCleanupTraits<ELEMENT, KEY> > >
{
};

// Provides case-sensitive comparison and hashing functionality through static
// and functor object methods. Can be instantiated with CHAR or WCHAR.
template <typename CharT>
struct CaseSensitiveStringCompareHash
{
private:
    typedef CharT const * str_t;

    static size_t _strcmp(CHAR const *left, CHAR const *right)
    {
        return ::strcmp(left, right);
    }

    static size_t _strcmp(WCHAR const *left, WCHAR const *right)
    {
        return ::wcscmp(left, right);
    }

    static size_t _hash(CHAR const *str)
    {
        return HashStringA(str);
    }
    
    static size_t _hash(WCHAR const *str)
    {
        return HashString(str);
    }

public:
    static size_t compare(str_t left, str_t right)
    {
        return _strcmp(left, right);
    }

    size_t operator()(str_t left, str_t right)
    {
        return compare(left, right);
    }

    static size_t hash(str_t str)
    {
        return _hash(str);
    }

    size_t operator()(str_t str)
    {
        return hash(str);
    }
};

// Provides case-insensitive comparison and hashing functionality through static
// and functor object methods. Can be instantiated with CHAR or WCHAR.
template <typename CharT>
struct CaseInsensitiveStringCompareHash
{
private:
    typedef CharT const * str_t;

    static size_t _strcmp(str_t left, str_t right)
    {
        return ::SString::_tstricmp(left, right);
    }

    static size_t _hash(CHAR const *str)
    {
        return HashiStringA(str);
    }
    
    static size_t _hash(WCHAR const *str)
    {
        return HashiString(str);
    }

public:
    static size_t compare(str_t left, str_t right)
    {
        return _strcmp(left, right);
    }

    size_t operator()(str_t left, str_t right)
    {
        return compare(left, right);
    }

    static size_t hash(str_t str)
    {
        return _hash(str);
    }

    size_t operator()(str_t str)
    {
        return hash(str);
    }
};

// StringSHashTraits is a traits class useful for string-keyed
// pointer hash tables. 

template <typename ElementT, typename CharT, typename ComparerT = CaseSensitiveStringCompareHash<CharT> >
class StringSHashTraits : public PtrSHashTraits<ElementT, CharT const *>
{
public:
    // explicitly declare local typedefs for these traits types, otherwise 
    // the compiler may get confused
    typedef PtrSHashTraits<ElementT, CharT const *> PARENT;
    typedef typename PARENT::element_t element_t;
    typedef typename PARENT::key_t key_t;
    typedef typename PARENT::count_t count_t;

    static BOOL Equals(key_t k1, key_t k2) 
    { 
        LIMITED_METHOD_CONTRACT;

        if (k1 == NULL && k2 == NULL)
            return TRUE;
        if (k1 == NULL || k2 == NULL)
            return FALSE;
        return ComparerT::compare(k1, k2) == 0; 
    }
    static count_t Hash(key_t k) 
    { 
        LIMITED_METHOD_CONTRACT;

        if (k == NULL)
            return 0;
        else
            return (count_t)ComparerT::hash(k); 
    }
};

template <typename COMINTERFACE, typename CharT> // Could use IUnknown but would rather take advantage of C++ type checking
struct StringHashElement
{
    const CharT *GetKey()
    {
        return String;
    }

    COMINTERFACE *Object;
    CharT *String;
};

template <typename COMINTERFACE, typename CharT, typename ComparerT = CaseSensitiveStringCompareHash<CharT> >
class StringHashWithCleanupTraits : public StringSHashTraits<StringHashElement<COMINTERFACE, CharT>, CharT, ComparerT>
{
public:
    void OnDestructPerEntryCleanupAction(StringHashElement<COMINTERFACE, CharT> * e)
    {
        if (e->String != NULL)
        {
            delete[] e->String;
        }
        
        if (e->Object != NULL)
        {
            e->Object->Release();
        }
    }
    static const bool s_DestructPerEntryCleanupAction = true;
};

template <typename COMINTERFACE, typename CharT, typename ComparerT = CaseSensitiveStringCompareHash<CharT> >
class StringSHashWithCleanup : public SHash< StringHashWithCleanupTraits<COMINTERFACE, CharT, ComparerT> >
{
};

template <typename ELEMENT>
class StringSHash : public SHash< StringSHashTraits<ELEMENT, CHAR> >
{
};

template <typename ELEMENT>
class WStringSHash : public SHash< StringSHashTraits<ELEMENT, WCHAR> >
{
};

template <typename ELEMENT> 
class SStringSHashTraits : public PtrSHashTraits<ELEMENT, SString>
{
  public:
    typedef PtrSHashTraits<ELEMENT, SString> PARENT;
    typedef typename PARENT::element_t element_t;
    typedef typename PARENT::key_t key_t;
    typedef typename PARENT::count_t count_t;

    static const bool s_NoThrow = false;

    static BOOL Equals(const key_t &k1, const key_t &k2) 
    { 
        WRAPPER_NO_CONTRACT;
        return k1.Equals(k2);
    }
    static count_t Hash(const key_t &k) 
    { 
        WRAPPER_NO_CONTRACT;
        return k.Hash();
    }
};

template <typename ELEMENT>
class SStringSHash : public SHash< SStringSHashTraits<ELEMENT> >
{
};

template <typename ELEMENT>
class SetSHashTraits : public DefaultSHashTraits<ELEMENT>
{
public:
    // explicitly declare local typedefs for these traits types, otherwise 
    // the compiler may get confused
    typedef typename DefaultSHashTraits<ELEMENT>::element_t element_t;
    typedef typename DefaultSHashTraits<ELEMENT>::count_t count_t;

    typedef ELEMENT key_t;

    static key_t GetKey(element_t e)
    {
        LIMITED_METHOD_CONTRACT;
        return e;
    }
    static BOOL Equals(key_t k1, key_t k2)
    {
        LIMITED_METHOD_CONTRACT;
        return k1 == k2;
    }
    static count_t Hash(key_t k)
    {
        LIMITED_METHOD_CONTRACT;
        return (count_t)(size_t)k;
    }
};

template <typename ELEMENT, typename TRAITS = NoRemoveSHashTraits< SetSHashTraits <ELEMENT> > >
class SetSHash : public SHash< TRAITS >
{
    typedef SHash<TRAITS> PARENT;

public:
    BOOL Contains(ELEMENT key) const
    {
        return PARENT::LookupPtr(key) != NULL;
    }
};

template <typename ELEMENT> 
class PtrSetSHashTraits : public SetSHashTraits<ELEMENT>
{
  public:

    // explicitly declare local typedefs for these traits types, otherwise 
    // the compiler may get confused
    typedef SetSHashTraits<ELEMENT> PARENT;
    typedef typename PARENT::element_t element_t;
    typedef typename PARENT::key_t key_t;
    typedef typename PARENT::count_t count_t;

    static count_t Hash(key_t k) 
    { 
        WRAPPER_NO_CONTRACT;
        return (count_t)(size_t)k >> 2;
    }
};

template <typename PARENT_TRAITS>
class DeleteElementsOnDestructSHashTraits : public PARENT_TRAITS
{
public:
    static inline void OnDestructPerEntryCleanupAction(typename PARENT_TRAITS::element_t e)
    {
        delete e;
    }
    static const bool s_DestructPerEntryCleanupAction = true;
};

#if !defined(CC_JIT) // workaround: Key is redefined in JIT64

template <typename KEY, typename VALUE>
class KeyValuePair {
    KEY     key;
    VALUE   value;

public:
    KeyValuePair()
    {
    }

    KeyValuePair(const KEY& k, const VALUE& v)
        : key(k), value(v)
    {
    }

    KEY const & Key() const
    {
        LIMITED_METHOD_CONTRACT;
        return key;
    }

    VALUE const & Value() const
    {
        LIMITED_METHOD_CONTRACT;
        return value;
    }
};

template <typename KEY, typename VALUE>
class MapSHashTraits : public DefaultSHashTraits< KeyValuePair<KEY,VALUE> >
{
public:
    // explicitly declare local typedefs for these traits types, otherwise 
    // the compiler may get confused
    typedef typename DefaultSHashTraits< KeyValuePair<KEY,VALUE> >::element_t element_t;
    typedef typename DefaultSHashTraits< KeyValuePair<KEY,VALUE> >::count_t count_t;

    typedef KEY key_t;

    static key_t GetKey(element_t e)
    {
        LIMITED_METHOD_CONTRACT;
        return e.Key();
    }
    static BOOL Equals(key_t k1, key_t k2)
    {
        LIMITED_METHOD_CONTRACT;
        return k1 == k2;
    }
    static count_t Hash(key_t k)
    {
        LIMITED_METHOD_CONTRACT;
        return (count_t)(size_t)k;
    }

    static const element_t Null() { LIMITED_METHOD_CONTRACT; return element_t(KEY(),VALUE()); }
    static const element_t Deleted() { LIMITED_METHOD_CONTRACT; return element_t(KEY(-1), VALUE()); }
    static bool IsNull(const element_t &e) { LIMITED_METHOD_CONTRACT; return e.Key() == KEY(); }
    static bool IsDeleted(const element_t &e) { return e.Key() == KEY(-1); }
};

template <typename KEY, typename VALUE, typename TRAITS = NoRemoveSHashTraits< MapSHashTraits <KEY, VALUE> > >
class MapSHash : public SHash< TRAITS >
{
    typedef SHash< TRAITS > PARENT;

public:
    void Add(KEY key, VALUE value)
    {
        CONTRACTL
        {
            THROWS;
            GC_NOTRIGGER;
            PRECONDITION(key != (KEY)0);
        }
        CONTRACTL_END;

        PARENT::Add(KeyValuePair<KEY,VALUE>(key, value));
    }

    BOOL Lookup(KEY key, VALUE* pValue) const
    {
        CONTRACTL
        {
            NOTHROW;
            GC_NOTRIGGER;
            PRECONDITION(key != (KEY)0);
        }
        CONTRACTL_END;

        const KeyValuePair<KEY,VALUE> *pRet = PARENT::LookupPtr(key);
        if (pRet == NULL)
            return FALSE;

        *pValue = pRet->Value();
        return TRUE;
    }
};

template <typename KEY, typename VALUE>
class MapSHashWithRemove : public SHash< MapSHashTraits <KEY, VALUE> >
{
    typedef SHash< MapSHashTraits <KEY, VALUE> > PARENT;

public:
    void Add(KEY key, VALUE value)
    {
        CONTRACTL
        {
            THROWS;
            GC_NOTRIGGER;
            PRECONDITION(key != (KEY)0 && key != (KEY)-1);
        }
        CONTRACTL_END;

        PARENT::Add(KeyValuePair<KEY,VALUE>(key, value));
    }

    BOOL Lookup(KEY key, VALUE* pValue) const
    {
        CONTRACTL
        {
            NOTHROW;
            GC_NOTRIGGER;
            PRECONDITION(key != (KEY)0 && key != (KEY)-1);
        }
        CONTRACTL_END;

        const KeyValuePair<KEY,VALUE> *pRet = PARENT::LookupPtr(key);
        if (pRet == NULL)
            return FALSE;

        *pValue = pRet->Value();
        return TRUE;
    }

    void Remove(KEY key)
    {
        CONTRACTL
        {
            NOTHROW;
            GC_NOTRIGGER;
            PRECONDITION(key != (KEY)0 && key != (KEY)-1);
        }
        CONTRACTL_END;

        PARENT::Remove(key);
    }
};

#endif // CC_JIT

#include "shash.inl"

#endif // _SHASH_H_