include/mcld/ADT/HashIterator.h

//===- 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