//===- HashIterator.h -----------------------------------------------------===// // // The MCLinker Project // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// #ifndef MCLD_HASH_ITERATOR_H #define MCLD_HASH_ITERATOR_H #ifdef ENABLE_UNITTEST #include <gtest.h> #endif #include <cstddef> namespace mcld { /** \class ChainIteratorBase * \brief ChaintIteratorBase follows the HashEntryTy with the same hash value. */ template<typename HashTableImplTy> class ChainIteratorBase { public: typedef HashTableImplTy hash_table; typedef typename HashTableImplTy::key_type key_type; typedef typename HashTableImplTy::entry_type entry_type; typedef typename HashTableImplTy::bucket_type bucket_type; public: ChainIteratorBase() : m_pHashTable(0), m_HashValue(0), m_Index(0), m_EndIndex(0) { } ChainIteratorBase(HashTableImplTy* pTable, const key_type& pKey) : m_pHashTable(pTable) { m_HashValue = pTable->hash()(pKey); m_EndIndex = m_Index = m_HashValue % m_pHashTable->m_NumOfBuckets; const unsigned int probe = 1; while(true) { bucket_type &bucket = m_pHashTable->m_Buckets[m_Index]; if (bucket_type::getTombstone() == bucket.Entry) { // Ignore tombstones. } else if (m_HashValue == bucket.FullHashValue) { if (bucket.Entry->compare(pKey)) { m_EndIndex = m_Index; break; } } m_Index += probe; if (m_Index == m_pHashTable->m_NumOfBuckets) m_Index = 0; // doesn't exist if (m_EndIndex == m_Index) { reset(); break; } } } ChainIteratorBase(const ChainIteratorBase& pCopy) : m_pHashTable(pCopy.m_pHashTable), m_Index(pCopy.m_Index), m_EndIndex(pCopy.m_EndIndex), m_HashValue(pCopy.m_HashValue) { } ChainIteratorBase& assign(const ChainIteratorBase& pCopy) { m_pHashTable = pCopy.m_pHashTable; m_Index = pCopy.m_Index; m_EndIndex = pCopy.m_EndIndex; m_HashValue = pCopy.m_HashValue; return *this; } inline bucket_type* getBucket() { if (0 == m_pHashTable) return 0; return &(m_pHashTable->m_Buckets[m_Index]); } inline const bucket_type* getBucket() const { if (0 == m_pHashTable) return 0; return &(m_pHashTable->m_Buckets[m_Index]); } inline entry_type* getEntry() { if (0 == m_pHashTable) return 0; return m_pHashTable->m_Buckets[m_Index].Entry; } inline const entry_type* getEntry() const { if (0 == m_pHashTable) return 0; return m_pHashTable->m_Buckets[m_Index].Entry; } inline void reset() { m_pHashTable = 0; m_Index = 0; m_EndIndex = 0; m_HashValue = 0; } inline void advance() { if (0 == m_pHashTable) return; const unsigned int probe = 1; while(true) { m_Index += probe; if (m_Index == m_pHashTable->m_NumOfBuckets) m_Index = 0; // reach end() if (m_Index == m_EndIndex) { reset(); return; } bucket_type &bucket = m_pHashTable->m_Buckets[m_Index]; if (bucket_type::getTombstone() == bucket.Entry || bucket_type::getEmptyBucket() == bucket.Entry) { // Ignore tombstones. } else if (m_HashValue == bucket.FullHashValue) { return; } } } bool operator==(const ChainIteratorBase& pCopy) const { if (m_pHashTable == pCopy.m_pHashTable) { if (0 == m_pHashTable) return true; return ((m_HashValue == pCopy.m_HashValue) && (m_EndIndex == pCopy.m_EndIndex) && (m_Index == pCopy.m_Index)); } return false; } bool operator!=(const ChainIteratorBase& pCopy) const { return !(*this == pCopy); } private: HashTableImplTy* m_pHashTable; unsigned int m_Index; unsigned int m_HashValue; unsigned int m_EndIndex; }; /** \class EntryIteratorBase * \brief EntryIteratorBase walks over hash table by the natural layout of the * buckets */ template<typename HashTableImplTy> class EntryIteratorBase { public: typedef HashTableImplTy hash_table; typedef typename HashTableImplTy::key_type key_type; typedef typename HashTableImplTy::entry_type entry_type; typedef typename HashTableImplTy::bucket_type bucket_type; public: EntryIteratorBase() : m_pHashTable(0), m_Index(0) { } EntryIteratorBase(HashTableImplTy* pTable, unsigned int pIndex) : m_pHashTable(pTable), m_Index(pIndex) { } EntryIteratorBase(const EntryIteratorBase& pCopy) : m_pHashTable(pCopy.m_pHashTable), m_Index(pCopy.m_Index) { } EntryIteratorBase& assign(const EntryIteratorBase& pCopy) { m_pHashTable = pCopy.m_pHashTable; m_Index = pCopy.m_Index; return *this; } inline bucket_type* getBucket() { if (0 == m_pHashTable) return 0; return &(m_pHashTable->m_Buckets[m_Index]); } inline const bucket_type* getBucket() const { if (0 == m_pHashTable) return 0; return &(m_pHashTable->m_Buckets[m_Index]); } inline entry_type* getEntry() { if (0 == m_pHashTable) return 0; return m_pHashTable->m_Buckets[m_Index].Entry; } inline const entry_type* getEntry() const { if (0 == m_pHashTable) return 0; return m_pHashTable->m_Buckets[m_Index].Entry; } inline void reset() { m_pHashTable = 0; m_Index = 0; } inline void advance() { if (0 == m_pHashTable) return; do { ++m_Index; if (m_pHashTable->m_NumOfBuckets == m_Index) { // to the end reset(); return; } } while(bucket_type::getEmptyBucket() == m_pHashTable->m_Buckets[m_Index].Entry || bucket_type::getTombstone() == m_pHashTable->m_Buckets[m_Index].Entry); } bool operator==(const EntryIteratorBase& pCopy) const { return ((m_pHashTable == pCopy.m_pHashTable) && (m_Index == pCopy.m_Index)); } bool operator!=(const EntryIteratorBase& pCopy) const { return !(*this == pCopy); } private: HashTableImplTy* m_pHashTable; unsigned int m_Index; }; /** \class HashIterator * \brief HashIterator provides a policy-based iterator. * * HashTable has two kinds of iterators. One is used to traverse buckets * with the same hash value; the other is used to traverse all entries of the * hash table. * * HashIterator is a template policy-based iterator, which can change its * behavior by change the template argument IteratorBase. HashTable defines * above two iterators by defining HashIterators with different IteratorBase. */ template<typename IteratorBase, typename Traits> class HashIterator : public IteratorBase { public: typedef Traits traits; typedef typename traits::pointer pointer; typedef typename traits::reference reference; typedef size_t size_type; typedef ptrdiff_t difference_type; typedef IteratorBase Base; typedef HashIterator<IteratorBase, Traits> Self; typedef typename traits::nonconst_traits nonconst_traits; typedef HashIterator<IteratorBase, nonconst_traits> iterator; typedef typename traits::const_traits const_traits; typedef HashIterator<IteratorBase, const_traits> const_iterator; typedef std::forward_iterator_tag iterator_category; public: HashIterator() : IteratorBase() { } /// HashIterator - constructor for EntryIterator HashIterator(typename IteratorBase::hash_table* pTable, unsigned int pIndex) : IteratorBase(pTable, pIndex) { } /// HashIterator - constructor for ChainIterator explicit HashIterator(typename IteratorBase::hash_table* pTable, const typename IteratorBase::key_type& pKey, int) : IteratorBase(pTable, pKey) { } HashIterator(const HashIterator& pCopy) : IteratorBase(pCopy) { } ~HashIterator() { } HashIterator& operator=(const HashIterator& pCopy) { IteratorBase::assign(pCopy); return *this; } // ----- operators ----- // Self& operator++() { this->Base::advance(); return *this; } Self operator++(int) { Self tmp = *this; this->Base::advance(); return tmp; } }; } // namespace of mcld #endif