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