1 // Licensed to the .NET Foundation under one or more agreements.
2 // The .NET Foundation licenses this file to you under the MIT license.
3 // See the LICENSE file in the project root for more information.
9 #include "utilcode.h" // for string hash functions
14 // SHash is a templated closed chaining hash table of pointers. It provides
15 // for multiple entries under the same key, and also for deleting elements.
18 // Synchronization requirements depend on use. There are several properties to take into account:
20 // - Lookups may be asynchronous with each other
21 // - Lookups must be exclusive with Add operations
22 // (@todo: this can be remedied by delaying destruction of old tables during reallocation, e.g. during GC)
23 // - Remove operations may be asynchronous with Lookup/Add, unless elements are also deallocated. (In which
24 // case full synchronization is required)
27 // - The Add method never replaces an element. The new element will be added even if an element with the same
28 // key is already present. If you don't want this, use AddOrReplace.
29 // - You need special sentinel values for the element to represent Null and Deleted. 0 and -1 are the default
30 // choices but you will need something else if elements can legally have any of these two values.
31 // - Deriving directly from the general purpose classes (such as SHash itself) requires implementing a
32 // TRAITS class which can be daunting. Consider using one of the specialized classes (e.g. WStringSHash) first.
34 // A SHash is templated by a class of TRAITS. These traits define the various specifics of the
35 // particular hash table.
36 // The required traits are:
38 // element_t Type of elements in the hash table. These elements are stored
39 // by value in the hash table. Elements must look more or less
40 // like primitives - they must support assignment relatively
41 // efficiently. There are 2 required sentinel values:
42 // Null and Deleted (described below). (Note that element_t is
43 // very commonly a pointer type.)
45 // The key must be derivable from the element; if your
46 // table's keys are independent of the stored values, element_t
47 // should be a key/value pair.
49 // key_t Type of the lookup key. The key is used for identity
50 // comparison between elements, and also as a key for lookup.
51 // This is also used by value and should support
52 // efficient assignment.
54 // count_t integral type for counts. Typically inherited by default
57 // static key_t GetKey(const element_t &e) Get key from element. Should be stable for a given e.
58 // static BOOL Equals(key_t k1, key_t k2) Compare 2 keys for equality. Again, should be stable.
59 // static count_t Hash(key_t k) Compute hash from a key. For efficient operation, the hashes
60 // for a set of elements should have random uniform distribution.
62 // static const bool s_NoThrow TRUE if GetKey, Equals, and hash are NOTHROW functions.
63 // Affects the THROWS clauses of several SHash functions.
64 // (Note that the Null- and Deleted-related functions below
65 // are not affected by this and must always be NOTHROW.)
67 // static element_t Null() Return the Null sentinal value. May be inherited from
68 // default traits if it can be assigned from 0.
69 // static element_t Deleted() Return the Deleted sentinal value. May be inherited from the
70 // default traits if it can be assigned from -1.
71 // static const bool IsNull(const ELEMENT &e) Compare element with Null sentinal value. May be inherited from
72 // default traits if it can be assigned from 0.
73 // static const bool IsDeleted(const ELEMENT &e) Compare element with Deleted sentinal value. May be inherited from the
74 // default traits if it can be assigned from -1.
76 // static void OnDestructPerEntryCleanupAction(ELEMENT& e) Called on every element when in hashtable destructor.
77 // s_DestructPerEntryCleanupAction must be set to true if implemented.
79 // s_growth_factor_numerator
80 // s_growth_factor_denominator Factor to grow allocation (numerator/denominator).
81 // Typically inherited from default traits (3/2)
83 // s_density_factor_numerator
84 // s_density_factor_denominator Maxium occupied density of table before growth
85 // occurs (num/denom). Typically inherited (3/4).
87 // s_minimum_allocation Minimum table allocation count (size on first growth.) It is
88 // probably preferable to call Reallocate on initialization rather
89 // than override his from the default traits. (7)
91 // s_supports_remove Set to false for a slightly faster implementation that does not
92 // support deletes. There is a downside to the s_supports_remove flag,
93 // in that there may be more copies of the template instantiated through
94 // the system as different variants are used.
96 // s_DestructPerEntryCleanupAction Set to true if OnDestructPerEntryCleanupAction has non-empty implementation.
98 // DefaultHashTraits provides defaults for seldomly customized values in traits classes.
100 template < typename ELEMENT >
101 class DefaultSHashTraits
104 typedef COUNT_T count_t;
105 typedef ELEMENT element_t;
106 typedef DPTR(element_t) PTR_element_t; // by default SHash is DAC-aware. For RS
107 // only SHash use NonDacAwareSHashTraits
108 // (which typedefs element_t* PTR_element_t)
110 static const COUNT_T s_growth_factor_numerator = 3;
111 static const COUNT_T s_growth_factor_denominator = 2;
113 static const COUNT_T s_density_factor_numerator = 3;
114 static const COUNT_T s_density_factor_denominator = 4;
116 static const COUNT_T s_minimum_allocation = 7;
118 static const bool s_supports_remove = true;
120 static const ELEMENT Null() { return (const ELEMENT) 0; }
121 static const ELEMENT Deleted() { return (const ELEMENT) -1; }
122 static bool IsNull(const ELEMENT &e) { return e == (const ELEMENT) 0; }
123 static bool IsDeleted(const ELEMENT &e) { return e == (const ELEMENT) -1; }
125 static inline void OnDestructPerEntryCleanupAction(const ELEMENT& e) { /* Do nothing */ }
126 static const bool s_DestructPerEntryCleanupAction = false;
128 static const bool s_NoThrow = true;
130 // No defaults - must specify:
133 // static key_t GetKey(const element_t &i);
134 // static BOOL Equals(key_t k1, key_t k2);
135 // static count_t Hash(key_t k);
138 // Hash table class definition
140 template <typename TRAITS>
141 class SHash : public TRAITS
142 , private noncopyable
144 friend class VerifyLayoutsMD; // verifies class layout doesn't accidentally change
147 // explicitly declare local typedefs for these traits types, otherwise
148 // the compiler may get confused
149 typedef typename TRAITS::element_t element_t;
150 typedef typename TRAITS::PTR_element_t PTR_element_t;
151 typedef typename TRAITS::key_t key_t;
152 typedef typename TRAITS::count_t count_t;
159 friend class KeyIndex;
162 // Constructor/destructor. SHash tables always start out empty, with no
163 // allocation overhead. Call Reallocate to prime with an initial size if
170 // Lookup an element in the table by key. Returns NULL if no element in the table
171 // has the given key. Note that multiple entries for the same key may be stored -
172 // this will return the first element added. Use KeyIterator to find all elements
175 element_t Lookup(key_t key) const;
177 // Pointer-based flavor of Lookup (allows efficient access to tables of structures)
179 const element_t* LookupPtr(key_t key) const;
181 // Add an element to the hash table. This will never replace an element; multiple
182 // elements may be stored with the same key.
184 void Add(const element_t &element);
186 // Add a new element to the hash table, if no element with the same key is already
187 // there. Otherwise, it will replace the existing element. This has the effect of
188 // updating an element rather than adding a duplicate.
189 void AddOrReplace(const element_t & element);
191 // Remove the first element matching the key from the hash table.
193 void Remove(key_t key);
195 // Remove the specific element.
197 void Remove(Iterator& i);
198 void Remove(KeyIterator& i);
200 // Pointer-based flavor of Remove (allows efficient access to tables of structures)
202 void RemovePtr(element_t * element);
204 // Remove all elements in the hashtable
208 // Begin and End pointers for iteration over entire table.
210 Iterator Begin() const;
211 Iterator End() const;
213 // Begin and End pointers for iteration over all elements with a given key.
215 KeyIterator Begin(key_t key) const;
216 KeyIterator End(key_t key) const;
218 // Return the number of elements currently stored in the table
220 count_t GetCount() const;
222 // Resizes a hash table for growth. The new size is computed based
223 // on the current population, growth factor, and maximum density factor.
227 // Reallocates a hash table to a specific size. The size must be big enough
228 // to hold all elements in the table appropriately.
230 // Note that the actual table size must always be a prime number; the number
231 // passed in will be upward adjusted if necessary.
233 void Reallocate(count_t newTableSize);
235 // Makes a call on the Functor for each element in the hash table, passing
236 // the element as an argument. Functor is expected to look like this:
241 // void operator() (element_t &element) { ... }
244 template<typename Functor> void ForEach(Functor &functor);
248 // See if it is OK to grow the hash table by one element. If not, reallocate
252 // See if it is OK to grow the hash table by one element. If not, allocate new
253 // hash table and return it together with its size *pcNewSize (used by code:AddPhases).
254 // Returns NULL if there already is space for one element.
255 element_t * CheckGrowth_OnlyAllocateNewTable(count_t * pcNewSize);
257 // Allocates new resized hash table for growth. Does not update the hash table on the object.
258 // The new size is computed based on the current population, growth factor, and maximum density factor.
259 element_t * Grow_OnlyAllocateNewTable(count_t * pcNewSize);
261 // Utility function to allocate new table (does not copy the values into it yet). Returns the size of new table in
262 // *pcNewTableSize (finds next prime).
263 // Phase 1 of code:Reallocate - it is split to support code:AddPhases.
264 element_t * AllocateNewTable(count_t requestedSize, count_t * pcNewTableSize);
266 // Utility function to replace old table with newly allocated table (as allocated by
267 // code:AllocateNewTable). Copies all 'old' values into the new table first.
268 // Returns the old table. Caller is expected to delete it (via code:DeleteOldTable).
269 // Phase 2 of code:Reallocate - it is split to support code:AddPhases.
270 element_t * ReplaceTable(element_t * newTable, count_t newTableSize);
272 // Utility function to delete old table (as returned by code:ReplaceTable).
273 // Phase 3 of code:Reallocate - it is split to support code:AddPhases.
274 void DeleteOldTable(element_t * oldTable);
276 // Utility function that does not call code:CheckGrowth.
277 // Add an element to the hash table. This will never replace an element; multiple
278 // elements may be stored with the same key.
279 void Add_GrowthChecked(const element_t & element);
281 // Utility function to add a new element to the hash table. Note that
282 // it is perfectly fine for the element to be a duplicate - if so it
283 // is added an additional time. Returns TRUE if a new empty spot was used;
284 // FALSE if an existing deleted slot.
285 static BOOL Add(element_t *table, count_t tableSize, const element_t &element);
287 // Utility function to add a new element to the hash table, if no element with the same key
288 // is already there. Otherwise, it will replace the existing element. This has the effect of
289 // updating an element rather than adding a duplicate.
290 void AddOrReplace(element_t *table, count_t tableSize, const element_t &element);
292 // Utility function to find the first element with the given key in
295 static const element_t* Lookup(PTR_element_t table, count_t tableSize, key_t key);
297 // Utility function to remove the first element with the given key
298 // in the hash table.
300 void Remove(element_t *table, count_t tableSize, key_t key);
302 // Utility function to remove the specific element.
304 void RemoveElement(element_t *table, count_t tableSize, element_t *element);
306 // Index for whole table iterator. This is also the base for the keyed iterator.
312 // CheckedIteratorBase is a no-op in RET builds. having it as an empty base-class
313 // causes differences in the sizeof(SHash::Iterator) in DAC vs. non-DAC builds.
314 // avoid the issue by not specifying it as a base class in RET builds
315 : public CheckedIteratorBase< SHash<TRAITS> >
319 friend class Iterator;
320 friend class Enumerator<const element_t, Iterator>;
322 // The methods implementation has to be here for portability
323 // Some compilers won't compile the separate implementation in shash.inl
326 PTR_element_t m_table;
331 Index(const SHash *hash, BOOL begin)
332 : m_table(hash->m_table),
333 m_tableSize(hash->m_tableSize),
334 m_index(begin ? 0 : m_tableSize)
336 LIMITED_METHOD_CONTRACT;
339 const element_t &Get() const
341 LIMITED_METHOD_CONTRACT;
343 return m_table[m_index];
348 LIMITED_METHOD_CONTRACT;
350 if (m_index < m_tableSize)
351 if (TRAITS::IsNull(m_table[m_index]) || TRAITS::IsDeleted(m_table[m_index]))
357 LIMITED_METHOD_CONTRACT;
359 if (m_index >= m_tableSize)
365 if (m_index >= m_tableSize)
367 if (!TRAITS::IsNull(m_table[m_index]) && !TRAITS::IsDeleted(m_table[m_index]))
372 bool Equal(const Index &i) const
374 LIMITED_METHOD_CONTRACT;
376 return i.m_index == m_index;
379 CHECK DoCheck() const
385 class Iterator : public Index, public Enumerator<const element_t, Iterator>
390 Iterator(const SHash *hash, BOOL begin)
396 // Index for iterating elements with a given key.
398 // Note that the m_index field
399 // is artificially bumped to m_tableSize when the end of iteration is reached.
400 // This allows a canonical End iterator to be used.
402 class KeyIndex : public Index
405 friend class KeyIterator;
406 friend class Enumerator<const element_t, KeyIterator>;
408 // The methods implementation has to be here for portability
409 // Some compilers won't compile the separate implementation in shash.inl
414 KeyIndex(const SHash *hash, BOOL begin)
415 : Index(hash, begin),
418 LIMITED_METHOD_CONTRACT;
421 void SetKey(key_t key)
423 LIMITED_METHOD_CONTRACT;
425 if (Index::m_tableSize > 0)
428 count_t hash = TRAITS::Hash(key);
430 this->m_index = hash % this->m_tableSize;
431 m_increment = (hash % (this->m_tableSize-1)) + 1;
433 // Find first valid element
434 if (TRAITS::IsNull(this->m_table[this->m_index]))
435 this->m_index = this->m_tableSize;
436 else if (TRAITS::IsDeleted(this->m_table[this->m_index])
437 || !TRAITS::Equals(m_key, TRAITS::GetKey(this->m_table[this->m_index])))
444 LIMITED_METHOD_CONTRACT;
448 this->m_index += m_increment;
449 if (this->m_index >= this->m_tableSize)
450 this->m_index -= this->m_tableSize;
452 if (TRAITS::IsNull(this->m_table[this->m_index]))
454 this->m_index = this->m_tableSize;
458 if (!TRAITS::IsDeleted(this->m_table[this->m_index])
459 && TRAITS::Equals(m_key, TRAITS::GetKey(this->m_table[this->m_index])))
467 class KeyIterator : public KeyIndex, public Enumerator<const element_t, KeyIterator>
473 operator Iterator &()
475 return *(Iterator*)this;
478 operator const Iterator &()
480 return *(const Iterator*)this;
483 KeyIterator(const SHash *hash, BOOL begin)
484 : KeyIndex(hash, begin)
489 // Wrapper and holder for adding an element to the hash table. Useful for Add operations that have to happen
490 // under a rare lock that does not allow call out into host.
491 // There are 3 phases:
492 // 1. code:PreallocateForAdd ... Can allocate memory (calls into host).
493 // 2. code:Add ... Adds one element (does NOT call into host).
494 // or code:AddNothing_PublishPreallocatedTable ... Publishes the pre-allocated memory from step #1 (if any).
495 // 3. code:DeleteOldTable (or destructor) ... Can delete the old memory (calls into host).
497 // CrstHolder lockAdd(&crstLockForAdd); // Serialize all Add operations.
498 // HostAssemblyMap::AddPhases addCall;
499 // addCall.PreallocateForAdd(&shash); // 1. Allocates memory for one Add call (if needed). addCall serves as holder for the allocated memory.
501 // // We cannot call out into host from ForbidSuspend region (i.e. no allocations/deallocations).
502 // ForbidSuspendThreadHolder suspend; // Required by the 'special' read-lock
504 // CrstHolder lock(&crstLock);
505 // if (some_condition)
506 // { // 2a. Add item. This may replace SHash inner table with the one pre-allocated in step 1.
507 // addCall.Add(shashItem);
510 // { // 2b. Skip adding item. This may replace SHash inner table with the one pre-allocated in step 1.
511 // addCall.AddNothing_PublishPreallocatedTable();
515 // addCall.DeleteOldTable(); // 3. Cleanup old table memory from shash (if it was replaced by pre-allocated table in step 2).
516 // // Note: addCall destructor would take care of deleting the memory as well.
523 // Prepares object for one call to code:Add. Pre-allocates new table memory if needed, does not publish
524 // the table yet (it is kept ready only in this holder for call to code:Add).
525 // Calls out into host.
526 void PreallocateForAdd(SHash * pHash);
528 // Add an element to the hash table. This will never replace an element; multiple elements may be stored
529 // with the same key.
530 // Will use/publish pre-allocated memory from code:PreallocateForAdd.
531 // Does not call out into host.
532 // Only one Add* method can be called once per object! (Create a new object for each call)
533 void Add(const element_t & element);
535 // Element will not be added to the hash table.
536 // Will use/publish pre-allocated memory from code:PreallocateForAdd.
537 // Does not call out into host.
538 // Only one Add* method can be called once per object! (Create a new object for each call)
539 void AddNothing_PublishPreallocatedTable();
541 // Deletes old table if it was replaced by call to code:Add or code:AddNothing_PublishPreallocatedTable.
542 // Calls out into host.
543 void DeleteOldTable();
547 element_t * m_newTable;
548 count_t m_newTableSize;
549 element_t * m_oldTable;
552 PTR_element_t dbg_m_table;
553 count_t dbg_m_tableSize;
554 count_t dbg_m_tableCount;
555 count_t dbg_m_tableOccupied;
556 count_t dbg_m_tableMax;
557 BOOL dbg_m_fAddCalled;
559 }; // class SHash::AddPhases
561 // Adds an entry to the hash table according to the guidelines above for
562 // avoiding a callout to the host while the read lock is held.
563 // Returns true if elem was added to the map, otherwise false.
564 // When elem was not added (false is returned), and if ppStoredElem is non-null,
565 // then it is set to point to the value in the map.
566 template <typename LockHolderT,
567 typename AddLockHolderT,
570 bool CheckAddInPhases(
571 element_t const & elem,
574 IUnknown * addRefObject = nullptr);
578 // Test for prime number.
579 static BOOL IsPrime(COUNT_T number);
581 // Find the next prime number >= the given value.
583 static COUNT_T NextPrime(COUNT_T number);
587 PTR_element_t m_table; // pointer to table
588 count_t m_tableSize; // allocated size of table
589 count_t m_tableCount; // number of elements in table
590 count_t m_tableOccupied; // number, includes deleted slots
591 count_t m_tableMax; // maximum occupied count before reallocating
594 // disables support for DAC marshaling. Useful for defining right-side only SHashes
595 template <typename PARENT>
596 class NonDacAwareSHashTraits : public PARENT
599 typedef typename PARENT::element_t element_t;
600 typedef element_t * PTR_element_t;
603 // disables support for removing elements - produces slightly faster implementation
605 template <typename PARENT>
606 class NoRemoveSHashTraits : public PARENT
609 // explicitly declare local typedefs for these traits types, otherwise
610 // the compiler may get confused
611 typedef typename PARENT::element_t element_t;
612 typedef typename PARENT::count_t count_t;
614 static const bool s_supports_remove = false;
615 static const element_t Deleted() { UNREACHABLE(); }
616 static bool IsDeleted(const element_t &e) { LIMITED_METHOD_DAC_CONTRACT; return false; }
619 // PtrHashTraits is a template to provides useful defaults for pointer hash tables
620 // It relies on methods GetKey and Hash defined on ELEMENT
622 template <typename ELEMENT, typename KEY>
623 class PtrSHashTraits : public DefaultSHashTraits<ELEMENT *>
627 // explicitly declare local typedefs for these traits types, otherwise
628 // the compiler may get confused
629 typedef DefaultSHashTraits<ELEMENT *> PARENT;
630 typedef typename PARENT::element_t element_t;
631 typedef typename PARENT::count_t count_t;
635 static key_t GetKey(const element_t &e)
640 static BOOL Equals(key_t k1, key_t k2)
642 LIMITED_METHOD_CONTRACT;
645 static count_t Hash(key_t k)
648 return ELEMENT::Hash(k);
652 template <typename ELEMENT, typename KEY>
653 class PtrSHash : public SHash< PtrSHashTraits<ELEMENT, KEY> >
657 template <typename ELEMENT, typename KEY>
658 class PtrSHashWithCleanupTraits
659 : public PtrSHashTraits<ELEMENT, KEY>
662 void OnDestructPerEntryCleanupAction(ELEMENT * elem)
666 static const bool s_DestructPerEntryCleanupAction = true;
669 // a class that automatically deletes data referenced by the pointers (so effectively it takes ownership of the data)
670 // since I was too lazy to implement Remove() APIs properly, removing entries is disallowed
671 template <typename ELEMENT, typename KEY>
672 class PtrSHashWithCleanup : public SHash< NoRemoveSHashTraits< PtrSHashWithCleanupTraits<ELEMENT, KEY> > >
676 // Provides case-sensitive comparison and hashing functionality through static
677 // and functor object methods. Can be instantiated with CHAR or WCHAR.
678 template <typename CharT>
679 struct CaseSensitiveStringCompareHash
682 typedef CharT const * str_t;
684 static size_t _strcmp(CHAR const *left, CHAR const *right)
686 return ::strcmp(left, right);
689 static size_t _strcmp(WCHAR const *left, WCHAR const *right)
691 return ::wcscmp(left, right);
694 static size_t _hash(CHAR const *str)
696 return HashStringA(str);
699 static size_t _hash(WCHAR const *str)
701 return HashString(str);
705 static size_t compare(str_t left, str_t right)
707 return _strcmp(left, right);
710 size_t operator()(str_t left, str_t right)
712 return compare(left, right);
715 static size_t hash(str_t str)
720 size_t operator()(str_t str)
726 // Provides case-insensitive comparison and hashing functionality through static
727 // and functor object methods. Can be instantiated with CHAR or WCHAR.
728 template <typename CharT>
729 struct CaseInsensitiveStringCompareHash
732 typedef CharT const * str_t;
734 static size_t _strcmp(str_t left, str_t right)
736 return ::SString::_tstricmp(left, right);
739 static size_t _hash(CHAR const *str)
741 return HashiStringA(str);
744 static size_t _hash(WCHAR const *str)
746 return HashiString(str);
750 static size_t compare(str_t left, str_t right)
752 return _strcmp(left, right);
755 size_t operator()(str_t left, str_t right)
757 return compare(left, right);
760 static size_t hash(str_t str)
765 size_t operator()(str_t str)
771 // StringSHashTraits is a traits class useful for string-keyed
772 // pointer hash tables.
774 template <typename ElementT, typename CharT, typename ComparerT = CaseSensitiveStringCompareHash<CharT> >
775 class StringSHashTraits : public PtrSHashTraits<ElementT, CharT const *>
778 // explicitly declare local typedefs for these traits types, otherwise
779 // the compiler may get confused
780 typedef PtrSHashTraits<ElementT, CharT const *> PARENT;
781 typedef typename PARENT::element_t element_t;
782 typedef typename PARENT::key_t key_t;
783 typedef typename PARENT::count_t count_t;
785 static BOOL Equals(key_t k1, key_t k2)
787 LIMITED_METHOD_CONTRACT;
789 if (k1 == NULL && k2 == NULL)
791 if (k1 == NULL || k2 == NULL)
793 return ComparerT::compare(k1, k2) == 0;
795 static count_t Hash(key_t k)
797 LIMITED_METHOD_CONTRACT;
802 return (count_t)ComparerT::hash(k);
806 template <typename COMINTERFACE, typename CharT> // Could use IUnknown but would rather take advantage of C++ type checking
807 struct StringHashElement
809 const CharT *GetKey()
814 COMINTERFACE *Object;
818 template <typename COMINTERFACE, typename CharT, typename ComparerT = CaseSensitiveStringCompareHash<CharT> >
819 class StringHashWithCleanupTraits : public StringSHashTraits<StringHashElement<COMINTERFACE, CharT>, CharT, ComparerT>
822 void OnDestructPerEntryCleanupAction(StringHashElement<COMINTERFACE, CharT> * e)
824 if (e->String != NULL)
829 if (e->Object != NULL)
831 e->Object->Release();
834 static const bool s_DestructPerEntryCleanupAction = true;
837 template <typename COMINTERFACE, typename CharT, typename ComparerT = CaseSensitiveStringCompareHash<CharT> >
838 class StringSHashWithCleanup : public SHash< StringHashWithCleanupTraits<COMINTERFACE, CharT, ComparerT> >
842 template <typename ELEMENT>
843 class StringSHash : public SHash< StringSHashTraits<ELEMENT, CHAR> >
847 template <typename ELEMENT>
848 class WStringSHash : public SHash< StringSHashTraits<ELEMENT, WCHAR> >
852 template <typename ELEMENT>
853 class SStringSHashTraits : public PtrSHashTraits<ELEMENT, SString>
856 typedef PtrSHashTraits<ELEMENT, SString> PARENT;
857 typedef typename PARENT::element_t element_t;
858 typedef typename PARENT::key_t key_t;
859 typedef typename PARENT::count_t count_t;
861 static const bool s_NoThrow = false;
863 static BOOL Equals(const key_t &k1, const key_t &k2)
866 return k1.Equals(k2);
868 static count_t Hash(const key_t &k)
875 template <typename ELEMENT>
876 class SStringSHash : public SHash< SStringSHashTraits<ELEMENT> >
880 template <typename ELEMENT>
881 class SetSHashTraits : public DefaultSHashTraits<ELEMENT>
884 // explicitly declare local typedefs for these traits types, otherwise
885 // the compiler may get confused
886 typedef typename DefaultSHashTraits<ELEMENT>::element_t element_t;
887 typedef typename DefaultSHashTraits<ELEMENT>::count_t count_t;
889 typedef ELEMENT key_t;
891 static key_t GetKey(element_t e)
893 LIMITED_METHOD_CONTRACT;
896 static BOOL Equals(key_t k1, key_t k2)
898 LIMITED_METHOD_CONTRACT;
901 static count_t Hash(key_t k)
903 LIMITED_METHOD_CONTRACT;
904 return (count_t)(size_t)k;
908 template <typename ELEMENT, typename TRAITS = NoRemoveSHashTraits< SetSHashTraits <ELEMENT> > >
909 class SetSHash : public SHash< TRAITS >
911 typedef SHash<TRAITS> PARENT;
914 BOOL Contains(ELEMENT key) const
916 return PARENT::LookupPtr(key) != NULL;
920 template <typename ELEMENT>
921 class PtrSetSHashTraits : public SetSHashTraits<ELEMENT>
925 // explicitly declare local typedefs for these traits types, otherwise
926 // the compiler may get confused
927 typedef SetSHashTraits<ELEMENT> PARENT;
928 typedef typename PARENT::element_t element_t;
929 typedef typename PARENT::key_t key_t;
930 typedef typename PARENT::count_t count_t;
932 static count_t Hash(key_t k)
935 return (count_t)(size_t)k >> 2;
939 template <typename PARENT_TRAITS>
940 class DeleteElementsOnDestructSHashTraits : public PARENT_TRAITS
943 static inline void OnDestructPerEntryCleanupAction(typename PARENT_TRAITS::element_t e)
947 static const bool s_DestructPerEntryCleanupAction = true;
950 #if !defined(CC_JIT) // workaround: Key is redefined in JIT64
952 template <typename KEY, typename VALUE>
962 KeyValuePair(const KEY& k, const VALUE& v)
967 KEY const & Key() const
969 LIMITED_METHOD_CONTRACT;
973 VALUE const & Value() const
975 LIMITED_METHOD_CONTRACT;
980 template <typename KEY, typename VALUE>
981 class MapSHashTraits : public DefaultSHashTraits< KeyValuePair<KEY,VALUE> >
984 // explicitly declare local typedefs for these traits types, otherwise
985 // the compiler may get confused
986 typedef typename DefaultSHashTraits< KeyValuePair<KEY,VALUE> >::element_t element_t;
987 typedef typename DefaultSHashTraits< KeyValuePair<KEY,VALUE> >::count_t count_t;
991 static key_t GetKey(element_t e)
993 LIMITED_METHOD_CONTRACT;
996 static BOOL Equals(key_t k1, key_t k2)
998 LIMITED_METHOD_CONTRACT;
1001 static count_t Hash(key_t k)
1003 LIMITED_METHOD_CONTRACT;
1004 return (count_t)(size_t)k;
1007 static const element_t Null() { LIMITED_METHOD_CONTRACT; return element_t(KEY(),VALUE()); }
1008 static const element_t Deleted() { LIMITED_METHOD_CONTRACT; return element_t(KEY(-1), VALUE()); }
1009 static bool IsNull(const element_t &e) { LIMITED_METHOD_CONTRACT; return e.Key() == KEY(); }
1010 static bool IsDeleted(const element_t &e) { return e.Key() == KEY(-1); }
1013 template <typename KEY, typename VALUE, typename TRAITS = NoRemoveSHashTraits< MapSHashTraits <KEY, VALUE> > >
1014 class MapSHash : public SHash< TRAITS >
1016 typedef SHash< TRAITS > PARENT;
1019 void Add(KEY key, VALUE value)
1025 PRECONDITION(key != (KEY)0);
1029 PARENT::Add(KeyValuePair<KEY,VALUE>(key, value));
1032 BOOL Lookup(KEY key, VALUE* pValue) const
1038 PRECONDITION(key != (KEY)0);
1042 const KeyValuePair<KEY,VALUE> *pRet = PARENT::LookupPtr(key);
1046 *pValue = pRet->Value();
1051 template <typename KEY, typename VALUE>
1052 class MapSHashWithRemove : public SHash< MapSHashTraits <KEY, VALUE> >
1054 typedef SHash< MapSHashTraits <KEY, VALUE> > PARENT;
1057 void Add(KEY key, VALUE value)
1063 PRECONDITION(key != (KEY)0 && key != (KEY)-1);
1067 PARENT::Add(KeyValuePair<KEY,VALUE>(key, value));
1070 BOOL Lookup(KEY key, VALUE* pValue) const
1076 PRECONDITION(key != (KEY)0 && key != (KEY)-1);
1080 const KeyValuePair<KEY,VALUE> *pRet = PARENT::LookupPtr(key);
1084 *pValue = pRet->Value();
1088 void Remove(KEY key)
1094 PRECONDITION(key != (KEY)0 && key != (KEY)-1);
1098 PARENT::Remove(key);
1104 #include "shash.inl"