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