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#ifndef _SHASH_INL_
6#define _SHASH_INL_
7
8// Many SHash functions do not throw on their own, but may propagate an exception
9// from Hash, Equals, or GetKey.
10#define NOTHROW_UNLESS_TRAITS_THROWS if (TRAITS::s_NoThrow) NOTHROW; else THROWS
11
12void DECLSPEC_NORETURN ThrowOutOfMemory();
13
14template <typename TRAITS>
15SHash<TRAITS>::SHash()
16 : m_table(nullptr),
17 m_tableSize(0),
18 m_tableCount(0),
19 m_tableOccupied(0),
20 m_tableMax(0)
21{
22 LIMITED_METHOD_CONTRACT;
23
24#ifndef __GNUC__ // these crash GCC
25 static_assert_no_msg(SHash<TRAITS>::s_growth_factor_numerator > SHash<TRAITS>::s_growth_factor_denominator);
26 static_assert_no_msg(SHash<TRAITS>::s_density_factor_numerator < SHash<TRAITS>::s_density_factor_denominator);
27#endif
28}
29
30template <typename TRAITS>
31SHash<TRAITS>::~SHash()
32{
33 LIMITED_METHOD_CONTRACT;
34
35 if (TRAITS::s_DestructPerEntryCleanupAction)
36 {
37 for (Iterator i = Begin(); i != End(); i++)
38 {
39 TRAITS::OnDestructPerEntryCleanupAction(*i);
40 }
41 }
42
43 delete [] m_table;
44}
45
46template <typename TRAITS>
47typename SHash<TRAITS>::count_t SHash<TRAITS>::GetCount() const
48{
49 LIMITED_METHOD_CONTRACT;
50
51 return m_tableCount;
52}
53
54template <typename TRAITS>
55typename SHash<TRAITS>::element_t SHash<TRAITS>::Lookup(key_t key) const
56{
57 CONTRACT(element_t)
58 {
59 NOTHROW_UNLESS_TRAITS_THROWS;
60 GC_NOTRIGGER;
61 INSTANCE_CHECK;
62 POSTCONDITION(TRAITS::IsNull(RETVAL) || TRAITS::Equals(key, TRAITS::GetKey(RETVAL)));
63 SUPPORTS_DAC_WRAPPER;
64 }
65 CONTRACT_END;
66
67 const element_t *pRet = Lookup(m_table, m_tableSize, key);
68 RETURN ((pRet != NULL) ? (*pRet) : TRAITS::Null());
69}
70
71template <typename TRAITS>
72const typename SHash<TRAITS>::element_t * SHash<TRAITS>::LookupPtr(key_t key) const
73{
74 CONTRACT(const element_t *)
75 {
76 NOTHROW_UNLESS_TRAITS_THROWS;
77 GC_NOTRIGGER;
78 INSTANCE_CHECK;
79 POSTCONDITION(RETVAL == NULL || TRAITS::Equals(key, TRAITS::GetKey(*RETVAL)));
80 }
81 CONTRACT_END;
82
83 RETURN Lookup(m_table, m_tableSize, key);
84}
85
86template <typename TRAITS>
87void SHash<TRAITS>::Add(const element_t & element)
88{
89 CONTRACT_VOID
90 {
91 THROWS;
92 GC_NOTRIGGER;
93 INSTANCE_CHECK;
94 POSTCONDITION(TRAITS::Equals(TRAITS::GetKey(element), TRAITS::GetKey(*LookupPtr(TRAITS::GetKey(element)))));
95 }
96 CONTRACT_END;
97
98 CheckGrowth();
99
100 Add_GrowthChecked(element);
101
102 RETURN;
103}
104
105template <typename TRAITS>
106void SHash<TRAITS>::Add_GrowthChecked(const element_t & element)
107{
108 CONTRACT_VOID
109 {
110 NOTHROW_UNLESS_TRAITS_THROWS;
111 GC_NOTRIGGER;
112 INSTANCE_CHECK;
113 POSTCONDITION(TRAITS::Equals(TRAITS::GetKey(element), TRAITS::GetKey(*LookupPtr(TRAITS::GetKey(element)))));
114 }
115 CONTRACT_END;
116
117 if (Add(m_table, m_tableSize, element))
118 m_tableOccupied++;
119 m_tableCount++;
120
121 RETURN;
122}
123
124template <typename TRAITS>
125void SHash<TRAITS>::AddOrReplace(const element_t &element)
126{
127 CONTRACT_VOID
128 {
129 THROWS;
130 GC_NOTRIGGER;
131 INSTANCE_CHECK;
132 static_assert(!TRAITS::s_supports_remove, "SHash::AddOrReplace is not implemented for SHash with support for remove operations.");
133 POSTCONDITION(TRAITS::Equals(TRAITS::GetKey(element), TRAITS::GetKey(*LookupPtr(TRAITS::GetKey(element)))));
134 }
135 CONTRACT_END;
136
137 CheckGrowth();
138
139 AddOrReplace(m_table, m_tableSize, element);
140
141 RETURN;
142}
143
144template <typename TRAITS>
145void SHash<TRAITS>::Remove(key_t key)
146{
147 CONTRACT_VOID
148 {
149 NOTHROW_UNLESS_TRAITS_THROWS;
150 GC_NOTRIGGER;
151 INSTANCE_CHECK;
152 static_assert(TRAITS::s_supports_remove, "This SHash does not support remove operations.");
153 PRECONDITION(!(TRAITS::IsNull(Lookup(key))));
154 }
155 CONTRACT_END;
156
157 Remove(m_table, m_tableSize, key);
158
159 RETURN;
160}
161
162template <typename TRAITS>
163void SHash<TRAITS>::Remove(Iterator& i)
164{
165 CONTRACT_VOID
166 {
167 NOTHROW;
168 GC_NOTRIGGER;
169 INSTANCE_CHECK;
170 static_assert(TRAITS::s_supports_remove, "This SHash does not support remove operations.");
171 PRECONDITION(!(TRAITS::IsNull(*i)));
172 PRECONDITION(!(TRAITS::IsDeleted(*i)));
173 }
174 CONTRACT_END;
175
176 RemoveElement(m_table, m_tableSize, (element_t*)&(*i));
177
178 RETURN;
179}
180
181template <typename TRAITS>
182void SHash<TRAITS>::Remove(KeyIterator& i)
183{
184 CONTRACT_VOID
185 {
186 NOTHROW;
187 GC_NOTRIGGER;
188 INSTANCE_CHECK;
189 static_assert(TRAITS::s_supports_remove, "This SHash does not support remove operations.");
190 PRECONDITION(!(TRAITS::IsNull(*i)));
191 PRECONDITION(!(TRAITS::IsDeleted(*i)));
192 }
193 CONTRACT_END;
194
195 RemoveElement(m_table, m_tableSize, (element_t*)&(*i));
196
197 RETURN;
198}
199
200template <typename TRAITS>
201void SHash<TRAITS>::RemovePtr(element_t * p)
202{
203 CONTRACT_VOID
204 {
205 NOTHROW;
206 GC_NOTRIGGER;
207 INSTANCE_CHECK;
208 static_assert(TRAITS::s_supports_remove, "This SHash does not support remove operations.");
209 PRECONDITION(!(TRAITS::IsNull(*p)));
210 PRECONDITION(!(TRAITS::IsDeleted(*p)));
211 }
212 CONTRACT_END;
213
214 RemoveElement(m_table, m_tableSize, p);
215
216 RETURN;
217}
218
219template <typename TRAITS>
220void SHash<TRAITS>::RemoveAll()
221{
222 CONTRACT_VOID
223 {
224 NOTHROW;
225 GC_NOTRIGGER;
226 INSTANCE_CHECK;
227 }
228 CONTRACT_END;
229
230 delete [] m_table;
231
232 m_table = NULL;
233 m_tableSize = 0;
234 m_tableCount = 0;
235 m_tableOccupied = 0;
236 m_tableMax = 0;
237
238 RETURN;
239}
240
241template <typename TRAITS>
242typename SHash<TRAITS>::Iterator SHash<TRAITS>::Begin() const
243{
244 LIMITED_METHOD_CONTRACT;
245
246 Iterator i(this, TRUE);
247 i.First();
248 return i;
249}
250
251template <typename TRAITS>
252typename SHash<TRAITS>::Iterator SHash<TRAITS>::End() const
253{
254 LIMITED_METHOD_CONTRACT;
255
256 return Iterator(this, FALSE);
257}
258
259template <typename TRAITS>
260typename SHash<TRAITS>::KeyIterator SHash<TRAITS>::Begin(key_t key) const
261{
262 LIMITED_METHOD_CONTRACT;
263
264 KeyIterator k(this, TRUE);
265 k.SetKey(key);
266 return k;
267}
268
269template <typename TRAITS>
270typename SHash<TRAITS>::KeyIterator SHash<TRAITS>::End(key_t key) const
271{
272 LIMITED_METHOD_CONTRACT;
273
274 return KeyIterator(this, FALSE);
275}
276
277template <typename TRAITS>
278BOOL SHash<TRAITS>::CheckGrowth()
279{
280 CONTRACT(BOOL)
281 {
282 THROWS;
283 GC_NOTRIGGER;
284 INSTANCE_CHECK;
285 }
286 CONTRACT_END;
287
288 if (m_tableOccupied == m_tableMax)
289 {
290 Grow();
291 RETURN TRUE;
292 }
293
294 RETURN FALSE;
295}
296
297template <typename TRAITS>
298typename SHash<TRAITS>::element_t *
299SHash<TRAITS>::CheckGrowth_OnlyAllocateNewTable(count_t * pcNewSize)
300{
301 CONTRACT(element_t *)
302 {
303 THROWS;
304 GC_NOTRIGGER;
305 INSTANCE_CHECK;
306 }
307 CONTRACT_END;
308
309 if (m_tableOccupied == m_tableMax)
310 {
311 RETURN Grow_OnlyAllocateNewTable(pcNewSize);
312 }
313
314 RETURN NULL;
315}
316
317template <typename TRAITS>
318void SHash<TRAITS>::Grow()
319{
320 CONTRACT_VOID
321 {
322 THROWS;
323 GC_NOTRIGGER;
324 INSTANCE_CHECK;
325 }
326 CONTRACT_END;
327
328 count_t newSize;
329 element_t * newTable = Grow_OnlyAllocateNewTable(&newSize);
330 element_t * oldTable = ReplaceTable(newTable, newSize);
331 DeleteOldTable(oldTable);
332
333 RETURN;
334}
335
336template <typename TRAITS>
337typename SHash<TRAITS>::element_t *
338SHash<TRAITS>::Grow_OnlyAllocateNewTable(count_t * pcNewSize)
339{
340 CONTRACT(element_t *)
341 {
342 THROWS;
343 GC_NOTRIGGER;
344 INSTANCE_CHECK;
345 }
346 CONTRACT_END;
347
348 count_t newSize = (count_t) (m_tableCount
349 * TRAITS::s_growth_factor_numerator / TRAITS::s_growth_factor_denominator
350 * TRAITS::s_density_factor_denominator / TRAITS::s_density_factor_numerator);
351 if (newSize < TRAITS::s_minimum_allocation)
352 newSize = TRAITS::s_minimum_allocation;
353
354 // handle potential overflow
355 if (newSize < m_tableCount)
356 ThrowOutOfMemory();
357
358 RETURN AllocateNewTable(newSize, pcNewSize);
359}
360
361template <typename TRAITS>
362void SHash<TRAITS>::Reallocate(count_t requestedSize)
363{
364 CONTRACT_VOID
365 {
366 THROWS;
367 GC_NOTRIGGER;
368 INSTANCE_CHECK;
369 }
370 CONTRACT_END;
371
372 count_t newTableSize;
373 element_t * newTable = AllocateNewTable(requestedSize, &newTableSize);
374 element_t * oldTable = ReplaceTable(newTable, newTableSize);
375 DeleteOldTable(oldTable);
376
377 RETURN;
378}
379
380template <typename TRAITS>
381template <typename Functor>
382void SHash<TRAITS>::ForEach(Functor &functor)
383{
384 WRAPPER_NO_CONTRACT; // LIMITED_METHOD_CONTRACT + Functor
385
386 for (count_t i = 0; i < m_tableSize; i++)
387 {
388 element_t element = m_table[i];
389 if (!TRAITS::IsNull(element) && !TRAITS::IsDeleted(element))
390 {
391 functor(element);
392 }
393 }
394}
395
396template <typename TRAITS>
397typename SHash<TRAITS>::element_t *
398SHash<TRAITS>::AllocateNewTable(count_t requestedSize, count_t * pcNewTableSize)
399{
400 CONTRACT(element_t *)
401 {
402 THROWS;
403 GC_NOTRIGGER;
404 INSTANCE_CHECK;
405 PRECONDITION(requestedSize >=
406 (count_t) (GetCount() * TRAITS::s_density_factor_denominator / TRAITS::s_density_factor_numerator));
407 }
408 CONTRACT_END;
409
410 // Allocation size must be a prime number. This is necessary so that hashes uniformly
411 // distribute to all indices, and so that chaining will visit all indices in the hash table.
412 *pcNewTableSize = NextPrime(requestedSize);
413
414 element_t * newTable = new element_t [*pcNewTableSize];
415
416 element_t * p = newTable;
417 element_t * pEnd = newTable + *pcNewTableSize;
418 while (p < pEnd)
419 {
420 *p = TRAITS::Null();
421 p++;
422 }
423
424 RETURN newTable;
425}
426
427template <typename TRAITS>
428typename SHash<TRAITS>::element_t *
429SHash<TRAITS>::ReplaceTable(element_t * newTable, count_t newTableSize)
430{
431 CONTRACT(element_t *)
432 {
433 NOTHROW_UNLESS_TRAITS_THROWS;
434 GC_NOTRIGGER;
435 INSTANCE_CHECK;
436 PRECONDITION(newTableSize >=
437 (count_t) (GetCount() * TRAITS::s_density_factor_denominator / TRAITS::s_density_factor_numerator));
438 }
439 CONTRACT_END;
440
441 element_t * oldTable = m_table;
442
443 // Move all entries over to new table.
444 for (Iterator i = Begin(), end = End(); i != end; i++)
445 {
446 const element_t & cur = (*i);
447 if (!TRAITS::IsNull(cur) && !TRAITS::IsDeleted(cur))
448 Add(newTable, newTableSize, cur);
449 }
450
451 m_table = PTR_element_t(newTable);
452 m_tableSize = newTableSize;
453 m_tableMax = (count_t) (newTableSize * TRAITS::s_density_factor_numerator / TRAITS::s_density_factor_denominator);
454 m_tableOccupied = m_tableCount;
455
456 RETURN oldTable;
457}
458
459template <typename TRAITS>
460void
461SHash<TRAITS>::DeleteOldTable(element_t * oldTable)
462{
463 CONTRACT_VOID
464 {
465 NOTHROW;
466 GC_NOTRIGGER;
467 }
468 CONTRACT_END;
469
470 // @todo:
471 // We might want to try to delay this cleanup to allow asynchronous readers
472 if (oldTable != NULL)
473 delete [] oldTable;
474
475 RETURN;
476}
477
478template <typename TRAITS>
479const typename SHash<TRAITS>::element_t * SHash<TRAITS>::Lookup(PTR_element_t table, count_t tableSize, key_t key)
480{
481 CONTRACT(const element_t *)
482 {
483 NOTHROW_UNLESS_TRAITS_THROWS;
484 GC_NOTRIGGER;
485 POSTCONDITION(RETVAL == NULL || TRAITS::Equals(key, TRAITS::GetKey(*RETVAL)));
486 SUPPORTS_DAC_WRAPPER; // supports DAC only if the traits class does
487 }
488 CONTRACT_END;
489
490 if (tableSize == 0)
491 RETURN NULL;
492
493 count_t hash = TRAITS::Hash(key);
494 count_t index = hash % tableSize;
495 count_t increment = 0; // delay computation
496
497 while (TRUE)
498 {
499 element_t& current = table[index];
500
501 if (TRAITS::IsNull(current))
502 RETURN NULL;
503
504 if (!TRAITS::IsDeleted(current)
505 && TRAITS::Equals(key, TRAITS::GetKey(current)))
506 {
507 RETURN &current;
508 }
509
510 if (increment == 0)
511 increment = (hash % (tableSize-1)) + 1;
512
513 index += increment;
514 if (index >= tableSize)
515 index -= tableSize;
516 }
517}
518
519template <typename TRAITS>
520BOOL SHash<TRAITS>::Add(element_t * table, count_t tableSize, const element_t & element)
521{
522 CONTRACT(BOOL)
523 {
524 NOTHROW_UNLESS_TRAITS_THROWS;
525 GC_NOTRIGGER;
526 POSTCONDITION(TRAITS::Equals(TRAITS::GetKey(element), TRAITS::GetKey(*Lookup(table, tableSize, TRAITS::GetKey(element)))));
527 }
528 CONTRACT_END;
529
530 key_t key = TRAITS::GetKey(element);
531
532 count_t hash = TRAITS::Hash(key);
533 count_t index = hash % tableSize;
534 count_t increment = 0; // delay computation
535
536 while (TRUE)
537 {
538 element_t & current = table[index];
539
540 if (TRAITS::IsNull(current))
541 {
542 table[index] = element;
543 RETURN TRUE;
544 }
545
546 if (TRAITS::IsDeleted(current))
547 {
548 table[index] = element;
549 RETURN FALSE;
550 }
551
552 if (increment == 0)
553 increment = (hash % (tableSize-1)) + 1;
554
555 index += increment;
556 if (index >= tableSize)
557 index -= tableSize;
558 }
559}
560
561template <typename TRAITS>
562void SHash<TRAITS>::AddOrReplace(element_t *table, count_t tableSize, const element_t &element)
563{
564 CONTRACT_VOID
565 {
566 NOTHROW_UNLESS_TRAITS_THROWS;
567 GC_NOTRIGGER;
568 static_assert(!TRAITS::s_supports_remove, "SHash::AddOrReplace is not implemented for SHash with support for remove operations.");
569 POSTCONDITION(TRAITS::Equals(TRAITS::GetKey(element), TRAITS::GetKey(*Lookup(table, tableSize, TRAITS::GetKey(element)))));
570 }
571 CONTRACT_END;
572
573 key_t key = TRAITS::GetKey(element);
574
575 count_t hash = TRAITS::Hash(key);
576 count_t index = hash % tableSize;
577 count_t increment = 0; // delay computation
578
579 while (TRUE)
580 {
581 element_t& current = table[index];
582 _ASSERTE(!TRAITS::IsDeleted(current));
583
584 if (TRAITS::IsNull(current))
585 {
586 table[index] = element;
587 m_tableCount++;
588 m_tableOccupied++;
589 RETURN;
590 }
591 else if (TRAITS::Equals(key, TRAITS::GetKey(current)))
592 {
593 table[index] = element;
594 RETURN;
595 }
596
597 if (increment == 0)
598 increment = (hash % (tableSize-1)) + 1;
599
600 index += increment;
601 if (index >= tableSize)
602 index -= tableSize;
603 }
604}
605
606template <typename TRAITS>
607void SHash<TRAITS>::Remove(element_t *table, count_t tableSize, key_t key)
608{
609 CONTRACT_VOID
610 {
611 NOTHROW_UNLESS_TRAITS_THROWS;
612 GC_NOTRIGGER;
613 static_assert(TRAITS::s_supports_remove, "This SHash does not support remove operations.");
614 PRECONDITION(Lookup(table, tableSize, key) != NULL);
615 }
616 CONTRACT_END;
617
618 count_t hash = TRAITS::Hash(key);
619 count_t index = hash % tableSize;
620 count_t increment = 0; // delay computation
621
622 while (TRUE)
623 {
624 element_t& current = table[index];
625
626 if (TRAITS::IsNull(current))
627 RETURN;
628
629 if (!TRAITS::IsDeleted(current)
630 && TRAITS::Equals(key, TRAITS::GetKey(current)))
631 {
632 table[index] = TRAITS::Deleted();
633 m_tableCount--;
634 RETURN;
635 }
636
637 if (increment == 0)
638 increment = (hash % (tableSize-1)) + 1;
639
640 index += increment;
641 if (index >= tableSize)
642 index -= tableSize;
643 }
644}
645
646template <typename TRAITS>
647void SHash<TRAITS>::RemoveElement(element_t *table, count_t tableSize, element_t *element)
648{
649 CONTRACT_VOID
650 {
651 NOTHROW;
652 GC_NOTRIGGER;
653 static_assert(TRAITS::s_supports_remove, "This SHash does not support remove operations.");
654 PRECONDITION(table <= element && element < table + tableSize);
655 PRECONDITION(!TRAITS::IsNull(*element) && !TRAITS::IsDeleted(*element));
656 }
657 CONTRACT_END;
658
659 *element = TRAITS::Deleted();
660 m_tableCount--;
661 RETURN;
662}
663
664template <typename TRAITS>
665BOOL SHash<TRAITS>::IsPrime(COUNT_T number)
666{
667 CONTRACT(BOOL)
668 {
669 NOTHROW;
670 GC_NOTRIGGER;
671 }
672 CONTRACT_END;
673
674 // This is a very low-tech check for primality, which doesn't scale very well.
675 // There are more efficient tests if this proves to be burdensome for larger
676 // tables.
677
678 if ((number & 1) == 0)
679 RETURN FALSE;
680
681 COUNT_T factor = 3;
682 while (factor * factor <= number)
683 {
684 if ((number % factor) == 0)
685 RETURN FALSE;
686 factor += 2;
687 }
688
689 RETURN TRUE;
690}
691
692// allow coexistence with simplerhash.inl
693#ifndef _HASH_PRIMES_DEFINED
694#define _HASH_PRIMES_DEFINED
695
696namespace
697{
698 const COUNT_T g_shash_primes[] = {
699 11,17,23,29,37,47,59,71,89,107,131,163,197,239,293,353,431,521,631,761,919,
700 1103,1327,1597,1931,2333,2801,3371,4049,4861,5839,7013,8419,10103,12143,14591,
701 17519,21023,25229,30293,36353,43627,52361,62851,75431,90523, 108631, 130363,
702 156437, 187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403,
703 968897, 1162687, 1395263, 1674319, 2009191, 2411033, 2893249, 3471899, 4166287,
704 4999559, 5999471, 7199369 };
705}
706
707#endif //_HASH_PRIMES_DEFINED
708
709template <typename TRAITS>
710COUNT_T SHash<TRAITS>::NextPrime(COUNT_T number)
711{
712 CONTRACT(COUNT_T)
713 {
714 NOTHROW;
715 GC_NOTRIGGER;
716 POSTCONDITION(IsPrime(RETVAL));
717 }
718 CONTRACT_END;
719
720 for (int i = 0; i < (int) (sizeof(g_shash_primes) / sizeof(g_shash_primes[0])); i++) {
721 if (g_shash_primes[i] >= number)
722 RETURN g_shash_primes[i];
723 }
724
725 if ((number&1) == 0)
726 number++;
727
728 while (number != 1) {
729 if (IsPrime(number))
730 RETURN number;
731 number +=2;
732 }
733
734 // overflow
735 ThrowOutOfMemory();
736}
737
738template <typename TRAITS>
739SHash<TRAITS>::AddPhases::AddPhases()
740{
741 LIMITED_METHOD_CONTRACT;
742
743 m_pHash = NULL;
744 m_newTable = NULL;
745 m_newTableSize = 0;
746 m_oldTable = NULL;
747
748 INDEBUG(dbg_m_fAddCalled = FALSE;)
749}
750
751template <typename TRAITS>
752SHash<TRAITS>::AddPhases::~AddPhases()
753{
754 LIMITED_METHOD_CONTRACT;
755
756 if (m_newTable != NULL)
757 { // The new table was not applied to the hash yet
758 _ASSERTE((m_pHash != NULL) && (m_newTableSize != 0) && (m_oldTable == NULL));
759
760 delete [] m_newTable;
761 }
762 DeleteOldTable();
763}
764
765template <typename TRAITS>
766void SHash<TRAITS>::AddPhases::PreallocateForAdd(SHash * pHash)
767{
768 CONTRACT_VOID
769 {
770 THROWS;
771 GC_NOTRIGGER;
772 }
773 CONTRACT_END;
774
775 _ASSERTE((m_pHash == NULL) && (m_newTable == NULL) && (m_newTableSize == 0) && (m_oldTable == NULL));
776
777 m_pHash = pHash;
778 // May return NULL if the allocation was not needed
779 m_newTable = m_pHash->CheckGrowth_OnlyAllocateNewTable(&m_newTableSize);
780
781#ifdef _DEBUG
782 dbg_m_table = pHash->m_table;
783 dbg_m_tableSize = pHash->m_tableSize;
784 dbg_m_tableCount = pHash->m_tableCount;
785 dbg_m_tableOccupied = pHash->m_tableOccupied;
786 dbg_m_tableMax = pHash->m_tableMax;
787#endif //_DEBUG
788
789 RETURN;
790}
791
792template <typename TRAITS>
793void SHash<TRAITS>::AddPhases::Add(const element_t & element)
794{
795 CONTRACT_VOID
796 {
797 NOTHROW_UNLESS_TRAITS_THROWS;
798 GC_NOTRIGGER;
799 }
800 CONTRACT_END;
801
802 _ASSERTE((m_pHash != NULL) && (m_oldTable == NULL));
803 // Add can be called only once on this object
804 _ASSERTE(!dbg_m_fAddCalled);
805
806 // Check that the hash table didn't change since call to code:PreallocateForAdd
807 _ASSERTE(dbg_m_table == m_pHash->m_table);
808 _ASSERTE(dbg_m_tableSize == m_pHash->m_tableSize);
809 _ASSERTE(dbg_m_tableCount >= m_pHash->m_tableCount); // Remove operation might have removed elements
810 _ASSERTE(dbg_m_tableOccupied == m_pHash->m_tableOccupied);
811 _ASSERTE(dbg_m_tableMax == m_pHash->m_tableMax);
812
813 if (m_newTable != NULL)
814 { // We have pre-allocated table from code:PreallocateForAdd, use it.
815 _ASSERTE(m_newTableSize != 0);
816
817 // May return NULL if there was not table allocated yet
818 m_oldTable = m_pHash->ReplaceTable(m_newTable, m_newTableSize);
819
820 m_newTable = NULL;
821 m_newTableSize = 0;
822 }
823 // We know that we have enough space, direcly add the element
824 m_pHash->Add_GrowthChecked(element);
825
826 INDEBUG(dbg_m_fAddCalled = TRUE;)
827
828 RETURN;
829}
830
831template <typename TRAITS>
832void SHash<TRAITS>::AddPhases::AddNothing_PublishPreallocatedTable()
833{
834 CONTRACT_VOID
835 {
836 NOTHROW_UNLESS_TRAITS_THROWS;
837 GC_NOTRIGGER;
838 }
839 CONTRACT_END;
840
841 _ASSERTE((m_pHash != NULL) && (m_oldTable == NULL));
842 // Add can be called only once on this object
843 _ASSERTE(!dbg_m_fAddCalled);
844
845 // Check that the hash table didn't change since call to code:PreallocateForAdd
846 _ASSERTE(dbg_m_table == m_pHash->m_table);
847 _ASSERTE(dbg_m_tableSize == m_pHash->m_tableSize);
848 _ASSERTE(dbg_m_tableCount >= m_pHash->m_tableCount); // Remove operation might have removed elements
849 _ASSERTE(dbg_m_tableOccupied == m_pHash->m_tableOccupied);
850 _ASSERTE(dbg_m_tableMax == m_pHash->m_tableMax);
851
852 if (m_newTable != NULL)
853 { // We have pre-allocated table from code:PreallocateForAdd, use it.
854 _ASSERTE(m_newTableSize != 0);
855
856 // May return NULL if there was not table allocated yet
857 m_oldTable = m_pHash->ReplaceTable(m_newTable, m_newTableSize);
858
859 m_newTable = NULL;
860 m_newTableSize = 0;
861 }
862
863 INDEBUG(dbg_m_fAddCalled = TRUE;)
864
865 RETURN;
866}
867
868template <typename TRAITS>
869void SHash<TRAITS>::AddPhases::DeleteOldTable()
870{
871 LIMITED_METHOD_CONTRACT;
872
873 if (m_oldTable != NULL)
874 {
875 _ASSERTE((m_pHash != NULL) && (m_newTable == NULL) && (m_newTableSize == 0));
876
877 delete [] m_oldTable;
878 m_oldTable = NULL;
879 }
880}
881
882template <typename TRAITS>
883template <typename LockHolderT,
884 typename AddLockHolderT,
885 typename LockT,
886 typename AddLockT>
887bool SHash<TRAITS>::CheckAddInPhases(
888 element_t const & elem,
889 LockT & lock,
890 AddLockT & addLock,
891 IUnknown * addRefObject)
892{
893 CONTRACTL
894 {
895 THROWS;
896 GC_NOTRIGGER;
897 INSTANCE_CHECK;
898 }
899 CONTRACTL_END;
900
901 AddLockHolderT hAddLock(&addLock);
902 AddPhases addCall;
903
904 // 1. Preallocate one element
905 addCall.PreallocateForAdd(this);
906 {
907 // 2. Take the reader lock. Host callouts now forbidden.
908 LockHolderT hLock(&lock);
909
910 element_t const * pEntry = LookupPtr(TRAITS::GetKey(elem));
911 if (pEntry != nullptr)
912 {
913 // 3a. Use the newly allocated table (if any) to avoid later redundant allocation.
914 addCall.AddNothing_PublishPreallocatedTable();
915 return false;
916 }
917 else
918 {
919 // 3b. Add the element to the hash table.
920 addCall.Add(elem);
921
922 if (addRefObject != nullptr)
923 {
924 clr::SafeAddRef(addRefObject);
925 }
926
927 return true;
928 }
929 }
930
931 // 4. addCall's destructor will take care of any required cleanup.
932}
933
934
935#endif // _SHASH_INL_
936