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