15460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao//===- HashIterator.h -----------------------------------------------------===// 25460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// 35460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// The MCLinker Project 45460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// 55460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// This file is distributed under the University of Illinois Open Source 65460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// License. See LICENSE.TXT for details. 75460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// 85460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao//===----------------------------------------------------------------------===// 937b74a387bb3993387029859c2d9d051c41c724eStephen Hines#ifndef MCLD_ADT_HASHITERATOR_H_ 1037b74a387bb3993387029859c2d9d051c41c724eStephen Hines#define MCLD_ADT_HASHITERATOR_H_ 115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 12f767be5432ccac097334be48698e48621d730190Shih-wei Liao#include <cstddef> 13f767be5432ccac097334be48698e48621d730190Shih-wei Liao 145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaonamespace mcld { 155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class ChainIteratorBase 175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief ChaintIteratorBase follows the HashEntryTy with the same hash value. 185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 1937b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <typename HashTableImplTy> 2037b74a387bb3993387029859c2d9d051c41c724eStephen Hinesclass ChainIteratorBase { 2137b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashTableImplTy hash_table; 235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename HashTableImplTy::key_type key_type; 245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename HashTableImplTy::entry_type entry_type; 255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename HashTableImplTy::bucket_type bucket_type; 265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2737b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ChainIteratorBase() 2937b74a387bb3993387029859c2d9d051c41c724eStephen Hines : m_pHashTable(NULL), m_Index(0), m_HashValue(0), m_EndIndex(0) {} 305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ChainIteratorBase(HashTableImplTy* pTable, const key_type& pKey) 3237b74a387bb3993387029859c2d9d051c41c724eStephen Hines : m_pHashTable(pTable) { 335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_HashValue = pTable->hash()(pKey); 345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_EndIndex = m_Index = m_HashValue % m_pHashTable->m_NumOfBuckets; 355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const unsigned int probe = 1; 3637b74a387bb3993387029859c2d9d051c41c724eStephen Hines while (true) { 3737b74a387bb3993387029859c2d9d051c41c724eStephen Hines bucket_type& bucket = m_pHashTable->m_Buckets[m_Index]; 385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (bucket_type::getTombstone() == bucket.Entry) { 395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // Ignore tombstones. 4037b74a387bb3993387029859c2d9d051c41c724eStephen Hines } else if (m_HashValue == bucket.FullHashValue) { 415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (bucket.Entry->compare(pKey)) { 425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_EndIndex = m_Index; 435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao break; 445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_Index += probe; 475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (m_Index == m_pHashTable->m_NumOfBuckets) 485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_Index = 0; 495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // doesn't exist 505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (m_EndIndex == m_Index) { 515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao reset(); 525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao break; 535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ChainIteratorBase(const ChainIteratorBase& pCopy) 5837b74a387bb3993387029859c2d9d051c41c724eStephen Hines : m_pHashTable(pCopy.m_pHashTable), 5937b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_Index(pCopy.m_Index), 6037b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_HashValue(pCopy.m_HashValue), 6137b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_EndIndex(pCopy.m_EndIndex) {} 625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ChainIteratorBase& assign(const ChainIteratorBase& pCopy) { 645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pHashTable = pCopy.m_pHashTable; 655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_Index = pCopy.m_Index; 665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_HashValue = pCopy.m_HashValue; 6722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao m_EndIndex = pCopy.m_EndIndex; 685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return *this; 695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline bucket_type* getBucket() { 7237b74a387bb3993387029859c2d9d051c41c724eStephen Hines if (m_pHashTable == NULL) 7337b74a387bb3993387029859c2d9d051c41c724eStephen Hines return NULL; 745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return &(m_pHashTable->m_Buckets[m_Index]); 755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline const bucket_type* getBucket() const { 7837b74a387bb3993387029859c2d9d051c41c724eStephen Hines if (m_pHashTable == NULL) 7937b74a387bb3993387029859c2d9d051c41c724eStephen Hines return NULL; 805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return &(m_pHashTable->m_Buckets[m_Index]); 815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline entry_type* getEntry() { 8437b74a387bb3993387029859c2d9d051c41c724eStephen Hines if (m_pHashTable == NULL) 8537b74a387bb3993387029859c2d9d051c41c724eStephen Hines return NULL; 865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return m_pHashTable->m_Buckets[m_Index].Entry; 875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline const entry_type* getEntry() const { 9037b74a387bb3993387029859c2d9d051c41c724eStephen Hines if (m_pHashTable == NULL) 9137b74a387bb3993387029859c2d9d051c41c724eStephen Hines return NULL; 925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return m_pHashTable->m_Buckets[m_Index].Entry; 935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline void reset() { 9637b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pHashTable = NULL; 975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_Index = 0; 985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_EndIndex = 0; 995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_HashValue = 0; 1005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline void advance() { 10337b74a387bb3993387029859c2d9d051c41c724eStephen Hines if (m_pHashTable == NULL) 1045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return; 1055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const unsigned int probe = 1; 10637b74a387bb3993387029859c2d9d051c41c724eStephen Hines while (true) { 1075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_Index += probe; 1085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (m_Index == m_pHashTable->m_NumOfBuckets) 1095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_Index = 0; 1105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // reach end() 1115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (m_Index == m_EndIndex) { 1125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao reset(); 1135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return; 1145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 11637b74a387bb3993387029859c2d9d051c41c724eStephen Hines bucket_type& bucket = m_pHashTable->m_Buckets[m_Index]; 1175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (bucket_type::getTombstone() == bucket.Entry || 1195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bucket_type::getEmptyBucket() == bucket.Entry) { 1205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // Ignore tombstones. 12137b74a387bb3993387029859c2d9d051c41c724eStephen Hines } else if (m_HashValue == bucket.FullHashValue) { 1225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return; 1235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool operator==(const ChainIteratorBase& pCopy) const { 1285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (m_pHashTable == pCopy.m_pHashTable) { 12937b74a387bb3993387029859c2d9d051c41c724eStephen Hines if (m_pHashTable == NULL) 1305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return true; 1315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return ((m_HashValue == pCopy.m_HashValue) && 13237b74a387bb3993387029859c2d9d051c41c724eStephen Hines (m_EndIndex == pCopy.m_EndIndex) && (m_Index == pCopy.m_Index)); 1335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return false; 1355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 13737b74a387bb3993387029859c2d9d051c41c724eStephen Hines bool operator!=(const ChainIteratorBase& pCopy) const { 13837b74a387bb3993387029859c2d9d051c41c724eStephen Hines return !(*this == pCopy); 13937b74a387bb3993387029859c2d9d051c41c724eStephen Hines } 1405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 14137b74a387bb3993387029859c2d9d051c41c724eStephen Hines private: 1425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableImplTy* m_pHashTable; 1435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao unsigned int m_Index; 1445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao unsigned int m_HashValue; 1455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao unsigned int m_EndIndex; 1465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 147f767be5432ccac097334be48698e48621d730190Shih-wei Liao 1485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class EntryIteratorBase 1495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief EntryIteratorBase walks over hash table by the natural layout of the 1505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * buckets 1515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 15237b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <typename HashTableImplTy> 15337b74a387bb3993387029859c2d9d051c41c724eStephen Hinesclass EntryIteratorBase { 15437b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 1555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashTableImplTy hash_table; 1565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename HashTableImplTy::key_type key_type; 1575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename HashTableImplTy::entry_type entry_type; 1585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename HashTableImplTy::bucket_type bucket_type; 1595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 16037b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 16137b74a387bb3993387029859c2d9d051c41c724eStephen Hines EntryIteratorBase() : m_pHashTable(NULL), m_Index(0) {} 1625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 16337b74a387bb3993387029859c2d9d051c41c724eStephen Hines EntryIteratorBase(HashTableImplTy* pTable, unsigned int pIndex) 16437b74a387bb3993387029859c2d9d051c41c724eStephen Hines : m_pHashTable(pTable), m_Index(pIndex) {} 1655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EntryIteratorBase(const EntryIteratorBase& pCopy) 16737b74a387bb3993387029859c2d9d051c41c724eStephen Hines : m_pHashTable(pCopy.m_pHashTable), m_Index(pCopy.m_Index) {} 1685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EntryIteratorBase& assign(const EntryIteratorBase& pCopy) { 1705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pHashTable = pCopy.m_pHashTable; 1715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_Index = pCopy.m_Index; 1725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return *this; 1735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline bucket_type* getBucket() { 17637b74a387bb3993387029859c2d9d051c41c724eStephen Hines if (m_pHashTable == NULL) 17737b74a387bb3993387029859c2d9d051c41c724eStephen Hines return NULL; 1785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return &(m_pHashTable->m_Buckets[m_Index]); 1795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline const bucket_type* getBucket() const { 18237b74a387bb3993387029859c2d9d051c41c724eStephen Hines if (m_pHashTable == NULL) 18337b74a387bb3993387029859c2d9d051c41c724eStephen Hines return NULL; 1845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return &(m_pHashTable->m_Buckets[m_Index]); 1855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline entry_type* getEntry() { 18837b74a387bb3993387029859c2d9d051c41c724eStephen Hines if (m_pHashTable == NULL) 18937b74a387bb3993387029859c2d9d051c41c724eStephen Hines return NULL; 1905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return m_pHashTable->m_Buckets[m_Index].Entry; 1915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline const entry_type* getEntry() const { 19437b74a387bb3993387029859c2d9d051c41c724eStephen Hines if (m_pHashTable == NULL) 19537b74a387bb3993387029859c2d9d051c41c724eStephen Hines return NULL; 1965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return m_pHashTable->m_Buckets[m_Index].Entry; 1975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline void reset() { 20037b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pHashTable = NULL; 2015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_Index = 0; 2025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline void advance() { 20537b74a387bb3993387029859c2d9d051c41c724eStephen Hines if (m_pHashTable == NULL) 2065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return; 2075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao do { 2085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++m_Index; 20937b74a387bb3993387029859c2d9d051c41c724eStephen Hines if (m_pHashTable->m_NumOfBuckets == m_Index) { // to the end 2105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao reset(); 2115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return; 2125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 21337b74a387bb3993387029859c2d9d051c41c724eStephen Hines } while (bucket_type::getEmptyBucket() == 21437b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pHashTable->m_Buckets[m_Index].Entry || 21537b74a387bb3993387029859c2d9d051c41c724eStephen Hines bucket_type::getTombstone() == 21637b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pHashTable->m_Buckets[m_Index].Entry); 2175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 21937b74a387bb3993387029859c2d9d051c41c724eStephen Hines bool operator==(const EntryIteratorBase& pCopy) const { 22037b74a387bb3993387029859c2d9d051c41c724eStephen Hines return ((m_pHashTable == pCopy.m_pHashTable) && (m_Index == pCopy.m_Index)); 22137b74a387bb3993387029859c2d9d051c41c724eStephen Hines } 2225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 22337b74a387bb3993387029859c2d9d051c41c724eStephen Hines bool operator!=(const EntryIteratorBase& pCopy) const { 22437b74a387bb3993387029859c2d9d051c41c724eStephen Hines return !(*this == pCopy); 22537b74a387bb3993387029859c2d9d051c41c724eStephen Hines } 2265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 22737b74a387bb3993387029859c2d9d051c41c724eStephen Hines private: 2285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableImplTy* m_pHashTable; 2295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao unsigned int m_Index; 2305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 2315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class HashIterator 2335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief HashIterator provides a policy-based iterator. 2345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 2355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * HashTable has two kinds of iterators. One is used to traverse buckets 2365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * with the same hash value; the other is used to traverse all entries of the 2375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * hash table. 2385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 2395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * HashIterator is a template policy-based iterator, which can change its 2405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * behavior by change the template argument IteratorBase. HashTable defines 2415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * above two iterators by defining HashIterators with different IteratorBase. 2425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 24337b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <typename IteratorBase, typename Traits> 24437b74a387bb3993387029859c2d9d051c41c724eStephen Hinesclass HashIterator : public IteratorBase { 24537b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 24637b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef Traits traits; 24737b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef typename traits::pointer pointer; 2485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename traits::reference reference; 24937b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef size_t size_type; 25037b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef ptrdiff_t difference_type; 25137b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef IteratorBase Base; 2525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 25337b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef HashIterator<IteratorBase, Traits> Self; 2545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename traits::nonconst_traits nonconst_traits; 25637b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef HashIterator<IteratorBase, nonconst_traits> iterator; 2575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 25837b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef typename traits::const_traits const_traits; 25937b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef HashIterator<IteratorBase, const_traits> const_iterator; 26037b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef std::forward_iterator_tag iterator_category; 2615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 26237b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 26337b74a387bb3993387029859c2d9d051c41c724eStephen Hines HashIterator() : IteratorBase() {} 2645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// HashIterator - constructor for EntryIterator 2665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashIterator(typename IteratorBase::hash_table* pTable, unsigned int pIndex) 26737b74a387bb3993387029859c2d9d051c41c724eStephen Hines : IteratorBase(pTable, pIndex) {} 2685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// HashIterator - constructor for ChainIterator 2705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao explicit HashIterator(typename IteratorBase::hash_table* pTable, 2715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const typename IteratorBase::key_type& pKey, 2725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao int) 27337b74a387bb3993387029859c2d9d051c41c724eStephen Hines : IteratorBase(pTable, pKey) {} 2745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 27537b74a387bb3993387029859c2d9d051c41c724eStephen Hines HashIterator(const HashIterator& pCopy) : IteratorBase(pCopy) {} 2765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 27737b74a387bb3993387029859c2d9d051c41c724eStephen Hines ~HashIterator() {} 2785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashIterator& operator=(const HashIterator& pCopy) { 2805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao IteratorBase::assign(pCopy); 2815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return *this; 2825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // ----- operators ----- // 2855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Self& operator++() { 2865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao this->Base::advance(); 2875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return *this; 2885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Self operator++(int) { 2915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Self tmp = *this; 2925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao this->Base::advance(); 2935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return tmp; 2945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 2965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 29737b74a387bb3993387029859c2d9d051c41c724eStephen Hines} // namespace mcld 298affc150dc44fab1911775a49636d0ce85333b634Zonr Chang 29937b74a387bb3993387029859c2d9d051c41c724eStephen Hines#endif // MCLD_ADT_HASHITERATOR_H_ 300