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 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* 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* 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> 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> 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> 77 HashTableImpl<HashEntryTy, HashFunctionTy>::~HashTableImpl() { 78 clear(); 79 } 80 81 /// empty - check if the hash table is empty 82 template <typename HashEntryTy, typename HashFunctionTy> 83 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> 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> 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> 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> 157 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> 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> 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
