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