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 //===----------------------------------------------------------------------===// 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* 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* 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> 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> 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> 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> 92 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> 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> 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 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 176 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> 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> 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
