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