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.
4
5
6#ifndef _SHASH_H_
7#define _SHASH_H_
8
9#include "utilcode.h" // for string hash functions
10#include "clrtypes.h"
11#include "check.h"
12#include "iterator.h"
13
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.
16
17// Synchronization:
18// Synchronization requirements depend on use. There are several properties to take into account:
19//
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)
25
26// Common "gotchas":
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.
33
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:
37//
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.)
44//
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.
48//
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.
53//
54// count_t integral type for counts. Typically inherited by default
55// Traits (COUNT_T).
56//
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.
61//
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.)
66//
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.
75//
76// static void OnDestructPerEntryCleanupAction(ELEMENT& e) Called on every element when in hashtable destructor.
77// s_DestructPerEntryCleanupAction must be set to true if implemented.
78//
79// s_growth_factor_numerator
80// s_growth_factor_denominator Factor to grow allocation (numerator/denominator).
81// Typically inherited from default traits (3/2)
82//
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).
86//
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)
90//
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.
95//
96// s_DestructPerEntryCleanupAction Set to true if OnDestructPerEntryCleanupAction has non-empty implementation.
97//
98// DefaultHashTraits provides defaults for seldomly customized values in traits classes.
99
100template < typename ELEMENT >
101class DefaultSHashTraits
102{
103 public:
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)
109
110 static const COUNT_T s_growth_factor_numerator = 3;
111 static const COUNT_T s_growth_factor_denominator = 2;
112
113 static const COUNT_T s_density_factor_numerator = 3;
114 static const COUNT_T s_density_factor_denominator = 4;
115
116 static const COUNT_T s_minimum_allocation = 7;
117
118 static const bool s_supports_remove = true;
119
120 static ELEMENT Null() { return (const ELEMENT) 0; }
121 static 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; }
124
125 static inline void OnDestructPerEntryCleanupAction(const ELEMENT& e) { /* Do nothing */ }
126 static const bool s_DestructPerEntryCleanupAction = false;
127
128 static const bool s_NoThrow = true;
129
130 // No defaults - must specify:
131 //
132 // typedef key_t;
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);
136};
137
138// Hash table class definition
139
140template <typename TRAITS>
141class SHash : public TRAITS
142 , private noncopyable
143{
144 friend class VerifyLayoutsMD; // verifies class layout doesn't accidentally change
145
146 public:
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;
153
154 class Index;
155 friend class Index;
156 class Iterator;
157
158 class KeyIndex;
159 friend class KeyIndex;
160 class KeyIterator;
161
162 // Constructor/destructor. SHash tables always start out empty, with no
163 // allocation overhead. Call Reallocate to prime with an initial size if
164 // desired.
165
166 SHash();
167
168 ~SHash();
169
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
173 // with a given key.
174
175 element_t Lookup(key_t key) const;
176
177 // Pointer-based flavor of Lookup (allows efficient access to tables of structures)
178
179 const element_t* LookupPtr(key_t key) const;
180
181 // Add an element to the hash table. This will never replace an element; multiple
182 // elements may be stored with the same key.
183
184 void Add(const element_t &element);
185
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);
190
191 // Remove the first element matching the key from the hash table.
192
193 void Remove(key_t key);
194
195 // Remove the specific element.
196
197 void Remove(Iterator& i);
198 void Remove(KeyIterator& i);
199
200 // Pointer-based flavor of Remove (allows efficient access to tables of structures)
201
202 void RemovePtr(element_t * element);
203
204 // Remove all elements in the hashtable
205
206 void RemoveAll();
207
208 // Begin and End pointers for iteration over entire table.
209
210 Iterator Begin() const;
211 Iterator End() const;
212
213 // Begin and End pointers for iteration over all elements with a given key.
214
215 KeyIterator Begin(key_t key) const;
216 KeyIterator End(key_t key) const;
217
218 // Return the number of elements currently stored in the table
219
220 count_t GetCount() const;
221
222 // Resizes a hash table for growth. The new size is computed based
223 // on the current population, growth factor, and maximum density factor.
224
225 void Grow();
226
227 // Reallocates a hash table to a specific size. The size must be big enough
228 // to hold all elements in the table appropriately.
229 //
230 // Note that the actual table size must always be a prime number; the number
231 // passed in will be upward adjusted if necessary.
232
233 void Reallocate(count_t newTableSize);
234
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:
237 //
238 // class Functor
239 // {
240 // public:
241 // void operator() (element_t &element) { ... }
242 // }
243
244 template<typename Functor> void ForEach(Functor &functor);
245
246 private:
247
248 // See if it is OK to grow the hash table by one element. If not, reallocate
249 // the hash table.
250 BOOL CheckGrowth();
251
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);
256
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);
260
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);
265
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);
271
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);
275
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);
280
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);
286
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);
291
292 // Utility function to find the first element with the given key in
293 // the hash table.
294
295 static const element_t* Lookup(PTR_element_t table, count_t tableSize, key_t key);
296
297 // Utility function to remove the first element with the given key
298 // in the hash table.
299
300 void Remove(element_t *table, count_t tableSize, key_t key);
301
302 // Utility function to remove the specific element.
303
304 void RemoveElement(element_t *table, count_t tableSize, element_t *element);
305
306 // Index for whole table iterator. This is also the base for the keyed iterator.
307
308 public:
309
310 class Index
311#ifdef _DEBUG
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> >
316#endif
317 {
318 friend class SHash;
319 friend class Iterator;
320 friend class Enumerator<const element_t, Iterator>;
321
322 // The methods implementation has to be here for portability
323 // Some compilers won't compile the separate implementation in shash.inl
324 protected:
325
326 PTR_element_t m_table;
327 count_t m_tableSize;
328 count_t m_index;
329
330
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)
335 {
336 LIMITED_METHOD_CONTRACT;
337 }
338
339 const element_t &Get() const
340 {
341 LIMITED_METHOD_CONTRACT;
342
343 return m_table[m_index];
344 }
345
346 void First()
347 {
348 LIMITED_METHOD_CONTRACT;
349
350 if (m_index < m_tableSize)
351 if (TRAITS::IsNull(m_table[m_index]) || TRAITS::IsDeleted(m_table[m_index]))
352 Next();
353 }
354
355 void Next()
356 {
357 LIMITED_METHOD_CONTRACT;
358
359 if (m_index >= m_tableSize)
360 return;
361
362 for (;;)
363 {
364 m_index++;
365 if (m_index >= m_tableSize)
366 break;
367 if (!TRAITS::IsNull(m_table[m_index]) && !TRAITS::IsDeleted(m_table[m_index]))
368 break;
369 }
370 }
371
372 bool Equal(const Index &i) const
373 {
374 LIMITED_METHOD_CONTRACT;
375
376 return i.m_index == m_index;
377 }
378
379 CHECK DoCheck() const
380 {
381 CHECK_OK;
382 }
383 };
384
385 class Iterator : public Index, public Enumerator<const element_t, Iterator>
386 {
387 friend class SHash;
388
389 public:
390 Iterator(const SHash *hash, BOOL begin)
391 : Index(hash, begin)
392 {
393 }
394 };
395
396 // Index for iterating elements with a given key.
397 //
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.
401
402 class KeyIndex : public Index
403 {
404 friend class SHash;
405 friend class KeyIterator;
406 friend class Enumerator<const element_t, KeyIterator>;
407
408 // The methods implementation has to be here for portability
409 // Some compilers won't compile the separate implementation in shash.inl
410 protected:
411 key_t m_key;
412 count_t m_increment;
413
414 KeyIndex(const SHash *hash, BOOL begin)
415 : Index(hash, begin),
416 m_increment(0)
417 {
418 LIMITED_METHOD_CONTRACT;
419 }
420
421 void SetKey(key_t key)
422 {
423 LIMITED_METHOD_CONTRACT;
424
425 if (Index::m_tableSize > 0)
426 {
427 m_key = key;
428 count_t hash = TRAITS::Hash(key);
429
430 this->m_index = hash % this->m_tableSize;
431 m_increment = (hash % (this->m_tableSize-1)) + 1;
432
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])))
438 Next();
439 }
440 }
441
442 void Next()
443 {
444 LIMITED_METHOD_CONTRACT;
445
446 while (TRUE)
447 {
448 this->m_index += m_increment;
449 if (this->m_index >= this->m_tableSize)
450 this->m_index -= this->m_tableSize;
451
452 if (TRAITS::IsNull(this->m_table[this->m_index]))
453 {
454 this->m_index = this->m_tableSize;
455 break;
456 }
457
458 if (!TRAITS::IsDeleted(this->m_table[this->m_index])
459 && TRAITS::Equals(m_key, TRAITS::GetKey(this->m_table[this->m_index])))
460 {
461 break;
462 }
463 }
464 }
465 };
466
467 class KeyIterator : public KeyIndex, public Enumerator<const element_t, KeyIterator>
468 {
469 friend class SHash;
470
471 public:
472
473 operator Iterator &()
474 {
475 return *(Iterator*)this;
476 }
477
478 operator const Iterator &()
479 {
480 return *(const Iterator*)this;
481 }
482
483 KeyIterator(const SHash *hash, BOOL begin)
484 : KeyIndex(hash, begin)
485 {
486 }
487 };
488
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).
496 // Example:
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.
500 // {
501 // // We cannot call out into host from ForbidSuspend region (i.e. no allocations/deallocations).
502 // ForbidSuspendThreadHolder suspend; // Required by the 'special' read-lock
503 // {
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);
508 // }
509 // else
510 // { // 2b. Skip adding item. This may replace SHash inner table with the one pre-allocated in step 1.
511 // addCall.AddNothing_PublishPreallocatedTable();
512 // }
513 // }
514 // }
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.
517 class AddPhases
518 {
519 public:
520 AddPhases();
521 ~AddPhases();
522
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);
527
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);
534
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();
540
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();
544
545 private:
546 SHash * m_pHash;
547 element_t * m_newTable;
548 count_t m_newTableSize;
549 element_t * m_oldTable;
550
551 #ifdef _DEBUG
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;
558 #endif //_DEBUG
559 }; // class SHash::AddPhases
560
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,
568 typename LockT,
569 typename AddLockT>
570 bool CheckAddInPhases(
571 element_t const & elem,
572 LockT & lock,
573 AddLockT & addLock,
574 IUnknown * addRefObject = nullptr);
575
576 private:
577
578 // Test for prime number.
579 static BOOL IsPrime(COUNT_T number);
580
581 // Find the next prime number >= the given value.
582
583 static COUNT_T NextPrime(COUNT_T number);
584
585 // Instance members
586
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
592}; // class SHash
593
594// disables support for DAC marshaling. Useful for defining right-side only SHashes
595template <typename PARENT>
596class NonDacAwareSHashTraits : public PARENT
597{
598public:
599 typedef typename PARENT::element_t element_t;
600 typedef element_t * PTR_element_t;
601};
602
603// disables support for removing elements - produces slightly faster implementation
604
605template <typename PARENT>
606class NoRemoveSHashTraits : public PARENT
607{
608public:
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;
613
614 static const bool s_supports_remove = false;
615 static element_t Deleted() { UNREACHABLE(); }
616 static bool IsDeleted(const element_t &e) { LIMITED_METHOD_DAC_CONTRACT; return false; }
617};
618
619// PtrHashTraits is a template to provides useful defaults for pointer hash tables
620// It relies on methods GetKey and Hash defined on ELEMENT
621
622template <typename ELEMENT, typename KEY>
623class PtrSHashTraits : public DefaultSHashTraits<ELEMENT *>
624{
625 public:
626
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;
632
633 typedef KEY key_t;
634
635 static key_t GetKey(const element_t &e)
636 {
637 WRAPPER_NO_CONTRACT;
638 return e->GetKey();
639 }
640 static BOOL Equals(key_t k1, key_t k2)
641 {
642 LIMITED_METHOD_CONTRACT;
643 return k1 == k2;
644 }
645 static count_t Hash(key_t k)
646 {
647 WRAPPER_NO_CONTRACT;
648 return ELEMENT::Hash(k);
649 }
650};
651
652template <typename ELEMENT, typename KEY>
653class PtrSHash : public SHash< PtrSHashTraits<ELEMENT, KEY> >
654{
655};
656
657template <typename ELEMENT, typename KEY>
658class PtrSHashWithCleanupTraits
659 : public PtrSHashTraits<ELEMENT, KEY>
660{
661public:
662 void OnDestructPerEntryCleanupAction(ELEMENT * elem)
663 {
664 delete elem;
665 }
666 static const bool s_DestructPerEntryCleanupAction = true;
667};
668
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
671template <typename ELEMENT, typename KEY>
672class PtrSHashWithCleanup : public SHash< NoRemoveSHashTraits< PtrSHashWithCleanupTraits<ELEMENT, KEY> > >
673{
674};
675
676// Provides case-sensitive comparison and hashing functionality through static
677// and functor object methods. Can be instantiated with CHAR or WCHAR.
678template <typename CharT>
679struct CaseSensitiveStringCompareHash
680{
681private:
682 typedef CharT const * str_t;
683
684 static size_t _strcmp(CHAR const *left, CHAR const *right)
685 {
686 return ::strcmp(left, right);
687 }
688
689 static size_t _strcmp(WCHAR const *left, WCHAR const *right)
690 {
691 return ::wcscmp(left, right);
692 }
693
694 static size_t _hash(CHAR const *str)
695 {
696 return HashStringA(str);
697 }
698
699 static size_t _hash(WCHAR const *str)
700 {
701 return HashString(str);
702 }
703
704public:
705 static size_t compare(str_t left, str_t right)
706 {
707 return _strcmp(left, right);
708 }
709
710 size_t operator()(str_t left, str_t right)
711 {
712 return compare(left, right);
713 }
714
715 static size_t hash(str_t str)
716 {
717 return _hash(str);
718 }
719
720 size_t operator()(str_t str)
721 {
722 return hash(str);
723 }
724};
725
726// Provides case-insensitive comparison and hashing functionality through static
727// and functor object methods. Can be instantiated with CHAR or WCHAR.
728template <typename CharT>
729struct CaseInsensitiveStringCompareHash
730{
731private:
732 typedef CharT const * str_t;
733
734 static size_t _strcmp(str_t left, str_t right)
735 {
736 return ::SString::_tstricmp(left, right);
737 }
738
739 static size_t _hash(CHAR const *str)
740 {
741 return HashiStringA(str);
742 }
743
744 static size_t _hash(WCHAR const *str)
745 {
746 return HashiString(str);
747 }
748
749public:
750 static size_t compare(str_t left, str_t right)
751 {
752 return _strcmp(left, right);
753 }
754
755 size_t operator()(str_t left, str_t right)
756 {
757 return compare(left, right);
758 }
759
760 static size_t hash(str_t str)
761 {
762 return _hash(str);
763 }
764
765 size_t operator()(str_t str)
766 {
767 return hash(str);
768 }
769};
770
771// StringSHashTraits is a traits class useful for string-keyed
772// pointer hash tables.
773
774template <typename ElementT, typename CharT, typename ComparerT = CaseSensitiveStringCompareHash<CharT> >
775class StringSHashTraits : public PtrSHashTraits<ElementT, CharT const *>
776{
777public:
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;
784
785 static BOOL Equals(key_t k1, key_t k2)
786 {
787 LIMITED_METHOD_CONTRACT;
788
789 if (k1 == NULL && k2 == NULL)
790 return TRUE;
791 if (k1 == NULL || k2 == NULL)
792 return FALSE;
793 return ComparerT::compare(k1, k2) == 0;
794 }
795 static count_t Hash(key_t k)
796 {
797 LIMITED_METHOD_CONTRACT;
798
799 if (k == NULL)
800 return 0;
801 else
802 return (count_t)ComparerT::hash(k);
803 }
804};
805
806template <typename COMINTERFACE, typename CharT> // Could use IUnknown but would rather take advantage of C++ type checking
807struct StringHashElement
808{
809 const CharT *GetKey()
810 {
811 return String;
812 }
813
814 COMINTERFACE *Object;
815 CharT *String;
816};
817
818template <typename COMINTERFACE, typename CharT, typename ComparerT = CaseSensitiveStringCompareHash<CharT> >
819class StringHashWithCleanupTraits : public StringSHashTraits<StringHashElement<COMINTERFACE, CharT>, CharT, ComparerT>
820{
821public:
822 void OnDestructPerEntryCleanupAction(StringHashElement<COMINTERFACE, CharT> * e)
823 {
824 if (e->String != NULL)
825 {
826 delete[] e->String;
827 }
828
829 if (e->Object != NULL)
830 {
831 e->Object->Release();
832 }
833 }
834 static const bool s_DestructPerEntryCleanupAction = true;
835};
836
837template <typename COMINTERFACE, typename CharT, typename ComparerT = CaseSensitiveStringCompareHash<CharT> >
838class StringSHashWithCleanup : public SHash< StringHashWithCleanupTraits<COMINTERFACE, CharT, ComparerT> >
839{
840};
841
842template <typename ELEMENT>
843class StringSHash : public SHash< StringSHashTraits<ELEMENT, CHAR> >
844{
845};
846
847template <typename ELEMENT>
848class WStringSHash : public SHash< StringSHashTraits<ELEMENT, WCHAR> >
849{
850};
851
852template <typename ELEMENT>
853class SStringSHashTraits : public PtrSHashTraits<ELEMENT, SString>
854{
855 public:
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;
860
861 static const bool s_NoThrow = false;
862
863 static BOOL Equals(const key_t &k1, const key_t &k2)
864 {
865 WRAPPER_NO_CONTRACT;
866 return k1.Equals(k2);
867 }
868 static count_t Hash(const key_t &k)
869 {
870 WRAPPER_NO_CONTRACT;
871 return k.Hash();
872 }
873};
874
875template <typename ELEMENT>
876class SStringSHash : public SHash< SStringSHashTraits<ELEMENT> >
877{
878};
879
880template <typename ELEMENT>
881class SetSHashTraits : public DefaultSHashTraits<ELEMENT>
882{
883public:
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;
888
889 typedef ELEMENT key_t;
890
891 static key_t GetKey(element_t e)
892 {
893 LIMITED_METHOD_CONTRACT;
894 return e;
895 }
896 static BOOL Equals(key_t k1, key_t k2)
897 {
898 LIMITED_METHOD_CONTRACT;
899 return k1 == k2;
900 }
901 static count_t Hash(key_t k)
902 {
903 LIMITED_METHOD_CONTRACT;
904 return (count_t)(size_t)k;
905 }
906};
907
908template <typename ELEMENT, typename TRAITS = NoRemoveSHashTraits< SetSHashTraits <ELEMENT> > >
909class SetSHash : public SHash< TRAITS >
910{
911 typedef SHash<TRAITS> PARENT;
912
913public:
914 BOOL Contains(ELEMENT key) const
915 {
916 return PARENT::LookupPtr(key) != NULL;
917 }
918};
919
920template <typename ELEMENT>
921class PtrSetSHashTraits : public SetSHashTraits<ELEMENT>
922{
923 public:
924
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;
931
932 static count_t Hash(key_t k)
933 {
934 WRAPPER_NO_CONTRACT;
935 return (count_t)(size_t)k >> 2;
936 }
937};
938
939template <typename PARENT_TRAITS>
940class DeleteElementsOnDestructSHashTraits : public PARENT_TRAITS
941{
942public:
943 static inline void OnDestructPerEntryCleanupAction(typename PARENT_TRAITS::element_t e)
944 {
945 delete e;
946 }
947 static const bool s_DestructPerEntryCleanupAction = true;
948};
949
950#if !defined(CC_JIT) // workaround: Key is redefined in JIT64
951
952template <typename KEY, typename VALUE>
953class KeyValuePair {
954 KEY key;
955 VALUE value;
956
957public:
958 KeyValuePair()
959 {
960 }
961
962 KeyValuePair(const KEY& k, const VALUE& v)
963 : key(k), value(v)
964 {
965 }
966
967 KEY const & Key() const
968 {
969 LIMITED_METHOD_CONTRACT;
970 return key;
971 }
972
973 VALUE const & Value() const
974 {
975 LIMITED_METHOD_CONTRACT;
976 return value;
977 }
978};
979
980template <typename KEY, typename VALUE>
981class MapSHashTraits : public DefaultSHashTraits< KeyValuePair<KEY,VALUE> >
982{
983public:
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;
988
989 typedef KEY key_t;
990
991 static key_t GetKey(element_t e)
992 {
993 LIMITED_METHOD_CONTRACT;
994 return e.Key();
995 }
996 static BOOL Equals(key_t k1, key_t k2)
997 {
998 LIMITED_METHOD_CONTRACT;
999 return k1 == k2;
1000 }
1001 static count_t Hash(key_t k)
1002 {
1003 LIMITED_METHOD_CONTRACT;
1004 return (count_t)(size_t)k;
1005 }
1006
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); }
1011};
1012
1013template <typename KEY, typename VALUE, typename TRAITS = NoRemoveSHashTraits< MapSHashTraits <KEY, VALUE> > >
1014class MapSHash : public SHash< TRAITS >
1015{
1016 typedef SHash< TRAITS > PARENT;
1017
1018public:
1019 void Add(KEY key, VALUE value)
1020 {
1021 CONTRACTL
1022 {
1023 THROWS;
1024 GC_NOTRIGGER;
1025 PRECONDITION(key != (KEY)0);
1026 }
1027 CONTRACTL_END;
1028
1029 PARENT::Add(KeyValuePair<KEY,VALUE>(key, value));
1030 }
1031
1032 BOOL Lookup(KEY key, VALUE* pValue) const
1033 {
1034 CONTRACTL
1035 {
1036 NOTHROW;
1037 GC_NOTRIGGER;
1038 PRECONDITION(key != (KEY)0);
1039 }
1040 CONTRACTL_END;
1041
1042 const KeyValuePair<KEY,VALUE> *pRet = PARENT::LookupPtr(key);
1043 if (pRet == NULL)
1044 return FALSE;
1045
1046 *pValue = pRet->Value();
1047 return TRUE;
1048 }
1049};
1050
1051template <typename KEY, typename VALUE>
1052class MapSHashWithRemove : public SHash< MapSHashTraits <KEY, VALUE> >
1053{
1054 typedef SHash< MapSHashTraits <KEY, VALUE> > PARENT;
1055
1056public:
1057 void Add(KEY key, VALUE value)
1058 {
1059 CONTRACTL
1060 {
1061 THROWS;
1062 GC_NOTRIGGER;
1063 PRECONDITION(key != (KEY)0 && key != (KEY)-1);
1064 }
1065 CONTRACTL_END;
1066
1067 PARENT::Add(KeyValuePair<KEY,VALUE>(key, value));
1068 }
1069
1070 BOOL Lookup(KEY key, VALUE* pValue) const
1071 {
1072 CONTRACTL
1073 {
1074 NOTHROW;
1075 GC_NOTRIGGER;
1076 PRECONDITION(key != (KEY)0 && key != (KEY)-1);
1077 }
1078 CONTRACTL_END;
1079
1080 const KeyValuePair<KEY,VALUE> *pRet = PARENT::LookupPtr(key);
1081 if (pRet == NULL)
1082 return FALSE;
1083
1084 *pValue = pRet->Value();
1085 return TRUE;
1086 }
1087
1088 void Remove(KEY key)
1089 {
1090 CONTRACTL
1091 {
1092 NOTHROW;
1093 GC_NOTRIGGER;
1094 PRECONDITION(key != (KEY)0 && key != (KEY)-1);
1095 }
1096 CONTRACTL_END;
1097
1098 PARENT::Remove(key);
1099 }
1100};
1101
1102#endif // CC_JIT
1103
1104#include "shash.inl"
1105
1106#endif // _SHASH_H_
1107