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