From 4b4aad7217d3292650e77eec2cf4c198ea9c3b4b Mon Sep 17 00:00:00 2001 From: Jiyoung Yun Date: Wed, 23 Nov 2016 19:09:09 +0900 Subject: Imported Upstream version 1.1.0 --- src/inc/simplerhash.inl | 350 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 350 insertions(+) create mode 100644 src/inc/simplerhash.inl (limited to 'src/inc/simplerhash.inl') diff --git a/src/inc/simplerhash.inl b/src/inc/simplerhash.inl new file mode 100644 index 0000000000..dc72acba26 --- /dev/null +++ b/src/inc/simplerhash.inl @@ -0,0 +1,350 @@ +// 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 _SIMPLERHASHTABLE_INL_ +#define _SIMPLERHASHTABLE_INL_ + +// To implement magic-number divide with a 32-bit magic number, +// multiply by the magic number, take the top 64 bits, and shift that +// by the amount given in the table. + +inline +unsigned magicNumberDivide(unsigned numerator, const PrimeInfo &p) +{ + unsigned __int64 num = numerator; + unsigned __int64 mag = p.magic; + unsigned __int64 product = (num * mag) >> (32 + p.shift); + return (unsigned) product; +} + +inline +unsigned magicNumberRem(unsigned numerator, const PrimeInfo &p) +{ + unsigned div = magicNumberDivide(numerator, p); + unsigned result = numerator - (div * p.prime); + assert(result == numerator % p.prime); + return result; +} + +template +SimplerHashTable::SimplerHashTable(IAllocator* alloc) + : m_alloc(alloc), + m_table(NULL), + m_tableSizeInfo(), + m_tableCount(0), + m_tableMax(0) +{ + assert(m_alloc != nullptr); + +#ifndef __GNUC__ // these crash GCC + static_assert_no_msg(Behavior::s_growth_factor_numerator > Behavior::s_growth_factor_denominator); + static_assert_no_msg(Behavior::s_density_factor_numerator < Behavior::s_density_factor_denominator); +#endif +} + +template +SimplerHashTable::~SimplerHashTable() +{ + RemoveAll(); +} + +template +void * SimplerHashTable::operator new(size_t sz, IAllocator * alloc) +{ + return alloc->Alloc(sz); +} + +template +void * SimplerHashTable::operator new[](size_t sz, IAllocator * alloc) +{ + return alloc->Alloc(sz); +} + +template +void SimplerHashTable::operator delete(void * p, IAllocator * alloc) +{ + alloc->Free(p); +} + +template +void SimplerHashTable::operator delete[](void * p, IAllocator * alloc) +{ + alloc->Free(p); +} + +template +unsigned SimplerHashTable::GetCount() const +{ + return m_tableCount; +} + +template +bool SimplerHashTable::Lookup(Key key, Value* pVal) const +{ + Node* pN = FindNode(key); + + if (pN != NULL) + { + if (pVal != NULL) + { + *pVal = pN->m_val; + } + return true; + } + else + { + return false; + } +} + +template +Value *SimplerHashTable::LookupPointer(Key key) const +{ + Node* pN = FindNode(key); + + if (pN != NULL) + return &(pN->m_val); + else + return NULL; +} + +template +typename SimplerHashTable::Node* +SimplerHashTable::FindNode(Key k) const +{ + if (m_tableSizeInfo.prime == 0) + return NULL; + + unsigned index = GetIndexForKey(k); + + Node* pN = m_table[index]; + if (pN == NULL) + return NULL; + + // Otherwise... + while (pN != NULL && !KeyFuncs::Equals(k, pN->m_key)) + pN = pN->m_next; + + assert(pN == NULL || KeyFuncs::Equals(k, pN->m_key)); + + // If pN != NULL, it's the node for the key, else the key isn't mapped. + return pN; +} + +template +unsigned SimplerHashTable::GetIndexForKey(Key k) const +{ + unsigned hash = KeyFuncs::GetHashCode(k); + + unsigned index = magicNumberRem(hash, m_tableSizeInfo); + + return index; +} + +template +bool SimplerHashTable::Set(Key k, Value v) +{ + CheckGrowth(); + + assert(m_tableSizeInfo.prime != 0); + + unsigned index = GetIndexForKey(k); + + Node* pN = m_table[index]; + while (pN != NULL && !KeyFuncs::Equals(k, pN->m_key)) + { + pN = pN->m_next; + } + if (pN != NULL) + { + pN->m_val = v; + return true; + } + else + { + Node* pNewNode = new (m_alloc) Node(k, v, m_table[index]); + m_table[index] = pNewNode; + m_tableCount++; + return false; + } +} + +template +bool SimplerHashTable::Remove(Key k) +{ + unsigned index = GetIndexForKey(k); + + Node* pN = m_table[index]; + Node** ppN = &m_table[index]; + while (pN != NULL && !KeyFuncs::Equals(k, pN->m_key)) + { + ppN = &pN->m_next; + pN = pN->m_next; + } + if (pN != NULL) + { + *ppN = pN->m_next; + m_tableCount--; + Node::operator delete(pN, m_alloc); + return true; + } + else + { + return false; + } +} + +template +void SimplerHashTable::RemoveAll() +{ + for (unsigned i = 0; i < m_tableSizeInfo.prime; i++) + { + for (Node* pN = m_table[i]; pN != NULL; ) + { + Node* pNext = pN->m_next; + Node::operator delete(pN, m_alloc); + pN = pNext; + } + } + m_alloc->Free(m_table); + + m_table = NULL; + m_tableSizeInfo = PrimeInfo(); + m_tableCount = 0; + m_tableMax = 0; + + return; +} + +template +typename SimplerHashTable::KeyIterator SimplerHashTable::Begin() const +{ + KeyIterator i(this, TRUE); + return i; +} + +template +typename SimplerHashTable::KeyIterator SimplerHashTable::End() const +{ + return KeyIterator(this, FALSE); +} + +template +void SimplerHashTable::CheckGrowth() +{ + if (m_tableCount == m_tableMax) + { + Grow(); + } +} + +template +void SimplerHashTable::Grow() +{ + unsigned newSize = (unsigned) (m_tableCount + * Behavior::s_growth_factor_numerator / Behavior::s_growth_factor_denominator + * Behavior::s_density_factor_denominator / Behavior::s_density_factor_numerator); + if (newSize < Behavior::s_minimum_allocation) + newSize = Behavior::s_minimum_allocation; + + // handle potential overflow + if (newSize < m_tableCount) + Behavior::NoMemory(); + + Reallocate(newSize); +} + +template +void SimplerHashTable::Reallocate(unsigned newTableSize) +{ + assert(newTableSize >= (GetCount() * Behavior::s_density_factor_denominator / Behavior::s_density_factor_numerator)); + + // 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. + PrimeInfo newPrime = NextPrime(newTableSize); + newTableSize = newPrime.prime; + + Node** newTable = (Node**)m_alloc->ArrayAlloc(newTableSize, sizeof(Node*)); + + for (unsigned i = 0; i < newTableSize; i++) { + newTable[i] = NULL; + } + + // Move all entries over to new table (re-using the Node structures.) + + for (unsigned i = 0; i < m_tableSizeInfo.prime; i++) + { + Node* pN = m_table[i]; + while (pN != NULL) + { + Node* pNext = pN->m_next; + + unsigned newIndex = magicNumberRem(KeyFuncs::GetHashCode(pN->m_key), newPrime); + pN->m_next = newTable[newIndex]; + newTable[newIndex] = pN; + + pN = pNext; + } + } + + // @todo: + // We might want to try to delay this cleanup to allow asynchronous readers + if (m_table != NULL) + m_alloc->Free(m_table); + + m_table = newTable; + m_tableSizeInfo = newPrime; + m_tableMax = (unsigned) (newTableSize * Behavior::s_density_factor_numerator / Behavior::s_density_factor_denominator); +} + +// Table of primes and their magic-number-divide constant. +// For more info see the book "Hacker's Delight" chapter 10.9 "Unsigned Division by Divisors >= 1" +// These were selected by looking for primes, each roughly twice as big as the next, having +// 32-bit magic numbers, (because the algorithm for using 33-bit magic numbers is slightly slower). +// + +SELECTANY const PrimeInfo primeInfo[] = +{ + PrimeInfo(9, 0x38e38e39, 1), + PrimeInfo(23, 0xb21642c9, 4), + PrimeInfo(59, 0x22b63cbf, 3), + PrimeInfo(131, 0xfa232cf3, 7), + PrimeInfo(239, 0x891ac73b, 7), + PrimeInfo(433, 0x975a751, 4), + PrimeInfo(761, 0x561e46a5, 8), + PrimeInfo(1399, 0xbb612aa3, 10), + PrimeInfo(2473, 0x6a009f01, 10), + PrimeInfo(4327, 0xf2555049, 12), + PrimeInfo(7499, 0x45ea155f, 11), + PrimeInfo(12973, 0x1434f6d3, 10), + PrimeInfo(22433, 0x2ebe18db, 12), + PrimeInfo(46559, 0xb42bebd5, 15), + PrimeInfo(96581, 0xadb61b1b, 16), + PrimeInfo(200341, 0x29df2461, 15), + PrimeInfo(415517, 0xa181c46d, 18), + PrimeInfo(861719, 0x4de0bde5, 18), + PrimeInfo(1787021, 0x9636c46f, 20), + PrimeInfo(3705617, 0x4870adc1, 20), + PrimeInfo(7684087, 0x8bbc5b83, 22), + PrimeInfo(15933877, 0x86c65361, 23), + PrimeInfo(33040633, 0x40fec79b, 23), + PrimeInfo(68513161, 0x7d605cd1, 25), + PrimeInfo(142069021, 0xf1da390b, 27), + PrimeInfo(294594427, 0x74a2507d, 27), + PrimeInfo(733045421, 0x5dbec447, 28), +}; + +template +PrimeInfo SimplerHashTable::NextPrime(unsigned number) +{ + for (int i = 0; i < (int) (sizeof(primeInfo) / sizeof(primeInfo[0])); i++) { + if (primeInfo[i].prime >= number) + return primeInfo[i]; + } + + // overflow + Behavior::NoMemory(); +} + +#endif // _SIMPLERHASHTABLE_INL_ -- cgit v1.2.3