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" 1137b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/ADT/HashEntry.h" 1237b74a387bb3993387029859c2d9d051c41c724eStephen 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// Constructor can do set-up work for all test here. 2037b74a387bb3993387029859c2d9d051c41c724eStephen HinesHashTableTest::HashTableTest() { 215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// Destructor can do clean-up work that doesn't throw exceptions here. 2437b74a387bb3993387029859c2d9d051c41c724eStephen HinesHashTableTest::~HashTableTest() { 255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// SetUp() will be called immediately before each test. 2837b74a387bb3993387029859c2d9d051c41c724eStephen Hinesvoid HashTableTest::SetUp() { 295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// TearDown() will be called immediately after each test. 3237b74a387bb3993387029859c2d9d051c41c724eStephen Hinesvoid HashTableTest::TearDown() { 335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao//==========================================================================// 365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// Testcases 375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// 3837b74a387bb3993387029859c2d9d051c41c724eStephen Hinesstruct IntCompare { 3937b74a387bb3993387029859c2d9d051c41c724eStephen Hines bool operator()(int X, int Y) const { return (X == Y); } 405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4237b74a387bb3993387029859c2d9d051c41c724eStephen Hinesstruct PtrCompare { 4337b74a387bb3993387029859c2d9d051c41c724eStephen Hines bool operator()(const int* X, const int* Y) const { return (X == Y); } 445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4637b74a387bb3993387029859c2d9d051c41c724eStephen Hinesstruct PtrHash { 4737b74a387bb3993387029859c2d9d051c41c724eStephen Hines size_t operator()(const int* pKey) const { 4837b74a387bb3993387029859c2d9d051c41c724eStephen Hines return (unsigned((uintptr_t)pKey) >> 4) ^ (unsigned((uintptr_t)pKey) >> 9); 495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 5237b74a387bb3993387029859c2d9d051c41c724eStephen Hinesstruct IntHash { 5337b74a387bb3993387029859c2d9d051c41c724eStephen Hines size_t operator()(int pKey) const { return pKey; } 545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 5637b74a387bb3993387029859c2d9d051c41c724eStephen Hinesstruct IntMod3Hash { 5737b74a387bb3993387029859c2d9d051c41c724eStephen Hines size_t operator()(int pKey) const { return pKey % 3; } 585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 6037b74a387bb3993387029859c2d9d051c41c724eStephen HinesTEST_F(HashTableTest, ptr_entry) { 615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao int A = 1; 625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao int* pA = &A; 635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashEntry<int*, int, PtrCompare> HashEntryType; 6537b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef HashTable<HashEntryType, PtrHash, EntryFactory<HashEntryType> > 6637b74a387bb3993387029859c2d9d051c41c724eStephen Hines HashTableTy; 6737b74a387bb3993387029859c2d9d051c41c724eStephen Hines HashTableTy* hashTable = new HashTableTy(0); 685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool exist; 702bf3f881f79c4d883f379e63725e788c310739a3Pirama Arumuga Nainar hashTable->insert(pA, exist); 715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_FALSE(hashTable->empty()); 735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::iterator iter; 755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao iter = hashTable->find(NULL); 7637b74a387bb3993387029859c2d9d051c41c724eStephen Hines EXPECT_TRUE(iter == hashTable->end()); 775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao delete hashTable; 785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 8037b74a387bb3993387029859c2d9d051c41c724eStephen HinesTEST_F(HashTableTest, constructor) { 815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashEntry<int, int, IntCompare> HashEntryType; 825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > hashTable(16); 8322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao EXPECT_TRUE(17 == hashTable.numOfBuckets()); 845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_TRUE(hashTable.empty()); 8522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao EXPECT_TRUE(0 == hashTable.numOfEntries()); 865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 8837b74a387bb3993387029859c2d9d051c41c724eStephen HinesTEST_F(HashTableTest, allocattion) { 895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashEntry<int, int, IntCompare> HashEntryType; 9037b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > 9137b74a387bb3993387029859c2d9d051c41c724eStephen Hines HashTableTy; 9237b74a387bb3993387029859c2d9d051c41c724eStephen Hines HashTableTy* hashTable = new HashTableTy(22); 935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool exist; 955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao int key = 100; 965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::entry_type* val = hashTable->insert(key, exist); 975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao val->setValue(999); 985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_FALSE(hashTable->empty()); 995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_FALSE(exist); 1005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_FALSE(NULL == val); 1015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::iterator entry = hashTable->find(key); 1025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_EQ(999, entry.getEntry()->value()); 1035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao delete hashTable; 1045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 1055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 10637b74a387bb3993387029859c2d9d051c41c724eStephen HinesTEST_F(HashTableTest, alloc100) { 1075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashEntry<int, int, IntCompare> HashEntryType; 10837b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > 10937b74a387bb3993387029859c2d9d051c41c724eStephen Hines HashTableTy; 11037b74a387bb3993387029859c2d9d051c41c724eStephen Hines HashTableTy* hashTable = new HashTableTy(22); 1115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool exist; 1135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::entry_type* entry = 0; 11437b74a387bb3993387029859c2d9d051c41c724eStephen Hines for (int key = 0; key < 100; ++key) { 1155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao entry = hashTable->insert(key, exist); 1165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_FALSE(hashTable->empty()); 1175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_FALSE(exist); 1185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_FALSE(NULL == entry); 11922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao EXPECT_TRUE(key == entry->key()); 12037b74a387bb3993387029859c2d9d051c41c724eStephen Hines entry->setValue(key + 10); 1215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_FALSE(hashTable->empty()); 12422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao EXPECT_TRUE(100 == hashTable->numOfEntries()); 12522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao EXPECT_TRUE(197 == hashTable->numOfBuckets()); 1265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao delete hashTable; 1275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 1285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 12937b74a387bb3993387029859c2d9d051c41c724eStephen HinesTEST_F(HashTableTest, erase100) { 1305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashEntry<int, int, IntCompare> HashEntryType; 13137b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > 13237b74a387bb3993387029859c2d9d051c41c724eStephen Hines HashTableTy; 13337b74a387bb3993387029859c2d9d051c41c724eStephen Hines HashTableTy* hashTable = new HashTableTy(0); 1345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool exist; 13637b74a387bb3993387029859c2d9d051c41c724eStephen Hines for (unsigned int key = 0; key < 100; ++key) 1372bf3f881f79c4d883f379e63725e788c310739a3Pirama Arumuga Nainar hashTable->insert(key, exist); 1385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_FALSE(hashTable->empty()); 1405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao int count; 1425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::iterator iter; 14337b74a387bb3993387029859c2d9d051c41c724eStephen Hines for (unsigned int key = 0; key < 100; ++key) { 1445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao count = hashTable->erase(key); 1455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_EQ(1, count); 1465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao iter = hashTable->find(key); 1475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_TRUE(iter == hashTable->end()); 1485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_TRUE(hashTable->empty()); 1515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao delete hashTable; 1525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 1535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 15437b74a387bb3993387029859c2d9d051c41c724eStephen HinesTEST_F(HashTableTest, clear) { 1555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashEntry<int, int, IntCompare> HashEntryType; 15637b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > 15737b74a387bb3993387029859c2d9d051c41c724eStephen Hines HashTableTy; 15837b74a387bb3993387029859c2d9d051c41c724eStephen Hines HashTableTy* hashTable = new HashTableTy(22); 1595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool exist; 16137b74a387bb3993387029859c2d9d051c41c724eStephen Hines for (unsigned int key = 0; key < 100; ++key) { 1622bf3f881f79c4d883f379e63725e788c310739a3Pirama Arumuga Nainar hashTable->insert(key, exist); 1635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao hashTable->clear(); 1665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::iterator iter; 16837b74a387bb3993387029859c2d9d051c41c724eStephen Hines for (unsigned int key = 0; key < 100; ++key) { 1695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao iter = hashTable->find(key); 1705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_TRUE(iter == hashTable->end()); 1715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_TRUE(hashTable->empty()); 1745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao delete hashTable; 1755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 1765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 17737b74a387bb3993387029859c2d9d051c41c724eStephen HinesTEST_F(HashTableTest, tombstone) { 1785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashEntry<int, int, IntCompare> HashEntryType; 17937b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef HashTable<HashEntryType, IntMod3Hash, EntryFactory<HashEntryType> > 18037b74a387bb3993387029859c2d9d051c41c724eStephen Hines HashTableTy; 18137b74a387bb3993387029859c2d9d051c41c724eStephen Hines HashTableTy* hashTable = new HashTableTy(); 1825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool exist; 18437b74a387bb3993387029859c2d9d051c41c724eStephen Hines for (unsigned int key = 0; key < 100; ++key) { 1852bf3f881f79c4d883f379e63725e788c310739a3Pirama Arumuga Nainar hashTable->insert(key, exist); 1865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_FALSE(hashTable->empty()); 1885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao int count; 1905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::iterator iter; 19137b74a387bb3993387029859c2d9d051c41c724eStephen Hines for (unsigned int key = 0; key < 20; ++key) { 1925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao count = hashTable->erase(key); 1935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_EQ(1, count); 1945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao iter = hashTable->find(key); 1955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_TRUE(iter == hashTable->end()); 1965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 19722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao EXPECT_TRUE(80 == hashTable->numOfEntries()); 1985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 19937b74a387bb3993387029859c2d9d051c41c724eStephen Hines for (unsigned int key = 20; key < 100; ++key) { 2005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao iter = hashTable->find(key); 2015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_TRUE(iter != hashTable->end()); 2025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 20437b74a387bb3993387029859c2d9d051c41c724eStephen Hines for (unsigned int key = 0; key < 20; ++key) { 2052bf3f881f79c4d883f379e63725e788c310739a3Pirama Arumuga Nainar hashTable->insert(key, exist); 2065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 20722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao EXPECT_TRUE(100 == hashTable->numOfEntries()); 20822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao EXPECT_TRUE(197 == hashTable->numOfBuckets()); 2095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao delete hashTable; 2115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 2125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 21337b74a387bb3993387029859c2d9d051c41c724eStephen HinesTEST_F(HashTableTest, rehash_test) { 2145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashEntry<int, int, IntCompare> HashEntryType; 21537b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > 21637b74a387bb3993387029859c2d9d051c41c724eStephen Hines HashTableTy; 21737b74a387bb3993387029859c2d9d051c41c724eStephen Hines HashTableTy* hashTable = new HashTableTy(0); 2185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool exist; 2205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::entry_type* entry = 0; 22137b74a387bb3993387029859c2d9d051c41c724eStephen Hines for (unsigned int key = 0; key < 400000; ++key) { 2225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao entry = hashTable->insert(key, exist); 22337b74a387bb3993387029859c2d9d051c41c724eStephen Hines entry->setValue(key + 10); 2245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::iterator iter; 22737b74a387bb3993387029859c2d9d051c41c724eStephen Hines for (int key = 0; key < 400000; ++key) { 2285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao iter = hashTable->find(key); 22937b74a387bb3993387029859c2d9d051c41c724eStephen Hines EXPECT_EQ((key + 10), iter.getEntry()->value()); 2305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao delete hashTable; 2335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 2345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 23537b74a387bb3993387029859c2d9d051c41c724eStephen HinesTEST_F(HashTableTest, bucket_iterator) { 2365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashEntry<int, int, IntCompare> HashEntryType; 23737b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > 23837b74a387bb3993387029859c2d9d051c41c724eStephen Hines HashTableTy; 23937b74a387bb3993387029859c2d9d051c41c724eStephen Hines HashTableTy* hashTable = new HashTableTy(0); 2405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool exist; 2425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::entry_type* entry = 0; 24337b74a387bb3993387029859c2d9d051c41c724eStephen Hines for (unsigned int key = 0; key < 400000; ++key) { 2445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao entry = hashTable->insert(key, exist); 24537b74a387bb3993387029859c2d9d051c41c724eStephen Hines entry->setValue(key + 10); 2465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::iterator iter, iEnd = hashTable->end(); 24922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao int counter = 0; 2505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for (iter = hashTable->begin(); iter != iEnd; ++iter) { 25137b74a387bb3993387029859c2d9d051c41c724eStephen Hines EXPECT_EQ(iter.getEntry()->key() + 10, iter.getEntry()->value()); 2525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++counter; 2535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_EQ(400000, counter); 2555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao delete hashTable; 2565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 2575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 25837b74a387bb3993387029859c2d9d051c41c724eStephen HinesTEST_F(HashTableTest, chain_iterator_single) { 2595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashEntry<int, int, IntCompare> HashEntryType; 26037b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > 26137b74a387bb3993387029859c2d9d051c41c724eStephen Hines HashTableTy; 26237b74a387bb3993387029859c2d9d051c41c724eStephen Hines HashTableTy* hashTable = new HashTableTy(); 2635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool exist; 2655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::entry_type* entry = 0; 26637b74a387bb3993387029859c2d9d051c41c724eStephen Hines for (int key = 0; key < 16; ++key) { 26737b74a387bb3993387029859c2d9d051c41c724eStephen Hines entry = hashTable->insert(key * 37, exist); 26837b74a387bb3993387029859c2d9d051c41c724eStephen Hines entry->setValue(key + 10); 2695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 27037b74a387bb3993387029859c2d9d051c41c724eStephen Hines for (int key = 0; key < 16; ++key) { 27122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao int counter = 0; 27237b74a387bb3993387029859c2d9d051c41c724eStephen Hines HashTableTy::chain_iterator iter, iEnd = hashTable->end(key * 37); 27337b74a387bb3993387029859c2d9d051c41c724eStephen Hines for (iter = hashTable->begin(key * 37); iter != iEnd; ++iter) { 27437b74a387bb3993387029859c2d9d051c41c724eStephen Hines EXPECT_EQ(key + 10, iter.getEntry()->value()); 2755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++counter; 2765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao EXPECT_EQ(1, counter); 2785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao delete hashTable; 2805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 2815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 28237b74a387bb3993387029859c2d9d051c41c724eStephen Hinesstruct FixHash { 28337b74a387bb3993387029859c2d9d051c41c724eStephen Hines size_t operator()(int pKey) const { return 10; } 2845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 2855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 28637b74a387bb3993387029859c2d9d051c41c724eStephen HinesTEST_F(HashTableTest, chain_iterator_list) { 2875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef HashEntry<int, int, IntCompare> HashEntryType; 28837b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef HashTable<HashEntryType, FixHash, EntryFactory<HashEntryType> > 28937b74a387bb3993387029859c2d9d051c41c724eStephen Hines HashTableTy; 29037b74a387bb3993387029859c2d9d051c41c724eStephen Hines HashTableTy* hashTable = new HashTableTy(); 2915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool exist; 2935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::entry_type* entry = 0; 29437b74a387bb3993387029859c2d9d051c41c724eStephen Hines for (unsigned int key = 0; key < 16; ++key) { 2955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao entry = hashTable->insert(key, exist); 2965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_FALSE(exist); 2975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao entry->setValue(key); 2985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 29922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ASSERT_TRUE(16 == hashTable->numOfEntries()); 30022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ASSERT_TRUE(37 == hashTable->numOfBuckets()); 3015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao unsigned int key = 0; 30322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao int count = 0; 3045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao HashTableTy::chain_iterator iter, iEnd = hashTable->end(key); 3055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao for (iter = hashTable->begin(key); iter != iEnd; ++iter) { 3065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao count++; 3075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 3085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ASSERT_EQ(16, count); 3095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao delete hashTable; 3105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 311