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 24 namespace mcld 25 { 26 27 struct 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 37 template<typename ValueType, 38 typename KeyType> 39 struct 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 49 uint32_t findNextPrime(uint32_t x); 50 51 /** \class StringUnorderedMap 52 * \brief The most simple hash of linked list version. 53 * 54 * \see 55 */ 56 template<typename KeyType, 57 typename ValueType, 58 typename KeyCompareFunctor, 59 typename HashFunction = StringUnorderedMapDefaultHash, 60 typename Allocator = std::allocator<std::pair<KeyType, ValueType> > > 61 class StringUnorderedMap 62 { 63 public: 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 84 private: 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 93 private: 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 104 template<typename ValueType, 105 typename KeyStorageType, 106 typename HashFunction, 107 typename Allocator> 108 StringUnorderedMap<ValueType, KeyStorageType, HashFunction, Allocator>:: 109 StringUnorderedMapImpl::StringUnorderedMapImpl(size_t pCapacity) 110 : m_Capacity(0), m_Size(0), m_HashTable(0) 111 { 112 this->reserve(pCapacity); 113 } 114 115 template<typename ValueType, 116 typename KeyStorageType, 117 typename HashFunction, 118 typename Allocator> 119 void 120 StringUnorderedMap<ValueType, KeyStorageType, HashFunction, Allocator>:: 121 StringUnorderedMapImpl::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 132 template<typename ValueType, 133 typename KeyStorageType, 134 typename HashFunction, 135 typename Allocator> 136 void 137 StringUnorderedMap<ValueType, KeyStorageType, HashFunction, Allocator>:: 138 StringUnorderedMapImpl::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 156 template<typename ValueType, 157 typename KeyStorageType, 158 typename HashFunction, 159 typename Allocator> 160 template<typename InitType> 161 ValueType & 162 StringUnorderedMap<ValueType, KeyStorageType, HashFunction, Allocator>:: 163 StringUnorderedMapImpl::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 190 template<typename ValueType, 191 typename KeyStorageType, 192 typename HashFunction, 193 typename Allocator> 194 void 195 StringUnorderedMap<ValueType, KeyStorageType, HashFunction, Allocator>:: 196 StringUnorderedMapImpl::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 211 template<typename ValueType, 212 typename KeyStorageType, 213 typename HashFunction, 214 typename Allocator> 215 StringUnorderedMap<ValueType, KeyStorageType, HashFunction, Allocator>:: 216 StringUnorderedMapImpl::~StringUnorderedMapImpl() 217 { 218 this->clear(); 219 } 220 221 222 } // namespace of mcld 223 224 #endif 225 226
