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