1 //===- HashBase.tcc -------------------------------------------------------===//
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
10 //===----------------------------------------------------------------------===//
11 // internal non-member functions
12 //===----------------------------------------------------------------------===//
compute_bucket_count(unsigned int pNumOfBuckets)13 inline static unsigned int compute_bucket_count(unsigned int pNumOfBuckets)
14 {
15 static const unsigned int bucket_size[] =
16 {
17 1, 3, 17, 37, 67, 97, 197, 419, 977, 2593, 4099, 8209, 12289,
18 16411, 20483, 32771, 49157, 65537, 98317, 131101, 196613
19 };
20
21 const unsigned int buckets_count =
22 sizeof(bucket_size) / sizeof(bucket_size[0]);
23 unsigned int idx = 0;
24 do {
25 if (pNumOfBuckets < bucket_size[idx]) {
26 return bucket_size[idx];
27 }
28 ++idx;
29 } while(idx < buckets_count);
30
31 return (pNumOfBuckets+131101); // rare case. increase constantly
32 }
33
34 //===----------------------------------------------------------------------===//
35 // template implementation of HashBucket
36 //===----------------------------------------------------------------------===//
37 template<typename DataType>
38 typename HashBucket<DataType>::entry_type*
getEmptyBucket()39 HashBucket<DataType>::getEmptyBucket()
40 {
41 static entry_type* empty_bucket = reinterpret_cast<entry_type*>(0x0);
42 return empty_bucket;
43 }
44
45 template<typename DataType>
46 typename HashBucket<DataType>::entry_type*
getTombstone()47 HashBucket<DataType>::getTombstone()
48 {
49 static entry_type* tombstone = reinterpret_cast<entry_type*>(0x1);
50 return tombstone;
51 }
52
53 //===----------------------------------------------------------------------===//
54 // template implementation of HashTableImpl
55 //===----------------------------------------------------------------------===//
56 template<typename HashEntryTy,
57 typename HashFunctionTy>
HashTableImpl()58 HashTableImpl<HashEntryTy, HashFunctionTy>::HashTableImpl()
59 : m_Buckets(0),
60 m_NumOfBuckets(0),
61 m_NumOfEntries(0),
62 m_NumOfTombstones(0),
63 m_Hasher() {
64 }
65
66 template<typename HashEntryTy,
67 typename HashFunctionTy>
HashTableImpl(unsigned int pInitSize)68 HashTableImpl<HashEntryTy, HashFunctionTy>::HashTableImpl(
69 unsigned int pInitSize)
70 : m_Hasher() {
71 if (pInitSize) {
72 init(pInitSize);
73 return;
74 }
75
76 m_Buckets = 0;
77 m_NumOfBuckets = 0;
78 m_NumOfEntries = 0;
79 m_NumOfTombstones = 0;
80 }
81
82 template<typename HashEntryTy,
83 typename HashFunctionTy>
~HashTableImpl()84 HashTableImpl<HashEntryTy, HashFunctionTy>::~HashTableImpl()
85 {
86 clear();
87 }
88
89 /// empty - check if the hash table is empty
90 template<typename HashEntryTy,
91 typename HashFunctionTy>
empty() const92 bool HashTableImpl<HashEntryTy, HashFunctionTy>::empty() const
93 {
94 return (0 == m_NumOfEntries);
95 }
96
97 /// init - initialize the hash table.
98 template<typename HashEntryTy,
99 typename HashFunctionTy>
init(unsigned int pInitSize)100 void HashTableImpl<HashEntryTy, HashFunctionTy>::init(unsigned int pInitSize)
101 {
102 m_NumOfBuckets = pInitSize? compute_bucket_count(pInitSize): NumOfInitBuckets;
103
104 m_NumOfEntries = 0;
105 m_NumOfTombstones = 0;
106
107 /** calloc also set bucket.Item = bucket_type::getEmptyStone() **/
108 m_Buckets = (bucket_type*)calloc(m_NumOfBuckets, sizeof(bucket_type));
109 }
110
111 /// clear - clear the hash table.
112 template<typename HashEntryTy,
113 typename HashFunctionTy>
clear()114 void HashTableImpl<HashEntryTy, HashFunctionTy>::clear()
115 {
116 free(m_Buckets);
117
118 m_Buckets = 0;
119 m_NumOfBuckets = 0;
120 m_NumOfEntries = 0;
121 m_NumOfTombstones = 0;
122 }
123
124 /// lookUpBucketFor - look up the bucket whose key is pKey
125 template<typename HashEntryTy,
126 typename HashFunctionTy>
127 unsigned int
lookUpBucketFor(const typename HashTableImpl<HashEntryTy,HashFunctionTy>::key_type & pKey)128 HashTableImpl<HashEntryTy, HashFunctionTy>::lookUpBucketFor(
129 const typename HashTableImpl<HashEntryTy, HashFunctionTy>::key_type& pKey)
130 {
131 if (0 == m_NumOfBuckets) {
132 // NumOfBuckets is changed after init(pInitSize)
133 init(NumOfInitBuckets);
134 }
135
136 unsigned int full_hash = m_Hasher(pKey);
137 unsigned int index = full_hash % m_NumOfBuckets;
138
139 const unsigned int probe = 1;
140 int firstTombstone = -1;
141
142 // linear probing
143 while(true) {
144 bucket_type& bucket = m_Buckets[index];
145 // If we found an empty bucket, this key isn't in the table yet, return it.
146 if (bucket_type::getEmptyBucket() == bucket.Entry) {
147 if (-1 != firstTombstone) {
148 m_Buckets[firstTombstone].FullHashValue = full_hash;
149 return firstTombstone;
150 }
151
152 bucket.FullHashValue = full_hash;
153 return index;
154 }
155
156 if (bucket_type::getTombstone() == bucket.Entry) {
157 if (-1 == firstTombstone) {
158 firstTombstone = index;
159 }
160 }
161 else if (bucket.FullHashValue == full_hash) {
162 if (bucket.Entry->compare(pKey)) {
163 return index;
164 }
165 }
166
167 index += probe;
168 if (index == m_NumOfBuckets)
169 index = 0;
170 }
171 }
172
173 template<typename HashEntryTy,
174 typename HashFunctionTy>
175 int
findKey(const typename HashTableImpl<HashEntryTy,HashFunctionTy>::key_type & pKey) const176 HashTableImpl<HashEntryTy, HashFunctionTy>::findKey(
177 const typename HashTableImpl<HashEntryTy, HashFunctionTy>::key_type& pKey) const
178 {
179 if (0 == m_NumOfBuckets)
180 return -1;
181
182 unsigned int full_hash = m_Hasher(pKey);
183 unsigned int index = full_hash % m_NumOfBuckets;
184
185 const unsigned int probe = 1;
186 // linear probing
187 while (true) {
188 bucket_type &bucket = m_Buckets[index];
189
190 if (bucket_type::getEmptyBucket() == bucket.Entry)
191 return -1;
192
193 if (bucket_type::getTombstone() == bucket.Entry) {
194 // Ignore tombstones.
195 }
196 else if (full_hash == bucket.FullHashValue) {
197 // get string, compare, if match, return index
198 if (bucket.Entry->compare(pKey))
199 return index;
200 }
201 index += probe;
202 if (index == m_NumOfBuckets)
203 index = 0;
204 }
205 }
206
207 template<typename HashEntryTy,
208 typename HashFunctionTy>
mayRehash()209 void HashTableImpl<HashEntryTy, HashFunctionTy>::mayRehash()
210 {
211
212 unsigned int new_size;
213 // If the hash table is now more than 3/4 full, or if fewer than 1/8 of
214 // the buckets are empty (meaning that many are filled with tombstones),
215 // grow/rehash the table.
216 if ((m_NumOfEntries<<2) > m_NumOfBuckets*3)
217 new_size = compute_bucket_count(m_NumOfBuckets);
218 else if (((m_NumOfBuckets-(m_NumOfEntries+m_NumOfTombstones))<<3) < m_NumOfBuckets)
219 new_size = m_NumOfBuckets;
220 else
221 return;
222
223 doRehash(new_size);
224 }
225
226 template<typename HashEntryTy,
227 typename HashFunctionTy>
doRehash(unsigned int pNewSize)228 void HashTableImpl<HashEntryTy, HashFunctionTy>::doRehash(unsigned int pNewSize)
229 {
230 bucket_type* new_table = (bucket_type*)calloc(pNewSize, sizeof(bucket_type));
231
232 // Rehash all the items into their new buckets. Luckily :) we already have
233 // the hash values available, so we don't have to recall hash function again.
234 for (bucket_type *IB = m_Buckets, *E = m_Buckets+m_NumOfBuckets; IB != E; ++IB) {
235 if (IB->Entry != bucket_type::getEmptyBucket() &&
236 IB->Entry != bucket_type::getTombstone()) {
237 // Fast case, bucket available.
238 unsigned full_hash = IB->FullHashValue;
239 unsigned new_bucket = full_hash % pNewSize;
240 if (bucket_type::getEmptyBucket() == new_table[new_bucket].Entry) {
241 new_table[new_bucket].Entry = IB->Entry;
242 new_table[new_bucket].FullHashValue = full_hash;
243 continue;
244 }
245
246 // Otherwise probe for a spot.
247 const unsigned int probe = 1;
248 do {
249 new_bucket += probe;
250 if (new_bucket == pNewSize)
251 new_bucket = 0;
252 } while (new_table[new_bucket].Entry != bucket_type::getEmptyBucket());
253
254 // Finally found a slot. Fill it in.
255 new_table[new_bucket].Entry = IB->Entry;
256 new_table[new_bucket].FullHashValue = full_hash;
257 }
258 }
259
260 free(m_Buckets);
261
262 m_Buckets = new_table;
263 m_NumOfBuckets = pNewSize;
264 m_NumOfTombstones = 0;
265 }
266
267