1//===- HashTableTest.cpp --------------------------------------------------===// 2// 3// The MCLinker Project 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9 10#include "HashTableTest.h" 11#include "mcld/ADT/HashEntry.h" 12#include "mcld/ADT/HashTable.h" 13#include <cstdlib> 14 15using namespace std; 16using namespace mcld; 17using namespace mcldtest; 18 19 20// Constructor can do set-up work for all test here. 21HashTableTest::HashTableTest() 22{ 23} 24 25// Destructor can do clean-up work that doesn't throw exceptions here. 26HashTableTest::~HashTableTest() 27{ 28} 29 30// SetUp() will be called immediately before each test. 31void HashTableTest::SetUp() 32{ 33} 34 35// TearDown() will be called immediately after each test. 36void HashTableTest::TearDown() 37{ 38} 39 40//==========================================================================// 41// Testcases 42// 43struct IntCompare 44{ 45 bool operator()(int X, int Y) const 46 { return (X==Y); } 47}; 48 49struct PtrCompare 50{ 51 bool operator()(const int* X, const int* Y) const 52 { return (X==Y); } 53}; 54 55struct PtrHash 56{ 57 size_t operator()(const int* pKey) const 58 { 59 return (unsigned((uintptr_t)pKey) >> 4) ^ 60 (unsigned((uintptr_t)pKey) >> 9); 61 } 62}; 63 64struct IntHash 65{ 66 size_t operator()(int pKey) const 67 { return pKey; } 68}; 69 70struct IntMod3Hash 71{ 72 size_t operator()(int pKey) const 73 { return pKey % 3; } 74}; 75 76TEST_F( HashTableTest, ptr_entry ) { 77 int A = 1; 78 int* pA = &A; 79 80 typedef HashEntry<int*, int, PtrCompare> HashEntryType; 81 typedef HashTable<HashEntryType, PtrHash, EntryFactory<HashEntryType> > HashTableTy; 82 HashTableTy *hashTable = new HashTableTy(0); 83 84 bool exist; 85 HashTableTy::entry_type* entry = 0; 86 87 entry = hashTable->insert(pA, exist); 88 89 EXPECT_FALSE(hashTable->empty()); 90 91 HashTableTy::iterator iter; 92 iter = hashTable->find(NULL); 93 EXPECT_TRUE(iter==hashTable->end()); 94 delete hashTable; 95} 96 97TEST_F( HashTableTest, constructor ) { 98 typedef HashEntry<int, int, IntCompare> HashEntryType; 99 HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > hashTable(16); 100 EXPECT_TRUE(17 == hashTable.numOfBuckets()); 101 EXPECT_TRUE(hashTable.empty()); 102 EXPECT_TRUE(0 == hashTable.numOfEntries()); 103} 104 105TEST_F( HashTableTest, allocattion ) { 106 typedef HashEntry<int, int, IntCompare> HashEntryType; 107 typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy; 108 HashTableTy *hashTable = new HashTableTy(22); 109 110 bool exist; 111 int key = 100; 112 HashTableTy::entry_type* val = hashTable->insert(key, exist); 113 val->setValue(999); 114 EXPECT_FALSE(hashTable->empty()); 115 EXPECT_FALSE(exist); 116 EXPECT_FALSE(NULL == val); 117 HashTableTy::iterator entry = hashTable->find(key); 118 EXPECT_EQ(999, entry.getEntry()->value()); 119 delete hashTable; 120} 121 122TEST_F( HashTableTest, alloc100 ) { 123 typedef HashEntry<int, int, IntCompare> HashEntryType; 124 typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy; 125 HashTableTy *hashTable = new HashTableTy(22); 126 127 bool exist; 128 HashTableTy::entry_type* entry = 0; 129 for (int key=0; key<100; ++key) { 130 entry = hashTable->insert(key, exist); 131 EXPECT_FALSE(hashTable->empty()); 132 EXPECT_FALSE(exist); 133 EXPECT_FALSE(NULL == entry); 134 EXPECT_TRUE(key == entry->key()); 135 entry->setValue(key+10); 136 } 137 138 EXPECT_FALSE(hashTable->empty()); 139 EXPECT_TRUE(100 == hashTable->numOfEntries()); 140 EXPECT_TRUE(197 == hashTable->numOfBuckets()); 141 delete hashTable; 142} 143 144TEST_F( HashTableTest, erase100 ) { 145 typedef HashEntry<int, int, IntCompare> HashEntryType; 146 typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy; 147 HashTableTy *hashTable = new HashTableTy(0); 148 149 bool exist; 150 HashTableTy::entry_type* entry = 0; 151 for (unsigned int key=0; key<100; ++key) 152 entry = hashTable->insert(key, exist); 153 154 EXPECT_FALSE(hashTable->empty()); 155 156 int count; 157 HashTableTy::iterator iter; 158 for (unsigned int key=0; key<100; ++key) { 159 count = hashTable->erase(key); 160 EXPECT_EQ(1, count); 161 iter = hashTable->find(key); 162 EXPECT_TRUE(iter == hashTable->end()); 163 } 164 165 EXPECT_TRUE(hashTable->empty()); 166 delete hashTable; 167} 168 169TEST_F( HashTableTest, clear) { 170 typedef HashEntry<int, int, IntCompare> HashEntryType; 171 typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy; 172 HashTableTy *hashTable = new HashTableTy(22); 173 174 bool exist; 175 HashTableTy::entry_type* entry = 0; 176 for (unsigned int key=0; key<100; ++key) { 177 entry = hashTable->insert(key, exist); 178 } 179 180 hashTable->clear(); 181 182 HashTableTy::iterator iter; 183 for (unsigned int key=0; key<100; ++key) { 184 iter = hashTable->find(key); 185 EXPECT_TRUE(iter == hashTable->end()); 186 } 187 188 EXPECT_TRUE(hashTable->empty()); 189 delete hashTable; 190} 191 192TEST_F( HashTableTest, tombstone ) { 193 typedef HashEntry<int, int, IntCompare> HashEntryType; 194 typedef HashTable<HashEntryType, IntMod3Hash, EntryFactory<HashEntryType> > HashTableTy; 195 HashTableTy *hashTable = new HashTableTy(); 196 197 bool exist; 198 HashTableTy::entry_type* entry = 0; 199 for (unsigned int key=0; key<100; ++key) { 200 entry = hashTable->insert(key, exist); 201 } 202 EXPECT_FALSE(hashTable->empty()); 203 204 int count; 205 HashTableTy::iterator iter; 206 for (unsigned int key=0; key<20; ++key) { 207 count = hashTable->erase(key); 208 EXPECT_EQ(1, count); 209 iter = hashTable->find(key); 210 EXPECT_TRUE(iter == hashTable->end()); 211 } 212 EXPECT_TRUE(80 == hashTable->numOfEntries()); 213 214 for (unsigned int key=20; key<100; ++key) { 215 iter = hashTable->find(key); 216 EXPECT_TRUE(iter != hashTable->end()); 217 } 218 219 for (unsigned int key=0; key<20; ++key) { 220 entry = hashTable->insert(key, exist); 221 } 222 EXPECT_TRUE(100 == hashTable->numOfEntries()); 223 EXPECT_TRUE(197 == hashTable->numOfBuckets()); 224 225 delete hashTable; 226} 227 228TEST_F( HashTableTest, rehash_test ) { 229 typedef HashEntry<int, int, IntCompare> HashEntryType; 230 typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy; 231 HashTableTy *hashTable = new HashTableTy(0); 232 233 bool exist; 234 HashTableTy::entry_type* entry = 0; 235 for (unsigned int key=0; key<400000; ++key) { 236 entry = hashTable->insert(key, exist); 237 entry->setValue(key+10); 238 } 239 240 HashTableTy::iterator iter; 241 for (int key=0; key<400000; ++key) { 242 iter = hashTable->find(key); 243 EXPECT_EQ((key+10), iter.getEntry()->value()); 244 } 245 246 delete hashTable; 247} 248 249TEST_F( HashTableTest, bucket_iterator ) { 250 typedef HashEntry<int, int, IntCompare> HashEntryType; 251 typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy; 252 HashTableTy *hashTable = new HashTableTy(0); 253 254 bool exist; 255 HashTableTy::entry_type* entry = 0; 256 for (unsigned int key=0; key<400000; ++key) { 257 entry = hashTable->insert(key, exist); 258 entry->setValue(key+10); 259 } 260 261 HashTableTy::iterator iter, iEnd = hashTable->end(); 262 int counter = 0; 263 for (iter = hashTable->begin(); iter != iEnd; ++iter) { 264 EXPECT_EQ(iter.getEntry()->key()+10, iter.getEntry()->value()); 265 ++counter; 266 } 267 EXPECT_EQ(400000, counter); 268 delete hashTable; 269} 270 271 272TEST_F( HashTableTest, chain_iterator_single ) { 273 typedef HashEntry<int, int, IntCompare> HashEntryType; 274 typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy; 275 HashTableTy *hashTable = new HashTableTy(); 276 277 bool exist; 278 HashTableTy::entry_type* entry = 0; 279 for (int key=0; key<16; ++key) { 280 entry = hashTable->insert(key*37, exist); 281 entry->setValue(key+10); 282 } 283 for (int key=0; key<16; ++key) { 284 int counter = 0; 285 HashTableTy::chain_iterator iter, iEnd = hashTable->end(key*37); 286 for (iter = hashTable->begin(key*37); iter != iEnd; ++iter) { 287 EXPECT_EQ(key+10, iter.getEntry()->value()); 288 ++counter; 289 } 290 EXPECT_EQ(1, counter); 291 } 292 delete hashTable; 293} 294 295struct FixHash 296{ 297 size_t operator()(int pKey) const { 298 return 10; 299 } 300}; 301 302 303TEST_F( HashTableTest, chain_iterator_list ) { 304 typedef HashEntry<int, int, IntCompare> HashEntryType; 305 typedef HashTable<HashEntryType, FixHash, EntryFactory<HashEntryType> > HashTableTy; 306 HashTableTy *hashTable = new HashTableTy(); 307 308 bool exist; 309 HashTableTy::entry_type* entry = 0; 310 for (unsigned int key=0; key<16; ++key) { 311 entry = hashTable->insert(key, exist); 312 ASSERT_FALSE(exist); 313 entry->setValue(key); 314 } 315 ASSERT_TRUE(16 == hashTable->numOfEntries()); 316 ASSERT_TRUE(37 == hashTable->numOfBuckets()); 317 318 unsigned int key = 0; 319 int count = 0; 320 HashTableTy::chain_iterator iter, iEnd = hashTable->end(key); 321 for (iter = hashTable->begin(key); iter != iEnd; ++iter) { 322 count++; 323 } 324 ASSERT_EQ(16, count); 325 delete hashTable; 326} 327