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