include/mcld/ADT/HashTable.tcc

//===- HashTable.tcc ---------------------------------------------------------===//
//
//                     The MCLinker Project
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//

//===--------------------------------------------------------------------===//
// template implementation of HashTable
template<typename HashEntryTy,
         typename HashFunctionTy,
         typename EntryFactoryTy>
HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::HashTable(size_type pSize)
  : HashTableImpl<HashEntryTy, HashFunctionTy>(pSize), m_EntryFactory()
{
}

template<typename HashEntryTy,
         typename HashFunctionTy,
         typename EntryFactoryTy>
HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::~HashTable()
{
  if (BaseTy::empty())
    return;

  /** clean up **/
  for (unsigned int i=0; i < BaseTy::m_NumOfBuckets; ++i) {
    if (bucket_type::getEmptyBucket() != BaseTy::m_Buckets[i].Entry &&
        bucket_type::getTombstone() != BaseTy::m_Buckets[i].Entry ) {
      m_EntryFactory.destroy(BaseTy::m_Buckets[i].Entry);
    }
  }
}

template<typename HashEntryTy,
         typename HashFunctionTy,
         typename EntryFactoryTy>
void HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::clear()
{
  if (BaseTy::empty())
    return;

  /** clean up **/
  for (unsigned int i=0; i < BaseTy::m_NumOfBuckets; ++i) {
    if (bucket_type::getEmptyBucket() != BaseTy::m_Buckets[i].Entry ) {
      if (bucket_type::getTombstone() != BaseTy::m_Buckets[i].Entry ) {
        m_EntryFactory.destroy(BaseTy::m_Buckets[i].Entry);
      }
      BaseTy::m_Buckets[i].Entry = bucket_type::getEmptyBucket();
    }
  }
  BaseTy::m_NumOfEntries = 0;
  BaseTy::m_NumOfTombstones = 0;
}

/// insert - insert a new element to the container. If the element already
//  exist, return the element.
template<typename HashEntryTy,
         typename HashFunctionTy,
         typename EntryFactoryTy>
typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::entry_type*
HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::insert(
  const typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::key_type& pKey,
  bool& pExist)
{
  unsigned int index = BaseTy::lookUpBucketFor(pKey);
  bucket_type& bucket = BaseTy::m_Buckets[index];
  entry_type* entry = bucket.Entry;
  if (bucket_type::getEmptyBucket() != entry &&
      bucket_type::getTombstone() != entry) {
    // Already exist in the table
    pExist = true;
    return entry;
  }

  // find a tombstone
  if (bucket_type::getTombstone() == entry)
    --BaseTy::m_NumOfTombstones;

  entry = bucket.Entry = m_EntryFactory.produce(pKey);
  ++BaseTy::m_NumOfEntries;
  BaseTy::mayRehash();
  pExist = false;
  return entry;
}

/// erase - remove the elements with the pKey
//  @return the number of removed elements.
template<typename HashEntryTy,
         typename HashFunctionTy,
         typename EntryFactoryTy>
typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::size_type
HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::erase(
        const typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::key_type& pKey)
{
  int index;
  if (-1 == (index = BaseTy::findKey(pKey)))
    return 0;

  bucket_type& bucket = BaseTy::m_Buckets[index];
  m_EntryFactory.destroy(bucket.Entry);
  bucket.Entry = bucket_type::getTombstone();

  --BaseTy::m_NumOfEntries;
  ++BaseTy::m_NumOfTombstones;
  BaseTy::mayRehash();
  return 1;
}

template<typename HashEntryTy,
         typename HashFunctionTy,
         typename EntryFactoryTy>
typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::iterator
HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::find(
  const typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::key_type& pKey)
{
  int index;
  if (-1 == (index = BaseTy::findKey(pKey)))
    return end();
  return iterator(this, index);
}

template<typename HashEntryTy,
         typename HashFunctionTy,
         typename EntryFactoryTy>
typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_iterator
HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::find(
  const typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::key_type& pKey) const
{
  int index;
  if (-1 == (index = BaseTy::findKey(pKey)))
    return end();
  return const_iterator(this, index);
}

template<typename HashEntryTy,
         typename HashFunctionTy,
         typename EntryFactoryTy>
typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::size_type
HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::count(
  const typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::key_type& pKey) const
{
  const_chain_iterator bucket, bEnd = end(pKey);
  size_type count = 0;
  for (bucket = begin(pKey); bucket != bEnd; ++bucket)
    ++count;
  return count;
}

template<typename HashEntryTy,
         typename HashFunctionTy,
         typename EntryFactoryTy>
float HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::load_factor() const
{
  return ((float)BaseTy::m_NumOfEntries/(float)BaseTy::m_NumOfBuckets);
}

template<typename HashEntryTy,
         typename HashFunctionTy,
         typename EntryFactoryTy>
void
HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::rehash()
{
  BaseTy::mayRehash();
}

template<typename HashEntryTy,
         typename HashFunctionTy,
         typename EntryFactoryTy>
void
HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::rehash(
       typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::size_type pCount)
{
  BaseTy::doRehash(pCount);
}

template<typename HashEntryTy,
         typename HashFunctionTy,
         typename EntryFactoryTy>
typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::iterator
HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::begin()
{
  if (BaseTy::empty())
    return end();
  unsigned int index = 0;
  while (bucket_type::getTombstone() == BaseTy::m_Buckets[index].Entry ||
         bucket_type::getEmptyBucket() == BaseTy::m_Buckets[index].Entry) {
    ++index;
  }
  return iterator(this, index);
}

template<typename HashEntryTy,
         typename HashFunctionTy,
         typename EntryFactoryTy>
typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::iterator
HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::end()
{
  return iterator(NULL, 0);
}

template<typename HashEntryTy,
         typename HashFunctionTy,
         typename EntryFactoryTy>
typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_iterator
HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::begin() const
{
  if (BaseTy::empty())
    return end();
  unsigned int index = 0;
  while (bucket_type::getTombstone() == BaseTy::m_Buckets[index].Entry ||
         bucket_type::getEmptyBucket() == BaseTy::m_Buckets[index].Entry) {
    ++index;
  }
  return const_iterator(this, index);
}

template<typename HashEntryTy,
         typename HashFunctionTy,
         typename EntryFactoryTy>
typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_iterator
HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::end() const
{
  return const_iterator(NULL, 0);
}

template<typename HashEntryTy,
         typename HashFunctionTy,
         typename EntryFactoryTy>
typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::chain_iterator
HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::begin(
    const typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::key_type& pKey)
{
  return chain_iterator(this, pKey, 0x0);
}

template<typename HashEntryTy,
         typename HashFunctionTy,
         typename EntryFactoryTy>
typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::chain_iterator
HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::end(
    const typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::key_type& pKey)
{
  return chain_iterator();
}

template<typename HashEntryTy,
         typename HashFunctionTy,
         typename EntryFactoryTy>
typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_chain_iterator
HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::begin(
  const typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::key_type& pKey) const
{
  return const_chain_iterator(this, pKey, 0x0);
}

template<typename HashEntryTy,
         typename HashFunctionTy,
         typename EntryFactoryTy>
typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_chain_iterator
HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::end(
  const typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::key_type& pKey) const
{
  return const_chain_iterator();
}