15460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao//===- HashTableTest.cpp --------------------------------------------------===// 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 105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include "HashTableTest.h" 11f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines#include <mcld/ADT/HashEntry.h> 12f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines#include <mcld/ADT/HashTable.h> 135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <cstdlib> 145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaousing namespace std; 165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaousing namespace mcld; 175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaousing namespace mcldtest; 185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// Constructor can do set-up work for all test here. 215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei LiaoHashTableTest::HashTableTest() 225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// Destructor can do clean-up work that doesn't throw exceptions here. 265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei LiaoHashTableTest::~HashTableTest() 275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// SetUp() will be called immediately before each test. 315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaovoid HashTableTest::SetUp() 325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// TearDown() will be called immediately after each test. 365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaovoid HashTableTest::TearDown() 375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao//==========================================================================// 415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// Testcases 425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// 435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaostruct IntCompare 445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool operator()(int X, int Y) const 465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return (X==Y); } 475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaostruct PtrCompare 505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool operator()(const int* X, const int* Y) const 525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return (X==Y); } 535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaostruct PtrHash 565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao size_t operator()(const int* pKey) const 585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return (unsigned((uintptr_t)pKey) >> 4) ^ 605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao (unsigned((uintptr_t)pKey) >> 9); 615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaostruct IntHash 655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao size_t operator()(int pKey) const 675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return pKey; } 685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaostruct IntMod3Hash 715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao size_t operator()(int pKey) const 735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return pKey % 3; } 745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei LiaoTEST_F( HashTableTest, ptr_entry ) { 775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao int A = 1; 785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao int* pA = &A; 795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashEntry<int*, int, PtrCompare> HashEntryType; 815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashTable<HashEntryType, PtrHash, EntryFactory<HashEntryType> > HashTableTy; 825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy *hashTable = new HashTableTy(0); 835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool exist; 855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::entry_type* entry = 0; 865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao entry = hashTable->insert(pA, exist); 885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_FALSE(hashTable->empty()); 905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::iterator iter; 925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao iter = hashTable->find(NULL); 935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_TRUE(iter==hashTable->end()); 945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao delete hashTable; 955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei LiaoTEST_F( HashTableTest, constructor ) { 985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashEntry<int, int, IntCompare> HashEntryType; 995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > hashTable(16); 10022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao EXPECT_TRUE(17 == hashTable.numOfBuckets()); 1015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_TRUE(hashTable.empty()); 10222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao EXPECT_TRUE(0 == hashTable.numOfEntries()); 1035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 1045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei LiaoTEST_F( HashTableTest, allocattion ) { 1065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashEntry<int, int, IntCompare> HashEntryType; 1075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy; 1085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy *hashTable = new HashTableTy(22); 1095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool exist; 1115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao int key = 100; 1125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::entry_type* val = hashTable->insert(key, exist); 1135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao val->setValue(999); 1145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_FALSE(hashTable->empty()); 1155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_FALSE(exist); 1165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_FALSE(NULL == val); 1175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::iterator entry = hashTable->find(key); 1185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_EQ(999, entry.getEntry()->value()); 1195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao delete hashTable; 1205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 1215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei LiaoTEST_F( HashTableTest, alloc100 ) { 1235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashEntry<int, int, IntCompare> HashEntryType; 1245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy; 1255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy *hashTable = new HashTableTy(22); 1265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool exist; 1285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::entry_type* entry = 0; 12922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for (int key=0; key<100; ++key) { 1305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao entry = hashTable->insert(key, exist); 1315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_FALSE(hashTable->empty()); 1325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_FALSE(exist); 1335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_FALSE(NULL == entry); 13422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao EXPECT_TRUE(key == entry->key()); 1355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao entry->setValue(key+10); 1365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_FALSE(hashTable->empty()); 13922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao EXPECT_TRUE(100 == hashTable->numOfEntries()); 14022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao EXPECT_TRUE(197 == hashTable->numOfBuckets()); 1415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao delete hashTable; 1425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 1435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei LiaoTEST_F( HashTableTest, erase100 ) { 1455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashEntry<int, int, IntCompare> HashEntryType; 1465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy; 1475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy *hashTable = new HashTableTy(0); 1485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool exist; 1505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::entry_type* entry = 0; 1515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for (unsigned int key=0; key<100; ++key) 1525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao entry = hashTable->insert(key, exist); 1535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_FALSE(hashTable->empty()); 1555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao int count; 1575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::iterator iter; 1585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for (unsigned int key=0; key<100; ++key) { 1595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao count = hashTable->erase(key); 1605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_EQ(1, count); 1615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao iter = hashTable->find(key); 1625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_TRUE(iter == hashTable->end()); 1635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_TRUE(hashTable->empty()); 1665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao delete hashTable; 1675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 1685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei LiaoTEST_F( HashTableTest, clear) { 1705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashEntry<int, int, IntCompare> HashEntryType; 1715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy; 1725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy *hashTable = new HashTableTy(22); 1735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool exist; 1755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::entry_type* entry = 0; 1765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for (unsigned int key=0; key<100; ++key) { 1775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao entry = hashTable->insert(key, exist); 1785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hashTable->clear(); 1815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::iterator iter; 1835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for (unsigned int key=0; key<100; ++key) { 1845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao iter = hashTable->find(key); 1855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_TRUE(iter == hashTable->end()); 1865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_TRUE(hashTable->empty()); 1895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao delete hashTable; 1905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 1915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei LiaoTEST_F( HashTableTest, tombstone ) { 1935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashEntry<int, int, IntCompare> HashEntryType; 1945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashTable<HashEntryType, IntMod3Hash, EntryFactory<HashEntryType> > HashTableTy; 1955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy *hashTable = new HashTableTy(); 1965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool exist; 1985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::entry_type* entry = 0; 1995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for (unsigned int key=0; key<100; ++key) { 2005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao entry = hashTable->insert(key, exist); 2015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_FALSE(hashTable->empty()); 2035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao int count; 2055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::iterator iter; 2065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for (unsigned int key=0; key<20; ++key) { 2075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao count = hashTable->erase(key); 2085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_EQ(1, count); 2095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao iter = hashTable->find(key); 2105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_TRUE(iter == hashTable->end()); 2115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 21222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao EXPECT_TRUE(80 == hashTable->numOfEntries()); 2135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for (unsigned int key=20; key<100; ++key) { 2155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao iter = hashTable->find(key); 2165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_TRUE(iter != hashTable->end()); 2175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for (unsigned int key=0; key<20; ++key) { 2205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao entry = hashTable->insert(key, exist); 2215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 22222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao EXPECT_TRUE(100 == hashTable->numOfEntries()); 22322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao EXPECT_TRUE(197 == hashTable->numOfBuckets()); 2245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao delete hashTable; 2265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 2275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei LiaoTEST_F( HashTableTest, rehash_test ) { 2295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashEntry<int, int, IntCompare> HashEntryType; 2305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy; 2315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy *hashTable = new HashTableTy(0); 2325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool exist; 2345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::entry_type* entry = 0; 2355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for (unsigned int key=0; key<400000; ++key) { 2365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao entry = hashTable->insert(key, exist); 2375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao entry->setValue(key+10); 2385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::iterator iter; 24122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for (int key=0; key<400000; ++key) { 2425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao iter = hashTable->find(key); 2435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_EQ((key+10), iter.getEntry()->value()); 2445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao delete hashTable; 2475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 2485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei LiaoTEST_F( HashTableTest, bucket_iterator ) { 2505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashEntry<int, int, IntCompare> HashEntryType; 2515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy; 2525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy *hashTable = new HashTableTy(0); 2535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool exist; 2555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::entry_type* entry = 0; 2565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for (unsigned int key=0; key<400000; ++key) { 2575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao entry = hashTable->insert(key, exist); 2585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao entry->setValue(key+10); 2595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::iterator iter, iEnd = hashTable->end(); 26222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao int counter = 0; 2635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for (iter = hashTable->begin(); iter != iEnd; ++iter) { 2645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_EQ(iter.getEntry()->key()+10, iter.getEntry()->value()); 2655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++counter; 2665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_EQ(400000, counter); 2685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao delete hashTable; 2695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 2705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei LiaoTEST_F( HashTableTest, chain_iterator_single ) { 2735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashEntry<int, int, IntCompare> HashEntryType; 2745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy; 2755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy *hashTable = new HashTableTy(); 2765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool exist; 2785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::entry_type* entry = 0; 27922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for (int key=0; key<16; ++key) { 2805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao entry = hashTable->insert(key*37, exist); 2815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao entry->setValue(key+10); 2825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 28322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for (int key=0; key<16; ++key) { 28422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao int counter = 0; 2855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::chain_iterator iter, iEnd = hashTable->end(key*37); 2865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for (iter = hashTable->begin(key*37); iter != iEnd; ++iter) { 2875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_EQ(key+10, iter.getEntry()->value()); 2885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++counter; 2895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_EQ(1, counter); 2915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao delete hashTable; 2935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 2945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaostruct FixHash 2965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 2975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao size_t operator()(int pKey) const { 2985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return 10; 2995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 3005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 3015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei LiaoTEST_F( HashTableTest, chain_iterator_list ) { 3045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashEntry<int, int, IntCompare> HashEntryType; 3055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashTable<HashEntryType, FixHash, EntryFactory<HashEntryType> > HashTableTy; 3065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy *hashTable = new HashTableTy(); 3075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool exist; 3095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::entry_type* entry = 0; 3105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for (unsigned int key=0; key<16; ++key) { 3115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao entry = hashTable->insert(key, exist); 3125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_FALSE(exist); 3135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao entry->setValue(key); 3145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 31522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ASSERT_TRUE(16 == hashTable->numOfEntries()); 31622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ASSERT_TRUE(37 == hashTable->numOfBuckets()); 3175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao unsigned int key = 0; 31922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao int count = 0; 3205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::chain_iterator iter, iEnd = hashTable->end(key); 3215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for (iter = hashTable->begin(key); iter != iEnd; ++iter) { 3225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao count++; 3235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 3245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(16, count); 3255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao delete hashTable; 3265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 327