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 {
operatorStringUnorderedMapDefaultHash29 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>
operatorStringUnorderedMapEntryInit42 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)
m_Impl(pCapacity)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
empty()76 bool empty()
77 { return m_Size == 0; }
78
capacity()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>::
StringUnorderedMapImpl(size_t pCapacity)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>::
reserve(size_t pCapacity)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>::
rehash(size_t pCapacity)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>::
getOrCreate(const KeyType & pStr,ValueType & pInitVal)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>::
clear()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>::
~StringUnorderedMapImpl()216 StringUnorderedMapImpl::~StringUnorderedMapImpl()
217 {
218 this->clear();
219 }
220
221
222 } // namespace of mcld
223
224 #endif
225
226