Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame^] | 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_EQ(17, hashTable.numOfBuckets()); |
| 101 | EXPECT_TRUE(hashTable.empty()); |
| 102 | EXPECT_EQ(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 (unsigned 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_EQ(key, entry->key()); |
| 135 | entry->setValue(key+10); |
| 136 | } |
| 137 | |
| 138 | EXPECT_FALSE(hashTable->empty()); |
| 139 | EXPECT_EQ(100, hashTable->numOfEntries()); |
| 140 | EXPECT_EQ(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 | int count; |
| 183 | HashTableTy::iterator iter; |
| 184 | for (unsigned int key=0; key<100; ++key) { |
| 185 | iter = hashTable->find(key); |
| 186 | EXPECT_TRUE(iter == hashTable->end()); |
| 187 | } |
| 188 | |
| 189 | EXPECT_TRUE(hashTable->empty()); |
| 190 | delete hashTable; |
| 191 | } |
| 192 | |
| 193 | TEST_F( HashTableTest, tombstone ) { |
| 194 | typedef HashEntry<int, int, IntCompare> HashEntryType; |
| 195 | typedef HashTable<HashEntryType, IntMod3Hash, EntryFactory<HashEntryType> > HashTableTy; |
| 196 | HashTableTy *hashTable = new HashTableTy(); |
| 197 | |
| 198 | bool exist; |
| 199 | HashTableTy::entry_type* entry = 0; |
| 200 | for (unsigned int key=0; key<100; ++key) { |
| 201 | entry = hashTable->insert(key, exist); |
| 202 | } |
| 203 | EXPECT_FALSE(hashTable->empty()); |
| 204 | |
| 205 | int count; |
| 206 | HashTableTy::iterator iter; |
| 207 | for (unsigned int key=0; key<20; ++key) { |
| 208 | count = hashTable->erase(key); |
| 209 | EXPECT_EQ(1, count); |
| 210 | iter = hashTable->find(key); |
| 211 | EXPECT_TRUE(iter == hashTable->end()); |
| 212 | } |
| 213 | EXPECT_EQ(80, hashTable->numOfEntries()); |
| 214 | |
| 215 | for (unsigned int key=20; key<100; ++key) { |
| 216 | iter = hashTable->find(key); |
| 217 | EXPECT_TRUE(iter != hashTable->end()); |
| 218 | } |
| 219 | |
| 220 | for (unsigned int key=0; key<20; ++key) { |
| 221 | entry = hashTable->insert(key, exist); |
| 222 | } |
| 223 | EXPECT_EQ(100, hashTable->numOfEntries()); |
| 224 | EXPECT_EQ(197, hashTable->numOfBuckets()); |
| 225 | |
| 226 | delete hashTable; |
| 227 | } |
| 228 | |
| 229 | TEST_F( HashTableTest, rehash_test ) { |
| 230 | typedef HashEntry<int, int, IntCompare> HashEntryType; |
| 231 | typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy; |
| 232 | HashTableTy *hashTable = new HashTableTy(0); |
| 233 | |
| 234 | bool exist; |
| 235 | HashTableTy::entry_type* entry = 0; |
| 236 | for (unsigned int key=0; key<400000; ++key) { |
| 237 | entry = hashTable->insert(key, exist); |
| 238 | entry->setValue(key+10); |
| 239 | } |
| 240 | |
| 241 | HashTableTy::iterator iter; |
| 242 | for (unsigned int key=0; key<400000; ++key) { |
| 243 | iter = hashTable->find(key); |
| 244 | EXPECT_EQ((key+10), iter.getEntry()->value()); |
| 245 | } |
| 246 | |
| 247 | delete hashTable; |
| 248 | } |
| 249 | |
| 250 | TEST_F( HashTableTest, bucket_iterator ) { |
| 251 | typedef HashEntry<int, int, IntCompare> HashEntryType; |
| 252 | typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy; |
| 253 | HashTableTy *hashTable = new HashTableTy(0); |
| 254 | |
| 255 | bool exist; |
| 256 | HashTableTy::entry_type* entry = 0; |
| 257 | for (unsigned int key=0; key<400000; ++key) { |
| 258 | entry = hashTable->insert(key, exist); |
| 259 | entry->setValue(key+10); |
| 260 | } |
| 261 | |
| 262 | HashTableTy::iterator iter, iEnd = hashTable->end(); |
| 263 | unsigned int counter = 0; |
| 264 | for (iter = hashTable->begin(); iter != iEnd; ++iter) { |
| 265 | EXPECT_EQ(iter.getEntry()->key()+10, iter.getEntry()->value()); |
| 266 | ++counter; |
| 267 | } |
| 268 | EXPECT_EQ(400000, counter); |
| 269 | delete hashTable; |
| 270 | } |
| 271 | |
| 272 | |
| 273 | TEST_F( HashTableTest, chain_iterator_single ) { |
| 274 | typedef HashEntry<int, int, IntCompare> HashEntryType; |
| 275 | typedef HashTable<HashEntryType, IntHash, EntryFactory<HashEntryType> > HashTableTy; |
| 276 | HashTableTy *hashTable = new HashTableTy(); |
| 277 | |
| 278 | bool exist; |
| 279 | HashTableTy::entry_type* entry = 0; |
| 280 | for (unsigned int key=0; key<16; ++key) { |
| 281 | entry = hashTable->insert(key*37, exist); |
| 282 | entry->setValue(key+10); |
| 283 | } |
| 284 | for (unsigned int key=0; key<16; ++key) { |
| 285 | unsigned int counter = 0; |
| 286 | HashTableTy::chain_iterator iter, iEnd = hashTable->end(key*37); |
| 287 | for (iter = hashTable->begin(key*37); iter != iEnd; ++iter) { |
| 288 | EXPECT_EQ(key+10, iter.getEntry()->value()); |
| 289 | ++counter; |
| 290 | } |
| 291 | EXPECT_EQ(1, counter); |
| 292 | } |
| 293 | delete hashTable; |
| 294 | } |
| 295 | |
| 296 | struct FixHash |
| 297 | { |
| 298 | size_t operator()(int pKey) const { |
| 299 | return 10; |
| 300 | } |
| 301 | }; |
| 302 | |
| 303 | |
| 304 | TEST_F( HashTableTest, chain_iterator_list ) { |
| 305 | typedef HashEntry<int, int, IntCompare> HashEntryType; |
| 306 | typedef HashTable<HashEntryType, FixHash, EntryFactory<HashEntryType> > HashTableTy; |
| 307 | HashTableTy *hashTable = new HashTableTy(); |
| 308 | |
| 309 | bool exist; |
| 310 | HashTableTy::entry_type* entry = 0; |
| 311 | for (unsigned int key=0; key<16; ++key) { |
| 312 | entry = hashTable->insert(key, exist); |
| 313 | ASSERT_FALSE(exist); |
| 314 | entry->setValue(key); |
| 315 | } |
| 316 | ASSERT_EQ(16, hashTable->numOfEntries()); |
| 317 | ASSERT_EQ(37, hashTable->numOfBuckets()); |
| 318 | |
| 319 | unsigned int key = 0; |
| 320 | unsigned int count = 0; |
| 321 | HashTableTy::chain_iterator iter, iEnd = hashTable->end(key); |
| 322 | for (iter = hashTable->begin(key); iter != iEnd; ++iter) { |
| 323 | count++; |
| 324 | } |
| 325 | ASSERT_EQ(16, count); |
| 326 | delete hashTable; |
| 327 | } |