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.
HashTableTest()20 HashTableTest::HashTableTest() {
21 }
22
23 // Destructor can do clean-up work that doesn't throw exceptions here.
~HashTableTest()24 HashTableTest::~HashTableTest() {
25 }
26
27 // SetUp() will be called immediately before each test.
SetUp()28 void HashTableTest::SetUp() {
29 }
30
31 // TearDown() will be called immediately after each test.
TearDown()32 void HashTableTest::TearDown() {
33 }
34
35 //==========================================================================//
36 // Testcases
37 //
38 struct IntCompare {
operator ()IntCompare39 bool operator()(int X, int Y) const { return (X == Y); }
40 };
41
42 struct PtrCompare {
operator ()PtrCompare43 bool operator()(const int* X, const int* Y) const { return (X == Y); }
44 };
45
46 struct PtrHash {
operator ()PtrHash47 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 {
operator ()IntHash53 size_t operator()(int pKey) const { return pKey; }
54 };
55
56 struct IntMod3Hash {
operator ()IntMod3Hash57 size_t operator()(int pKey) const { return pKey % 3; }
58 };
59
TEST_F(HashTableTest,ptr_entry)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
TEST_F(HashTableTest,constructor)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
TEST_F(HashTableTest,allocattion)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
TEST_F(HashTableTest,alloc100)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
TEST_F(HashTableTest,erase100)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
TEST_F(HashTableTest,clear)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
TEST_F(HashTableTest,tombstone)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
TEST_F(HashTableTest,rehash_test)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
TEST_F(HashTableTest,bucket_iterator)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
TEST_F(HashTableTest,chain_iterator_single)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 {
operator ()FixHash283 size_t operator()(int pKey) const { return 10; }
284 };
285
TEST_F(HashTableTest,chain_iterator_list)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