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