blob: 165f4ae481284f0fbe76a9a616b7a8fcf6148a70 [file] [log] [blame]
//===- HashBase.tcc -------------------------------------------------------===//
//
// The MCLinker Project
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//===--------------------------------------------------------------------===//
// internal non-member functions
inline static unsigned int compute_bucket_count(unsigned int pNumOfBuckets)
{
static const unsigned int bucket_size[] =
{
1, 3, 17, 37, 67, 97, 197, 419, 977, 2593, 4099, 8209, 12289,
16411, 20483, 32771, 49157, 65537, 98317, 131101, 196613
};
const unsigned int buckets_count =
sizeof(bucket_size) / sizeof(bucket_size[0]);
unsigned int idx = 0;
do {
if (pNumOfBuckets < bucket_size[idx]) {
return bucket_size[idx];
}
++idx;
} while(idx < buckets_count);
return (pNumOfBuckets+131101); // rare case. increase constantly
}
//===--------------------------------------------------------------------===//
// template implementation of HashBucket
template<typename DataType>
typename HashBucket<DataType>::entry_type*
HashBucket<DataType>::getEmptyBucket()
{
static entry_type* empty_bucket = reinterpret_cast<entry_type*>(0x0);
return empty_bucket;
}
template<typename DataType>
typename HashBucket<DataType>::entry_type*
HashBucket<DataType>::getTombstone()
{
static entry_type* tombstone = reinterpret_cast<entry_type*>(0x1);
return tombstone;
}
//===--------------------------------------------------------------------===//
// template implementation of HashTableImpl
template<typename HashEntryTy,
typename HashFunctionTy>
HashTableImpl<HashEntryTy, HashFunctionTy>::HashTableImpl()
: m_Buckets(0),
m_NumOfBuckets(0),
m_NumOfEntries(0),
m_NumOfTombstones(0),
m_Hasher() {
}
template<typename HashEntryTy,
typename HashFunctionTy>
HashTableImpl<HashEntryTy, HashFunctionTy>::HashTableImpl(
unsigned int pInitSize)
: m_Hasher() {
if (pInitSize) {
init(pInitSize);
return;
}
m_Buckets = 0;
m_NumOfBuckets = 0;
m_NumOfEntries = 0;
m_NumOfTombstones = 0;
}
template<typename HashEntryTy,
typename HashFunctionTy>
HashTableImpl<HashEntryTy, HashFunctionTy>::~HashTableImpl()
{
clear();
}
/// empty - check if the hash table is empty
template<typename HashEntryTy,
typename HashFunctionTy>
bool HashTableImpl<HashEntryTy, HashFunctionTy>::empty() const
{
return (0 == m_NumOfEntries);
}
/// init - initialize the hash table.
template<typename HashEntryTy,
typename HashFunctionTy>
void HashTableImpl<HashEntryTy, HashFunctionTy>::init(unsigned int pInitSize)
{
m_NumOfBuckets = pInitSize? compute_bucket_count(pInitSize): NumOfInitBuckets;
m_NumOfEntries = 0;
m_NumOfTombstones = 0;
/** calloc also set bucket.Item = bucket_type::getEmptyStone() **/
m_Buckets = (bucket_type*)calloc(m_NumOfBuckets, sizeof(bucket_type));
}
/// clear - clear the hash table.
template<typename HashEntryTy,
typename HashFunctionTy>
void HashTableImpl<HashEntryTy, HashFunctionTy>::clear()
{
free(m_Buckets);
m_Buckets = 0;
m_NumOfBuckets = 0;
m_NumOfEntries = 0;
m_NumOfTombstones = 0;
}
/// lookUpBucketFor - look up the bucket whose key is pKey
template<typename HashEntryTy,
typename HashFunctionTy>
unsigned int
HashTableImpl<HashEntryTy, HashFunctionTy>::lookUpBucketFor(
const typename HashTableImpl<HashEntryTy, HashFunctionTy>::key_type& pKey)
{
if (0 == m_NumOfBuckets) {
// NumOfBuckets is changed after init(pInitSize)
init(NumOfInitBuckets);
}
unsigned int full_hash = m_Hasher(pKey);
unsigned int index = full_hash % m_NumOfBuckets;
const unsigned int probe = 1;
int firstTombstone = -1;
// linear probing
while(true) {
bucket_type& bucket = m_Buckets[index];
// If we found an empty bucket, this key isn't in the table yet, return it.
if (bucket_type::getEmptyBucket() == bucket.Entry) {
if (-1 != firstTombstone) {
m_Buckets[firstTombstone].FullHashValue = full_hash;
return firstTombstone;
}
bucket.FullHashValue = full_hash;
return index;
}
if (bucket_type::getTombstone() == bucket.Entry) {
if (-1 == firstTombstone) {
firstTombstone = index;
}
}
else if (bucket.FullHashValue == full_hash) {
if (bucket.Entry->compare(pKey)) {
return index;
}
}
index += probe;
if (index == m_NumOfBuckets)
index = 0;
}
}
template<typename HashEntryTy,
typename HashFunctionTy>
int
HashTableImpl<HashEntryTy, HashFunctionTy>::findKey(
const typename HashTableImpl<HashEntryTy, HashFunctionTy>::key_type& pKey) const
{
if (0 == m_NumOfBuckets)
return -1;
unsigned int full_hash = m_Hasher(pKey);
unsigned int index = full_hash % m_NumOfBuckets;
const unsigned int probe = 1;
// linear probing
while (true) {
bucket_type &bucket = m_Buckets[index];
if (bucket_type::getEmptyBucket() == bucket.Entry)
return -1;
if (bucket_type::getTombstone() == bucket.Entry) {
// Ignore tombstones.
}
else if (full_hash == bucket.FullHashValue) {
// get string, compare, if match, return index
if (bucket.Entry->compare(pKey))
return index;
}
index += probe;
if (index == m_NumOfBuckets)
index = 0;
}
}
template<typename HashEntryTy,
typename HashFunctionTy>
void HashTableImpl<HashEntryTy, HashFunctionTy>::mayRehash()
{
unsigned int new_size;
// If the hash table is now more than 3/4 full, or if fewer than 1/8 of
// the buckets are empty (meaning that many are filled with tombstones),
// grow/rehash the table.
if ((m_NumOfEntries<<2) > m_NumOfBuckets*3)
new_size = compute_bucket_count(m_NumOfBuckets);
else if (((m_NumOfBuckets-(m_NumOfEntries+m_NumOfTombstones))<<3) < m_NumOfBuckets)
new_size = m_NumOfBuckets;
else
return;
doRehash(new_size);
}
template<typename HashEntryTy,
typename HashFunctionTy>
void HashTableImpl<HashEntryTy, HashFunctionTy>::doRehash(unsigned int pNewSize)
{
bucket_type* new_table = (bucket_type*)calloc(pNewSize, sizeof(bucket_type));
// Rehash all the items into their new buckets. Luckily :) we already have
// the hash values available, so we don't have to recall hash function again.
for (bucket_type *IB = m_Buckets, *E = m_Buckets+m_NumOfBuckets; IB != E; ++IB) {
if (IB->Entry != bucket_type::getEmptyBucket() &&
IB->Entry != bucket_type::getTombstone()) {
// Fast case, bucket available.
unsigned full_hash = IB->FullHashValue;
unsigned new_bucket = full_hash % pNewSize;
if (bucket_type::getEmptyBucket() == new_table[new_bucket].Entry) {
new_table[new_bucket].Entry = IB->Entry;
new_table[new_bucket].FullHashValue = full_hash;
continue;
}
// Otherwise probe for a spot.
const unsigned int probe = 1;
do {
new_bucket += probe;
if (new_bucket == pNewSize)
new_bucket = 0;
} while (new_table[new_bucket].Entry != bucket_type::getEmptyBucket());
// Finally found a slot. Fill it in.
new_table[new_bucket].Entry = IB->Entry;
new_table[new_bucket].FullHashValue = full_hash;
}
}
free(m_Buckets);
m_Buckets = new_table;
m_NumOfBuckets = pNewSize;
m_NumOfTombstones = 0;
}