path: root/src/inc/shash.h

//
// 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_