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
14namespace mcld {
15
16/** \class ChainIteratorBase
17 *  \brief ChaintIteratorBase follows the HashEntryTy with the same hash value.
18 */
19template<typename HashTableImplTy>
20class ChainIteratorBase
21{
22public:
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
28public:
29  ChainIteratorBase()
30  : m_pHashTable(0), m_Index(0), m_HashValue(0), m_EndIndex(0)
31  { }
32
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
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
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
76  inline bucket_type* getBucket() {
77    if (0 == m_pHashTable)
78      return 0;
79    return &(m_pHashTable->m_Buckets[m_Index]);
80  }
81
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
88  inline entry_type* getEntry() {
89    if (0 == m_pHashTable)
90      return 0;
91    return m_pHashTable->m_Buckets[m_Index].Entry;
92  }
93
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
100  inline void reset() {
101    m_pHashTable = 0;
102    m_Index = 0;
103    m_EndIndex = 0;
104    m_HashValue = 0;
105  }
106
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
147private:
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 */
158template<typename HashTableImplTy>
159class EntryIteratorBase
160{
161public:
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
167public:
168  EntryIteratorBase()
169  : m_pHashTable(0), m_Index(0)
170  { }
171
172  EntryIteratorBase(HashTableImplTy* pTable,
173                   unsigned int pIndex)
174  : m_pHashTable(pTable), m_Index(pIndex)
175  { }
176
177  EntryIteratorBase(const EntryIteratorBase& pCopy)
178  : m_pHashTable(pCopy.m_pHashTable), m_Index(pCopy.m_Index)
179  { }
180
181  EntryIteratorBase& assign(const EntryIteratorBase& pCopy) {
182    m_pHashTable = pCopy.m_pHashTable;
183    m_Index = pCopy.m_Index;
184    return *this;
185  }
186
187  inline bucket_type* getBucket() {
188    if (0 == m_pHashTable)
189      return 0;
190    return &(m_pHashTable->m_Buckets[m_Index]);
191  }
192
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
199  inline entry_type* getEntry() {
200    if (0 == m_pHashTable)
201      return 0;
202    return m_pHashTable->m_Buckets[m_Index].Entry;
203  }
204
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
211  inline void reset() {
212    m_pHashTable = 0;
213    m_Index = 0;
214  }
215
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
236private:
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 */
253template<typename IteratorBase,
254         typename Traits>
255class HashIterator : public IteratorBase
256{
257public:
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
277public:
278  HashIterator()
279  : IteratorBase()
280  { }
281
282  /// HashIterator - constructor for EntryIterator
283  HashIterator(typename IteratorBase::hash_table* pTable, unsigned int pIndex)
284  : IteratorBase(pTable, pIndex)
285  { }
286
287  /// HashIterator - constructor for ChainIterator
288  explicit HashIterator(typename IteratorBase::hash_table* pTable,
289                        const typename IteratorBase::key_type& pKey,
290                        int)
291  : IteratorBase(pTable, pKey)
292  { }
293
294  HashIterator(const HashIterator& pCopy)
295  : IteratorBase(pCopy)
296  { }
297
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