Home | History | Annotate | Download | only in ADT 
      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:
     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  */
    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:
    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  */
    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:
    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