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 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* 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* 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> 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> 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> 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> 89 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> 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> 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 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 173 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> 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> 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
