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( 16 size_type pSize) 17 : HashTableImpl<HashEntryTy, HashFunctionTy>(pSize), m_EntryFactory() { 18 } 19 20 template <typename HashEntryTy, 21 typename HashFunctionTy, 22 typename EntryFactoryTy> 23 HashTable<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 36 template <typename HashEntryTy, 37 typename HashFunctionTy, 38 typename EntryFactoryTy> 39 void 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. 58 template <typename HashEntryTy, 59 typename HashFunctionTy, 60 typename EntryFactoryTy> 61 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::entry_type* 62 HashTable<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. 90 template <typename HashEntryTy, 91 typename HashFunctionTy, 92 typename EntryFactoryTy> 93 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::size_type 94 HashTable<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 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, 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 126 template <typename HashEntryTy, 127 typename HashFunctionTy, 128 typename EntryFactoryTy> 129 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_iterator 130 HashTable<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 140 template <typename HashEntryTy, 141 typename HashFunctionTy, 142 typename EntryFactoryTy> 143 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::size_type 144 HashTable<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 155 template <typename HashEntryTy, 156 typename HashFunctionTy, 157 typename EntryFactoryTy> 158 float HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::load_factor() 159 const { 160 return ((float)BaseTy::m_NumOfEntries / (float)BaseTy::m_NumOfBuckets); 161 } 162 163 template <typename HashEntryTy, 164 typename HashFunctionTy, 165 typename EntryFactoryTy> 166 void HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::rehash() { 167 BaseTy::mayRehash(); 168 } 169 170 template <typename HashEntryTy, 171 typename HashFunctionTy, 172 typename EntryFactoryTy> 173 void HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::rehash( 174 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::size_type 175 pCount) { 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 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 194 template <typename HashEntryTy, 195 typename HashFunctionTy, 196 typename EntryFactoryTy> 197 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::iterator 198 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::end() { 199 return iterator(NULL, 0); 200 } 201 202 template <typename HashEntryTy, 203 typename HashFunctionTy, 204 typename EntryFactoryTy> 205 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_iterator 206 HashTable<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 217 template <typename HashEntryTy, 218 typename HashFunctionTy, 219 typename EntryFactoryTy> 220 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_iterator 221 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::end() const { 222 return const_iterator(NULL, 0); 223 } 224 225 template <typename HashEntryTy, 226 typename HashFunctionTy, 227 typename EntryFactoryTy> 228 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::chain_iterator 229 HashTable<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 236 template <typename HashEntryTy, 237 typename HashFunctionTy, 238 typename EntryFactoryTy> 239 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::chain_iterator 240 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::end( 241 const typename HashTable<HashEntryTy, 242 HashFunctionTy, 243 EntryFactoryTy>::key_type& pKey) { 244 return chain_iterator(); 245 } 246 247 template <typename HashEntryTy, 248 typename HashFunctionTy, 249 typename EntryFactoryTy> 250 typename HashTable<HashEntryTy, 251 HashFunctionTy, 252 EntryFactoryTy>::const_chain_iterator 253 HashTable<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 260 template <typename HashEntryTy, 261 typename HashFunctionTy, 262 typename EntryFactoryTy> 263 typename HashTable<HashEntryTy, 264 HashFunctionTy, 265 EntryFactoryTy>::const_chain_iterator 266 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::end( 267 const typename HashTable<HashEntryTy, 268 HashFunctionTy, 269 EntryFactoryTy>::key_type& pKey) const { 270 return const_chain_iterator(); 271 } 272
