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 15 using namespace std; 16 using namespace mcld; 17 using namespace mcldtest; 18 19 20 // Constructor can do set-up work for all test here. 21 HashTableTest::HashTableTest() 22 { 23 } 24 25 // Destructor can do clean-up work that doesn't throw exceptions here. 26 HashTableTest::~HashTableTest() 27 { 28 } 29 30 // SetUp() will be called immediately before each test. 31 void HashTableTest::SetUp() 32 { 33 } 34 35 // TearDown() will be called immediately after each test. 36 void HashTableTest::TearDown() 37 { 38 } 39 40 //==========================================================================// 41 // Testcases 42 // 43 struct IntCompare 44 { 45 bool operator()(int X, int Y) const 46 { return (X==Y); } 47 }; 48 49 struct PtrCompare 50 { 51 bool operator()(const int* X, const int* Y) const 52 { return (X==Y); } 53 }; 54 55 struct 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 64 struct IntHash 65 { 66 size_t operator()(int pKey) const 67 { return pKey; } 68 }; 69 70 struct IntMod3Hash 71 { 72 size_t operator()(int pKey) const 73 { return pKey % 3; } 74 }; 75 76 TEST_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 97 TEST_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 105 TEST_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 122 TEST_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 144 TEST_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 169 TEST_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 192 TEST_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 228 TEST_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 249 TEST_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 272 TEST_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 295 struct FixHash 296 { 297 size_t operator()(int pKey) const { 298 return 10; 299 } 300 }; 301 302 303 TEST_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
