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