include/mcld/ADT/HashBase.tcc

//===- 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()
{
  free(m_Buckets);
}

/// 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));
}

/// 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;
}