summaryrefslogtreecommitdiff
path: root/src/inc/shash.inl
diff options
context:
space:
mode:
Diffstat (limited to 'src/inc/shash.inl')
-rw-r--r--src/inc/shash.inl935
1 files changed, 935 insertions, 0 deletions
diff --git a/src/inc/shash.inl b/src/inc/shash.inl
new file mode 100644
index 0000000000..72affb45ba
--- /dev/null
+++ b/src/inc/shash.inl
@@ -0,0 +1,935 @@
+// Licensed to the .NET Foundation under one or more agreements.
+// The .NET Foundation licenses this file to you under the MIT license.
+// See the LICENSE file in the project root for more information.
+
+#ifndef _SHASH_INL_
+#define _SHASH_INL_
+
+// Many SHash functions do not throw on their own, but may propagate an exception
+// from Hash, Equals, or GetKey.
+#define NOTHROW_UNLESS_TRAITS_THROWS if (TRAITS::s_NoThrow) NOTHROW; else THROWS
+
+void DECLSPEC_NORETURN ThrowOutOfMemory();
+
+template <typename TRAITS>
+SHash<TRAITS>::SHash()
+ : m_table(nullptr),
+ m_tableSize(0),
+ m_tableCount(0),
+ m_tableOccupied(0),
+ m_tableMax(0)
+{
+ LIMITED_METHOD_CONTRACT;
+
+#ifndef __GNUC__ // these crash GCC
+ static_assert_no_msg(s_growth_factor_numerator > s_growth_factor_denominator);
+ static_assert_no_msg(s_density_factor_numerator < s_density_factor_denominator);
+#endif
+}
+
+template <typename TRAITS>
+SHash<TRAITS>::~SHash()
+{
+ LIMITED_METHOD_CONTRACT;
+
+ if (TRAITS::s_DestructPerEntryCleanupAction)
+ {
+ for (Iterator i = Begin(); i != End(); i++)
+ {
+ TRAITS::OnDestructPerEntryCleanupAction(*i);
+ }
+ }
+
+ delete [] m_table;
+}
+
+template <typename TRAITS>
+typename SHash<TRAITS>::count_t SHash<TRAITS>::GetCount() const
+{
+ LIMITED_METHOD_CONTRACT;
+
+ return m_tableCount;
+}
+
+template <typename TRAITS>
+typename SHash<TRAITS>::element_t SHash<TRAITS>::Lookup(key_t key) const
+{
+ CONTRACT(element_t)
+ {
+ NOTHROW_UNLESS_TRAITS_THROWS;
+ GC_NOTRIGGER;
+ INSTANCE_CHECK;
+ POSTCONDITION(TRAITS::IsNull(RETVAL) || TRAITS::Equals(key, TRAITS::GetKey(RETVAL)));
+ SUPPORTS_DAC_WRAPPER;
+ }
+ CONTRACT_END;
+
+ const element_t *pRet = Lookup(m_table, m_tableSize, key);
+ RETURN ((pRet != NULL) ? (*pRet) : TRAITS::Null());
+}
+
+template <typename TRAITS>
+const typename SHash<TRAITS>::element_t * SHash<TRAITS>::LookupPtr(key_t key) const
+{
+ CONTRACT(const element_t *)
+ {
+ NOTHROW_UNLESS_TRAITS_THROWS;
+ GC_NOTRIGGER;
+ INSTANCE_CHECK;
+ POSTCONDITION(RETVAL == NULL || TRAITS::Equals(key, TRAITS::GetKey(*RETVAL)));
+ }
+ CONTRACT_END;
+
+ RETURN Lookup(m_table, m_tableSize, key);
+}
+
+template <typename TRAITS>
+void SHash<TRAITS>::Add(const element_t & element)
+{
+ CONTRACT_VOID
+ {
+ THROWS;
+ GC_NOTRIGGER;
+ INSTANCE_CHECK;
+ POSTCONDITION(TRAITS::Equals(TRAITS::GetKey(element), TRAITS::GetKey(*LookupPtr(TRAITS::GetKey(element)))));
+ }
+ CONTRACT_END;
+
+ CheckGrowth();
+
+ Add_GrowthChecked(element);
+
+ RETURN;
+}
+
+template <typename TRAITS>
+void SHash<TRAITS>::Add_GrowthChecked(const element_t & element)
+{
+ CONTRACT_VOID
+ {
+ NOTHROW_UNLESS_TRAITS_THROWS;
+ GC_NOTRIGGER;
+ INSTANCE_CHECK;
+ POSTCONDITION(TRAITS::Equals(TRAITS::GetKey(element), TRAITS::GetKey(*LookupPtr(TRAITS::GetKey(element)))));
+ }
+ CONTRACT_END;
+
+ if (Add(m_table, m_tableSize, element))
+ m_tableOccupied++;
+ m_tableCount++;
+
+ RETURN;
+}
+
+template <typename TRAITS>
+void SHash<TRAITS>::AddOrReplace(const element_t &element)
+{
+ CONTRACT_VOID
+ {
+ THROWS;
+ GC_NOTRIGGER;
+ INSTANCE_CHECK;
+ static_assert(!TRAITS::s_supports_remove, "SHash::AddOrReplace is not implemented for SHash with support for remove operations.");
+ POSTCONDITION(TRAITS::Equals(TRAITS::GetKey(element), TRAITS::GetKey(*LookupPtr(TRAITS::GetKey(element)))));
+ }
+ CONTRACT_END;
+
+ CheckGrowth();
+
+ AddOrReplace(m_table, m_tableSize, element);
+
+ RETURN;
+}
+
+template <typename TRAITS>
+void SHash<TRAITS>::Remove(key_t key)
+{
+ CONTRACT_VOID
+ {
+ NOTHROW_UNLESS_TRAITS_THROWS;
+ GC_NOTRIGGER;
+ INSTANCE_CHECK;
+ static_assert(TRAITS::s_supports_remove, "This SHash does not support remove operations.");
+ PRECONDITION(!(TRAITS::IsNull(Lookup(key))));
+ }
+ CONTRACT_END;
+
+ Remove(m_table, m_tableSize, key);
+
+ RETURN;
+}
+
+template <typename TRAITS>
+void SHash<TRAITS>::Remove(Iterator& i)
+{
+ CONTRACT_VOID
+ {
+ NOTHROW;
+ GC_NOTRIGGER;
+ INSTANCE_CHECK;
+ static_assert(TRAITS::s_supports_remove, "This SHash does not support remove operations.");
+ PRECONDITION(!(TRAITS::IsNull(*i)));
+ PRECONDITION(!(TRAITS::IsDeleted(*i)));
+ }
+ CONTRACT_END;
+
+ RemoveElement(m_table, m_tableSize, (element_t*)&(*i));
+
+ RETURN;
+}
+
+template <typename TRAITS>
+void SHash<TRAITS>::Remove(KeyIterator& i)
+{
+ CONTRACT_VOID
+ {
+ NOTHROW;
+ GC_NOTRIGGER;
+ INSTANCE_CHECK;
+ static_assert(TRAITS::s_supports_remove, "This SHash does not support remove operations.");
+ PRECONDITION(!(TRAITS::IsNull(*i)));
+ PRECONDITION(!(TRAITS::IsDeleted(*i)));
+ }
+ CONTRACT_END;
+
+ RemoveElement(m_table, m_tableSize, (element_t*)&(*i));
+
+ RETURN;
+}
+
+template <typename TRAITS>
+void SHash<TRAITS>::RemovePtr(element_t * p)
+{
+ CONTRACT_VOID
+ {
+ NOTHROW;
+ GC_NOTRIGGER;
+ INSTANCE_CHECK;
+ static_assert(TRAITS::s_supports_remove, "This SHash does not support remove operations.");
+ PRECONDITION(!(TRAITS::IsNull(*p)));
+ PRECONDITION(!(TRAITS::IsDeleted(*p)));
+ }
+ CONTRACT_END;
+
+ RemoveElement(m_table, m_tableSize, p);
+
+ RETURN;
+}
+
+template <typename TRAITS>
+void SHash<TRAITS>::RemoveAll()
+{
+ CONTRACT_VOID
+ {
+ NOTHROW;
+ GC_NOTRIGGER;
+ INSTANCE_CHECK;
+ }
+ CONTRACT_END;
+
+ delete [] m_table;
+
+ m_table = NULL;
+ m_tableSize = 0;
+ m_tableCount = 0;
+ m_tableOccupied = 0;
+ m_tableMax = 0;
+
+ RETURN;
+}
+
+template <typename TRAITS>
+typename SHash<TRAITS>::Iterator SHash<TRAITS>::Begin() const
+{
+ LIMITED_METHOD_CONTRACT;
+
+ Iterator i(this, TRUE);
+ i.First();
+ return i;
+}
+
+template <typename TRAITS>
+typename SHash<TRAITS>::Iterator SHash<TRAITS>::End() const
+{
+ LIMITED_METHOD_CONTRACT;
+
+ return Iterator(this, FALSE);
+}
+
+template <typename TRAITS>
+typename SHash<TRAITS>::KeyIterator SHash<TRAITS>::Begin(key_t key) const
+{
+ LIMITED_METHOD_CONTRACT;
+
+ KeyIterator k(this, TRUE);
+ k.SetKey(key);
+ return k;
+}
+
+template <typename TRAITS>
+typename SHash<TRAITS>::KeyIterator SHash<TRAITS>::End(key_t key) const
+{
+ LIMITED_METHOD_CONTRACT;
+
+ return KeyIterator(this, FALSE);
+}
+
+template <typename TRAITS>
+BOOL SHash<TRAITS>::CheckGrowth()
+{
+ CONTRACT(BOOL)
+ {
+ THROWS;
+ GC_NOTRIGGER;
+ INSTANCE_CHECK;
+ }
+ CONTRACT_END;
+
+ if (m_tableOccupied == m_tableMax)
+ {
+ Grow();
+ RETURN TRUE;
+ }
+
+ RETURN FALSE;
+}
+
+template <typename TRAITS>
+typename SHash<TRAITS>::element_t *
+SHash<TRAITS>::CheckGrowth_OnlyAllocateNewTable(count_t * pcNewSize)
+{
+ CONTRACT(element_t *)
+ {
+ THROWS;
+ GC_NOTRIGGER;
+ INSTANCE_CHECK;
+ }
+ CONTRACT_END;
+
+ if (m_tableOccupied == m_tableMax)
+ {
+ RETURN Grow_OnlyAllocateNewTable(pcNewSize);
+ }
+
+ RETURN NULL;
+}
+
+template <typename TRAITS>
+void SHash<TRAITS>::Grow()
+{
+ CONTRACT_VOID
+ {
+ THROWS;
+ GC_NOTRIGGER;
+ INSTANCE_CHECK;
+ }
+ CONTRACT_END;
+
+ count_t newSize;
+ element_t * newTable = Grow_OnlyAllocateNewTable(&newSize);
+ element_t * oldTable = ReplaceTable(newTable, newSize);
+ DeleteOldTable(oldTable);
+
+ RETURN;
+}
+
+template <typename TRAITS>
+typename SHash<TRAITS>::element_t *
+SHash<TRAITS>::Grow_OnlyAllocateNewTable(count_t * pcNewSize)
+{
+ CONTRACT(element_t *)
+ {
+ THROWS;
+ GC_NOTRIGGER;
+ INSTANCE_CHECK;
+ }
+ CONTRACT_END;
+
+ count_t newSize = (count_t) (m_tableCount
+ * TRAITS::s_growth_factor_numerator / TRAITS::s_growth_factor_denominator
+ * TRAITS::s_density_factor_denominator / TRAITS::s_density_factor_numerator);
+ if (newSize < TRAITS::s_minimum_allocation)
+ newSize = TRAITS::s_minimum_allocation;
+
+ // handle potential overflow
+ if (newSize < m_tableCount)
+ ThrowOutOfMemory();
+
+ RETURN AllocateNewTable(newSize, pcNewSize);
+}
+
+template <typename TRAITS>
+void SHash<TRAITS>::Reallocate(count_t requestedSize)
+{
+ CONTRACT_VOID
+ {
+ THROWS;
+ GC_NOTRIGGER;
+ INSTANCE_CHECK;
+ }
+ CONTRACT_END;
+
+ count_t newTableSize;
+ element_t * newTable = AllocateNewTable(requestedSize, &newTableSize);
+ element_t * oldTable = ReplaceTable(newTable, newTableSize);
+ DeleteOldTable(oldTable);
+
+ RETURN;
+}
+
+template <typename TRAITS>
+template <typename Functor>
+void SHash<TRAITS>::ForEach(Functor &functor)
+{
+ WRAPPER_NO_CONTRACT; // LIMITED_METHOD_CONTRACT + Functor
+
+ for (count_t i = 0; i < m_tableSize; i++)
+ {
+ element_t element = m_table[i];
+ if (!TRAITS::IsNull(element) && !TRAITS::IsDeleted(element))
+ {
+ functor(element);
+ }
+ }
+}
+
+template <typename TRAITS>
+typename SHash<TRAITS>::element_t *
+SHash<TRAITS>::AllocateNewTable(count_t requestedSize, count_t * pcNewTableSize)
+{
+ CONTRACT(element_t *)
+ {
+ THROWS;
+ GC_NOTRIGGER;
+ INSTANCE_CHECK;
+ PRECONDITION(requestedSize >=
+ (count_t) (GetCount() * s_density_factor_denominator / s_density_factor_numerator));
+ }
+ CONTRACT_END;
+
+ // Allocation size must be a prime number. This is necessary so that hashes uniformly
+ // distribute to all indices, and so that chaining will visit all indices in the hash table.
+ *pcNewTableSize = NextPrime(requestedSize);
+
+ element_t * newTable = new element_t [*pcNewTableSize];
+
+ element_t * p = newTable;
+ element_t * pEnd = newTable + *pcNewTableSize;
+ while (p < pEnd)
+ {
+ *p = TRAITS::Null();
+ p++;
+ }
+
+ RETURN newTable;
+}
+
+template <typename TRAITS>
+typename SHash<TRAITS>::element_t *
+SHash<TRAITS>::ReplaceTable(element_t * newTable, count_t newTableSize)
+{
+ CONTRACT(element_t *)
+ {
+ NOTHROW_UNLESS_TRAITS_THROWS;
+ GC_NOTRIGGER;
+ INSTANCE_CHECK;
+ PRECONDITION(newTableSize >=
+ (count_t) (GetCount() * s_density_factor_denominator / s_density_factor_numerator));
+ }
+ CONTRACT_END;
+
+ element_t * oldTable = m_table;
+
+ // Move all entries over to new table.
+ for (Iterator i = Begin(), end = End(); i != end; i++)
+ {
+ const element_t & cur = (*i);
+ if (!TRAITS::IsNull(cur) && !TRAITS::IsDeleted(cur))
+ Add(newTable, newTableSize, cur);
+ }
+
+ m_table = PTR_element_t(newTable);
+ m_tableSize = newTableSize;
+ m_tableMax = (count_t) (newTableSize * TRAITS::s_density_factor_numerator / TRAITS::s_density_factor_denominator);
+ m_tableOccupied = m_tableCount;
+
+ RETURN oldTable;
+}
+
+template <typename TRAITS>
+void
+SHash<TRAITS>::DeleteOldTable(element_t * oldTable)
+{
+ CONTRACT_VOID
+ {
+ NOTHROW;
+ GC_NOTRIGGER;
+ }
+ CONTRACT_END;
+
+ // @todo:
+ // We might want to try to delay this cleanup to allow asynchronous readers
+ if (oldTable != NULL)
+ delete [] oldTable;
+
+ RETURN;
+}
+
+template <typename TRAITS>
+const typename SHash<TRAITS>::element_t * SHash<TRAITS>::Lookup(PTR_element_t table, count_t tableSize, key_t key)
+{
+ CONTRACT(const element_t *)
+ {
+ NOTHROW_UNLESS_TRAITS_THROWS;
+ GC_NOTRIGGER;
+ POSTCONDITION(RETVAL == NULL || TRAITS::Equals(key, TRAITS::GetKey(*RETVAL)));
+ SUPPORTS_DAC_WRAPPER; // supports DAC only if the traits class does
+ }
+ CONTRACT_END;
+
+ if (tableSize == 0)
+ RETURN NULL;
+
+ count_t hash = TRAITS::Hash(key);
+ count_t index = hash % tableSize;
+ count_t increment = 0; // delay computation
+
+ while (TRUE)
+ {
+ element_t& current = table[index];
+
+ if (TRAITS::IsNull(current))
+ RETURN NULL;
+
+ if (!TRAITS::IsDeleted(current)
+ && TRAITS::Equals(key, TRAITS::GetKey(current)))
+ {
+ RETURN &current;
+ }
+
+ if (increment == 0)
+ increment = (hash % (tableSize-1)) + 1;
+
+ index += increment;
+ if (index >= tableSize)
+ index -= tableSize;
+ }
+}
+
+template <typename TRAITS>
+BOOL SHash<TRAITS>::Add(element_t * table, count_t tableSize, const element_t & element)
+{
+ CONTRACT(BOOL)
+ {
+ NOTHROW_UNLESS_TRAITS_THROWS;
+ GC_NOTRIGGER;
+ POSTCONDITION(TRAITS::Equals(TRAITS::GetKey(element), TRAITS::GetKey(*Lookup(table, tableSize, TRAITS::GetKey(element)))));
+ }
+ CONTRACT_END;
+
+ key_t key = TRAITS::GetKey(element);
+
+ count_t hash = TRAITS::Hash(key);
+ count_t index = hash % tableSize;
+ count_t increment = 0; // delay computation
+
+ while (TRUE)
+ {
+ element_t & current = table[index];
+
+ if (TRAITS::IsNull(current))
+ {
+ table[index] = element;
+ RETURN TRUE;
+ }
+
+ if (TRAITS::IsDeleted(current))
+ {
+ table[index] = element;
+ RETURN FALSE;
+ }
+
+ if (increment == 0)
+ increment = (hash % (tableSize-1)) + 1;
+
+ index += increment;
+ if (index >= tableSize)
+ index -= tableSize;
+ }
+}
+
+template <typename TRAITS>
+void SHash<TRAITS>::AddOrReplace(element_t *table, count_t tableSize, const element_t &element)
+{
+ CONTRACT_VOID
+ {
+ NOTHROW_UNLESS_TRAITS_THROWS;
+ GC_NOTRIGGER;
+ static_assert(!TRAITS::s_supports_remove, "SHash::AddOrReplace is not implemented for SHash with support for remove operations.");
+ POSTCONDITION(TRAITS::Equals(TRAITS::GetKey(element), TRAITS::GetKey(*Lookup(table, tableSize, TRAITS::GetKey(element)))));
+ }
+ CONTRACT_END;
+
+ key_t key = TRAITS::GetKey(element);
+
+ count_t hash = TRAITS::Hash(key);
+ count_t index = hash % tableSize;
+ count_t increment = 0; // delay computation
+
+ while (TRUE)
+ {
+ element_t& current = table[index];
+ _ASSERTE(!TRAITS::IsDeleted(current));
+
+ if (TRAITS::IsNull(current))
+ {
+ table[index] = element;
+ m_tableCount++;
+ m_tableOccupied++;
+ RETURN;
+ }
+ else if (TRAITS::Equals(key, TRAITS::GetKey(current)))
+ {
+ table[index] = element;
+ RETURN;
+ }
+
+ if (increment == 0)
+ increment = (hash % (tableSize-1)) + 1;
+
+ index += increment;
+ if (index >= tableSize)
+ index -= tableSize;
+ }
+}
+
+template <typename TRAITS>
+void SHash<TRAITS>::Remove(element_t *table, count_t tableSize, key_t key)
+{
+ CONTRACT_VOID
+ {
+ NOTHROW_UNLESS_TRAITS_THROWS;
+ GC_NOTRIGGER;
+ static_assert(TRAITS::s_supports_remove, "This SHash does not support remove operations.");
+ PRECONDITION(Lookup(table, tableSize, key) != NULL);
+ }
+ CONTRACT_END;
+
+ count_t hash = TRAITS::Hash(key);
+ count_t index = hash % tableSize;
+ count_t increment = 0; // delay computation
+
+ while (TRUE)
+ {
+ element_t& current = table[index];
+
+ if (TRAITS::IsNull(current))
+ RETURN;
+
+ if (!TRAITS::IsDeleted(current)
+ && TRAITS::Equals(key, TRAITS::GetKey(current)))
+ {
+ table[index] = TRAITS::Deleted();
+ m_tableCount--;
+ RETURN;
+ }
+
+ if (increment == 0)
+ increment = (hash % (tableSize-1)) + 1;
+
+ index += increment;
+ if (index >= tableSize)
+ index -= tableSize;
+ }
+}
+
+template <typename TRAITS>
+void SHash<TRAITS>::RemoveElement(element_t *table, count_t tableSize, element_t *element)
+{
+ CONTRACT_VOID
+ {
+ NOTHROW;
+ GC_NOTRIGGER;
+ static_assert(TRAITS::s_supports_remove, "This SHash does not support remove operations.");
+ PRECONDITION(table <= element && element < table + tableSize);
+ PRECONDITION(!TRAITS::IsNull(*element) && !TRAITS::IsDeleted(*element));
+ }
+ CONTRACT_END;
+
+ *element = TRAITS::Deleted();
+ m_tableCount--;
+ RETURN;
+}
+
+template <typename TRAITS>
+BOOL SHash<TRAITS>::IsPrime(COUNT_T number)
+{
+ CONTRACT(BOOL)
+ {
+ NOTHROW;
+ GC_NOTRIGGER;
+ }
+ CONTRACT_END;
+
+ // This is a very low-tech check for primality, which doesn't scale very well.
+ // There are more efficient tests if this proves to be burdensome for larger
+ // tables.
+
+ if ((number & 1) == 0)
+ RETURN FALSE;
+
+ COUNT_T factor = 3;
+ while (factor * factor <= number)
+ {
+ if ((number % factor) == 0)
+ RETURN FALSE;
+ factor += 2;
+ }
+
+ RETURN TRUE;
+}
+
+// allow coexistence with simplerhash.inl
+#ifndef _HASH_PRIMES_DEFINED
+#define _HASH_PRIMES_DEFINED
+
+namespace
+{
+ const COUNT_T g_shash_primes[] = {
+ 11,17,23,29,37,47,59,71,89,107,131,163,197,239,293,353,431,521,631,761,919,
+ 1103,1327,1597,1931,2333,2801,3371,4049,4861,5839,7013,8419,10103,12143,14591,
+ 17519,21023,25229,30293,36353,43627,52361,62851,75431,90523, 108631, 130363,
+ 156437, 187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403,
+ 968897, 1162687, 1395263, 1674319, 2009191, 2411033, 2893249, 3471899, 4166287,
+ 4999559, 5999471, 7199369 };
+}
+
+#endif //_HASH_PRIMES_DEFINED
+
+template <typename TRAITS>
+COUNT_T SHash<TRAITS>::NextPrime(COUNT_T number)
+{
+ CONTRACT(COUNT_T)
+ {
+ NOTHROW;
+ GC_NOTRIGGER;
+ POSTCONDITION(IsPrime(RETVAL));
+ }
+ CONTRACT_END;
+
+ for (int i = 0; i < (int) (sizeof(g_shash_primes) / sizeof(g_shash_primes[0])); i++) {
+ if (g_shash_primes[i] >= number)
+ RETURN g_shash_primes[i];
+ }
+
+ if ((number&1) == 0)
+ number++;
+
+ while (number != 1) {
+ if (IsPrime(number))
+ RETURN number;
+ number +=2;
+ }
+
+ // overflow
+ ThrowOutOfMemory();
+}
+
+template <typename TRAITS>
+SHash<TRAITS>::AddPhases::AddPhases()
+{
+ LIMITED_METHOD_CONTRACT;
+
+ m_pHash = NULL;
+ m_newTable = NULL;
+ m_newTableSize = 0;
+ m_oldTable = NULL;
+
+ INDEBUG(dbg_m_fAddCalled = FALSE;)
+}
+
+template <typename TRAITS>
+SHash<TRAITS>::AddPhases::~AddPhases()
+{
+ LIMITED_METHOD_CONTRACT;
+
+ if (m_newTable != NULL)
+ { // The new table was not applied to the hash yet
+ _ASSERTE((m_pHash != NULL) && (m_newTableSize != 0) && (m_oldTable == NULL));
+
+ delete [] m_newTable;
+ }
+ DeleteOldTable();
+}
+
+template <typename TRAITS>
+void SHash<TRAITS>::AddPhases::PreallocateForAdd(SHash * pHash)
+{
+ CONTRACT_VOID
+ {
+ THROWS;
+ GC_NOTRIGGER;
+ }
+ CONTRACT_END;
+
+ _ASSERTE((m_pHash == NULL) && (m_newTable == NULL) && (m_newTableSize == 0) && (m_oldTable == NULL));
+
+ m_pHash = pHash;
+ // May return NULL if the allocation was not needed
+ m_newTable = m_pHash->CheckGrowth_OnlyAllocateNewTable(&m_newTableSize);
+
+#ifdef _DEBUG
+ dbg_m_table = pHash->m_table;
+ dbg_m_tableSize = pHash->m_tableSize;
+ dbg_m_tableCount = pHash->m_tableCount;
+ dbg_m_tableOccupied = pHash->m_tableOccupied;
+ dbg_m_tableMax = pHash->m_tableMax;
+#endif //_DEBUG
+
+ RETURN;
+}
+
+template <typename TRAITS>
+void SHash<TRAITS>::AddPhases::Add(const element_t & element)
+{
+ CONTRACT_VOID
+ {
+ NOTHROW_UNLESS_TRAITS_THROWS;
+ GC_NOTRIGGER;
+ }
+ CONTRACT_END;
+
+ _ASSERTE((m_pHash != NULL) && (m_oldTable == NULL));
+ // Add can be called only once on this object
+ _ASSERTE(!dbg_m_fAddCalled);
+
+ // Check that the hash table didn't change since call to code:PreallocateForAdd
+ _ASSERTE(dbg_m_table == m_pHash->m_table);
+ _ASSERTE(dbg_m_tableSize == m_pHash->m_tableSize);
+ _ASSERTE(dbg_m_tableCount >= m_pHash->m_tableCount); // Remove operation might have removed elements
+ _ASSERTE(dbg_m_tableOccupied == m_pHash->m_tableOccupied);
+ _ASSERTE(dbg_m_tableMax == m_pHash->m_tableMax);
+
+ if (m_newTable != NULL)
+ { // We have pre-allocated table from code:PreallocateForAdd, use it.
+ _ASSERTE(m_newTableSize != 0);
+
+ // May return NULL if there was not table allocated yet
+ m_oldTable = m_pHash->ReplaceTable(m_newTable, m_newTableSize);
+
+ m_newTable = NULL;
+ m_newTableSize = 0;
+ }
+ // We know that we have enough space, direcly add the element
+ m_pHash->Add_GrowthChecked(element);
+
+ INDEBUG(dbg_m_fAddCalled = TRUE;)
+
+ RETURN;
+}
+
+template <typename TRAITS>
+void SHash<TRAITS>::AddPhases::AddNothing_PublishPreallocatedTable()
+{
+ CONTRACT_VOID
+ {
+ NOTHROW_UNLESS_TRAITS_THROWS;
+ GC_NOTRIGGER;
+ }
+ CONTRACT_END;
+
+ _ASSERTE((m_pHash != NULL) && (m_oldTable == NULL));
+ // Add can be called only once on this object
+ _ASSERTE(!dbg_m_fAddCalled);
+
+ // Check that the hash table didn't change since call to code:PreallocateForAdd
+ _ASSERTE(dbg_m_table == m_pHash->m_table);
+ _ASSERTE(dbg_m_tableSize == m_pHash->m_tableSize);
+ _ASSERTE(dbg_m_tableCount >= m_pHash->m_tableCount); // Remove operation might have removed elements
+ _ASSERTE(dbg_m_tableOccupied == m_pHash->m_tableOccupied);
+ _ASSERTE(dbg_m_tableMax == m_pHash->m_tableMax);
+
+ if (m_newTable != NULL)
+ { // We have pre-allocated table from code:PreallocateForAdd, use it.
+ _ASSERTE(m_newTableSize != 0);
+
+ // May return NULL if there was not table allocated yet
+ m_oldTable = m_pHash->ReplaceTable(m_newTable, m_newTableSize);
+
+ m_newTable = NULL;
+ m_newTableSize = 0;
+ }
+
+ INDEBUG(dbg_m_fAddCalled = TRUE;)
+
+ RETURN;
+}
+
+template <typename TRAITS>
+void SHash<TRAITS>::AddPhases::DeleteOldTable()
+{
+ LIMITED_METHOD_CONTRACT;
+
+ if (m_oldTable != NULL)
+ {
+ _ASSERTE((m_pHash != NULL) && (m_newTable == NULL) && (m_newTableSize == 0));
+
+ delete [] m_oldTable;
+ m_oldTable = NULL;
+ }
+}
+
+template <typename TRAITS>
+template <typename LockHolderT,
+ typename AddLockHolderT,
+ typename LockT,
+ typename AddLockT>
+bool SHash<TRAITS>::CheckAddInPhases(
+ element_t const & elem,
+ LockT & lock,
+ AddLockT & addLock,
+ IUnknown * addRefObject)
+{
+ CONTRACTL
+ {
+ THROWS;
+ GC_NOTRIGGER;
+ INSTANCE_CHECK;
+ }
+ CONTRACTL_END;
+
+ AddLockHolderT hAddLock(&addLock);
+ AddPhases addCall;
+
+ // 1. Preallocate one element
+ addCall.PreallocateForAdd(this);
+ {
+ // 2. Take the reader lock. Host callouts now forbidden.
+ LockHolderT hLock(&lock);
+
+ element_t const * pEntry = LookupPtr(TRAITS::GetKey(elem));
+ if (pEntry != nullptr)
+ {
+ // 3a. Use the newly allocated table (if any) to avoid later redundant allocation.
+ addCall.AddNothing_PublishPreallocatedTable();
+ return false;
+ }
+ else
+ {
+ // 3b. Add the element to the hash table.
+ addCall.Add(elem);
+
+ if (addRefObject != nullptr)
+ {
+ clr::SafeAddRef(addRefObject);
+ }
+
+ return true;
+ }
+ }
+
+ // 4. addCall's destructor will take care of any required cleanup.
+}
+
+
+#endif // _SHASH_INL_