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 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:
28  ChainIteratorBase()
29      : m_pHashTable(NULL), m_Index(0), m_HashValue(0), m_EndIndex(0) {}
30
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
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
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
71  inline bucket_type* getBucket() {
72    if (m_pHashTable == NULL)
73      return NULL;
74    return &(m_pHashTable->m_Buckets[m_Index]);
75  }
76
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
83  inline entry_type* getEntry() {
84    if (m_pHashTable == NULL)
85      return NULL;
86    return m_pHashTable->m_Buckets[m_Index].Entry;
87  }
88
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
95  inline void reset() {
96    m_pHashTable = NULL;
97    m_Index = 0;
98    m_EndIndex = 0;
99    m_HashValue = 0;
100  }
101
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 */
152template <typename HashTableImplTy>
153class 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:
161  EntryIteratorBase() : m_pHashTable(NULL), m_Index(0) {}
162
163  EntryIteratorBase(HashTableImplTy* pTable, unsigned int pIndex)
164      : m_pHashTable(pTable), m_Index(pIndex) {}
165
166  EntryIteratorBase(const EntryIteratorBase& pCopy)
167      : m_pHashTable(pCopy.m_pHashTable), m_Index(pCopy.m_Index) {}
168
169  EntryIteratorBase& assign(const EntryIteratorBase& pCopy) {
170    m_pHashTable = pCopy.m_pHashTable;
171    m_Index = pCopy.m_Index;
172    return *this;
173  }
174
175  inline bucket_type* getBucket() {
176    if (m_pHashTable == NULL)
177      return NULL;
178    return &(m_pHashTable->m_Buckets[m_Index]);
179  }
180
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
187  inline entry_type* getEntry() {
188    if (m_pHashTable == NULL)
189      return NULL;
190    return m_pHashTable->m_Buckets[m_Index].Entry;
191  }
192
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
199  inline void reset() {
200    m_pHashTable = NULL;
201    m_Index = 0;
202  }
203
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 */
243template <typename IteratorBase, typename Traits>
244class 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:
263  HashIterator() : IteratorBase() {}
264
265  /// HashIterator - constructor for EntryIterator
266  HashIterator(typename IteratorBase::hash_table* pTable, unsigned int pIndex)
267      : IteratorBase(pTable, pIndex) {}
268
269  /// HashIterator - constructor for ChainIterator
270  explicit HashIterator(typename IteratorBase::hash_table* pTable,
271                        const typename IteratorBase::key_type& pKey,
272                        int)
273      : IteratorBase(pTable, pKey) {}
274
275  HashIterator(const HashIterator& pCopy) : IteratorBase(pCopy) {}
276
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