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