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//===----------------------------------------------------------------------===// 987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#ifndef MCLD_ADT_HASHITERATOR_H 1087f34658dec9097d987d254a990ea7f311bfc95fStephen 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 */ 195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<typename HashTableImplTy> 205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass ChainIteratorBase 215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashTableImplTy hash_table; 245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename HashTableImplTy::key_type key_type; 255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename HashTableImplTy::entry_type entry_type; 265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename HashTableImplTy::bucket_type bucket_type; 275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ChainIteratorBase() 3022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao : m_pHashTable(0), m_Index(0), m_HashValue(0), m_EndIndex(0) 315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ChainIteratorBase(HashTableImplTy* pTable, const key_type& pKey) 345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : m_pHashTable(pTable) 355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_HashValue = pTable->hash()(pKey); 375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_EndIndex = m_Index = m_HashValue % m_pHashTable->m_NumOfBuckets; 385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const unsigned int probe = 1; 395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao while(true) { 405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bucket_type &bucket = m_pHashTable->m_Buckets[m_Index]; 415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (bucket_type::getTombstone() == bucket.Entry) { 425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // Ignore tombstones. 435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao else if (m_HashValue == bucket.FullHashValue) { 455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (bucket.Entry->compare(pKey)) { 465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_EndIndex = m_Index; 475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao break; 485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_Index += probe; 515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (m_Index == m_pHashTable->m_NumOfBuckets) 525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_Index = 0; 535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // doesn't exist 545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (m_EndIndex == m_Index) { 555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao reset(); 565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao break; 575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ChainIteratorBase(const ChainIteratorBase& pCopy) 625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : m_pHashTable(pCopy.m_pHashTable), 635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_Index(pCopy.m_Index), 6422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao m_HashValue(pCopy.m_HashValue), 6522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao m_EndIndex(pCopy.m_EndIndex) 665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ChainIteratorBase& assign(const ChainIteratorBase& pCopy) { 695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pHashTable = pCopy.m_pHashTable; 705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_Index = pCopy.m_Index; 715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_HashValue = pCopy.m_HashValue; 7222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao m_EndIndex = pCopy.m_EndIndex; 735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return *this; 745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline bucket_type* getBucket() { 775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (0 == m_pHashTable) 785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return 0; 795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return &(m_pHashTable->m_Buckets[m_Index]); 805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline const bucket_type* getBucket() const { 835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (0 == m_pHashTable) 845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return 0; 855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return &(m_pHashTable->m_Buckets[m_Index]); 865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline entry_type* getEntry() { 895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (0 == m_pHashTable) 905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return 0; 915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return m_pHashTable->m_Buckets[m_Index].Entry; 925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline const entry_type* getEntry() const { 955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (0 == m_pHashTable) 965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return 0; 975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return m_pHashTable->m_Buckets[m_Index].Entry; 985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline void reset() { 1015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pHashTable = 0; 1025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_Index = 0; 1035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_EndIndex = 0; 1045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_HashValue = 0; 1055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline void advance() { 1085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (0 == m_pHashTable) 1095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return; 1105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const unsigned int probe = 1; 1115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao while(true) { 1125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_Index += probe; 1135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (m_Index == m_pHashTable->m_NumOfBuckets) 1145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_Index = 0; 1155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // reach end() 1165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (m_Index == m_EndIndex) { 1175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao reset(); 1185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return; 1195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bucket_type &bucket = m_pHashTable->m_Buckets[m_Index]; 1225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (bucket_type::getTombstone() == bucket.Entry || 1245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bucket_type::getEmptyBucket() == bucket.Entry) { 1255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // Ignore tombstones. 1265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao else if (m_HashValue == bucket.FullHashValue) { 1285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return; 1295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool operator==(const ChainIteratorBase& pCopy) const { 1345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (m_pHashTable == pCopy.m_pHashTable) { 1355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (0 == m_pHashTable) 1365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return true; 1375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return ((m_HashValue == pCopy.m_HashValue) && 1385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao (m_EndIndex == pCopy.m_EndIndex) && 1395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao (m_Index == pCopy.m_Index)); 1405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return false; 1425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool operator!=(const ChainIteratorBase& pCopy) const 1455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return !(*this == pCopy); } 1465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoprivate: 1485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableImplTy* m_pHashTable; 1495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao unsigned int m_Index; 1505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao unsigned int m_HashValue; 1515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao unsigned int m_EndIndex; 1525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 153f767be5432ccac097334be48698e48621d730190Shih-wei Liao 1545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class EntryIteratorBase 1555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief EntryIteratorBase walks over hash table by the natural layout of the 1565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * buckets 1575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 1585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<typename HashTableImplTy> 1595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass EntryIteratorBase 1605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 1615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 1625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashTableImplTy hash_table; 1635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename HashTableImplTy::key_type key_type; 1645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename HashTableImplTy::entry_type entry_type; 1655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename HashTableImplTy::bucket_type bucket_type; 1665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 1685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EntryIteratorBase() 1695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : m_pHashTable(0), m_Index(0) 1705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 1715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EntryIteratorBase(HashTableImplTy* pTable, 1735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao unsigned int pIndex) 1745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : m_pHashTable(pTable), m_Index(pIndex) 1755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 1765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EntryIteratorBase(const EntryIteratorBase& pCopy) 1785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : m_pHashTable(pCopy.m_pHashTable), m_Index(pCopy.m_Index) 1795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 1805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EntryIteratorBase& assign(const EntryIteratorBase& pCopy) { 1825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pHashTable = pCopy.m_pHashTable; 1835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_Index = pCopy.m_Index; 1845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return *this; 1855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline bucket_type* getBucket() { 1885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (0 == m_pHashTable) 1895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return 0; 1905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return &(m_pHashTable->m_Buckets[m_Index]); 1915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline const bucket_type* getBucket() const { 1945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (0 == m_pHashTable) 1955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return 0; 1965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return &(m_pHashTable->m_Buckets[m_Index]); 1975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline entry_type* getEntry() { 2005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (0 == m_pHashTable) 2015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return 0; 2025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return m_pHashTable->m_Buckets[m_Index].Entry; 2035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline const entry_type* getEntry() const { 2065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (0 == m_pHashTable) 2075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return 0; 2085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return m_pHashTable->m_Buckets[m_Index].Entry; 2095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline void reset() { 2125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pHashTable = 0; 2135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_Index = 0; 2145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline void advance() { 2175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (0 == m_pHashTable) 2185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return; 2195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao do { 2205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++m_Index; 2215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (m_pHashTable->m_NumOfBuckets == m_Index) { // to the end 2225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao reset(); 2235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return; 2245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 225f767be5432ccac097334be48698e48621d730190Shih-wei Liao } while(bucket_type::getEmptyBucket() == m_pHashTable->m_Buckets[m_Index].Entry || 2265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bucket_type::getTombstone() == m_pHashTable->m_Buckets[m_Index].Entry); 2275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool operator==(const EntryIteratorBase& pCopy) const 2305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return ((m_pHashTable == pCopy.m_pHashTable) && 2315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao (m_Index == pCopy.m_Index)); } 2325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool operator!=(const EntryIteratorBase& pCopy) const 2345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return !(*this == pCopy); } 2355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoprivate: 2375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableImplTy* m_pHashTable; 2385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao unsigned int m_Index; 2395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 2415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class HashIterator 2435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief HashIterator provides a policy-based iterator. 2445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 2455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * HashTable has two kinds of iterators. One is used to traverse buckets 2465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * with the same hash value; the other is used to traverse all entries of the 2475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * hash table. 2485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 2495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * HashIterator is a template policy-based iterator, which can change its 2505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * behavior by change the template argument IteratorBase. HashTable defines 2515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * above two iterators by defining HashIterators with different IteratorBase. 2525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 2535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<typename IteratorBase, 2545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typename Traits> 2555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass HashIterator : public IteratorBase 2565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 2575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 2585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef Traits traits; 2595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename traits::pointer pointer; 2605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename traits::reference reference; 2615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef size_t size_type; 2625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef ptrdiff_t difference_type; 2635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef IteratorBase Base; 2645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashIterator<IteratorBase, 2665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Traits> Self; 2675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename traits::nonconst_traits nonconst_traits; 2695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashIterator<IteratorBase, 2705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao nonconst_traits> iterator; 2715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename traits::const_traits const_traits; 2735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashIterator<IteratorBase, 2745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const_traits> const_iterator; 2755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef std::forward_iterator_tag iterator_category; 2765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 2785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashIterator() 2795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : IteratorBase() 2805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 2815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// HashIterator - constructor for EntryIterator 2835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashIterator(typename IteratorBase::hash_table* pTable, unsigned int pIndex) 2845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : IteratorBase(pTable, pIndex) 2855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 2865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// HashIterator - constructor for ChainIterator 2885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao explicit HashIterator(typename IteratorBase::hash_table* pTable, 2895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const typename IteratorBase::key_type& pKey, 2905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao int) 2915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : IteratorBase(pTable, pKey) 2925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 2935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashIterator(const HashIterator& pCopy) 2955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : IteratorBase(pCopy) 2965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 2975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ~HashIterator() 2995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 3005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashIterator& operator=(const HashIterator& pCopy) { 3025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao IteratorBase::assign(pCopy); 3035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return *this; 3045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 3055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // ----- operators ----- // 3075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Self& operator++() { 3085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao this->Base::advance(); 3095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return *this; 3105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 3115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Self operator++(int) { 3135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Self tmp = *this; 3145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao this->Base::advance(); 3155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return tmp; 3165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 3175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 3185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} // namespace of mcld 3205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#endif 322affc150dc44fab1911775a49636d0ce85333b634Zonr Chang 323