include/mcld/LD/StringUnorderedMap.h

//===- 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