HashTable.tcc revision 22add6ff3426df1a85089fe6a6e1597ee3b6f300
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(size_type pSize) 16 : HashTableImpl<HashEntryTy, HashFunctionTy>(pSize), m_EntryFactory() 17{ 18} 19 20template<typename HashEntryTy, 21 typename HashFunctionTy, 22 typename EntryFactoryTy> 23HashTable<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 37template<typename HashEntryTy, 38 typename HashFunctionTy, 39 typename EntryFactoryTy> 40void 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. 60template<typename HashEntryTy, 61 typename HashFunctionTy, 62 typename EntryFactoryTy> 63typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::entry_type* 64HashTable<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. 91template<typename HashEntryTy, 92 typename HashFunctionTy, 93 typename EntryFactoryTy> 94typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::size_type 95HashTable<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 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, 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 125template<typename HashEntryTy, 126 typename HashFunctionTy, 127 typename EntryFactoryTy> 128typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_iterator 129HashTable<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 138template<typename HashEntryTy, 139 typename HashFunctionTy, 140 typename EntryFactoryTy> 141typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::size_type 142HashTable<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 152template<typename HashEntryTy, 153 typename HashFunctionTy, 154 typename EntryFactoryTy> 155float HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::load_factor() const 156{ 157 return ((float)BaseTy::m_NumOfEntries/(float)BaseTy::m_NumOfBuckets); 158} 159 160template<typename HashEntryTy, 161 typename HashFunctionTy, 162 typename EntryFactoryTy> 163void 164HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::rehash() 165{ 166 BaseTy::mayRehash(); 167} 168 169template<typename HashEntryTy, 170 typename HashFunctionTy, 171 typename EntryFactoryTy> 172void 173HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::rehash( 174 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::size_type pCount) 175{ 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{ 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 195template<typename HashEntryTy, 196 typename HashFunctionTy, 197 typename EntryFactoryTy> 198typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::iterator 199HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::end() 200{ 201 return iterator(NULL, 0); 202} 203 204template<typename HashEntryTy, 205 typename HashFunctionTy, 206 typename EntryFactoryTy> 207typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_iterator 208HashTable<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 220template<typename HashEntryTy, 221 typename HashFunctionTy, 222 typename EntryFactoryTy> 223typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_iterator 224HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::end() const 225{ 226 return const_iterator(NULL, 0); 227} 228 229template<typename HashEntryTy, 230 typename HashFunctionTy, 231 typename EntryFactoryTy> 232typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::chain_iterator 233HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::begin( 234 const typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::key_type& pKey) 235{ 236 return chain_iterator(this, pKey, 0x0); 237} 238 239template<typename HashEntryTy, 240 typename HashFunctionTy, 241 typename EntryFactoryTy> 242typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::chain_iterator 243HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::end( 244 const typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::key_type& pKey) 245{ 246 return chain_iterator(); 247} 248 249template<typename HashEntryTy, 250 typename HashFunctionTy, 251 typename EntryFactoryTy> 252typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_chain_iterator 253HashTable<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 259template<typename HashEntryTy, 260 typename HashFunctionTy, 261 typename EntryFactoryTy> 262typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_chain_iterator 263HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::end( 264 const typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::key_type& pKey) const 265{ 266 return const_chain_iterator(); 267} 268 269