1 //===- HashIterator.h -----------------------------------------------------===// 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 #ifndef MCLD_HASH_ITERATOR_H 10 #define MCLD_HASH_ITERATOR_H 11 #ifdef ENABLE_UNITTEST 12 #include <gtest.h> 13 #endif 14 15 #include <cstddef> 16 17 namespace mcld { 18 19 /** \class ChainIteratorBase 20 * \brief ChaintIteratorBase follows the HashEntryTy with the same hash value. 21 */ 22 template<typename HashTableImplTy> 23 class ChainIteratorBase 24 { 25 public: 26 typedef HashTableImplTy hash_table; 27 typedef typename HashTableImplTy::key_type key_type; 28 typedef typename HashTableImplTy::entry_type entry_type; 29 typedef typename HashTableImplTy::bucket_type bucket_type; 30 31 public: 32 ChainIteratorBase() 33 : m_pHashTable(0), m_Index(0), m_HashValue(0), m_EndIndex(0) 34 { } 35 36 ChainIteratorBase(HashTableImplTy* pTable, const key_type& pKey) 37 : m_pHashTable(pTable) 38 { 39 m_HashValue = pTable->hash()(pKey); 40 m_EndIndex = m_Index = m_HashValue % m_pHashTable->m_NumOfBuckets; 41 const unsigned int probe = 1; 42 while(true) { 43 bucket_type &bucket = m_pHashTable->m_Buckets[m_Index]; 44 if (bucket_type::getTombstone() == bucket.Entry) { 45 // Ignore tombstones. 46 } 47 else if (m_HashValue == bucket.FullHashValue) { 48 if (bucket.Entry->compare(pKey)) { 49 m_EndIndex = m_Index; 50 break; 51 } 52 } 53 m_Index += probe; 54 if (m_Index == m_pHashTable->m_NumOfBuckets) 55 m_Index = 0; 56 // doesn't exist 57 if (m_EndIndex == m_Index) { 58 reset(); 59 break; 60 } 61 } 62 } 63 64 ChainIteratorBase(const ChainIteratorBase& pCopy) 65 : m_pHashTable(pCopy.m_pHashTable), 66 m_Index(pCopy.m_Index), 67 m_HashValue(pCopy.m_HashValue), 68 m_EndIndex(pCopy.m_EndIndex) 69 { } 70 71 ChainIteratorBase& assign(const ChainIteratorBase& pCopy) { 72 m_pHashTable = pCopy.m_pHashTable; 73 m_Index = pCopy.m_Index; 74 m_HashValue = pCopy.m_HashValue; 75 m_EndIndex = pCopy.m_EndIndex; 76 return *this; 77 } 78 79 inline bucket_type* getBucket() { 80 if (0 == m_pHashTable) 81 return 0; 82 return &(m_pHashTable->m_Buckets[m_Index]); 83 } 84 85 inline const bucket_type* getBucket() const { 86 if (0 == m_pHashTable) 87 return 0; 88 return &(m_pHashTable->m_Buckets[m_Index]); 89 } 90 91 inline entry_type* getEntry() { 92 if (0 == m_pHashTable) 93 return 0; 94 return m_pHashTable->m_Buckets[m_Index].Entry; 95 } 96 97 inline const entry_type* getEntry() const { 98 if (0 == m_pHashTable) 99 return 0; 100 return m_pHashTable->m_Buckets[m_Index].Entry; 101 } 102 103 inline void reset() { 104 m_pHashTable = 0; 105 m_Index = 0; 106 m_EndIndex = 0; 107 m_HashValue = 0; 108 } 109 110 inline void advance() { 111 if (0 == m_pHashTable) 112 return; 113 const unsigned int probe = 1; 114 while(true) { 115 m_Index += probe; 116 if (m_Index == m_pHashTable->m_NumOfBuckets) 117 m_Index = 0; 118 // reach end() 119 if (m_Index == m_EndIndex) { 120 reset(); 121 return; 122 } 123 124 bucket_type &bucket = m_pHashTable->m_Buckets[m_Index]; 125 126 if (bucket_type::getTombstone() == bucket.Entry || 127 bucket_type::getEmptyBucket() == bucket.Entry) { 128 // Ignore tombstones. 129 } 130 else if (m_HashValue == bucket.FullHashValue) { 131 return; 132 } 133 } 134 } 135 136 bool operator==(const ChainIteratorBase& pCopy) const { 137 if (m_pHashTable == pCopy.m_pHashTable) { 138 if (0 == m_pHashTable) 139 return true; 140 return ((m_HashValue == pCopy.m_HashValue) && 141 (m_EndIndex == pCopy.m_EndIndex) && 142 (m_Index == pCopy.m_Index)); 143 } 144 return false; 145 } 146 147 bool operator!=(const ChainIteratorBase& pCopy) const 148 { return !(*this == pCopy); } 149 150 private: 151 HashTableImplTy* m_pHashTable; 152 unsigned int m_Index; 153 unsigned int m_HashValue; 154 unsigned int m_EndIndex; 155 }; 156 157 /** \class EntryIteratorBase 158 * \brief EntryIteratorBase walks over hash table by the natural layout of the 159 * buckets 160 */ 161 template<typename HashTableImplTy> 162 class EntryIteratorBase 163 { 164 public: 165 typedef HashTableImplTy hash_table; 166 typedef typename HashTableImplTy::key_type key_type; 167 typedef typename HashTableImplTy::entry_type entry_type; 168 typedef typename HashTableImplTy::bucket_type bucket_type; 169 170 public: 171 EntryIteratorBase() 172 : m_pHashTable(0), m_Index(0) 173 { } 174 175 EntryIteratorBase(HashTableImplTy* pTable, 176 unsigned int pIndex) 177 : m_pHashTable(pTable), m_Index(pIndex) 178 { } 179 180 EntryIteratorBase(const EntryIteratorBase& pCopy) 181 : m_pHashTable(pCopy.m_pHashTable), m_Index(pCopy.m_Index) 182 { } 183 184 EntryIteratorBase& assign(const EntryIteratorBase& pCopy) { 185 m_pHashTable = pCopy.m_pHashTable; 186 m_Index = pCopy.m_Index; 187 return *this; 188 } 189 190 inline bucket_type* getBucket() { 191 if (0 == m_pHashTable) 192 return 0; 193 return &(m_pHashTable->m_Buckets[m_Index]); 194 } 195 196 inline const bucket_type* getBucket() const { 197 if (0 == m_pHashTable) 198 return 0; 199 return &(m_pHashTable->m_Buckets[m_Index]); 200 } 201 202 inline entry_type* getEntry() { 203 if (0 == m_pHashTable) 204 return 0; 205 return m_pHashTable->m_Buckets[m_Index].Entry; 206 } 207 208 inline const entry_type* getEntry() const { 209 if (0 == m_pHashTable) 210 return 0; 211 return m_pHashTable->m_Buckets[m_Index].Entry; 212 } 213 214 inline void reset() { 215 m_pHashTable = 0; 216 m_Index = 0; 217 } 218 219 inline void advance() { 220 if (0 == m_pHashTable) 221 return; 222 do { 223 ++m_Index; 224 if (m_pHashTable->m_NumOfBuckets == m_Index) { // to the end 225 reset(); 226 return; 227 } 228 } while(bucket_type::getEmptyBucket() == m_pHashTable->m_Buckets[m_Index].Entry || 229 bucket_type::getTombstone() == m_pHashTable->m_Buckets[m_Index].Entry); 230 } 231 232 bool operator==(const EntryIteratorBase& pCopy) const 233 { return ((m_pHashTable == pCopy.m_pHashTable) && 234 (m_Index == pCopy.m_Index)); } 235 236 bool operator!=(const EntryIteratorBase& pCopy) const 237 { return !(*this == pCopy); } 238 239 private: 240 HashTableImplTy* m_pHashTable; 241 unsigned int m_Index; 242 243 }; 244 245 /** \class HashIterator 246 * \brief HashIterator provides a policy-based iterator. 247 * 248 * HashTable has two kinds of iterators. One is used to traverse buckets 249 * with the same hash value; the other is used to traverse all entries of the 250 * hash table. 251 * 252 * HashIterator is a template policy-based iterator, which can change its 253 * behavior by change the template argument IteratorBase. HashTable defines 254 * above two iterators by defining HashIterators with different IteratorBase. 255 */ 256 template<typename IteratorBase, 257 typename Traits> 258 class HashIterator : public IteratorBase 259 { 260 public: 261 typedef Traits traits; 262 typedef typename traits::pointer pointer; 263 typedef typename traits::reference reference; 264 typedef size_t size_type; 265 typedef ptrdiff_t difference_type; 266 typedef IteratorBase Base; 267 268 typedef HashIterator<IteratorBase, 269 Traits> Self; 270 271 typedef typename traits::nonconst_traits nonconst_traits; 272 typedef HashIterator<IteratorBase, 273 nonconst_traits> iterator; 274 275 typedef typename traits::const_traits const_traits; 276 typedef HashIterator<IteratorBase, 277 const_traits> const_iterator; 278 typedef std::forward_iterator_tag iterator_category; 279 280 public: 281 HashIterator() 282 : IteratorBase() 283 { } 284 285 /// HashIterator - constructor for EntryIterator 286 HashIterator(typename IteratorBase::hash_table* pTable, unsigned int pIndex) 287 : IteratorBase(pTable, pIndex) 288 { } 289 290 /// HashIterator - constructor for ChainIterator 291 explicit HashIterator(typename IteratorBase::hash_table* pTable, 292 const typename IteratorBase::key_type& pKey, 293 int) 294 : IteratorBase(pTable, pKey) 295 { } 296 297 HashIterator(const HashIterator& pCopy) 298 : IteratorBase(pCopy) 299 { } 300 301 ~HashIterator() 302 { } 303 304 HashIterator& operator=(const HashIterator& pCopy) { 305 IteratorBase::assign(pCopy); 306 return *this; 307 } 308 309 // ----- operators ----- // 310 Self& operator++() { 311 this->Base::advance(); 312 return *this; 313 } 314 315 Self operator++(int) { 316 Self tmp = *this; 317 this->Base::advance(); 318 return tmp; 319 } 320 }; 321 322 } // namespace of mcld 323 324 #endif 325 326
