blob: 74399825babca06e71b0dc185e17b9b8c6892bf0 [file] [log] [blame]
//===- 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();
}