1 //===- HashTable.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 // template implementation of HashTable 12 template<typename HashEntryTy, 13 typename HashFunctionTy, 14 typename EntryFactoryTy> 15 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::HashTable(size_type pSize) 16 : HashTableImpl<HashEntryTy, HashFunctionTy>(pSize), m_EntryFactory() 17 { 18 } 19 20 template<typename HashEntryTy, 21 typename HashFunctionTy, 22 typename EntryFactoryTy> 23 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::~HashTable() 24 { 25 if (BaseTy::empty()) 26 return; 27 28 /** clean up **/ 29 for (unsigned int i=0; i < BaseTy::m_NumOfBuckets; ++i) { 30 if (bucket_type::getEmptyBucket() != BaseTy::m_Buckets[i].Entry && 31 bucket_type::getTombstone() != BaseTy::m_Buckets[i].Entry ) { 32 m_EntryFactory.destroy(BaseTy::m_Buckets[i].Entry); 33 } 34 } 35 } 36 37 template<typename HashEntryTy, 38 typename HashFunctionTy, 39 typename EntryFactoryTy> 40 void HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::clear() 41 { 42 if (BaseTy::empty()) 43 return; 44 45 /** clean up **/ 46 for (unsigned int i=0; i < BaseTy::m_NumOfBuckets; ++i) { 47 if (bucket_type::getEmptyBucket() != BaseTy::m_Buckets[i].Entry ) { 48 if (bucket_type::getTombstone() != BaseTy::m_Buckets[i].Entry ) { 49 m_EntryFactory.destroy(BaseTy::m_Buckets[i].Entry); 50 } 51 BaseTy::m_Buckets[i].Entry = bucket_type::getEmptyBucket(); 52 } 53 } 54 55 BaseTy::clear(); 56 } 57 58 /// insert - insert a new element to the container. If the element already 59 // exist, return the element. 60 template<typename HashEntryTy, 61 typename HashFunctionTy, 62 typename EntryFactoryTy> 63 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::entry_type* 64 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::insert( 65 const typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::key_type& pKey, 66 bool& pExist) 67 { 68 unsigned int index = BaseTy::lookUpBucketFor(pKey); 69 bucket_type& bucket = BaseTy::m_Buckets[index]; 70 entry_type* entry = bucket.Entry; 71 if (bucket_type::getEmptyBucket() != entry && 72 bucket_type::getTombstone() != entry) { 73 // Already exist in the table 74 pExist = true; 75 return entry; 76 } 77 78 // find a tombstone 79 if (bucket_type::getTombstone() == entry) 80 --BaseTy::m_NumOfTombstones; 81 82 entry = bucket.Entry = m_EntryFactory.produce(pKey); 83 ++BaseTy::m_NumOfEntries; 84 BaseTy::mayRehash(); 85 pExist = false; 86 return entry; 87 } 88 89 /// erase - remove the elements with the pKey 90 // @return the number of removed elements. 91 template<typename HashEntryTy, 92 typename HashFunctionTy, 93 typename EntryFactoryTy> 94 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::size_type 95 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::erase( 96 const typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::key_type& pKey) 97 { 98 int index; 99 if (-1 == (index = BaseTy::findKey(pKey))) 100 return 0; 101 102 bucket_type& bucket = BaseTy::m_Buckets[index]; 103 m_EntryFactory.destroy(bucket.Entry); 104 bucket.Entry = bucket_type::getTombstone(); 105 106 --BaseTy::m_NumOfEntries; 107 ++BaseTy::m_NumOfTombstones; 108 BaseTy::mayRehash(); 109 return 1; 110 } 111 112 template<typename HashEntryTy, 113 typename HashFunctionTy, 114 typename EntryFactoryTy> 115 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::iterator 116 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::find( 117 const typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::key_type& pKey) 118 { 119 int index; 120 if (-1 == (index = BaseTy::findKey(pKey))) 121 return end(); 122 return iterator(this, index); 123 } 124 125 template<typename HashEntryTy, 126 typename HashFunctionTy, 127 typename EntryFactoryTy> 128 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_iterator 129 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::find( 130 const typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::key_type& pKey) const 131 { 132 int index; 133 if (-1 == (index = BaseTy::findKey(pKey))) 134 return end(); 135 return const_iterator(this, index); 136 } 137 138 template<typename HashEntryTy, 139 typename HashFunctionTy, 140 typename EntryFactoryTy> 141 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::size_type 142 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::count( 143 const typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::key_type& pKey) const 144 { 145 const_chain_iterator bucket, bEnd = end(pKey); 146 size_type count = 0; 147 for (bucket = begin(pKey); bucket != bEnd; ++bucket) 148 ++count; 149 return count; 150 } 151 152 template<typename HashEntryTy, 153 typename HashFunctionTy, 154 typename EntryFactoryTy> 155 float HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::load_factor() const 156 { 157 return ((float)BaseTy::m_NumOfEntries/(float)BaseTy::m_NumOfBuckets); 158 } 159 160 template<typename HashEntryTy, 161 typename HashFunctionTy, 162 typename EntryFactoryTy> 163 void 164 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::rehash() 165 { 166 BaseTy::mayRehash(); 167 } 168 169 template<typename HashEntryTy, 170 typename HashFunctionTy, 171 typename EntryFactoryTy> 172 void 173 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::rehash( 174 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::size_type pCount) 175 { 176 BaseTy::doRehash(pCount); 177 } 178 179 template<typename HashEntryTy, 180 typename HashFunctionTy, 181 typename EntryFactoryTy> 182 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::iterator 183 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::begin() 184 { 185 if (BaseTy::empty()) 186 return end(); 187 unsigned int index = 0; 188 while (bucket_type::getTombstone() == BaseTy::m_Buckets[index].Entry || 189 bucket_type::getEmptyBucket() == BaseTy::m_Buckets[index].Entry) { 190 ++index; 191 } 192 return iterator(this, index); 193 } 194 195 template<typename HashEntryTy, 196 typename HashFunctionTy, 197 typename EntryFactoryTy> 198 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::iterator 199 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::end() 200 { 201 return iterator(NULL, 0); 202 } 203 204 template<typename HashEntryTy, 205 typename HashFunctionTy, 206 typename EntryFactoryTy> 207 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_iterator 208 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::begin() const 209 { 210 if (BaseTy::empty()) 211 return end(); 212 unsigned int index = 0; 213 while (bucket_type::getTombstone() == BaseTy::m_Buckets[index].Entry || 214 bucket_type::getEmptyBucket() == BaseTy::m_Buckets[index].Entry) { 215 ++index; 216 } 217 return const_iterator(this, index); 218 } 219 220 template<typename HashEntryTy, 221 typename HashFunctionTy, 222 typename EntryFactoryTy> 223 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_iterator 224 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::end() const 225 { 226 return const_iterator(NULL, 0); 227 } 228 229 template<typename HashEntryTy, 230 typename HashFunctionTy, 231 typename EntryFactoryTy> 232 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::chain_iterator 233 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::begin( 234 const typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::key_type& pKey) 235 { 236 return chain_iterator(this, pKey, 0x0); 237 } 238 239 template<typename HashEntryTy, 240 typename HashFunctionTy, 241 typename EntryFactoryTy> 242 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::chain_iterator 243 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::end( 244 const typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::key_type& pKey) 245 { 246 return chain_iterator(); 247 } 248 249 template<typename HashEntryTy, 250 typename HashFunctionTy, 251 typename EntryFactoryTy> 252 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_chain_iterator 253 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::begin( 254 const typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::key_type& pKey) const 255 { 256 return const_chain_iterator(this, pKey, 0x0); 257 } 258 259 template<typename HashEntryTy, 260 typename HashFunctionTy, 261 typename EntryFactoryTy> 262 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_chain_iterator 263 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::end( 264 const typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::key_type& pKey) const 265 { 266 return const_chain_iterator(); 267 } 268 269
