//===- StringUnorderedMap.h -----------------------------------------------===//
//
// The MCLinker Project
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
#ifndef MCLD_SEARCH_TABLE_H
#define MCLD_SEARCH_TABLE_H
#include <vector>
// For std::allocate.
#include <memory>
// For uint32_t.
#include <stdint.h>
#include <cassert>
// For memset.
#include <cstring>
#ifdef ENABLE_UNITTEST
#include <gtest.h>
#endif
/* FIXME: Move StringUnorderedMap under ADT. */
namespace mcld
{
struct StringUnorderedMapDefaultHash
{
size_t operator()(const char *pStr) {
size_t hashVal = 31;
while (*pStr)
hashVal = hashVal * 131 + (*pStr++);
return hashVal;
}
};
template<typename ValueType,
typename KeyType>
struct StringUnorderedMapEntryInit
{
template <typename InitType>
void operator()(KeyType &pKey, ValueType &pValue,
const KeyType &pStr, InitType pInitVal) {
::new ((void*)&pKey) KeyStorageType(pStr);
::new ((void*)&pValue) ValueType(pInitVal);
}
};
uint32_t findNextPrime(uint32_t x);
/** \class StringUnorderedMap
* \brief The most simple hash of linked list version.
*
* \see
*/
template<typename KeyType,
typename ValueType,
typename KeyCompareFunctor,
typename HashFunction = StringUnorderedMapDefaultHash,
typename Allocator = std::allocator<std::pair<KeyType, ValueType> > >
class StringUnorderedMap
{
public:
explicit StringUnorderedMap(size_t pCapacity = 17)
: m_Impl(pCapacity)
{}
~StringUnorderedMap();
void reserve(size_t pCapacity);
ValueType &getOrCreate(const KeyType &pStr, const ValueType &pInitVal);
ValueType &getOrCreate(const KeyType &pStr);
bool empty()
{ return m_Size == 0; }
size_t capacity() const
{ return m_Capacity; }
void clear();
private:
struct HashEntry {
size_t hashVal;
std::pair<KeyType, ValueType>
HashEntry *next;
};
typedef Allocator::template rebind<HashEntry>::other HashEntryAllocator;
void rehash(size_t pCapacity);
private:
size_t m_Capacity;
size_t m_Size;
// array of pointers to hash entries
HashEntry **m_HashTable;
HashEntryAllocator m_HashEntryAllocator;
};
// =================================implementation============================
// StringUnorderedMap::StringUnorderedMapImpl
template<typename ValueType,
typename KeyStorageType,
typename HashFunction,
typename Allocator>
StringUnorderedMap<ValueType, KeyStorageType, HashFunction, Allocator>::
StringUnorderedMapImpl::StringUnorderedMapImpl(size_t pCapacity)
: m_Capacity(0), m_Size(0), m_HashTable(0)
{
this->reserve(pCapacity);
}
template<typename ValueType,
typename KeyStorageType,
typename HashFunction,
typename Allocator>
void
StringUnorderedMap<ValueType, KeyStorageType, HashFunction, Allocator>::
StringUnorderedMapImpl::reserve(size_t pCapacity)
{
if (pCapacity < this->m_Capacity)
return;
size_t nextSize = findNextPrime(static_cast<uint32_t>(pCapacity));
// FIXME: Error handling.
assert(nextSize > this->m_Capacity && "findNextPrime error.");
if (this->m_Capacity != nextSize)
this->rehash(nextSize);
}
template<typename ValueType,
typename KeyStorageType,
typename HashFunction,
typename Allocator>
void
StringUnorderedMap<ValueType, KeyStorageType, HashFunction, Allocator>::
StringUnorderedMapImpl::rehash(size_t pCapacity)
{
HashEntry **tmpTable = new HashEntry*[pCapacity];
std::memset(tmpTable, 0, pCapacity * sizeof(HashEntry*));
if (this->m_HashTable) {
for (size_t i = 0; i < this->m_Capacity; ++i)
for (HashEntry *j = this->m_HashTable[i]; j != 0; ) {
HashEntry *nextJ = j->next;
j->next = tmpTable[j->hashVal % pCapacity];
tmpTable[j->hashVal % pCapacity] = j;
j = nextJ;
}
delete[] m_HashTable;
}
this->m_Capacity = pCapacity;
this->m_HashTable = tmpTable;
}
template<typename ValueType,
typename KeyStorageType,
typename HashFunction,
typename Allocator>
template<typename InitType>
ValueType &
StringUnorderedMap<ValueType, KeyStorageType, HashFunction, Allocator>::
StringUnorderedMapImpl::getOrCreate(const KeyType &pStr, ValueType &pInitVal)
{
HashFunction hash;
size_t hashVal = hash(pStr);
HashEntry *&head = this->m_HashTable[hashVal % this->m_Capacity];
HashEntry *ans = 0;
for(HashEntry *ptr = head; ptr != 0; ptr = ptr->next)
if(hashVal == ptr->hashVal && pStr.equals(ptr->str)) {
ans = ptr;
break;
}
if (ans == 0) {
ans = this->allocate(1);
ans->hashVal = hashVal;
StringUnorderedMapEntryInit<ValueType, KeyStorageType> init;
init(ans->str, ans->value, pStr, pInitVal);
ans->next = head;
head = ans;
++m_Size;
if(this->m_Size * 4LL >= this->m_Capacity * 3LL) // load factor = 0.75
this->reserve(this->m_Capacity+1);
}
return ans->value;
}
template<typename ValueType,
typename KeyStorageType,
typename HashFunction,
typename Allocator>
void
StringUnorderedMap<ValueType, KeyStorageType, HashFunction, Allocator>::
StringUnorderedMapImpl::clear()
{
if (this->m_HashTable) {
for (size_t i = 0; i < this->m_Capacity; ++i)
for (HashEntry *j = this->m_HashTable[i]; j != 0; ) {
HashEntry *nextJ = j->next;
this->destroy(j);
this->deallocate(j, 1);
j = nextJ;
}
delete[] m_HashTable;
}
}
template<typename ValueType,
typename KeyStorageType,
typename HashFunction,
typename Allocator>
StringUnorderedMap<ValueType, KeyStorageType, HashFunction, Allocator>::
StringUnorderedMapImpl::~StringUnorderedMapImpl()
{
this->clear();
}
} // namespace of mcld
#endif