HashBase.tcc revision 5460a1f25d9ddecb5c70667267d66d51af177a99
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 12inline 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 35template<typename DataType> 36typename HashBucket<DataType>::entry_type* 37HashBucket<DataType>::getEmptyBucket() 38{ 39 static entry_type* empty_bucket = reinterpret_cast<entry_type*>(0x0); 40 return empty_bucket; 41} 42 43template<typename DataType> 44typename HashBucket<DataType>::entry_type* 45HashBucket<DataType>::getTombstone() 46{ 47 static entry_type* tombstone = reinterpret_cast<entry_type*>(0x1); 48 return tombstone; 49} 50 51//===--------------------------------------------------------------------===// 52// template implementation of HashTableImpl 53template<typename HashEntryTy, 54 typename HashFunctionTy> 55HashTableImpl<HashEntryTy, HashFunctionTy>::HashTableImpl() 56 : m_Buckets(0), 57 m_NumOfBuckets(0), 58 m_NumOfEntries(0), 59 m_NumOfTombstones(0), 60 m_Hasher() { 61} 62 63template<typename HashEntryTy, 64 typename HashFunctionTy> 65HashTableImpl<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 79template<typename HashEntryTy, 80 typename HashFunctionTy> 81HashTableImpl<HashEntryTy, HashFunctionTy>::~HashTableImpl() 82{ 83 free(m_Buckets); 84} 85 86/// empty - check if the hash table is empty 87template<typename HashEntryTy, 88 typename HashFunctionTy> 89bool HashTableImpl<HashEntryTy, HashFunctionTy>::empty() const 90{ 91 return (0 == m_NumOfEntries); 92} 93 94/// init - initialize the hash table. 95template<typename HashEntryTy, 96 typename HashFunctionTy> 97void 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/// lookUpBucketFor - look up the bucket whose key is pKey 109template<typename HashEntryTy, 110 typename HashFunctionTy> 111unsigned int 112HashTableImpl<HashEntryTy, HashFunctionTy>::lookUpBucketFor( 113 const typename HashTableImpl<HashEntryTy, HashFunctionTy>::key_type& pKey) 114{ 115 if (0 == m_NumOfBuckets) { 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 (-1 != firstTombstone) { 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 (-1 == firstTombstone) { 142 firstTombstone = index; 143 } 144 } 145 else if (bucket.FullHashValue == full_hash) { 146 if (bucket.Entry->compare(pKey)) { 147 return index; 148 } 149 } 150 151 index += probe; 152 if (index == m_NumOfBuckets) 153 index = 0; 154 } 155} 156 157template<typename HashEntryTy, 158 typename HashFunctionTy> 159int 160HashTableImpl<HashEntryTy, HashFunctionTy>::findKey( 161 const typename HashTableImpl<HashEntryTy, HashFunctionTy>::key_type& pKey) const 162{ 163 if (0 == m_NumOfBuckets) 164 return -1; 165 166 unsigned int full_hash = m_Hasher(pKey); 167 unsigned int index = full_hash % m_NumOfBuckets; 168 169 const unsigned int probe = 1; 170 // linear probing 171 while (true) { 172 bucket_type &bucket = m_Buckets[index]; 173 174 if (bucket_type::getEmptyBucket() == bucket.Entry) 175 return -1; 176 177 if (bucket_type::getTombstone() == bucket.Entry) { 178 // Ignore tombstones. 179 } 180 else if (full_hash == bucket.FullHashValue) { 181 // get string, compare, if match, return index 182 if (bucket.Entry->compare(pKey)) 183 return index; 184 } 185 index += probe; 186 if (index == m_NumOfBuckets) 187 index = 0; 188 } 189} 190 191template<typename HashEntryTy, 192 typename HashFunctionTy> 193void HashTableImpl<HashEntryTy, HashFunctionTy>::mayRehash() 194{ 195 196 unsigned int new_size; 197 // If the hash table is now more than 3/4 full, or if fewer than 1/8 of 198 // the buckets are empty (meaning that many are filled with tombstones), 199 // grow/rehash the table. 200 if ((m_NumOfEntries<<2) > m_NumOfBuckets*3) 201 new_size = compute_bucket_count(m_NumOfBuckets); 202 else if (((m_NumOfBuckets-(m_NumOfEntries+m_NumOfTombstones))<<3) < m_NumOfBuckets) 203 new_size = m_NumOfBuckets; 204 else 205 return; 206 207 doRehash(new_size); 208} 209 210template<typename HashEntryTy, 211 typename HashFunctionTy> 212void HashTableImpl<HashEntryTy, HashFunctionTy>::doRehash(unsigned int pNewSize) 213{ 214 bucket_type* new_table = (bucket_type*)calloc(pNewSize, sizeof(bucket_type)); 215 216 // Rehash all the items into their new buckets. Luckily :) we already have 217 // the hash values available, so we don't have to recall hash function again. 218 for (bucket_type *IB = m_Buckets, *E = m_Buckets+m_NumOfBuckets; IB != E; ++IB) { 219 if (IB->Entry != bucket_type::getEmptyBucket() && 220 IB->Entry != bucket_type::getTombstone()) { 221 // Fast case, bucket available. 222 unsigned full_hash = IB->FullHashValue; 223 unsigned new_bucket = full_hash % pNewSize; 224 if (bucket_type::getEmptyBucket() == new_table[new_bucket].Entry) { 225 new_table[new_bucket].Entry = IB->Entry; 226 new_table[new_bucket].FullHashValue = full_hash; 227 continue; 228 } 229 230 // Otherwise probe for a spot. 231 const unsigned int probe = 1; 232 do { 233 new_bucket += probe; 234 if (new_bucket == pNewSize) 235 new_bucket = 0; 236 } while (new_table[new_bucket].Entry != bucket_type::getEmptyBucket()); 237 238 // Finally found a slot. Fill it in. 239 new_table[new_bucket].Entry = IB->Entry; 240 new_table[new_bucket].FullHashValue = full_hash; 241 } 242 } 243 244 free(m_Buckets); 245 246 m_Buckets = new_table; 247 m_NumOfBuckets = pNewSize; 248 m_NumOfTombstones = 0; 249} 250 251