1//===- StringUnorderedMap.h -----------------------------------------------===// 2// 3// The MCLinker Project 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9#ifndef MCLD_SEARCH_TABLE_H 10#define MCLD_SEARCH_TABLE_H 11#include <vector> 12// For std::allocate. 13#include <memory> 14// For uint32_t. 15#include <stdint.h> 16#include <cassert> 17// For memset. 18#include <cstring> 19#ifdef ENABLE_UNITTEST 20#include <gtest.h> 21#endif 22/* FIXME: Move StringUnorderedMap under ADT. */ 23 24namespace mcld 25{ 26 27struct StringUnorderedMapDefaultHash 28{ 29 size_t operator()(const char *pStr) { 30 size_t hashVal = 31; 31 while (*pStr) 32 hashVal = hashVal * 131 + (*pStr++); 33 return hashVal; 34 } 35}; 36 37template<typename ValueType, 38 typename KeyType> 39struct StringUnorderedMapEntryInit 40{ 41 template <typename InitType> 42 void operator()(KeyType &pKey, ValueType &pValue, 43 const KeyType &pStr, InitType pInitVal) { 44 ::new ((void*)&pKey) KeyStorageType(pStr); 45 ::new ((void*)&pValue) ValueType(pInitVal); 46 } 47}; 48 49uint32_t findNextPrime(uint32_t x); 50 51/** \class StringUnorderedMap 52 * \brief The most simple hash of linked list version. 53 * 54 * \see 55 */ 56template<typename KeyType, 57 typename ValueType, 58 typename KeyCompareFunctor, 59 typename HashFunction = StringUnorderedMapDefaultHash, 60 typename Allocator = std::allocator<std::pair<KeyType, ValueType> > > 61class StringUnorderedMap 62{ 63public: 64 explicit StringUnorderedMap(size_t pCapacity = 17) 65 : m_Impl(pCapacity) 66 {} 67 68 ~StringUnorderedMap(); 69 70 void reserve(size_t pCapacity); 71 72 ValueType &getOrCreate(const KeyType &pStr, const ValueType &pInitVal); 73 74 ValueType &getOrCreate(const KeyType &pStr); 75 76 bool empty() 77 { return m_Size == 0; } 78 79 size_t capacity() const 80 { return m_Capacity; } 81 82 void clear(); 83 84private: 85 struct HashEntry { 86 size_t hashVal; 87 std::pair<KeyType, ValueType> 88 HashEntry *next; 89 }; 90 typedef Allocator::template rebind<HashEntry>::other HashEntryAllocator; 91 void rehash(size_t pCapacity); 92 93private: 94 size_t m_Capacity; 95 size_t m_Size; 96 // array of pointers to hash entries 97 HashEntry **m_HashTable; 98 HashEntryAllocator m_HashEntryAllocator; 99}; 100 101 102// =================================implementation============================ 103// StringUnorderedMap::StringUnorderedMapImpl 104template<typename ValueType, 105 typename KeyStorageType, 106 typename HashFunction, 107 typename Allocator> 108StringUnorderedMap<ValueType, KeyStorageType, HashFunction, Allocator>:: 109StringUnorderedMapImpl::StringUnorderedMapImpl(size_t pCapacity) 110 : m_Capacity(0), m_Size(0), m_HashTable(0) 111{ 112 this->reserve(pCapacity); 113} 114 115template<typename ValueType, 116 typename KeyStorageType, 117 typename HashFunction, 118 typename Allocator> 119void 120StringUnorderedMap<ValueType, KeyStorageType, HashFunction, Allocator>:: 121StringUnorderedMapImpl::reserve(size_t pCapacity) 122{ 123 if (pCapacity < this->m_Capacity) 124 return; 125 size_t nextSize = findNextPrime(static_cast<uint32_t>(pCapacity)); 126 // FIXME: Error handling. 127 assert(nextSize > this->m_Capacity && "findNextPrime error."); 128 if (this->m_Capacity != nextSize) 129 this->rehash(nextSize); 130} 131 132template<typename ValueType, 133 typename KeyStorageType, 134 typename HashFunction, 135 typename Allocator> 136void 137StringUnorderedMap<ValueType, KeyStorageType, HashFunction, Allocator>:: 138StringUnorderedMapImpl::rehash(size_t pCapacity) 139{ 140 HashEntry **tmpTable = new HashEntry*[pCapacity]; 141 std::memset(tmpTable, 0, pCapacity * sizeof(HashEntry*)); 142 if (this->m_HashTable) { 143 for (size_t i = 0; i < this->m_Capacity; ++i) 144 for (HashEntry *j = this->m_HashTable[i]; j != 0; ) { 145 HashEntry *nextJ = j->next; 146 j->next = tmpTable[j->hashVal % pCapacity]; 147 tmpTable[j->hashVal % pCapacity] = j; 148 j = nextJ; 149 } 150 delete[] m_HashTable; 151 } 152 this->m_Capacity = pCapacity; 153 this->m_HashTable = tmpTable; 154} 155 156template<typename ValueType, 157 typename KeyStorageType, 158 typename HashFunction, 159 typename Allocator> 160template<typename InitType> 161ValueType & 162StringUnorderedMap<ValueType, KeyStorageType, HashFunction, Allocator>:: 163StringUnorderedMapImpl::getOrCreate(const KeyType &pStr, ValueType &pInitVal) 164{ 165 HashFunction hash; 166 size_t hashVal = hash(pStr); 167 HashEntry *&head = this->m_HashTable[hashVal % this->m_Capacity]; 168 169 HashEntry *ans = 0; 170 for(HashEntry *ptr = head; ptr != 0; ptr = ptr->next) 171 if(hashVal == ptr->hashVal && pStr.equals(ptr->str)) { 172 ans = ptr; 173 break; 174 } 175 if (ans == 0) { 176 ans = this->allocate(1); 177 ans->hashVal = hashVal; 178 StringUnorderedMapEntryInit<ValueType, KeyStorageType> init; 179 init(ans->str, ans->value, pStr, pInitVal); 180 ans->next = head; 181 head = ans; 182 ++m_Size; 183 if(this->m_Size * 4LL >= this->m_Capacity * 3LL) // load factor = 0.75 184 this->reserve(this->m_Capacity+1); 185 } 186 187 return ans->value; 188} 189 190template<typename ValueType, 191 typename KeyStorageType, 192 typename HashFunction, 193 typename Allocator> 194void 195StringUnorderedMap<ValueType, KeyStorageType, HashFunction, Allocator>:: 196StringUnorderedMapImpl::clear() 197{ 198 if (this->m_HashTable) { 199 for (size_t i = 0; i < this->m_Capacity; ++i) 200 for (HashEntry *j = this->m_HashTable[i]; j != 0; ) { 201 HashEntry *nextJ = j->next; 202 this->destroy(j); 203 this->deallocate(j, 1); 204 j = nextJ; 205 } 206 delete[] m_HashTable; 207 } 208} 209 210 211template<typename ValueType, 212 typename KeyStorageType, 213 typename HashFunction, 214 typename Allocator> 215StringUnorderedMap<ValueType, KeyStorageType, HashFunction, Allocator>:: 216StringUnorderedMapImpl::~StringUnorderedMapImpl() 217{ 218 this->clear(); 219} 220 221 222} // namespace of mcld 223 224#endif 225