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