1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
|
//===- 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
|
