HashBase.tcc revision f33f6de54db174aa679a4b6d1e040d37e95541c0
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//===----------------------------------------------------------------------===// 13inline 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//===----------------------------------------------------------------------===// 37template<typename DataType> 38typename HashBucket<DataType>::entry_type* 39HashBucket<DataType>::getEmptyBucket() 40{ 41 static entry_type* empty_bucket = reinterpret_cast<entry_type*>(0x0); 42 return empty_bucket; 43} 44 45template<typename DataType> 46typename HashBucket<DataType>::entry_type* 47HashBucket<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//===----------------------------------------------------------------------===// 56template<typename HashEntryTy, 57 typename HashFunctionTy> 58HashTableImpl<HashEntryTy, HashFunctionTy>::HashTableImpl() 59 : m_Buckets(0), 60 m_NumOfBuckets(0), 61 m_NumOfEntries(0), 62 m_NumOfTombstones(0), 63 m_Hasher() { 64} 65 66template<typename HashEntryTy, 67 typename HashFunctionTy> 68HashTableImpl<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 82template<typename HashEntryTy, 83 typename HashFunctionTy> 84HashTableImpl<HashEntryTy, HashFunctionTy>::~HashTableImpl() 85{ 86 clear(); 87} 88 89/// empty - check if the hash table is empty 90template<typename HashEntryTy, 91 typename HashFunctionTy> 92bool HashTableImpl<HashEntryTy, HashFunctionTy>::empty() const 93{ 94 return (0 == m_NumOfEntries); 95} 96 97/// init - initialize the hash table. 98template<typename HashEntryTy, 99 typename HashFunctionTy> 100void 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. 112template<typename HashEntryTy, 113 typename HashFunctionTy> 114void 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 125template<typename HashEntryTy, 126 typename HashFunctionTy> 127unsigned int 128HashTableImpl<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 173template<typename HashEntryTy, 174 typename HashFunctionTy> 175int 176HashTableImpl<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 207template<typename HashEntryTy, 208 typename HashFunctionTy> 209void 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 226template<typename HashEntryTy, 227 typename HashFunctionTy> 228void 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